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