* Copyright (c) 1990, 1993
* The Regents of the University of California. All rights reserved.
* This code is derived from software contributed to Berkeley by
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. All advertising materials mentioning features or use of this software
* must display the following acknowledgement:
* This product includes software developed by the University of
* California, Berkeley and its contributors.
* 4. Neither the name of the University nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid
[] = "@(#)bt_utils.c 8.1 (Berkeley) 6/4/93";
#endif /* LIBC_SCCS and not lint */
* __BT_RET -- Build return key/data pair as a result of search or scan.
* d: LEAF to be returned to the user.
* key: user's key structure (NULL if not to be filled in)
* data: user's data structure
* RET_SUCCESS, RET_ERROR.
__bt_ret(t
, e
, key
, data
)
bl
= GETBLEAF(e
->page
, e
->index
);
if (bl
->flags
& P_BIGDATA
) {
if (__ovfl_get(t
, bl
->bytes
+ bl
->ksize
,
&data
->size
, &t
->bt_dbuf
, &t
->bt_dbufsz
))
/* Use +1 in case the first record retrieved is 0 length. */
if (bl
->dsize
+ 1 > t
->bt_dbufsz
) {
if ((p
= realloc(t
->bt_dbuf
, bl
->dsize
+ 1)) == NULL
)
t
->bt_dbufsz
= bl
->dsize
+ 1;
memmove(t
->bt_dbuf
, bl
->bytes
+ bl
->ksize
, bl
->dsize
);
if (bl
->flags
& P_BIGKEY
) {
if (__ovfl_get(t
, bl
->bytes
,
&key
->size
, &t
->bt_kbuf
, &t
->bt_kbufsz
))
if (bl
->ksize
> t
->bt_kbufsz
) {
if ((p
= realloc(t
->bt_kbuf
, bl
->ksize
)) == NULL
)
t
->bt_kbufsz
= bl
->ksize
;
memmove(t
->bt_kbuf
, bl
->bytes
, bl
->ksize
);
* __BT_CMP -- Compare a key to a given record.
* k1: DBT pointer of first arg to comparison
* e: pointer to EPG for comparison
* The left-most key on internal pages, at any level of the tree, is
* guaranteed by the following code to be less than any user key.
* This saves us from having to update the leftmost key on an internal
* page when the user inserts a new key in the tree smaller than
* anything we've yet seen.
if (e
->index
== 0 && h
->prevpg
== P_INVALID
&& !(h
->flags
& P_BLEAF
))
if (h
->flags
& P_BLEAF
) {
bl
= GETBLEAF(h
, e
->index
);
if (bl
->flags
& P_BIGKEY
)
bi
= GETBINTERNAL(h
, e
->index
);
if (bi
->flags
& P_BIGKEY
)
if (__ovfl_get(t
, bigkey
,
&k2
.size
, &t
->bt_dbuf
, &t
->bt_dbufsz
))
return ((*t
->bt_cmp
)(k1
, &k2
));
* __BT_DEFCMP -- Default comparison routine.
register u_char
*p1
, *p2
;
len
= MIN(a
->size
, b
->size
);
for (p1
= a
->data
, p2
= b
->data
; len
--; ++p1
, ++p2
)
return (a
->size
- b
->size
);
* __BT_DEFPFX -- Default prefix routine.
* Number of bytes needed to distinguish b from a.
register u_char
*p1
, *p2
;
len
= MIN(a
->size
, b
->size
);
for (p1
= a
->data
, p2
= b
->data
; len
--; ++p1
, ++p2
, ++cnt
)
/* a->size must be <= b->size, or they wouldn't be in this order. */
return (a
->size
< b
->size
? a
->size
+ 1 : a
->size
);