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