1 /* $NetBSD: hash_bigkey.c,v 1.25 2015/11/18 18:22:42 christos Exp $ */ 2 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 #if HAVE_NBTOOL_CONFIG_H 36 #include "nbtool_config.h" 37 #endif 38 39 #include <sys/cdefs.h> 40 __RCSID("$NetBSD: hash_bigkey.c,v 1.25 2015/11/18 18:22:42 christos Exp $"); 41 42 /* 43 * PACKAGE: hash 44 * DESCRIPTION: 45 * Big key/data handling for the hashing package. 46 * 47 * ROUTINES: 48 * External 49 * __big_keydata 50 * __big_split 51 * __big_insert 52 * __big_return 53 * __big_delete 54 * __find_last_page 55 * Internal 56 * collect_key 57 * collect_data 58 */ 59 60 #include <sys/param.h> 61 62 #include <errno.h> 63 #include <stdio.h> 64 #include <stdlib.h> 65 #include <string.h> 66 #include <assert.h> 67 68 #include <db.h> 69 #include "hash.h" 70 #include "page.h" 71 #include "extern.h" 72 73 static int collect_key(HTAB *, BUFHEAD *, int, DBT *, int); 74 static int collect_data(HTAB *, BUFHEAD *, int, int); 75 76 /* 77 * Big_insert 78 * 79 * You need to do an insert and the key/data pair is too big 80 * 81 * Returns: 82 * 0 ==> OK 83 *-1 ==> ERROR 84 */ 85 int 86 __big_insert(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val) 87 { 88 uint16_t *p, n; 89 size_t key_size, val_size; 90 uint16_t space, move_bytes, off; 91 char *cp, *key_data, *val_data; 92 size_t temp; 93 94 cp = bufp->page; /* Character pointer of p. */ 95 p = (uint16_t *)(void *)cp; 96 97 key_data = (char *)key->data; 98 _DBFIT(key->size, int); 99 key_size = key->size; 100 val_data = (char *)val->data; 101 _DBFIT(val->size, int); 102 val_size = val->size; 103 104 /* First move the Key */ 105 106 temp = FREESPACE(p) - BIGOVERHEAD; 107 _DBFIT(temp, uint16_t); 108 space = (uint16_t)temp; 109 while (key_size) { 110 size_t kspace = MIN(space, key_size); 111 _DBFIT(kspace, uint16_t); 112 move_bytes = (uint16_t)kspace; 113 off = OFFSET(p) - move_bytes; 114 memmove(cp + off, key_data, (size_t)move_bytes); 115 key_size -= move_bytes; 116 key_data += move_bytes; 117 n = p[0]; 118 p[++n] = off; 119 p[0] = ++n; 120 temp = off - PAGE_META(n); 121 _DBFIT(temp, uint16_t); 122 FREESPACE(p) = (uint16_t)temp; 123 OFFSET(p) = off; 124 p[n] = PARTIAL_KEY; 125 bufp = __add_ovflpage(hashp, bufp); 126 if (!bufp) 127 return (-1); 128 n = p[0]; 129 if (!key_size) { 130 space = FREESPACE(p); 131 if (space) { 132 size_t vspace = MIN(space, val_size); 133 _DBFIT(vspace, uint16_t); 134 move_bytes = (uint16_t)vspace; 135 /* 136 * If the data would fit exactly in the 137 * remaining space, we must overflow it to the 138 * next page; otherwise the invariant that the 139 * data must end on a page with FREESPACE 140 * non-zero would fail. 141 */ 142 if (space == val_size && val_size == val->size) 143 goto toolarge; 144 off = OFFSET(p) - move_bytes; 145 memmove(cp + off, val_data, (size_t)move_bytes); 146 val_data += move_bytes; 147 val_size -= move_bytes; 148 p[n] = off; 149 p[n - 2] = FULL_KEY_DATA; 150 FREESPACE(p) = FREESPACE(p) - move_bytes; 151 OFFSET(p) = off; 152 } else { 153 toolarge: 154 p[n - 2] = FULL_KEY; 155 } 156 } 157 p = (uint16_t *)(void *)bufp->page; 158 cp = bufp->page; 159 bufp->flags |= BUF_MOD; 160 temp = FREESPACE(p) - BIGOVERHEAD; 161 _DBFIT(temp, uint16_t); 162 space = (uint16_t)temp; 163 } 164 165 /* Now move the data */ 166 temp = FREESPACE(p) - BIGOVERHEAD; 167 _DBFIT(temp, uint16_t); 168 space = (uint16_t)temp; 169 while (val_size) { 170 size_t vspace = MIN(space, val_size); 171 _DBFIT(vspace, uint16_t); 172 move_bytes = (uint16_t)vspace; 173 /* 174 * Here's the hack to make sure that if the data ends on the 175 * same page as the key ends, FREESPACE is at least one. 176 */ 177 if (space == val_size && val_size == val->size) 178 move_bytes--; 179 off = OFFSET(p) - move_bytes; 180 memmove(cp + off, val_data, (size_t)move_bytes); 181 val_size -= move_bytes; 182 val_data += move_bytes; 183 n = p[0]; 184 p[++n] = off; 185 p[0] = ++n; 186 temp = off - PAGE_META(n); 187 _DBFIT(temp, uint16_t); 188 FREESPACE(p) = (uint16_t)temp; 189 OFFSET(p) = off; 190 if (val_size) { 191 p[n] = FULL_KEY; 192 bufp = __add_ovflpage(hashp, bufp); 193 if (!bufp) 194 return (-1); 195 cp = bufp->page; 196 p = (uint16_t *)(void *)cp; 197 } else 198 p[n] = FULL_KEY_DATA; 199 bufp->flags |= BUF_MOD; 200 temp = FREESPACE(p) - BIGOVERHEAD; 201 _DBFIT(temp, uint16_t); 202 space = (uint16_t)temp; 203 } 204 return (0); 205 } 206 207 /* 208 * Called when bufp's page contains a partial key (index should be 1) 209 * 210 * All pages in the big key/data pair except bufp are freed. We cannot 211 * free bufp because the page pointing to it is lost and we can't get rid 212 * of its pointer. 213 * 214 * Returns: 215 * 0 => OK 216 *-1 => ERROR 217 */ 218 int 219 __big_delete(HTAB *hashp, BUFHEAD *bufp) 220 { 221 BUFHEAD *last_bfp, *rbufp; 222 uint16_t *bp, pageno; 223 int key_done, n; 224 size_t temp; 225 226 rbufp = bufp; 227 last_bfp = NULL; 228 bp = (uint16_t *)(void *)bufp->page; 229 pageno = 0; 230 key_done = 0; 231 232 while (!key_done || (bp[2] != FULL_KEY_DATA)) { 233 if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) 234 key_done = 1; 235 236 /* 237 * If there is freespace left on a FULL_KEY_DATA page, then 238 * the data is short and fits entirely on this page, and this 239 * is the last page. 240 */ 241 if (bp[2] == FULL_KEY_DATA && FREESPACE(bp)) 242 break; 243 pageno = bp[bp[0] - 1]; 244 rbufp->flags |= BUF_MOD; 245 rbufp = __get_buf(hashp, (uint32_t)pageno, rbufp, 0); 246 if (last_bfp) 247 __free_ovflpage(hashp, last_bfp); 248 last_bfp = rbufp; 249 if (!rbufp) 250 return (-1); /* Error. */ 251 bp = (uint16_t *)(void *)rbufp->page; 252 } 253 254 /* 255 * If we get here then rbufp points to the last page of the big 256 * key/data pair. Bufp points to the first one -- it should now be 257 * empty pointing to the next page after this pair. Can't free it 258 * because we don't have the page pointing to it. 259 */ 260 261 /* This is information from the last page of the pair. */ 262 n = bp[0]; 263 pageno = bp[n - 1]; 264 265 /* Now, bp is the first page of the pair. */ 266 bp = (uint16_t *)(void *)bufp->page; 267 if (n > 2) { 268 /* There is an overflow page. */ 269 bp[1] = pageno; 270 bp[2] = OVFLPAGE; 271 bufp->ovfl = rbufp->ovfl; 272 } else 273 /* This is the last page. */ 274 bufp->ovfl = NULL; 275 n -= 2; 276 bp[0] = n; 277 temp = HASH_BSIZE(hashp) - PAGE_META(n); 278 _DBFIT(temp, uint16_t); 279 FREESPACE(bp) = (uint16_t)temp; 280 OFFSET(bp) = HASH_BSIZE(hashp); 281 282 bufp->flags |= BUF_MOD; 283 if (rbufp) 284 __free_ovflpage(hashp, rbufp); 285 if (last_bfp && last_bfp != rbufp) 286 __free_ovflpage(hashp, last_bfp); 287 288 hashp->NKEYS--; 289 return (0); 290 } 291 /* 292 * Returns: 293 * 0 = key not found 294 * -1 = get next overflow page 295 * -2 means key not found and this is big key/data 296 * -3 error 297 */ 298 int 299 __find_bigpair(HTAB *hashp, BUFHEAD *bufp, int ndx, char *key, int size) 300 { 301 uint16_t *bp; 302 char *p; 303 int ksize; 304 uint16_t bytes; 305 char *kkey; 306 307 bp = (uint16_t *)(void *)bufp->page; 308 p = bufp->page; 309 ksize = size; 310 kkey = key; 311 312 for (bytes = HASH_BSIZE(hashp) - bp[ndx]; 313 bytes <= size && bp[ndx + 1] == PARTIAL_KEY; 314 bytes = HASH_BSIZE(hashp) - bp[ndx]) { 315 if (memcmp(p + bp[ndx], kkey, (size_t)bytes)) 316 return (-2); 317 kkey += bytes; 318 ksize -= bytes; 319 bufp = __get_buf(hashp, (uint32_t)bp[ndx + 2], bufp, 0); 320 if (!bufp) 321 return (-3); 322 p = bufp->page; 323 bp = (uint16_t *)(void *)p; 324 ndx = 1; 325 } 326 327 if (bytes != ksize || memcmp(p + bp[ndx], kkey, (size_t)bytes)) { 328 #ifdef HASH_STATISTICS 329 ++hash_collisions; 330 #endif 331 return (-2); 332 } else 333 return (ndx); 334 } 335 336 /* 337 * Given the buffer pointer of the first overflow page of a big pair, 338 * find the end of the big pair 339 * 340 * This will set bpp to the buffer header of the last page of the big pair. 341 * It will return the pageno of the overflow page following the last page 342 * of the pair; 0 if there isn't any (i.e. big pair is the last key in the 343 * bucket) 344 */ 345 uint16_t 346 __find_last_page(HTAB *hashp, BUFHEAD **bpp) 347 { 348 BUFHEAD *bufp; 349 uint16_t *bp, pageno; 350 int n; 351 352 bufp = *bpp; 353 bp = (uint16_t *)(void *)bufp->page; 354 for (;;) { 355 n = bp[0]; 356 357 /* 358 * This is the last page if: the tag is FULL_KEY_DATA and 359 * either only 2 entries OVFLPAGE marker is explicit there 360 * is freespace on the page. 361 */ 362 if (bp[2] == FULL_KEY_DATA && 363 ((n == 2) || (bp[n] == OVFLPAGE) || (FREESPACE(bp)))) 364 break; 365 366 pageno = bp[n - 1]; 367 bufp = __get_buf(hashp, (uint32_t)pageno, bufp, 0); 368 if (!bufp) 369 return (0); /* Need to indicate an error! */ 370 bp = (uint16_t *)(void *)bufp->page; 371 } 372 373 *bpp = bufp; 374 if (bp[0] > 2) 375 return (bp[3]); 376 else 377 return (0); 378 } 379 380 /* 381 * Return the data for the key/data pair that begins on this page at this 382 * index (index should always be 1). 383 */ 384 int 385 __big_return(HTAB *hashp, BUFHEAD *bufp, int ndx, DBT *val, int set_current) 386 { 387 BUFHEAD *save_p; 388 uint16_t *bp, len, off, save_addr; 389 char *tp; 390 391 bp = (uint16_t *)(void *)bufp->page; 392 while (bp[ndx + 1] == PARTIAL_KEY) { 393 bufp = __get_buf(hashp, (uint32_t)bp[bp[0] - 1], bufp, 0); 394 if (!bufp) 395 return (-1); 396 bp = (uint16_t *)(void *)bufp->page; 397 ndx = 1; 398 } 399 400 if (bp[ndx + 1] == FULL_KEY) { 401 bufp = __get_buf(hashp, (uint32_t)bp[bp[0] - 1], bufp, 0); 402 if (!bufp) 403 return (-1); 404 bp = (uint16_t *)(void *)bufp->page; 405 save_p = bufp; 406 save_addr = save_p->addr; 407 off = bp[1]; 408 len = 0; 409 } else 410 if (!FREESPACE(bp)) { 411 /* 412 * This is a hack. We can't distinguish between 413 * FULL_KEY_DATA that contains complete data or 414 * incomplete data, so we require that if the data 415 * is complete, there is at least 1 byte of free 416 * space left. 417 */ 418 off = bp[bp[0]]; 419 len = bp[1] - off; 420 save_p = bufp; 421 save_addr = bufp->addr; 422 bufp = __get_buf(hashp, (uint32_t)bp[bp[0] - 1], bufp, 423 0); 424 if (!bufp) 425 return (-1); 426 bp = (uint16_t *)(void *)bufp->page; 427 } else { 428 /* The data is all on one page. */ 429 tp = (char *)(void *)bp; 430 off = bp[bp[0]]; 431 val->data = (uint8_t *)tp + off; 432 val->size = bp[1] - off; 433 if (set_current) { 434 if (bp[0] == 2) { /* No more buckets in 435 * chain */ 436 hashp->cpage = NULL; 437 hashp->cbucket++; 438 hashp->cndx = 1; 439 } else { 440 hashp->cpage = __get_buf(hashp, 441 (uint32_t)bp[bp[0] - 1], bufp, 0); 442 if (!hashp->cpage) 443 return (-1); 444 hashp->cndx = 1; 445 if (!((uint16_t *)(void *) 446 hashp->cpage->page)[0]) { 447 hashp->cbucket++; 448 hashp->cpage = NULL; 449 } 450 } 451 } 452 return (0); 453 } 454 455 val->size = collect_data(hashp, bufp, (int)len, set_current); 456 if (val->size == (size_t)-1) 457 return (-1); 458 if (save_p->addr != save_addr) { 459 /* We are pretty short on buffers. */ 460 errno = EINVAL; /* OUT OF BUFFERS */ 461 return (-1); 462 } 463 memmove(hashp->tmp_buf, (save_p->page) + off, (size_t)len); 464 val->data = (uint8_t *)hashp->tmp_buf; 465 return (0); 466 } 467 /* 468 * Count how big the total datasize is by recursing through the pages. Then 469 * allocate a buffer and copy the data as you recurse up. 470 */ 471 static int 472 collect_data(HTAB *hashp, BUFHEAD *bufp, int len, int set) 473 { 474 uint16_t *bp; 475 char *p; 476 BUFHEAD *xbp; 477 uint16_t save_addr; 478 int mylen, totlen; 479 480 p = bufp->page; 481 bp = (uint16_t *)(void *)p; 482 mylen = HASH_BSIZE(hashp) - bp[1]; 483 save_addr = bufp->addr; 484 485 if (bp[2] == FULL_KEY_DATA) { /* End of Data */ 486 totlen = len + mylen; 487 if (hashp->tmp_buf) 488 free(hashp->tmp_buf); 489 if ((hashp->tmp_buf = calloc(1, (size_t)totlen)) == NULL) 490 return (-1); 491 if (set) { 492 hashp->cndx = 1; 493 if (bp[0] == 2) { /* No more buckets in chain */ 494 hashp->cpage = NULL; 495 hashp->cbucket++; 496 } else { 497 hashp->cpage = 498 __get_buf(hashp, (uint32_t)bp[bp[0] - 1], 499 bufp, 0); 500 if (!hashp->cpage) 501 return (-1); 502 else if (!((uint16_t *)(void *)hashp->cpage->page)[0]) { 503 hashp->cbucket++; 504 hashp->cpage = NULL; 505 } 506 } 507 } 508 } else { 509 xbp = __get_buf(hashp, (uint32_t)bp[bp[0] - 1], bufp, 0); 510 if (!xbp || ((totlen = 511 collect_data(hashp, xbp, len + mylen, set)) < 1)) 512 return (-1); 513 } 514 if (bufp->addr != save_addr) { 515 errno = EINVAL; /* Out of buffers. */ 516 return (-1); 517 } 518 memmove(&hashp->tmp_buf[len], (bufp->page) + bp[1], (size_t)mylen); 519 return (totlen); 520 } 521 522 /* 523 * Fill in the key and data for this big pair. 524 */ 525 int 526 __big_keydata(HTAB *hashp, BUFHEAD *bufp, DBT *key, DBT *val, int set) 527 { 528 key->size = collect_key(hashp, bufp, 0, val, set); 529 if (key->size == (size_t)-1) 530 return (-1); 531 key->data = (uint8_t *)hashp->tmp_key; 532 return (0); 533 } 534 535 /* 536 * Count how big the total key size is by recursing through the pages. Then 537 * collect the data, allocate a buffer and copy the key as you recurse up. 538 */ 539 static int 540 collect_key(HTAB *hashp, BUFHEAD *bufp, int len, DBT *val, int set) 541 { 542 BUFHEAD *xbp; 543 char *p; 544 int mylen, totlen; 545 uint16_t *bp, save_addr; 546 547 p = bufp->page; 548 bp = (uint16_t *)(void *)p; 549 mylen = HASH_BSIZE(hashp) - bp[1]; 550 551 save_addr = bufp->addr; 552 totlen = len + mylen; 553 if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) { /* End of Key. */ 554 if (hashp->tmp_key != NULL) 555 free(hashp->tmp_key); 556 if ((hashp->tmp_key = calloc(1, (size_t)totlen)) == NULL) 557 return (-1); 558 if (__big_return(hashp, bufp, 1, val, set)) 559 return (-1); 560 } else { 561 xbp = __get_buf(hashp, (uint32_t)bp[bp[0] - 1], bufp, 0); 562 if (!xbp || ((totlen = 563 collect_key(hashp, xbp, totlen, val, set)) < 1)) 564 return (-1); 565 } 566 if (bufp->addr != save_addr) { 567 errno = EINVAL; /* MIS -- OUT OF BUFFERS */ 568 return (-1); 569 } 570 memmove(&hashp->tmp_key[len], (bufp->page) + bp[1], (size_t)mylen); 571 return (totlen); 572 } 573 574 /* 575 * Returns: 576 * 0 => OK 577 * -1 => error 578 */ 579 int 580 __big_split( 581 HTAB *hashp, 582 BUFHEAD *op, /* Pointer to where to put keys that go in old bucket */ 583 BUFHEAD *np, /* Pointer to new bucket page */ 584 /* Pointer to first page containing the big key/data */ 585 BUFHEAD *big_keyp, 586 int addr, /* Address of big_keyp */ 587 uint32_t obucket,/* Old Bucket */ 588 SPLIT_RETURN *ret 589 ) 590 { 591 BUFHEAD *tmpp; 592 uint16_t *tp; 593 BUFHEAD *bp; 594 DBT key, val; 595 uint32_t change; 596 uint16_t free_space, n, off; 597 size_t temp; 598 599 bp = big_keyp; 600 601 /* Now figure out where the big key/data goes */ 602 if (__big_keydata(hashp, big_keyp, &key, &val, 0)) 603 return (-1); 604 change = (__call_hash(hashp, key.data, (int)key.size) != obucket); 605 606 if ((ret->next_addr = __find_last_page(hashp, &big_keyp)) != 0) { 607 if (!(ret->nextp = 608 __get_buf(hashp, (uint32_t)ret->next_addr, big_keyp, 0))) 609 return (-1); 610 } else 611 ret->nextp = NULL; 612 613 /* Now make one of np/op point to the big key/data pair */ 614 _DIAGASSERT(np->ovfl == NULL); 615 if (change) 616 tmpp = np; 617 else 618 tmpp = op; 619 620 tmpp->flags |= BUF_MOD; 621 #ifdef DEBUG1 622 (void)fprintf(stderr, 623 "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp->addr, 624 (tmpp->ovfl ? tmpp->ovfl->addr : 0), (bp ? bp->addr : 0)); 625 #endif 626 tmpp->ovfl = bp; /* one of op/np point to big_keyp */ 627 tp = (uint16_t *)(void *)tmpp->page; 628 _DIAGASSERT(FREESPACE(tp) >= OVFLSIZE); 629 n = tp[0]; 630 off = OFFSET(tp); 631 free_space = FREESPACE(tp); 632 tp[++n] = (uint16_t)addr; 633 tp[++n] = OVFLPAGE; 634 tp[0] = n; 635 OFFSET(tp) = off; 636 temp = free_space - OVFLSIZE; 637 _DBFIT(temp, uint16_t); 638 FREESPACE(tp) = (uint16_t)temp; 639 640 /* 641 * Finally, set the new and old return values. BIG_KEYP contains a 642 * pointer to the last page of the big key_data pair. Make sure that 643 * big_keyp has no following page (2 elements) or create an empty 644 * following page. 645 */ 646 647 ret->newp = np; 648 ret->oldp = op; 649 650 tp = (uint16_t *)(void *)big_keyp->page; 651 big_keyp->flags |= BUF_MOD; 652 if (tp[0] > 2) { 653 /* 654 * There may be either one or two offsets on this page. If 655 * there is one, then the overflow page is linked on normally 656 * and tp[4] is OVFLPAGE. If there are two, tp[4] contains 657 * the second offset and needs to get stuffed in after the 658 * next overflow page is added. 659 */ 660 n = tp[4]; 661 free_space = FREESPACE(tp); 662 off = OFFSET(tp); 663 tp[0] -= 2; 664 temp = free_space + OVFLSIZE; 665 _DBFIT(temp, uint16_t); 666 FREESPACE(tp) = (uint16_t)temp; 667 OFFSET(tp) = off; 668 tmpp = __add_ovflpage(hashp, big_keyp); 669 if (!tmpp) 670 return (-1); 671 tp[4] = n; 672 } else 673 tmpp = big_keyp; 674 675 if (change) 676 ret->newp = tmpp; 677 else 678 ret->oldp = tmpp; 679 return (0); 680 } 681
Indexes created Sun Sep 21 14:09:52 GMT 2025