17c478bd9Sstevel@tonic-gate /*-
27c478bd9Sstevel@tonic-gate * Copyright (c) 1990, 1993, 1994
37c478bd9Sstevel@tonic-gate * The Regents of the University of California. All rights reserved.
47c478bd9Sstevel@tonic-gate *
57c478bd9Sstevel@tonic-gate * This code is derived from software contributed to Berkeley by
67c478bd9Sstevel@tonic-gate * Mike Olson.
77c478bd9Sstevel@tonic-gate *
87c478bd9Sstevel@tonic-gate * Redistribution and use in source and binary forms, with or without
97c478bd9Sstevel@tonic-gate * modification, are permitted provided that the following conditions
107c478bd9Sstevel@tonic-gate * are met:
117c478bd9Sstevel@tonic-gate * 1. Redistributions of source code must retain the above copyright
127c478bd9Sstevel@tonic-gate * notice, this list of conditions and the following disclaimer.
137c478bd9Sstevel@tonic-gate * 2. Redistributions in binary form must reproduce the above copyright
147c478bd9Sstevel@tonic-gate * notice, this list of conditions and the following disclaimer in the
157c478bd9Sstevel@tonic-gate * documentation and/or other materials provided with the distribution.
167c478bd9Sstevel@tonic-gate * 3. All advertising materials mentioning features or use of this software
177c478bd9Sstevel@tonic-gate * must display the following acknowledgement:
187c478bd9Sstevel@tonic-gate * This product includes software developed by the University of
197c478bd9Sstevel@tonic-gate * California, Berkeley and its contributors.
207c478bd9Sstevel@tonic-gate * 4. Neither the name of the University nor the names of its contributors
217c478bd9Sstevel@tonic-gate * may be used to endorse or promote products derived from this software
227c478bd9Sstevel@tonic-gate * without specific prior written permission.
237c478bd9Sstevel@tonic-gate *
247c478bd9Sstevel@tonic-gate * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
257c478bd9Sstevel@tonic-gate * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
267c478bd9Sstevel@tonic-gate * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
277c478bd9Sstevel@tonic-gate * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
287c478bd9Sstevel@tonic-gate * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
297c478bd9Sstevel@tonic-gate * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
307c478bd9Sstevel@tonic-gate * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
317c478bd9Sstevel@tonic-gate * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
327c478bd9Sstevel@tonic-gate * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
337c478bd9Sstevel@tonic-gate * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
347c478bd9Sstevel@tonic-gate * SUCH DAMAGE.
357c478bd9Sstevel@tonic-gate */
367c478bd9Sstevel@tonic-gate
377c478bd9Sstevel@tonic-gate #if defined(LIBC_SCCS) && !defined(lint)
387c478bd9Sstevel@tonic-gate static char sccsid[] = "@(#)bt_utils.c 8.8 (Berkeley) 7/20/94";
397c478bd9Sstevel@tonic-gate #endif /* LIBC_SCCS and not lint */
407c478bd9Sstevel@tonic-gate
417c478bd9Sstevel@tonic-gate #include <sys/param.h>
427c478bd9Sstevel@tonic-gate
437c478bd9Sstevel@tonic-gate #include <stdio.h>
447c478bd9Sstevel@tonic-gate #include <stdlib.h>
457c478bd9Sstevel@tonic-gate #include <string.h>
467c478bd9Sstevel@tonic-gate
477c478bd9Sstevel@tonic-gate #include "db-int.h"
487c478bd9Sstevel@tonic-gate #include "btree.h"
497c478bd9Sstevel@tonic-gate
507c478bd9Sstevel@tonic-gate /*
517c478bd9Sstevel@tonic-gate * __bt_ret --
527c478bd9Sstevel@tonic-gate * Build return key/data pair.
537c478bd9Sstevel@tonic-gate *
547c478bd9Sstevel@tonic-gate * Parameters:
557c478bd9Sstevel@tonic-gate * t: tree
567c478bd9Sstevel@tonic-gate * e: key/data pair to be returned
577c478bd9Sstevel@tonic-gate * key: user's key structure (NULL if not to be filled in)
587c478bd9Sstevel@tonic-gate * rkey: memory area to hold key
597c478bd9Sstevel@tonic-gate * data: user's data structure (NULL if not to be filled in)
607c478bd9Sstevel@tonic-gate * rdata: memory area to hold data
617c478bd9Sstevel@tonic-gate * copy: always copy the key/data item
627c478bd9Sstevel@tonic-gate *
637c478bd9Sstevel@tonic-gate * Returns:
647c478bd9Sstevel@tonic-gate * RET_SUCCESS, RET_ERROR.
657c478bd9Sstevel@tonic-gate */
667c478bd9Sstevel@tonic-gate int
__bt_ret(t,e,key,rkey,data,rdata,copy)677c478bd9Sstevel@tonic-gate __bt_ret(t, e, key, rkey, data, rdata, copy)
687c478bd9Sstevel@tonic-gate BTREE *t;
697c478bd9Sstevel@tonic-gate EPG *e;
707c478bd9Sstevel@tonic-gate DBT *key, *rkey, *data, *rdata;
717c478bd9Sstevel@tonic-gate int copy;
727c478bd9Sstevel@tonic-gate {
737c478bd9Sstevel@tonic-gate BLEAF *bl;
747c478bd9Sstevel@tonic-gate void *p;
757c478bd9Sstevel@tonic-gate
767c478bd9Sstevel@tonic-gate bl = GETBLEAF(e->page, e->index);
777c478bd9Sstevel@tonic-gate
787c478bd9Sstevel@tonic-gate /*
797c478bd9Sstevel@tonic-gate * We must copy big keys/data to make them contigous. Otherwise,
807c478bd9Sstevel@tonic-gate * leave the page pinned and don't copy unless the user specified
817c478bd9Sstevel@tonic-gate * concurrent access.
827c478bd9Sstevel@tonic-gate */
837c478bd9Sstevel@tonic-gate if (key == NULL)
847c478bd9Sstevel@tonic-gate goto dataonly;
857c478bd9Sstevel@tonic-gate
867c478bd9Sstevel@tonic-gate if (bl->flags & P_BIGKEY) {
877c478bd9Sstevel@tonic-gate if (__ovfl_get(t, bl->bytes,
887c478bd9Sstevel@tonic-gate &key->size, &rkey->data, &rkey->size))
897c478bd9Sstevel@tonic-gate return (RET_ERROR);
907c478bd9Sstevel@tonic-gate key->data = rkey->data;
917c478bd9Sstevel@tonic-gate } else if (copy || F_ISSET(t, B_DB_LOCK)) {
927c478bd9Sstevel@tonic-gate if (bl->ksize > rkey->size) {
937c478bd9Sstevel@tonic-gate p = (void *)(rkey->data == NULL ?
947c478bd9Sstevel@tonic-gate malloc(bl->ksize) : realloc(rkey->data, bl->ksize));
957c478bd9Sstevel@tonic-gate if (p == NULL)
967c478bd9Sstevel@tonic-gate return (RET_ERROR);
977c478bd9Sstevel@tonic-gate rkey->data = p;
987c478bd9Sstevel@tonic-gate rkey->size = bl->ksize;
997c478bd9Sstevel@tonic-gate }
1007c478bd9Sstevel@tonic-gate memmove(rkey->data, bl->bytes, bl->ksize);
1017c478bd9Sstevel@tonic-gate key->size = bl->ksize;
1027c478bd9Sstevel@tonic-gate key->data = rkey->data;
1037c478bd9Sstevel@tonic-gate } else {
1047c478bd9Sstevel@tonic-gate key->size = bl->ksize;
1057c478bd9Sstevel@tonic-gate key->data = bl->bytes;
1067c478bd9Sstevel@tonic-gate }
1077c478bd9Sstevel@tonic-gate
1087c478bd9Sstevel@tonic-gate dataonly:
1097c478bd9Sstevel@tonic-gate if (data == NULL)
1107c478bd9Sstevel@tonic-gate return (RET_SUCCESS);
1117c478bd9Sstevel@tonic-gate
1127c478bd9Sstevel@tonic-gate if (bl->flags & P_BIGDATA) {
1137c478bd9Sstevel@tonic-gate if (__ovfl_get(t, bl->bytes + bl->ksize,
1147c478bd9Sstevel@tonic-gate &data->size, &rdata->data, &rdata->size))
1157c478bd9Sstevel@tonic-gate return (RET_ERROR);
1167c478bd9Sstevel@tonic-gate data->data = rdata->data;
1177c478bd9Sstevel@tonic-gate } else if (copy || F_ISSET(t, B_DB_LOCK)) {
1187c478bd9Sstevel@tonic-gate /* Use +1 in case the first record retrieved is 0 length. */
1197c478bd9Sstevel@tonic-gate if (bl->dsize + 1 > rdata->size) {
1207c478bd9Sstevel@tonic-gate p = (void *)(rdata->data == NULL ?
1217c478bd9Sstevel@tonic-gate malloc(bl->dsize + 1) :
1227c478bd9Sstevel@tonic-gate realloc(rdata->data, bl->dsize + 1));
1237c478bd9Sstevel@tonic-gate if (p == NULL)
1247c478bd9Sstevel@tonic-gate return (RET_ERROR);
1257c478bd9Sstevel@tonic-gate rdata->data = p;
1267c478bd9Sstevel@tonic-gate rdata->size = bl->dsize + 1;
1277c478bd9Sstevel@tonic-gate }
1287c478bd9Sstevel@tonic-gate memmove(rdata->data, bl->bytes + bl->ksize, bl->dsize);
1297c478bd9Sstevel@tonic-gate data->size = bl->dsize;
1307c478bd9Sstevel@tonic-gate data->data = rdata->data;
1317c478bd9Sstevel@tonic-gate } else {
1327c478bd9Sstevel@tonic-gate data->size = bl->dsize;
1337c478bd9Sstevel@tonic-gate data->data = bl->bytes + bl->ksize;
1347c478bd9Sstevel@tonic-gate }
1357c478bd9Sstevel@tonic-gate
1367c478bd9Sstevel@tonic-gate return (RET_SUCCESS);
1377c478bd9Sstevel@tonic-gate }
1387c478bd9Sstevel@tonic-gate
1397c478bd9Sstevel@tonic-gate /*
1407c478bd9Sstevel@tonic-gate * __BT_CMP -- Compare a key to a given record.
1417c478bd9Sstevel@tonic-gate *
1427c478bd9Sstevel@tonic-gate * Parameters:
1437c478bd9Sstevel@tonic-gate * t: tree
1447c478bd9Sstevel@tonic-gate * k1: DBT pointer of first arg to comparison
1457c478bd9Sstevel@tonic-gate * e: pointer to EPG for comparison
1467c478bd9Sstevel@tonic-gate *
1477c478bd9Sstevel@tonic-gate * Returns:
1487c478bd9Sstevel@tonic-gate * < 0 if k1 is < record
1497c478bd9Sstevel@tonic-gate * = 0 if k1 is = record
1507c478bd9Sstevel@tonic-gate * > 0 if k1 is > record
1517c478bd9Sstevel@tonic-gate */
1527c478bd9Sstevel@tonic-gate int
__bt_cmp(t,k1,e)1537c478bd9Sstevel@tonic-gate __bt_cmp(t, k1, e)
1547c478bd9Sstevel@tonic-gate BTREE *t;
1557c478bd9Sstevel@tonic-gate const DBT *k1;
1567c478bd9Sstevel@tonic-gate EPG *e;
1577c478bd9Sstevel@tonic-gate {
1587c478bd9Sstevel@tonic-gate BINTERNAL *bi;
1597c478bd9Sstevel@tonic-gate BLEAF *bl;
1607c478bd9Sstevel@tonic-gate DBT k2;
1617c478bd9Sstevel@tonic-gate PAGE *h;
1627c478bd9Sstevel@tonic-gate void *bigkey;
1637c478bd9Sstevel@tonic-gate
1647c478bd9Sstevel@tonic-gate /*
1657c478bd9Sstevel@tonic-gate * The left-most key on internal pages, at any level of the tree, is
1667c478bd9Sstevel@tonic-gate * guaranteed by the following code to be less than any user key.
1677c478bd9Sstevel@tonic-gate * This saves us from having to update the leftmost key on an internal
1687c478bd9Sstevel@tonic-gate * page when the user inserts a new key in the tree smaller than
1697c478bd9Sstevel@tonic-gate * anything we've yet seen.
1707c478bd9Sstevel@tonic-gate */
1717c478bd9Sstevel@tonic-gate h = e->page;
1727c478bd9Sstevel@tonic-gate if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF))
1737c478bd9Sstevel@tonic-gate return (1);
1747c478bd9Sstevel@tonic-gate
1757c478bd9Sstevel@tonic-gate bigkey = NULL;
1767c478bd9Sstevel@tonic-gate if (h->flags & P_BLEAF) {
1777c478bd9Sstevel@tonic-gate bl = GETBLEAF(h, e->index);
1787c478bd9Sstevel@tonic-gate if (bl->flags & P_BIGKEY)
1797c478bd9Sstevel@tonic-gate bigkey = bl->bytes;
1807c478bd9Sstevel@tonic-gate else {
1817c478bd9Sstevel@tonic-gate k2.data = bl->bytes;
1827c478bd9Sstevel@tonic-gate k2.size = bl->ksize;
1837c478bd9Sstevel@tonic-gate }
1847c478bd9Sstevel@tonic-gate } else {
1857c478bd9Sstevel@tonic-gate bi = GETBINTERNAL(h, e->index);
1867c478bd9Sstevel@tonic-gate if (bi->flags & P_BIGKEY)
1877c478bd9Sstevel@tonic-gate bigkey = bi->bytes;
1887c478bd9Sstevel@tonic-gate else {
1897c478bd9Sstevel@tonic-gate k2.data = bi->bytes;
1907c478bd9Sstevel@tonic-gate k2.size = bi->ksize;
1917c478bd9Sstevel@tonic-gate }
1927c478bd9Sstevel@tonic-gate }
1937c478bd9Sstevel@tonic-gate
1947c478bd9Sstevel@tonic-gate if (bigkey) {
1957c478bd9Sstevel@tonic-gate if (__ovfl_get(t, bigkey,
1967c478bd9Sstevel@tonic-gate &k2.size, &t->bt_rdata.data, &t->bt_rdata.size))
1977c478bd9Sstevel@tonic-gate return (RET_ERROR);
1987c478bd9Sstevel@tonic-gate k2.data = t->bt_rdata.data;
1997c478bd9Sstevel@tonic-gate }
2007c478bd9Sstevel@tonic-gate return ((*t->bt_cmp)(k1, &k2));
2017c478bd9Sstevel@tonic-gate }
2027c478bd9Sstevel@tonic-gate
2037c478bd9Sstevel@tonic-gate /*
2047c478bd9Sstevel@tonic-gate * __BT_DEFCMP -- Default comparison routine.
2057c478bd9Sstevel@tonic-gate *
2067c478bd9Sstevel@tonic-gate * Parameters:
2077c478bd9Sstevel@tonic-gate * a: DBT #1
2087c478bd9Sstevel@tonic-gate * b: DBT #2
2097c478bd9Sstevel@tonic-gate *
2107c478bd9Sstevel@tonic-gate * Returns:
2117c478bd9Sstevel@tonic-gate * < 0 if a is < b
2127c478bd9Sstevel@tonic-gate * = 0 if a is = b
2137c478bd9Sstevel@tonic-gate * > 0 if a is > b
2147c478bd9Sstevel@tonic-gate */
2157c478bd9Sstevel@tonic-gate int
__bt_defcmp(a,b)2167c478bd9Sstevel@tonic-gate __bt_defcmp(a, b)
2177c478bd9Sstevel@tonic-gate const DBT *a, *b;
2187c478bd9Sstevel@tonic-gate {
2197c478bd9Sstevel@tonic-gate register size_t len;
2207c478bd9Sstevel@tonic-gate register u_char *p1, *p2;
2217c478bd9Sstevel@tonic-gate
2227c478bd9Sstevel@tonic-gate /*
2237c478bd9Sstevel@tonic-gate * XXX
2247c478bd9Sstevel@tonic-gate * If a size_t doesn't fit in an int, this routine can lose.
2257c478bd9Sstevel@tonic-gate * What we need is a integral type which is guaranteed to be
2267c478bd9Sstevel@tonic-gate * larger than a size_t, and there is no such thing.
2277c478bd9Sstevel@tonic-gate */
2287c478bd9Sstevel@tonic-gate len = MIN(a->size, b->size);
2297c478bd9Sstevel@tonic-gate for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2)
2307c478bd9Sstevel@tonic-gate if (*p1 != *p2)
2317c478bd9Sstevel@tonic-gate return ((int)*p1 - (int)*p2);
2327c478bd9Sstevel@tonic-gate return ((int)a->size - (int)b->size);
2337c478bd9Sstevel@tonic-gate }
2347c478bd9Sstevel@tonic-gate
2357c478bd9Sstevel@tonic-gate /*
2367c478bd9Sstevel@tonic-gate * __BT_DEFPFX -- Default prefix routine.
2377c478bd9Sstevel@tonic-gate *
2387c478bd9Sstevel@tonic-gate * Parameters:
2397c478bd9Sstevel@tonic-gate * a: DBT #1
2407c478bd9Sstevel@tonic-gate * b: DBT #2
2417c478bd9Sstevel@tonic-gate *
2427c478bd9Sstevel@tonic-gate * Returns:
2437c478bd9Sstevel@tonic-gate * Number of bytes needed to distinguish b from a.
2447c478bd9Sstevel@tonic-gate */
2457c478bd9Sstevel@tonic-gate size_t
__bt_defpfx(a,b)2467c478bd9Sstevel@tonic-gate __bt_defpfx(a, b)
2477c478bd9Sstevel@tonic-gate const DBT *a, *b;
2487c478bd9Sstevel@tonic-gate {
2497c478bd9Sstevel@tonic-gate register u_char *p1, *p2;
2507c478bd9Sstevel@tonic-gate register size_t cnt, len;
2517c478bd9Sstevel@tonic-gate
2527c478bd9Sstevel@tonic-gate cnt = 1;
2537c478bd9Sstevel@tonic-gate len = MIN(a->size, b->size);
2547c478bd9Sstevel@tonic-gate for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
2557c478bd9Sstevel@tonic-gate if (*p1 != *p2)
2567c478bd9Sstevel@tonic-gate return (cnt);
2577c478bd9Sstevel@tonic-gate
2587c478bd9Sstevel@tonic-gate /* a->size must be <= b->size, or they wouldn't be in this order. */
2597c478bd9Sstevel@tonic-gate return (a->size < b->size ? a->size + 1 : a->size);
2607c478bd9Sstevel@tonic-gate }
261