2
* Copyright (c) 1990, 1993, 1994
3
* The Regents of the University of California. All rights reserved.
5
* This code is derived from software contributed to Berkeley by
8
* Redistribution and use in source and binary forms, with or without
9
* modification, are permitted provided that the following conditions
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.
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
37
#if defined(LIBC_SCCS) && !defined(lint)
38
static char sccsid[] = "@(#)bt_utils.c 8.8 (Berkeley) 7/20/94";
39
#endif /* LIBC_SCCS and not lint */
41
#include <sys/param.h>
52
* Build return key/data pair.
56
* e: key/data pair to be returned
57
* key: user's key structure (NULL if not to be filled in)
58
* rkey: memory area to hold key
59
* data: user's data structure (NULL if not to be filled in)
60
* rdata: memory area to hold data
61
* copy: always copy the key/data item
64
* RET_SUCCESS, RET_ERROR.
67
__bt_ret(t, e, key, rkey, data, rdata, copy)
70
DBT *key, *rkey, *data, *rdata;
76
bl = GETBLEAF(e->page, e->index);
79
* We must copy big keys/data to make them contigous. Otherwise,
80
* leave the page pinned and don't copy unless the user specified
86
if (bl->flags & P_BIGKEY) {
87
if (__ovfl_get(t, bl->bytes,
88
&key->size, &rkey->data, &rkey->size))
90
key->data = rkey->data;
91
} else if (copy || F_ISSET(t, B_DB_LOCK)) {
92
if (bl->ksize > rkey->size) {
93
p = (void *)(rkey->data == NULL ?
94
malloc(bl->ksize) : realloc(rkey->data, bl->ksize));
98
rkey->size = bl->ksize;
100
memmove(rkey->data, bl->bytes, bl->ksize);
101
key->size = bl->ksize;
102
key->data = rkey->data;
104
key->size = bl->ksize;
105
key->data = bl->bytes;
110
return (RET_SUCCESS);
112
if (bl->flags & P_BIGDATA) {
113
if (__ovfl_get(t, bl->bytes + bl->ksize,
114
&data->size, &rdata->data, &rdata->size))
116
data->data = rdata->data;
117
} else if (copy || F_ISSET(t, B_DB_LOCK)) {
118
/* Use +1 in case the first record retrieved is 0 length. */
119
if (bl->dsize + 1 > rdata->size) {
120
p = (void *)(rdata->data == NULL ?
121
malloc(bl->dsize + 1) :
122
realloc(rdata->data, bl->dsize + 1));
126
rdata->size = bl->dsize + 1;
128
memmove(rdata->data, bl->bytes + bl->ksize, bl->dsize);
129
data->size = bl->dsize;
130
data->data = rdata->data;
132
data->size = bl->dsize;
133
data->data = bl->bytes + bl->ksize;
136
return (RET_SUCCESS);
140
* __BT_CMP -- Compare a key to a given record.
144
* k1: DBT pointer of first arg to comparison
145
* e: pointer to EPG for comparison
148
* < 0 if k1 is < record
149
* = 0 if k1 is = record
150
* > 0 if k1 is > record
165
* The left-most key on internal pages, at any level of the tree, is
166
* guaranteed by the following code to be less than any user key.
167
* This saves us from having to update the leftmost key on an internal
168
* page when the user inserts a new key in the tree smaller than
169
* anything we've yet seen.
172
if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF))
176
if (h->flags & P_BLEAF) {
177
bl = GETBLEAF(h, e->index);
178
if (bl->flags & P_BIGKEY)
185
bi = GETBINTERNAL(h, e->index);
186
if (bi->flags & P_BIGKEY)
195
if (__ovfl_get(t, bigkey,
196
&k2.size, &t->bt_rdata.data, &t->bt_rdata.size))
198
k2.data = t->bt_rdata.data;
200
return ((*t->bt_cmp)(k1, &k2));
204
* __BT_DEFCMP -- Default comparison routine.
220
register u_char *p1, *p2;
224
* If a size_t doesn't fit in an int, this routine can lose.
225
* What we need is a integral type which is guaranteed to be
226
* larger than a size_t, and there is no such thing.
228
len = MIN(a->size, b->size);
229
for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2)
231
return ((int)*p1 - (int)*p2);
232
return ((int)a->size - (int)b->size);
236
* __BT_DEFPFX -- Default prefix routine.
243
* Number of bytes needed to distinguish b from a.
249
register u_char *p1, *p2;
250
register size_t cnt, len;
253
len = MIN(a->size, b->size);
254
for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
258
/* a->size must be <= b->size, or they wouldn't be in this order. */
259
return (a->size < b->size ? a->size + 1 : a->size);