158f0484fSRodney W. Grimes /*-
28a16b7a1SPedro F. Giffuni * SPDX-License-Identifier: BSD-3-Clause
38a16b7a1SPedro F. Giffuni *
4ef5d438eSPaul Traina * Copyright (c) 1990, 1993, 1994
558f0484fSRodney W. Grimes * The Regents of the University of California. All rights reserved.
658f0484fSRodney W. Grimes *
758f0484fSRodney W. Grimes * This code is derived from software contributed to Berkeley by
858f0484fSRodney W. Grimes * Mike Olson.
958f0484fSRodney W. Grimes *
1058f0484fSRodney W. Grimes * Redistribution and use in source and binary forms, with or without
1158f0484fSRodney W. Grimes * modification, are permitted provided that the following conditions
1258f0484fSRodney W. Grimes * are met:
1358f0484fSRodney W. Grimes * 1. Redistributions of source code must retain the above copyright
1458f0484fSRodney W. Grimes * notice, this list of conditions and the following disclaimer.
1558f0484fSRodney W. Grimes * 2. Redistributions in binary form must reproduce the above copyright
1658f0484fSRodney W. Grimes * notice, this list of conditions and the following disclaimer in the
1758f0484fSRodney W. Grimes * documentation and/or other materials provided with the distribution.
18fbbd9655SWarner Losh * 3. Neither the name of the University nor the names of its contributors
1958f0484fSRodney W. Grimes * may be used to endorse or promote products derived from this software
2058f0484fSRodney W. Grimes * without specific prior written permission.
2158f0484fSRodney W. Grimes *
2258f0484fSRodney W. Grimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
2358f0484fSRodney W. Grimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
2458f0484fSRodney W. Grimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
2558f0484fSRodney W. Grimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
2658f0484fSRodney W. Grimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
2758f0484fSRodney W. Grimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
2858f0484fSRodney W. Grimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
2958f0484fSRodney W. Grimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
3058f0484fSRodney W. Grimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
3158f0484fSRodney W. Grimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
3258f0484fSRodney W. Grimes * SUCH DAMAGE.
3358f0484fSRodney W. Grimes */
3458f0484fSRodney W. Grimes
3558f0484fSRodney W. Grimes #include <sys/param.h>
3658f0484fSRodney W. Grimes
3758f0484fSRodney W. Grimes #include <stdio.h>
3858f0484fSRodney W. Grimes #include <stdlib.h>
3958f0484fSRodney W. Grimes #include <string.h>
4058f0484fSRodney W. Grimes
4158f0484fSRodney W. Grimes #include <db.h>
4258f0484fSRodney W. Grimes #include "btree.h"
4358f0484fSRodney W. Grimes
4458f0484fSRodney W. Grimes /*
45ef5d438eSPaul Traina * __bt_ret --
46ef5d438eSPaul Traina * Build return key/data pair.
4758f0484fSRodney W. Grimes *
4858f0484fSRodney W. Grimes * Parameters:
4958f0484fSRodney W. Grimes * t: tree
50ef5d438eSPaul Traina * e: key/data pair to be returned
5158f0484fSRodney W. Grimes * key: user's key structure (NULL if not to be filled in)
52ef5d438eSPaul Traina * rkey: memory area to hold key
53ef5d438eSPaul Traina * data: user's data structure (NULL if not to be filled in)
54ef5d438eSPaul Traina * rdata: memory area to hold data
55ef5d438eSPaul Traina * copy: always copy the key/data item
5658f0484fSRodney W. Grimes *
5758f0484fSRodney W. Grimes * Returns:
5858f0484fSRodney W. Grimes * RET_SUCCESS, RET_ERROR.
5958f0484fSRodney W. Grimes */
6058f0484fSRodney W. Grimes int
__bt_ret(BTREE * t,EPG * e,DBT * key,DBT * rkey,DBT * data,DBT * rdata,int copy)610ac22237SXin LI __bt_ret(BTREE *t, EPG *e, DBT *key, DBT *rkey, DBT *data, DBT *rdata, int copy)
6258f0484fSRodney W. Grimes {
63ef5d438eSPaul Traina BLEAF *bl;
64ef5d438eSPaul Traina void *p;
6558f0484fSRodney W. Grimes
6658f0484fSRodney W. Grimes bl = GETBLEAF(e->page, e->index);
6758f0484fSRodney W. Grimes
6858f0484fSRodney W. Grimes /*
69f362c952Srilysh * We must copy big keys/data to make them contiguous. Otherwise,
70ef5d438eSPaul Traina * leave the page pinned and don't copy unless the user specified
7158f0484fSRodney W. Grimes * concurrent access.
7258f0484fSRodney W. Grimes */
73ef5d438eSPaul Traina if (key == NULL)
74ef5d438eSPaul Traina goto dataonly;
75ef5d438eSPaul Traina
76ef5d438eSPaul Traina if (bl->flags & P_BIGKEY) {
77ef5d438eSPaul Traina if (__ovfl_get(t, bl->bytes,
78ef5d438eSPaul Traina &key->size, &rkey->data, &rkey->size))
79ef5d438eSPaul Traina return (RET_ERROR);
80ef5d438eSPaul Traina key->data = rkey->data;
81ef5d438eSPaul Traina } else if (copy || F_ISSET(t, B_DB_LOCK)) {
82ef5d438eSPaul Traina if (bl->ksize > rkey->size) {
837ccf00dfSXin LI p = realloc(rkey->data, bl->ksize);
84ef5d438eSPaul Traina if (p == NULL)
85ef5d438eSPaul Traina return (RET_ERROR);
86ef5d438eSPaul Traina rkey->data = p;
87ef5d438eSPaul Traina rkey->size = bl->ksize;
88ef5d438eSPaul Traina }
89ef5d438eSPaul Traina memmove(rkey->data, bl->bytes, bl->ksize);
90ef5d438eSPaul Traina key->size = bl->ksize;
91ef5d438eSPaul Traina key->data = rkey->data;
92ef5d438eSPaul Traina } else {
93ef5d438eSPaul Traina key->size = bl->ksize;
94ef5d438eSPaul Traina key->data = bl->bytes;
95ef5d438eSPaul Traina }
96ef5d438eSPaul Traina
97ef5d438eSPaul Traina dataonly:
98ef5d438eSPaul Traina if (data == NULL)
99ef5d438eSPaul Traina return (RET_SUCCESS);
100ef5d438eSPaul Traina
10158f0484fSRodney W. Grimes if (bl->flags & P_BIGDATA) {
10258f0484fSRodney W. Grimes if (__ovfl_get(t, bl->bytes + bl->ksize,
103ef5d438eSPaul Traina &data->size, &rdata->data, &rdata->size))
10458f0484fSRodney W. Grimes return (RET_ERROR);
105ef5d438eSPaul Traina data->data = rdata->data;
106ef5d438eSPaul Traina } else if (copy || F_ISSET(t, B_DB_LOCK)) {
10758f0484fSRodney W. Grimes /* Use +1 in case the first record retrieved is 0 length. */
108ef5d438eSPaul Traina if (bl->dsize + 1 > rdata->size) {
1097ccf00dfSXin LI p = realloc(rdata->data, bl->dsize + 1);
110ef5d438eSPaul Traina if (p == NULL)
11158f0484fSRodney W. Grimes return (RET_ERROR);
112ef5d438eSPaul Traina rdata->data = p;
113ef5d438eSPaul Traina rdata->size = bl->dsize + 1;
11458f0484fSRodney W. Grimes }
115ef5d438eSPaul Traina memmove(rdata->data, bl->bytes + bl->ksize, bl->dsize);
11658f0484fSRodney W. Grimes data->size = bl->dsize;
117ef5d438eSPaul Traina data->data = rdata->data;
11858f0484fSRodney W. Grimes } else {
11958f0484fSRodney W. Grimes data->size = bl->dsize;
12058f0484fSRodney W. Grimes data->data = bl->bytes + bl->ksize;
12158f0484fSRodney W. Grimes }
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
__bt_cmp(BTREE * t,const DBT * k1,EPG * e)1400ac22237SXin LI __bt_cmp(BTREE *t, const DBT *k1, EPG *e)
14158f0484fSRodney W. Grimes {
14258f0484fSRodney W. Grimes BINTERNAL *bi;
14358f0484fSRodney W. Grimes BLEAF *bl;
14458f0484fSRodney W. Grimes DBT k2;
14558f0484fSRodney W. Grimes PAGE *h;
14658f0484fSRodney W. Grimes void *bigkey;
14758f0484fSRodney W. Grimes
14858f0484fSRodney W. Grimes /*
14958f0484fSRodney W. Grimes * The left-most key on internal pages, at any level of the tree, is
15058f0484fSRodney W. Grimes * guaranteed by the following code to be less than any user key.
15158f0484fSRodney W. Grimes * This saves us from having to update the leftmost key on an internal
15258f0484fSRodney W. Grimes * page when the user inserts a new key in the tree smaller than
15358f0484fSRodney W. Grimes * anything we've yet seen.
15458f0484fSRodney W. Grimes */
15558f0484fSRodney W. Grimes h = e->page;
15658f0484fSRodney W. Grimes if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF))
15758f0484fSRodney W. Grimes return (1);
15858f0484fSRodney W. Grimes
15958f0484fSRodney W. Grimes bigkey = NULL;
16058f0484fSRodney W. Grimes if (h->flags & P_BLEAF) {
16158f0484fSRodney W. Grimes bl = GETBLEAF(h, e->index);
16258f0484fSRodney W. Grimes if (bl->flags & P_BIGKEY)
16358f0484fSRodney W. Grimes bigkey = bl->bytes;
16458f0484fSRodney W. Grimes else {
16558f0484fSRodney W. Grimes k2.data = bl->bytes;
16658f0484fSRodney W. Grimes k2.size = bl->ksize;
16758f0484fSRodney W. Grimes }
16858f0484fSRodney W. Grimes } else {
16958f0484fSRodney W. Grimes bi = GETBINTERNAL(h, e->index);
17058f0484fSRodney W. Grimes if (bi->flags & P_BIGKEY)
17158f0484fSRodney W. Grimes bigkey = bi->bytes;
17258f0484fSRodney W. Grimes else {
17358f0484fSRodney W. Grimes k2.data = bi->bytes;
17458f0484fSRodney W. Grimes k2.size = bi->ksize;
17558f0484fSRodney W. Grimes }
17658f0484fSRodney W. Grimes }
17758f0484fSRodney W. Grimes
17858f0484fSRodney W. Grimes if (bigkey) {
17958f0484fSRodney W. Grimes if (__ovfl_get(t, bigkey,
180ef5d438eSPaul Traina &k2.size, &t->bt_rdata.data, &t->bt_rdata.size))
18158f0484fSRodney W. Grimes return (RET_ERROR);
182ef5d438eSPaul Traina k2.data = t->bt_rdata.data;
18358f0484fSRodney W. Grimes }
18458f0484fSRodney W. Grimes return ((*t->bt_cmp)(k1, &k2));
18558f0484fSRodney W. Grimes }
18658f0484fSRodney W. Grimes
18758f0484fSRodney W. Grimes /*
18858f0484fSRodney W. Grimes * __BT_DEFCMP -- Default comparison routine.
18958f0484fSRodney W. Grimes *
19058f0484fSRodney W. Grimes * Parameters:
19158f0484fSRodney W. Grimes * a: DBT #1
19258f0484fSRodney W. Grimes * b: DBT #2
19358f0484fSRodney W. Grimes *
19458f0484fSRodney W. Grimes * Returns:
19558f0484fSRodney W. Grimes * < 0 if a is < b
19658f0484fSRodney W. Grimes * = 0 if a is = b
19758f0484fSRodney W. Grimes * > 0 if a is > b
19858f0484fSRodney W. Grimes */
19958f0484fSRodney W. Grimes int
__bt_defcmp(const DBT * a,const DBT * b)2000ac22237SXin LI __bt_defcmp(const DBT *a, const DBT *b)
20158f0484fSRodney W. Grimes {
2028fb3f3f6SDavid E. O'Brien size_t len;
2038fb3f3f6SDavid E. O'Brien u_char *p1, *p2;
20458f0484fSRodney W. Grimes
20558f0484fSRodney W. Grimes /*
20658f0484fSRodney W. Grimes * XXX
20758f0484fSRodney W. Grimes * If a size_t doesn't fit in an int, this routine can lose.
2089d5abbddSJens Schweikhardt * What we need is an integral type which is guaranteed to be
20958f0484fSRodney W. Grimes * larger than a size_t, and there is no such thing.
21058f0484fSRodney W. Grimes */
21158f0484fSRodney W. Grimes len = MIN(a->size, b->size);
21258f0484fSRodney W. Grimes for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2)
21358f0484fSRodney W. Grimes if (*p1 != *p2)
21458f0484fSRodney W. Grimes return ((int)*p1 - (int)*p2);
21558f0484fSRodney W. Grimes return ((int)a->size - (int)b->size);
21658f0484fSRodney W. Grimes }
21758f0484fSRodney W. Grimes
21858f0484fSRodney W. Grimes /*
21958f0484fSRodney W. Grimes * __BT_DEFPFX -- Default prefix routine.
22058f0484fSRodney W. Grimes *
22158f0484fSRodney W. Grimes * Parameters:
22258f0484fSRodney W. Grimes * a: DBT #1
22358f0484fSRodney W. Grimes * b: DBT #2
22458f0484fSRodney W. Grimes *
22558f0484fSRodney W. Grimes * Returns:
22658f0484fSRodney W. Grimes * Number of bytes needed to distinguish b from a.
22758f0484fSRodney W. Grimes */
22858f0484fSRodney W. Grimes size_t
__bt_defpfx(const DBT * a,const DBT * b)2290ac22237SXin LI __bt_defpfx(const DBT *a, const DBT *b)
23058f0484fSRodney W. Grimes {
2318fb3f3f6SDavid E. O'Brien u_char *p1, *p2;
2328fb3f3f6SDavid E. O'Brien size_t cnt, len;
23358f0484fSRodney W. Grimes
23458f0484fSRodney W. Grimes cnt = 1;
23558f0484fSRodney W. Grimes len = MIN(a->size, b->size);
23658f0484fSRodney W. Grimes for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
23758f0484fSRodney W. Grimes if (*p1 != *p2)
23858f0484fSRodney W. Grimes return (cnt);
23958f0484fSRodney W. Grimes
24058f0484fSRodney W. Grimes /* a->size must be <= b->size, or they wouldn't be in this order. */
24158f0484fSRodney W. Grimes return (a->size < b->size ? a->size + 1 : a->size);
24258f0484fSRodney W. Grimes }
243