Commit | Line | Data |
---|---|---|
fb5357d5 MO |
1 | /*- |
2 | * Copyright (c) 1990 The Regents of the University of California. | |
3 | * All rights reserved. | |
4 | * | |
5 | * This code is derived from software contributed to Berkeley by | |
6 | * Mike Olson. | |
7 | * | |
af359dea 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) | |
af359dea | 38 | static char sccsid[] = "@(#)utils.c 5.3 (Berkeley) 3/3/91"; |
fb5357d5 MO |
39 | #endif /* LIBC_SCCS and not lint */ |
40 | ||
41 | #include <sys/types.h> | |
42 | #include <db.h> | |
fb91cf55 KB |
43 | #include <stdlib.h> |
44 | #include <string.h> | |
fb5357d5 MO |
45 | #include "btree.h" |
46 | ||
47 | /* | |
48 | * _BT_BUILDRET -- Build return key/data pair as a result of search or scan. | |
49 | * | |
50 | * This routine manages the statically allocated buffers in which we | |
51 | * return data to the user. | |
52 | * | |
53 | * Parameters: | |
54 | * t -- btree from which to return datum | |
55 | * d -- DATUM to be returned to the user. | |
56 | * data -- data argument supplied by user for return | |
57 | * key -- key argument supplied by user for return | |
58 | * | |
59 | * Returns: | |
60 | * RET_SUCCESS, RET_ERROR. | |
61 | * | |
62 | * Side Effects: | |
63 | * May free and reallocate static buffers, if the data | |
64 | * we want to return is bigger than the space we have to | |
65 | * do so. | |
66 | */ | |
67 | ||
68 | int | |
69 | _bt_buildret(t, d, data, key) | |
70 | BTREE_P t; | |
71 | DATUM *d; | |
72 | DBT *data; | |
73 | DBT *key; | |
74 | { | |
75 | static int _data_s = 0; | |
76 | static int _key_s = 0; | |
77 | static char *_data = (char *) NULL; | |
78 | static char *_key = (char *) NULL; | |
79 | pgno_t chain; | |
80 | ||
81 | if (d->d_flags & D_BIGKEY) { | |
82 | if (_key != (char *) NULL) | |
83 | (void) free(_key); | |
84 | (void) bcopy((char *) &(d->d_bytes[0]), | |
85 | (char *) &chain, | |
86 | sizeof(chain)); | |
87 | if (_bt_getbig(t, chain, &_key, &_key_s) == RET_ERROR) | |
88 | return (RET_ERROR); | |
7d2840f6 | 89 | key->data = (u_char *)_key; |
fb5357d5 MO |
90 | key->size = _key_s; |
91 | } else { | |
92 | /* need more space for key? */ | |
93 | if (d->d_ksize > _key_s) { | |
94 | if (_key != (char *) NULL) | |
95 | (void) free (_key); | |
96 | if ((_key = (char *) malloc((unsigned) d->d_ksize)) | |
97 | == (char *) NULL) | |
98 | return (RET_ERROR); | |
99 | _key_s = d->d_ksize; | |
100 | } | |
101 | ||
7d2840f6 | 102 | key->data = (u_char *)_key; |
fb5357d5 MO |
103 | if ((key->size = d->d_ksize) > 0) |
104 | (void) bcopy(&(d->d_bytes[0]), | |
105 | _key, | |
106 | (int) d->d_ksize); | |
107 | } | |
108 | ||
109 | if (d->d_flags & D_BIGDATA) { | |
110 | if (_data != (char *) NULL) | |
111 | (void) free(_data); | |
112 | (void) bcopy(&(d->d_bytes[d->d_ksize]), | |
113 | (char *) &chain, | |
114 | sizeof(chain)); | |
115 | if (_bt_getbig(t, chain, &_data, &_data_s) == RET_ERROR) | |
116 | return (RET_ERROR); | |
7d2840f6 | 117 | data->data = (u_char *)_data; |
fb5357d5 MO |
118 | data->size = _data_s; |
119 | } else { | |
120 | /* need more space for data? */ | |
121 | if (d->d_dsize > _data_s) { | |
122 | if (_data != (char *) NULL) | |
123 | (void) free (_data); | |
124 | if ((_data = (char *) malloc((unsigned) d->d_dsize)) | |
125 | == (char *) NULL) | |
126 | return (RET_ERROR); | |
127 | _data_s = d->d_dsize; | |
128 | } | |
129 | ||
7d2840f6 | 130 | data->data = (u_char *)_data; |
fb5357d5 MO |
131 | |
132 | if ((data->size = d->d_dsize) > 0) | |
133 | (void) bcopy(&(d->d_bytes[d->d_ksize]), | |
134 | _data, | |
135 | (size_t) (d->d_dsize)); | |
136 | } | |
137 | ||
138 | return (RET_SUCCESS); | |
139 | } | |
140 | ||
141 | /* | |
142 | * _BT_CMP -- Compare a key to a given item on the current page. | |
143 | * | |
144 | * This routine is a wrapper for the user's comparison function. | |
145 | * | |
146 | * Parameters: | |
147 | * t -- tree in which to do comparison | |
148 | * p -- pointer to one argument for the comparison function | |
149 | * n -- index of item to supply second arg to comparison function | |
150 | * | |
151 | * Returns: | |
152 | * < 0 if p is < item at n | |
153 | * = 0 if p is = item at n | |
154 | * > 0 if p is > item at n | |
155 | */ | |
156 | ||
157 | int | |
158 | _bt_cmp(t, p, n) | |
159 | BTREE_P t; | |
160 | char *p; | |
161 | index_t n; | |
162 | { | |
163 | BTHEADER *h; | |
164 | IDATUM *id; | |
165 | DATUM *d; | |
166 | char *arg; | |
167 | int ignore; | |
168 | int free_arg; | |
169 | pgno_t chain; | |
170 | int r; | |
171 | ||
172 | h = t->bt_curpage; | |
173 | ||
174 | /* | |
175 | * The left-most key at any level of the tree on internal pages | |
176 | * is guaranteed (artificially, by the code here) to be less than | |
177 | * any user key. This saves us from having to update the leftmost | |
178 | * key when the user inserts a new key in the tree smaller than | |
179 | * anything we've seen yet. | |
180 | */ | |
181 | ||
182 | if (h->h_prevpg == P_NONE && !(h->h_flags & F_LEAF) && n == 0) | |
183 | return (1); | |
184 | ||
185 | if (h->h_flags & F_LEAF) { | |
186 | d = (DATUM *) GETDATUM(h,n); | |
187 | if (d->d_flags & D_BIGKEY) { | |
188 | free_arg = TRUE; | |
189 | bcopy(&(d->d_bytes[0]), (char *) &chain, sizeof(chain)); | |
190 | if (_bt_getbig(t, chain, &arg, &ignore) == RET_ERROR) | |
191 | return (RET_ERROR); | |
192 | } else { | |
193 | free_arg = FALSE; | |
194 | arg = &(d->d_bytes[0]); | |
195 | } | |
196 | } else { | |
197 | id = (IDATUM *) GETDATUM(h,n); | |
198 | if (id->i_flags & D_BIGKEY) { | |
199 | free_arg = TRUE; | |
200 | bcopy(&(id->i_bytes[0]), | |
201 | (char *) &chain, | |
202 | sizeof(chain)); | |
203 | if (_bt_getbig(t, chain, &arg, &ignore) == RET_ERROR) | |
204 | return (RET_ERROR); | |
205 | } else { | |
206 | free_arg = FALSE; | |
207 | arg = &(id->i_bytes[0]); | |
208 | } | |
209 | } | |
210 | r = (*(t->bt_compare))(p, arg); | |
211 | ||
212 | if (free_arg) | |
213 | (void) free(arg); | |
214 | ||
215 | return (r); | |
216 | } | |
217 | ||
218 | /* | |
219 | * _BT_PUSH/_BT_POP -- Push/pop a parent page number on the parent stack. | |
220 | * | |
221 | * When we descend the tree, we keep track of parent pages in order | |
222 | * to handle splits on insertions. | |
223 | * | |
224 | * Parameters: | |
225 | * t -- tree for which to push parent | |
226 | * pgno -- page number to push (_bt_push only) | |
227 | * | |
228 | * Returns: | |
229 | * RET_SUCCESS, RET_ERROR. | |
230 | */ | |
231 | ||
232 | int | |
233 | _bt_push(t, pgno) | |
234 | BTREE_P t; | |
235 | pgno_t pgno; | |
236 | { | |
237 | BTSTACK *new; | |
238 | ||
239 | if ((new = (BTSTACK *) malloc((unsigned) sizeof(BTSTACK))) | |
240 | == (BTSTACK *) NULL) | |
241 | return (RET_ERROR); | |
242 | new->bts_pgno = pgno; | |
243 | new->bts_next = t->bt_stack; | |
244 | t->bt_stack = new; | |
245 | ||
246 | return (RET_SUCCESS); | |
247 | } | |
248 | ||
249 | pgno_t | |
250 | _bt_pop(t) | |
251 | BTREE_P t; | |
252 | { | |
253 | BTSTACK *s; | |
254 | pgno_t p = P_NONE; | |
255 | ||
256 | if ((s = t->bt_stack) != (BTSTACK *) NULL) { | |
257 | p = s->bts_pgno; | |
258 | t->bt_stack = s->bts_next; | |
259 | (void) free ((char *) s); | |
260 | } | |
261 | return (p); | |
262 | } | |
263 | ||
264 | #ifdef DEBUG | |
265 | void | |
266 | _btdump(tree) | |
267 | BTREE tree; | |
268 | { | |
269 | BTREE_P t = (BTREE_P) tree; | |
270 | DATUM *d; | |
271 | IDATUM *id; | |
272 | BTHEADER *h; | |
273 | pgno_t npages; | |
274 | pgno_t i; | |
275 | index_t cur, top; | |
276 | ||
277 | npages = t->bt_npages; | |
278 | (void) printf("\"%s\" fd %d pgsz %d curpg %d @ 0x%lx", | |
279 | t->bt_fname, t->bt_s.bt_d.d_fd, | |
280 | t->bt_psize, t->bt_curpage); | |
281 | (void) printf("npg %d cmp 0x%lx flags=(", npages, t->bt_compare); | |
282 | if (t->bt_flags & BTF_SEQINIT) | |
283 | (void) printf("BTF_SEQINIT"); | |
284 | (void) printf(")\n"); | |
285 | ||
286 | for (i = P_ROOT; i <= npages; i++) { | |
287 | if (_bt_getpage(t, i) == RET_ERROR) | |
288 | _punt(); | |
289 | h = t->bt_curpage; | |
290 | top = NEXTINDEX(h); | |
291 | (void) printf(" page %d:\n", i); | |
292 | (void) printf("\tpgno %d prev %d next %d\n", | |
293 | h->h_pgno, h->h_prevpg, h->h_nextpg); | |
294 | (void) printf("\tlower %d upper %d nextind %d flags (", | |
295 | h->h_lower, h->h_upper, top); | |
296 | if (h->h_flags & F_LEAF) | |
297 | (void) printf("F_LEAF"); | |
298 | else | |
299 | (void) printf("<internal>"); | |
300 | if (h->h_flags & F_DIRTY) | |
301 | (void) printf("|F_DIRTY"); | |
302 | if (h->h_flags & F_PRESERVE) | |
303 | (void) printf("|F_PRESERVE"); | |
304 | if (h->h_flags & F_CONT) { | |
305 | (void) printf("|F_CONT)"); | |
306 | if (h->h_prevpg == P_NONE) { | |
307 | size_t longsz; | |
308 | (void) bcopy((char *) &(h->h_linp[0]), | |
309 | (char *) &longsz, | |
310 | sizeof(longsz)); | |
311 | printf("\n\t\t(chain start, data length %ld)", | |
312 | longsz); | |
313 | } | |
314 | printf("\n"); | |
315 | continue; | |
316 | } | |
317 | (void) printf(")\n"); | |
318 | for (cur = 0; cur < top; cur++) { | |
319 | (void) printf("\t [%d] off %d ", cur, h->h_linp[cur]); | |
320 | if (h->h_flags & F_LEAF) { | |
321 | d = (DATUM *) GETDATUM(h,cur); | |
322 | (void) printf("ksize %d", d->d_ksize); | |
323 | if (d->d_flags & D_BIGKEY) | |
324 | (void) printf(" (indirect)"); | |
325 | (void) printf("; dsize %d", d->d_dsize); | |
326 | if (d->d_flags & D_BIGDATA) | |
327 | (void) printf(" (indirect)"); | |
328 | } else { | |
329 | id = (IDATUM *) GETDATUM(h,cur); | |
330 | (void) printf("size %d pgno %d", | |
331 | id->i_size, id->i_pgno); | |
332 | if (id->i_flags & D_BIGKEY) | |
333 | (void) printf(" (indirect)"); | |
334 | } | |
335 | (void) printf("\n"); | |
336 | } | |
337 | (void) printf("\n"); | |
338 | } | |
339 | } | |
340 | #endif /* DEBUG */ | |
341 | ||
342 | #ifdef DEBUG | |
343 | _punt() | |
344 | { | |
345 | int pid; | |
346 | ||
347 | pid = getpid(); | |
348 | (void) kill(pid, SIGILL); | |
349 | } | |
350 | #endif /* DEBUG */ |