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.19 (Berkeley) 09/26/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 if (hashp != NULL) 203 (void)close(hashp->fp); 204 205 error0: 206 free(hashp); 207 errno = save_errno; 208 return (NULL); 209 } 210 211 static int 212 hash_close(dbp) 213 DB *dbp; 214 { 215 int retval; 216 217 if (!dbp) 218 return (ERROR); 219 hashp = (HTAB *)dbp->internal; 220 retval = hdestroy(); 221 free(dbp); 222 return (retval); 223 } 224 225 /************************** LOCAL CREATION ROUTINES **********************/ 226 static HTAB * 227 init_hash(info) 228 HASHINFO *info; 229 { 230 int nelem; 231 232 nelem = 1; 233 hashp->NKEYS = 0; 234 hashp->LORDER = BYTE_ORDER; 235 hashp->BSIZE = DEF_BUCKET_SIZE; 236 hashp->BSHIFT = DEF_BUCKET_SHIFT; 237 hashp->SGSIZE = DEF_SEGSIZE; 238 hashp->SSHIFT = DEF_SEGSIZE_SHIFT; 239 hashp->DSIZE = DEF_DIRSIZE; 240 hashp->FFACTOR = DEF_FFACTOR; 241 hashp->hash = default_hash; 242 bzero(hashp->SPARES, sizeof(hashp->SPARES)); 243 bzero (hashp->BITMAPS, sizeof (hashp->BITMAPS)); 244 245 if (info) { 246 if (info->bsize) { 247 /* Round pagesize up to power of 2 */ 248 hashp->BSHIFT = __log2(info->bsize); 249 hashp->BSIZE = 1 << hashp->BSHIFT; 250 if (hashp->BSIZE > MAX_BSIZE) { 251 errno = EINVAL; 252 return (NULL); 253 } 254 } 255 if (info->ffactor) 256 hashp->FFACTOR = info->ffactor; 257 if (info->hash) 258 hashp->hash = info->hash; 259 if (info->nelem) 260 nelem = info->nelem; 261 if (info->lorder) { 262 if (info->lorder != BIG_ENDIAN && 263 info->lorder != LITTLE_ENDIAN) { 264 errno = EINVAL; 265 return (NULL); 266 } 267 hashp->LORDER = info->lorder; 268 } 269 } 270 /* init_htab should destroy the table and set errno if it fails */ 271 if (init_htab(nelem)) 272 return (NULL); 273 else 274 return (hashp); 275 } 276 /* 277 * This calls alloc_segs which may run out of memory. Alloc_segs will destroy 278 * the table and set errno, so we just pass the error information along. 279 * 280 * Returns 0 on No Error 281 */ 282 static int 283 init_htab(nelem) 284 int nelem; 285 { 286 register int nbuckets, nsegs; 287 int l2; 288 289 /* 290 * Divide number of elements by the fill factor and determine a 291 * desired number of buckets. Allocate space for the next greater 292 * power of two number of buckets. 293 */ 294 nelem = (nelem - 1) / hashp->FFACTOR + 1; 295 296 l2 = __log2(nelem); 297 nbuckets = 1 << l2; 298 nbuckets = MAX(nbuckets, 2); 299 300 hashp->SPARES[l2] = l2 + 1; 301 hashp->SPARES[l2 + 1] = l2 + 1; 302 hashp->OVFL_POINT = l2; 303 hashp->LAST_FREED = 2; 304 305 /* First bitmap page is at: splitpoint l2 page offset 1 */ 306 if (__init_bitmap(OADDR_OF(l2, 1), l2 + 1, 0)) 307 return (-1); 308 309 hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1; 310 hashp->HIGH_MASK = (nbuckets << 1) - 1; 311 hashp->HDRPAGES = ((MAX(sizeof(HASHHDR), MINHDRSIZE) - 1) >> 312 hashp->BSHIFT) + 1; 313 314 nsegs = (nbuckets - 1) / hashp->SGSIZE + 1; 315 nsegs = 1 << __log2(nsegs); 316 317 if (nsegs > hashp->DSIZE) 318 hashp->DSIZE = nsegs; 319 return (alloc_segs(nsegs)); 320 } 321 322 /********************** DESTROY/CLOSE ROUTINES ************************/ 323 324 /* 325 * Flushes any changes to the file if necessary and destroys the hashp 326 * structure, freeing all allocated space. 327 */ 328 static int 329 hdestroy() 330 { 331 int i, save_errno; 332 333 save_errno = 0; 334 335 if (hashp != NULL) { 336 #ifdef HASH_STATISTICS 337 (void)fprintf(stderr, "hdestroy: accesses %ld collisions %ld\n", 338 hash_accesses, hash_collisions); 339 (void)fprintf(stderr, "hdestroy: expansions %ld\n", 340 hash_expansions); 341 (void)fprintf(stderr, "hdestroy: overflows %ld\n", 342 hash_overflows); 343 (void)fprintf(stderr, "keys %ld maxp %d segmentcount %d\n", 344 hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs); 345 346 for (i = 0; i < NCACHED; i++) 347 (void)fprintf(stderr, 348 "spares[%d] = %d\n", i, hashp->SPARES[i]); 349 #endif 350 /* 351 * Call on buffer manager to free buffers, and if required, 352 * write them to disk. 353 */ 354 if (__buf_free(1, hashp->save_file)) 355 save_errno = errno; 356 if (hashp->dir) { 357 free(*hashp->dir); /* Free initial segments */ 358 /* Free extra segments */ 359 while (hashp->exsegs--) 360 free(hashp->dir[--hashp->nsegs]); 361 free(hashp->dir); 362 } 363 if (flush_meta() && !save_errno) 364 save_errno = errno; 365 /* Free Bigmaps */ 366 for (i = 0; i < hashp->nmaps; i++) 367 if (hashp->mapp[i]) 368 free(hashp->mapp[i]); 369 370 if (hashp->fp != -1) 371 (void)close(hashp->fp); 372 free(hashp); 373 hashp = NULL; 374 } 375 if (save_errno) { 376 errno = save_errno; 377 return (ERROR); 378 } 379 return (SUCCESS); 380 } 381 /* 382 * Write modified pages to disk 383 * 384 * Returns: 385 * 0 == OK 386 * -1 ERROR 387 */ 388 static int 389 hash_sync(dbp) 390 const DB *dbp; 391 { 392 if (!dbp) 393 return (ERROR); 394 hashp = (HTAB *)dbp->internal; 395 396 if (!hashp->save_file) 397 return (0); 398 if (__buf_free(0, 1) || flush_meta()) 399 return (ERROR); 400 hashp->new_file = 0; 401 return (0); 402 } 403 404 /* 405 * Returns: 406 * 0 == OK 407 * -1 indicates that errno should be set 408 */ 409 static int 410 flush_meta() 411 { 412 HASHHDR *whdrp; 413 int fp, i, wsize; 414 415 if (!hashp->save_file) 416 return (0); 417 hashp->MAGIC = HASHMAGIC; 418 hashp->VERSION = HASHVERSION; 419 hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY)); 420 421 fp = hashp->fp; 422 whdrp = &hashp->hdr; 423 #if BYTE_ORDER == LITTLE_ENDIAN 424 whdrp = &whdr; 425 swap_header_copy(&hashp->hdr, whdrp); 426 #endif 427 if ((lseek(fp, 0, SEEK_SET) == -1) || 428 ((wsize = write(fp, whdrp, sizeof(HASHHDR))) == -1)) 429 return (-1); 430 else 431 if (wsize != sizeof(HASHHDR)) { 432 errno = EFTYPE; 433 hashp->errno = errno; 434 return (-1); 435 } 436 for (i = 0; i < NCACHED; i++) 437 if (hashp->mapp[i]) 438 if (__put_page((char *)hashp->mapp[i], 439 hashp->BITMAPS[i], 0, 1)) 440 return (-1); 441 return (0); 442 } 443 444 /*******************************SEARCH ROUTINES *****************************/ 445 /* 446 * All the access routines return 447 * 448 * Returns: 449 * 0 on SUCCESS 450 * 1 to indicate an external ERROR (i.e. key not found, etc) 451 * -1 to indicate an internal ERROR (i.e. out of memory, etc) 452 */ 453 static int 454 hash_get(dbp, key, data, flag) 455 const DB *dbp; 456 const DBT *key; 457 DBT *data; 458 u_int flag; 459 { 460 if (flag) { 461 hashp->errno = errno = EINVAL; 462 return (ERROR); 463 } 464 hashp = (HTAB *)dbp->internal; 465 if (hashp->flags & O_WRONLY) { 466 hashp->errno = errno = EPERM; 467 return (ERROR); 468 } 469 return (hash_access(HASH_GET, (DBT *)key, data)); 470 } 471 472 static int 473 hash_put(dbp, key, data, flag) 474 const DB *dbp; 475 const DBT *key, *data; 476 u_int flag; 477 { 478 if (flag && flag != R_NOOVERWRITE) { 479 hashp->errno = errno = EINVAL; 480 return (ERROR); 481 } 482 hashp = (HTAB *)dbp->internal; 483 if ((hashp->flags & O_ACCMODE) == O_RDONLY) { 484 hashp->errno = errno = EPERM; 485 return (ERROR); 486 } 487 return (hash_access(flag == R_NOOVERWRITE ? 488 HASH_PUTNEW : HASH_PUT, (DBT *)key, (DBT *)data)); 489 } 490 491 static int 492 hash_delete(dbp, key, flag) 493 const DB *dbp; 494 const DBT *key; 495 u_int flag; /* Ignored */ 496 { 497 if (flag && flag != R_CURSOR) { 498 hashp->errno = errno = EINVAL; 499 return (ERROR); 500 } 501 hashp = (HTAB *)dbp->internal; 502 if ((hashp->flags & O_ACCMODE) == O_RDONLY) { 503 hashp->errno = errno = EPERM; 504 return (ERROR); 505 } 506 return (hash_access(HASH_DELETE, (DBT *)key, NULL)); 507 } 508 509 /* 510 * Assume that hashp has been set in wrapper routine. 511 */ 512 static int 513 hash_access(action, key, val) 514 ACTION action; 515 DBT *key, *val; 516 { 517 register BUFHEAD *rbufp; 518 BUFHEAD *bufp, *save_bufp; 519 register u_short *bp; 520 register int n, ndx, off, size; 521 register char *kp; 522 u_short pageno; 523 524 #ifdef HASH_STATISTICS 525 hash_accesses++; 526 #endif 527 528 off = hashp->BSIZE; 529 size = key->size; 530 kp = (char *)key->data; 531 rbufp = __get_buf(__call_hash(kp, size), NULL, 0); 532 if (!rbufp) 533 return (ERROR); 534 save_bufp = rbufp; 535 536 /* Pin the bucket chain */ 537 rbufp->flags |= BUF_PIN; 538 for (bp = (u_short *)rbufp->page, n = *bp++, ndx = 1; ndx < n;) 539 if (bp[1] >= REAL_KEY) { 540 /* Real key/data pair */ 541 if (size == off - *bp && 542 bcmp(kp, rbufp->page + *bp, size) == 0) 543 goto found; 544 off = bp[1]; 545 #ifdef HASH_STATISTICS 546 hash_collisions++; 547 #endif 548 bp += 2; 549 ndx += 2; 550 } else if (bp[1] == OVFLPAGE) { 551 rbufp = __get_buf(*bp, rbufp, 0); 552 if (!rbufp) { 553 save_bufp->flags &= ~BUF_PIN; 554 return (ERROR); 555 } 556 /* FOR LOOP INIT */ 557 bp = (u_short *)rbufp->page; 558 n = *bp++; 559 ndx = 1; 560 off = hashp->BSIZE; 561 } else if (bp[1] < REAL_KEY) { 562 if ((ndx = __find_bigpair(rbufp, ndx, kp, size)) > 0) 563 goto found; 564 if (ndx == -2) { 565 bufp = rbufp; 566 if (!(pageno = __find_last_page(&bufp))) { 567 ndx = 0; 568 rbufp = bufp; 569 break; /* FOR */ 570 } 571 rbufp = __get_buf(pageno, bufp, 0); 572 if (!rbufp) { 573 save_bufp->flags &= ~BUF_PIN; 574 return (ERROR); 575 } 576 /* FOR LOOP INIT */ 577 bp = (u_short *)rbufp->page; 578 n = *bp++; 579 ndx = 1; 580 off = hashp->BSIZE; 581 } else { 582 save_bufp->flags &= ~BUF_PIN; 583 return (ERROR); 584 } 585 } 586 587 /* Not found */ 588 switch (action) { 589 case HASH_PUT: 590 case HASH_PUTNEW: 591 if (__addel(rbufp, key, val)) { 592 save_bufp->flags &= ~BUF_PIN; 593 return (ERROR); 594 } else { 595 save_bufp->flags &= ~BUF_PIN; 596 return (SUCCESS); 597 } 598 case HASH_GET: 599 case HASH_DELETE: 600 default: 601 save_bufp->flags &= ~BUF_PIN; 602 return (ABNORMAL); 603 } 604 605 found: 606 switch (action) { 607 case HASH_PUTNEW: 608 save_bufp->flags &= ~BUF_PIN; 609 return (ABNORMAL); 610 case HASH_GET: 611 bp = (u_short *)rbufp->page; 612 if (bp[ndx + 1] < REAL_KEY) { 613 if (__big_return(rbufp, ndx, val, 0)) 614 return (ERROR); 615 } else { 616 val->data = (u_char *)rbufp->page + (int)bp[ndx + 1]; 617 val->size = bp[ndx] - bp[ndx + 1]; 618 } 619 break; 620 case HASH_PUT: 621 if ((__delpair(rbufp, ndx)) || (__addel(rbufp, key, val))) { 622 save_bufp->flags &= ~BUF_PIN; 623 return (ERROR); 624 } 625 break; 626 case HASH_DELETE: 627 if (__delpair(rbufp, ndx)) 628 return (ERROR); 629 break; 630 } 631 save_bufp->flags &= ~BUF_PIN; 632 return (SUCCESS); 633 } 634 635 static int 636 hash_seq(dbp, key, data, flag) 637 const DB *dbp; 638 DBT *key, *data; 639 u_int flag; 640 { 641 register u_int bucket; 642 register BUFHEAD *bufp; 643 u_short *bp, ndx; 644 645 if (flag && flag != R_FIRST && flag != R_NEXT) { 646 hashp->errno = errno = EINVAL; 647 return (ERROR); 648 } 649 hashp = (HTAB *)dbp->internal; 650 if (hashp->flags & O_WRONLY) { 651 hashp->errno = errno = EPERM; 652 return (ERROR); 653 } 654 #ifdef HASH_STATISTICS 655 hash_accesses++; 656 #endif 657 if ((hashp->cbucket < 0) || (flag == R_FIRST)) { 658 hashp->cbucket = 0; 659 hashp->cndx = 1; 660 hashp->cpage = NULL; 661 } 662 if (!(bufp = hashp->cpage)) { 663 for (bucket = hashp->cbucket; bucket <= hashp->MAX_BUCKET; 664 bucket++, hashp->cndx = 1) { 665 666 bufp = __get_buf(bucket, NULL, 0); 667 if (!bufp) 668 return (ERROR); 669 hashp->cpage = bufp; 670 bp = (u_short *)bufp->page; 671 if (bp[0]) 672 break; 673 } 674 hashp->cbucket = bucket; 675 if (hashp->cbucket > hashp->MAX_BUCKET) { 676 hashp->cbucket = -1; 677 return (ABNORMAL); 678 } 679 } else 680 bp = (u_short *)hashp->cpage->page; 681 682 #ifdef DEBUG 683 assert(bp); 684 assert(bufp); 685 #endif 686 while (bp[hashp->cndx + 1] == OVFLPAGE) { 687 bufp = hashp->cpage = __get_buf(bp[hashp->cndx], bufp, 0); 688 if (!bufp) 689 return (ERROR); 690 bp = (u_short *)(bufp->page); 691 hashp->cndx = 1; 692 } 693 ndx = hashp->cndx; 694 if (bp[ndx + 1] < REAL_KEY) { 695 if (__big_keydata(bufp, key, data, 1)) 696 return (ERROR); 697 } else { 698 key->data = (u_char *)hashp->cpage->page + bp[ndx]; 699 key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx]; 700 data->data = (u_char *)hashp->cpage->page + bp[ndx + 1]; 701 data->size = bp[ndx] - bp[ndx + 1]; 702 ndx += 2; 703 if (ndx > bp[0]) { 704 hashp->cpage = NULL; 705 hashp->cbucket++; 706 hashp->cndx = 1; 707 } else 708 hashp->cndx = ndx; 709 } 710 return (SUCCESS); 711 } 712 713 /********************************* UTILITIES ************************/ 714 715 /* 716 * Returns: 717 * 0 ==> OK 718 * -1 ==> Error 719 */ 720 extern int 721 __expand_table() 722 { 723 u_int old_bucket, new_bucket; 724 int dirsize, new_segnum, spare_ndx; 725 726 #ifdef HASH_STATISTICS 727 hash_expansions++; 728 #endif 729 new_bucket = ++hashp->MAX_BUCKET; 730 old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK); 731 732 new_segnum = new_bucket >> hashp->SSHIFT; 733 734 /* Check if we need a new segment */ 735 if (new_segnum >= hashp->nsegs) { 736 /* Check if we need to expand directory */ 737 if (new_segnum >= hashp->DSIZE) { 738 /* Reallocate directory */ 739 dirsize = hashp->DSIZE * sizeof(SEGMENT *); 740 if (!hash_realloc(&hashp->dir, dirsize, dirsize << 1)) 741 return (-1); 742 hashp->DSIZE = dirsize << 1; 743 } 744 if (!(hashp->dir[new_segnum] = 745 calloc(hashp->SGSIZE, sizeof(SEGMENT)))) 746 return (-1); 747 hashp->exsegs++; 748 hashp->nsegs++; 749 } 750 /* 751 * If the split point is increasing (MAX_BUCKET's log base 2 752 * * increases), we need to copy the current contents of the spare 753 * split bucket to the next bucket. 754 */ 755 spare_ndx = __log2(hashp->MAX_BUCKET); 756 if ( spare_ndx > hashp->OVFL_POINT ) { 757 hashp->SPARES[spare_ndx] = hashp->SPARES[hashp->OVFL_POINT]; 758 hashp->OVFL_POINT = spare_ndx; 759 } 760 761 if (new_bucket > hashp->HIGH_MASK) { 762 /* Starting a new doubling */ 763 hashp->LOW_MASK = hashp->HIGH_MASK; 764 hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK; 765 } 766 /* Relocate records to the new bucket */ 767 return (__split_page(old_bucket, new_bucket)); 768 } 769 770 /* 771 * If realloc guarantees that the pointer is not destroyed if the realloc 772 * fails, then this routine can go away. 773 */ 774 static void * 775 hash_realloc(p_ptr, oldsize, newsize) 776 SEGMENT **p_ptr; 777 int oldsize, newsize; 778 { 779 register void *p; 780 781 if (p = malloc(newsize)) { 782 bcopy(*p_ptr, p, oldsize); 783 bzero(*p_ptr + oldsize, newsize - oldsize); 784 free(*p_ptr); 785 *p_ptr = p; 786 } 787 return (p); 788 } 789 790 extern u_int 791 __call_hash(k, len) 792 char *k; 793 int len; 794 { 795 int n, bucket; 796 797 n = hashp->hash(k, len); 798 bucket = n & hashp->HIGH_MASK; 799 if (bucket > hashp->MAX_BUCKET) 800 bucket = bucket & hashp->LOW_MASK; 801 return (bucket); 802 } 803 804 /* 805 * Allocate segment table. On error, destroy the table and set errno. 806 * 807 * Returns 0 on success 808 */ 809 static int 810 alloc_segs(nsegs) 811 int nsegs; 812 { 813 register int i; 814 register SEGMENT store; 815 816 int save_errno; 817 818 if (!(hashp->dir = calloc(hashp->DSIZE, sizeof(SEGMENT *)))) { 819 save_errno = errno; 820 (void)hdestroy(); 821 errno = save_errno; 822 return (-1); 823 } 824 /* Allocate segments */ 825 store = calloc(nsegs << hashp->SSHIFT, sizeof(SEGMENT)); 826 if (!store) { 827 save_errno = errno; 828 (void)hdestroy(); 829 errno = save_errno; 830 return (-1); 831 } 832 for (i = 0; i < nsegs; i++, hashp->nsegs++) 833 hashp->dir[i] = &store[i << hashp->SSHIFT]; 834 return (0); 835 } 836 837 #if BYTE_ORDER == LITTLE_ENDIAN 838 /* 839 * Hashp->hdr needs to be byteswapped. 840 */ 841 static void 842 swap_header_copy(srcp, destp) 843 HASHHDR *srcp, *destp; 844 { 845 int i; 846 847 BLSWAP_COPY(srcp->magic, destp->magic); 848 BLSWAP_COPY(srcp->version, destp->version); 849 BLSWAP_COPY(srcp->lorder, destp->lorder); 850 BLSWAP_COPY(srcp->bsize, destp->bsize); 851 BLSWAP_COPY(srcp->bshift, destp->bshift); 852 BLSWAP_COPY(srcp->dsize, destp->dsize); 853 BLSWAP_COPY(srcp->ssize, destp->ssize); 854 BLSWAP_COPY(srcp->sshift, destp->sshift); 855 BLSWAP_COPY(srcp->ovfl_point, destp->ovfl_point); 856 BLSWAP_COPY(srcp->last_freed, destp->last_freed); 857 BLSWAP_COPY(srcp->max_bucket, destp->max_bucket); 858 BLSWAP_COPY(srcp->high_mask, destp->high_mask); 859 BLSWAP_COPY(srcp->low_mask, destp->low_mask); 860 BLSWAP_COPY(srcp->ffactor, destp->ffactor); 861 BLSWAP_COPY(srcp->nkeys, destp->nkeys); 862 BLSWAP_COPY(srcp->hdrpages, destp->hdrpages); 863 BLSWAP_COPY(srcp->h_charkey, destp->h_charkey); 864 for (i = 0; i < NCACHED; i++) { 865 BLSWAP_COPY(srcp->spares[i], destp->spares[i]); 866 BSSWAP_COPY(srcp->bitmaps[i], destp->bitmaps[i]); 867 } 868 } 869 870 static void 871 swap_header() 872 { 873 HASHHDR *hdrp; 874 int i; 875 876 hdrp = &hashp->hdr; 877 878 BLSWAP(hdrp->magic); 879 BLSWAP(hdrp->version); 880 BLSWAP(hdrp->lorder); 881 BLSWAP(hdrp->bsize); 882 BLSWAP(hdrp->bshift); 883 BLSWAP(hdrp->dsize); 884 BLSWAP(hdrp->ssize); 885 BLSWAP(hdrp->sshift); 886 BLSWAP(hdrp->ovfl_point); 887 BLSWAP(hdrp->last_freed); 888 BLSWAP(hdrp->max_bucket); 889 BLSWAP(hdrp->high_mask); 890 BLSWAP(hdrp->low_mask); 891 BLSWAP(hdrp->ffactor); 892 BLSWAP(hdrp->nkeys); 893 BLSWAP(hdrp->hdrpages); 894 BLSWAP(hdrp->h_charkey); 895 for (i = 0; i < NCACHED; i++) { 896 BLSWAP(hdrp->spares[i]); 897 BSSWAP(hdrp->bitmaps[i]); 898 } 899 } 900 #endif 901