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