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