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. ***REMOVED*** - see
17 * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change
18 * 4. Neither the name of the University nor the names of its contributors
19 * may be used to endorse or promote products derived from this software
20 * without specific prior written permission.
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 #if defined(LIBC_SCCS) && !defined(lint)
36 static char sccsid
[] = "@(#)hash_bigkey.c 8.3 (Berkeley) 5/31/94";
37 #endif /* LIBC_SCCS and not lint */
42 * Big key/data handling for the hashing package.
57 #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh)
58 #include <sys/param.h>
73 /* #include "extern.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(HTAB
*hashp
, BUFHEAD
*bufp
, const DBT
*key
, const DBT
*val
)
91 uint key_size
, n
, val_size
;
92 uint16 space
, move_bytes
, off
;
93 char *cp
, *key_data
, *val_data
;
95 cp
= bufp
->page
; /* Character pointer of p. */
98 key_data
= (char *)key
->data
;
100 val_data
= (char *)val
->data
;
101 val_size
= val
->size
;
103 /* First move the Key */
104 for (space
= FREESPACE(p
) - BIGOVERHEAD
; key_size
;
105 space
= FREESPACE(p
) - BIGOVERHEAD
) {
106 move_bytes
= PR_MIN(space
, key_size
);
107 off
= OFFSET(p
) - move_bytes
;
108 memmove(cp
+ off
, key_data
, move_bytes
);
109 key_size
-= move_bytes
;
110 key_data
+= move_bytes
;
114 FREESPACE(p
) = off
- PAGE_META(n
);
117 bufp
= __add_ovflpage(hashp
, bufp
);
123 move_bytes
= PR_MIN(FREESPACE(p
), val_size
);
124 off
= OFFSET(p
) - move_bytes
;
126 memmove(cp
+ off
, val_data
, move_bytes
);
127 val_data
+= move_bytes
;
128 val_size
-= move_bytes
;
129 p
[n
- 2] = FULL_KEY_DATA
;
130 FREESPACE(p
) = FREESPACE(p
) - move_bytes
;
135 p
= (uint16
*)bufp
->page
;
137 bufp
->flags
|= BUF_MOD
;
140 /* Now move the data */
141 for (space
= FREESPACE(p
) - BIGOVERHEAD
; val_size
;
142 space
= FREESPACE(p
) - BIGOVERHEAD
) {
143 move_bytes
= PR_MIN(space
, val_size
);
145 * Here's the hack to make sure that if the data ends on the
146 * same page as the key ends, FREESPACE is at least one.
148 if (space
== val_size
&& val_size
== val
->size
)
150 off
= OFFSET(p
) - move_bytes
;
151 memmove(cp
+ off
, val_data
, move_bytes
);
152 val_size
-= move_bytes
;
153 val_data
+= move_bytes
;
157 FREESPACE(p
) = off
- PAGE_META(n
);
161 bufp
= __add_ovflpage(hashp
, bufp
);
167 p
[n
] = FULL_KEY_DATA
;
168 bufp
->flags
|= BUF_MOD
;
174 * Called when bufp's page contains a partial key (index should be 1)
176 * All pages in the big key/data pair except bufp are freed. We cannot
177 * free bufp because the page pointing to it is lost and we can't get rid
185 __big_delete(HTAB
*hashp
, BUFHEAD
*bufp
)
187 register BUFHEAD
*last_bfp
, *rbufp
;
193 bp
= (uint16
*)bufp
->page
;
197 while (!key_done
|| (bp
[2] != FULL_KEY_DATA
)) {
198 if (bp
[2] == FULL_KEY
|| bp
[2] == FULL_KEY_DATA
)
202 * If there is freespace left on a FULL_KEY_DATA page, then
203 * the data is short and fits entirely on this page, and this
206 if (bp
[2] == FULL_KEY_DATA
&& FREESPACE(bp
))
208 pageno
= bp
[bp
[0] - 1];
209 rbufp
->flags
|= BUF_MOD
;
210 rbufp
= __get_buf(hashp
, pageno
, rbufp
, 0);
212 __free_ovflpage(hashp
, last_bfp
);
215 return (-1); /* Error. */
216 bp
= (uint16
*)rbufp
->page
;
220 * If we get here then rbufp points to the last page of the big
221 * key/data pair. Bufp points to the first one -- it should now be
222 * empty pointing to the next page after this pair. Can't free it
223 * because we don't have the page pointing to it.
226 /* This is information from the last page of the pair. */
230 /* Now, bp is the first page of the pair. */
231 bp
= (uint16
*)bufp
->page
;
233 /* There is an overflow page. */
236 bufp
->ovfl
= rbufp
->ovfl
;
238 /* This is the last page. */
242 FREESPACE(bp
) = hashp
->BSIZE
- PAGE_META(n
);
243 OFFSET(bp
) = hashp
->BSIZE
- 1;
245 bufp
->flags
|= BUF_MOD
;
247 __free_ovflpage(hashp
, rbufp
);
248 if (last_bfp
!= rbufp
)
249 __free_ovflpage(hashp
, last_bfp
);
257 * -1 = get next overflow page
258 * -2 means key not found and this is big key/data
262 __find_bigpair(HTAB
*hashp
, BUFHEAD
*bufp
, int ndx
, char *key
, int size
)
270 bp
= (uint16
*)bufp
->page
;
275 for (bytes
= hashp
->BSIZE
- bp
[ndx
];
276 bytes
<= size
&& bp
[ndx
+ 1] == PARTIAL_KEY
;
277 bytes
= hashp
->BSIZE
- bp
[ndx
]) {
278 if (memcmp(p
+ bp
[ndx
], kkey
, bytes
))
282 bufp
= __get_buf(hashp
, bp
[ndx
+ 2], bufp
, 0);
290 if (bytes
!= ksize
|| memcmp(p
+ bp
[ndx
], kkey
, bytes
)) {
291 #ifdef HASH_STATISTICS
300 * Given the buffer pointer of the first overflow page of a big pair,
301 * find the end of the big pair
303 * This will set bpp to the buffer header of the last page of the big pair.
304 * It will return the pageno of the overflow page following the last page
305 * of the pair; 0 if there isn't any (i.e. big pair is the last key in the
309 __find_last_page(HTAB
*hashp
, BUFHEAD
**bpp
)
316 bp
= (uint16
*)bufp
->page
;
321 * This is the last page if: the tag is FULL_KEY_DATA and
322 * either only 2 entries OVFLPAGE marker is explicit there
323 * is freespace on the page.
325 if (bp
[2] == FULL_KEY_DATA
&&
326 ((n
== 2) || (bp
[n
] == OVFLPAGE
) || (FREESPACE(bp
))))
329 /* LJM bound the size of n to reasonable limits
331 if(n
> hashp
->BSIZE
/sizeof(uint16
))
335 bufp
= __get_buf(hashp
, pageno
, bufp
, 0);
337 return (0); /* Need to indicate an error! */
338 bp
= (uint16
*)bufp
->page
;
349 * Return the data for the key/data pair that begins on this page at this
350 * index (index should always be 1).
361 uint16
*bp
, len
, off
, save_addr
;
365 bp
= (uint16
*)bufp
->page
;
366 while (bp
[ndx
+ 1] == PARTIAL_KEY
) {
367 bufp
= __get_buf(hashp
, bp
[bp
[0] - 1], bufp
, 0);
370 bp
= (uint16
*)bufp
->page
;
374 if (bp
[ndx
+ 1] == FULL_KEY
) {
375 bufp
= __get_buf(hashp
, bp
[bp
[0] - 1], bufp
, 0);
378 bp
= (uint16
*)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
= (uint16
*)bufp
->page
;
401 /* The data is all on one page. */
404 val
->data
= (uint8
*)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 /* pin our saved buf so that we don't lose if
429 * we run out of buffers */
430 save_flags
= save_p
->flags
;
431 save_p
->flags
|= BUF_PIN
;
432 val
->size
= collect_data(hashp
, bufp
, (int)len
, set_current
);
433 save_p
->flags
= save_flags
;
434 if (val
->size
== (size_t)-1)
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
= (uint8
*)hashp
->tmp_buf
;
448 * Count how big the total datasize is by looping through the pages. Then
449 * allocate a buffer and copy the data in the second loop. NOTE: Our caller
450 * may already have a bp which it is holding onto. The caller is
451 * responsible for copying that bp into our temp buffer. 'len' is how much
452 * space to reserve for that buffer.
466 * save the input buf head because we need to walk the list twice.
467 * pin it to make sure it doesn't leave the buffer pool.
468 * This has the effect of growing the buffer pool if necessary.
471 save_flags
= save_bufp
->flags
;
472 save_bufp
->flags
|= BUF_PIN
;
474 /* read the length of the buffer */
475 for (totlen
= len
; bufp
; bufp
= __get_buf(hashp
, bp
[bp
[0]-1], bufp
, 0)) {
476 bp
= (uint16
*)bufp
->page
;
477 mylen
= hashp
->BSIZE
- bp
[1];
479 /* if mylen ever goes negative it means that the
480 * page is screwed up.
483 save_bufp
->flags
= save_flags
;
487 if (bp
[2] == FULL_KEY_DATA
) { /* End of Data */
493 save_bufp
->flags
= save_flags
;
497 /* allocate a temp buf */
499 free(hashp
->tmp_buf
);
500 if ((hashp
->tmp_buf
= (char *)malloc((size_t)totlen
)) == NULL
) {
501 save_bufp
->flags
= save_flags
;
505 /* copy the buffers back into temp buf */
506 for (bufp
= save_bufp
; bufp
;
507 bufp
= __get_buf(hashp
, bp
[bp
[0]-1], bufp
, 0)) {
508 bp
= (uint16
*)bufp
->page
;
509 mylen
= hashp
->BSIZE
- bp
[1];
510 memmove(&hashp
->tmp_buf
[len
], (bufp
->page
) + bp
[1], (size_t)mylen
);
512 if (bp
[2] == FULL_KEY_DATA
) {
517 /* 'clear' the pin flags */
518 save_bufp
->flags
= save_flags
;
520 /* update the database cursor */
523 if (bp
[0] == 2) { /* No more buckets in chain */
527 hashp
->cpage
= __get_buf(hashp
, bp
[bp
[0] - 1], bufp
, 0);
530 else if (!((uint16
*)hashp
->cpage
->page
)[0]) {
540 * Fill in the key and data for this big pair.
549 key
->size
= collect_key(hashp
, bufp
, 0, val
, set
);
550 if (key
->size
== (size_t)-1)
552 key
->data
= (uint8
*)hashp
->tmp_key
;
557 * Count how big the total key size is by recursing through the pages. Then
558 * collect the data, allocate a buffer and copy the key as you recurse up.
571 uint16
*bp
, save_addr
;
575 mylen
= hashp
->BSIZE
- bp
[1];
577 save_addr
= bufp
->addr
;
578 totlen
= len
+ mylen
;
579 if (bp
[2] == FULL_KEY
|| bp
[2] == FULL_KEY_DATA
) { /* End of Key. */
580 if (hashp
->tmp_key
!= NULL
)
581 free(hashp
->tmp_key
);
582 if ((hashp
->tmp_key
= (char *)malloc((size_t)totlen
)) == NULL
)
584 if (__big_return(hashp
, bufp
, 1, val
, set
))
587 xbp
= __get_buf(hashp
, bp
[bp
[0] - 1], bufp
, 0);
588 if (!xbp
|| ((totlen
=
589 collect_key(hashp
, xbp
, totlen
, val
, set
)) < 1))
592 if (bufp
->addr
!= save_addr
) {
593 errno
= EINVAL
; /* MIS -- OUT OF BUFFERS */
596 memmove(&hashp
->tmp_key
[len
], (bufp
->page
) + bp
[1], (size_t)mylen
);
608 BUFHEAD
*op
, /* Pointer to where to put keys that go in old bucket */
609 BUFHEAD
*np
, /* Pointer to new bucket page */
610 /* Pointer to first page containing the big key/data */
612 uint32 addr
, /* Address of big_keyp */
613 uint32 obucket
,/* Old Bucket */
616 register BUFHEAD
*tmpp
;
621 uint16 free_space
, n
, off
;
625 /* Now figure out where the big key/data goes */
626 if (__big_keydata(hashp
, big_keyp
, &key
, &val
, 0))
628 change
= (__call_hash(hashp
,(char*) key
.data
, key
.size
) != obucket
);
630 if ((ret
->next_addr
= __find_last_page(hashp
, &big_keyp
))) {
632 __get_buf(hashp
, ret
->next_addr
, big_keyp
, 0)))
637 /* Now make one of np/op point to the big key/data pair */
639 assert(np
->ovfl
== NULL
);
646 tmpp
->flags
|= BUF_MOD
;
648 (void)fprintf(stderr
,
649 "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp
->addr
,
650 (tmpp
->ovfl
? tmpp
->ovfl
->addr
: 0), (bp
? bp
->addr
: 0));
652 tmpp
->ovfl
= bp
; /* one of op/np point to big_keyp */
653 tp
= (uint16
*)tmpp
->page
;
656 #if 0 /* this get's tripped on database corrupted error */
657 assert(FREESPACE(tp
) >= OVFLSIZE
);
659 if(FREESPACE(tp
) < OVFLSIZE
)
660 return(DATABASE_CORRUPTED_ERROR
);
664 free_space
= FREESPACE(tp
);
665 tp
[++n
] = (uint16
)addr
;
669 FREESPACE(tp
) = free_space
- OVFLSIZE
;
672 * Finally, set the new and old return values. BIG_KEYP contains a
673 * pointer to the last page of the big key_data pair. Make sure that
674 * big_keyp has no following page (2 elements) or create an empty
681 tp
= (uint16
*)big_keyp
->page
;
682 big_keyp
->flags
|= BUF_MOD
;
685 * There may be either one or two offsets on this page. If
686 * there is one, then the overflow page is linked on normally
687 * and tp[4] is OVFLPAGE. If there are two, tp[4] contains
688 * the second offset and needs to get stuffed in after the
689 * next overflow page is added.
692 free_space
= FREESPACE(tp
);
695 FREESPACE(tp
) = free_space
+ OVFLSIZE
;
697 tmpp
= __add_ovflpage(hashp
, big_keyp
);