2 * Copyright (c) 1990, 1993, 1994
3 * The Regents of the University of California. All rights reserved.
5 * This code is derived from software contributed to Berkeley by
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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 * 4. 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.
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
33 #if defined(LIBC_SCCS) && !defined(lint)
34 static char sccsid[] = "@(#)hash_bigkey.c 8.3 (Berkeley) 5/31/94";
35 #endif /* LIBC_SCCS and not lint */
36 #include <sys/cdefs.h>
37 __FBSDID("$FreeBSD$");
42 * Big key/data handling for the hashing package.
57 #include <sys/param.h>
73 static int collect_key(HTAB *, BUFHEAD *, int, DBT *, int);
74 static int collect_data(HTAB *, BUFHEAD *, int, int);
79 * You need to do an insert and the key/data pair is too big
86 __big_insert(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val)
90 unsigned int val_size;
91 u_int16_t space, move_bytes, off;
92 char *cp, *key_data, *val_data;
94 cp = bufp->page; /* Character pointer of p. */
97 key_data = (char *)key->data;
99 val_data = (char *)val->data;
100 val_size = val->size;
102 /* First move the Key */
103 for (space = FREESPACE(p) - BIGOVERHEAD; key_size;
104 space = FREESPACE(p) - BIGOVERHEAD) {
105 move_bytes = MIN(space, key_size);
106 off = OFFSET(p) - move_bytes;
107 memmove(cp + off, key_data, move_bytes);
108 key_size -= move_bytes;
109 key_data += move_bytes;
113 FREESPACE(p) = off - PAGE_META(n);
116 bufp = __add_ovflpage(hashp, bufp);
121 space = FREESPACE(p);
123 move_bytes = MIN(space, val_size);
125 * If the data would fit exactly in the
126 * remaining space, we must overflow it to the
127 * next page; otherwise the invariant that the
128 * data must end on a page with FREESPACE
129 * non-zero would fail.
131 if (space == val_size && val_size == val->size)
133 off = OFFSET(p) - move_bytes;
134 memmove(cp + off, val_data, move_bytes);
135 val_data += move_bytes;
136 val_size -= move_bytes;
138 p[n - 2] = FULL_KEY_DATA;
139 FREESPACE(p) = FREESPACE(p) - move_bytes;
146 p = (u_int16_t *)bufp->page;
148 bufp->flags |= BUF_MOD;
151 /* Now move the data */
152 for (space = FREESPACE(p) - BIGOVERHEAD; val_size;
153 space = FREESPACE(p) - BIGOVERHEAD) {
154 move_bytes = MIN(space, val_size);
156 * Here's the hack to make sure that if the data ends on the
157 * same page as the key ends, FREESPACE is at least one.
159 if (space == val_size && val_size == val->size)
161 off = OFFSET(p) - move_bytes;
162 memmove(cp + off, val_data, move_bytes);
163 val_size -= move_bytes;
164 val_data += move_bytes;
168 FREESPACE(p) = off - PAGE_META(n);
172 bufp = __add_ovflpage(hashp, bufp);
178 p[n] = FULL_KEY_DATA;
179 bufp->flags |= BUF_MOD;
185 * Called when bufp's page contains a partial key (index should be 1)
187 * All pages in the big key/data pair except bufp are freed. We cannot
188 * free bufp because the page pointing to it is lost and we can't get rid
196 __big_delete(HTAB *hashp, BUFHEAD *bufp)
198 BUFHEAD *last_bfp, *rbufp;
199 u_int16_t *bp, pageno;
204 bp = (u_int16_t *)bufp->page;
208 while (!key_done || (bp[2] != FULL_KEY_DATA)) {
209 if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA)
213 * If there is freespace left on a FULL_KEY_DATA page, then
214 * the data is short and fits entirely on this page, and this
217 if (bp[2] == FULL_KEY_DATA && FREESPACE(bp))
219 pageno = bp[bp[0] - 1];
220 rbufp->flags |= BUF_MOD;
221 rbufp = __get_buf(hashp, pageno, rbufp, 0);
223 __free_ovflpage(hashp, last_bfp);
226 return (-1); /* Error. */
227 bp = (u_int16_t *)rbufp->page;
231 * If we get here then rbufp points to the last page of the big
232 * key/data pair. Bufp points to the first one -- it should now be
233 * empty pointing to the next page after this pair. Can't free it
234 * because we don't have the page pointing to it.
237 /* This is information from the last page of the pair. */
241 /* Now, bp is the first page of the pair. */
242 bp = (u_int16_t *)bufp->page;
244 /* There is an overflow page. */
247 bufp->ovfl = rbufp->ovfl;
249 /* This is the last page. */
253 FREESPACE(bp) = hashp->BSIZE - PAGE_META(n);
254 OFFSET(bp) = hashp->BSIZE;
256 bufp->flags |= BUF_MOD;
258 __free_ovflpage(hashp, rbufp);
259 if (last_bfp && last_bfp != rbufp)
260 __free_ovflpage(hashp, last_bfp);
268 * -1 = get next overflow page
269 * -2 means key not found and this is big key/data
273 __find_bigpair(HTAB *hashp, BUFHEAD *bufp, int ndx, char *key, int size)
281 bp = (u_int16_t *)bufp->page;
286 for (bytes = hashp->BSIZE - bp[ndx];
287 bytes <= size && bp[ndx + 1] == PARTIAL_KEY;
288 bytes = hashp->BSIZE - bp[ndx]) {
289 if (memcmp(p + bp[ndx], kkey, bytes))
293 bufp = __get_buf(hashp, bp[ndx + 2], bufp, 0);
301 if (bytes != ksize || memcmp(p + bp[ndx], kkey, bytes)) {
302 #ifdef HASH_STATISTICS
311 * Given the buffer pointer of the first overflow page of a big pair,
312 * find the end of the big pair
314 * This will set bpp to the buffer header of the last page of the big pair.
315 * It will return the pageno of the overflow page following the last page
316 * of the pair; 0 if there isn't any (i.e. big pair is the last key in the
320 __find_last_page(HTAB *hashp, BUFHEAD **bpp)
323 u_int16_t *bp, pageno;
327 bp = (u_int16_t *)bufp->page;
332 * This is the last page if: the tag is FULL_KEY_DATA and
333 * either only 2 entries OVFLPAGE marker is explicit there
334 * is freespace on the page.
336 if (bp[2] == FULL_KEY_DATA &&
337 ((n == 2) || (bp[n] == OVFLPAGE) || (FREESPACE(bp))))
341 bufp = __get_buf(hashp, pageno, bufp, 0);
343 return (0); /* Need to indicate an error! */
344 bp = (u_int16_t *)bufp->page;
355 * Return the data for the key/data pair that begins on this page at this
356 * index (index should always be 1).
359 __big_return(HTAB *hashp, BUFHEAD *bufp, int ndx, DBT *val, int set_current)
362 u_int16_t *bp, len, off, save_addr;
365 bp = (u_int16_t *)bufp->page;
366 while (bp[ndx + 1] == PARTIAL_KEY) {
367 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
370 bp = (u_int16_t *)bufp->page;
374 if (bp[ndx + 1] == FULL_KEY) {
375 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
378 bp = (u_int16_t *)bufp->page;
380 save_addr = save_p->addr;
384 if (!FREESPACE(bp)) {
386 * This is a hack. We can't distinguish between
387 * FULL_KEY_DATA that contains complete data or
388 * incomplete data, so we require that if the data
389 * is complete, there is at least 1 byte of free
395 save_addr = bufp->addr;
396 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
399 bp = (u_int16_t *)bufp->page;
401 /* The data is all on one page. */
404 val->data = (u_char *)tp + off;
405 val->size = bp[1] - off;
407 if (bp[0] == 2) { /* No more buckets in
413 hashp->cpage = __get_buf(hashp,
414 bp[bp[0] - 1], bufp, 0);
419 hashp->cpage->page)[0]) {
428 val->size = (size_t)collect_data(hashp, bufp, (int)len, set_current);
429 if (val->size == (size_t)-1)
431 if (save_p->addr != save_addr) {
432 /* We are pretty short on buffers. */
433 errno = EINVAL; /* OUT OF BUFFERS */
436 memmove(hashp->tmp_buf, (save_p->page) + off, len);
437 val->data = (u_char *)hashp->tmp_buf;
441 * Count how big the total datasize is by recursing through the pages. Then
442 * allocate a buffer and copy the data as you recurse up.
445 collect_data(HTAB *hashp, BUFHEAD *bufp, int len, int set)
455 mylen = hashp->BSIZE - bp[1];
456 save_addr = bufp->addr;
458 if (bp[2] == FULL_KEY_DATA) { /* End of Data */
459 totlen = len + mylen;
461 free(hashp->tmp_buf);
462 if ((hashp->tmp_buf = (char *)malloc(totlen)) == NULL)
466 if (bp[0] == 2) { /* No more buckets in chain */
471 __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
474 else if (!((u_int16_t *)hashp->cpage->page)[0]) {
481 xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
482 if (!xbp || ((totlen =
483 collect_data(hashp, xbp, len + mylen, set)) < 1))
486 if (bufp->addr != save_addr) {
487 errno = EINVAL; /* Out of buffers. */
490 memmove(&hashp->tmp_buf[len], (bufp->page) + bp[1], mylen);
495 * Fill in the key and data for this big pair.
498 __big_keydata(HTAB *hashp, BUFHEAD *bufp, DBT *key, DBT *val, int set)
500 key->size = (size_t)collect_key(hashp, bufp, 0, val, set);
501 if (key->size == (size_t)-1)
503 key->data = (u_char *)hashp->tmp_key;
508 * Count how big the total key size is by recursing through the pages. Then
509 * collect the data, allocate a buffer and copy the key as you recurse up.
512 collect_key(HTAB *hashp, BUFHEAD *bufp, int len, DBT *val, int set)
517 u_int16_t *bp, save_addr;
521 mylen = hashp->BSIZE - bp[1];
523 save_addr = bufp->addr;
524 totlen = len + mylen;
525 if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) { /* End of Key. */
526 if (hashp->tmp_key != NULL)
527 free(hashp->tmp_key);
528 if ((hashp->tmp_key = (char *)malloc(totlen)) == NULL)
530 if (__big_return(hashp, bufp, 1, val, set))
533 xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
534 if (!xbp || ((totlen =
535 collect_key(hashp, xbp, totlen, val, set)) < 1))
538 if (bufp->addr != save_addr) {
539 errno = EINVAL; /* MIS -- OUT OF BUFFERS */
542 memmove(&hashp->tmp_key[len], (bufp->page) + bp[1], mylen);
552 __big_split(HTAB *hashp,
553 BUFHEAD *op, /* Pointer to where to put keys that go in old bucket */
554 BUFHEAD *np, /* Pointer to new bucket page */
555 BUFHEAD *big_keyp, /* Pointer to first page containing the big key/data */
556 int addr, /* Address of big_keyp */
557 u_int32_t obucket, /* Old Bucket */
563 u_int16_t free_space, n, off, *tp;
567 /* Now figure out where the big key/data goes */
568 if (__big_keydata(hashp, big_keyp, &key, &val, 0))
570 change = (__call_hash(hashp, key.data, key.size) != obucket);
572 if ( (ret->next_addr = __find_last_page(hashp, &big_keyp)) ) {
574 __get_buf(hashp, ret->next_addr, big_keyp, 0)))
579 /* Now make one of np/op point to the big key/data pair */
581 assert(np->ovfl == NULL);
588 tmpp->flags |= BUF_MOD;
590 (void)fprintf(stderr,
591 "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp->addr,
592 (tmpp->ovfl ? tmpp->ovfl->addr : 0), (bp ? bp->addr : 0));
594 tmpp->ovfl = bp; /* one of op/np point to big_keyp */
595 tp = (u_int16_t *)tmpp->page;
597 assert(FREESPACE(tp) >= OVFLSIZE);
601 free_space = FREESPACE(tp);
602 tp[++n] = (u_int16_t)addr;
606 FREESPACE(tp) = free_space - OVFLSIZE;
609 * Finally, set the new and old return values. BIG_KEYP contains a
610 * pointer to the last page of the big key_data pair. Make sure that
611 * big_keyp has no following page (2 elements) or create an empty
618 tp = (u_int16_t *)big_keyp->page;
619 big_keyp->flags |= BUF_MOD;
622 * There may be either one or two offsets on this page. If
623 * there is one, then the overflow page is linked on normally
624 * and tp[4] is OVFLPAGE. If there are two, tp[4] contains
625 * the second offset and needs to get stuffed in after the
626 * next overflow page is added.
629 free_space = FREESPACE(tp);
632 FREESPACE(tp) = free_space + OVFLSIZE;
634 tmpp = __add_ovflpage(hashp, big_keyp);