1 /*- 2 * Copyright (c) 1990 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Margo Seltzer. 7 * 8 * %sccs.include.redist.c% 9 */ 10 11 #if defined(LIBC_SCCS) && !defined(lint) 12 static char sccsid[] = "@(#)hash.c 5.18 (Berkeley) 09/11/91"; 13 #endif /* LIBC_SCCS and not lint */ 14 15 #include <sys/param.h> 16 #include <sys/stat.h> 17 #include <fcntl.h> 18 #include <errno.h> 19 #ifdef DEBUG 20 #include <assert.h> 21 #endif 22 #include <db.h> 23 #include <stdio.h> 24 #include <stdlib.h> 25 #include <unistd.h> 26 #include <string.h> 27 #include "hash.h" 28 #include "page.h" 29 #include "extern.h" 30 31 static int alloc_segs __P((int)); 32 static int flush_meta __P((void)); 33 static int hash_access __P((ACTION, DBT *, DBT *)); 34 static int hash_close __P((DB *)); 35 static int hash_delete __P((const DB *, const DBT *, u_int)); 36 static int hash_get __P((const DB *, const DBT *, DBT *, u_int)); 37 static int hash_put __P((const DB *, const DBT *, const DBT *, u_int)); 38 static void *hash_realloc __P((SEGMENT **, int, int)); 39 static int hash_seq __P((const DB *, DBT *, DBT *, u_int)); 40 static int hash_sync __P((const DB *)); 41 static int hdestroy __P((void)); 42 static HTAB *init_hash __P((HASHINFO *)); 43 static int init_htab __P((int)); 44 #if BYTE_ORDER == LITTLE_ENDIAN 45 static void swap_header __P((void)); 46 static void swap_header_copy __P((HASHHDR *, HASHHDR *)); 47 #endif 48 49 /* Fast arithmetic, relying on powers of 2, */ 50 #define MOD(x, y) ((x) & ((y) - 1)) 51 52 #define RETURN_ERROR(ERR, LOC) { save_errno = ERR; goto LOC; } 53 54 /* Return values */ 55 #define SUCCESS (0) 56 #define ERROR (-1) 57 #define ABNORMAL (1) 58 59 /* Local data */ 60 HTAB *hashp = NULL; 61 62 #ifdef HASH_STATISTICS 63 long hash_accesses, hash_collisions, hash_expansions, hash_overflows; 64 #endif 65 66 /************************** INTERFACE ROUTINES ***************************/ 67 /* OPEN/CLOSE */ 68 69 extern DB * 70 __hash_open(file, flags, mode, info) 71 const char *file; 72 int flags, mode; 73 const HASHINFO *info; /* Special directives for create */ 74 { 75 struct stat statbuf; 76 DB *dbp; 77 int bpages, hdrsize, new_table, nsegs, save_errno; 78 79 if (!(hashp = calloc(1, sizeof(HTAB)))) 80 return (NULL); 81 hashp->fp = -1; 82 /* 83 * Select flags relevant to us. Even if user wants write only, we need 84 * to be able to read the actual file, so we need to open it read/write. 85 * But, the field in the hashp structure needs to be accurate so that 86 * we can check accesses. 87 */ 88 hashp->flags = flags = 89 flags & (O_CREAT | O_EXCL | O_RDONLY | O_RDWR | O_TRUNC | O_WRONLY); 90 if (flags & O_WRONLY) 91 flags = (flags & ~O_WRONLY) | O_RDWR; 92 93 new_table = 0; 94 if (!file || (flags & O_TRUNC) || 95 (stat(file, &statbuf) && (errno == ENOENT))) { 96 if (errno == ENOENT) 97 errno = 0; /* Just in case someone looks at errno */ 98 new_table = 1; 99 } 100 if (file) { 101 if ((hashp->fp = open(file, flags, mode)) == -1) 102 RETURN_ERROR(errno, error0); 103 (void)fcntl(hashp->fp, F_SETFD, 1); 104 } 105 if (new_table) { 106 if (!(hashp = init_hash((HASHINFO *)info))) 107 RETURN_ERROR(errno, error1); 108 } else { 109 /* Table already exists */ 110 if (info && info->hash) 111 hashp->hash = info->hash; 112 else 113 hashp->hash = default_hash; 114 115 hdrsize = read(hashp->fp, &hashp->hdr, sizeof(HASHHDR)); 116 #if BYTE_ORDER == LITTLE_ENDIAN 117 swap_header(); 118 #endif 119 if (hdrsize == -1) 120 RETURN_ERROR(errno, error1); 121 if (hdrsize != sizeof(HASHHDR)) 122 RETURN_ERROR(EFTYPE, error1); 123 /* Verify file type, versions and hash function */ 124 if (hashp->MAGIC != HASHMAGIC) 125 RETURN_ERROR(EFTYPE, error1); 126 if (hashp->VERSION != HASHVERSION) 127 RETURN_ERROR(EFTYPE, error1); 128 if (hashp->hash(CHARKEY, sizeof(CHARKEY)) != hashp->H_CHARKEY) 129 RETURN_ERROR(EFTYPE, error1); 130 /* 131 * Figure out how many segments we need. Max_Bucket is the 132 * maximum bucket number, so the number of buckets is 133 * max_bucket + 1. 134 */ 135 nsegs = (hashp->MAX_BUCKET + 1 + hashp->SGSIZE - 1) / 136 hashp->SGSIZE; 137 hashp->nsegs = 0; 138 if (alloc_segs(nsegs)) 139 /* 140 * If alloc_segs fails, table will have been destroyed 141 * and errno will have been set. 142 */ 143 return (NULL); 144 /* Read in bitmaps */ 145 bpages = (hashp->SPARES[hashp->OVFL_POINT] + 146 (hashp->BSIZE << BYTE_SHIFT) - 1) >> 147 (hashp->BSHIFT + BYTE_SHIFT); 148 149 hashp->nmaps = bpages; 150 (void)memset(&hashp->mapp[0], 0, bpages * sizeof(u_long *)); 151 } 152 153 /* Initialize Buffer Manager */ 154 if (info && info->cachesize) 155 __buf_init(info->cachesize); 156 else 157 __buf_init(DEF_BUFSIZE); 158 159 hashp->new_file = new_table; 160 hashp->save_file = file && (hashp->flags & (O_WRONLY | O_RDWR)); 161 hashp->cbucket = -1; 162 if (!(dbp = malloc(sizeof(DB)))) { 163 save_errno = errno; 164 hdestroy(); 165 errno = save_errno; 166 return (NULL); 167 } 168 dbp->internal = (char *)hashp; 169 dbp->close = hash_close; 170 dbp->del = hash_delete; 171 dbp->get = hash_get; 172 dbp->put = hash_put; 173 dbp->seq = hash_seq; 174 dbp->sync = hash_sync; 175 dbp->type = DB_HASH; 176 177 #ifdef DEBUG 178 (void)fprintf(stderr, 179 "%s\n%s%x\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%x\n%s%x\n%s%d\n%s%d\n", 180 "init_htab:", 181 "TABLE POINTER ", hashp, 182 "BUCKET SIZE ", hashp->BSIZE, 183 "BUCKET SHIFT ", hashp->BSHIFT, 184 "DIRECTORY SIZE ", hashp->DSIZE, 185 "SEGMENT SIZE ", hashp->SGSIZE, 186 "SEGMENT SHIFT ", hashp->SSHIFT, 187 "FILL FACTOR ", hashp->FFACTOR, 188 "MAX BUCKET ", hashp->MAX_BUCKET, 189 "OVFL POINT ", hashp->OVFL_POINT, 190 "LAST FREED ", hashp->LAST_FREED, 191 "HIGH MASK ", hashp->HIGH_MASK, 192 "LOW MASK ", hashp->LOW_MASK, 193 "NSEGS ", hashp->nsegs, 194 "NKEYS ", hashp->NKEYS); 195 #endif 196 #ifdef HASH_STATISTICS 197 hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0; 198 #endif 199 return (dbp); 200 201 error1: 202 (void)close(hashp->fp); 203 204 error0: 205 free(hashp); 206 errno = save_errno; 207 return (NULL); 208 } 209 210 static int 211 hash_close(dbp) 212 DB *dbp; 213 { 214 int retval; 215 216 if (!dbp) 217 return (ERROR); 218 hashp = (HTAB *)dbp->internal; 219 retval = hdestroy(); 220 free(dbp); 221 return (retval); 222 } 223 224 /************************** LOCAL CREATION ROUTINES **********************/ 225 static HTAB * 226 init_hash(info) 227 HASHINFO *info; 228 { 229 int nelem; 230 231 nelem = 1; 232 hashp->NKEYS = 0; 233 hashp->LORDER = BYTE_ORDER; 234 hashp->BSIZE = DEF_BUCKET_SIZE; 235 hashp->BSHIFT = DEF_BUCKET_SHIFT; 236 hashp->SGSIZE = DEF_SEGSIZE; 237 hashp->SSHIFT = DEF_SEGSIZE_SHIFT; 238 hashp->DSIZE = DEF_DIRSIZE; 239 hashp->FFACTOR = DEF_FFACTOR; 240 hashp->hash = default_hash; 241 bzero(hashp->SPARES, sizeof(hashp->SPARES)); 242 bzero (hashp->BITMAPS, sizeof (hashp->BITMAPS)); 243 244 if (info) { 245 if (info->bsize) { 246 /* Round pagesize up to power of 2 */ 247 hashp->BSHIFT = __log2(info->bsize); 248 hashp->BSIZE = 1 << hashp->BSHIFT; 249 if (hashp->BSIZE > MAX_BSIZE) { 250 errno = EINVAL; 251 return (NULL); 252 } 253 } 254 if (info->ffactor) 255 hashp->FFACTOR = info->ffactor; 256 if (info->hash) 257 hashp->hash = info->hash; 258 if (info->nelem) 259 nelem = info->nelem; 260 if (info->lorder) { 261 if (info->lorder != BIG_ENDIAN && 262 info->lorder != LITTLE_ENDIAN) { 263 errno = EINVAL; 264 return (NULL); 265 } 266 hashp->LORDER = info->lorder; 267 } 268 } 269 /* init_htab should destroy the table and set errno if it fails */ 270 if (init_htab(nelem)) 271 return (NULL); 272 else 273 return (hashp); 274 } 275 /* 276 * This calls alloc_segs which may run out of memory. Alloc_segs will destroy 277 * the table and set errno, so we just pass the error information along. 278 * 279 * Returns 0 on No Error 280 */ 281 static int 282 init_htab(nelem) 283 int nelem; 284 { 285 register int nbuckets, nsegs; 286 int l2; 287 288 /* 289 * Divide number of elements by the fill factor and determine a 290 * desired number of buckets. Allocate space for the next greater 291 * power of two number of buckets. 292 */ 293 nelem = (nelem - 1) / hashp->FFACTOR + 1; 294 295 l2 = __log2(nelem); 296 nbuckets = 1 << l2; 297 nbuckets = MAX(nbuckets, 2); 298 299 hashp->SPARES[l2] = l2 + 1; 300 hashp->SPARES[l2 + 1] = l2 + 1; 301 hashp->OVFL_POINT = l2; 302 hashp->LAST_FREED = 2; 303 304 /* First bitmap page is at: splitpoint l2 page offset 1 */ 305 if (__init_bitmap(OADDR_OF(l2, 1), l2 + 1, 0)) 306 return (-1); 307 308 hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1; 309 hashp->HIGH_MASK = (nbuckets << 1) - 1; 310 hashp->HDRPAGES = ((MAX(sizeof(HASHHDR), MINHDRSIZE) - 1) >> 311 hashp->BSHIFT) + 1; 312 313 nsegs = (nbuckets - 1) / hashp->SGSIZE + 1; 314 nsegs = 1 << __log2(nsegs); 315 316 if (nsegs > hashp->DSIZE) 317 hashp->DSIZE = nsegs; 318 return (alloc_segs(nsegs)); 319 } 320 321 /********************** DESTROY/CLOSE ROUTINES ************************/ 322 323 /* 324 * Flushes any changes to the file if necessary and destroys the hashp 325 * structure, freeing all allocated space. 326 */ 327 static int 328 hdestroy() 329 { 330 int i, save_errno; 331 332 save_errno = 0; 333 334 if (hashp != NULL) { 335 #ifdef HASH_STATISTICS 336 (void)fprintf(stderr, "hdestroy: accesses %ld collisions %ld\n", 337 hash_accesses, hash_collisions); 338 (void)fprintf(stderr, "hdestroy: expansions %ld\n", 339 hash_expansions); 340 (void)fprintf(stderr, "hdestroy: overflows %ld\n", 341 hash_overflows); 342 (void)fprintf(stderr, "keys %ld maxp %d segmentcount %d\n", 343 hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs); 344 345 for (i = 0; i < NCACHED; i++) 346 (void)fprintf(stderr, 347 "spares[%d] = %d\n", i, hashp->SPARES[i]); 348 #endif 349 /* 350 * Call on buffer manager to free buffers, and if required, 351 * write them to disk. 352 */ 353 if (__buf_free(1, hashp->save_file)) 354 save_errno = errno; 355 if (hashp->dir) { 356 free(*hashp->dir); /* Free initial segments */ 357 /* Free extra segments */ 358 while (hashp->exsegs--) 359 free(hashp->dir[--hashp->nsegs]); 360 free(hashp->dir); 361 } 362 if (flush_meta() && !save_errno) 363 save_errno = errno; 364 /* Free Bigmaps */ 365 for (i = 0; i < hashp->nmaps; i++) 366 if (hashp->mapp[i]) 367 free(hashp->mapp[i]); 368 369 if (hashp->fp != -1) 370 (void)close(hashp->fp); 371 free(hashp); 372 hashp = NULL; 373 } 374 if (save_errno) { 375 errno = save_errno; 376 return (ERROR); 377 } 378 return (SUCCESS); 379 } 380 /* 381 * Write modified pages to disk 382 * 383 * Returns: 384 * 0 == OK 385 * -1 ERROR 386 */ 387 static int 388 hash_sync(dbp) 389 const DB *dbp; 390 { 391 if (!dbp) 392 return (ERROR); 393 hashp = (HTAB *)dbp->internal; 394 395 if (!hashp->save_file) 396 return (0); 397 if (__buf_free(0, 1) || flush_meta()) 398 return (ERROR); 399 hashp->new_file = 0; 400 return (0); 401 } 402 403 /* 404 * Returns: 405 * 0 == OK 406 * -1 indicates that errno should be set 407 */ 408 static int 409 flush_meta() 410 { 411 HASHHDR *whdrp; 412 int fp, i, wsize; 413 414 if (!hashp->save_file) 415 return (0); 416 hashp->MAGIC = HASHMAGIC; 417 hashp->VERSION = HASHVERSION; 418 hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY)); 419 420 fp = hashp->fp; 421 whdrp = &hashp->hdr; 422 #if BYTE_ORDER == LITTLE_ENDIAN 423 whdrp = &whdr; 424 swap_header_copy(&hashp->hdr, whdrp); 425 #endif 426 if ((lseek(fp, 0, SEEK_SET) == -1) || 427 ((wsize = write(fp, whdrp, sizeof(HASHHDR))) == -1)) 428 return (-1); 429 else 430 if (wsize != sizeof(HASHHDR)) { 431 errno = EFTYPE; 432 hashp->errno = errno; 433 return (-1); 434 } 435 for (i = 0; i < NCACHED; i++) 436 if (hashp->mapp[i]) 437 if (__put_page((char *)hashp->mapp[i], 438 hashp->BITMAPS[i], 0, 1)) 439 return (-1); 440 return (0); 441 } 442 443 /*******************************SEARCH ROUTINES *****************************/ 444 /* 445 * All the access routines return 446 * 447 * Returns: 448 * 0 on SUCCESS 449 * 1 to indicate an external ERROR (i.e. key not found, etc) 450 * -1 to indicate an internal ERROR (i.e. out of memory, etc) 451 */ 452 static int 453 hash_get(dbp, key, data, flag) 454 const DB *dbp; 455 const DBT *key; 456 DBT *data; 457 u_int flag; 458 { 459 if (flag) { 460 hashp->errno = errno = EINVAL; 461 return (ERROR); 462 } 463 hashp = (HTAB *)dbp->internal; 464 if (hashp->flags & O_WRONLY) { 465 hashp->errno = errno = EPERM; 466 return (ERROR); 467 } 468 return (hash_access(HASH_GET, (DBT *)key, data)); 469 } 470 471 static int 472 hash_put(dbp, key, data, flag) 473 const DB *dbp; 474 const DBT *key, *data; 475 u_int flag; 476 { 477 if (flag && flag != R_NOOVERWRITE) { 478 hashp->errno = errno = EINVAL; 479 return (ERROR); 480 } 481 hashp = (HTAB *)dbp->internal; 482 if ((hashp->flags & O_ACCMODE) == O_RDONLY) { 483 hashp->errno = errno = EPERM; 484 return (ERROR); 485 } 486 return (hash_access(flag == R_NOOVERWRITE ? 487 HASH_PUTNEW : HASH_PUT, (DBT *)key, (DBT *)data)); 488 } 489 490 static int 491 hash_delete(dbp, key, flag) 492 const DB *dbp; 493 const DBT *key; 494 u_int flag; /* Ignored */ 495 { 496 if (flag && flag != R_CURSOR) { 497 hashp->errno = errno = EINVAL; 498 return (ERROR); 499 } 500 hashp = (HTAB *)dbp->internal; 501 if ((hashp->flags & O_ACCMODE) == O_RDONLY) { 502 hashp->errno = errno = EPERM; 503 return (ERROR); 504 } 505 return (hash_access(HASH_DELETE, (DBT *)key, NULL)); 506 } 507 508 /* 509 * Assume that hashp has been set in wrapper routine. 510 */ 511 static int 512 hash_access(action, key, val) 513 ACTION action; 514 DBT *key, *val; 515 { 516 register BUFHEAD *rbufp; 517 BUFHEAD *bufp, *save_bufp; 518 register u_short *bp; 519 register int n, ndx, off, size; 520 register char *kp; 521 u_short pageno; 522 523 #ifdef HASH_STATISTICS 524 hash_accesses++; 525 #endif 526 527 off = hashp->BSIZE; 528 size = key->size; 529 kp = (char *)key->data; 530 rbufp = __get_buf(__call_hash(kp, size), NULL, 0); 531 if (!rbufp) 532 return (ERROR); 533 save_bufp = rbufp; 534 535 /* Pin the bucket chain */ 536 rbufp->flags |= BUF_PIN; 537 for (bp = (u_short *)rbufp->page, n = *bp++, ndx = 1; ndx < n;) 538 if (bp[1] >= REAL_KEY) { 539 /* Real key/data pair */ 540 if (size == off - *bp && 541 bcmp(kp, rbufp->page + *bp, size) == 0) 542 goto found; 543 off = bp[1]; 544 #ifdef HASH_STATISTICS 545 hash_collisions++; 546 #endif 547 bp += 2; 548 ndx += 2; 549 } else if (bp[1] == OVFLPAGE) { 550 rbufp = __get_buf(*bp, rbufp, 0); 551 if (!rbufp) { 552 save_bufp->flags &= ~BUF_PIN; 553 return (ERROR); 554 } 555 /* FOR LOOP INIT */ 556 bp = (u_short *)rbufp->page; 557 n = *bp++; 558 ndx = 1; 559 off = hashp->BSIZE; 560 } else if (bp[1] < REAL_KEY) { 561 if ((ndx = __find_bigpair(rbufp, ndx, kp, size)) > 0) 562 goto found; 563 if (ndx == -2) { 564 bufp = rbufp; 565 if (!(pageno = __find_last_page(&bufp))) { 566 ndx = 0; 567 rbufp = bufp; 568 break; /* FOR */ 569 } 570 rbufp = __get_buf(pageno, bufp, 0); 571 if (!rbufp) { 572 save_bufp->flags &= ~BUF_PIN; 573 return (ERROR); 574 } 575 /* FOR LOOP INIT */ 576 bp = (u_short *)rbufp->page; 577 n = *bp++; 578 ndx = 1; 579 off = hashp->BSIZE; 580 } else { 581 save_bufp->flags &= ~BUF_PIN; 582 return (ERROR); 583 } 584 } 585 586 /* Not found */ 587 switch (action) { 588 case HASH_PUT: 589 case HASH_PUTNEW: 590 if (__addel(rbufp, key, val)) { 591 save_bufp->flags &= ~BUF_PIN; 592 return (ERROR); 593 } else { 594 save_bufp->flags &= ~BUF_PIN; 595 return (SUCCESS); 596 } 597 case HASH_GET: 598 case HASH_DELETE: 599 default: 600 save_bufp->flags &= ~BUF_PIN; 601 return (ABNORMAL); 602 } 603 604 found: 605 switch (action) { 606 case HASH_PUTNEW: 607 save_bufp->flags &= ~BUF_PIN; 608 return (ABNORMAL); 609 case HASH_GET: 610 bp = (u_short *)rbufp->page; 611 if (bp[ndx + 1] < REAL_KEY) { 612 if (__big_return(rbufp, ndx, val, 0)) 613 return (ERROR); 614 } else { 615 val->data = (u_char *)rbufp->page + (int)bp[ndx + 1]; 616 val->size = bp[ndx] - bp[ndx + 1]; 617 } 618 break; 619 case HASH_PUT: 620 if ((__delpair(rbufp, ndx)) || (__addel(rbufp, key, val))) { 621 save_bufp->flags &= ~BUF_PIN; 622 return (ERROR); 623 } 624 break; 625 case HASH_DELETE: 626 if (__delpair(rbufp, ndx)) 627 return (ERROR); 628 break; 629 } 630 save_bufp->flags &= ~BUF_PIN; 631 return (SUCCESS); 632 } 633 634 static int 635 hash_seq(dbp, key, data, flag) 636 const DB *dbp; 637 DBT *key, *data; 638 u_int flag; 639 { 640 register u_int bucket; 641 register BUFHEAD *bufp; 642 u_short *bp, ndx; 643 644 if (flag && flag != R_FIRST && flag != R_NEXT) { 645 hashp->errno = errno = EINVAL; 646 return (ERROR); 647 } 648 hashp = (HTAB *)dbp->internal; 649 if (hashp->flags & O_WRONLY) { 650 hashp->errno = errno = EPERM; 651 return (ERROR); 652 } 653 #ifdef HASH_STATISTICS 654 hash_accesses++; 655 #endif 656 if ((hashp->cbucket < 0) || (flag == R_FIRST)) { 657 hashp->cbucket = 0; 658 hashp->cndx = 1; 659 hashp->cpage = NULL; 660 } 661 if (!(bufp = hashp->cpage)) { 662 for (bucket = hashp->cbucket; bucket <= hashp->MAX_BUCKET; 663 bucket++, hashp->cndx = 1) { 664 665 bufp = __get_buf(bucket, NULL, 0); 666 if (!bufp) 667 return (ERROR); 668 hashp->cpage = bufp; 669 bp = (u_short *)bufp->page; 670 if (bp[0]) 671 break; 672 } 673 hashp->cbucket = bucket; 674 if (hashp->cbucket > hashp->MAX_BUCKET) { 675 hashp->cbucket = -1; 676 return (ABNORMAL); 677 } 678 } else 679 bp = (u_short *)hashp->cpage->page; 680 681 #ifdef DEBUG 682 assert(bp); 683 assert(bufp); 684 #endif 685 while (bp[hashp->cndx + 1] == OVFLPAGE) { 686 bufp = hashp->cpage = __get_buf(bp[hashp->cndx], bufp, 0); 687 if (!bufp) 688 return (ERROR); 689 bp = (u_short *)(bufp->page); 690 hashp->cndx = 1; 691 } 692 ndx = hashp->cndx; 693 if (bp[ndx + 1] < REAL_KEY) { 694 if (__big_keydata(bufp, key, data, 1)) 695 return (ERROR); 696 } else { 697 key->data = (u_char *)hashp->cpage->page + bp[ndx]; 698 key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx]; 699 data->data = (u_char *)hashp->cpage->page + bp[ndx + 1]; 700 data->size = bp[ndx] - bp[ndx + 1]; 701 ndx += 2; 702 if (ndx > bp[0]) { 703 hashp->cpage = NULL; 704 hashp->cbucket++; 705 hashp->cndx = 1; 706 } else 707 hashp->cndx = ndx; 708 } 709 return (SUCCESS); 710 } 711 712 /********************************* UTILITIES ************************/ 713 714 /* 715 * Returns: 716 * 0 ==> OK 717 * -1 ==> Error 718 */ 719 extern int 720 __expand_table() 721 { 722 u_int old_bucket, new_bucket; 723 int dirsize, new_segnum, spare_ndx; 724 725 #ifdef HASH_STATISTICS 726 hash_expansions++; 727 #endif 728 new_bucket = ++hashp->MAX_BUCKET; 729 old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK); 730 731 new_segnum = new_bucket >> hashp->SSHIFT; 732 733 /* Check if we need a new segment */ 734 if (new_segnum >= hashp->nsegs) { 735 /* Check if we need to expand directory */ 736 if (new_segnum >= hashp->DSIZE) { 737 /* Reallocate directory */ 738 dirsize = hashp->DSIZE * sizeof(SEGMENT *); 739 if (!hash_realloc(&hashp->dir, dirsize, dirsize << 1)) 740 return (-1); 741 hashp->DSIZE = dirsize << 1; 742 } 743 if (!(hashp->dir[new_segnum] = 744 calloc(hashp->SGSIZE, sizeof(SEGMENT)))) 745 return (-1); 746 hashp->exsegs++; 747 hashp->nsegs++; 748 } 749 /* 750 * If the split point is increasing (MAX_BUCKET's log base 2 751 * * increases), we need to copy the current contents of the spare 752 * split bucket to the next bucket. 753 */ 754 spare_ndx = __log2(hashp->MAX_BUCKET); 755 if ( spare_ndx > hashp->OVFL_POINT ) { 756 hashp->SPARES[spare_ndx] = hashp->SPARES[hashp->OVFL_POINT]; 757 hashp->OVFL_POINT = spare_ndx; 758 } 759 760 if (new_bucket > hashp->HIGH_MASK) { 761 /* Starting a new doubling */ 762 hashp->LOW_MASK = hashp->HIGH_MASK; 763 hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK; 764 } 765 /* Relocate records to the new bucket */ 766 return (__split_page(old_bucket, new_bucket)); 767 } 768 769 /* 770 * If realloc guarantees that the pointer is not destroyed if the realloc 771 * fails, then this routine can go away. 772 */ 773 static void * 774 hash_realloc(p_ptr, oldsize, newsize) 775 SEGMENT **p_ptr; 776 int oldsize, newsize; 777 { 778 register void *p; 779 780 if (p = malloc(newsize)) { 781 bcopy(*p_ptr, p, oldsize); 782 bzero(*p_ptr + oldsize, newsize - oldsize); 783 free(*p_ptr); 784 *p_ptr = p; 785 } 786 return (p); 787 } 788 789 extern u_int 790 __call_hash(k, len) 791 char *k; 792 int len; 793 { 794 int n, bucket; 795 796 n = hashp->hash(k, len); 797 bucket = n & hashp->HIGH_MASK; 798 if (bucket > hashp->MAX_BUCKET) 799 bucket = bucket & hashp->LOW_MASK; 800 return (bucket); 801 } 802 803 /* 804 * Allocate segment table. On error, destroy the table and set errno. 805 * 806 * Returns 0 on success 807 */ 808 static int 809 alloc_segs(nsegs) 810 int nsegs; 811 { 812 register int i; 813 register SEGMENT store; 814 815 int save_errno; 816 817 if (!(hashp->dir = calloc(hashp->DSIZE, sizeof(SEGMENT *)))) { 818 save_errno = errno; 819 (void)hdestroy(); 820 errno = save_errno; 821 return (-1); 822 } 823 /* Allocate segments */ 824 store = calloc(nsegs << hashp->SSHIFT, sizeof(SEGMENT)); 825 if (!store) { 826 save_errno = errno; 827 (void)hdestroy(); 828 errno = save_errno; 829 return (-1); 830 } 831 for (i = 0; i < nsegs; i++, hashp->nsegs++) 832 hashp->dir[i] = &store[i << hashp->SSHIFT]; 833 return (0); 834 } 835 836 #if BYTE_ORDER == LITTLE_ENDIAN 837 /* 838 * Hashp->hdr needs to be byteswapped. 839 */ 840 static void 841 swap_header_copy(srcp, destp) 842 HASHHDR *srcp, *destp; 843 { 844 int i; 845 846 BLSWAP_COPY(srcp->magic, destp->magic); 847 BLSWAP_COPY(srcp->version, destp->version); 848 BLSWAP_COPY(srcp->lorder, destp->lorder); 849 BLSWAP_COPY(srcp->bsize, destp->bsize); 850 BLSWAP_COPY(srcp->bshift, destp->bshift); 851 BLSWAP_COPY(srcp->dsize, destp->dsize); 852 BLSWAP_COPY(srcp->ssize, destp->ssize); 853 BLSWAP_COPY(srcp->sshift, destp->sshift); 854 BLSWAP_COPY(srcp->ovfl_point, destp->ovfl_point); 855 BLSWAP_COPY(srcp->last_freed, destp->last_freed); 856 BLSWAP_COPY(srcp->max_bucket, destp->max_bucket); 857 BLSWAP_COPY(srcp->high_mask, destp->high_mask); 858 BLSWAP_COPY(srcp->low_mask, destp->low_mask); 859 BLSWAP_COPY(srcp->ffactor, destp->ffactor); 860 BLSWAP_COPY(srcp->nkeys, destp->nkeys); 861 BLSWAP_COPY(srcp->hdrpages, destp->hdrpages); 862 BLSWAP_COPY(srcp->h_charkey, destp->h_charkey); 863 for (i = 0; i < NCACHED; i++) { 864 BLSWAP_COPY(srcp->spares[i], destp->spares[i]); 865 BSSWAP_COPY(srcp->bitmaps[i], destp->bitmaps[i]); 866 } 867 } 868 869 static void 870 swap_header() 871 { 872 HASHHDR *hdrp; 873 int i; 874 875 hdrp = &hashp->hdr; 876 877 BLSWAP(hdrp->magic); 878 BLSWAP(hdrp->version); 879 BLSWAP(hdrp->lorder); 880 BLSWAP(hdrp->bsize); 881 BLSWAP(hdrp->bshift); 882 BLSWAP(hdrp->dsize); 883 BLSWAP(hdrp->ssize); 884 BLSWAP(hdrp->sshift); 885 BLSWAP(hdrp->ovfl_point); 886 BLSWAP(hdrp->last_freed); 887 BLSWAP(hdrp->max_bucket); 888 BLSWAP(hdrp->high_mask); 889 BLSWAP(hdrp->low_mask); 890 BLSWAP(hdrp->ffactor); 891 BLSWAP(hdrp->nkeys); 892 BLSWAP(hdrp->hdrpages); 893 BLSWAP(hdrp->h_charkey); 894 for (i = 0; i < NCACHED; i++) { 895 BLSWAP(hdrp->spares[i]); 896 BSSWAP(hdrp->bitmaps[i]); 897 } 898 } 899 #endif 900