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