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