1 #pragma ident "%Z%%M% %I% %E% SMI"
2
3 /*-
4 * Copyright (c) 1990, 1993, 1994
5 * The Regents of the University of California. All rights reserved.
6 *
7 * This code is derived from software contributed to Berkeley by
8 * Margo Seltzer.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 * 3. All advertising materials mentioning features or use of this software
19 * must display the following acknowledgement:
20 * This product includes software developed by the University of
21 * California, Berkeley and its contributors.
22 * 4. Neither the name of the University nor the names of its contributors
23 * may be used to endorse or promote products derived from this software
24 * without specific prior written permission.
25 *
26 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36 * SUCH DAMAGE.
37 */
38
39 #if defined(LIBC_SCCS) && !defined(lint)
40 static char sccsid[] = "@(#)hash_bigkey.c 8.5 (Berkeley) 11/2/95";
41 #endif /* LIBC_SCCS and not lint */
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 #include <sys/types.h>
61
62 #include <stdlib.h>
63 #include <string.h>
64
65 #ifdef DEBUG
66 #include <assert.h>
67 #endif
68
69 #include "db-int.h"
70 #include "hash.h"
71 #include "page.h"
72 #include "extern.h"
73
74 static int32_t collect_key __P((HTAB *, PAGE16 *, int32_t, db_pgno_t *));
75 static int32_t collect_data __P((HTAB *, PAGE16 *, int32_t));
76
77 /*
78 * Big_insert
79 *
80 * You need to do an insert and the key/data pair is greater than
81 * MINFILL * the bucket size
82 *
83 * Returns:
84 * 0 ==> OK
85 * -1 ==> ERROR
86 */
87 int32_t
__big_insert(hashp,pagep,key,val)88 __big_insert(hashp, pagep, key, val)
89 HTAB *hashp;
90 PAGE16 *pagep;
91 const DBT *key, *val;
92 {
93 size_t key_size, val_size;
94 indx_t key_move_bytes, val_move_bytes;
95 int8_t *key_data, *val_data, base_page;
96
97 key_data = (int8_t *)key->data;
98 key_size = key->size;
99 val_data = (int8_t *)val->data;
100 val_size = val->size;
101
102 NUM_ENT(pagep) = NUM_ENT(pagep) + 1;
103
104 for (base_page = 1; key_size + val_size;) {
105 /* Add a page! */
106 pagep =
107 __add_bigpage(hashp, pagep, NUM_ENT(pagep) - 1, base_page);
108 if (!pagep)
109 return (-1);
110
111 /* There's just going to be one entry on this page. */
112 NUM_ENT(pagep) = 1;
113
114 /* Move the key's data. */
115 key_move_bytes = MIN(FREESPACE(pagep), key_size);
116 /* Mark the page as to how much key & data is on this page. */
117 BIGKEYLEN(pagep) = key_move_bytes;
118 val_move_bytes =
119 MIN(FREESPACE(pagep) - key_move_bytes, val_size);
120 BIGDATALEN(pagep) = val_move_bytes;
121
122 /* Note big pages build beginning --> end, not vice versa. */
123 if (key_move_bytes)
124 memmove(BIGKEY(pagep), key_data, key_move_bytes);
125 if (val_move_bytes)
126 memmove(BIGDATA(pagep), val_data, val_move_bytes);
127
128 key_size -= key_move_bytes;
129 key_data += key_move_bytes;
130 val_size -= val_move_bytes;
131 val_data += val_move_bytes;
132
133 base_page = 0;
134 }
135 __put_page(hashp, pagep, A_RAW, 1);
136 return (0);
137 }
138
139 /*
140 * Called when we need to delete a big pair.
141 *
142 * Returns:
143 * 0 => OK
144 * -1 => ERROR
145 */
146 int32_t
147 #ifdef __STDC__
__big_delete(HTAB * hashp,PAGE16 * pagep,indx_t ndx)148 __big_delete(HTAB *hashp, PAGE16 *pagep, indx_t ndx)
149 #else
150 __big_delete(hashp, pagep, ndx)
151 HTAB *hashp;
152 PAGE16 *pagep;
153 u_int32_t ndx; /* Index of big pair on base page. */
154 #endif
155 {
156 PAGE16 *last_pagep;
157
158 /* Get first page with big key/data. */
159 pagep = __get_page(hashp, OADDR_TO_PAGE(DATA_OFF(pagep, ndx)), A_RAW);
160 if (!pagep)
161 return (-1);
162
163 /*
164 * Traverse through the pages, freeing the previous one (except
165 * the first) at each new page.
166 */
167 while (NEXT_PGNO(pagep) != INVALID_PGNO) {
168 last_pagep = pagep;
169 pagep = __get_page(hashp, NEXT_PGNO(pagep), A_RAW);
170 if (!pagep)
171 return (-1);
172 __delete_page(hashp, last_pagep, A_OVFL);
173 }
174
175 /* Free the last page in the chain. */
176 __delete_page(hashp, pagep, A_OVFL);
177 return (0);
178 }
179
180 /*
181 * Given a key, indicates whether the big key at cursorp matches the
182 * given key.
183 *
184 * Returns:
185 * 1 = Found!
186 * 0 = Key not found
187 * -1 error
188 */
189 int32_t
__find_bigpair(hashp,cursorp,key,size)190 __find_bigpair(hashp, cursorp, key, size)
191 HTAB *hashp;
192 CURSOR *cursorp;
193 int8_t *key;
194 int32_t size;
195 {
196 PAGE16 *pagep, *hold_pagep;
197 db_pgno_t next_pgno;
198 int32_t ksize;
199 u_int16_t bytes;
200 int8_t *kkey;
201
202 ksize = size;
203 kkey = key;
204 bytes = 0;
205
206 hold_pagep = NULL;
207 /* Chances are, hashp->cpage is the base page. */
208 if (cursorp->pagep)
209 pagep = hold_pagep = cursorp->pagep;
210 else {
211 pagep = __get_page(hashp, cursorp->pgno, A_RAW);
212 if (!pagep)
213 return (-1);
214 }
215
216 /*
217 * Now, get the first page with the big stuff on it.
218 *
219 * XXX
220 * KLUDGE: we know that cursor is looking at the _next_ item, so
221 * we have to look at pgndx - 1.
222 */
223 next_pgno = OADDR_TO_PAGE(DATA_OFF(pagep, (cursorp->pgndx - 1)));
224 if (!hold_pagep)
225 __put_page(hashp, pagep, A_RAW, 0);
226 pagep = __get_page(hashp, next_pgno, A_RAW);
227 if (!pagep)
228 return (-1);
229
230 /* While there are both keys to compare. */
231 while ((ksize > 0) && (BIGKEYLEN(pagep))) {
232 if (ksize < KEY_OFF(pagep, 0) ||
233 memcmp(BIGKEY(pagep), kkey, BIGKEYLEN(pagep))) {
234 __put_page(hashp, pagep, A_RAW, 0);
235 return (0);
236 }
237 kkey += BIGKEYLEN(pagep);
238 ksize -= BIGKEYLEN(pagep);
239 if (NEXT_PGNO(pagep) != INVALID_PGNO) {
240 next_pgno = NEXT_PGNO(pagep);
241 __put_page(hashp, pagep, A_RAW, 0);
242 pagep = __get_page(hashp, next_pgno, A_RAW);
243 if (!pagep)
244 return (-1);
245 }
246 }
247 __put_page(hashp, pagep, A_RAW, 0);
248 #ifdef DEBUG
249 assert(ksize >= 0);
250 #endif
251 if (ksize != 0) {
252 #ifdef HASH_STATISTICS
253 ++hash_collisions;
254 #endif
255 return (0);
256 } else
257 return (1);
258 }
259
260 /*
261 * Fill in the key and data for this big pair.
262 */
263 int32_t
__big_keydata(hashp,pagep,key,val,ndx)264 __big_keydata(hashp, pagep, key, val, ndx)
265 HTAB *hashp;
266 PAGE16 *pagep;
267 DBT *key, *val;
268 int32_t ndx;
269 {
270 ITEM_INFO ii;
271 PAGE16 *key_pagep;
272 db_pgno_t last_page;
273
274 key_pagep =
275 __get_page(hashp, OADDR_TO_PAGE(DATA_OFF(pagep, ndx)), A_RAW);
276 if (!key_pagep)
277 return (-1);
278 key->size = collect_key(hashp, key_pagep, 0, &last_page);
279 key->data = hashp->bigkey_buf;
280 __put_page(hashp, key_pagep, A_RAW, 0);
281
282 if (key->size == -1)
283 return (-1);
284
285 /* Create an item_info to direct __big_return to the beginning pgno. */
286 ii.pgno = last_page;
287 return (__big_return(hashp, &ii, val, 1));
288 }
289
290 /*
291 * Return the big key on page, ndx.
292 */
293 int32_t
294 #ifdef __STDC__
__get_bigkey(HTAB * hashp,PAGE16 * pagep,indx_t ndx,DBT * key)295 __get_bigkey(HTAB *hashp, PAGE16 *pagep, indx_t ndx, DBT *key)
296 #else
297 __get_bigkey(hashp, pagep, ndx, key)
298 HTAB *hashp;
299 PAGE16 *pagep;
300 u_int32_t ndx;
301 DBT *key;
302 #endif
303 {
304 PAGE16 *key_pagep;
305
306 key_pagep =
307 __get_page(hashp, OADDR_TO_PAGE(DATA_OFF(pagep, ndx)), A_RAW);
308 if (!pagep)
309 return (-1);
310 key->size = collect_key(hashp, key_pagep, 0, NULL);
311 key->data = hashp->bigkey_buf;
312
313 __put_page(hashp, key_pagep, A_RAW, 0);
314
315 return (0);
316 }
317
318 /*
319 * Return the big key and data indicated in item_info.
320 */
321 int32_t
__big_return(hashp,item_info,val,on_bigkey_page)322 __big_return(hashp, item_info, val, on_bigkey_page)
323 HTAB *hashp;
324 ITEM_INFO *item_info;
325 DBT *val;
326 int32_t on_bigkey_page;
327 {
328 PAGE16 *pagep;
329 db_pgno_t next_pgno;
330
331 if (!on_bigkey_page) {
332 /* Get first page with big pair on it. */
333 pagep = __get_page(hashp,
334 OADDR_TO_PAGE(item_info->data_off), A_RAW);
335 if (!pagep)
336 return (-1);
337 } else {
338 pagep = __get_page(hashp, item_info->pgno, A_RAW);
339 if (!pagep)
340 return (-1);
341 }
342
343 /* Traverse through the bigkey pages until a page with data is found. */
344 while (!BIGDATALEN(pagep)) {
345 next_pgno = NEXT_PGNO(pagep);
346 __put_page(hashp, pagep, A_RAW, 0);
347 pagep = __get_page(hashp, next_pgno, A_RAW);
348 if (!pagep)
349 return (-1);
350 }
351
352 val->size = collect_data(hashp, pagep, 0);
353 if (val->size < 1)
354 return (-1);
355 val->data = (void *)hashp->bigdata_buf;
356
357 __put_page(hashp, pagep, A_RAW, 0);
358 return (0);
359 }
360
361 /*
362 * Given a page with a big key on it, traverse through the pages counting data
363 * length, and collect all of the data on the way up. Store the key in
364 * hashp->bigkey_buf. last_page indicates to the calling function what the
365 * last page with key on it is; this will help if you later want to retrieve
366 * the data portion.
367 *
368 * Does the work for __get_bigkey.
369 *
370 * Return total length of data; -1 if error.
371 */
372 static int32_t
collect_key(hashp,pagep,len,last_page)373 collect_key(hashp, pagep, len, last_page)
374 HTAB *hashp;
375 PAGE16 *pagep;
376 int32_t len;
377 db_pgno_t *last_page;
378 {
379 PAGE16 *next_pagep;
380 int32_t totlen, retval;
381 db_pgno_t next_pgno;
382 #ifdef DEBUG
383 db_pgno_t save_addr;
384 #endif
385
386 /* If this is the last page with key. */
387 if (BIGDATALEN(pagep)) {
388 totlen = len + BIGKEYLEN(pagep);
389 if (hashp->bigkey_buf)
390 free(hashp->bigkey_buf);
391 hashp->bigkey_buf = (u_int8_t *)malloc(totlen);
392 if (!hashp->bigkey_buf)
393 return (-1);
394 memcpy(hashp->bigkey_buf + len,
395 BIGKEY(pagep), BIGKEYLEN(pagep));
396 if (last_page)
397 *last_page = ADDR(pagep);
398 return (totlen);
399 }
400
401 /* Key filled up all of last key page, so we've gone 1 too far. */
402 if (BIGKEYLEN(pagep) == 0) {
403 if (hashp->bigkey_buf)
404 free(hashp->bigkey_buf);
405 hashp->bigkey_buf = (u_int8_t *)malloc(len);
406 return (hashp->bigkey_buf ? len : -1);
407 }
408 totlen = len + BIGKEYLEN(pagep);
409
410 /* Set pagep to the next page in the chain. */
411 if (last_page)
412 *last_page = ADDR(pagep);
413 next_pgno = NEXT_PGNO(pagep);
414 next_pagep = __get_page(hashp, next_pgno, A_RAW);
415 if (!next_pagep)
416 return (-1);
417 #ifdef DEBUG
418 save_addr = ADDR(pagep);
419 #endif
420 retval = collect_key(hashp, next_pagep, totlen, last_page);
421
422 #ifdef DEBUG
423 assert(save_addr == ADDR(pagep));
424 #endif
425 memcpy(hashp->bigkey_buf + len, BIGKEY(pagep), BIGKEYLEN(pagep));
426 __put_page(hashp, next_pagep, A_RAW, 0);
427
428 return (retval);
429 }
430
431 /*
432 * Given a page with big data on it, recur through the pages counting data
433 * length, and collect all of the data on the way up. Store the data in
434 * hashp->bigdata_buf.
435 *
436 * Does the work for __big_return.
437 *
438 * Return total length of data; -1 if error.
439 */
440 static int32_t
collect_data(hashp,pagep,len)441 collect_data(hashp, pagep, len)
442 HTAB *hashp;
443 PAGE16 *pagep;
444 int32_t len;
445 {
446 PAGE16 *next_pagep;
447 int32_t totlen, retval;
448 db_pgno_t next_pgno;
449 #ifdef DEBUG
450 db_pgno_t save_addr;
451 #endif
452
453 /* If there is no next page. */
454 if (NEXT_PGNO(pagep) == INVALID_PGNO) {
455 if (hashp->bigdata_buf)
456 free(hashp->bigdata_buf);
457 totlen = len + BIGDATALEN(pagep);
458 hashp->bigdata_buf = (u_int8_t *)malloc(totlen);
459 if (!hashp->bigdata_buf)
460 return (-1);
461 memcpy(hashp->bigdata_buf + totlen - BIGDATALEN(pagep),
462 BIGDATA(pagep), BIGDATALEN(pagep));
463 return (totlen);
464 }
465 totlen = len + BIGDATALEN(pagep);
466
467 /* Set pagep to the next page in the chain. */
468 next_pgno = NEXT_PGNO(pagep);
469 next_pagep = __get_page(hashp, next_pgno, A_RAW);
470 if (!next_pagep)
471 return (-1);
472
473 #ifdef DEBUG
474 save_addr = ADDR(pagep);
475 #endif
476 retval = collect_data(hashp, next_pagep, totlen);
477 #ifdef DEBUG
478 assert(save_addr == ADDR(pagep));
479 #endif
480 memcpy(hashp->bigdata_buf + totlen - BIGDATALEN(pagep),
481 BIGDATA(pagep), BIGDATALEN(pagep));
482 __put_page(hashp, next_pagep, A_RAW, 0);
483
484 return (retval);
485 }
486