1 #pragma ident "%Z%%M% %I% %E% SMI" 2 3 4 /*- 5 * Copyright (c) 1990, 1993, 1994 6 * The Regents of the University of California. All rights reserved. 7 * 8 * This code is derived from software contributed to Berkeley by 9 * Margo Seltzer. 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions 13 * are met: 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions and the following disclaimer. 16 * 2. Redistributions in binary form must reproduce the above copyright 17 * notice, this list of conditions and the following disclaimer in the 18 * documentation and/or other materials provided with the distribution. 19 * 3. All advertising materials mentioning features or use of this software 20 * must display the following acknowledgement: 21 * This product includes software developed by the University of 22 * California, Berkeley and its contributors. 23 * 4. Neither the name of the University nor the names of its contributors 24 * may be used to endorse or promote products derived from this software 25 * without specific prior written permission. 26 * 27 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 28 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 29 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 30 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 31 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 32 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 33 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 34 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 35 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 36 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 37 * SUCH DAMAGE. 38 */ 39 40 #if defined(LIBC_SCCS) && !defined(lint) 41 static char sccsid[] = "@(#)hash.c 8.12 (Berkeley) 11/7/95"; 42 #endif /* LIBC_SCCS and not lint */ 43 44 #undef _TS_ERRNO_ 45 #include <sys/param.h> 46 #include <sys/stat.h> 47 48 #include <errno.h> 49 #include <fcntl.h> 50 #include <stdio.h> 51 #include <stdlib.h> 52 #include <string.h> 53 #include <unistd.h> 54 #include <libintl.h> 55 #ifdef DEBUG 56 #include <assert.h> 57 #endif 58 59 #include "db-int.h" 60 #include "hash.h" 61 #include "page.h" 62 #include "extern.h" 63 64 static int32_t flush_meta __P((HTAB *)); 65 static int32_t hash_access __P((HTAB *, ACTION, const DBT *, DBT *)); 66 static int32_t hash_close __P((DB *)); 67 static int32_t hash_delete __P((const DB *, const DBT *, u_int32_t)); 68 static int32_t hash_fd __P((const DB *)); 69 static int32_t hash_get __P((const DB *, const DBT *, DBT *, u_int32_t)); 70 static int32_t hash_put __P((const DB *, DBT *, const DBT *, u_int32_t)); 71 static int32_t hash_seq __P((const DB *, DBT *, DBT *, u_int32_t)); 72 static int32_t hash_sync __P((const DB *, u_int32_t)); 73 static int32_t hdestroy __P((HTAB *)); 74 static int32_t cursor_get __P((const DB *, CURSOR *, DBT *, DBT *, \ 75 u_int32_t)); 76 static int32_t cursor_delete __P((const DB *, CURSOR *, u_int32_t)); 77 static HTAB *init_hash __P((HTAB *, const char *, const HASHINFO *)); 78 static int32_t init_htab __P((HTAB *, int32_t)); 79 #if DB_BYTE_ORDER == DB_LITTLE_ENDIAN 80 static void swap_header __P((HTAB *)); 81 static void swap_header_copy __P((HASHHDR *, HASHHDR *)); 82 #endif 83 static u_int32_t hget_header __P((HTAB *, u_int32_t)); 84 static void hput_header __P((HTAB *)); 85 86 #define RETURN_ERROR(ERR, LOC) { save_errno = ERR; goto LOC; } 87 88 /* Return values */ 89 #define SUCCESS (0) 90 #define ERROR (-1) 91 #define ABNORMAL (1) 92 93 #ifdef HASH_STATISTICS 94 u_int32_t hash_accesses, hash_collisions, hash_expansions, hash_overflows, 95 hash_bigpages; 96 #endif 97 98 /************************** INTERFACE ROUTINES ***************************/ 99 /* OPEN/CLOSE */ 100 101 extern DB * 102 __kdb2_hash_open(file, flags, mode, info, dflags) 103 const char *file; 104 int32_t flags, mode, dflags; 105 const HASHINFO *info; /* Special directives for create */ 106 { 107 struct stat statbuf; 108 DB *dbp; 109 DBT mpool_key; 110 HTAB *hashp; 111 int32_t bpages, csize, new_table, save_errno, specified_file; 112 113 if ((flags & O_ACCMODE) == O_WRONLY) { 114 errno = EINVAL; 115 return (NULL); 116 } 117 if (!(hashp = (HTAB *)calloc(1, sizeof(HTAB)))) { 118 errno = ENOMEM; 119 return (NULL); 120 } 121 hashp->fp = -1; 122 123 /* set this now, before file goes away... */ 124 specified_file = (file != NULL); 125 if (!file) { 126 /* 127 * If we are root and thus have access to /var/run, then use 128 * it, else tempnam(3) will use /var/tmp. 129 */ 130 if (!(file = tempnam("/var/run", NULL))) { 131 /* 132 * No memory here is not the only failure 133 * possibility, but probably the most likely. 134 */ 135 errno = ENOMEM; 136 free(hashp); 137 return(NULL); 138 } 139 140 /* store the file name so that we can unlink it later */ 141 hashp->fname = file; 142 #ifdef DEBUG 143 fprintf(stderr, dgettext(TEXT_DOMAIN, 144 "Using file name %s.\n"), file); 145 #endif 146 } 147 /* 148 * Even if user wants write only, we need to be able to read 149 * the actual file, so we need to open it read/write. But, the 150 * field in the hashp structure needs to be accurate so that 151 * we can check accesses. 152 */ 153 hashp->flags = flags; 154 hashp->save_file = specified_file && (hashp->flags & O_RDWR); 155 156 new_table = 0; 157 if (!file || (flags & O_TRUNC) || 158 (stat(file, &statbuf) && (errno == ENOENT))) { 159 if (errno == ENOENT) 160 errno = 0; /* In case someone looks at errno. */ 161 new_table = 1; 162 } 163 if (file) { 164 if ((hashp->fp = open(file, flags|O_BINARY, mode)) == -1) 165 RETURN_ERROR(errno, error0); 166 (void)fcntl(hashp->fp, F_SETFD, 1); 167 } 168 169 /* Process arguments to set up hash table header. */ 170 if (new_table) { 171 if (!(hashp = init_hash(hashp, file, info))) 172 RETURN_ERROR(errno, error1); 173 } else { 174 /* Table already exists */ 175 if (info && info->hash) 176 hashp->hash = info->hash; 177 else 178 hashp->hash = __default_hash; 179 180 /* copy metadata from page into header */ 181 if (hget_header(hashp, 182 (info && info->bsize ? info->bsize : DEF_BUCKET_SIZE)) != 183 sizeof(HASHHDR)) 184 RETURN_ERROR(EFTYPE, error1); 185 186 /* Verify file type, versions and hash function */ 187 if (hashp->hdr.magic != HASHMAGIC) 188 RETURN_ERROR(EFTYPE, error1); 189 #define OLDHASHVERSION 1 190 if (hashp->hdr.version != HASHVERSION && 191 hashp->hdr.version != OLDHASHVERSION) 192 RETURN_ERROR(EFTYPE, error1); 193 if (hashp->hash(CHARKEY, sizeof(CHARKEY)) 194 != hashp->hdr.h_charkey) 195 RETURN_ERROR(EFTYPE, error1); 196 /* 197 * Figure out how many segments we need. Max_Bucket is the 198 * maximum bucket number, so the number of buckets is 199 * max_bucket + 1. 200 */ 201 202 /* Read in bitmaps */ 203 bpages = (hashp->hdr.spares[hashp->hdr.ovfl_point] + 204 (hashp->hdr.bsize << BYTE_SHIFT) - 1) >> 205 (hashp->hdr.bshift + BYTE_SHIFT); 206 207 hashp->nmaps = bpages; 208 (void)memset(&hashp->mapp[0], 0, bpages * sizeof(u_int32_t *)); 209 } 210 211 /* start up mpool */ 212 mpool_key.data = (u_int8_t *)file; 213 mpool_key.size = strlen(file); 214 215 if (info && info->cachesize) 216 csize = info->cachesize / hashp->hdr.bsize; 217 else 218 csize = DEF_CACHESIZE / hashp->hdr.bsize; 219 hashp->mp = mpool_open(&mpool_key, hashp->fp, hashp->hdr.bsize, csize); 220 221 if (!hashp->mp) 222 RETURN_ERROR(errno, error1); 223 mpool_filter(hashp->mp, __pgin_routine, __pgout_routine, hashp); 224 225 /* 226 * For a new table, set up the bitmaps. 227 */ 228 if (new_table && 229 init_htab(hashp, info && info->nelem ? info->nelem : 1)) 230 goto error2; 231 232 /* initialize the cursor queue */ 233 TAILQ_INIT(&hashp->curs_queue); 234 hashp->seq_cursor = NULL; 235 236 237 /* get a chunk of memory for our split buffer */ 238 hashp->split_buf = (PAGE16 *)malloc(hashp->hdr.bsize); 239 if (!hashp->split_buf) 240 goto error2; 241 242 hashp->new_file = new_table; 243 244 if (!(dbp = (DB *)malloc(sizeof(DB)))) 245 goto error2; 246 247 dbp->internal = hashp; 248 dbp->close = hash_close; 249 dbp->del = hash_delete; 250 dbp->fd = hash_fd; 251 dbp->get = hash_get; 252 dbp->put = hash_put; 253 dbp->seq = hash_seq; 254 dbp->sync = hash_sync; 255 dbp->type = DB_HASH; 256 257 #ifdef DEBUG 258 (void)fprintf(stderr, 259 "%s\n%s%lx\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", 260 "init_htab:", 261 "TABLE POINTER ", (void *)hashp, 262 "BUCKET SIZE ", hashp->hdr.bsize, 263 "BUCKET SHIFT ", hashp->hdr.bshift, 264 "FILL FACTOR ", hashp->hdr.ffactor, 265 "MAX BUCKET ", hashp->hdr.max_bucket, 266 "OVFL POINT ", hashp->hdr.ovfl_point, 267 "LAST FREED ", hashp->hdr.last_freed, 268 "HIGH MASK ", hashp->hdr.high_mask, 269 "LOW MASK ", hashp->hdr.low_mask, 270 "NKEYS ", hashp->hdr.nkeys); 271 #endif 272 #ifdef HASH_STATISTICS 273 hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0; 274 hash_bigpages = 0; 275 #endif 276 return (dbp); 277 278 error2: 279 hdestroy(hashp); 280 errno = save_errno; 281 return (NULL); 282 283 error1: 284 if (hashp != NULL) 285 (void)close(hashp->fp); 286 287 error0: 288 if (!specified_file) 289 free((void*)(hashp->fname)); /* SUNW14resync */ 290 free(hashp); 291 errno = save_errno; 292 return (NULL); 293 } 294 295 static int32_t 296 hash_close(dbp) 297 DB *dbp; 298 { 299 HTAB *hashp; 300 int32_t retval; 301 302 if (!dbp) 303 return (ERROR); 304 305 hashp = (HTAB *)dbp->internal; 306 retval = hdestroy(hashp); 307 free(dbp); 308 return (retval); 309 } 310 311 static int32_t 312 hash_fd(dbp) 313 const DB *dbp; 314 { 315 HTAB *hashp; 316 317 if (!dbp) 318 return (ERROR); 319 320 hashp = (HTAB *)dbp->internal; 321 if (hashp->fp == -1) { 322 errno = ENOENT; 323 return (-1); 324 } 325 return (hashp->fp); 326 } 327 328 /************************** LOCAL CREATION ROUTINES **********************/ 329 static HTAB * 330 init_hash(hashp, file, info) 331 HTAB *hashp; 332 const char *file; 333 const HASHINFO *info; 334 { 335 struct stat statbuf; 336 int32_t nelem; 337 338 nelem = 1; 339 hashp->hdr.nkeys = 0; 340 hashp->hdr.lorder = DB_BYTE_ORDER; 341 hashp->hdr.bsize = DEF_BUCKET_SIZE; 342 hashp->hdr.bshift = DEF_BUCKET_SHIFT; 343 hashp->hdr.ffactor = DEF_FFACTOR; 344 hashp->hash = __default_hash; 345 memset(hashp->hdr.spares, 0, sizeof(hashp->hdr.spares)); 346 memset(hashp->hdr.bitmaps, 0, sizeof(hashp->hdr.bitmaps)); 347 348 /* Fix bucket size to be optimal for file system */ 349 if (file != NULL) { 350 if (stat(file, &statbuf)) 351 return (NULL); 352 hashp->hdr.bsize = statbuf.st_blksize; 353 hashp->hdr.bshift = __log2(hashp->hdr.bsize); 354 } 355 if (info) { 356 if (info->bsize) { 357 /* Round pagesize up to power of 2 */ 358 hashp->hdr.bshift = __log2(info->bsize); 359 hashp->hdr.bsize = 1 << hashp->hdr.bshift; 360 if (hashp->hdr.bsize > MAX_BSIZE) { 361 errno = EINVAL; 362 return (NULL); 363 } 364 } 365 if (info->ffactor) 366 hashp->hdr.ffactor = info->ffactor; 367 if (info->hash) 368 hashp->hash = info->hash; 369 if (info->lorder) { 370 if ((info->lorder != DB_BIG_ENDIAN) && 371 (info->lorder != DB_LITTLE_ENDIAN)) { 372 errno = EINVAL; 373 return (NULL); 374 } 375 hashp->hdr.lorder = info->lorder; 376 } 377 } 378 return (hashp); 379 } 380 381 /* 382 * Returns 0 on No Error 383 */ 384 static int32_t 385 init_htab(hashp, nelem) 386 HTAB *hashp; 387 int32_t nelem; 388 { 389 int32_t l2, nbuckets; 390 391 /* 392 * Divide number of elements by the fill factor and determine a 393 * desired number of buckets. Allocate space for the next greater 394 * power of two number of buckets. 395 */ 396 nelem = (nelem - 1) / hashp->hdr.ffactor + 1; 397 398 l2 = __log2(MAX(nelem, 2)); 399 nbuckets = 1 << l2; 400 401 hashp->hdr.spares[l2] = l2 + 1; 402 hashp->hdr.spares[l2 + 1] = l2 + 1; 403 hashp->hdr.ovfl_point = l2; 404 hashp->hdr.last_freed = 2; 405 406 hashp->hdr.max_bucket = hashp->hdr.low_mask = nbuckets - 1; 407 hashp->hdr.high_mask = (nbuckets << 1) - 1; 408 409 /* 410 * The number of header pages is the size of the header divided by 411 * the amount of freespace on header pages (the page size - the 412 * size of 1 integer where the length of the header info on that 413 * page is stored) plus another page if it didn't divide evenly. 414 */ 415 hashp->hdr.hdrpages = 416 (sizeof(HASHHDR) / (hashp->hdr.bsize - HEADER_OVERHEAD)) + 417 (((sizeof(HASHHDR) % (hashp->hdr.bsize - HEADER_OVERHEAD)) == 0) 418 ? 0 : 1); 419 420 /* Create pages for these buckets */ 421 /* 422 for (i = 0; i <= hashp->hdr.max_bucket; i++) { 423 if (__new_page(hashp, (u_int32_t)i, A_BUCKET) != 0) 424 return (-1); 425 } 426 */ 427 428 /* First bitmap page is at: splitpoint l2 page offset 1 */ 429 if (__ibitmap(hashp, OADDR_OF(l2, 1), l2 + 1, 0)) 430 return (-1); 431 432 return (0); 433 } 434 435 /* 436 * Functions to get/put hash header. We access the file directly. 437 */ 438 static u_int32_t 439 hget_header(hashp, page_size) 440 HTAB *hashp; 441 u_int32_t page_size; 442 { 443 u_int32_t num_copied, i; 444 u_int8_t *hdr_dest; 445 446 num_copied = 0; 447 i = 0; 448 449 hdr_dest = (u_int8_t *)&hashp->hdr; 450 451 /* 452 * XXX 453 * This should not be printing to stderr on a "normal" error case. 454 */ 455 lseek(hashp->fp, 0, SEEK_SET); 456 num_copied = read(hashp->fp, hdr_dest, sizeof(HASHHDR)); 457 if (num_copied != sizeof(HASHHDR)) { 458 fprintf(stderr, dgettext(TEXT_DOMAIN, 459 "hash: could not retrieve header")); 460 return (0); 461 } 462 #if DB_BYTE_ORDER == DB_LITTLE_ENDIAN 463 swap_header(hashp); 464 #endif 465 return (num_copied); 466 } 467 468 static void 469 hput_header(hashp) 470 HTAB *hashp; 471 { 472 HASHHDR *whdrp; 473 #if DB_BYTE_ORDER == DB_LITTLE_ENDIAN 474 HASHHDR whdr; 475 #endif 476 u_int32_t num_copied, i; 477 478 num_copied = i = 0; 479 480 whdrp = &hashp->hdr; 481 #if DB_BYTE_ORDER == DB_LITTLE_ENDIAN 482 whdrp = &whdr; 483 swap_header_copy(&hashp->hdr, whdrp); 484 #endif 485 486 lseek(hashp->fp, 0, SEEK_SET); 487 num_copied = write(hashp->fp, whdrp, sizeof(HASHHDR)); 488 if (num_copied != sizeof(HASHHDR)) 489 (void)fprintf(stderr, dgettext(TEXT_DOMAIN, 490 "hash: could not write hash header")); 491 return; 492 } 493 494 /********************** DESTROY/CLOSE ROUTINES ************************/ 495 496 /* 497 * Flushes any changes to the file if necessary and destroys the hashp 498 * structure, freeing all allocated space. 499 */ 500 static int32_t 501 hdestroy(hashp) 502 HTAB *hashp; 503 { 504 int32_t save_errno; 505 506 save_errno = 0; 507 508 #ifdef HASH_STATISTICS 509 { int i; 510 (void)fprintf(stderr, dgettext(TEXT_DOMAIN, 511 "hdestroy: accesses %ld collisions %ld\n"), 512 hash_accesses, hash_collisions); 513 (void)fprintf(stderr, 514 dgettext(TEXT_DOMAIN, 515 "hdestroy: expansions %ld\n"), hash_expansions); 516 (void)fprintf(stderr, 517 dgettext(TEXT_DOMAIN, 518 "hdestroy: overflows %ld\n"), hash_overflows); 519 (void)fprintf(stderr, 520 dgettext(TEXT_DOMAIN, 521 "hdestroy: big key/data pages %ld\n"), hash_bigpages); 522 (void)fprintf(stderr, 523 "keys %ld maxp %d\n", hashp->hdr.nkeys, hashp->hdr.max_bucket); 524 525 for (i = 0; i < NCACHED; i++) 526 (void)fprintf(stderr, 527 "spares[%d] = %d\n", i, hashp->hdr.spares[i]); 528 } 529 #endif 530 531 if (flush_meta(hashp) && !save_errno) 532 save_errno = errno; 533 534 /* Free the split page */ 535 if (hashp->split_buf) 536 free(hashp->split_buf); 537 538 /* Free the big key and big data returns */ 539 if (hashp->bigkey_buf) 540 free(hashp->bigkey_buf); 541 if (hashp->bigdata_buf) 542 free(hashp->bigdata_buf); 543 544 /* XXX This should really iterate over the cursor queue, but 545 it's not clear how to do that, and the only cursor a hash 546 table ever creates is the one used by hash_seq(). Passing 547 NULL as the first arg is also a kludge, but I know that 548 it's never used, so I do it. The intent is to plug the 549 memory leak. Correctness can come later. */ 550 551 if (hashp->seq_cursor) 552 hashp->seq_cursor->delete(NULL, hashp->seq_cursor, 0); 553 554 /* shut down mpool */ 555 mpool_sync(hashp->mp); 556 mpool_close(hashp->mp); 557 558 if (hashp->fp != -1) 559 (void)close(hashp->fp); 560 561 /* 562 * *** This may cause problems if hashp->fname is set in any case 563 * other than the case that we are generating a temporary file name. 564 * Note that the new version of mpool should support temporary 565 * files within mpool itself. 566 */ 567 if (hashp->fname && !hashp->save_file) { 568 #ifdef DEBUG 569 fprintf(stderr, dgettext(TEXT_DOMAIN, 570 "Unlinking file %s.\n"), hashp->fname); 571 #endif 572 /* we need to chmod the file to allow it to be deleted... */ 573 chmod(hashp->fname, 0700); 574 unlink(hashp->fname); 575 /* destroy the temporary name */ 576 free((void *)(hashp->fname)); /* SUNW14resync */ 577 } 578 free(hashp); 579 580 if (save_errno) { 581 errno = save_errno; 582 return (ERROR); 583 } 584 return (SUCCESS); 585 } 586 587 /* 588 * Write modified pages to disk 589 * 590 * Returns: 591 * 0 == OK 592 * -1 ERROR 593 */ 594 static int32_t 595 hash_sync(dbp, flags) 596 const DB *dbp; 597 u_int32_t flags; 598 { 599 HTAB *hashp; 600 601 hashp = (HTAB *)dbp->internal; 602 603 /* 604 * XXX 605 * Check success/failure conditions. 606 */ 607 return (flush_meta(hashp) || mpool_sync(hashp->mp)); 608 } 609 610 /* 611 * Returns: 612 * 0 == OK 613 * -1 indicates that errno should be set 614 */ 615 static int32_t 616 flush_meta(hashp) 617 HTAB *hashp; 618 { 619 int32_t i; 620 621 if (!hashp->save_file) 622 return (0); 623 hashp->hdr.magic = HASHMAGIC; 624 hashp->hdr.version = HASHVERSION; 625 hashp->hdr.h_charkey = hashp->hash(CHARKEY, sizeof(CHARKEY)); 626 627 /* write out metadata */ 628 hput_header(hashp); 629 630 for (i = 0; i < NCACHED; i++) 631 if (hashp->mapp[i]) { 632 if (__put_page(hashp, 633 (PAGE16 *)hashp->mapp[i], A_BITMAP, 1)) 634 return (-1); 635 hashp->mapp[i] = NULL; 636 } 637 return (0); 638 } 639 640 /*******************************SEARCH ROUTINES *****************************/ 641 /* 642 * All the access routines return 643 * 644 * Returns: 645 * 0 on SUCCESS 646 * 1 to indicate an external ERROR (i.e. key not found, etc) 647 * -1 to indicate an internal ERROR (i.e. out of memory, etc) 648 */ 649 650 /* *** make sure this is true! */ 651 652 static int32_t 653 hash_get(dbp, key, data, flag) 654 const DB *dbp; 655 const DBT *key; 656 DBT *data; 657 u_int32_t flag; 658 { 659 HTAB *hashp; 660 661 hashp = (HTAB *)dbp->internal; 662 if (flag) { 663 hashp->local_errno = errno = EINVAL; 664 return (ERROR); 665 } 666 return (hash_access(hashp, HASH_GET, key, data)); 667 } 668 669 static int32_t 670 hash_put(dbp, key, data, flag) 671 const DB *dbp; 672 DBT *key; 673 const DBT *data; 674 u_int32_t flag; 675 { 676 HTAB *hashp; 677 678 hashp = (HTAB *)dbp->internal; 679 if (flag && flag != R_NOOVERWRITE) { 680 hashp->local_errno = errno = EINVAL; 681 return (ERROR); 682 } 683 if ((hashp->flags & O_ACCMODE) == O_RDONLY) { 684 hashp->local_errno = errno = EPERM; 685 return (ERROR); 686 } 687 return (hash_access(hashp, flag == R_NOOVERWRITE ? 688 HASH_PUTNEW : HASH_PUT, key, (DBT *)data)); 689 } 690 691 static int32_t 692 hash_delete(dbp, key, flag) 693 const DB *dbp; 694 const DBT *key; 695 u_int32_t flag; /* Ignored */ 696 { 697 HTAB *hashp; 698 699 hashp = (HTAB *)dbp->internal; 700 if (flag) { 701 hashp->local_errno = errno = EINVAL; 702 return (ERROR); 703 } 704 if ((hashp->flags & O_ACCMODE) == O_RDONLY) { 705 hashp->local_errno = errno = EPERM; 706 return (ERROR); 707 } 708 709 return (hash_access(hashp, HASH_DELETE, key, NULL)); 710 } 711 712 /* 713 * Assume that hashp has been set in wrapper routine. 714 */ 715 static int32_t 716 hash_access(hashp, action, key, val) 717 HTAB *hashp; 718 ACTION action; 719 const DBT *key; 720 DBT *val; 721 { 722 DBT page_key, page_val; 723 CURSOR cursor; 724 ITEM_INFO item_info; 725 u_int32_t bucket; 726 u_int32_t num_items; 727 728 #ifdef HASH_STATISTICS 729 hash_accesses++; 730 #endif 731 732 num_items = 0; 733 734 /* 735 * Set up item_info so that we're looking for space to add an item 736 * as we cycle through the pages looking for the key. 737 */ 738 if (action == HASH_PUT || action == HASH_PUTNEW) { 739 if (ISBIG(key->size + val->size, hashp)) 740 item_info.seek_size = PAIR_OVERHEAD; 741 else 742 item_info.seek_size = key->size + val->size; 743 } else 744 item_info.seek_size = 0; 745 item_info.seek_found_page = 0; 746 747 bucket = __call_hash(hashp, (int8_t *)key->data, key->size); 748 749 cursor.pagep = NULL; 750 __get_item_reset(hashp, &cursor); 751 752 cursor.bucket = bucket; 753 while (1) { 754 __get_item_next(hashp, &cursor, &page_key, &page_val, &item_info); 755 if (item_info.status == ITEM_ERROR) 756 return (ABNORMAL); 757 if (item_info.status == ITEM_NO_MORE) 758 break; 759 num_items++; 760 if (item_info.key_off == BIGPAIR) { 761 /* 762 * !!! 763 * 0 is a valid index. 764 */ 765 if (__find_bigpair(hashp, &cursor, (int8_t *)key->data, 766 key->size) > 0) 767 goto found; 768 } else if (key->size == page_key.size && 769 !memcmp(key->data, page_key.data, key->size)) 770 goto found; 771 } 772 #ifdef HASH_STATISTICS 773 hash_collisions++; 774 #endif 775 __get_item_done(hashp, &cursor); 776 777 /* 778 * At this point, item_info will list either the last page in 779 * the chain, or the last page in the chain plus a pgno for where 780 * to find the first page in the chain with space for the 781 * item we wish to add. 782 */ 783 784 /* Not found */ 785 switch (action) { 786 case HASH_PUT: 787 case HASH_PUTNEW: 788 if (__addel(hashp, &item_info, key, val, num_items, 0)) 789 return (ERROR); 790 break; 791 case HASH_GET: 792 case HASH_DELETE: 793 default: 794 return (ABNORMAL); 795 } 796 797 if (item_info.caused_expand) 798 __expand_table(hashp); 799 return (SUCCESS); 800 801 found: __get_item_done(hashp, &cursor); 802 803 switch (action) { 804 case HASH_PUTNEW: 805 /* mpool_put(hashp->mp, pagep, 0); */ 806 return (ABNORMAL); 807 case HASH_GET: 808 if (item_info.key_off == BIGPAIR) { 809 if (__big_return(hashp, &item_info, val, 0)) 810 return (ERROR); 811 } else { 812 val->data = page_val.data; 813 val->size = page_val.size; 814 } 815 /* *** data may not be available! */ 816 break; 817 case HASH_PUT: 818 if (__delpair(hashp, &cursor, &item_info) || 819 __addel(hashp, &item_info, key, val, UNKNOWN, 0)) 820 return (ERROR); 821 __get_item_done(hashp, &cursor); 822 if (item_info.caused_expand) 823 __expand_table(hashp); 824 break; 825 case HASH_DELETE: 826 if (__delpair(hashp, &cursor, &item_info)) 827 return (ERROR); 828 break; 829 default: 830 abort(); 831 } 832 return (SUCCESS); 833 } 834 835 /* ****************** CURSORS ********************************** */ 836 CURSOR * 837 __cursor_creat(dbp) 838 const DB *dbp; 839 { 840 CURSOR *new_curs; 841 HTAB *hashp; 842 843 new_curs = (CURSOR *)malloc(sizeof(struct cursor_t)); 844 if (!new_curs) 845 return NULL; 846 new_curs->internal = 847 (struct item_info *)malloc(sizeof(struct item_info)); 848 if (!new_curs->internal) { 849 free(new_curs); 850 return NULL; 851 } 852 new_curs->get = cursor_get; 853 new_curs->delete = cursor_delete; 854 855 new_curs->bucket = 0; 856 new_curs->pgno = INVALID_PGNO; 857 new_curs->ndx = 0; 858 new_curs->pgndx = 0; 859 new_curs->pagep = NULL; 860 861 /* place onto queue of cursors */ 862 hashp = (HTAB *)dbp->internal; 863 TAILQ_INSERT_TAIL(&hashp->curs_queue, new_curs, queue); 864 865 return new_curs; 866 } 867 868 static int32_t 869 cursor_get(dbp, cursorp, key, val, flags) 870 const DB *dbp; 871 CURSOR *cursorp; 872 DBT *key, *val; 873 u_int32_t flags; 874 { 875 HTAB *hashp; 876 ITEM_INFO item_info; 877 878 hashp = (HTAB *)dbp->internal; 879 880 if (flags && flags != R_FIRST && flags != R_NEXT) { 881 hashp->local_errno = errno = EINVAL; 882 return (ERROR); 883 } 884 #ifdef HASH_STATISTICS 885 hash_accesses++; 886 #endif 887 888 item_info.seek_size = 0; 889 890 if (flags == R_FIRST) 891 __get_item_first(hashp, cursorp, key, val, &item_info); 892 else 893 __get_item_next(hashp, cursorp, key, val, &item_info); 894 895 /* 896 * This needs to be changed around. As is, get_item_next advances 897 * the pointers on the page but this function actually advances 898 * bucket pointers. This works, since the only other place we 899 * use get_item_next is in hash_access which only deals with one 900 * bucket at a time. However, there is the problem that certain other 901 * functions (such as find_bigpair and delpair) depend on the 902 * pgndx member of the cursor. Right now, they are using pngdx - 1 903 * since indices refer to the __next__ item that is to be fetched 904 * from the page. This is ugly, as you may have noticed, whoever 905 * you are. The best solution would be to depend on item_infos to 906 * deal with _current_ information, and have the cursors only 907 * deal with _next_ information. In that scheme, get_item_next 908 * would also advance buckets. Version 3... 909 */ 910 911 912 /* 913 * Must always enter this loop to do error handling and 914 * check for big key/data pair. 915 */ 916 while (1) { 917 if (item_info.status == ITEM_OK) { 918 if (item_info.key_off == BIGPAIR && 919 __big_keydata(hashp, cursorp->pagep, key, val, 920 item_info.pgndx)) 921 return (ABNORMAL); 922 923 break; 924 } else if (item_info.status != ITEM_NO_MORE) 925 return (ABNORMAL); 926 927 __put_page(hashp, cursorp->pagep, A_RAW, 0); 928 cursorp->ndx = cursorp->pgndx = 0; 929 cursorp->bucket++; 930 cursorp->pgno = INVALID_PGNO; 931 cursorp->pagep = NULL; 932 if (cursorp->bucket > hashp->hdr.max_bucket) 933 return (ABNORMAL); 934 __get_item_next(hashp, cursorp, key, val, &item_info); 935 } 936 937 __get_item_done(hashp, cursorp); 938 return (0); 939 } 940 941 static int32_t 942 cursor_delete(dbp, cursor, flags) 943 const DB *dbp; 944 CURSOR *cursor; 945 u_int32_t flags; 946 { 947 /* XXX this is empirically determined, so it might not be completely 948 correct, but it seems to work. At the very least it fixes 949 a memory leak */ 950 951 free(cursor->internal); 952 free(cursor); 953 954 return (0); 955 } 956 957 static int32_t 958 hash_seq(dbp, key, val, flag) 959 const DB *dbp; 960 DBT *key, *val; 961 u_int32_t flag; 962 { 963 HTAB *hashp; 964 965 /* 966 * Seq just uses the default cursor to go sequecing through the 967 * database. Note that the default cursor is the first in the list. 968 */ 969 970 hashp = (HTAB *)dbp->internal; 971 if (!hashp->seq_cursor) 972 hashp->seq_cursor = __cursor_creat(dbp); 973 974 return (hashp->seq_cursor->get(dbp, hashp->seq_cursor, key, val, flag)); 975 } 976 977 /********************************* UTILITIES ************************/ 978 979 /* 980 * Returns: 981 * 0 ==> OK 982 * -1 ==> Error 983 */ 984 int32_t 985 __expand_table(hashp) 986 HTAB *hashp; 987 { 988 u_int32_t old_bucket, new_bucket; 989 int32_t spare_ndx; 990 991 #ifdef HASH_STATISTICS 992 hash_expansions++; 993 #endif 994 new_bucket = ++hashp->hdr.max_bucket; 995 old_bucket = (hashp->hdr.max_bucket & hashp->hdr.low_mask); 996 997 /* Get a page for this new bucket */ 998 if (__new_page(hashp, new_bucket, A_BUCKET) != 0) 999 return (-1); 1000 1001 /* 1002 * If the split point is increasing (hdr.max_bucket's log base 2 1003 * increases), we need to copy the current contents of the spare 1004 * split bucket to the next bucket. 1005 */ 1006 spare_ndx = __log2(hashp->hdr.max_bucket + 1); 1007 if (spare_ndx > hashp->hdr.ovfl_point) { 1008 hashp->hdr.spares[spare_ndx] = hashp->hdr.spares[hashp->hdr.ovfl_point]; 1009 hashp->hdr.ovfl_point = spare_ndx; 1010 } 1011 if (new_bucket > hashp->hdr.high_mask) { 1012 /* Starting a new doubling */ 1013 hashp->hdr.low_mask = hashp->hdr.high_mask; 1014 hashp->hdr.high_mask = new_bucket | hashp->hdr.low_mask; 1015 } 1016 if (BUCKET_TO_PAGE(new_bucket) > MAX_PAGES(hashp)) { 1017 fprintf(stderr,dgettext(TEXT_DOMAIN, 1018 "hash: Cannot allocate new bucket. Pages exhausted.\n")); 1019 return (-1); 1020 } 1021 /* Relocate records to the new bucket */ 1022 return (__split_page(hashp, old_bucket, new_bucket)); 1023 } 1024 1025 u_int32_t 1026 __call_hash(hashp, k, len) 1027 HTAB *hashp; 1028 int8_t *k; 1029 int32_t len; 1030 { 1031 int32_t n, bucket; 1032 1033 n = hashp->hash(k, len); 1034 bucket = n & hashp->hdr.high_mask; 1035 if (bucket > hashp->hdr.max_bucket) 1036 bucket = bucket & hashp->hdr.low_mask; 1037 return (bucket); 1038 } 1039 1040 #if DB_BYTE_ORDER == DB_LITTLE_ENDIAN 1041 /* 1042 * Hashp->hdr needs to be byteswapped. 1043 */ 1044 static void 1045 swap_header_copy(srcp, destp) 1046 HASHHDR *srcp, *destp; 1047 { 1048 int32_t i; 1049 1050 P_32_COPY(srcp->magic, destp->magic); 1051 P_32_COPY(srcp->version, destp->version); 1052 P_32_COPY(srcp->lorder, destp->lorder); 1053 P_32_COPY(srcp->bsize, destp->bsize); 1054 P_32_COPY(srcp->bshift, destp->bshift); 1055 P_32_COPY(srcp->ovfl_point, destp->ovfl_point); 1056 P_32_COPY(srcp->last_freed, destp->last_freed); 1057 P_32_COPY(srcp->max_bucket, destp->max_bucket); 1058 P_32_COPY(srcp->high_mask, destp->high_mask); 1059 P_32_COPY(srcp->low_mask, destp->low_mask); 1060 P_32_COPY(srcp->ffactor, destp->ffactor); 1061 P_32_COPY(srcp->nkeys, destp->nkeys); 1062 P_32_COPY(srcp->hdrpages, destp->hdrpages); 1063 P_32_COPY(srcp->h_charkey, destp->h_charkey); 1064 for (i = 0; i < NCACHED; i++) { 1065 P_32_COPY(srcp->spares[i], destp->spares[i]); 1066 P_16_COPY(srcp->bitmaps[i], destp->bitmaps[i]); 1067 } 1068 } 1069 1070 static void 1071 swap_header(hashp) 1072 HTAB *hashp; 1073 { 1074 HASHHDR *hdrp; 1075 int32_t i; 1076 1077 hdrp = &hashp->hdr; 1078 1079 M_32_SWAP(hdrp->magic); 1080 M_32_SWAP(hdrp->version); 1081 M_32_SWAP(hdrp->lorder); 1082 M_32_SWAP(hdrp->bsize); 1083 M_32_SWAP(hdrp->bshift); 1084 M_32_SWAP(hdrp->ovfl_point); 1085 M_32_SWAP(hdrp->last_freed); 1086 M_32_SWAP(hdrp->max_bucket); 1087 M_32_SWAP(hdrp->high_mask); 1088 M_32_SWAP(hdrp->low_mask); 1089 M_32_SWAP(hdrp->ffactor); 1090 M_32_SWAP(hdrp->nkeys); 1091 M_32_SWAP(hdrp->hdrpages); 1092 M_32_SWAP(hdrp->h_charkey); 1093 for (i = 0; i < NCACHED; i++) { 1094 M_32_SWAP(hdrp->spares[i]); 1095 M_16_SWAP(hdrp->bitmaps[i]); 1096 } 1097 } 1098 #endif /* DB_BYTE_ORDER == DB_LITTLE_ENDIAN */ 1099