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. 16fbbd9655SWarner Losh * 3. Neither the name of the University nor the names of its contributors 1758f0484fSRodney W. Grimes * may be used to endorse or promote products derived from this software 1858f0484fSRodney W. Grimes * without specific prior written permission. 1958f0484fSRodney W. Grimes * 2058f0484fSRodney W. Grimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 2158f0484fSRodney W. Grimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2258f0484fSRodney W. Grimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2358f0484fSRodney W. Grimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 2458f0484fSRodney W. Grimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2558f0484fSRodney W. Grimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2658f0484fSRodney W. Grimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2758f0484fSRodney W. Grimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2858f0484fSRodney W. Grimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2958f0484fSRodney W. Grimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 3058f0484fSRodney W. Grimes * SUCH DAMAGE. 3158f0484fSRodney W. Grimes */ 3258f0484fSRodney W. Grimes 3358f0484fSRodney W. Grimes #if defined(LIBC_SCCS) && !defined(lint) 34ef5d438eSPaul Traina static char sccsid[] = "@(#)bt_utils.c 8.8 (Berkeley) 7/20/94"; 3558f0484fSRodney W. Grimes #endif /* LIBC_SCCS and not lint */ 368fb3f3f6SDavid E. O'Brien #include <sys/cdefs.h> 378fb3f3f6SDavid E. O'Brien __FBSDID("$FreeBSD$"); 3858f0484fSRodney W. Grimes 3958f0484fSRodney W. Grimes #include <sys/param.h> 4058f0484fSRodney W. Grimes 4158f0484fSRodney W. Grimes #include <stdio.h> 4258f0484fSRodney W. Grimes #include <stdlib.h> 4358f0484fSRodney W. Grimes #include <string.h> 4458f0484fSRodney W. Grimes 4558f0484fSRodney W. Grimes #include <db.h> 4658f0484fSRodney W. Grimes #include "btree.h" 4758f0484fSRodney W. Grimes 4858f0484fSRodney W. Grimes /* 49ef5d438eSPaul Traina * __bt_ret -- 50ef5d438eSPaul Traina * Build return key/data pair. 5158f0484fSRodney W. Grimes * 5258f0484fSRodney W. Grimes * Parameters: 5358f0484fSRodney W. Grimes * t: tree 54ef5d438eSPaul Traina * e: key/data pair to be returned 5558f0484fSRodney W. Grimes * key: user's key structure (NULL if not to be filled in) 56ef5d438eSPaul Traina * rkey: memory area to hold key 57ef5d438eSPaul Traina * data: user's data structure (NULL if not to be filled in) 58ef5d438eSPaul Traina * rdata: memory area to hold data 59ef5d438eSPaul Traina * copy: always copy the key/data item 6058f0484fSRodney W. Grimes * 6158f0484fSRodney W. Grimes * Returns: 6258f0484fSRodney W. Grimes * RET_SUCCESS, RET_ERROR. 6358f0484fSRodney W. Grimes */ 6458f0484fSRodney W. Grimes int 650ac22237SXin LI __bt_ret(BTREE *t, EPG *e, DBT *key, DBT *rkey, DBT *data, DBT *rdata, int copy) 6658f0484fSRodney W. Grimes { 67ef5d438eSPaul Traina BLEAF *bl; 68ef5d438eSPaul Traina void *p; 6958f0484fSRodney W. Grimes 7058f0484fSRodney W. Grimes bl = GETBLEAF(e->page, e->index); 7158f0484fSRodney W. Grimes 7258f0484fSRodney W. Grimes /* 73ef5d438eSPaul Traina * We must copy big keys/data to make them contigous. Otherwise, 74ef5d438eSPaul Traina * leave the page pinned and don't copy unless the user specified 7558f0484fSRodney W. Grimes * concurrent access. 7658f0484fSRodney W. Grimes */ 77ef5d438eSPaul Traina if (key == NULL) 78ef5d438eSPaul Traina goto dataonly; 79ef5d438eSPaul Traina 80ef5d438eSPaul Traina if (bl->flags & P_BIGKEY) { 81ef5d438eSPaul Traina if (__ovfl_get(t, bl->bytes, 82ef5d438eSPaul Traina &key->size, &rkey->data, &rkey->size)) 83ef5d438eSPaul Traina return (RET_ERROR); 84ef5d438eSPaul Traina key->data = rkey->data; 85ef5d438eSPaul Traina } else if (copy || F_ISSET(t, B_DB_LOCK)) { 86ef5d438eSPaul Traina if (bl->ksize > rkey->size) { 877ccf00dfSXin LI p = realloc(rkey->data, bl->ksize); 88ef5d438eSPaul Traina if (p == NULL) 89ef5d438eSPaul Traina return (RET_ERROR); 90ef5d438eSPaul Traina rkey->data = p; 91ef5d438eSPaul Traina rkey->size = bl->ksize; 92ef5d438eSPaul Traina } 93ef5d438eSPaul Traina memmove(rkey->data, bl->bytes, bl->ksize); 94ef5d438eSPaul Traina key->size = bl->ksize; 95ef5d438eSPaul Traina key->data = rkey->data; 96ef5d438eSPaul Traina } else { 97ef5d438eSPaul Traina key->size = bl->ksize; 98ef5d438eSPaul Traina key->data = bl->bytes; 99ef5d438eSPaul Traina } 100ef5d438eSPaul Traina 101ef5d438eSPaul Traina dataonly: 102ef5d438eSPaul Traina if (data == NULL) 103ef5d438eSPaul Traina return (RET_SUCCESS); 104ef5d438eSPaul Traina 10558f0484fSRodney W. Grimes if (bl->flags & P_BIGDATA) { 10658f0484fSRodney W. Grimes if (__ovfl_get(t, bl->bytes + bl->ksize, 107ef5d438eSPaul Traina &data->size, &rdata->data, &rdata->size)) 10858f0484fSRodney W. Grimes return (RET_ERROR); 109ef5d438eSPaul Traina data->data = rdata->data; 110ef5d438eSPaul Traina } else if (copy || F_ISSET(t, B_DB_LOCK)) { 11158f0484fSRodney W. Grimes /* Use +1 in case the first record retrieved is 0 length. */ 112ef5d438eSPaul Traina if (bl->dsize + 1 > rdata->size) { 1137ccf00dfSXin LI p = realloc(rdata->data, bl->dsize + 1); 114ef5d438eSPaul Traina if (p == NULL) 11558f0484fSRodney W. Grimes return (RET_ERROR); 116ef5d438eSPaul Traina rdata->data = p; 117ef5d438eSPaul Traina rdata->size = bl->dsize + 1; 11858f0484fSRodney W. Grimes } 119ef5d438eSPaul Traina memmove(rdata->data, bl->bytes + bl->ksize, bl->dsize); 12058f0484fSRodney W. Grimes data->size = bl->dsize; 121ef5d438eSPaul Traina data->data = rdata->data; 12258f0484fSRodney W. Grimes } else { 12358f0484fSRodney W. Grimes data->size = bl->dsize; 12458f0484fSRodney W. Grimes data->data = bl->bytes + bl->ksize; 12558f0484fSRodney W. Grimes } 12658f0484fSRodney W. Grimes 12758f0484fSRodney W. Grimes return (RET_SUCCESS); 12858f0484fSRodney W. Grimes } 12958f0484fSRodney W. Grimes 13058f0484fSRodney W. Grimes /* 13158f0484fSRodney W. Grimes * __BT_CMP -- Compare a key to a given record. 13258f0484fSRodney W. Grimes * 13358f0484fSRodney W. Grimes * Parameters: 13458f0484fSRodney W. Grimes * t: tree 13558f0484fSRodney W. Grimes * k1: DBT pointer of first arg to comparison 13658f0484fSRodney W. Grimes * e: pointer to EPG for comparison 13758f0484fSRodney W. Grimes * 13858f0484fSRodney W. Grimes * Returns: 13958f0484fSRodney W. Grimes * < 0 if k1 is < record 14058f0484fSRodney W. Grimes * = 0 if k1 is = record 14158f0484fSRodney W. Grimes * > 0 if k1 is > record 14258f0484fSRodney W. Grimes */ 14358f0484fSRodney W. Grimes int 1440ac22237SXin LI __bt_cmp(BTREE *t, const DBT *k1, EPG *e) 14558f0484fSRodney W. Grimes { 14658f0484fSRodney W. Grimes BINTERNAL *bi; 14758f0484fSRodney W. Grimes BLEAF *bl; 14858f0484fSRodney W. Grimes DBT k2; 14958f0484fSRodney W. Grimes PAGE *h; 15058f0484fSRodney W. Grimes void *bigkey; 15158f0484fSRodney W. Grimes 15258f0484fSRodney W. Grimes /* 15358f0484fSRodney W. Grimes * The left-most key on internal pages, at any level of the tree, is 15458f0484fSRodney W. Grimes * guaranteed by the following code to be less than any user key. 15558f0484fSRodney W. Grimes * This saves us from having to update the leftmost key on an internal 15658f0484fSRodney W. Grimes * page when the user inserts a new key in the tree smaller than 15758f0484fSRodney W. Grimes * anything we've yet seen. 15858f0484fSRodney W. Grimes */ 15958f0484fSRodney W. Grimes h = e->page; 16058f0484fSRodney W. Grimes if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF)) 16158f0484fSRodney W. Grimes return (1); 16258f0484fSRodney W. Grimes 16358f0484fSRodney W. Grimes bigkey = NULL; 16458f0484fSRodney W. Grimes if (h->flags & P_BLEAF) { 16558f0484fSRodney W. Grimes bl = GETBLEAF(h, e->index); 16658f0484fSRodney W. Grimes if (bl->flags & P_BIGKEY) 16758f0484fSRodney W. Grimes bigkey = bl->bytes; 16858f0484fSRodney W. Grimes else { 16958f0484fSRodney W. Grimes k2.data = bl->bytes; 17058f0484fSRodney W. Grimes k2.size = bl->ksize; 17158f0484fSRodney W. Grimes } 17258f0484fSRodney W. Grimes } else { 17358f0484fSRodney W. Grimes bi = GETBINTERNAL(h, e->index); 17458f0484fSRodney W. Grimes if (bi->flags & P_BIGKEY) 17558f0484fSRodney W. Grimes bigkey = bi->bytes; 17658f0484fSRodney W. Grimes else { 17758f0484fSRodney W. Grimes k2.data = bi->bytes; 17858f0484fSRodney W. Grimes k2.size = bi->ksize; 17958f0484fSRodney W. Grimes } 18058f0484fSRodney W. Grimes } 18158f0484fSRodney W. Grimes 18258f0484fSRodney W. Grimes if (bigkey) { 18358f0484fSRodney W. Grimes if (__ovfl_get(t, bigkey, 184ef5d438eSPaul Traina &k2.size, &t->bt_rdata.data, &t->bt_rdata.size)) 18558f0484fSRodney W. Grimes return (RET_ERROR); 186ef5d438eSPaul Traina k2.data = t->bt_rdata.data; 18758f0484fSRodney W. Grimes } 18858f0484fSRodney W. Grimes return ((*t->bt_cmp)(k1, &k2)); 18958f0484fSRodney W. Grimes } 19058f0484fSRodney W. Grimes 19158f0484fSRodney W. Grimes /* 19258f0484fSRodney W. Grimes * __BT_DEFCMP -- Default comparison routine. 19358f0484fSRodney W. Grimes * 19458f0484fSRodney W. Grimes * Parameters: 19558f0484fSRodney W. Grimes * a: DBT #1 19658f0484fSRodney W. Grimes * b: DBT #2 19758f0484fSRodney W. Grimes * 19858f0484fSRodney W. Grimes * Returns: 19958f0484fSRodney W. Grimes * < 0 if a is < b 20058f0484fSRodney W. Grimes * = 0 if a is = b 20158f0484fSRodney W. Grimes * > 0 if a is > b 20258f0484fSRodney W. Grimes */ 20358f0484fSRodney W. Grimes int 2040ac22237SXin LI __bt_defcmp(const DBT *a, const DBT *b) 20558f0484fSRodney W. Grimes { 2068fb3f3f6SDavid E. O'Brien size_t len; 2078fb3f3f6SDavid E. O'Brien 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. 2129d5abbddSJens Schweikhardt * What we need is an 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 2330ac22237SXin LI __bt_defpfx(const DBT *a, const DBT *b) 23458f0484fSRodney W. Grimes { 2358fb3f3f6SDavid E. O'Brien u_char *p1, *p2; 2368fb3f3f6SDavid E. O'Brien size_t cnt, len; 23758f0484fSRodney W. Grimes 23858f0484fSRodney W. Grimes cnt = 1; 23958f0484fSRodney W. Grimes len = MIN(a->size, b->size); 24058f0484fSRodney W. Grimes for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt) 24158f0484fSRodney W. Grimes if (*p1 != *p2) 24258f0484fSRodney W. Grimes return (cnt); 24358f0484fSRodney W. Grimes 24458f0484fSRodney W. Grimes /* a->size must be <= b->size, or they wouldn't be in this order. */ 24558f0484fSRodney W. Grimes return (a->size < b->size ? a->size + 1 : a->size); 24658f0484fSRodney W. Grimes } 247