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