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