hash.c (31663B)
1 /*- 2 * Copyright (c) 1990, 1993, 1994 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. ***REMOVED*** - see 17 * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change 18 * 4. 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 #if defined(LIBC_SCCS) && !defined(lint) 36 static char sccsid[] = "@(#)hash.c 8.9 (Berkeley) 6/16/94"; 37 #endif /* LIBC_SCCS and not lint */ 38 39 #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) 40 #include <sys/param.h> 41 #endif 42 43 #if !defined(macintosh) 44 #include <sys/stat.h> 45 #endif 46 47 #if defined(macintosh) 48 #include <unix.h> 49 #include <unistd.h> 50 #endif 51 52 #include <errno.h> 53 #include <fcntl.h> 54 #include <stdio.h> 55 #include <stdlib.h> 56 #include <string.h> 57 58 #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) 59 #include <unistd.h> 60 #endif 61 #if defined(_WIN32) || defined(_WINDOWS) 62 #include <windows.h> 63 #endif 64 65 #include <assert.h> 66 67 #include "mcom_db.h" 68 #include "hash.h" 69 #include "page.h" 70 71 /* 72 #include "extern.h" 73 */ 74 static int alloc_segs(HTAB *, int); 75 static int flush_meta(HTAB *); 76 static int hash_access(HTAB *, ACTION, DBT *, DBT *); 77 static int hash_close(DB *); 78 static int hash_delete(const DB *, const DBT *, uint); 79 static int hash_fd(const DB *); 80 static int hash_get(const DB *, const DBT *, DBT *, uint); 81 static int hash_put(const DB *, DBT *, const DBT *, uint); 82 static void *hash_realloc(SEGMENT **, size_t, size_t); 83 static int hash_seq(const DB *, DBT *, DBT *, uint); 84 static int hash_sync(const DB *, uint); 85 static int hdestroy(HTAB *); 86 static HTAB *init_hash(HTAB *, const char *, HASHINFO *); 87 static int init_htab(HTAB *, int); 88 #if BYTE_ORDER == LITTLE_ENDIAN 89 static void swap_header(HTAB *); 90 static void swap_header_copy(HASHHDR *, HASHHDR *); 91 #endif 92 93 /* Fast arithmetic, relying on powers of 2, */ 94 #define MOD(x, y) ((x) & ((y)-1)) 95 96 #define RETURN_ERROR(ERR, LOC) \ 97 { \ 98 save_errno = ERR; \ 99 goto LOC; \ 100 } 101 102 /* Return values */ 103 #define SUCCESS (0) 104 #define DBM_ERROR (-1) 105 #define ABNORMAL (1) 106 107 #ifdef HASH_STATISTICS 108 int hash_accesses, hash_collisions, hash_expansions, hash_overflows; 109 #endif 110 111 /* A new Lou (montulli@mozilla.com) routine. 112 * 113 * The database is screwed. 114 * 115 * This closes the file, flushing buffers as appropriate. 116 */ 117 static void 118 dbm_remove_database(DB *dbp) 119 { 120 HTAB *hashp = (HTAB *)dbp->internal; 121 122 assert(0); 123 124 if (!hashp) 125 return; 126 hdestroy(hashp); 127 dbp->internal = NULL; 128 } 129 130 /************************** INTERFACE ROUTINES ***************************/ 131 /* OPEN/CLOSE */ 132 133 extern DB * 134 dbm_hash_open(const char *file, int flags, int mode, const HASHINFO *info, int dflags) 135 { 136 HTAB *hashp = NULL; 137 struct stat statbuf; 138 DB *dbp; 139 int bpages, hdrsize, new_table, nsegs, save_errno; 140 141 if ((flags & O_ACCMODE) == O_WRONLY) { 142 errno = EINVAL; 143 return NULL; 144 } 145 146 /* zero the statbuffer so that 147 * we can check it for a non-zero 148 * date to see if stat succeeded 149 */ 150 memset(&statbuf, 0, sizeof(struct stat)); 151 152 if (!(hashp = (HTAB *)calloc(1, sizeof(HTAB)))) { 153 errno = ENOMEM; 154 return NULL; 155 } 156 hashp->fp = NO_FILE; 157 if (file) 158 hashp->filename = strdup(file); 159 160 /* 161 * Even if user wants write only, we need to be able to read 162 * the actual file, so we need to open it read/write. But, the 163 * field in the hashp structure needs to be accurate so that 164 * we can check accesses. 165 */ 166 hashp->flags = flags; 167 168 new_table = 0; 169 if (!file || (flags & O_TRUNC) || (stat(file, &statbuf) && (errno == ENOENT))) { 170 if (errno == ENOENT) 171 errno = 0; /* Just in case someone looks at errno */ 172 new_table = 1; 173 } else if (statbuf.st_mtime && statbuf.st_size == 0) { 174 /* check for a zero length file and delete it 175 * if it exists 176 */ 177 new_table = 1; 178 } 179 hashp->file_size = statbuf.st_size; 180 181 if (file) { 182 #if defined(_WIN32) || defined(_WINDOWS) || defined(macintosh) 183 if ((hashp->fp = DBFILE_OPEN(file, flags | O_BINARY, mode)) == -1) 184 RETURN_ERROR(errno, error1); 185 #else 186 if ((hashp->fp = open(file, flags, mode)) == -1) 187 RETURN_ERROR(errno, error1); 188 (void)fcntl(hashp->fp, F_SETFD, 1); 189 #endif 190 } 191 if (new_table) { 192 if (!init_hash(hashp, file, (HASHINFO *)info)) 193 RETURN_ERROR(errno, error1); 194 } else { 195 /* Table already exists */ 196 if (info && info->hash) 197 hashp->hash = info->hash; 198 else 199 hashp->hash = dbm_default_hash; 200 201 hdrsize = read(hashp->fp, (char *)&hashp->hdr, sizeof(HASHHDR)); 202 if (hdrsize == -1) 203 RETURN_ERROR(errno, error1); 204 if (hdrsize != sizeof(HASHHDR)) 205 RETURN_ERROR(EFTYPE, error1); 206 #if BYTE_ORDER == LITTLE_ENDIAN 207 swap_header(hashp); 208 #endif 209 /* Verify file type, versions and hash function */ 210 if (hashp->MAGIC != HASHMAGIC) 211 RETURN_ERROR(EFTYPE, error1); 212 #define OLDHASHVERSION 1 213 if (hashp->VERSION != HASHVERSION && 214 hashp->VERSION != OLDHASHVERSION) 215 RETURN_ERROR(EFTYPE, error1); 216 if (hashp->hash(CHARKEY, sizeof(CHARKEY)) != hashp->H_CHARKEY) 217 RETURN_ERROR(EFTYPE, error1); 218 if (hashp->NKEYS < 0) /* Old bad database. */ 219 RETURN_ERROR(EFTYPE, error1); 220 221 /* 222 * Figure out how many segments we need. Max_Bucket is the 223 * maximum bucket number, so the number of buckets is 224 * max_bucket + 1. 225 */ 226 nsegs = (hashp->MAX_BUCKET + 1 + hashp->SGSIZE - 1) / 227 hashp->SGSIZE; 228 hashp->nsegs = 0; 229 if (alloc_segs(hashp, nsegs)) 230 /* If alloc_segs fails, errno will have been set. */ 231 RETURN_ERROR(errno, error1); 232 /* Read in bitmaps */ 233 bpages = (hashp->SPARES[hashp->OVFL_POINT] + 234 (hashp->BSIZE << BYTE_SHIFT) - 1) >> 235 (hashp->BSHIFT + BYTE_SHIFT); 236 237 hashp->nmaps = bpages; 238 (void)memset(&hashp->mapp[0], 0, bpages * sizeof(uint32 *)); 239 } 240 241 /* Initialize Buffer Manager */ 242 if (info && info->cachesize) 243 dbm_buf_init(hashp, (int32)info->cachesize); 244 else 245 dbm_buf_init(hashp, DEF_BUFSIZE); 246 247 hashp->new_file = new_table; 248 #ifdef macintosh 249 hashp->save_file = file && !(hashp->flags & O_RDONLY); 250 #else 251 hashp->save_file = file && (hashp->flags & O_RDWR); 252 #endif 253 hashp->cbucket = -1; 254 if (!(dbp = (DB *)malloc(sizeof(DB)))) { 255 RETURN_ERROR(ENOMEM, error1); 256 } 257 dbp->internal = hashp; 258 dbp->close = hash_close; 259 dbp->del = hash_delete; 260 dbp->fd = hash_fd; 261 dbp->get = hash_get; 262 dbp->put = hash_put; 263 dbp->seq = hash_seq; 264 dbp->sync = hash_sync; 265 dbp->type = DB_HASH; 266 267 #ifdef HASH_STATISTICS 268 hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0; 269 #endif 270 return (dbp); 271 272 error1: 273 hdestroy(hashp); 274 errno = save_errno; 275 return (NULL); 276 } 277 278 static int 279 hash_close(DB *dbp) 280 { 281 HTAB *hashp; 282 int retval; 283 284 if (!dbp) 285 return (DBM_ERROR); 286 287 hashp = (HTAB *)dbp->internal; 288 if (!hashp) 289 return (DBM_ERROR); 290 291 retval = hdestroy(hashp); 292 free(dbp); 293 return (retval); 294 } 295 296 static int 297 hash_fd(const DB *dbp) 298 { 299 HTAB *hashp; 300 301 if (!dbp) 302 return (DBM_ERROR); 303 304 hashp = (HTAB *)dbp->internal; 305 if (!hashp) 306 return (DBM_ERROR); 307 308 if (hashp->fp == -1) { 309 errno = ENOENT; 310 return (-1); 311 } 312 return (hashp->fp); 313 } 314 315 /************************** LOCAL CREATION ROUTINES **********************/ 316 static HTAB * 317 init_hash(HTAB *hashp, const char *file, HASHINFO *info) 318 { 319 struct stat statbuf; 320 int nelem; 321 322 nelem = 1; 323 hashp->NKEYS = 0; 324 hashp->LORDER = BYTE_ORDER; 325 hashp->BSIZE = DEF_BUCKET_SIZE; 326 hashp->BSHIFT = DEF_BUCKET_SHIFT; 327 hashp->SGSIZE = DEF_SEGSIZE; 328 hashp->SSHIFT = DEF_SEGSIZE_SHIFT; 329 hashp->DSIZE = DEF_DIRSIZE; 330 hashp->FFACTOR = DEF_FFACTOR; 331 hashp->hash = dbm_default_hash; 332 memset(hashp->SPARES, 0, sizeof(hashp->SPARES)); 333 memset(hashp->BITMAPS, 0, sizeof(hashp->BITMAPS)); 334 335 /* Fix bucket size to be optimal for file system */ 336 if (file != NULL) { 337 if (stat(file, &statbuf)) 338 return (NULL); 339 340 #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) 341 #if defined(__QNX__) && !defined(__QNXNTO__) 342 hashp->BSIZE = 512; /* preferred blk size on qnx4 */ 343 #else 344 hashp->BSIZE = statbuf.st_blksize; 345 #endif 346 347 /* new code added by Lou to reduce block 348 * size down below MAX_BSIZE 349 */ 350 if (hashp->BSIZE > MAX_BSIZE) 351 hashp->BSIZE = MAX_BSIZE; 352 #endif 353 hashp->BSHIFT = dbm_log2((uint32)hashp->BSIZE); 354 } 355 356 if (info) { 357 if (info->bsize) { 358 /* Round pagesize up to power of 2 */ 359 hashp->BSHIFT = dbm_log2(info->bsize); 360 hashp->BSIZE = 1 << hashp->BSHIFT; 361 if (hashp->BSIZE > MAX_BSIZE) { 362 errno = EINVAL; 363 return (NULL); 364 } 365 } 366 if (info->ffactor) 367 hashp->FFACTOR = info->ffactor; 368 if (info->hash) 369 hashp->hash = info->hash; 370 if (info->nelem) 371 nelem = info->nelem; 372 if (info->lorder) { 373 if (info->lorder != BIG_ENDIAN && 374 info->lorder != LITTLE_ENDIAN) { 375 errno = EINVAL; 376 return (NULL); 377 } 378 hashp->LORDER = info->lorder; 379 } 380 } 381 /* init_htab sets errno if it fails */ 382 if (init_htab(hashp, nelem)) 383 return (NULL); 384 else 385 return (hashp); 386 } 387 /* 388 * This calls alloc_segs which may run out of memory. Alloc_segs will 389 * set errno, so we just pass the error information along. 390 * 391 * Returns 0 on No Error 392 */ 393 static int 394 init_htab(HTAB *hashp, int nelem) 395 { 396 register int nbuckets, nsegs; 397 int l2; 398 399 /* 400 * Divide number of elements by the fill factor and determine a 401 * desired number of buckets. Allocate space for the next greater 402 * power of two number of buckets. 403 */ 404 nelem = (nelem - 1) / hashp->FFACTOR + 1; 405 406 l2 = dbm_log2((uint32)PR_MAX(nelem, 2)); 407 nbuckets = 1 << l2; 408 409 hashp->SPARES[l2] = l2 + 1; 410 hashp->SPARES[l2 + 1] = l2 + 1; 411 hashp->OVFL_POINT = l2; 412 hashp->LAST_FREED = 2; 413 414 /* First bitmap page is at: splitpoint l2 page offset 1 */ 415 if (dbm_ibitmap(hashp, (int)OADDR_OF(l2, 1), l2 + 1, 0)) 416 return (-1); 417 418 hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1; 419 hashp->HIGH_MASK = (nbuckets << 1) - 1; 420 hashp->HDRPAGES = ((PR_MAX(sizeof(HASHHDR), MINHDRSIZE) - 1) >> 421 hashp->BSHIFT) + 422 1; 423 424 nsegs = (nbuckets - 1) / hashp->SGSIZE + 1; 425 nsegs = 1 << dbm_log2((uint32)nsegs); 426 427 if (nsegs > hashp->DSIZE) 428 hashp->DSIZE = nsegs; 429 return (alloc_segs(hashp, nsegs)); 430 } 431 432 /********************** DESTROY/CLOSE ROUTINES ************************/ 433 434 /* 435 * Flushes any changes to the file if necessary and destroys the hashp 436 * structure, freeing all allocated space. 437 */ 438 static int 439 hdestroy(HTAB *hashp) 440 { 441 int i, save_errno; 442 443 save_errno = 0; 444 445 #ifdef HASH_STATISTICS 446 (void)fprintf(stderr, "hdestroy: accesses %ld collisions %ld\n", 447 hash_accesses, hash_collisions); 448 (void)fprintf(stderr, "hdestroy: expansions %ld\n", 449 hash_expansions); 450 (void)fprintf(stderr, "hdestroy: overflows %ld\n", 451 hash_overflows); 452 (void)fprintf(stderr, "keys %ld maxp %d segmentcount %d\n", 453 hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs); 454 455 for (i = 0; i < NCACHED; i++) 456 (void)fprintf(stderr, 457 "spares[%d] = %d\n", i, hashp->SPARES[i]); 458 #endif 459 /* 460 * Call on buffer manager to free buffers, and if required, 461 * write them to disk. 462 */ 463 if (dbm_buf_free(hashp, 1, hashp->save_file)) 464 save_errno = errno; 465 if (hashp->dir) { 466 free(*hashp->dir); /* Free initial segments */ 467 /* Free extra segments */ 468 while (hashp->exsegs--) 469 free(hashp->dir[--hashp->nsegs]); 470 free(hashp->dir); 471 } 472 if (flush_meta(hashp) && !save_errno) 473 save_errno = errno; 474 /* Free Bigmaps */ 475 for (i = 0; i < hashp->nmaps; i++) 476 if (hashp->mapp[i]) 477 free(hashp->mapp[i]); 478 479 if (hashp->fp != -1) 480 (void)close(hashp->fp); 481 482 if (hashp->filename) { 483 #if defined(_WIN32) || defined(_WINDOWS) 484 if (hashp->is_temp) 485 (void)unlink(hashp->filename); 486 #endif 487 free(hashp->filename); 488 } 489 if (hashp->tmp_buf) 490 free(hashp->tmp_buf); 491 if (hashp->tmp_key) 492 free(hashp->tmp_key); 493 free(hashp); 494 if (save_errno) { 495 errno = save_errno; 496 return (DBM_ERROR); 497 } 498 return (SUCCESS); 499 } 500 501 #if defined(_WIN32) || defined(_WINDOWS) 502 /* 503 * Close and reopen file to force file length update on windows. 504 * 505 * Returns: 506 * 0 == OK 507 * -1 DBM_ERROR 508 */ 509 static int 510 update_EOF(HTAB *hashp) 511 { 512 #if defined(DBM_REOPEN_ON_FLUSH) 513 char *file = hashp->filename; 514 off_t file_size; 515 int flags; 516 int mode = -1; 517 struct stat statbuf; 518 519 memset(&statbuf, 0, sizeof statbuf); 520 521 /* make sure we won't lose the file by closing it. */ 522 if (!file || (stat(file, &statbuf) && (errno == ENOENT))) { 523 /* pretend we did it. */ 524 return 0; 525 } 526 527 (void)close(hashp->fp); 528 529 flags = hashp->flags & ~(O_TRUNC | O_CREAT | O_EXCL); 530 531 if ((hashp->fp = DBFILE_OPEN(file, flags | O_BINARY, mode)) == -1) 532 return -1; 533 file_size = lseek(hashp->fp, (off_t)0, SEEK_END); 534 if (file_size == -1) 535 return -1; 536 hashp->file_size = file_size; 537 return 0; 538 #else 539 int fd = hashp->fp; 540 off_t file_size = lseek(fd, (off_t)0, SEEK_END); 541 HANDLE handle = (HANDLE)_get_osfhandle(fd); 542 BOOL cool = FlushFileBuffers(handle); 543 #ifdef DEBUG3 544 if (!cool) { 545 DWORD err = GetLastError(); 546 (void)fprintf(stderr, 547 "FlushFileBuffers failed, last error = %d, 0x%08x\n", 548 err, err); 549 } 550 #endif 551 if (file_size == -1) 552 return -1; 553 hashp->file_size = file_size; 554 return cool ? 0 : -1; 555 #endif 556 } 557 #endif 558 559 /* 560 * Write modified pages to disk 561 * 562 * Returns: 563 * 0 == OK 564 * -1 DBM_ERROR 565 */ 566 static int 567 hash_sync(const DB *dbp, uint flags) 568 { 569 HTAB *hashp; 570 571 if (flags != 0) { 572 errno = EINVAL; 573 return (DBM_ERROR); 574 } 575 576 if (!dbp) 577 return (DBM_ERROR); 578 579 hashp = (HTAB *)dbp->internal; 580 if (!hashp) 581 return (DBM_ERROR); 582 583 if (!hashp->save_file) 584 return (0); 585 if (dbm_buf_free(hashp, 0, 1) || flush_meta(hashp)) 586 return (DBM_ERROR); 587 #if defined(_WIN32) || defined(_WINDOWS) 588 if (hashp->updateEOF && hashp->filename && !hashp->is_temp) { 589 int status = update_EOF(hashp); 590 hashp->updateEOF = 0; 591 if (status) 592 return status; 593 } 594 #endif 595 hashp->new_file = 0; 596 return (0); 597 } 598 599 /* 600 * Returns: 601 * 0 == OK 602 * -1 indicates that errno should be set 603 */ 604 static int 605 flush_meta(HTAB *hashp) 606 { 607 HASHHDR *whdrp; 608 #if BYTE_ORDER == LITTLE_ENDIAN 609 HASHHDR whdr; 610 #endif 611 int fp, i, wsize; 612 613 if (!hashp->save_file) 614 return (0); 615 hashp->MAGIC = HASHMAGIC; 616 hashp->VERSION = HASHVERSION; 617 hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY)); 618 619 fp = hashp->fp; 620 whdrp = &hashp->hdr; 621 #if BYTE_ORDER == LITTLE_ENDIAN 622 whdrp = &whdr; 623 swap_header_copy(&hashp->hdr, whdrp); 624 #endif 625 if ((lseek(fp, (off_t)0, SEEK_SET) == -1) || 626 ((wsize = write(fp, (char *)whdrp, sizeof(HASHHDR))) == -1)) 627 return (-1); 628 else if (wsize != sizeof(HASHHDR)) { 629 errno = EFTYPE; 630 hashp->dbmerrno = errno; 631 return (-1); 632 } 633 for (i = 0; i < NCACHED; i++) 634 if (hashp->mapp[i]) 635 if (dbm_put_page(hashp, (char *)hashp->mapp[i], 636 hashp->BITMAPS[i], 0, 1)) 637 return (-1); 638 return (0); 639 } 640 641 /*******************************SEARCH ROUTINES *****************************/ 642 /* 643 * All the access routines return 644 * 645 * Returns: 646 * 0 on SUCCESS 647 * 1 to indicate an external DBM_ERROR (i.e. key not found, etc) 648 * -1 to indicate an internal DBM_ERROR (i.e. out of memory, etc) 649 */ 650 static int 651 hash_get( 652 const DB *dbp, 653 const DBT *key, 654 DBT *data, 655 uint flag) 656 { 657 HTAB *hashp; 658 int rv; 659 660 hashp = (HTAB *)dbp->internal; 661 if (!hashp) 662 return (DBM_ERROR); 663 664 if (flag) { 665 hashp->dbmerrno = errno = EINVAL; 666 return (DBM_ERROR); 667 } 668 669 rv = hash_access(hashp, HASH_GET, (DBT *)key, data); 670 671 if (rv == DATABASE_CORRUPTED_ERROR) { 672 #if defined(unix) && defined(DEBUG) 673 printf("\n\nDBM Database has been corrupted, tell Lou...\n\n"); 674 #endif 675 dbm_remove_database((DB *)dbp); 676 } 677 678 return (rv); 679 } 680 681 static int 682 hash_put( 683 const DB *dbp, 684 DBT *key, 685 const DBT *data, 686 uint flag) 687 { 688 HTAB *hashp; 689 int rv; 690 691 hashp = (HTAB *)dbp->internal; 692 if (!hashp) 693 return (DBM_ERROR); 694 695 if (flag && flag != R_NOOVERWRITE) { 696 hashp->dbmerrno = errno = EINVAL; 697 return (DBM_ERROR); 698 } 699 if ((hashp->flags & O_ACCMODE) == O_RDONLY) { 700 hashp->dbmerrno = errno = EPERM; 701 return (DBM_ERROR); 702 } 703 704 rv = hash_access(hashp, flag == R_NOOVERWRITE ? HASH_PUTNEW : HASH_PUT, 705 (DBT *)key, (DBT *)data); 706 707 if (rv == DATABASE_CORRUPTED_ERROR) { 708 #if defined(unix) && defined(DEBUG) 709 printf("\n\nDBM Database has been corrupted, tell Lou...\n\n"); 710 #endif 711 dbm_remove_database((DB *)dbp); 712 } 713 714 return (rv); 715 } 716 717 static int 718 hash_delete( 719 const DB *dbp, 720 const DBT *key, 721 uint flag) /* Ignored */ 722 { 723 HTAB *hashp; 724 int rv; 725 726 hashp = (HTAB *)dbp->internal; 727 if (!hashp) 728 return (DBM_ERROR); 729 730 if (flag && flag != R_CURSOR) { 731 hashp->dbmerrno = errno = EINVAL; 732 return (DBM_ERROR); 733 } 734 if ((hashp->flags & O_ACCMODE) == O_RDONLY) { 735 hashp->dbmerrno = errno = EPERM; 736 return (DBM_ERROR); 737 } 738 rv = hash_access(hashp, HASH_DELETE, (DBT *)key, NULL); 739 740 if (rv == DATABASE_CORRUPTED_ERROR) { 741 #if defined(unix) && defined(DEBUG) 742 printf("\n\nDBM Database has been corrupted, tell Lou...\n\n"); 743 #endif 744 dbm_remove_database((DB *)dbp); 745 } 746 747 return (rv); 748 } 749 750 #define MAX_OVERFLOW_HASH_ACCESS_LOOPS 2000 751 /* 752 * Assume that hashp has been set in wrapper routine. 753 */ 754 static int 755 hash_access( 756 HTAB *hashp, 757 ACTION action, 758 DBT *key, DBT *val) 759 { 760 register BUFHEAD *rbufp; 761 BUFHEAD *bufp, *save_bufp; 762 register uint16 *bp; 763 register long n, ndx, off; 764 register size_t size; 765 register char *kp; 766 uint16 pageno; 767 uint32 ovfl_loop_count = 0; 768 int32 last_overflow_page_no = -1; 769 770 #ifdef HASH_STATISTICS 771 hash_accesses++; 772 #endif 773 774 off = hashp->BSIZE; 775 size = key->size; 776 kp = (char *)key->data; 777 rbufp = dbm_get_buf(hashp, dbm_call_hash(hashp, kp, size), NULL, 0); 778 if (!rbufp) 779 return (DATABASE_CORRUPTED_ERROR); 780 save_bufp = rbufp; 781 782 /* Pin the bucket chain */ 783 rbufp->flags |= BUF_PIN; 784 for (bp = (uint16 *)rbufp->page, n = *bp++, ndx = 1; ndx < n;) { 785 786 if (bp[1] >= REAL_KEY) { 787 /* Real key/data pair */ 788 if (size == (unsigned long)(off - *bp) && 789 memcmp(kp, rbufp->page + *bp, size) == 0) 790 goto found; 791 off = bp[1]; 792 #ifdef HASH_STATISTICS 793 hash_collisions++; 794 #endif 795 bp += 2; 796 ndx += 2; 797 } else if (bp[1] == OVFLPAGE) { 798 799 /* database corruption: overflow loop detection */ 800 if (last_overflow_page_no == (int32)*bp) 801 return (DATABASE_CORRUPTED_ERROR); 802 803 last_overflow_page_no = *bp; 804 805 rbufp = dbm_get_buf(hashp, *bp, rbufp, 0); 806 if (!rbufp) { 807 save_bufp->flags &= ~BUF_PIN; 808 return (DBM_ERROR); 809 } 810 811 ovfl_loop_count++; 812 if (ovfl_loop_count > MAX_OVERFLOW_HASH_ACCESS_LOOPS) 813 return (DATABASE_CORRUPTED_ERROR); 814 815 /* FOR LOOP INIT */ 816 bp = (uint16 *)rbufp->page; 817 n = *bp++; 818 ndx = 1; 819 off = hashp->BSIZE; 820 } else if (bp[1] < REAL_KEY) { 821 if ((ndx = 822 dbm_find_bigpair(hashp, rbufp, ndx, kp, (int)size)) > 0) 823 goto found; 824 if (ndx == -2) { 825 bufp = rbufp; 826 if (!(pageno = 827 dbm_find_last_page(hashp, &bufp))) { 828 ndx = 0; 829 rbufp = bufp; 830 break; /* FOR */ 831 } 832 rbufp = dbm_get_buf(hashp, pageno, bufp, 0); 833 if (!rbufp) { 834 save_bufp->flags &= ~BUF_PIN; 835 return (DBM_ERROR); 836 } 837 /* FOR LOOP INIT */ 838 bp = (uint16 *)rbufp->page; 839 n = *bp++; 840 ndx = 1; 841 off = hashp->BSIZE; 842 } else { 843 save_bufp->flags &= ~BUF_PIN; 844 return (DBM_ERROR); 845 } 846 } 847 } 848 849 /* Not found */ 850 switch (action) { 851 case HASH_PUT: 852 case HASH_PUTNEW: 853 if (dbm_addel(hashp, rbufp, key, val)) { 854 save_bufp->flags &= ~BUF_PIN; 855 return (DBM_ERROR); 856 } else { 857 save_bufp->flags &= ~BUF_PIN; 858 return (SUCCESS); 859 } 860 case HASH_GET: 861 case HASH_DELETE: 862 default: 863 save_bufp->flags &= ~BUF_PIN; 864 return (ABNORMAL); 865 } 866 867 found: 868 switch (action) { 869 case HASH_PUTNEW: 870 save_bufp->flags &= ~BUF_PIN; 871 return (ABNORMAL); 872 case HASH_GET: 873 bp = (uint16 *)rbufp->page; 874 if (bp[ndx + 1] < REAL_KEY) { 875 if (dbm_big_return(hashp, rbufp, ndx, val, 0)) 876 return (DBM_ERROR); 877 } else { 878 val->data = (uint8 *)rbufp->page + (int)bp[ndx + 1]; 879 val->size = bp[ndx] - bp[ndx + 1]; 880 } 881 break; 882 case HASH_PUT: 883 if ((dbm_delpair(hashp, rbufp, ndx)) || 884 (dbm_addel(hashp, rbufp, key, val))) { 885 save_bufp->flags &= ~BUF_PIN; 886 return (DBM_ERROR); 887 } 888 break; 889 case HASH_DELETE: 890 if (dbm_delpair(hashp, rbufp, ndx)) 891 return (DBM_ERROR); 892 break; 893 default: 894 abort(); 895 } 896 save_bufp->flags &= ~BUF_PIN; 897 return (SUCCESS); 898 } 899 900 static int 901 hash_seq( 902 const DB *dbp, 903 DBT *key, DBT *data, 904 uint flag) 905 { 906 register uint32 bucket; 907 register BUFHEAD *bufp = NULL; 908 HTAB *hashp; 909 uint16 *bp, ndx; 910 911 hashp = (HTAB *)dbp->internal; 912 if (!hashp) 913 return (DBM_ERROR); 914 915 if (flag && flag != R_FIRST && flag != R_NEXT) { 916 hashp->dbmerrno = errno = EINVAL; 917 return (DBM_ERROR); 918 } 919 #ifdef HASH_STATISTICS 920 hash_accesses++; 921 #endif 922 if ((hashp->cbucket < 0) || (flag == R_FIRST)) { 923 hashp->cbucket = 0; 924 hashp->cndx = 1; 925 hashp->cpage = NULL; 926 } 927 928 for (bp = NULL; !bp || !bp[0];) { 929 if (!(bufp = hashp->cpage)) { 930 for (bucket = hashp->cbucket; 931 bucket <= (uint32)hashp->MAX_BUCKET; 932 bucket++, hashp->cndx = 1) { 933 bufp = dbm_get_buf(hashp, bucket, NULL, 0); 934 if (!bufp) 935 return (DBM_ERROR); 936 hashp->cpage = bufp; 937 bp = (uint16 *)bufp->page; 938 if (bp[0]) 939 break; 940 } 941 hashp->cbucket = bucket; 942 if (hashp->cbucket > hashp->MAX_BUCKET) { 943 hashp->cbucket = -1; 944 return (ABNORMAL); 945 } 946 } else 947 bp = (uint16 *)hashp->cpage->page; 948 949 #ifdef DEBUG 950 assert(bp); 951 assert(bufp); 952 #endif 953 while (bp[hashp->cndx + 1] == OVFLPAGE) { 954 bufp = hashp->cpage = 955 dbm_get_buf(hashp, bp[hashp->cndx], bufp, 0); 956 if (!bufp) 957 return (DBM_ERROR); 958 bp = (uint16 *)(bufp->page); 959 hashp->cndx = 1; 960 } 961 if (!bp[0]) { 962 hashp->cpage = NULL; 963 ++hashp->cbucket; 964 } 965 } 966 ndx = hashp->cndx; 967 if (bp[ndx + 1] < REAL_KEY) { 968 if (dbm_big_keydata(hashp, bufp, key, data, 1)) 969 return (DBM_ERROR); 970 } else { 971 key->data = (uint8 *)hashp->cpage->page + bp[ndx]; 972 key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx]; 973 data->data = (uint8 *)hashp->cpage->page + bp[ndx + 1]; 974 data->size = bp[ndx] - bp[ndx + 1]; 975 ndx += 2; 976 if (ndx > bp[0]) { 977 hashp->cpage = NULL; 978 hashp->cbucket++; 979 hashp->cndx = 1; 980 } else 981 hashp->cndx = ndx; 982 } 983 return (SUCCESS); 984 } 985 986 /********************************* UTILITIES ************************/ 987 988 /* 989 * Returns: 990 * 0 ==> OK 991 * -1 ==> Error 992 */ 993 extern int 994 dbm_expand_table(HTAB *hashp) 995 { 996 uint32 old_bucket, new_bucket; 997 int new_segnum, spare_ndx; 998 size_t dirsize; 999 1000 #ifdef HASH_STATISTICS 1001 hash_expansions++; 1002 #endif 1003 new_bucket = ++hashp->MAX_BUCKET; 1004 old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK); 1005 1006 new_segnum = new_bucket >> hashp->SSHIFT; 1007 1008 /* Check if we need a new segment */ 1009 if (new_segnum >= hashp->nsegs) { 1010 /* Check if we need to expand directory */ 1011 if (new_segnum >= hashp->DSIZE) { 1012 /* Reallocate directory */ 1013 dirsize = hashp->DSIZE * sizeof(SEGMENT *); 1014 if (!hash_realloc(&hashp->dir, dirsize, dirsize << 1)) 1015 return (-1); 1016 hashp->DSIZE = dirsize << 1; 1017 } 1018 if ((hashp->dir[new_segnum] = 1019 (SEGMENT)calloc((size_t)hashp->SGSIZE, sizeof(BUFHEAD *))) == NULL) 1020 return (-1); 1021 hashp->exsegs++; 1022 hashp->nsegs++; 1023 } 1024 /* 1025 * If the split point is increasing (MAX_BUCKET's log base 2 1026 * * increases), we need to copy the current contents of the spare 1027 * split bucket to the next bucket. 1028 */ 1029 spare_ndx = dbm_log2((uint32)(hashp->MAX_BUCKET + 1)); 1030 if (spare_ndx > hashp->OVFL_POINT) { 1031 hashp->SPARES[spare_ndx] = hashp->SPARES[hashp->OVFL_POINT]; 1032 hashp->OVFL_POINT = spare_ndx; 1033 } 1034 1035 if (new_bucket > (uint32)hashp->HIGH_MASK) { 1036 /* Starting a new doubling */ 1037 hashp->LOW_MASK = hashp->HIGH_MASK; 1038 hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK; 1039 } 1040 /* Relocate records to the new bucket */ 1041 return (dbm_split_page(hashp, old_bucket, new_bucket)); 1042 } 1043 1044 /* 1045 * If realloc guarantees that the pointer is not destroyed if the realloc 1046 * fails, then this routine can go away. 1047 */ 1048 static void * 1049 hash_realloc( 1050 SEGMENT **p_ptr, 1051 size_t oldsize, size_t newsize) 1052 { 1053 register void *p; 1054 1055 if ((p = malloc(newsize))) { 1056 memmove(p, *p_ptr, oldsize); 1057 memset((char *)p + oldsize, 0, newsize - oldsize); 1058 free(*p_ptr); 1059 *p_ptr = (SEGMENT *)p; 1060 } 1061 return (p); 1062 } 1063 1064 extern uint32 1065 dbm_call_hash(HTAB *hashp, char *k, size_t len) 1066 { 1067 uint32 n, bucket; 1068 1069 n = hashp->hash(k, len); 1070 bucket = n & hashp->HIGH_MASK; 1071 if (bucket > (uint32)hashp->MAX_BUCKET) 1072 bucket = bucket & hashp->LOW_MASK; 1073 return (bucket); 1074 } 1075 1076 /* 1077 * Allocate segment table. On error, set errno. 1078 * 1079 * Returns 0 on success 1080 */ 1081 static int 1082 alloc_segs( 1083 HTAB *hashp, 1084 int nsegs) 1085 { 1086 register int i; 1087 register SEGMENT store; 1088 1089 if ((hashp->dir = 1090 (SEGMENT *)calloc((size_t)hashp->DSIZE, sizeof(SEGMENT))) == NULL) { 1091 errno = ENOMEM; 1092 return (-1); 1093 } 1094 /* Allocate segments */ 1095 if ((store = 1096 (SEGMENT)calloc((size_t)nsegs << hashp->SSHIFT, sizeof(BUFHEAD *))) == NULL) { 1097 errno = ENOMEM; 1098 return (-1); 1099 } 1100 for (i = 0; i < nsegs; i++, hashp->nsegs++) 1101 hashp->dir[i] = &store[i << hashp->SSHIFT]; 1102 return (0); 1103 } 1104 1105 #if BYTE_ORDER == LITTLE_ENDIAN 1106 /* 1107 * Hashp->hdr needs to be byteswapped. 1108 */ 1109 static void 1110 swap_header_copy( 1111 HASHHDR *srcp, HASHHDR *destp) 1112 { 1113 int i; 1114 1115 P_32_COPY(srcp->magic, destp->magic); 1116 P_32_COPY(srcp->version, destp->version); 1117 P_32_COPY(srcp->lorder, destp->lorder); 1118 P_32_COPY(srcp->bsize, destp->bsize); 1119 P_32_COPY(srcp->bshift, destp->bshift); 1120 P_32_COPY(srcp->dsize, destp->dsize); 1121 P_32_COPY(srcp->ssize, destp->ssize); 1122 P_32_COPY(srcp->sshift, destp->sshift); 1123 P_32_COPY(srcp->ovfl_point, destp->ovfl_point); 1124 P_32_COPY(srcp->last_freed, destp->last_freed); 1125 P_32_COPY(srcp->max_bucket, destp->max_bucket); 1126 P_32_COPY(srcp->high_mask, destp->high_mask); 1127 P_32_COPY(srcp->low_mask, destp->low_mask); 1128 P_32_COPY(srcp->ffactor, destp->ffactor); 1129 P_32_COPY(srcp->nkeys, destp->nkeys); 1130 P_32_COPY(srcp->hdrpages, destp->hdrpages); 1131 P_32_COPY(srcp->h_charkey, destp->h_charkey); 1132 for (i = 0; i < NCACHED; i++) { 1133 P_32_COPY(srcp->spares[i], destp->spares[i]); 1134 P_16_COPY(srcp->bitmaps[i], destp->bitmaps[i]); 1135 } 1136 } 1137 1138 static void 1139 swap_header(HTAB *hashp) 1140 { 1141 HASHHDR *hdrp; 1142 int i; 1143 1144 hdrp = &hashp->hdr; 1145 1146 M_32_SWAP(hdrp->magic); 1147 M_32_SWAP(hdrp->version); 1148 M_32_SWAP(hdrp->lorder); 1149 M_32_SWAP(hdrp->bsize); 1150 M_32_SWAP(hdrp->bshift); 1151 M_32_SWAP(hdrp->dsize); 1152 M_32_SWAP(hdrp->ssize); 1153 M_32_SWAP(hdrp->sshift); 1154 M_32_SWAP(hdrp->ovfl_point); 1155 M_32_SWAP(hdrp->last_freed); 1156 M_32_SWAP(hdrp->max_bucket); 1157 M_32_SWAP(hdrp->high_mask); 1158 M_32_SWAP(hdrp->low_mask); 1159 M_32_SWAP(hdrp->ffactor); 1160 M_32_SWAP(hdrp->nkeys); 1161 M_32_SWAP(hdrp->hdrpages); 1162 M_32_SWAP(hdrp->h_charkey); 1163 for (i = 0; i < NCACHED; i++) { 1164 M_32_SWAP(hdrp->spares[i]); 1165 M_16_SWAP(hdrp->bitmaps[i]); 1166 } 1167 } 1168 #endif