BSD 4_3_Net_2 release
[unix-history] / usr / src / lib / libc / db / btree / utils.c
CommitLineData
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 38static 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
68int
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
157int
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
232int
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
249pgno_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
265void
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 */