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