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