1fb91d121Sbostic /*-
2c0ca25c5Sbostic * Copyright (c) 1990, 1993
3c0ca25c5Sbostic * The Regents of the University of California. All rights reserved.
4fb91d121Sbostic *
5fb91d121Sbostic * This code is derived from software contributed to Berkeley by
6fb91d121Sbostic * Margo Seltzer.
7fb91d121Sbostic *
8fb91d121Sbostic * %sccs.include.redist.c%
9fb91d121Sbostic */
10fb91d121Sbostic
11fb91d121Sbostic #if defined(LIBC_SCCS) && !defined(lint)
12*b601de3bSbostic static char sccsid[] = "@(#)hash_bigkey.c 8.2 (Berkeley) 02/21/94";
13fb91d121Sbostic #endif /* LIBC_SCCS and not lint */
14fb91d121Sbostic
15c62a4a66Sbostic /*
16c62a4a66Sbostic * PACKAGE: hash
17c62a4a66Sbostic * DESCRIPTION:
18c62a4a66Sbostic * Big key/data handling for the hashing package.
19c62a4a66Sbostic *
20c62a4a66Sbostic * ROUTINES:
21c62a4a66Sbostic * External
22c62a4a66Sbostic * __big_keydata
23c62a4a66Sbostic * __big_split
24c62a4a66Sbostic * __big_insert
25c62a4a66Sbostic * __big_return
26c62a4a66Sbostic * __big_delete
27c62a4a66Sbostic * __find_last_page
28c62a4a66Sbostic * Internal
29c62a4a66Sbostic * collect_key
30c62a4a66Sbostic * collect_data
31c62a4a66Sbostic */
32fb91d121Sbostic
3343ccde4eSbostic #include <sys/param.h>
349d0f053fSbostic
359d0f053fSbostic #include <errno.h>
36fb91d121Sbostic #include <stdio.h>
3787570ce5Sbostic #include <stdlib.h>
3887570ce5Sbostic #include <string.h>
399d0f053fSbostic
40c62a4a66Sbostic #ifdef DEBUG
41c62a4a66Sbostic #include <assert.h>
42c62a4a66Sbostic #endif
439d0f053fSbostic
44cbf11d4dSbostic #include <db.h>
45fb91d121Sbostic #include "hash.h"
46fb91d121Sbostic #include "page.h"
47c62a4a66Sbostic #include "extern.h"
48fb91d121Sbostic
499d0f053fSbostic static int collect_key __P((HTAB *, BUFHEAD *, int, DBT *, int));
509d0f053fSbostic static int collect_data __P((HTAB *, BUFHEAD *, int, int));
51fb91d121Sbostic
52fb91d121Sbostic /*
53c62a4a66Sbostic * Big_insert
54c62a4a66Sbostic *
55c62a4a66Sbostic * You need to do an insert and the key/data pair is too big
56c62a4a66Sbostic *
57c62a4a66Sbostic * Returns:
58c62a4a66Sbostic * 0 ==> OK
59c62a4a66Sbostic *-1 ==> ERROR
60fb91d121Sbostic */
61fb91d121Sbostic extern int
629d0f053fSbostic __big_insert(hashp, bufp, key, val)
639d0f053fSbostic HTAB *hashp;
64fb91d121Sbostic BUFHEAD *bufp;
65c62a4a66Sbostic const DBT *key, *val;
66fb91d121Sbostic {
67c62a4a66Sbostic register u_short *p;
68c62a4a66Sbostic int key_size, n, val_size;
69fb91d121Sbostic u_short space, move_bytes, off;
70c62a4a66Sbostic char *cp, *key_data, *val_data;
71c62a4a66Sbostic
72c62a4a66Sbostic cp = bufp->page; /* Character pointer of p. */
73c62a4a66Sbostic p = (u_short *)cp;
74fb91d121Sbostic
750a9054daSbostic key_data = (char *)key->data;
76fb91d121Sbostic key_size = key->size;
770a9054daSbostic val_data = (char *)val->data;
78fb91d121Sbostic val_size = val->size;
79fb91d121Sbostic
80fb91d121Sbostic /* First move the Key */
81c62a4a66Sbostic for (space = FREESPACE(p) - BIGOVERHEAD; key_size;
82fb91d121Sbostic space = FREESPACE(p) - BIGOVERHEAD) {
83fb91d121Sbostic move_bytes = MIN(space, key_size);
84fb91d121Sbostic off = OFFSET(p) - move_bytes;
8589be7141Sbostic memmove(cp + off, key_data, move_bytes);
86fb91d121Sbostic key_size -= move_bytes;
87fb91d121Sbostic key_data += move_bytes;
88fb91d121Sbostic n = p[0];
89fb91d121Sbostic p[++n] = off;
90fb91d121Sbostic p[0] = ++n;
91fb91d121Sbostic FREESPACE(p) = off - PAGE_META(n);
92fb91d121Sbostic OFFSET(p) = off;
93fb91d121Sbostic p[n] = PARTIAL_KEY;
949d0f053fSbostic bufp = __add_ovflpage(hashp, bufp);
95c62a4a66Sbostic if (!bufp)
96fb91d121Sbostic return (-1);
97fb91d121Sbostic n = p[0];
98c62a4a66Sbostic if (!key_size)
99fb91d121Sbostic if (FREESPACE(p)) {
100fb91d121Sbostic move_bytes = MIN(FREESPACE(p), val_size);
101fb91d121Sbostic off = OFFSET(p) - move_bytes;
102fb91d121Sbostic p[n] = off;
10389be7141Sbostic memmove(cp + off, val_data, move_bytes);
104fb91d121Sbostic val_data += move_bytes;
105fb91d121Sbostic val_size -= move_bytes;
106fb91d121Sbostic p[n - 2] = FULL_KEY_DATA;
107fb91d121Sbostic FREESPACE(p) = FREESPACE(p) - move_bytes;
108fb91d121Sbostic OFFSET(p) = off;
109c62a4a66Sbostic } else
110c62a4a66Sbostic p[n - 2] = FULL_KEY;
111fb91d121Sbostic p = (u_short *)bufp->page;
112fb91d121Sbostic cp = bufp->page;
113fb91d121Sbostic bufp->flags |= BUF_MOD;
114fb91d121Sbostic }
115fb91d121Sbostic
116fb91d121Sbostic /* Now move the data */
117c62a4a66Sbostic for (space = FREESPACE(p) - BIGOVERHEAD; val_size;
118fb91d121Sbostic space = FREESPACE(p) - BIGOVERHEAD) {
119fb91d121Sbostic move_bytes = MIN(space, val_size);
120fb91d121Sbostic /*
121c62a4a66Sbostic * Here's the hack to make sure that if the data ends on the
122c62a4a66Sbostic * same page as the key ends, FREESPACE is at least one.
123fb91d121Sbostic */
124c62a4a66Sbostic if (space == val_size && val_size == val->size)
125fb91d121Sbostic move_bytes--;
126fb91d121Sbostic off = OFFSET(p) - move_bytes;
12789be7141Sbostic memmove(cp + off, val_data, move_bytes);
128fb91d121Sbostic val_size -= move_bytes;
129fb91d121Sbostic val_data += move_bytes;
130fb91d121Sbostic n = p[0];
131fb91d121Sbostic p[++n] = off;
132fb91d121Sbostic p[0] = ++n;
133fb91d121Sbostic FREESPACE(p) = off - PAGE_META(n);
134fb91d121Sbostic OFFSET(p) = off;
135fb91d121Sbostic if (val_size) {
136fb91d121Sbostic p[n] = FULL_KEY;
1379d0f053fSbostic bufp = __add_ovflpage(hashp, bufp);
138c62a4a66Sbostic if (!bufp)
139fb91d121Sbostic return (-1);
140fb91d121Sbostic cp = bufp->page;
141fb91d121Sbostic p = (u_short *)cp;
142c62a4a66Sbostic } else
143fb91d121Sbostic p[n] = FULL_KEY_DATA;
144fb91d121Sbostic bufp->flags |= BUF_MOD;
145fb91d121Sbostic }
146fb91d121Sbostic return (0);
147fb91d121Sbostic }
148fb91d121Sbostic
149fb91d121Sbostic /*
150c62a4a66Sbostic * Called when bufp's page contains a partial key (index should be 1)
151c62a4a66Sbostic *
152c62a4a66Sbostic * All pages in the big key/data pair except bufp are freed. We cannot
153c62a4a66Sbostic * free bufp because the page pointing to it is lost and we can't get rid
154c62a4a66Sbostic * of its pointer.
155c62a4a66Sbostic *
156c62a4a66Sbostic * Returns:
157c62a4a66Sbostic * 0 => OK
158c62a4a66Sbostic *-1 => ERROR
159fb91d121Sbostic */
160fb91d121Sbostic extern int
1619d0f053fSbostic __big_delete(hashp, bufp)
1629d0f053fSbostic HTAB *hashp;
163fb91d121Sbostic BUFHEAD *bufp;
164fb91d121Sbostic {
165c62a4a66Sbostic register BUFHEAD *last_bfp, *rbufp;
166c62a4a66Sbostic u_short *bp, pageno;
167c62a4a66Sbostic int key_done, n;
168c62a4a66Sbostic
169c62a4a66Sbostic rbufp = bufp;
170c62a4a66Sbostic last_bfp = NULL;
171c62a4a66Sbostic bp = (u_short *)bufp->page;
172c62a4a66Sbostic pageno = 0;
173c62a4a66Sbostic key_done = 0;
174fb91d121Sbostic
175fb91d121Sbostic while (!key_done || (bp[2] != FULL_KEY_DATA)) {
176c62a4a66Sbostic if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA)
177c62a4a66Sbostic key_done = 1;
178fb91d121Sbostic
179fb91d121Sbostic /*
180c62a4a66Sbostic * If there is freespace left on a FULL_KEY_DATA page, then
181c62a4a66Sbostic * the data is short and fits entirely on this page, and this
182c62a4a66Sbostic * is the last page.
183fb91d121Sbostic */
184c62a4a66Sbostic if (bp[2] == FULL_KEY_DATA && FREESPACE(bp))
185c62a4a66Sbostic break;
186fb91d121Sbostic pageno = bp[bp[0] - 1];
187fb91d121Sbostic rbufp->flags |= BUF_MOD;
1889d0f053fSbostic rbufp = __get_buf(hashp, pageno, rbufp, 0);
189c62a4a66Sbostic if (last_bfp)
1909d0f053fSbostic __free_ovflpage(hashp, last_bfp);
191fb91d121Sbostic last_bfp = rbufp;
192c62a4a66Sbostic if (!rbufp)
193c62a4a66Sbostic return (-1); /* Error. */
194fb91d121Sbostic bp = (u_short *)rbufp->page;
195fb91d121Sbostic }
196fb91d121Sbostic
197fb91d121Sbostic /*
198c62a4a66Sbostic * If we get here then rbufp points to the last page of the big
199c62a4a66Sbostic * key/data pair. Bufp points to the first one -- it should now be
200c62a4a66Sbostic * empty pointing to the next page after this pair. Can't free it
201c62a4a66Sbostic * because we don't have the page pointing to it.
202fb91d121Sbostic */
203fb91d121Sbostic
204c62a4a66Sbostic /* This is information from the last page of the pair. */
205fb91d121Sbostic n = bp[0];
206fb91d121Sbostic pageno = bp[n - 1];
207fb91d121Sbostic
208c62a4a66Sbostic /* Now, bp is the first page of the pair. */
209fb91d121Sbostic bp = (u_short *)bufp->page;
210fb91d121Sbostic if (n > 2) {
211c62a4a66Sbostic /* There is an overflow page. */
212fb91d121Sbostic bp[1] = pageno;
213fb91d121Sbostic bp[2] = OVFLPAGE;
214fb91d121Sbostic bufp->ovfl = rbufp->ovfl;
215c62a4a66Sbostic } else
216c62a4a66Sbostic /* This is the last page. */
217fb91d121Sbostic bufp->ovfl = NULL;
218fb91d121Sbostic n -= 2;
219fb91d121Sbostic bp[0] = n;
220fb91d121Sbostic FREESPACE(bp) = hashp->BSIZE - PAGE_META(n);
221fb91d121Sbostic OFFSET(bp) = hashp->BSIZE - 1;
222fb91d121Sbostic
223fb91d121Sbostic bufp->flags |= BUF_MOD;
224c62a4a66Sbostic if (rbufp)
2259d0f053fSbostic __free_ovflpage(hashp, rbufp);
226c62a4a66Sbostic if (last_bfp != rbufp)
2279d0f053fSbostic __free_ovflpage(hashp, last_bfp);
228fb91d121Sbostic
229fb91d121Sbostic hashp->NKEYS--;
230fb91d121Sbostic return (0);
231fb91d121Sbostic }
232fb91d121Sbostic /*
233c62a4a66Sbostic * Returns:
234c62a4a66Sbostic * 0 = key not found
235c62a4a66Sbostic * -1 = get next overflow page
236c62a4a66Sbostic * -2 means key not found and this is big key/data
237c62a4a66Sbostic * -3 error
238fb91d121Sbostic */
239fb91d121Sbostic extern int
2409d0f053fSbostic __find_bigpair(hashp, bufp, ndx, key, size)
2419d0f053fSbostic HTAB *hashp;
242fb91d121Sbostic BUFHEAD *bufp;
243fb91d121Sbostic int ndx;
244fb91d121Sbostic char *key;
245fb91d121Sbostic int size;
246fb91d121Sbostic {
247c62a4a66Sbostic register u_short *bp;
248c62a4a66Sbostic register char *p;
249c62a4a66Sbostic int ksize;
250fb91d121Sbostic u_short bytes;
251c62a4a66Sbostic char *kkey;
252fb91d121Sbostic
253c62a4a66Sbostic bp = (u_short *)bufp->page;
254c62a4a66Sbostic p = bufp->page;
255c62a4a66Sbostic ksize = size;
256c62a4a66Sbostic kkey = key;
257fb91d121Sbostic
258fb91d121Sbostic for (bytes = hashp->BSIZE - bp[ndx];
259fb91d121Sbostic bytes <= size && bp[ndx + 1] == PARTIAL_KEY;
260fb91d121Sbostic bytes = hashp->BSIZE - bp[ndx]) {
26189be7141Sbostic if (memcmp(p + bp[ndx], kkey, bytes))
262c62a4a66Sbostic return (-2);
263fb91d121Sbostic kkey += bytes;
264fb91d121Sbostic ksize -= bytes;
2659d0f053fSbostic bufp = __get_buf(hashp, bp[ndx + 2], bufp, 0);
266c62a4a66Sbostic if (!bufp)
267fb91d121Sbostic return (-3);
268fb91d121Sbostic p = bufp->page;
269fb91d121Sbostic bp = (u_short *)p;
270fb91d121Sbostic ndx = 1;
271fb91d121Sbostic }
272fb91d121Sbostic
27389be7141Sbostic if (bytes != ksize || memcmp(p + bp[ndx], kkey, bytes)) {
274fb91d121Sbostic #ifdef HASH_STATISTICS
275c62a4a66Sbostic ++hash_collisions;
276fb91d121Sbostic #endif
277fb91d121Sbostic return (-2);
278c62a4a66Sbostic } else
279c62a4a66Sbostic return (ndx);
280fb91d121Sbostic }
281fb91d121Sbostic
282fb91d121Sbostic /*
283c62a4a66Sbostic * Given the buffer pointer of the first overflow page of a big pair,
284c62a4a66Sbostic * find the end of the big pair
285c62a4a66Sbostic *
286c62a4a66Sbostic * This will set bpp to the buffer header of the last page of the big pair.
287c62a4a66Sbostic * It will return the pageno of the overflow page following the last page
288c62a4a66Sbostic * of the pair; 0 if there isn't any (i.e. big pair is the last key in the
289c62a4a66Sbostic * bucket)
290fb91d121Sbostic */
291fb91d121Sbostic extern u_short
2929d0f053fSbostic __find_last_page(hashp, bpp)
2939d0f053fSbostic HTAB *hashp;
294fb91d121Sbostic BUFHEAD **bpp;
295fb91d121Sbostic {
296c62a4a66Sbostic BUFHEAD *bufp;
297c62a4a66Sbostic u_short *bp, pageno;
298fb91d121Sbostic int n;
299fb91d121Sbostic
300c62a4a66Sbostic bufp = *bpp;
301c62a4a66Sbostic bp = (u_short *)bufp->page;
302c62a4a66Sbostic for (;;) {
303fb91d121Sbostic n = bp[0];
304fb91d121Sbostic
305fb91d121Sbostic /*
306c62a4a66Sbostic * This is the last page if: the tag is FULL_KEY_DATA and
307c62a4a66Sbostic * either only 2 entries OVFLPAGE marker is explicit there
308c62a4a66Sbostic * is freespace on the page.
309fb91d121Sbostic */
310fb91d121Sbostic if (bp[2] == FULL_KEY_DATA &&
311c62a4a66Sbostic ((n == 2) || (bp[n] == OVFLPAGE) || (FREESPACE(bp))))
312c62a4a66Sbostic break;
313fb91d121Sbostic
314fb91d121Sbostic pageno = bp[n - 1];
3159d0f053fSbostic bufp = __get_buf(hashp, pageno, bufp, 0);
316c62a4a66Sbostic if (!bufp)
317c62a4a66Sbostic return (0); /* Need to indicate an error! */
318fb91d121Sbostic bp = (u_short *)bufp->page;
319fb91d121Sbostic }
320fb91d121Sbostic
321fb91d121Sbostic *bpp = bufp;
322c62a4a66Sbostic if (bp[0] > 2)
323c62a4a66Sbostic return (bp[3]);
324c62a4a66Sbostic else
325c62a4a66Sbostic return (0);
326fb91d121Sbostic }
327fb91d121Sbostic
328fb91d121Sbostic /*
329c62a4a66Sbostic * Return the data for the key/data pair that begins on this page at this
330c62a4a66Sbostic * index (index should always be 1).
331fb91d121Sbostic */
332fb91d121Sbostic extern int
3339d0f053fSbostic __big_return(hashp, bufp, ndx, val, set_current)
3349d0f053fSbostic HTAB *hashp;
335fb91d121Sbostic BUFHEAD *bufp;
336fb91d121Sbostic int ndx;
337fb91d121Sbostic DBT *val;
338fb91d121Sbostic int set_current;
339fb91d121Sbostic {
340fb91d121Sbostic BUFHEAD *save_p;
341c62a4a66Sbostic u_short *bp, len, off, save_addr;
342c62a4a66Sbostic char *tp;
343fb91d121Sbostic
344c62a4a66Sbostic bp = (u_short *)bufp->page;
345fb91d121Sbostic while (bp[ndx + 1] == PARTIAL_KEY) {
3469d0f053fSbostic bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
347c62a4a66Sbostic if (!bufp)
348c62a4a66Sbostic return (-1);
349fb91d121Sbostic bp = (u_short *)bufp->page;
350fb91d121Sbostic ndx = 1;
351fb91d121Sbostic }
352fb91d121Sbostic
353fb91d121Sbostic if (bp[ndx + 1] == FULL_KEY) {
3549d0f053fSbostic bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
355c62a4a66Sbostic if (!bufp)
356c62a4a66Sbostic return (-1);
357fb91d121Sbostic bp = (u_short *)bufp->page;
358fb91d121Sbostic save_p = bufp;
359fb91d121Sbostic save_addr = save_p->addr;
360fb91d121Sbostic off = bp[1];
361fb91d121Sbostic len = 0;
362c62a4a66Sbostic } else
363c62a4a66Sbostic if (!FREESPACE(bp)) {
364fb91d121Sbostic /*
365c62a4a66Sbostic * This is a hack. We can't distinguish between
366c62a4a66Sbostic * FULL_KEY_DATA that contains complete data or
367c62a4a66Sbostic * incomplete data, so we require that if the data
368c62a4a66Sbostic * is complete, there is at least 1 byte of free
369c62a4a66Sbostic * space left.
370fb91d121Sbostic */
371fb91d121Sbostic off = bp[bp[0]];
372fb91d121Sbostic len = bp[1] - off;
373fb91d121Sbostic save_p = bufp;
374fb91d121Sbostic save_addr = bufp->addr;
3759d0f053fSbostic bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
376c62a4a66Sbostic if (!bufp)
377c62a4a66Sbostic return (-1);
378fb91d121Sbostic bp = (u_short *)bufp->page;
379fb91d121Sbostic } else {
380c62a4a66Sbostic /* The data is all on one page. */
381fb91d121Sbostic tp = (char *)bp;
382fb91d121Sbostic off = bp[bp[0]];
3830a9054daSbostic val->data = (u_char *)tp + off;
384fb91d121Sbostic val->size = bp[1] - off;
385fb91d121Sbostic if (set_current) {
386c62a4a66Sbostic if (bp[0] == 2) { /* No more buckets in
387c62a4a66Sbostic * chain */
388fb91d121Sbostic hashp->cpage = NULL;
389fb91d121Sbostic hashp->cbucket++;
390fb91d121Sbostic hashp->cndx = 1;
391fb91d121Sbostic } else {
3929d0f053fSbostic hashp->cpage = __get_buf(hashp,
3939d0f053fSbostic bp[bp[0] - 1], bufp, 0);
394c62a4a66Sbostic if (!hashp->cpage)
395c62a4a66Sbostic return (-1);
396fb91d121Sbostic hashp->cndx = 1;
397c62a4a66Sbostic if (!((u_short *)
398c62a4a66Sbostic hashp->cpage->page)[0]) {
399fb91d121Sbostic hashp->cbucket++;
400fb91d121Sbostic hashp->cpage = NULL;
401fb91d121Sbostic }
402fb91d121Sbostic }
403fb91d121Sbostic }
404fb91d121Sbostic return (0);
405fb91d121Sbostic }
406fb91d121Sbostic
4079d0f053fSbostic val->size = collect_data(hashp, bufp, (int)len, set_current);
408c62a4a66Sbostic if (val->size == -1)
409fb91d121Sbostic return (-1);
410fb91d121Sbostic if (save_p->addr != save_addr) {
411c62a4a66Sbostic /* We are pretty short on buffers. */
412fb91d121Sbostic errno = EINVAL; /* OUT OF BUFFERS */
413fb91d121Sbostic return (-1);
414fb91d121Sbostic }
41589be7141Sbostic memmove(hashp->tmp_buf, (save_p->page) + off, len);
4160a9054daSbostic val->data = (u_char *)hashp->tmp_buf;
417fb91d121Sbostic return (0);
418fb91d121Sbostic }
419fb91d121Sbostic /*
420c62a4a66Sbostic * Count how big the total datasize is by recursing through the pages. Then
421c62a4a66Sbostic * allocate a buffer and copy the data as you recurse up.
422fb91d121Sbostic */
423fb91d121Sbostic static int
collect_data(hashp,bufp,len,set)4249d0f053fSbostic collect_data(hashp, bufp, len, set)
4259d0f053fSbostic HTAB *hashp;
426fb91d121Sbostic BUFHEAD *bufp;
427c62a4a66Sbostic int len, set;
428fb91d121Sbostic {
429c62a4a66Sbostic register u_short *bp;
430c62a4a66Sbostic register char *p;
431c62a4a66Sbostic BUFHEAD *xbp;
432fb91d121Sbostic u_short save_addr;
433fb91d121Sbostic int mylen, totlen;
434fb91d121Sbostic
435c62a4a66Sbostic p = bufp->page;
436c62a4a66Sbostic bp = (u_short *)p;
437fb91d121Sbostic mylen = hashp->BSIZE - bp[1];
438fb91d121Sbostic save_addr = bufp->addr;
439fb91d121Sbostic
440fb91d121Sbostic if (bp[2] == FULL_KEY_DATA) { /* End of Data */
441fb91d121Sbostic totlen = len + mylen;
442c62a4a66Sbostic if (hashp->tmp_buf)
443c62a4a66Sbostic free(hashp->tmp_buf);
444*b601de3bSbostic if ((hashp->tmp_buf = (char *)malloc(totlen)) == NULL)
445fb91d121Sbostic return (-1);
446fb91d121Sbostic if (set) {
447fb91d121Sbostic hashp->cndx = 1;
448fb91d121Sbostic if (bp[0] == 2) { /* No more buckets in chain */
449fb91d121Sbostic hashp->cpage = NULL;
450fb91d121Sbostic hashp->cbucket++;
451fb91d121Sbostic } else {
452c62a4a66Sbostic hashp->cpage =
4539d0f053fSbostic __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
454c62a4a66Sbostic if (!hashp->cpage)
455fb91d121Sbostic return (-1);
456c62a4a66Sbostic else if (!((u_short *)hashp->cpage->page)[0]) {
457fb91d121Sbostic hashp->cbucket++;
458fb91d121Sbostic hashp->cpage = NULL;
459fb91d121Sbostic }
460fb91d121Sbostic }
461fb91d121Sbostic }
462fb91d121Sbostic } else {
4639d0f053fSbostic xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
4649d0f053fSbostic if (!xbp || ((totlen =
4659d0f053fSbostic collect_data(hashp, xbp, len + mylen, set)) < 1))
466fb91d121Sbostic return (-1);
467fb91d121Sbostic }
468fb91d121Sbostic if (bufp->addr != save_addr) {
469c62a4a66Sbostic errno = EINVAL; /* Out of buffers. */
470fb91d121Sbostic return (-1);
471fb91d121Sbostic }
47289be7141Sbostic memmove(&hashp->tmp_buf[len], (bufp->page) + bp[1], mylen);
473fb91d121Sbostic return (totlen);
474fb91d121Sbostic }
475fb91d121Sbostic
476fb91d121Sbostic /*
477c62a4a66Sbostic * Fill in the key and data for this big pair.
478fb91d121Sbostic */
479fb91d121Sbostic extern int
4809d0f053fSbostic __big_keydata(hashp, bufp, key, val, set)
4819d0f053fSbostic HTAB *hashp;
482fb91d121Sbostic BUFHEAD *bufp;
483fb91d121Sbostic DBT *key, *val;
484fb91d121Sbostic int set;
485fb91d121Sbostic {
4869d0f053fSbostic key->size = collect_key(hashp, bufp, 0, val, set);
487c62a4a66Sbostic if (key->size == -1)
488fb91d121Sbostic return (-1);
4890a9054daSbostic key->data = (u_char *)hashp->tmp_key;
490fb91d121Sbostic return (0);
491fb91d121Sbostic }
492fb91d121Sbostic
493fb91d121Sbostic /*
494c62a4a66Sbostic * Count how big the total key size is by recursing through the pages. Then
495c62a4a66Sbostic * collect the data, allocate a buffer and copy the key as you recurse up.
496fb91d121Sbostic */
497fb91d121Sbostic static int
collect_key(hashp,bufp,len,val,set)4989d0f053fSbostic collect_key(hashp, bufp, len, val, set)
4999d0f053fSbostic HTAB *hashp;
500fb91d121Sbostic BUFHEAD *bufp;
501fb91d121Sbostic int len;
502fb91d121Sbostic DBT *val;
503fb91d121Sbostic int set;
504fb91d121Sbostic {
505fb91d121Sbostic BUFHEAD *xbp;
506c62a4a66Sbostic char *p;
507c62a4a66Sbostic int mylen, totlen;
508c62a4a66Sbostic u_short *bp, save_addr;
509fb91d121Sbostic
510c62a4a66Sbostic p = bufp->page;
511c62a4a66Sbostic bp = (u_short *)p;
512fb91d121Sbostic mylen = hashp->BSIZE - bp[1];
513fb91d121Sbostic
514fb91d121Sbostic save_addr = bufp->addr;
515fb91d121Sbostic totlen = len + mylen;
516c62a4a66Sbostic if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) { /* End of Key. */
517*b601de3bSbostic if (hashp->tmp_key != NULL)
518c62a4a66Sbostic free(hashp->tmp_key);
519*b601de3bSbostic if ((hashp->tmp_key = (char *)malloc(totlen)) == NULL)
520fb91d121Sbostic return (-1);
5219d0f053fSbostic if (__big_return(hashp, bufp, 1, val, set))
522b0a3b35bSbostic return (-1);
523fb91d121Sbostic } else {
5249d0f053fSbostic xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
5259d0f053fSbostic if (!xbp || ((totlen =
5269d0f053fSbostic collect_key(hashp, xbp, totlen, val, set)) < 1))
527fb91d121Sbostic return (-1);
528fb91d121Sbostic }
529fb91d121Sbostic if (bufp->addr != save_addr) {
530fb91d121Sbostic errno = EINVAL; /* MIS -- OUT OF BUFFERS */
531fb91d121Sbostic return (-1);
532fb91d121Sbostic }
53389be7141Sbostic memmove(&hashp->tmp_key[len], (bufp->page) + bp[1], mylen);
534fb91d121Sbostic return (totlen);
535fb91d121Sbostic }
536fb91d121Sbostic
537fb91d121Sbostic /*
538c62a4a66Sbostic * Returns:
539c62a4a66Sbostic * 0 => OK
540c62a4a66Sbostic * -1 => error
541fb91d121Sbostic */
542fb91d121Sbostic extern int
5439d0f053fSbostic __big_split(hashp, op, np, big_keyp, addr, obucket, ret)
5449d0f053fSbostic HTAB *hashp;
545fb91d121Sbostic BUFHEAD *op; /* Pointer to where to put keys that go in old bucket */
546fb91d121Sbostic BUFHEAD *np; /* Pointer to new bucket page */
547c62a4a66Sbostic /* Pointer to first page containing the big key/data */
548c62a4a66Sbostic BUFHEAD *big_keyp;
549c62a4a66Sbostic int addr; /* Address of big_keyp */
550cb6cacddSbostic u_int obucket;/* Old Bucket */
551fb91d121Sbostic SPLIT_RETURN *ret;
552fb91d121Sbostic {
553fb91d121Sbostic register BUFHEAD *tmpp;
554fb91d121Sbostic register u_short *tp;
555c62a4a66Sbostic BUFHEAD *bp;
556fb91d121Sbostic DBT key, val;
557cb6cacddSbostic u_int change;
558c62a4a66Sbostic u_short free_space, n, off;
559c62a4a66Sbostic
560c62a4a66Sbostic bp = big_keyp;
561fb91d121Sbostic
562fb91d121Sbostic /* Now figure out where the big key/data goes */
5639d0f053fSbostic if (__big_keydata(hashp, big_keyp, &key, &val, 0))
564fb91d121Sbostic return (-1);
5659d0f053fSbostic change = (__call_hash(hashp, key.data, key.size) != obucket);
566fb91d121Sbostic
5679d0f053fSbostic if (ret->next_addr = __find_last_page(hashp, &big_keyp)) {
5689d0f053fSbostic if (!(ret->nextp =
5699d0f053fSbostic __get_buf(hashp, ret->next_addr, big_keyp, 0)))
570fb91d121Sbostic return (-1);;
571c62a4a66Sbostic } else
572fb91d121Sbostic ret->nextp = NULL;
573fb91d121Sbostic
574fb91d121Sbostic /* Now make one of np/op point to the big key/data pair */
575c62a4a66Sbostic #ifdef DEBUG
576fb91d121Sbostic assert(np->ovfl == NULL);
577c62a4a66Sbostic #endif
578c62a4a66Sbostic if (change)
579c62a4a66Sbostic tmpp = np;
580c62a4a66Sbostic else
581c62a4a66Sbostic tmpp = op;
582fb91d121Sbostic
583fb91d121Sbostic tmpp->flags |= BUF_MOD;
584fb91d121Sbostic #ifdef DEBUG1
585c62a4a66Sbostic (void)fprintf(stderr,
586c62a4a66Sbostic "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp->addr,
587c62a4a66Sbostic (tmpp->ovfl ? tmpp->ovfl->addr : 0), (bp ? bp->addr : 0));
588fb91d121Sbostic #endif
589fb91d121Sbostic tmpp->ovfl = bp; /* one of op/np point to big_keyp */
590fb91d121Sbostic tp = (u_short *)tmpp->page;
591c62a4a66Sbostic #ifdef DEBUG
592fb91d121Sbostic assert(FREESPACE(tp) >= OVFLSIZE);
593c62a4a66Sbostic #endif
594fb91d121Sbostic n = tp[0];
595fb91d121Sbostic off = OFFSET(tp);
596fb91d121Sbostic free_space = FREESPACE(tp);
597c62a4a66Sbostic tp[++n] = (u_short)addr;
598fb91d121Sbostic tp[++n] = OVFLPAGE;
599fb91d121Sbostic tp[0] = n;
600fb91d121Sbostic OFFSET(tp) = off;
601fb91d121Sbostic FREESPACE(tp) = free_space - OVFLSIZE;
602fb91d121Sbostic
603fb91d121Sbostic /*
604c62a4a66Sbostic * Finally, set the new and old return values. BIG_KEYP contains a
605c62a4a66Sbostic * pointer to the last page of the big key_data pair. Make sure that
606c62a4a66Sbostic * big_keyp has no following page (2 elements) or create an empty
607c62a4a66Sbostic * following page.
608fb91d121Sbostic */
609fb91d121Sbostic
610fb91d121Sbostic ret->newp = np;
611fb91d121Sbostic ret->oldp = op;
612fb91d121Sbostic
613fb91d121Sbostic tp = (u_short *)big_keyp->page;
614fb91d121Sbostic big_keyp->flags |= BUF_MOD;
615fb91d121Sbostic if (tp[0] > 2) {
616fb91d121Sbostic /*
617c62a4a66Sbostic * There may be either one or two offsets on this page. If
618c62a4a66Sbostic * there is one, then the overflow page is linked on normally
619c62a4a66Sbostic * and tp[4] is OVFLPAGE. If there are two, tp[4] contains
620c62a4a66Sbostic * the second offset and needs to get stuffed in after the
621c62a4a66Sbostic * next overflow page is added.
622fb91d121Sbostic */
623fb91d121Sbostic n = tp[4];
624fb91d121Sbostic free_space = FREESPACE(tp);
625fb91d121Sbostic off = OFFSET(tp);
626fb91d121Sbostic tp[0] -= 2;
627fb91d121Sbostic FREESPACE(tp) = free_space + OVFLSIZE;
628fb91d121Sbostic OFFSET(tp) = off;
6299d0f053fSbostic tmpp = __add_ovflpage(hashp, big_keyp);
630c62a4a66Sbostic if (!tmpp)
631fb91d121Sbostic return (-1);
632fb91d121Sbostic tp[4] = n;
633c62a4a66Sbostic } else
634fb91d121Sbostic tmpp = big_keyp;
635fb91d121Sbostic
636c62a4a66Sbostic if (change)
637c62a4a66Sbostic ret->newp = tmpp;
638c62a4a66Sbostic else
639c62a4a66Sbostic ret->oldp = tmpp;
640fb91d121Sbostic return (0);
641fb91d121Sbostic }
642