1 | #include "port_before.h" |
---|
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 | * 4. 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 defined(LIBC_SCCS) && !defined(lint) |
---|
36 | static char sccsid[] = "@(#)bt_utils.c 8.8 (Berkeley) 7/20/94"; |
---|
37 | #endif /* LIBC_SCCS and not lint */ |
---|
38 | #include <sys/cdefs.h> |
---|
39 | __FBSDID("$FreeBSD$"); |
---|
40 | |
---|
41 | #include <sys/param.h> |
---|
42 | |
---|
43 | #include <stdio.h> |
---|
44 | #include <stdlib.h> |
---|
45 | #include <string.h> |
---|
46 | |
---|
47 | #include <db.h> |
---|
48 | #include "btree.h" |
---|
49 | |
---|
50 | /* |
---|
51 | * __bt_ret -- |
---|
52 | * Build return key/data pair. |
---|
53 | * |
---|
54 | * Parameters: |
---|
55 | * t: tree |
---|
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 |
---|
62 | * |
---|
63 | * Returns: |
---|
64 | * RET_SUCCESS, RET_ERROR. |
---|
65 | */ |
---|
66 | int |
---|
67 | __bt_ret(BTREE *t, EPG *e, DBT *key, DBT *rkey, DBT *data, DBT *rdata, int copy) |
---|
68 | { |
---|
69 | BLEAF *bl; |
---|
70 | void *p; |
---|
71 | |
---|
72 | bl = GETBLEAF(e->page, e->index); |
---|
73 | |
---|
74 | /* |
---|
75 | * We must copy big keys/data to make them contigous. Otherwise, |
---|
76 | * leave the page pinned and don't copy unless the user specified |
---|
77 | * concurrent access. |
---|
78 | */ |
---|
79 | if (key == NULL) |
---|
80 | goto dataonly; |
---|
81 | |
---|
82 | if (bl->flags & P_BIGKEY) { |
---|
83 | if (__ovfl_get(t, bl->bytes, |
---|
84 | &key->size, &rkey->data, &rkey->size)) |
---|
85 | return (RET_ERROR); |
---|
86 | key->data = rkey->data; |
---|
87 | } else if (copy || F_ISSET(t, B_DB_LOCK)) { |
---|
88 | if (bl->ksize > rkey->size) { |
---|
89 | p = realloc(rkey->data, bl->ksize); |
---|
90 | if (p == NULL) |
---|
91 | return (RET_ERROR); |
---|
92 | rkey->data = p; |
---|
93 | rkey->size = bl->ksize; |
---|
94 | } |
---|
95 | memmove(rkey->data, bl->bytes, bl->ksize); |
---|
96 | key->size = bl->ksize; |
---|
97 | key->data = rkey->data; |
---|
98 | } else { |
---|
99 | key->size = bl->ksize; |
---|
100 | key->data = bl->bytes; |
---|
101 | } |
---|
102 | |
---|
103 | dataonly: |
---|
104 | if (data == NULL) |
---|
105 | return (RET_SUCCESS); |
---|
106 | |
---|
107 | if (bl->flags & P_BIGDATA) { |
---|
108 | if (__ovfl_get(t, bl->bytes + bl->ksize, |
---|
109 | &data->size, &rdata->data, &rdata->size)) |
---|
110 | return (RET_ERROR); |
---|
111 | data->data = rdata->data; |
---|
112 | } else if (copy || F_ISSET(t, B_DB_LOCK)) { |
---|
113 | /* Use +1 in case the first record retrieved is 0 length. */ |
---|
114 | if (bl->dsize + 1 > rdata->size) { |
---|
115 | p = realloc(rdata->data, bl->dsize + 1); |
---|
116 | if (p == NULL) |
---|
117 | return (RET_ERROR); |
---|
118 | rdata->data = p; |
---|
119 | rdata->size = bl->dsize + 1; |
---|
120 | } |
---|
121 | memmove(rdata->data, bl->bytes + bl->ksize, bl->dsize); |
---|
122 | data->size = bl->dsize; |
---|
123 | data->data = rdata->data; |
---|
124 | } else { |
---|
125 | data->size = bl->dsize; |
---|
126 | data->data = bl->bytes + bl->ksize; |
---|
127 | } |
---|
128 | |
---|
129 | return (RET_SUCCESS); |
---|
130 | } |
---|
131 | |
---|
132 | /* |
---|
133 | * __BT_CMP -- Compare a key to a given record. |
---|
134 | * |
---|
135 | * Parameters: |
---|
136 | * t: tree |
---|
137 | * k1: DBT pointer of first arg to comparison |
---|
138 | * e: pointer to EPG for comparison |
---|
139 | * |
---|
140 | * Returns: |
---|
141 | * < 0 if k1 is < record |
---|
142 | * = 0 if k1 is = record |
---|
143 | * > 0 if k1 is > record |
---|
144 | */ |
---|
145 | int |
---|
146 | __bt_cmp(BTREE *t, const DBT *k1, EPG *e) |
---|
147 | { |
---|
148 | BINTERNAL *bi; |
---|
149 | BLEAF *bl; |
---|
150 | DBT k2; |
---|
151 | PAGE *h; |
---|
152 | void *bigkey; |
---|
153 | |
---|
154 | /* |
---|
155 | * The left-most key on internal pages, at any level of the tree, is |
---|
156 | * guaranteed by the following code to be less than any user key. |
---|
157 | * This saves us from having to update the leftmost key on an internal |
---|
158 | * page when the user inserts a new key in the tree smaller than |
---|
159 | * anything we've yet seen. |
---|
160 | */ |
---|
161 | h = e->page; |
---|
162 | if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF)) |
---|
163 | return (1); |
---|
164 | |
---|
165 | bigkey = NULL; |
---|
166 | if (h->flags & P_BLEAF) { |
---|
167 | bl = GETBLEAF(h, e->index); |
---|
168 | if (bl->flags & P_BIGKEY) |
---|
169 | bigkey = bl->bytes; |
---|
170 | else { |
---|
171 | k2.data = bl->bytes; |
---|
172 | k2.size = bl->ksize; |
---|
173 | } |
---|
174 | } else { |
---|
175 | bi = GETBINTERNAL(h, e->index); |
---|
176 | if (bi->flags & P_BIGKEY) |
---|
177 | bigkey = bi->bytes; |
---|
178 | else { |
---|
179 | k2.data = bi->bytes; |
---|
180 | k2.size = bi->ksize; |
---|
181 | } |
---|
182 | } |
---|
183 | |
---|
184 | if (bigkey) { |
---|
185 | if (__ovfl_get(t, bigkey, |
---|
186 | &k2.size, &t->bt_rdata.data, &t->bt_rdata.size)) |
---|
187 | return (RET_ERROR); |
---|
188 | k2.data = t->bt_rdata.data; |
---|
189 | } |
---|
190 | return ((*t->bt_cmp)(k1, &k2)); |
---|
191 | } |
---|
192 | |
---|
193 | /* |
---|
194 | * __BT_DEFCMP -- Default comparison routine. |
---|
195 | * |
---|
196 | * Parameters: |
---|
197 | * a: DBT #1 |
---|
198 | * b: DBT #2 |
---|
199 | * |
---|
200 | * Returns: |
---|
201 | * < 0 if a is < b |
---|
202 | * = 0 if a is = b |
---|
203 | * > 0 if a is > b |
---|
204 | */ |
---|
205 | int |
---|
206 | __bt_defcmp(const DBT *a, const DBT *b) |
---|
207 | { |
---|
208 | size_t len; |
---|
209 | u_char *p1, *p2; |
---|
210 | |
---|
211 | /* |
---|
212 | * XXX |
---|
213 | * If a size_t doesn't fit in an int, this routine can lose. |
---|
214 | * What we need is an integral type which is guaranteed to be |
---|
215 | * larger than a size_t, and there is no such thing. |
---|
216 | */ |
---|
217 | len = MIN(a->size, b->size); |
---|
218 | for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2) |
---|
219 | if (*p1 != *p2) |
---|
220 | return ((int)*p1 - (int)*p2); |
---|
221 | return ((int)a->size - (int)b->size); |
---|
222 | } |
---|
223 | |
---|
224 | /* |
---|
225 | * __BT_DEFPFX -- Default prefix routine. |
---|
226 | * |
---|
227 | * Parameters: |
---|
228 | * a: DBT #1 |
---|
229 | * b: DBT #2 |
---|
230 | * |
---|
231 | * Returns: |
---|
232 | * Number of bytes needed to distinguish b from a. |
---|
233 | */ |
---|
234 | size_t |
---|
235 | __bt_defpfx(const DBT *a, const DBT *b) |
---|
236 | { |
---|
237 | u_char *p1, *p2; |
---|
238 | size_t cnt, len; |
---|
239 | |
---|
240 | cnt = 1; |
---|
241 | len = MIN(a->size, b->size); |
---|
242 | for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt) |
---|
243 | if (*p1 != *p2) |
---|
244 | return (cnt); |
---|
245 | |
---|
246 | /* a->size must be <= b->size, or they wouldn't be in this order. */ |
---|
247 | return (a->size < b->size ? a->size + 1 : a->size); |
---|
248 | } |
---|