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

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
}