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