Commit | Line | Data |
---|---|---|
fb5357d5 | 1 | /*- |
2d87c421 KB |
2 | * Copyright (c) 1990, 1993 |
3 | * The Regents of the University of California. All rights reserved. | |
fb5357d5 MO |
4 | * |
5 | * This code is derived from software contributed to Berkeley by | |
6 | * Mike Olson. | |
7 | * | |
ad787160 C |
8 | * Redistribution and use in source and binary forms, with or without |
9 | * modification, are permitted provided that the following conditions | |
10 | * are met: | |
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. | |
23 | * | |
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 | |
34 | * SUCH DAMAGE. | |
fb5357d5 MO |
35 | */ |
36 | ||
37 | #if defined(LIBC_SCCS) && !defined(lint) | |
ad787160 | 38 | static char sccsid[] = "@(#)bt_utils.c 8.1 (Berkeley) 6/4/93"; |
fb5357d5 MO |
39 | #endif /* LIBC_SCCS and not lint */ |
40 | ||
91b5c9e5 | 41 | #include <sys/param.h> |
9f252354 | 42 | |
91b5c9e5 | 43 | #include <stdio.h> |
fb91cf55 KB |
44 | #include <stdlib.h> |
45 | #include <string.h> | |
9f252354 | 46 | |
94ac72c5 | 47 | #include <db.h> |
fb5357d5 MO |
48 | #include "btree.h" |
49 | ||
50 | /* | |
91b5c9e5 | 51 | * __BT_RET -- Build return key/data pair as a result of search or scan. |
fb5357d5 | 52 | * |
91b5c9e5 KB |
53 | * Parameters: |
54 | * t: tree | |
55 | * d: LEAF to be returned to the user. | |
05890675 | 56 | * key: user's key structure (NULL if not to be filled in) |
91b5c9e5 | 57 | * data: user's data structure |
fb5357d5 | 58 | * |
91b5c9e5 KB |
59 | * Returns: |
60 | * RET_SUCCESS, RET_ERROR. | |
fb5357d5 | 61 | */ |
fb5357d5 | 62 | int |
91b5c9e5 KB |
63 | __bt_ret(t, e, key, data) |
64 | BTREE *t; | |
65 | EPG *e; | |
66 | DBT *key, *data; | |
fb5357d5 | 67 | { |
91b5c9e5 | 68 | register BLEAF *bl; |
05890675 | 69 | register void *p; |
fb5357d5 | 70 | |
91b5c9e5 KB |
71 | bl = GETBLEAF(e->page, e->index); |
72 | ||
91b5c9e5 KB |
73 | if (bl->flags & P_BIGDATA) { |
74 | if (__ovfl_get(t, bl->bytes + bl->ksize, | |
75 | &data->size, &t->bt_dbuf, &t->bt_dbufsz)) | |
fb5357d5 | 76 | return (RET_ERROR); |
fb5357d5 | 77 | } else { |
aac068a2 KB |
78 | /* Use +1 in case the first record retrieved is 0 length. */ |
79 | if (bl->dsize + 1 > t->bt_dbufsz) { | |
80 | if ((p = realloc(t->bt_dbuf, bl->dsize + 1)) == NULL) | |
fb5357d5 | 81 | return (RET_ERROR); |
05890675 | 82 | t->bt_dbuf = p; |
aac068a2 | 83 | t->bt_dbufsz = bl->dsize + 1; |
fb5357d5 | 84 | } |
1911b5bf | 85 | memmove(t->bt_dbuf, bl->bytes + bl->ksize, bl->dsize); |
91b5c9e5 | 86 | data->size = bl->dsize; |
fb5357d5 | 87 | } |
91b5c9e5 | 88 | data->data = t->bt_dbuf; |
fb5357d5 | 89 | |
05890675 KB |
90 | if (key == NULL) |
91 | return (RET_SUCCESS); | |
92 | ||
93 | if (bl->flags & P_BIGKEY) { | |
94 | if (__ovfl_get(t, bl->bytes, | |
95 | &key->size, &t->bt_kbuf, &t->bt_kbufsz)) | |
96 | return (RET_ERROR); | |
97 | } else { | |
98 | if (bl->ksize > t->bt_kbufsz) { | |
99 | if ((p = realloc(t->bt_kbuf, bl->ksize)) == NULL) | |
100 | return (RET_ERROR); | |
101 | t->bt_kbuf = p; | |
102 | t->bt_kbufsz = bl->ksize; | |
103 | } | |
1911b5bf | 104 | memmove(t->bt_kbuf, bl->bytes, bl->ksize); |
05890675 KB |
105 | key->size = bl->ksize; |
106 | } | |
107 | key->data = t->bt_kbuf; | |
fb5357d5 MO |
108 | return (RET_SUCCESS); |
109 | } | |
110 | ||
111 | /* | |
91b5c9e5 | 112 | * __BT_CMP -- Compare a key to a given record. |
fb5357d5 | 113 | * |
91b5c9e5 KB |
114 | * Parameters: |
115 | * t: tree | |
116 | * k1: DBT pointer of first arg to comparison | |
117 | * e: pointer to EPG for comparison | |
fb5357d5 | 118 | * |
91b5c9e5 KB |
119 | * Returns: |
120 | * < 0 if k1 is < record | |
121 | * = 0 if k1 is = record | |
122 | * > 0 if k1 is > record | |
fb5357d5 | 123 | */ |
fb5357d5 | 124 | int |
91b5c9e5 KB |
125 | __bt_cmp(t, k1, e) |
126 | BTREE *t; | |
127 | const DBT *k1; | |
128 | EPG *e; | |
fb5357d5 | 129 | { |
91b5c9e5 KB |
130 | BINTERNAL *bi; |
131 | BLEAF *bl; | |
132 | DBT k2; | |
133 | PAGE *h; | |
134 | void *bigkey; | |
fb5357d5 MO |
135 | |
136 | /* | |
91b5c9e5 KB |
137 | * The left-most key on internal pages, at any level of the tree, is |
138 | * guaranteed by the following code to be less than any user key. | |
139 | * This saves us from having to update the leftmost key on an internal | |
140 | * page when the user inserts a new key in the tree smaller than | |
141 | * anything we've yet seen. | |
fb5357d5 | 142 | */ |
91b5c9e5 KB |
143 | h = e->page; |
144 | if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF)) | |
fb5357d5 MO |
145 | return (1); |
146 | ||
91b5c9e5 KB |
147 | bigkey = NULL; |
148 | if (h->flags & P_BLEAF) { | |
149 | bl = GETBLEAF(h, e->index); | |
150 | if (bl->flags & P_BIGKEY) | |
151 | bigkey = bl->bytes; | |
152 | else { | |
153 | k2.data = bl->bytes; | |
154 | k2.size = bl->ksize; | |
fb5357d5 MO |
155 | } |
156 | } else { | |
91b5c9e5 KB |
157 | bi = GETBINTERNAL(h, e->index); |
158 | if (bi->flags & P_BIGKEY) | |
159 | bigkey = bi->bytes; | |
160 | else { | |
161 | k2.data = bi->bytes; | |
162 | k2.size = bi->ksize; | |
fb5357d5 MO |
163 | } |
164 | } | |
fb5357d5 | 165 | |
91b5c9e5 KB |
166 | if (bigkey) { |
167 | if (__ovfl_get(t, bigkey, | |
168 | &k2.size, &t->bt_dbuf, &t->bt_dbufsz)) | |
169 | return (RET_ERROR); | |
170 | k2.data = t->bt_dbuf; | |
171 | } | |
aaf5ecfa | 172 | return ((*t->bt_cmp)(k1, &k2)); |
fb5357d5 MO |
173 | } |
174 | ||
175 | /* | |
91b5c9e5 | 176 | * __BT_DEFCMP -- Default comparison routine. |
fb5357d5 | 177 | * |
91b5c9e5 KB |
178 | * Parameters: |
179 | * a: DBT #1 | |
180 | * b: DBT #2 | |
fb5357d5 | 181 | * |
91b5c9e5 KB |
182 | * Returns: |
183 | * < 0 if a is < b | |
184 | * = 0 if a is = b | |
185 | * > 0 if a is > b | |
fb5357d5 | 186 | */ |
fb5357d5 | 187 | int |
91b5c9e5 KB |
188 | __bt_defcmp(a, b) |
189 | const DBT *a, *b; | |
fb5357d5 | 190 | { |
91b5c9e5 KB |
191 | register u_char *p1, *p2; |
192 | register int diff, len; | |
193 | ||
194 | len = MIN(a->size, b->size); | |
195 | for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2) | |
196 | if (diff = *p1 - *p2) | |
aaf5ecfa KB |
197 | return (diff); |
198 | return (a->size - b->size); | |
fb5357d5 | 199 | } |
fb5357d5 | 200 | |
91b5c9e5 KB |
201 | /* |
202 | * __BT_DEFPFX -- Default prefix routine. | |
203 | * | |
204 | * Parameters: | |
205 | * a: DBT #1 | |
206 | * b: DBT #2 | |
207 | * | |
208 | * Returns: | |
209 | * Number of bytes needed to distinguish b from a. | |
210 | */ | |
211 | int | |
212 | __bt_defpfx(a, b) | |
213 | const DBT *a, *b; | |
fb5357d5 | 214 | { |
91b5c9e5 KB |
215 | register u_char *p1, *p2; |
216 | register int len; | |
217 | int cnt; | |
218 | ||
219 | cnt = 1; | |
220 | len = MIN(a->size, b->size); | |
221 | for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt) | |
222 | if (*p1 != *p2) | |
aaf5ecfa | 223 | return (cnt); |
05890675 KB |
224 | |
225 | /* a->size must be <= b->size, or they wouldn't be in this order. */ | |
226 | return (a->size < b->size ? a->size + 1 : a->size); | |
fb5357d5 | 227 | } |