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
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__
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
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
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__
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
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
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
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