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 * 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.
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
37 #if defined(LIBC_SCCS) && !defined(lint)
38 static char sccsid[] = "@(#)hash_bigkey.c 8.3 (Berkeley) 5/31/94";
39 #endif /* LIBC_SCCS and not lint */
44 * Big key/data handling for the hashing package.
59 #include <sys/param.h>
75 static int collect_key __P((HTAB *, BUFHEAD *, int, DBT *, int));
76 static int collect_data __P((HTAB *, BUFHEAD *, int, int));
81 * You need to do an insert and the key/data pair is too big
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;
98 cp = bufp->page; /* Character pointer of p. */
101 key_data = (char *)key->data;
102 key_size = key->size;
103 val_data = (char *)val->data;
104 val_size = val->size;
106 /* First move the Key */
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;
137 p = (u_int16_t *)bufp->page;
139 bufp->flags |= BUF_MOD;
142 /* Now move the data */
143 for (space = FREESPACE(p) - BIGOVERHEAD; val_size;
144 space = FREESPACE(p) - BIGOVERHEAD) {
145 move_bytes = MIN(space, val_size);
147 * Here's the hack to make sure that if the data ends on the
148 * same page as the key ends, FREESPACE is at least one.
150 if (space == val_size && val_size == val->size)
152 off = OFFSET(p) - move_bytes;
153 memmove(cp + off, val_data, move_bytes);
154 val_size -= move_bytes;
155 val_data += move_bytes;
159 FREESPACE(p) = off - PAGE_META(n);
163 bufp = __add_ovflpage(hashp, bufp);
169 p[n] = FULL_KEY_DATA;
170 bufp->flags |= BUF_MOD;
176 * Called when bufp's page contains a partial key (index should be 1)
178 * All pages in the big key/data pair except bufp are freed. We cannot
179 * free bufp because the page pointing to it is lost and we can't get rid
187 __big_delete(hashp, bufp)
191 register BUFHEAD *last_bfp, *rbufp;
192 u_int16_t *bp, pageno;
197 bp = (u_int16_t *)bufp->page;
201 while (!key_done || (bp[2] != FULL_KEY_DATA)) {
202 if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA)
206 * If there is freespace left on a FULL_KEY_DATA page, then
207 * the data is short and fits entirely on this page, and this
210 if (bp[2] == FULL_KEY_DATA && FREESPACE(bp))
212 pageno = bp[bp[0] - 1];
213 rbufp->flags |= BUF_MOD;
214 rbufp = __get_buf(hashp, pageno, rbufp, 0);
216 __free_ovflpage(hashp, last_bfp);
219 return (-1); /* Error. */
220 bp = (u_int16_t *)rbufp->page;
224 * If we get here then rbufp points to the last page of the big
225 * key/data pair. Bufp points to the first one -- it should now be
226 * empty pointing to the next page after this pair. Can't free it
227 * because we don't have the page pointing to it.
230 /* This is information from the last page of the pair. */
234 /* Now, bp is the first page of the pair. */
235 bp = (u_int16_t *)bufp->page;
237 /* There is an overflow page. */
240 bufp->ovfl = rbufp->ovfl;
242 /* This is the last page. */
246 FREESPACE(bp) = hashp->BSIZE - PAGE_META(n);
247 OFFSET(bp) = hashp->BSIZE - 1;
249 bufp->flags |= BUF_MOD;
251 __free_ovflpage(hashp, rbufp);
252 if (last_bfp != rbufp)
253 __free_ovflpage(hashp, last_bfp);
261 * -1 = get next overflow page
262 * -2 means key not found and this is big key/data
266 __find_bigpair(hashp, bufp, ndx, key, size)
273 register u_int16_t *bp;
279 bp = (u_int16_t *)bufp->page;
284 for (bytes = hashp->BSIZE - bp[ndx];
285 bytes <= size && bp[ndx + 1] == PARTIAL_KEY;
286 bytes = hashp->BSIZE - bp[ndx]) {
287 if (memcmp(p + bp[ndx], kkey, bytes))
291 bufp = __get_buf(hashp, bp[ndx + 2], bufp, 0);
299 if (bytes != ksize || memcmp(p + bp[ndx], kkey, bytes)) {
300 #ifdef HASH_STATISTICS
309 * Given the buffer pointer of the first overflow page of a big pair,
310 * find the end of the big pair
312 * This will set bpp to the buffer header of the last page of the big pair.
313 * It will return the pageno of the overflow page following the last page
314 * of the pair; 0 if there isn't any (i.e. big pair is the last key in the
318 __find_last_page(hashp, 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(hashp, bufp, ndx, val, set_current)
367 u_int16_t *bp, len, off, save_addr;
370 bp = (u_int16_t *)bufp->page;
371 while (bp[ndx + 1] == PARTIAL_KEY) {
372 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
375 bp = (u_int16_t *)bufp->page;
379 if (bp[ndx + 1] == FULL_KEY) {
380 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
383 bp = (u_int16_t *)bufp->page;
385 save_addr = save_p->addr;
389 if (!FREESPACE(bp)) {
391 * This is a hack. We can't distinguish between
392 * FULL_KEY_DATA that contains complete data or
393 * incomplete data, so we require that if the data
394 * is complete, there is at least 1 byte of free
400 save_addr = bufp->addr;
401 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
404 bp = (u_int16_t *)bufp->page;
406 /* The data is all on one page. */
409 val->data = (u_char *)tp + off;
410 val->size = bp[1] - off;
412 if (bp[0] == 2) { /* No more buckets in
418 hashp->cpage = __get_buf(hashp,
419 bp[bp[0] - 1], bufp, 0);
424 hashp->cpage->page)[0]) {
433 val->size = collect_data(hashp, bufp, (int)len, set_current);
436 if (save_p->addr != save_addr) {
437 /* We are pretty short on buffers. */
438 errno = EINVAL; /* OUT OF BUFFERS */
441 memmove(hashp->tmp_buf, (save_p->page) + off, len);
442 val->data = (u_char *)hashp->tmp_buf;
446 * Count how big the total datasize is by recursing through the pages. Then
447 * allocate a buffer and copy the data as you recurse up.
450 collect_data(hashp, bufp, len, set)
455 register u_int16_t *bp;
463 mylen = hashp->BSIZE - bp[1];
464 save_addr = bufp->addr;
466 if (bp[2] == FULL_KEY_DATA) { /* End of Data */
467 totlen = len + mylen;
469 free(hashp->tmp_buf);
470 if ((hashp->tmp_buf = (char *)malloc(totlen)) == NULL)
474 if (bp[0] == 2) { /* No more buckets in chain */
479 __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
482 else if (!((u_int16_t *)hashp->cpage->page)[0]) {
489 xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
490 if (!xbp || ((totlen =
491 collect_data(hashp, xbp, len + mylen, set)) < 1))
494 if (bufp->addr != save_addr) {
495 errno = EINVAL; /* Out of buffers. */
498 memmove(&hashp->tmp_buf[len], (bufp->page) + bp[1], mylen);
503 * Fill in the key and data for this big pair.
506 __big_keydata(hashp, bufp, key, val, set)
512 key->size = collect_key(hashp, bufp, 0, val, set);
515 key->data = (u_char *)hashp->tmp_key;
520 * Count how big the total key size is by recursing through the pages. Then
521 * collect the data, allocate a buffer and copy the key as you recurse up.
524 collect_key(hashp, bufp, len, val, set)
534 u_int16_t *bp, save_addr;
538 mylen = hashp->BSIZE - bp[1];
540 save_addr = bufp->addr;
541 totlen = len + mylen;
542 if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) { /* End of Key. */
543 if (hashp->tmp_key != NULL)
544 free(hashp->tmp_key);
545 if ((hashp->tmp_key = (char *)malloc(totlen)) == NULL)
547 if (__big_return(hashp, bufp, 1, val, set))
550 xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
551 if (!xbp || ((totlen =
552 collect_key(hashp, xbp, totlen, val, set)) < 1))
555 if (bufp->addr != save_addr) {
556 errno = EINVAL; /* MIS -- OUT OF BUFFERS */
559 memmove(&hashp->tmp_key[len], (bufp->page) + bp[1], mylen);
569 __big_split(hashp, op, np, big_keyp, addr, obucket, ret)
571 BUFHEAD *op; /* Pointer to where to put keys that go in old bucket */
572 BUFHEAD *np; /* Pointer to new bucket page */
573 /* Pointer to first page containing the big key/data */
575 int addr; /* Address of big_keyp */
576 u_int32_t obucket;/* Old Bucket */
579 register BUFHEAD *tmpp;
580 register u_int16_t *tp;
584 u_int16_t free_space, n, off;
588 /* Now figure out where the big key/data goes */
589 if (__big_keydata(hashp, big_keyp, &key, &val, 0))
591 change = (__call_hash(hashp, key.data, key.size) != obucket);
593 if ( (ret->next_addr = __find_last_page(hashp, &big_keyp)) ) {
595 __get_buf(hashp, ret->next_addr, big_keyp, 0)))
600 /* Now make one of np/op point to the big key/data pair */
602 assert(np->ovfl == NULL);
609 tmpp->flags |= BUF_MOD;
611 (void)fprintf(stderr,
612 "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp->addr,
613 (tmpp->ovfl ? tmpp->ovfl->addr : 0), (bp ? bp->addr : 0));
615 tmpp->ovfl = bp; /* one of op/np point to big_keyp */
616 tp = (u_int16_t *)tmpp->page;
618 assert(FREESPACE(tp) >= OVFLSIZE);
622 free_space = FREESPACE(tp);
623 tp[++n] = (u_int16_t)addr;
627 FREESPACE(tp) = free_space - OVFLSIZE;
630 * Finally, set the new and old return values. BIG_KEYP contains a
631 * pointer to the last page of the big key_data pair. Make sure that
632 * big_keyp has no following page (2 elements) or create an empty
639 tp = (u_int16_t *)big_keyp->page;
640 big_keyp->flags |= BUF_MOD;
643 * There may be either one or two offsets on this page. If
644 * there is one, then the overflow page is linked on normally
645 * and tp[4] is OVFLPAGE. If there are two, tp[4] contains
646 * the second offset and needs to get stuffed in after the
647 * next overflow page is added.
650 free_space = FREESPACE(tp);
653 FREESPACE(tp) = free_space + OVFLSIZE;
655 tmpp = __add_ovflpage(hashp, big_keyp);