158f0484fSRodney W. Grimes /*- 258f0484fSRodney W. Grimes * Copyright (c) 1990, 1993 358f0484fSRodney W. Grimes * The Regents of the University of California. All rights reserved. 458f0484fSRodney W. Grimes * 558f0484fSRodney W. Grimes * This code is derived from software contributed to Berkeley by 658f0484fSRodney W. Grimes * Mike Olson. 758f0484fSRodney W. Grimes * 858f0484fSRodney W. Grimes * Redistribution and use in source and binary forms, with or without 958f0484fSRodney W. Grimes * modification, are permitted provided that the following conditions 1058f0484fSRodney W. Grimes * are met: 1158f0484fSRodney W. Grimes * 1. Redistributions of source code must retain the above copyright 1258f0484fSRodney W. Grimes * notice, this list of conditions and the following disclaimer. 1358f0484fSRodney W. Grimes * 2. Redistributions in binary form must reproduce the above copyright 1458f0484fSRodney W. Grimes * notice, this list of conditions and the following disclaimer in the 1558f0484fSRodney W. Grimes * documentation and/or other materials provided with the distribution. 1658f0484fSRodney W. Grimes * 3. All advertising materials mentioning features or use of this software 1758f0484fSRodney W. Grimes * must display the following acknowledgement: 1858f0484fSRodney W. Grimes * This product includes software developed by the University of 1958f0484fSRodney W. Grimes * California, Berkeley and its contributors. 2058f0484fSRodney W. Grimes * 4. Neither the name of the University nor the names of its contributors 2158f0484fSRodney W. Grimes * may be used to endorse or promote products derived from this software 2258f0484fSRodney W. Grimes * without specific prior written permission. 2358f0484fSRodney W. Grimes * 2458f0484fSRodney W. Grimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 2558f0484fSRodney W. Grimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2658f0484fSRodney W. Grimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2758f0484fSRodney W. Grimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 2858f0484fSRodney W. Grimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2958f0484fSRodney W. Grimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 3058f0484fSRodney W. Grimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 3158f0484fSRodney W. Grimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 3258f0484fSRodney W. Grimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 3358f0484fSRodney W. Grimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 3458f0484fSRodney W. Grimes * SUCH DAMAGE. 3558f0484fSRodney W. Grimes */ 3658f0484fSRodney W. Grimes 3758f0484fSRodney W. Grimes #if defined(LIBC_SCCS) && !defined(lint) 3858f0484fSRodney W. Grimes static char sccsid[] = "@(#)bt_utils.c 8.4 (Berkeley) 2/21/94"; 3958f0484fSRodney W. Grimes #endif /* LIBC_SCCS and not lint */ 4058f0484fSRodney W. Grimes 4158f0484fSRodney W. Grimes #include <sys/param.h> 4258f0484fSRodney W. Grimes 4358f0484fSRodney W. Grimes #include <stdio.h> 4458f0484fSRodney W. Grimes #include <stdlib.h> 4558f0484fSRodney W. Grimes #include <string.h> 4658f0484fSRodney W. Grimes 4758f0484fSRodney W. Grimes #include <db.h> 4858f0484fSRodney W. Grimes #include "btree.h" 4958f0484fSRodney W. Grimes 5058f0484fSRodney W. Grimes /* 5158f0484fSRodney W. Grimes * __BT_RET -- Build return key/data pair as a result of search or scan. 5258f0484fSRodney W. Grimes * 5358f0484fSRodney W. Grimes * Parameters: 5458f0484fSRodney W. Grimes * t: tree 5558f0484fSRodney W. Grimes * d: LEAF to be returned to the user. 5658f0484fSRodney W. Grimes * key: user's key structure (NULL if not to be filled in) 5758f0484fSRodney W. Grimes * data: user's data structure 5858f0484fSRodney W. Grimes * 5958f0484fSRodney W. Grimes * Returns: 6058f0484fSRodney W. Grimes * RET_SUCCESS, RET_ERROR. 6158f0484fSRodney W. Grimes */ 6258f0484fSRodney W. Grimes int 6358f0484fSRodney W. Grimes __bt_ret(t, e, key, data) 6458f0484fSRodney W. Grimes BTREE *t; 6558f0484fSRodney W. Grimes EPG *e; 6658f0484fSRodney W. Grimes DBT *key, *data; 6758f0484fSRodney W. Grimes { 6858f0484fSRodney W. Grimes register BLEAF *bl; 6958f0484fSRodney W. Grimes register void *p; 7058f0484fSRodney W. Grimes 7158f0484fSRodney W. Grimes bl = GETBLEAF(e->page, e->index); 7258f0484fSRodney W. Grimes 7358f0484fSRodney W. Grimes /* 7458f0484fSRodney W. Grimes * We always copy big keys/data to make them contigous. Otherwise, 7558f0484fSRodney W. Grimes * we leave the page pinned and don't copy unless the user specified 7658f0484fSRodney W. Grimes * concurrent access. 7758f0484fSRodney W. Grimes */ 7858f0484fSRodney W. Grimes if (bl->flags & P_BIGDATA) { 7958f0484fSRodney W. Grimes if (__ovfl_get(t, bl->bytes + bl->ksize, 8058f0484fSRodney W. Grimes &data->size, &t->bt_dbuf, &t->bt_dbufsz)) 8158f0484fSRodney W. Grimes return (RET_ERROR); 8258f0484fSRodney W. Grimes data->data = t->bt_dbuf; 8358f0484fSRodney W. Grimes } else if (ISSET(t, B_DB_LOCK)) { 8458f0484fSRodney W. Grimes /* Use +1 in case the first record retrieved is 0 length. */ 8558f0484fSRodney W. Grimes if (bl->dsize + 1 > t->bt_dbufsz) { 8658f0484fSRodney W. Grimes if ((p = 8758f0484fSRodney W. Grimes (void *)realloc(t->bt_dbuf, bl->dsize + 1)) == NULL) 8858f0484fSRodney W. Grimes return (RET_ERROR); 8958f0484fSRodney W. Grimes t->bt_dbuf = p; 9058f0484fSRodney W. Grimes t->bt_dbufsz = bl->dsize + 1; 9158f0484fSRodney W. Grimes } 9258f0484fSRodney W. Grimes memmove(t->bt_dbuf, bl->bytes + bl->ksize, bl->dsize); 9358f0484fSRodney W. Grimes data->size = bl->dsize; 9458f0484fSRodney W. Grimes data->data = t->bt_dbuf; 9558f0484fSRodney W. Grimes } else { 9658f0484fSRodney W. Grimes data->size = bl->dsize; 9758f0484fSRodney W. Grimes data->data = bl->bytes + bl->ksize; 9858f0484fSRodney W. Grimes } 9958f0484fSRodney W. Grimes 10058f0484fSRodney W. Grimes if (key == NULL) 10158f0484fSRodney W. Grimes return (RET_SUCCESS); 10258f0484fSRodney W. Grimes 10358f0484fSRodney W. Grimes if (bl->flags & P_BIGKEY) { 10458f0484fSRodney W. Grimes if (__ovfl_get(t, bl->bytes, 10558f0484fSRodney W. Grimes &key->size, &t->bt_kbuf, &t->bt_kbufsz)) 10658f0484fSRodney W. Grimes return (RET_ERROR); 10758f0484fSRodney W. Grimes key->data = t->bt_kbuf; 10858f0484fSRodney W. Grimes } else if (ISSET(t, B_DB_LOCK)) { 10958f0484fSRodney W. Grimes if (bl->ksize > t->bt_kbufsz) { 11058f0484fSRodney W. Grimes if ((p = 11158f0484fSRodney W. Grimes (void *)realloc(t->bt_kbuf, bl->ksize)) == NULL) 11258f0484fSRodney W. Grimes return (RET_ERROR); 11358f0484fSRodney W. Grimes t->bt_kbuf = p; 11458f0484fSRodney W. Grimes t->bt_kbufsz = bl->ksize; 11558f0484fSRodney W. Grimes } 11658f0484fSRodney W. Grimes memmove(t->bt_kbuf, bl->bytes, bl->ksize); 11758f0484fSRodney W. Grimes key->size = bl->ksize; 11858f0484fSRodney W. Grimes key->data = t->bt_kbuf; 11958f0484fSRodney W. Grimes } else { 12058f0484fSRodney W. Grimes key->size = bl->ksize; 12158f0484fSRodney W. Grimes key->data = bl->bytes; 12258f0484fSRodney W. Grimes } 12358f0484fSRodney W. Grimes return (RET_SUCCESS); 12458f0484fSRodney W. Grimes } 12558f0484fSRodney W. Grimes 12658f0484fSRodney W. Grimes /* 12758f0484fSRodney W. Grimes * __BT_CMP -- Compare a key to a given record. 12858f0484fSRodney W. Grimes * 12958f0484fSRodney W. Grimes * Parameters: 13058f0484fSRodney W. Grimes * t: tree 13158f0484fSRodney W. Grimes * k1: DBT pointer of first arg to comparison 13258f0484fSRodney W. Grimes * e: pointer to EPG for comparison 13358f0484fSRodney W. Grimes * 13458f0484fSRodney W. Grimes * Returns: 13558f0484fSRodney W. Grimes * < 0 if k1 is < record 13658f0484fSRodney W. Grimes * = 0 if k1 is = record 13758f0484fSRodney W. Grimes * > 0 if k1 is > record 13858f0484fSRodney W. Grimes */ 13958f0484fSRodney W. Grimes int 14058f0484fSRodney W. Grimes __bt_cmp(t, k1, e) 14158f0484fSRodney W. Grimes BTREE *t; 14258f0484fSRodney W. Grimes const DBT *k1; 14358f0484fSRodney W. Grimes EPG *e; 14458f0484fSRodney W. Grimes { 14558f0484fSRodney W. Grimes BINTERNAL *bi; 14658f0484fSRodney W. Grimes BLEAF *bl; 14758f0484fSRodney W. Grimes DBT k2; 14858f0484fSRodney W. Grimes PAGE *h; 14958f0484fSRodney W. Grimes void *bigkey; 15058f0484fSRodney W. Grimes 15158f0484fSRodney W. Grimes /* 15258f0484fSRodney W. Grimes * The left-most key on internal pages, at any level of the tree, is 15358f0484fSRodney W. Grimes * guaranteed by the following code to be less than any user key. 15458f0484fSRodney W. Grimes * This saves us from having to update the leftmost key on an internal 15558f0484fSRodney W. Grimes * page when the user inserts a new key in the tree smaller than 15658f0484fSRodney W. Grimes * anything we've yet seen. 15758f0484fSRodney W. Grimes */ 15858f0484fSRodney W. Grimes h = e->page; 15958f0484fSRodney W. Grimes if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF)) 16058f0484fSRodney W. Grimes return (1); 16158f0484fSRodney W. Grimes 16258f0484fSRodney W. Grimes bigkey = NULL; 16358f0484fSRodney W. Grimes if (h->flags & P_BLEAF) { 16458f0484fSRodney W. Grimes bl = GETBLEAF(h, e->index); 16558f0484fSRodney W. Grimes if (bl->flags & P_BIGKEY) 16658f0484fSRodney W. Grimes bigkey = bl->bytes; 16758f0484fSRodney W. Grimes else { 16858f0484fSRodney W. Grimes k2.data = bl->bytes; 16958f0484fSRodney W. Grimes k2.size = bl->ksize; 17058f0484fSRodney W. Grimes } 17158f0484fSRodney W. Grimes } else { 17258f0484fSRodney W. Grimes bi = GETBINTERNAL(h, e->index); 17358f0484fSRodney W. Grimes if (bi->flags & P_BIGKEY) 17458f0484fSRodney W. Grimes bigkey = bi->bytes; 17558f0484fSRodney W. Grimes else { 17658f0484fSRodney W. Grimes k2.data = bi->bytes; 17758f0484fSRodney W. Grimes k2.size = bi->ksize; 17858f0484fSRodney W. Grimes } 17958f0484fSRodney W. Grimes } 18058f0484fSRodney W. Grimes 18158f0484fSRodney W. Grimes if (bigkey) { 18258f0484fSRodney W. Grimes if (__ovfl_get(t, bigkey, 18358f0484fSRodney W. Grimes &k2.size, &t->bt_dbuf, &t->bt_dbufsz)) 18458f0484fSRodney W. Grimes return (RET_ERROR); 18558f0484fSRodney W. Grimes k2.data = t->bt_dbuf; 18658f0484fSRodney W. Grimes } 18758f0484fSRodney W. Grimes return ((*t->bt_cmp)(k1, &k2)); 18858f0484fSRodney W. Grimes } 18958f0484fSRodney W. Grimes 19058f0484fSRodney W. Grimes /* 19158f0484fSRodney W. Grimes * __BT_DEFCMP -- Default comparison routine. 19258f0484fSRodney W. Grimes * 19358f0484fSRodney W. Grimes * Parameters: 19458f0484fSRodney W. Grimes * a: DBT #1 19558f0484fSRodney W. Grimes * b: DBT #2 19658f0484fSRodney W. Grimes * 19758f0484fSRodney W. Grimes * Returns: 19858f0484fSRodney W. Grimes * < 0 if a is < b 19958f0484fSRodney W. Grimes * = 0 if a is = b 20058f0484fSRodney W. Grimes * > 0 if a is > b 20158f0484fSRodney W. Grimes */ 20258f0484fSRodney W. Grimes int 20358f0484fSRodney W. Grimes __bt_defcmp(a, b) 20458f0484fSRodney W. Grimes const DBT *a, *b; 20558f0484fSRodney W. Grimes { 20658f0484fSRodney W. Grimes register size_t len; 20758f0484fSRodney W. Grimes register u_char *p1, *p2; 20858f0484fSRodney W. Grimes 20958f0484fSRodney W. Grimes /* 21058f0484fSRodney W. Grimes * XXX 21158f0484fSRodney W. Grimes * If a size_t doesn't fit in an int, this routine can lose. 21258f0484fSRodney W. Grimes * What we need is a integral type which is guaranteed to be 21358f0484fSRodney W. Grimes * larger than a size_t, and there is no such thing. 21458f0484fSRodney W. Grimes */ 21558f0484fSRodney W. Grimes len = MIN(a->size, b->size); 21658f0484fSRodney W. Grimes for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2) 21758f0484fSRodney W. Grimes if (*p1 != *p2) 21858f0484fSRodney W. Grimes return ((int)*p1 - (int)*p2); 21958f0484fSRodney W. Grimes return ((int)a->size - (int)b->size); 22058f0484fSRodney W. Grimes } 22158f0484fSRodney W. Grimes 22258f0484fSRodney W. Grimes /* 22358f0484fSRodney W. Grimes * __BT_DEFPFX -- Default prefix routine. 22458f0484fSRodney W. Grimes * 22558f0484fSRodney W. Grimes * Parameters: 22658f0484fSRodney W. Grimes * a: DBT #1 22758f0484fSRodney W. Grimes * b: DBT #2 22858f0484fSRodney W. Grimes * 22958f0484fSRodney W. Grimes * Returns: 23058f0484fSRodney W. Grimes * Number of bytes needed to distinguish b from a. 23158f0484fSRodney W. Grimes */ 23258f0484fSRodney W. Grimes size_t 23358f0484fSRodney W. Grimes __bt_defpfx(a, b) 23458f0484fSRodney W. Grimes const DBT *a, *b; 23558f0484fSRodney W. Grimes { 23658f0484fSRodney W. Grimes register u_char *p1, *p2; 23758f0484fSRodney W. Grimes register size_t cnt, len; 23858f0484fSRodney W. Grimes 23958f0484fSRodney W. Grimes cnt = 1; 24058f0484fSRodney W. Grimes len = MIN(a->size, b->size); 24158f0484fSRodney W. Grimes for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt) 24258f0484fSRodney W. Grimes if (*p1 != *p2) 24358f0484fSRodney W. Grimes return (cnt); 24458f0484fSRodney W. Grimes 24558f0484fSRodney W. Grimes /* a->size must be <= b->size, or they wouldn't be in this order. */ 24658f0484fSRodney W. Grimes return (a->size < b->size ? a->size + 1 : a->size); 24758f0484fSRodney W. Grimes } 248