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