Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	lib/libc/db/btree/bt_utils.c	Lines:	0	72	0.0 %
Date:	2017-11-07	Branches:	0	52	0.0 %


/*	$OpenBSD: bt_utils.c,v 1.11 2015/01/16 16:48:51 deraadt Exp $	*/

/*-
 * Copyright (c) 1990, 1993, 1994
 *	The Regents of the University of California.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Mike Olson.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 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. 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
 * SUCH DAMAGE.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <db.h>
#include "btree.h"

#define MINIMUM(a, b)	(((a) < (b)) ? (a) : (b))

/*
 * __bt_ret --
 *	Build return key/data pair.
 *
 * Parameters:
 *	t:	tree
 *	e:	key/data pair to be returned
 *	key:	user's key structure (NULL if not to be filled in)
 *	rkey:	memory area to hold key
 *	data:	user's data structure (NULL if not to be filled in)
 *	rdata:	memory area to hold data
 *       copy:	always copy the key/data item
 *
 * Returns:
 *	RET_SUCCESS, RET_ERROR.
 */
int
__bt_ret(BTREE *t, EPG *e, DBT *key, DBT *rkey, DBT *data, DBT *rdata, int copy)
{
	BLEAF *bl;
	void *p;

	bl = GETBLEAF(e->page, e->index);

	/*
	 * We must copy big keys/data to make them contigous.  Otherwise,
	 * leave the page pinned and don't copy unless the user specified
	 * concurrent access.
	 */
	if (key == NULL)
		goto dataonly;

	if (bl->flags & P_BIGKEY) {
		if (__ovfl_get(t, bl->bytes,
		    &key->size, &rkey->data, &rkey->size))
			return (RET_ERROR);
		key->data = rkey->data;
	} else if (copy || F_ISSET(t, B_DB_LOCK)) {
		if (bl->ksize > rkey->size) {
			p = realloc(rkey->data, bl->ksize);
			if (p == NULL)
				return (RET_ERROR);
			rkey->data = p;
			rkey->size = bl->ksize;
		}
		memmove(rkey->data, bl->bytes, bl->ksize);
		key->size = bl->ksize;
		key->data = rkey->data;
	} else {
		key->size = bl->ksize;
		key->data = bl->bytes;
	}

dataonly:
	if (data == NULL)
		return (RET_SUCCESS);

	if (bl->flags & P_BIGDATA) {
		if (__ovfl_get(t, bl->bytes + bl->ksize,
		    &data->size, &rdata->data, &rdata->size))
			return (RET_ERROR);
		data->data = rdata->data;
	} else if (copy || F_ISSET(t, B_DB_LOCK)) {
		/* Use +1 in case the first record retrieved is 0 length. */
		if (bl->dsize + 1 > rdata->size) {
			p = realloc(rdata->data, bl->dsize + 1);
			if (p == NULL)
				return (RET_ERROR);
			rdata->data = p;
			rdata->size = bl->dsize + 1;
		}
		memmove(rdata->data, bl->bytes + bl->ksize, bl->dsize);
		data->size = bl->dsize;
		data->data = rdata->data;
	} else {
		data->size = bl->dsize;
		data->data = bl->bytes + bl->ksize;
	}

	return (RET_SUCCESS);
}

/*
 * __BT_CMP -- Compare a key to a given record.
 *
 * Parameters:
 *	t:	tree
 *	k1:	DBT pointer of first arg to comparison
 *	e:	pointer to EPG for comparison
 *
 * Returns:
 *	< 0 if k1 is < record
 *	= 0 if k1 is = record
 *	> 0 if k1 is > record
 */
int
__bt_cmp(BTREE *t, const DBT *k1, EPG *e)
{
	BINTERNAL *bi;
	BLEAF *bl;
	DBT k2;
	PAGE *h;
	void *bigkey;

	/*
	 * 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.
	 */
	h = e->page;
	if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF))
		return (1);

	bigkey = NULL;
	if (h->flags & P_BLEAF) {
		bl = GETBLEAF(h, e->index);
		if (bl->flags & P_BIGKEY)
			bigkey = bl->bytes;
		else {
			k2.data = bl->bytes;
			k2.size = bl->ksize;
		}
	} else {
		bi = GETBINTERNAL(h, e->index);
		if (bi->flags & P_BIGKEY)
			bigkey = bi->bytes;
		else {
			k2.data = bi->bytes;
			k2.size = bi->ksize;
		}
	}

	if (bigkey) {
		if (__ovfl_get(t, bigkey,
		    &k2.size, &t->bt_rdata.data, &t->bt_rdata.size))
			return (RET_ERROR);
		k2.data = t->bt_rdata.data;
	}
	return ((*t->bt_cmp)(k1, &k2));
}

/*
 * __BT_DEFCMP -- Default comparison routine.
 *
 * Parameters:
 *	a:	DBT #1
 *	b: 	DBT #2
 *
 * Returns:
 *	< 0 if a is < b
 *	= 0 if a is = b
 *	> 0 if a is > b
 */
int
__bt_defcmp(const DBT *a, const DBT *b)
{
	size_t len;
	u_char *p1, *p2;

	/*
	 * XXX
	 * If a size_t doesn't fit in an int, this routine can lose.
	 * What we need is a integral type which is guaranteed to be
	 * larger than a size_t, and there is no such thing.
	 */
	len = MINIMUM(a->size, b->size);
	for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2)
		if (*p1 != *p2)
			return ((int)*p1 - (int)*p2);
	return ((int)a->size - (int)b->size);
}

/*
 * __BT_DEFPFX -- Default prefix routine.
 *
 * Parameters:
 *	a:	DBT #1
 *	b: 	DBT #2
 *
 * Returns:
 *	Number of bytes needed to distinguish b from a.
 */
size_t
__bt_defpfx(a, b)
	const DBT *a, *b;
{
	u_char *p1, *p2;
	size_t cnt, len;

	cnt = 1;
	len = MINIMUM(a->size, b->size);
	for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
		if (*p1 != *p2)
			return (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);
}


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
1			/* $OpenBSD: bt_utils.c,v 1.11 2015/01/16 16:48:51 deraadt Exp $ */
2
3			/*-
4			* Copyright (c) 1990, 1993, 1994
5			* The Regents of the University of California. All rights reserved.
6			*
7			* This code is derived from software contributed to Berkeley by
8			* Mike Olson.
9			*
10			* Redistribution and use in source and binary forms, with or without
11			* modification, are permitted provided that the following conditions
12			* are met:
13			* 1. Redistributions of source code must retain the above copyright
14			* notice, this list of conditions and the following disclaimer.
15			* 2. Redistributions in binary form must reproduce the above copyright
16			* notice, this list of conditions and the following disclaimer in the
17			* documentation and/or other materials provided with the distribution.
18			* 3. Neither the name of the University nor the names of its contributors
19			* may be used to endorse or promote products derived from this software
20			* without specific prior written permission.
21			*
22			* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23			* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24			* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25			* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26			* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27			* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28			* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29			* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30			* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31			* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32			* SUCH DAMAGE.
33			*/
34
35			#include <stdio.h>
36			#include <stdlib.h>
37			#include <string.h>
38
39			#include <db.h>
40			#include "btree.h"
41
42			#define MINIMUM(a, b) (((a) < (b)) ? (a) : (b))
43
44			/*
45			* __bt_ret --
46			* Build return key/data pair.
47			*
48			* Parameters:
49			* t: tree
50			* e: key/data pair to be returned
51			* key: user's key structure (NULL if not to be filled in)
52			* rkey: memory area to hold key
53			* data: user's data structure (NULL if not to be filled in)
54			* rdata: memory area to hold data
55			* copy: always copy the key/data item
56			*
57			* Returns:
58			* RET_SUCCESS, RET_ERROR.
59			*/
60			int
61			__bt_ret(BTREE t, EPG e, DBT key, DBT rkey, DBT data, DBT rdata, int copy)
62			{
63			BLEAF *bl;
64			void *p;
65
66			bl = GETBLEAF(e->page, e->index);
67
68			/*
69			* We must copy big keys/data to make them contigous. Otherwise,
70			* leave the page pinned and don't copy unless the user specified
71			* concurrent access.
72			*/
73			if (key == NULL)
74			goto dataonly;
75
76			if (bl->flags & P_BIGKEY) {
77			if (__ovfl_get(t, bl->bytes,
78			&key->size, &rkey->data, &rkey->size))
79			return (RET_ERROR);
80			key->data = rkey->data;
81			} else if (copy \|\| F_ISSET(t, B_DB_LOCK)) {
82			if (bl->ksize > rkey->size) {
83			p = realloc(rkey->data, bl->ksize);
84			if (p == NULL)
85			return (RET_ERROR);
86			rkey->data = p;
87			rkey->size = bl->ksize;
88			}
89			memmove(rkey->data, bl->bytes, bl->ksize);
90			key->size = bl->ksize;
91			key->data = rkey->data;
92			} else {
93			key->size = bl->ksize;
94			key->data = bl->bytes;
95			}
96
97			dataonly:
98			if (data == NULL)
99			return (RET_SUCCESS);
100
101			if (bl->flags & P_BIGDATA) {
102			if (__ovfl_get(t, bl->bytes + bl->ksize,
103			&data->size, &rdata->data, &rdata->size))
104			return (RET_ERROR);
105			data->data = rdata->data;
106			} else if (copy \|\| F_ISSET(t, B_DB_LOCK)) {
107			/* Use +1 in case the first record retrieved is 0 length. */
108			if (bl->dsize + 1 > rdata->size) {
109			p = realloc(rdata->data, bl->dsize + 1);
110			if (p == NULL)
111			return (RET_ERROR);
112			rdata->data = p;
113			rdata->size = bl->dsize + 1;
114			}
115			memmove(rdata->data, bl->bytes + bl->ksize, bl->dsize);
116			data->size = bl->dsize;
117			data->data = rdata->data;
118			} else {
119			data->size = bl->dsize;
120			data->data = bl->bytes + bl->ksize;
121			}
122
123			return (RET_SUCCESS);
124			}
125
126			/*
127			* __BT_CMP -- Compare a key to a given record.
128			*
129			* Parameters:
130			* t: tree
131			* k1: DBT pointer of first arg to comparison
132			* e: pointer to EPG for comparison
133			*
134			* Returns:
135			* < 0 if k1 is < record
136			* = 0 if k1 is = record
137			* > 0 if k1 is > record
138			*/
139			int
140			__bt_cmp(BTREE t, const DBT k1, EPG *e)
141			{
142			BINTERNAL *bi;
143			BLEAF *bl;
144			DBT k2;
145			PAGE *h;
146			void *bigkey;
147
148			/*
149			* The left-most key on internal pages, at any level of the tree, is
150			* guaranteed by the following code to be less than any user key.
151			* This saves us from having to update the leftmost key on an internal
152			* page when the user inserts a new key in the tree smaller than
153			* anything we've yet seen.
154			*/
155			h = e->page;
156			if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF))
157			return (1);
158
159			bigkey = NULL;
160			if (h->flags & P_BLEAF) {
161			bl = GETBLEAF(h, e->index);
162			if (bl->flags & P_BIGKEY)
163			bigkey = bl->bytes;
164			else {
165			k2.data = bl->bytes;
166			k2.size = bl->ksize;
167			}
168			} else {
169			bi = GETBINTERNAL(h, e->index);
170			if (bi->flags & P_BIGKEY)
171			bigkey = bi->bytes;
172			else {
173			k2.data = bi->bytes;
174			k2.size = bi->ksize;
175			}
176			}
177
178			if (bigkey) {
179			if (__ovfl_get(t, bigkey,
180			&k2.size, &t->bt_rdata.data, &t->bt_rdata.size))
181			return (RET_ERROR);
182			k2.data = t->bt_rdata.data;
183			}
184			return ((*t->bt_cmp)(k1, &k2));
185			}
186
187			/*
188			* __BT_DEFCMP -- Default comparison routine.
189			*
190			* Parameters:
191			* a: DBT #1
192			* b: DBT #2
193			*
194			* Returns:
195			* < 0 if a is < b
196			* = 0 if a is = b
197			* > 0 if a is > b
198			*/
199			int
200			__bt_defcmp(const DBT a, const DBT b)
201			{
202			size_t len;
203			u_char p1, p2;
204
205			/*
206			* XXX
207			* If a size_t doesn't fit in an int, this routine can lose.
208			* What we need is a integral type which is guaranteed to be
209			* larger than a size_t, and there is no such thing.
210			*/
211			len = MINIMUM(a->size, b->size);
212			for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2)
213			if (p1 != p2)
214			return ((int)p1 - (int)p2);
215			return ((int)a->size - (int)b->size);
216			}
217
218			/*
219			* __BT_DEFPFX -- Default prefix routine.
220			*
221			* Parameters:
222			* a: DBT #1
223			* b: DBT #2
224			*
225			* Returns:
226			* Number of bytes needed to distinguish b from a.
227			*/
228			size_t
229			__bt_defpfx(a, b)
230			const DBT a, b;
231			{
232			u_char p1, p2;
233			size_t cnt, len;
234
235			cnt = 1;
236			len = MINIMUM(a->size, b->size);
237			for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
238			if (p1 != p2)
239			return (cnt);
240
241			/* a->size must be <= b->size, or they wouldn't be in this order. */
242			return (a->size < b->size ? a->size + 1 : a->size);
243			}