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