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