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.23 (Berkeley) 05/15/92"; 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 = flags & (O_CREAT | O_EXCL | O_EXLOCK | 89 O_RDONLY | O_RDWR | O_SHLOCK | 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(MAX(nelem, 2)); 297 nbuckets = 1 << l2; 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 #if BYTE_ORDER == LITTLE_ENDIAN 413 HASHHDR whdr; 414 #endif 415 int fp, i, wsize; 416 417 if (!hashp->save_file) 418 return (0); 419 hashp->MAGIC = HASHMAGIC; 420 hashp->VERSION = HASHVERSION; 421 hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY)); 422 423 fp = hashp->fp; 424 whdrp = &hashp->hdr; 425 #if BYTE_ORDER == LITTLE_ENDIAN 426 whdrp = &whdr; 427 swap_header_copy(&hashp->hdr, whdrp); 428 #endif 429 if ((lseek(fp, 0, SEEK_SET) == -1) || 430 ((wsize = write(fp, whdrp, sizeof(HASHHDR))) == -1)) 431 return (-1); 432 else 433 if (wsize != sizeof(HASHHDR)) { 434 errno = EFTYPE; 435 hashp->errno = errno; 436 return (-1); 437 } 438 for (i = 0; i < NCACHED; i++) 439 if (hashp->mapp[i]) 440 if (__put_page((char *)hashp->mapp[i], 441 hashp->BITMAPS[i], 0, 1)) 442 return (-1); 443 return (0); 444 } 445 446 /*******************************SEARCH ROUTINES *****************************/ 447 /* 448 * All the access routines return 449 * 450 * Returns: 451 * 0 on SUCCESS 452 * 1 to indicate an external ERROR (i.e. key not found, etc) 453 * -1 to indicate an internal ERROR (i.e. out of memory, etc) 454 */ 455 static int 456 hash_get(dbp, key, data, flag) 457 const DB *dbp; 458 const DBT *key; 459 DBT *data; 460 u_int flag; 461 { 462 if (flag) { 463 hashp->errno = errno = EINVAL; 464 return (ERROR); 465 } 466 hashp = (HTAB *)dbp->internal; 467 if (hashp->flags & O_WRONLY) { 468 hashp->errno = errno = EPERM; 469 return (ERROR); 470 } 471 return (hash_access(HASH_GET, (DBT *)key, data)); 472 } 473 474 static int 475 hash_put(dbp, key, data, flag) 476 const DB *dbp; 477 const DBT *key, *data; 478 u_int flag; 479 { 480 if (flag && flag != R_NOOVERWRITE) { 481 hashp->errno = errno = EINVAL; 482 return (ERROR); 483 } 484 hashp = (HTAB *)dbp->internal; 485 if ((hashp->flags & O_ACCMODE) == O_RDONLY) { 486 hashp->errno = errno = EPERM; 487 return (ERROR); 488 } 489 return (hash_access(flag == R_NOOVERWRITE ? 490 HASH_PUTNEW : HASH_PUT, (DBT *)key, (DBT *)data)); 491 } 492 493 static int 494 hash_delete(dbp, key, flag) 495 const DB *dbp; 496 const DBT *key; 497 u_int flag; /* Ignored */ 498 { 499 if (flag && flag != R_CURSOR) { 500 hashp->errno = errno = EINVAL; 501 return (ERROR); 502 } 503 hashp = (HTAB *)dbp->internal; 504 if ((hashp->flags & O_ACCMODE) == O_RDONLY) { 505 hashp->errno = errno = EPERM; 506 return (ERROR); 507 } 508 return (hash_access(HASH_DELETE, (DBT *)key, NULL)); 509 } 510 511 /* 512 * Assume that hashp has been set in wrapper routine. 513 */ 514 static int 515 hash_access(action, key, val) 516 ACTION action; 517 DBT *key, *val; 518 { 519 register BUFHEAD *rbufp; 520 BUFHEAD *bufp, *save_bufp; 521 register u_short *bp; 522 register int n, ndx, off, size; 523 register char *kp; 524 u_short pageno; 525 526 #ifdef HASH_STATISTICS 527 hash_accesses++; 528 #endif 529 530 off = hashp->BSIZE; 531 size = key->size; 532 kp = (char *)key->data; 533 rbufp = __get_buf(__call_hash(kp, size), NULL, 0); 534 if (!rbufp) 535 return (ERROR); 536 save_bufp = rbufp; 537 538 /* Pin the bucket chain */ 539 rbufp->flags |= BUF_PIN; 540 for (bp = (u_short *)rbufp->page, n = *bp++, ndx = 1; ndx < n;) 541 if (bp[1] >= REAL_KEY) { 542 /* Real key/data pair */ 543 if (size == off - *bp && 544 bcmp(kp, rbufp->page + *bp, size) == 0) 545 goto found; 546 off = bp[1]; 547 #ifdef HASH_STATISTICS 548 hash_collisions++; 549 #endif 550 bp += 2; 551 ndx += 2; 552 } else if (bp[1] == OVFLPAGE) { 553 rbufp = __get_buf(*bp, rbufp, 0); 554 if (!rbufp) { 555 save_bufp->flags &= ~BUF_PIN; 556 return (ERROR); 557 } 558 /* FOR LOOP INIT */ 559 bp = (u_short *)rbufp->page; 560 n = *bp++; 561 ndx = 1; 562 off = hashp->BSIZE; 563 } else if (bp[1] < REAL_KEY) { 564 if ((ndx = __find_bigpair(rbufp, ndx, kp, size)) > 0) 565 goto found; 566 if (ndx == -2) { 567 bufp = rbufp; 568 if (!(pageno = __find_last_page(&bufp))) { 569 ndx = 0; 570 rbufp = bufp; 571 break; /* FOR */ 572 } 573 rbufp = __get_buf(pageno, bufp, 0); 574 if (!rbufp) { 575 save_bufp->flags &= ~BUF_PIN; 576 return (ERROR); 577 } 578 /* FOR LOOP INIT */ 579 bp = (u_short *)rbufp->page; 580 n = *bp++; 581 ndx = 1; 582 off = hashp->BSIZE; 583 } else { 584 save_bufp->flags &= ~BUF_PIN; 585 return (ERROR); 586 } 587 } 588 589 /* Not found */ 590 switch (action) { 591 case HASH_PUT: 592 case HASH_PUTNEW: 593 if (__addel(rbufp, key, val)) { 594 save_bufp->flags &= ~BUF_PIN; 595 return (ERROR); 596 } else { 597 save_bufp->flags &= ~BUF_PIN; 598 return (SUCCESS); 599 } 600 case HASH_GET: 601 case HASH_DELETE: 602 default: 603 save_bufp->flags &= ~BUF_PIN; 604 return (ABNORMAL); 605 } 606 607 found: 608 switch (action) { 609 case HASH_PUTNEW: 610 save_bufp->flags &= ~BUF_PIN; 611 return (ABNORMAL); 612 case HASH_GET: 613 bp = (u_short *)rbufp->page; 614 if (bp[ndx + 1] < REAL_KEY) { 615 if (__big_return(rbufp, ndx, val, 0)) 616 return (ERROR); 617 } else { 618 val->data = (u_char *)rbufp->page + (int)bp[ndx + 1]; 619 val->size = bp[ndx] - bp[ndx + 1]; 620 } 621 break; 622 case HASH_PUT: 623 if ((__delpair(rbufp, ndx)) || (__addel(rbufp, key, val))) { 624 save_bufp->flags &= ~BUF_PIN; 625 return (ERROR); 626 } 627 break; 628 case HASH_DELETE: 629 if (__delpair(rbufp, ndx)) 630 return (ERROR); 631 break; 632 } 633 save_bufp->flags &= ~BUF_PIN; 634 return (SUCCESS); 635 } 636 637 static int 638 hash_seq(dbp, key, data, flag) 639 const DB *dbp; 640 DBT *key, *data; 641 u_int flag; 642 { 643 register u_int bucket; 644 register BUFHEAD *bufp; 645 u_short *bp, ndx; 646 647 if (flag && flag != R_FIRST && flag != R_NEXT) { 648 hashp->errno = errno = EINVAL; 649 return (ERROR); 650 } 651 hashp = (HTAB *)dbp->internal; 652 if (hashp->flags & O_WRONLY) { 653 hashp->errno = errno = EPERM; 654 return (ERROR); 655 } 656 #ifdef HASH_STATISTICS 657 hash_accesses++; 658 #endif 659 if ((hashp->cbucket < 0) || (flag == R_FIRST)) { 660 hashp->cbucket = 0; 661 hashp->cndx = 1; 662 hashp->cpage = NULL; 663 } 664 if (!(bufp = hashp->cpage)) { 665 for (bucket = hashp->cbucket; bucket <= hashp->MAX_BUCKET; 666 bucket++, hashp->cndx = 1) { 667 668 bufp = __get_buf(bucket, NULL, 0); 669 if (!bufp) 670 return (ERROR); 671 hashp->cpage = bufp; 672 bp = (u_short *)bufp->page; 673 if (bp[0]) 674 break; 675 } 676 hashp->cbucket = bucket; 677 if (hashp->cbucket > hashp->MAX_BUCKET) { 678 hashp->cbucket = -1; 679 return (ABNORMAL); 680 } 681 } else 682 bp = (u_short *)hashp->cpage->page; 683 684 #ifdef DEBUG 685 assert(bp); 686 assert(bufp); 687 #endif 688 while (bp[hashp->cndx + 1] == OVFLPAGE) { 689 bufp = hashp->cpage = __get_buf(bp[hashp->cndx], bufp, 0); 690 if (!bufp) 691 return (ERROR); 692 bp = (u_short *)(bufp->page); 693 hashp->cndx = 1; 694 } 695 ndx = hashp->cndx; 696 if (bp[ndx + 1] < REAL_KEY) { 697 if (__big_keydata(bufp, key, data, 1)) 698 return (ERROR); 699 } else { 700 key->data = (u_char *)hashp->cpage->page + bp[ndx]; 701 key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx]; 702 data->data = (u_char *)hashp->cpage->page + bp[ndx + 1]; 703 data->size = bp[ndx] - bp[ndx + 1]; 704 ndx += 2; 705 if (ndx > bp[0]) { 706 hashp->cpage = NULL; 707 hashp->cbucket++; 708 hashp->cndx = 1; 709 } else 710 hashp->cndx = ndx; 711 } 712 return (SUCCESS); 713 } 714 715 /********************************* UTILITIES ************************/ 716 717 /* 718 * Returns: 719 * 0 ==> OK 720 * -1 ==> Error 721 */ 722 extern int 723 __expand_table() 724 { 725 u_int old_bucket, new_bucket; 726 int dirsize, new_segnum, spare_ndx; 727 728 #ifdef HASH_STATISTICS 729 hash_expansions++; 730 #endif 731 new_bucket = ++hashp->MAX_BUCKET; 732 old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK); 733 734 new_segnum = new_bucket >> hashp->SSHIFT; 735 736 /* Check if we need a new segment */ 737 if (new_segnum >= hashp->nsegs) { 738 /* Check if we need to expand directory */ 739 if (new_segnum >= hashp->DSIZE) { 740 /* Reallocate directory */ 741 dirsize = hashp->DSIZE * sizeof(SEGMENT *); 742 if (!hash_realloc(&hashp->dir, dirsize, dirsize << 1)) 743 return (-1); 744 hashp->DSIZE = dirsize << 1; 745 } 746 if (!(hashp->dir[new_segnum] = 747 calloc(hashp->SGSIZE, sizeof(SEGMENT)))) 748 return (-1); 749 hashp->exsegs++; 750 hashp->nsegs++; 751 } 752 /* 753 * If the split point is increasing (MAX_BUCKET's log base 2 754 * * increases), we need to copy the current contents of the spare 755 * split bucket to the next bucket. 756 */ 757 spare_ndx = __log2(hashp->MAX_BUCKET + 1); 758 if (spare_ndx > hashp->OVFL_POINT) { 759 hashp->SPARES[spare_ndx] = hashp->SPARES[hashp->OVFL_POINT]; 760 hashp->OVFL_POINT = spare_ndx; 761 } 762 763 if (new_bucket > hashp->HIGH_MASK) { 764 /* Starting a new doubling */ 765 hashp->LOW_MASK = hashp->HIGH_MASK; 766 hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK; 767 } 768 /* Relocate records to the new bucket */ 769 return (__split_page(old_bucket, new_bucket)); 770 } 771 772 /* 773 * If realloc guarantees that the pointer is not destroyed if the realloc 774 * fails, then this routine can go away. 775 */ 776 static void * 777 hash_realloc(p_ptr, oldsize, newsize) 778 SEGMENT **p_ptr; 779 int oldsize, newsize; 780 { 781 register void *p; 782 783 if (p = malloc(newsize)) { 784 bcopy(*p_ptr, p, oldsize); 785 bzero(*p_ptr + oldsize, newsize - oldsize); 786 free(*p_ptr); 787 *p_ptr = p; 788 } 789 return (p); 790 } 791 792 extern u_int 793 __call_hash(k, len) 794 char *k; 795 int len; 796 { 797 int n, bucket; 798 799 n = hashp->hash(k, len); 800 bucket = n & hashp->HIGH_MASK; 801 if (bucket > hashp->MAX_BUCKET) 802 bucket = bucket & hashp->LOW_MASK; 803 return (bucket); 804 } 805 806 /* 807 * Allocate segment table. On error, destroy the table and set errno. 808 * 809 * Returns 0 on success 810 */ 811 static int 812 alloc_segs(nsegs) 813 int nsegs; 814 { 815 register int i; 816 register SEGMENT store; 817 818 int save_errno; 819 820 if (!(hashp->dir = calloc(hashp->DSIZE, sizeof(SEGMENT *)))) { 821 save_errno = errno; 822 (void)hdestroy(); 823 errno = save_errno; 824 return (-1); 825 } 826 /* Allocate segments */ 827 store = calloc(nsegs << hashp->SSHIFT, sizeof(SEGMENT)); 828 if (!store) { 829 save_errno = errno; 830 (void)hdestroy(); 831 errno = save_errno; 832 return (-1); 833 } 834 for (i = 0; i < nsegs; i++, hashp->nsegs++) 835 hashp->dir[i] = &store[i << hashp->SSHIFT]; 836 return (0); 837 } 838 839 #if BYTE_ORDER == LITTLE_ENDIAN 840 /* 841 * Hashp->hdr needs to be byteswapped. 842 */ 843 static void 844 swap_header_copy(srcp, destp) 845 HASHHDR *srcp, *destp; 846 { 847 int i; 848 849 BLSWAP_COPY(srcp->magic, destp->magic); 850 BLSWAP_COPY(srcp->version, destp->version); 851 BLSWAP_COPY(srcp->lorder, destp->lorder); 852 BLSWAP_COPY(srcp->bsize, destp->bsize); 853 BLSWAP_COPY(srcp->bshift, destp->bshift); 854 BLSWAP_COPY(srcp->dsize, destp->dsize); 855 BLSWAP_COPY(srcp->ssize, destp->ssize); 856 BLSWAP_COPY(srcp->sshift, destp->sshift); 857 BLSWAP_COPY(srcp->ovfl_point, destp->ovfl_point); 858 BLSWAP_COPY(srcp->last_freed, destp->last_freed); 859 BLSWAP_COPY(srcp->max_bucket, destp->max_bucket); 860 BLSWAP_COPY(srcp->high_mask, destp->high_mask); 861 BLSWAP_COPY(srcp->low_mask, destp->low_mask); 862 BLSWAP_COPY(srcp->ffactor, destp->ffactor); 863 BLSWAP_COPY(srcp->nkeys, destp->nkeys); 864 BLSWAP_COPY(srcp->hdrpages, destp->hdrpages); 865 BLSWAP_COPY(srcp->h_charkey, destp->h_charkey); 866 for (i = 0; i < NCACHED; i++) { 867 BLSWAP_COPY(srcp->spares[i], destp->spares[i]); 868 BSSWAP_COPY(srcp->bitmaps[i], destp->bitmaps[i]); 869 } 870 } 871 872 static void 873 swap_header() 874 { 875 HASHHDR *hdrp; 876 int i; 877 878 hdrp = &hashp->hdr; 879 880 BLSWAP(hdrp->magic); 881 BLSWAP(hdrp->version); 882 BLSWAP(hdrp->lorder); 883 BLSWAP(hdrp->bsize); 884 BLSWAP(hdrp->bshift); 885 BLSWAP(hdrp->dsize); 886 BLSWAP(hdrp->ssize); 887 BLSWAP(hdrp->sshift); 888 BLSWAP(hdrp->ovfl_point); 889 BLSWAP(hdrp->last_freed); 890 BLSWAP(hdrp->max_bucket); 891 BLSWAP(hdrp->high_mask); 892 BLSWAP(hdrp->low_mask); 893 BLSWAP(hdrp->ffactor); 894 BLSWAP(hdrp->nkeys); 895 BLSWAP(hdrp->hdrpages); 896 BLSWAP(hdrp->h_charkey); 897 for (i = 0; i < NCACHED; i++) { 898 BLSWAP(hdrp->spares[i]); 899 BSSWAP(hdrp->bitmaps[i]); 900 } 901 } 902 #endif 903