158f0484fSRodney W. Grimes /*- 2ef5d438eSPaul Traina * Copyright (c) 1990, 1993, 1994 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) 38ef5d438eSPaul Traina static char sccsid[] = "@(#)bt_utils.c 8.8 (Berkeley) 7/20/94"; 3958f0484fSRodney W. Grimes #endif /* LIBC_SCCS and not lint */ 408fb3f3f6SDavid E. O'Brien #include <sys/cdefs.h> 418fb3f3f6SDavid E. O'Brien __FBSDID("$FreeBSD$"); 4258f0484fSRodney W. Grimes 4358f0484fSRodney W. Grimes #include <sys/param.h> 4458f0484fSRodney W. Grimes 4558f0484fSRodney W. Grimes #include <stdio.h> 4658f0484fSRodney W. Grimes #include <stdlib.h> 4758f0484fSRodney W. Grimes #include <string.h> 4858f0484fSRodney W. Grimes 4958f0484fSRodney W. Grimes #include <db.h> 5058f0484fSRodney W. Grimes #include "btree.h" 5158f0484fSRodney W. Grimes 5258f0484fSRodney W. Grimes /* 53ef5d438eSPaul Traina * __bt_ret -- 54ef5d438eSPaul Traina * Build return key/data pair. 5558f0484fSRodney W. Grimes * 5658f0484fSRodney W. Grimes * Parameters: 5758f0484fSRodney W. Grimes * t: tree 58ef5d438eSPaul Traina * e: key/data pair to be returned 5958f0484fSRodney W. Grimes * key: user's key structure (NULL if not to be filled in) 60ef5d438eSPaul Traina * rkey: memory area to hold key 61ef5d438eSPaul Traina * data: user's data structure (NULL if not to be filled in) 62ef5d438eSPaul Traina * rdata: memory area to hold data 63ef5d438eSPaul Traina * copy: always copy the key/data item 6458f0484fSRodney W. Grimes * 6558f0484fSRodney W. Grimes * Returns: 6658f0484fSRodney W. Grimes * RET_SUCCESS, RET_ERROR. 6758f0484fSRodney W. Grimes */ 6858f0484fSRodney W. Grimes int 69ef5d438eSPaul Traina __bt_ret(t, e, key, rkey, data, rdata, copy) 7058f0484fSRodney W. Grimes BTREE *t; 7158f0484fSRodney W. Grimes EPG *e; 72ef5d438eSPaul Traina DBT *key, *rkey, *data, *rdata; 73ef5d438eSPaul Traina int copy; 7458f0484fSRodney W. Grimes { 75ef5d438eSPaul Traina BLEAF *bl; 76ef5d438eSPaul Traina void *p; 7758f0484fSRodney W. Grimes 7858f0484fSRodney W. Grimes bl = GETBLEAF(e->page, e->index); 7958f0484fSRodney W. Grimes 8058f0484fSRodney W. Grimes /* 81ef5d438eSPaul Traina * We must copy big keys/data to make them contigous. Otherwise, 82ef5d438eSPaul Traina * leave the page pinned and don't copy unless the user specified 8358f0484fSRodney W. Grimes * concurrent access. 8458f0484fSRodney W. Grimes */ 85ef5d438eSPaul Traina if (key == NULL) 86ef5d438eSPaul Traina goto dataonly; 87ef5d438eSPaul Traina 88ef5d438eSPaul Traina if (bl->flags & P_BIGKEY) { 89ef5d438eSPaul Traina if (__ovfl_get(t, bl->bytes, 90ef5d438eSPaul Traina &key->size, &rkey->data, &rkey->size)) 91ef5d438eSPaul Traina return (RET_ERROR); 92ef5d438eSPaul Traina key->data = rkey->data; 93ef5d438eSPaul Traina } else if (copy || F_ISSET(t, B_DB_LOCK)) { 94ef5d438eSPaul Traina if (bl->ksize > rkey->size) { 95ef5d438eSPaul Traina p = (void *)(rkey->data == NULL ? 96ef5d438eSPaul Traina malloc(bl->ksize) : realloc(rkey->data, bl->ksize)); 97ef5d438eSPaul Traina if (p == NULL) 98ef5d438eSPaul Traina return (RET_ERROR); 99ef5d438eSPaul Traina rkey->data = p; 100ef5d438eSPaul Traina rkey->size = bl->ksize; 101ef5d438eSPaul Traina } 102ef5d438eSPaul Traina memmove(rkey->data, bl->bytes, bl->ksize); 103ef5d438eSPaul Traina key->size = bl->ksize; 104ef5d438eSPaul Traina key->data = rkey->data; 105ef5d438eSPaul Traina } else { 106ef5d438eSPaul Traina key->size = bl->ksize; 107ef5d438eSPaul Traina key->data = bl->bytes; 108ef5d438eSPaul Traina } 109ef5d438eSPaul Traina 110ef5d438eSPaul Traina dataonly: 111ef5d438eSPaul Traina if (data == NULL) 112ef5d438eSPaul Traina return (RET_SUCCESS); 113ef5d438eSPaul Traina 11458f0484fSRodney W. Grimes if (bl->flags & P_BIGDATA) { 11558f0484fSRodney W. Grimes if (__ovfl_get(t, bl->bytes + bl->ksize, 116ef5d438eSPaul Traina &data->size, &rdata->data, &rdata->size)) 11758f0484fSRodney W. Grimes return (RET_ERROR); 118ef5d438eSPaul Traina data->data = rdata->data; 119ef5d438eSPaul Traina } else if (copy || F_ISSET(t, B_DB_LOCK)) { 12058f0484fSRodney W. Grimes /* Use +1 in case the first record retrieved is 0 length. */ 121ef5d438eSPaul Traina if (bl->dsize + 1 > rdata->size) { 122ef5d438eSPaul Traina p = (void *)(rdata->data == NULL ? 123ef5d438eSPaul Traina malloc(bl->dsize + 1) : 124ef5d438eSPaul Traina realloc(rdata->data, bl->dsize + 1)); 125ef5d438eSPaul Traina if (p == NULL) 12658f0484fSRodney W. Grimes return (RET_ERROR); 127ef5d438eSPaul Traina rdata->data = p; 128ef5d438eSPaul Traina rdata->size = bl->dsize + 1; 12958f0484fSRodney W. Grimes } 130ef5d438eSPaul Traina memmove(rdata->data, bl->bytes + bl->ksize, bl->dsize); 13158f0484fSRodney W. Grimes data->size = bl->dsize; 132ef5d438eSPaul Traina data->data = rdata->data; 13358f0484fSRodney W. Grimes } else { 13458f0484fSRodney W. Grimes data->size = bl->dsize; 13558f0484fSRodney W. Grimes data->data = bl->bytes + bl->ksize; 13658f0484fSRodney W. Grimes } 13758f0484fSRodney W. Grimes 13858f0484fSRodney W. Grimes return (RET_SUCCESS); 13958f0484fSRodney W. Grimes } 14058f0484fSRodney W. Grimes 14158f0484fSRodney W. Grimes /* 14258f0484fSRodney W. Grimes * __BT_CMP -- Compare a key to a given record. 14358f0484fSRodney W. Grimes * 14458f0484fSRodney W. Grimes * Parameters: 14558f0484fSRodney W. Grimes * t: tree 14658f0484fSRodney W. Grimes * k1: DBT pointer of first arg to comparison 14758f0484fSRodney W. Grimes * e: pointer to EPG for comparison 14858f0484fSRodney W. Grimes * 14958f0484fSRodney W. Grimes * Returns: 15058f0484fSRodney W. Grimes * < 0 if k1 is < record 15158f0484fSRodney W. Grimes * = 0 if k1 is = record 15258f0484fSRodney W. Grimes * > 0 if k1 is > record 15358f0484fSRodney W. Grimes */ 15458f0484fSRodney W. Grimes int 15558f0484fSRodney W. Grimes __bt_cmp(t, k1, e) 15658f0484fSRodney W. Grimes BTREE *t; 15758f0484fSRodney W. Grimes const DBT *k1; 15858f0484fSRodney W. Grimes EPG *e; 15958f0484fSRodney W. Grimes { 16058f0484fSRodney W. Grimes BINTERNAL *bi; 16158f0484fSRodney W. Grimes BLEAF *bl; 16258f0484fSRodney W. Grimes DBT k2; 16358f0484fSRodney W. Grimes PAGE *h; 16458f0484fSRodney W. Grimes void *bigkey; 16558f0484fSRodney W. Grimes 16658f0484fSRodney W. Grimes /* 16758f0484fSRodney W. Grimes * The left-most key on internal pages, at any level of the tree, is 16858f0484fSRodney W. Grimes * guaranteed by the following code to be less than any user key. 16958f0484fSRodney W. Grimes * This saves us from having to update the leftmost key on an internal 17058f0484fSRodney W. Grimes * page when the user inserts a new key in the tree smaller than 17158f0484fSRodney W. Grimes * anything we've yet seen. 17258f0484fSRodney W. Grimes */ 17358f0484fSRodney W. Grimes h = e->page; 17458f0484fSRodney W. Grimes if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF)) 17558f0484fSRodney W. Grimes return (1); 17658f0484fSRodney W. Grimes 17758f0484fSRodney W. Grimes bigkey = NULL; 17858f0484fSRodney W. Grimes if (h->flags & P_BLEAF) { 17958f0484fSRodney W. Grimes bl = GETBLEAF(h, e->index); 18058f0484fSRodney W. Grimes if (bl->flags & P_BIGKEY) 18158f0484fSRodney W. Grimes bigkey = bl->bytes; 18258f0484fSRodney W. Grimes else { 18358f0484fSRodney W. Grimes k2.data = bl->bytes; 18458f0484fSRodney W. Grimes k2.size = bl->ksize; 18558f0484fSRodney W. Grimes } 18658f0484fSRodney W. Grimes } else { 18758f0484fSRodney W. Grimes bi = GETBINTERNAL(h, e->index); 18858f0484fSRodney W. Grimes if (bi->flags & P_BIGKEY) 18958f0484fSRodney W. Grimes bigkey = bi->bytes; 19058f0484fSRodney W. Grimes else { 19158f0484fSRodney W. Grimes k2.data = bi->bytes; 19258f0484fSRodney W. Grimes k2.size = bi->ksize; 19358f0484fSRodney W. Grimes } 19458f0484fSRodney W. Grimes } 19558f0484fSRodney W. Grimes 19658f0484fSRodney W. Grimes if (bigkey) { 19758f0484fSRodney W. Grimes if (__ovfl_get(t, bigkey, 198ef5d438eSPaul Traina &k2.size, &t->bt_rdata.data, &t->bt_rdata.size)) 19958f0484fSRodney W. Grimes return (RET_ERROR); 200ef5d438eSPaul Traina k2.data = t->bt_rdata.data; 20158f0484fSRodney W. Grimes } 20258f0484fSRodney W. Grimes return ((*t->bt_cmp)(k1, &k2)); 20358f0484fSRodney W. Grimes } 20458f0484fSRodney W. Grimes 20558f0484fSRodney W. Grimes /* 20658f0484fSRodney W. Grimes * __BT_DEFCMP -- Default comparison routine. 20758f0484fSRodney W. Grimes * 20858f0484fSRodney W. Grimes * Parameters: 20958f0484fSRodney W. Grimes * a: DBT #1 21058f0484fSRodney W. Grimes * b: DBT #2 21158f0484fSRodney W. Grimes * 21258f0484fSRodney W. Grimes * Returns: 21358f0484fSRodney W. Grimes * < 0 if a is < b 21458f0484fSRodney W. Grimes * = 0 if a is = b 21558f0484fSRodney W. Grimes * > 0 if a is > b 21658f0484fSRodney W. Grimes */ 21758f0484fSRodney W. Grimes int 21858f0484fSRodney W. Grimes __bt_defcmp(a, b) 21958f0484fSRodney W. Grimes const DBT *a, *b; 22058f0484fSRodney W. Grimes { 2218fb3f3f6SDavid E. O'Brien size_t len; 2228fb3f3f6SDavid E. O'Brien u_char *p1, *p2; 22358f0484fSRodney W. Grimes 22458f0484fSRodney W. Grimes /* 22558f0484fSRodney W. Grimes * XXX 22658f0484fSRodney W. Grimes * If a size_t doesn't fit in an int, this routine can lose. 22758f0484fSRodney W. Grimes * What we need is a integral type which is guaranteed to be 22858f0484fSRodney W. Grimes * larger than a size_t, and there is no such thing. 22958f0484fSRodney W. Grimes */ 23058f0484fSRodney W. Grimes len = MIN(a->size, b->size); 23158f0484fSRodney W. Grimes for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2) 23258f0484fSRodney W. Grimes if (*p1 != *p2) 23358f0484fSRodney W. Grimes return ((int)*p1 - (int)*p2); 23458f0484fSRodney W. Grimes return ((int)a->size - (int)b->size); 23558f0484fSRodney W. Grimes } 23658f0484fSRodney W. Grimes 23758f0484fSRodney W. Grimes /* 23858f0484fSRodney W. Grimes * __BT_DEFPFX -- Default prefix routine. 23958f0484fSRodney W. Grimes * 24058f0484fSRodney W. Grimes * Parameters: 24158f0484fSRodney W. Grimes * a: DBT #1 24258f0484fSRodney W. Grimes * b: DBT #2 24358f0484fSRodney W. Grimes * 24458f0484fSRodney W. Grimes * Returns: 24558f0484fSRodney W. Grimes * Number of bytes needed to distinguish b from a. 24658f0484fSRodney W. Grimes */ 24758f0484fSRodney W. Grimes size_t 24858f0484fSRodney W. Grimes __bt_defpfx(a, b) 24958f0484fSRodney W. Grimes const DBT *a, *b; 25058f0484fSRodney W. Grimes { 2518fb3f3f6SDavid E. O'Brien u_char *p1, *p2; 2528fb3f3f6SDavid E. O'Brien size_t cnt, len; 25358f0484fSRodney W. Grimes 25458f0484fSRodney W. Grimes cnt = 1; 25558f0484fSRodney W. Grimes len = MIN(a->size, b->size); 25658f0484fSRodney W. Grimes for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt) 25758f0484fSRodney W. Grimes if (*p1 != *p2) 25858f0484fSRodney W. Grimes return (cnt); 25958f0484fSRodney W. Grimes 26058f0484fSRodney W. Grimes /* a->size must be <= b->size, or they wouldn't be in this order. */ 26158f0484fSRodney W. Grimes return (a->size < b->size ? a->size + 1 : a->size); 26258f0484fSRodney W. Grimes } 263