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