lib/libc/db/hash/bigkey.c

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