lib/libc/db/hash/hash_bigkey.c

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