37 #if defined(LIBC_SCCS) && !defined(lint)
38 static char sccsid[] =
"@(#)hash_bigkey.c 8.3 (Berkeley) 5/31/94";
59 #include <sys/param.h>
70 #include "../include/db.h"
76 static int collect_data __P((
HTAB *,
BUFHEAD *,
int,
int));
88 __big_insert(hashp, bufp, key,
val)
93 register u_int16_t *p;
94 int key_size, n, val_size;
95 u_int16_t space, move_bytes, off;
96 char *cp, *key_data, *val_data;
101 key_data = (
char *)key->data;
102 key_size = key->size;
103 val_data = (
char *)val->data;
104 val_size = val->size;
107 for (space = FREESPACE(p) - BIGOVERHEAD; key_size;
108 space = FREESPACE(p) - BIGOVERHEAD) {
109 move_bytes = MIN(space, key_size);
110 off = OFFSET(p) - move_bytes;
111 memmove(cp + off, key_data, move_bytes);
112 key_size -= move_bytes;
113 key_data += move_bytes;
117 FREESPACE(p) = off - PAGE_META(n);
120 bufp = __add_ovflpage(hashp, bufp);
126 move_bytes = MIN(FREESPACE(p), val_size);
127 off = OFFSET(p) - move_bytes;
129 memmove(cp + off, val_data, move_bytes);
130 val_data += move_bytes;
131 val_size -= move_bytes;
132 p[n - 2] = FULL_KEY_DATA;
133 FREESPACE(p) = FREESPACE(p) - move_bytes;
138 p = (u_int16_t *)bufp->page;
140 bufp->flags |= BUF_MOD;
144 for (space = FREESPACE(p) - BIGOVERHEAD; val_size;
145 space = FREESPACE(p) - BIGOVERHEAD) {
146 move_bytes = MIN(space, val_size);
151 if ((
int) space == val_size && (
size_t) val_size == val->size)
153 off = OFFSET(p) - move_bytes;
154 memmove(cp + off, val_data, move_bytes);
155 val_size -= move_bytes;
156 val_data += move_bytes;
160 FREESPACE(p) = off - PAGE_META(n);
164 bufp = __add_ovflpage(hashp, bufp);
170 p[n] = FULL_KEY_DATA;
171 bufp->flags |= BUF_MOD;
188 __big_delete(hashp, bufp)
192 register BUFHEAD *last_bfp, *rbufp;
193 u_int16_t *bp, pageno;
198 bp = (u_int16_t *)bufp->page;
202 while (!key_done || (bp[2] != FULL_KEY_DATA)) {
203 if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA)
211 if (bp[2] == FULL_KEY_DATA && FREESPACE(bp))
213 pageno = bp[bp[0] - 1];
214 rbufp->flags |= BUF_MOD;
215 rbufp = __get_buf(hashp, pageno, rbufp, 0);
217 __free_ovflpage(hashp, last_bfp);
221 bp = (u_int16_t *)rbufp->page;
236 bp = (u_int16_t *)bufp->page;
241 bufp->ovfl = rbufp->ovfl;
247 FREESPACE(bp) = hashp->BSIZE - PAGE_META(n);
248 OFFSET(bp) = hashp->BSIZE - 1;
250 bufp->flags |= BUF_MOD;
252 __free_ovflpage(hashp, rbufp);
253 if (last_bfp && last_bfp != rbufp)
254 __free_ovflpage(hashp, last_bfp);
267 __find_bigpair(hashp, bufp, ndx, key, size)
274 register u_int16_t *bp;
280 bp = (u_int16_t *)bufp->page;
285 for (bytes = hashp->BSIZE - bp[ndx];
286 bytes <= size && bp[ndx + 1] == PARTIAL_KEY;
287 bytes = hashp->BSIZE - bp[ndx]) {
288 if (memcmp(p + bp[ndx], kkey, bytes))
292 bufp = __get_buf(hashp, bp[ndx + 2], bufp, 0);
300 if (bytes != ksize || memcmp(p + bp[ndx], kkey, bytes)) {
301 #ifdef HASH_STATISTICS
319 __find_last_page(hashp, bpp)
324 u_int16_t *bp, pageno;
328 bp = (u_int16_t *)bufp->page;
337 if (bp[2] == FULL_KEY_DATA &&
338 ((n == 2) || (bp[n] == OVFLPAGE) || (FREESPACE(bp))))
342 bufp = __get_buf(hashp, pageno, bufp, 0);
345 bp = (u_int16_t *)bufp->page;
360 __big_return(hashp, bufp, ndx, val, set_current)
368 u_int16_t *bp, len, off, save_addr;
371 bp = (u_int16_t *)bufp->page;
372 while (bp[ndx + 1] == PARTIAL_KEY) {
373 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
376 bp = (u_int16_t *)bufp->page;
380 if (bp[ndx + 1] == FULL_KEY) {
381 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
384 bp = (u_int16_t *)bufp->page;
386 save_addr = save_p->addr;
390 if (!FREESPACE(bp)) {
401 save_addr = bufp->addr;
402 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
405 bp = (u_int16_t *)bufp->page;
410 val->data = (u_char *)tp + off;
411 val->size = bp[1] - off;
419 hashp->cpage = __get_buf(hashp,
420 bp[bp[0] - 1], bufp, 0);
425 hashp->cpage->page)[0]) {
434 val->size = collect_data(hashp, bufp, (
int)len, set_current);
435 if (val->size == (
size_t) -1)
437 if (save_p->addr != save_addr) {
442 memmove(hashp->tmp_buf, (save_p->page) + off, len);
443 val->data = (u_char *)hashp->tmp_buf;
451 collect_data(hashp, bufp, len, set)
456 register u_int16_t *bp;
464 mylen = hashp->BSIZE - bp[1];
465 save_addr = bufp->addr;
467 if (bp[2] == FULL_KEY_DATA) {
468 totlen = len + mylen;
470 free(hashp->tmp_buf);
471 if ((hashp->tmp_buf = (
char *)malloc(totlen)) == NULL)
480 __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
483 else if (!((u_int16_t *)hashp->cpage->page)[0]) {
490 xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
491 if (!xbp || ((totlen =
492 collect_data(hashp, xbp, len + mylen, set)) < 1))
495 if (bufp->addr != save_addr) {
499 memmove(&hashp->tmp_buf[len], (bufp->page) + bp[1], mylen);
507 __big_keydata(hashp, bufp, key, val, set)
513 key->size = collect_key(hashp, bufp, 0, val, set);
514 if (key->size == (
size_t) -1)
516 key->data = (u_char *)hashp->tmp_key;
525 collect_key(hashp, bufp, len, val, set)
535 u_int16_t *bp, save_addr;
539 mylen = hashp->BSIZE - bp[1];
541 save_addr = bufp->addr;
542 totlen = len + mylen;
543 if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) {
544 if (hashp->tmp_key != NULL)
545 free(hashp->tmp_key);
546 if ((hashp->tmp_key = (
char *)malloc(totlen)) == NULL)
548 if (__big_return(hashp, bufp, 1, val, set))
551 xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
552 if (!xbp || ((totlen =
553 collect_key(hashp, xbp, totlen, val, set)) < 1))
556 if (bufp->addr != save_addr) {
560 memmove(&hashp->tmp_key[len], (bufp->page) + bp[1], mylen);
570 __big_split(hashp, op, np, big_keyp, addr, obucket, ret)
581 register u_int16_t *tp;
585 u_int16_t free_space, n, off;
590 if (__big_keydata(hashp, big_keyp, &key, &val, 0))
592 change = (__call_hash(hashp, key.data, key.size) != obucket);
594 if ((ret->next_addr = __find_last_page(hashp, &big_keyp))) {
596 __get_buf(hashp, ret->next_addr, big_keyp, 0)))
603 assert(np->ovfl == NULL);
610 tmpp->flags |= BUF_MOD;
612 (void)fprintf(stderr,
613 "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp->addr,
614 (tmpp->ovfl ? tmpp->ovfl->addr : 0), (bp ? bp->addr : 0));
617 tp = (u_int16_t *)tmpp->page;
619 assert(FREESPACE(tp) >= OVFLSIZE);
623 free_space = FREESPACE(tp);
624 tp[++n] = (u_int16_t)addr;
628 FREESPACE(tp) = free_space - OVFLSIZE;
640 tp = (u_int16_t *)big_keyp->page;
641 big_keyp->flags |= BUF_MOD;
651 free_space = FREESPACE(tp);
654 FREESPACE(tp) = free_space + OVFLSIZE;
656 tmpp = __add_ovflpage(hashp, big_keyp);