1 /*-
2 * Copyright (c) 1990, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Mike Olson.
7 *
8 * %sccs.include.redist.c%
9 */
10
11 #if defined(LIBC_SCCS) && !defined(lint)
12 static char sccsid[] = "@(#)bt_utils.c 8.4 (Berkeley) 02/21/94";
13 #endif /* LIBC_SCCS and not lint */
14
15 #include <sys/param.h>
16
17 #include <stdio.h>
18 #include <stdlib.h>
19 #include <string.h>
20
21 #include <db.h>
22 #include "btree.h"
23
24 /*
25 * __BT_RET -- Build return key/data pair as a result of search or scan.
26 *
27 * Parameters:
28 * t: tree
29 * d: LEAF to be returned to the user.
30 * key: user's key structure (NULL if not to be filled in)
31 * data: user's data structure
32 *
33 * Returns:
34 * RET_SUCCESS, RET_ERROR.
35 */
36 int
__bt_ret(t,e,key,data)37 __bt_ret(t, e, key, data)
38 BTREE *t;
39 EPG *e;
40 DBT *key, *data;
41 {
42 register BLEAF *bl;
43 register void *p;
44
45 bl = GETBLEAF(e->page, e->index);
46
47 /*
48 * We always copy big keys/data to make them contigous. Otherwise,
49 * we leave the page pinned and don't copy unless the user specified
50 * concurrent access.
51 */
52 if (bl->flags & P_BIGDATA) {
53 if (__ovfl_get(t, bl->bytes + bl->ksize,
54 &data->size, &t->bt_dbuf, &t->bt_dbufsz))
55 return (RET_ERROR);
56 data->data = t->bt_dbuf;
57 } else if (ISSET(t, B_DB_LOCK)) {
58 /* Use +1 in case the first record retrieved is 0 length. */
59 if (bl->dsize + 1 > t->bt_dbufsz) {
60 if ((p =
61 (void *)realloc(t->bt_dbuf, bl->dsize + 1)) == NULL)
62 return (RET_ERROR);
63 t->bt_dbuf = p;
64 t->bt_dbufsz = bl->dsize + 1;
65 }
66 memmove(t->bt_dbuf, bl->bytes + bl->ksize, bl->dsize);
67 data->size = bl->dsize;
68 data->data = t->bt_dbuf;
69 } else {
70 data->size = bl->dsize;
71 data->data = bl->bytes + bl->ksize;
72 }
73
74 if (key == NULL)
75 return (RET_SUCCESS);
76
77 if (bl->flags & P_BIGKEY) {
78 if (__ovfl_get(t, bl->bytes,
79 &key->size, &t->bt_kbuf, &t->bt_kbufsz))
80 return (RET_ERROR);
81 key->data = t->bt_kbuf;
82 } else if (ISSET(t, B_DB_LOCK)) {
83 if (bl->ksize > t->bt_kbufsz) {
84 if ((p =
85 (void *)realloc(t->bt_kbuf, bl->ksize)) == NULL)
86 return (RET_ERROR);
87 t->bt_kbuf = p;
88 t->bt_kbufsz = bl->ksize;
89 }
90 memmove(t->bt_kbuf, bl->bytes, bl->ksize);
91 key->size = bl->ksize;
92 key->data = t->bt_kbuf;
93 } else {
94 key->size = bl->ksize;
95 key->data = bl->bytes;
96 }
97 return (RET_SUCCESS);
98 }
99
100 /*
101 * __BT_CMP -- Compare a key to a given record.
102 *
103 * Parameters:
104 * t: tree
105 * k1: DBT pointer of first arg to comparison
106 * e: pointer to EPG for comparison
107 *
108 * Returns:
109 * < 0 if k1 is < record
110 * = 0 if k1 is = record
111 * > 0 if k1 is > record
112 */
113 int
__bt_cmp(t,k1,e)114 __bt_cmp(t, k1, e)
115 BTREE *t;
116 const DBT *k1;
117 EPG *e;
118 {
119 BINTERNAL *bi;
120 BLEAF *bl;
121 DBT k2;
122 PAGE *h;
123 void *bigkey;
124
125 /*
126 * The left-most key on internal pages, at any level of the tree, is
127 * guaranteed by the following code to be less than any user key.
128 * This saves us from having to update the leftmost key on an internal
129 * page when the user inserts a new key in the tree smaller than
130 * anything we've yet seen.
131 */
132 h = e->page;
133 if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF))
134 return (1);
135
136 bigkey = NULL;
137 if (h->flags & P_BLEAF) {
138 bl = GETBLEAF(h, e->index);
139 if (bl->flags & P_BIGKEY)
140 bigkey = bl->bytes;
141 else {
142 k2.data = bl->bytes;
143 k2.size = bl->ksize;
144 }
145 } else {
146 bi = GETBINTERNAL(h, e->index);
147 if (bi->flags & P_BIGKEY)
148 bigkey = bi->bytes;
149 else {
150 k2.data = bi->bytes;
151 k2.size = bi->ksize;
152 }
153 }
154
155 if (bigkey) {
156 if (__ovfl_get(t, bigkey,
157 &k2.size, &t->bt_dbuf, &t->bt_dbufsz))
158 return (RET_ERROR);
159 k2.data = t->bt_dbuf;
160 }
161 return ((*t->bt_cmp)(k1, &k2));
162 }
163
164 /*
165 * __BT_DEFCMP -- Default comparison routine.
166 *
167 * Parameters:
168 * a: DBT #1
169 * b: DBT #2
170 *
171 * Returns:
172 * < 0 if a is < b
173 * = 0 if a is = b
174 * > 0 if a is > b
175 */
176 int
__bt_defcmp(a,b)177 __bt_defcmp(a, b)
178 const DBT *a, *b;
179 {
180 register size_t len;
181 register u_char *p1, *p2;
182
183 /*
184 * XXX
185 * If a size_t doesn't fit in an int, this routine can lose.
186 * What we need is a integral type which is guaranteed to be
187 * larger than a size_t, and there is no such thing.
188 */
189 len = MIN(a->size, b->size);
190 for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2)
191 if (*p1 != *p2)
192 return ((int)*p1 - (int)*p2);
193 return ((int)a->size - (int)b->size);
194 }
195
196 /*
197 * __BT_DEFPFX -- Default prefix routine.
198 *
199 * Parameters:
200 * a: DBT #1
201 * b: DBT #2
202 *
203 * Returns:
204 * Number of bytes needed to distinguish b from a.
205 */
206 size_t
__bt_defpfx(a,b)207 __bt_defpfx(a, b)
208 const DBT *a, *b;
209 {
210 register u_char *p1, *p2;
211 register size_t cnt, len;
212
213 cnt = 1;
214 len = MIN(a->size, b->size);
215 for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
216 if (*p1 != *p2)
217 return (cnt);
218
219 /* a->size must be <= b->size, or they wouldn't be in this order. */
220 return (a->size < b->size ? a->size + 1 : a->size);
221 }
222