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