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 */ 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 /* 51ef5d438eSPaul Traina * __bt_ret -- 52ef5d438eSPaul Traina * Build return key/data pair. 5358f0484fSRodney W. Grimes * 5458f0484fSRodney W. Grimes * Parameters: 5558f0484fSRodney W. Grimes * t: tree 56ef5d438eSPaul Traina * e: key/data pair to be returned 5758f0484fSRodney W. Grimes * key: user's key structure (NULL if not to be filled in) 58ef5d438eSPaul Traina * rkey: memory area to hold key 59ef5d438eSPaul Traina * data: user's data structure (NULL if not to be filled in) 60ef5d438eSPaul Traina * rdata: memory area to hold data 61ef5d438eSPaul Traina * copy: always copy the key/data item 6258f0484fSRodney W. Grimes * 6358f0484fSRodney W. Grimes * Returns: 6458f0484fSRodney W. Grimes * RET_SUCCESS, RET_ERROR. 6558f0484fSRodney W. Grimes */ 6658f0484fSRodney W. Grimes int 67ef5d438eSPaul Traina __bt_ret(t, e, key, rkey, data, rdata, copy) 6858f0484fSRodney W. Grimes BTREE *t; 6958f0484fSRodney W. Grimes EPG *e; 70ef5d438eSPaul Traina DBT *key, *rkey, *data, *rdata; 71ef5d438eSPaul Traina int copy; 7258f0484fSRodney W. Grimes { 73ef5d438eSPaul Traina BLEAF *bl; 74ef5d438eSPaul Traina void *p; 7558f0484fSRodney W. Grimes 7658f0484fSRodney W. Grimes bl = GETBLEAF(e->page, e->index); 7758f0484fSRodney W. Grimes 7858f0484fSRodney W. Grimes /* 79ef5d438eSPaul Traina * We must copy big keys/data to make them contigous. Otherwise, 80ef5d438eSPaul Traina * leave the page pinned and don't copy unless the user specified 8158f0484fSRodney W. Grimes * concurrent access. 8258f0484fSRodney W. Grimes */ 83ef5d438eSPaul Traina if (key == NULL) 84ef5d438eSPaul Traina goto dataonly; 85ef5d438eSPaul Traina 86ef5d438eSPaul Traina if (bl->flags & P_BIGKEY) { 87ef5d438eSPaul Traina if (__ovfl_get(t, bl->bytes, 88ef5d438eSPaul Traina &key->size, &rkey->data, &rkey->size)) 89ef5d438eSPaul Traina return (RET_ERROR); 90ef5d438eSPaul Traina key->data = rkey->data; 91ef5d438eSPaul Traina } else if (copy || F_ISSET(t, B_DB_LOCK)) { 92ef5d438eSPaul Traina if (bl->ksize > rkey->size) { 93ef5d438eSPaul Traina p = (void *)(rkey->data == NULL ? 94ef5d438eSPaul Traina malloc(bl->ksize) : realloc(rkey->data, bl->ksize)); 95ef5d438eSPaul Traina if (p == NULL) 96ef5d438eSPaul Traina return (RET_ERROR); 97ef5d438eSPaul Traina rkey->data = p; 98ef5d438eSPaul Traina rkey->size = bl->ksize; 99ef5d438eSPaul Traina } 100ef5d438eSPaul Traina memmove(rkey->data, bl->bytes, bl->ksize); 101ef5d438eSPaul Traina key->size = bl->ksize; 102ef5d438eSPaul Traina key->data = rkey->data; 103ef5d438eSPaul Traina } else { 104ef5d438eSPaul Traina key->size = bl->ksize; 105ef5d438eSPaul Traina key->data = bl->bytes; 106ef5d438eSPaul Traina } 107ef5d438eSPaul Traina 108ef5d438eSPaul Traina dataonly: 109ef5d438eSPaul Traina if (data == NULL) 110ef5d438eSPaul Traina return (RET_SUCCESS); 111ef5d438eSPaul Traina 11258f0484fSRodney W. Grimes if (bl->flags & P_BIGDATA) { 11358f0484fSRodney W. Grimes if (__ovfl_get(t, bl->bytes + bl->ksize, 114ef5d438eSPaul Traina &data->size, &rdata->data, &rdata->size)) 11558f0484fSRodney W. Grimes return (RET_ERROR); 116ef5d438eSPaul Traina data->data = rdata->data; 117ef5d438eSPaul Traina } else if (copy || F_ISSET(t, B_DB_LOCK)) { 11858f0484fSRodney W. Grimes /* Use +1 in case the first record retrieved is 0 length. */ 119ef5d438eSPaul Traina if (bl->dsize + 1 > rdata->size) { 120ef5d438eSPaul Traina p = (void *)(rdata->data == NULL ? 121ef5d438eSPaul Traina malloc(bl->dsize + 1) : 122ef5d438eSPaul Traina realloc(rdata->data, bl->dsize + 1)); 123ef5d438eSPaul Traina if (p == NULL) 12458f0484fSRodney W. Grimes return (RET_ERROR); 125ef5d438eSPaul Traina rdata->data = p; 126ef5d438eSPaul Traina rdata->size = bl->dsize + 1; 12758f0484fSRodney W. Grimes } 128ef5d438eSPaul Traina memmove(rdata->data, bl->bytes + bl->ksize, bl->dsize); 12958f0484fSRodney W. Grimes data->size = bl->dsize; 130ef5d438eSPaul Traina data->data = rdata->data; 13158f0484fSRodney W. Grimes } else { 13258f0484fSRodney W. Grimes data->size = bl->dsize; 13358f0484fSRodney W. Grimes data->data = bl->bytes + bl->ksize; 13458f0484fSRodney W. Grimes } 13558f0484fSRodney W. Grimes 13658f0484fSRodney W. Grimes return (RET_SUCCESS); 13758f0484fSRodney W. Grimes } 13858f0484fSRodney W. Grimes 13958f0484fSRodney W. Grimes /* 14058f0484fSRodney W. Grimes * __BT_CMP -- Compare a key to a given record. 14158f0484fSRodney W. Grimes * 14258f0484fSRodney W. Grimes * Parameters: 14358f0484fSRodney W. Grimes * t: tree 14458f0484fSRodney W. Grimes * k1: DBT pointer of first arg to comparison 14558f0484fSRodney W. Grimes * e: pointer to EPG for comparison 14658f0484fSRodney W. Grimes * 14758f0484fSRodney W. Grimes * Returns: 14858f0484fSRodney W. Grimes * < 0 if k1 is < record 14958f0484fSRodney W. Grimes * = 0 if k1 is = record 15058f0484fSRodney W. Grimes * > 0 if k1 is > record 15158f0484fSRodney W. Grimes */ 15258f0484fSRodney W. Grimes int 15358f0484fSRodney W. Grimes __bt_cmp(t, k1, e) 15458f0484fSRodney W. Grimes BTREE *t; 15558f0484fSRodney W. Grimes const DBT *k1; 15658f0484fSRodney W. Grimes EPG *e; 15758f0484fSRodney W. Grimes { 15858f0484fSRodney W. Grimes BINTERNAL *bi; 15958f0484fSRodney W. Grimes BLEAF *bl; 16058f0484fSRodney W. Grimes DBT k2; 16158f0484fSRodney W. Grimes PAGE *h; 16258f0484fSRodney W. Grimes void *bigkey; 16358f0484fSRodney W. Grimes 16458f0484fSRodney W. Grimes /* 16558f0484fSRodney W. Grimes * The left-most key on internal pages, at any level of the tree, is 16658f0484fSRodney W. Grimes * guaranteed by the following code to be less than any user key. 16758f0484fSRodney W. Grimes * This saves us from having to update the leftmost key on an internal 16858f0484fSRodney W. Grimes * page when the user inserts a new key in the tree smaller than 16958f0484fSRodney W. Grimes * anything we've yet seen. 17058f0484fSRodney W. Grimes */ 17158f0484fSRodney W. Grimes h = e->page; 17258f0484fSRodney W. Grimes if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF)) 17358f0484fSRodney W. Grimes return (1); 17458f0484fSRodney W. Grimes 17558f0484fSRodney W. Grimes bigkey = NULL; 17658f0484fSRodney W. Grimes if (h->flags & P_BLEAF) { 17758f0484fSRodney W. Grimes bl = GETBLEAF(h, e->index); 17858f0484fSRodney W. Grimes if (bl->flags & P_BIGKEY) 17958f0484fSRodney W. Grimes bigkey = bl->bytes; 18058f0484fSRodney W. Grimes else { 18158f0484fSRodney W. Grimes k2.data = bl->bytes; 18258f0484fSRodney W. Grimes k2.size = bl->ksize; 18358f0484fSRodney W. Grimes } 18458f0484fSRodney W. Grimes } else { 18558f0484fSRodney W. Grimes bi = GETBINTERNAL(h, e->index); 18658f0484fSRodney W. Grimes if (bi->flags & P_BIGKEY) 18758f0484fSRodney W. Grimes bigkey = bi->bytes; 18858f0484fSRodney W. Grimes else { 18958f0484fSRodney W. Grimes k2.data = bi->bytes; 19058f0484fSRodney W. Grimes k2.size = bi->ksize; 19158f0484fSRodney W. Grimes } 19258f0484fSRodney W. Grimes } 19358f0484fSRodney W. Grimes 19458f0484fSRodney W. Grimes if (bigkey) { 19558f0484fSRodney W. Grimes if (__ovfl_get(t, bigkey, 196ef5d438eSPaul Traina &k2.size, &t->bt_rdata.data, &t->bt_rdata.size)) 19758f0484fSRodney W. Grimes return (RET_ERROR); 198ef5d438eSPaul Traina k2.data = t->bt_rdata.data; 19958f0484fSRodney W. Grimes } 20058f0484fSRodney W. Grimes return ((*t->bt_cmp)(k1, &k2)); 20158f0484fSRodney W. Grimes } 20258f0484fSRodney W. Grimes 20358f0484fSRodney W. Grimes /* 20458f0484fSRodney W. Grimes * __BT_DEFCMP -- Default comparison routine. 20558f0484fSRodney W. Grimes * 20658f0484fSRodney W. Grimes * Parameters: 20758f0484fSRodney W. Grimes * a: DBT #1 20858f0484fSRodney W. Grimes * b: DBT #2 20958f0484fSRodney W. Grimes * 21058f0484fSRodney W. Grimes * Returns: 21158f0484fSRodney W. Grimes * < 0 if a is < b 21258f0484fSRodney W. Grimes * = 0 if a is = b 21358f0484fSRodney W. Grimes * > 0 if a is > b 21458f0484fSRodney W. Grimes */ 21558f0484fSRodney W. Grimes int 21658f0484fSRodney W. Grimes __bt_defcmp(a, b) 21758f0484fSRodney W. Grimes const DBT *a, *b; 21858f0484fSRodney W. Grimes { 21958f0484fSRodney W. Grimes register size_t len; 22058f0484fSRodney W. Grimes register u_char *p1, *p2; 22158f0484fSRodney W. Grimes 22258f0484fSRodney W. Grimes /* 22358f0484fSRodney W. Grimes * XXX 22458f0484fSRodney W. Grimes * If a size_t doesn't fit in an int, this routine can lose. 22558f0484fSRodney W. Grimes * What we need is a integral type which is guaranteed to be 22658f0484fSRodney W. Grimes * larger than a size_t, and there is no such thing. 22758f0484fSRodney W. Grimes */ 22858f0484fSRodney W. Grimes len = MIN(a->size, b->size); 22958f0484fSRodney W. Grimes for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2) 23058f0484fSRodney W. Grimes if (*p1 != *p2) 23158f0484fSRodney W. Grimes return ((int)*p1 - (int)*p2); 23258f0484fSRodney W. Grimes return ((int)a->size - (int)b->size); 23358f0484fSRodney W. Grimes } 23458f0484fSRodney W. Grimes 23558f0484fSRodney W. Grimes /* 23658f0484fSRodney W. Grimes * __BT_DEFPFX -- Default prefix routine. 23758f0484fSRodney W. Grimes * 23858f0484fSRodney W. Grimes * Parameters: 23958f0484fSRodney W. Grimes * a: DBT #1 24058f0484fSRodney W. Grimes * b: DBT #2 24158f0484fSRodney W. Grimes * 24258f0484fSRodney W. Grimes * Returns: 24358f0484fSRodney W. Grimes * Number of bytes needed to distinguish b from a. 24458f0484fSRodney W. Grimes */ 24558f0484fSRodney W. Grimes size_t 24658f0484fSRodney W. Grimes __bt_defpfx(a, b) 24758f0484fSRodney W. Grimes const DBT *a, *b; 24858f0484fSRodney W. Grimes { 24958f0484fSRodney W. Grimes register u_char *p1, *p2; 25058f0484fSRodney W. Grimes register size_t cnt, len; 25158f0484fSRodney W. Grimes 25258f0484fSRodney W. Grimes cnt = 1; 25358f0484fSRodney W. Grimes len = MIN(a->size, b->size); 25458f0484fSRodney W. Grimes for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt) 25558f0484fSRodney W. Grimes if (*p1 != *p2) 25658f0484fSRodney W. Grimes return (cnt); 25758f0484fSRodney W. Grimes 25858f0484fSRodney W. Grimes /* a->size must be <= b->size, or they wouldn't be in this order. */ 25958f0484fSRodney W. Grimes return (a->size < b->size ? a->size + 1 : a->size); 26058f0484fSRodney W. Grimes } 261