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