1/*	$NetBSD: bt_utils.c,v 1.12 2008/08/26 21:18:38 joerg Exp $	*/
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 * Mike Olson.
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. Neither the name of the University nor the names of its contributors
19 *    may be used to endorse or promote products derived from this software
20 *    without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE.
33 */
34
35#if HAVE_NBTOOL_CONFIG_H
36#include "nbtool_config.h"
37#endif
38
39#include <sys/cdefs.h>
40__RCSID("$NetBSD: bt_utils.c,v 1.12 2008/08/26 21:18:38 joerg Exp $");
41
42#include <sys/param.h>
43
44#include <assert.h>
45#include <stdio.h>
46#include <stdlib.h>
47#include <string.h>
48
49#include <db.h>
50#include "btree.h"
51
52/*
53 * __bt_ret --
54 *	Build return key/data pair.
55 *
56 * Parameters:
57 *	t:	tree
58 *	e:	key/data pair to be returned
59 *	key:	user's key structure (NULL if not to be filled in)
60 *	rkey:	memory area to hold key
61 *	data:	user's data structure (NULL if not to be filled in)
62 *	rdata:	memory area to hold data
63 *       copy:	always copy the key/data item
64 *
65 * Returns:
66 *	RET_SUCCESS, RET_ERROR.
67 */
68int
69__bt_ret(BTREE *t, EPG *e, DBT *key, DBT *rkey, DBT *data, DBT *rdata, int copy)
70{
71	BLEAF *bl;
72	void *p;
73
74	bl = GETBLEAF(e->page, e->index);
75
76	/*
77	 * We must copy big keys/data to make them contigous.  Otherwise,
78	 * leave the page pinned and don't copy unless the user specified
79	 * concurrent access.
80	 */
81	if (key == NULL)
82		goto dataonly;
83
84	if (bl->flags & P_BIGKEY) {
85		if (__ovfl_get(t, bl->bytes,
86		    &key->size, &rkey->data, &rkey->size))
87			return (RET_ERROR);
88		key->data = rkey->data;
89	} else if (copy || F_ISSET(t, B_DB_LOCK)) {
90		if (bl->ksize > rkey->size) {
91			p = (void *)(rkey->data == NULL ?
92			    malloc(bl->ksize) : realloc(rkey->data, bl->ksize));
93			if (p == NULL)
94				return (RET_ERROR);
95			rkey->data = p;
96			rkey->size = bl->ksize;
97		}
98		memmove(rkey->data, bl->bytes, bl->ksize);
99		key->size = bl->ksize;
100		key->data = rkey->data;
101	} else {
102		key->size = bl->ksize;
103		key->data = bl->bytes;
104	}
105
106dataonly:
107	if (data == NULL)
108		return (RET_SUCCESS);
109
110	if (bl->flags & P_BIGDATA) {
111		if (__ovfl_get(t, bl->bytes + bl->ksize,
112		    &data->size, &rdata->data, &rdata->size))
113			return (RET_ERROR);
114		data->data = rdata->data;
115	} else if (copy || F_ISSET(t, B_DB_LOCK)) {
116		/* Use +1 in case the first record retrieved is 0 length. */
117		if (bl->dsize + 1 > rdata->size) {
118			p = (void *)(rdata->data == NULL ?
119			    malloc(bl->dsize + 1) :
120			    realloc(rdata->data, bl->dsize + 1));
121			if (p == NULL)
122				return (RET_ERROR);
123			rdata->data = p;
124			rdata->size = bl->dsize + 1;
125		}
126		memmove(rdata->data, bl->bytes + bl->ksize, bl->dsize);
127		data->size = bl->dsize;
128		data->data = rdata->data;
129	} else {
130		data->size = bl->dsize;
131		data->data = bl->bytes + bl->ksize;
132	}
133
134	return (RET_SUCCESS);
135}
136
137/*
138 * __BT_CMP -- Compare a key to a given record.
139 *
140 * Parameters:
141 *	t:	tree
142 *	k1:	DBT pointer of first arg to comparison
143 *	e:	pointer to EPG for comparison
144 *
145 * Returns:
146 *	< 0 if k1 is < record
147 *	= 0 if k1 is = record
148 *	> 0 if k1 is > record
149 */
150int
151__bt_cmp(BTREE *t, const DBT *k1, EPG *e)
152{
153	BINTERNAL *bi;
154	BLEAF *bl;
155	DBT k2;
156	PAGE *h;
157	void *bigkey;
158
159	/*
160	 * The left-most key on internal pages, at any level of the tree, is
161	 * guaranteed by the following code to be less than any user key.
162	 * This saves us from having to update the leftmost key on an internal
163	 * page when the user inserts a new key in the tree smaller than
164	 * anything we've yet seen.
165	 */
166	h = e->page;
167	if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF))
168		return (1);
169
170	bigkey = NULL;
171	if (h->flags & P_BLEAF) {
172		bl = GETBLEAF(h, e->index);
173		if (bl->flags & P_BIGKEY)
174			bigkey = bl->bytes;
175		else {
176			k2.data = bl->bytes;
177			k2.size = bl->ksize;
178		}
179	} else {
180		bi = GETBINTERNAL(h, e->index);
181		if (bi->flags & P_BIGKEY)
182			bigkey = bi->bytes;
183		else {
184			k2.data = bi->bytes;
185			k2.size = bi->ksize;
186		}
187	}
188
189	if (bigkey) {
190		if (__ovfl_get(t, bigkey,
191		    &k2.size, &t->bt_rdata.data, &t->bt_rdata.size))
192			return (RET_ERROR);
193		k2.data = t->bt_rdata.data;
194	}
195	return ((*t->bt_cmp)(k1, &k2));
196}
197
198/*
199 * __BT_DEFCMP -- Default comparison routine.
200 *
201 * Parameters:
202 *	a:	DBT #1
203 *	b: 	DBT #2
204 *
205 * Returns:
206 *	< 0 if a is < b
207 *	= 0 if a is = b
208 *	> 0 if a is > b
209 */
210int
211__bt_defcmp(const DBT *a, const DBT *b)
212{
213	size_t len;
214	uint8_t *p1, *p2;
215
216	/*
217	 * XXX
218	 * If a size_t doesn't fit in an int, this routine can lose.
219	 * What we need is a integral type which is guaranteed to be
220	 * larger than a size_t, and there is no such thing.
221	 */
222	len = MIN(a->size, b->size);
223	for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2)
224		if (*p1 != *p2)
225			return ((int)*p1 - (int)*p2);
226	return ((int)a->size - (int)b->size);
227}
228
229/*
230 * __BT_DEFPFX -- Default prefix routine.
231 *
232 * Parameters:
233 *	a:	DBT #1
234 *	b: 	DBT #2
235 *
236 * Returns:
237 *	Number of bytes needed to distinguish b from a.
238 */
239size_t
240__bt_defpfx(const DBT *a, const DBT *b)
241{
242	uint8_t *p1, *p2;
243	size_t cnt, len;
244
245	cnt = 1;
246	len = MIN(a->size, b->size);
247	for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
248		if (*p1 != *p2)
249			return (cnt);
250
251	/* a->size must be <= b->size, or they wouldn't be in this order. */
252	return (a->size < b->size ? a->size + 1 : a->size);
253}
254