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 #if defined(LIBC_SCCS) && !defined(lint)
38 static char sccsid[] = "@(#)hash_bigkey.c 8.5 (Berkeley) 11/2/95";
39 #endif /* LIBC_SCCS and not lint */
40
41 /*
42 * PACKAGE: hash
43 * DESCRIPTION:
44 * Big key/data handling for the hashing package.
45 *
46 * ROUTINES:
47 * External
48 * __big_keydata
49 * __big_split
50 * __big_insert
51 * __big_return
52 * __big_delete
53 * __find_last_page
54 * Internal
55 * collect_key
56 * collect_data
57 */
58 #include <sys/types.h>
59
60 #include <stdlib.h>
61 #include <string.h>
62
63 #ifdef DEBUG
64 #include <assert.h>
65 #endif
66
67 #include "db-int.h"
68 #include "hash.h"
69 #include "page.h"
70 #include "extern.h"
71
72 static int32_t collect_key __P((HTAB *, PAGE16 *, int32_t, db_pgno_t *));
73 static int32_t collect_data __P((HTAB *, PAGE16 *, int32_t));
74
75 /*
76 * Big_insert
77 *
78 * You need to do an insert and the key/data pair is greater than
79 * MINFILL * the bucket size
80 *
81 * Returns:
82 * 0 ==> OK
83 * -1 ==> ERROR
84 */
85 int32_t
__big_insert(hashp,pagep,key,val)86 __big_insert(hashp, pagep, key, val)
87 HTAB *hashp;
88 PAGE16 *pagep;
89 const DBT *key, *val;
90 {
91 size_t key_size, val_size;
92 indx_t key_move_bytes, val_move_bytes;
93 int8_t *key_data, *val_data, base_page;
94
95 key_data = (int8_t *)key->data;
96 key_size = key->size;
97 val_data = (int8_t *)val->data;
98 val_size = val->size;
99
100 NUM_ENT(pagep) = NUM_ENT(pagep) + 1;
101
102 for (base_page = 1; key_size + val_size;) {
103 /* Add a page! */
104 pagep =
105 __add_bigpage(hashp, pagep, NUM_ENT(pagep) - 1, base_page);
106 if (!pagep)
107 return (-1);
108
109 /* There's just going to be one entry on this page. */
110 NUM_ENT(pagep) = 1;
111
112 /* Move the key's data. */
113 key_move_bytes = MIN(FREESPACE(pagep), key_size);
114 /* Mark the page as to how much key & data is on this page. */
115 BIGKEYLEN(pagep) = key_move_bytes;
116 val_move_bytes =
117 MIN(FREESPACE(pagep) - key_move_bytes, val_size);
118 BIGDATALEN(pagep) = val_move_bytes;
119
120 /* Note big pages build beginning --> end, not vice versa. */
121 if (key_move_bytes)
122 memmove(BIGKEY(pagep), key_data, key_move_bytes);
123 if (val_move_bytes)
124 memmove(BIGDATA(pagep), val_data, val_move_bytes);
125
126 key_size -= key_move_bytes;
127 key_data += key_move_bytes;
128 val_size -= val_move_bytes;
129 val_data += val_move_bytes;
130
131 base_page = 0;
132 }
133 __put_page(hashp, pagep, A_RAW, 1);
134 return (0);
135 }
136
137 /*
138 * Called when we need to delete a big pair.
139 *
140 * Returns:
141 * 0 => OK
142 * -1 => ERROR
143 */
144 int32_t
145 #ifdef __STDC__
__big_delete(HTAB * hashp,PAGE16 * pagep,indx_t ndx)146 __big_delete(HTAB *hashp, PAGE16 *pagep, indx_t ndx)
147 #else
148 __big_delete(hashp, pagep, ndx)
149 HTAB *hashp;
150 PAGE16 *pagep;
151 u_int32_t ndx; /* Index of big pair on base page. */
152 #endif
153 {
154 PAGE16 *last_pagep;
155
156 /* Get first page with big key/data. */
157 pagep = __get_page(hashp, OADDR_TO_PAGE(DATA_OFF(pagep, ndx)), A_RAW);
158 if (!pagep)
159 return (-1);
160
161 /*
162 * Traverse through the pages, freeing the previous one (except
163 * the first) at each new page.
164 */
165 while (NEXT_PGNO(pagep) != INVALID_PGNO) {
166 last_pagep = pagep;
167 pagep = __get_page(hashp, NEXT_PGNO(pagep), A_RAW);
168 if (!pagep)
169 return (-1);
170 __delete_page(hashp, last_pagep, A_OVFL);
171 }
172
173 /* Free the last page in the chain. */
174 __delete_page(hashp, pagep, A_OVFL);
175 return (0);
176 }
177
178 /*
179 * Given a key, indicates whether the big key at cursorp matches the
180 * given key.
181 *
182 * Returns:
183 * 1 = Found!
184 * 0 = Key not found
185 * -1 error
186 */
187 int32_t
__find_bigpair(hashp,cursorp,key,size)188 __find_bigpair(hashp, cursorp, key, size)
189 HTAB *hashp;
190 CURSOR *cursorp;
191 int8_t *key;
192 int32_t size;
193 {
194 PAGE16 *pagep, *hold_pagep;
195 db_pgno_t next_pgno;
196 int32_t ksize;
197 int8_t *kkey;
198
199 ksize = size;
200 kkey = key;
201
202 hold_pagep = NULL;
203 /* Chances are, hashp->cpage is the base page. */
204 if (cursorp->pagep)
205 pagep = hold_pagep = cursorp->pagep;
206 else {
207 pagep = __get_page(hashp, cursorp->pgno, A_RAW);
208 if (!pagep)
209 return (-1);
210 }
211
212 /*
213 * Now, get the first page with the big stuff on it.
214 *
215 * XXX
216 * KLUDGE: we know that cursor is looking at the _next_ item, so
217 * we have to look at pgndx - 1.
218 */
219 next_pgno = OADDR_TO_PAGE(DATA_OFF(pagep, (cursorp->pgndx - 1)));
220 if (!hold_pagep)
221 __put_page(hashp, pagep, A_RAW, 0);
222 pagep = __get_page(hashp, next_pgno, A_RAW);
223 if (!pagep)
224 return (-1);
225
226 /* While there are both keys to compare. */
227 while ((ksize > 0) && (BIGKEYLEN(pagep))) {
228 if (ksize < KEY_OFF(pagep, 0) ||
229 memcmp(BIGKEY(pagep), kkey, BIGKEYLEN(pagep))) {
230 __put_page(hashp, pagep, A_RAW, 0);
231 return (0);
232 }
233 kkey += BIGKEYLEN(pagep);
234 ksize -= BIGKEYLEN(pagep);
235 if (NEXT_PGNO(pagep) != INVALID_PGNO) {
236 next_pgno = NEXT_PGNO(pagep);
237 __put_page(hashp, pagep, A_RAW, 0);
238 pagep = __get_page(hashp, next_pgno, A_RAW);
239 if (!pagep)
240 return (-1);
241 }
242 }
243 __put_page(hashp, pagep, A_RAW, 0);
244 #ifdef DEBUG
245 assert(ksize >= 0);
246 #endif
247 if (ksize != 0) {
248 #ifdef HASH_STATISTICS
249 ++hash_collisions;
250 #endif
251 return (0);
252 } else
253 return (1);
254 }
255
256 /*
257 * Fill in the key and data for this big pair.
258 */
259 int32_t
__big_keydata(hashp,pagep,key,val,ndx)260 __big_keydata(hashp, pagep, key, val, ndx)
261 HTAB *hashp;
262 PAGE16 *pagep;
263 DBT *key, *val;
264 int32_t ndx;
265 {
266 ITEM_INFO ii;
267 PAGE16 *key_pagep;
268 db_pgno_t last_page;
269
270 key_pagep =
271 __get_page(hashp, OADDR_TO_PAGE(DATA_OFF(pagep, ndx)), A_RAW);
272 if (!key_pagep)
273 return (-1);
274 key->size = collect_key(hashp, key_pagep, 0, &last_page);
275 key->data = hashp->bigkey_buf;
276 __put_page(hashp, key_pagep, A_RAW, 0);
277
278 if (key->size == (size_t)-1)
279 return (-1);
280
281 /* Create an item_info to direct __big_return to the beginning pgno. */
282 ii.pgno = last_page;
283 return (__big_return(hashp, &ii, val, 1));
284 }
285
286 /*
287 * Return the big key on page, ndx.
288 */
289 int32_t
290 #ifdef __STDC__
__get_bigkey(HTAB * hashp,PAGE16 * pagep,indx_t ndx,DBT * key)291 __get_bigkey(HTAB *hashp, PAGE16 *pagep, indx_t ndx, DBT *key)
292 #else
293 __get_bigkey(hashp, pagep, ndx, key)
294 HTAB *hashp;
295 PAGE16 *pagep;
296 u_int32_t ndx;
297 DBT *key;
298 #endif
299 {
300 PAGE16 *key_pagep;
301
302 key_pagep =
303 __get_page(hashp, OADDR_TO_PAGE(DATA_OFF(pagep, ndx)), A_RAW);
304 if (!key_pagep)
305 return (-1);
306 key->size = collect_key(hashp, key_pagep, 0, NULL);
307 key->data = hashp->bigkey_buf;
308
309 __put_page(hashp, key_pagep, A_RAW, 0);
310
311 return (0);
312 }
313
314 /*
315 * Return the big key and data indicated in item_info.
316 */
317 int32_t
__big_return(hashp,item_info,val,on_bigkey_page)318 __big_return(hashp, item_info, val, on_bigkey_page)
319 HTAB *hashp;
320 ITEM_INFO *item_info;
321 DBT *val;
322 int32_t on_bigkey_page;
323 {
324 PAGE16 *pagep;
325 db_pgno_t next_pgno;
326
327 if (!on_bigkey_page) {
328 /* Get first page with big pair on it. */
329 pagep = __get_page(hashp,
330 OADDR_TO_PAGE(item_info->data_off), A_RAW);
331 if (!pagep)
332 return (-1);
333 } else {
334 pagep = __get_page(hashp, item_info->pgno, A_RAW);
335 if (!pagep)
336 return (-1);
337 }
338
339 /* Traverse through the bigkey pages until a page with data is found. */
340 while (!BIGDATALEN(pagep)) {
341 next_pgno = NEXT_PGNO(pagep);
342 __put_page(hashp, pagep, A_RAW, 0);
343 pagep = __get_page(hashp, next_pgno, A_RAW);
344 if (!pagep)
345 return (-1);
346 }
347
348 val->size = collect_data(hashp, pagep, 0);
349 if (val->size < 1)
350 return (-1);
351 val->data = (void *)hashp->bigdata_buf;
352
353 __put_page(hashp, pagep, A_RAW, 0);
354 return (0);
355 }
356
357 /*
358 * Given a page with a big key on it, traverse through the pages counting data
359 * length, and collect all of the data on the way up. Store the key in
360 * hashp->bigkey_buf. last_page indicates to the calling function what the
361 * last page with key on it is; this will help if you later want to retrieve
362 * the data portion.
363 *
364 * Does the work for __get_bigkey.
365 *
366 * Return total length of data; -1 if error.
367 */
368 static int32_t
collect_key(hashp,pagep,len,last_page)369 collect_key(hashp, pagep, len, last_page)
370 HTAB *hashp;
371 PAGE16 *pagep;
372 int32_t len;
373 db_pgno_t *last_page;
374 {
375 PAGE16 *next_pagep;
376 int32_t totlen, retval;
377 db_pgno_t next_pgno;
378 #ifdef DEBUG
379 db_pgno_t save_addr;
380 #endif
381
382 /* If this is the last page with key. */
383 if (BIGDATALEN(pagep)) {
384 totlen = len + BIGKEYLEN(pagep);
385 if (hashp->bigkey_buf)
386 free(hashp->bigkey_buf);
387 hashp->bigkey_buf = (u_int8_t *)malloc(totlen);
388 if (!hashp->bigkey_buf)
389 return (-1);
390 memcpy(hashp->bigkey_buf + len,
391 BIGKEY(pagep), BIGKEYLEN(pagep));
392 if (last_page)
393 *last_page = ADDR(pagep);
394 return (totlen);
395 }
396
397 /* Key filled up all of last key page, so we've gone 1 too far. */
398 if (BIGKEYLEN(pagep) == 0) {
399 if (hashp->bigkey_buf)
400 free(hashp->bigkey_buf);
401 hashp->bigkey_buf = (u_int8_t *)malloc(len);
402 return (hashp->bigkey_buf ? len : -1);
403 }
404 totlen = len + BIGKEYLEN(pagep);
405
406 /* Set pagep to the next page in the chain. */
407 if (last_page)
408 *last_page = ADDR(pagep);
409 next_pgno = NEXT_PGNO(pagep);
410 next_pagep = __get_page(hashp, next_pgno, A_RAW);
411 if (!next_pagep)
412 return (-1);
413 #ifdef DEBUG
414 save_addr = ADDR(pagep);
415 #endif
416 retval = collect_key(hashp, next_pagep, totlen, last_page);
417
418 #ifdef DEBUG
419 assert(save_addr == ADDR(pagep));
420 #endif
421 memcpy(hashp->bigkey_buf + len, BIGKEY(pagep), BIGKEYLEN(pagep));
422 __put_page(hashp, next_pagep, A_RAW, 0);
423
424 return (retval);
425 }
426
427 /*
428 * Given a page with big data on it, recur through the pages counting data
429 * length, and collect all of the data on the way up. Store the data in
430 * hashp->bigdata_buf.
431 *
432 * Does the work for __big_return.
433 *
434 * Return total length of data; -1 if error.
435 */
436 static int32_t
collect_data(hashp,pagep,len)437 collect_data(hashp, pagep, len)
438 HTAB *hashp;
439 PAGE16 *pagep;
440 int32_t len;
441 {
442 PAGE16 *next_pagep;
443 int32_t totlen, retval;
444 db_pgno_t next_pgno;
445 #ifdef DEBUG
446 db_pgno_t save_addr;
447 #endif
448
449 /* If there is no next page. */
450 if (NEXT_PGNO(pagep) == INVALID_PGNO) {
451 if (hashp->bigdata_buf)
452 free(hashp->bigdata_buf);
453 totlen = len + BIGDATALEN(pagep);
454 hashp->bigdata_buf = (u_int8_t *)malloc(totlen);
455 if (!hashp->bigdata_buf)
456 return (-1);
457 memcpy(hashp->bigdata_buf + totlen - BIGDATALEN(pagep),
458 BIGDATA(pagep), BIGDATALEN(pagep));
459 return (totlen);
460 }
461 totlen = len + BIGDATALEN(pagep);
462
463 /* Set pagep to the next page in the chain. */
464 next_pgno = NEXT_PGNO(pagep);
465 next_pagep = __get_page(hashp, next_pgno, A_RAW);
466 if (!next_pagep)
467 return (-1);
468
469 #ifdef DEBUG
470 save_addr = ADDR(pagep);
471 #endif
472 retval = collect_data(hashp, next_pagep, totlen);
473 #ifdef DEBUG
474 assert(save_addr == ADDR(pagep));
475 #endif
476 memcpy(hashp->bigdata_buf + totlen - BIGDATALEN(pagep),
477 BIGDATA(pagep), BIGDATALEN(pagep));
478 __put_page(hashp, next_pagep, A_RAW, 0);
479
480 return (retval);
481 }
482