Asterisk - The Open Source Telephony Project  18.5.0
bt_seq.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_seq.c 8.7 (Berkeley) 7/20/94";
39 #endif /* LIBC_SCCS and not lint */
40 
41 #include <sys/types.h>
42 
43 #include <errno.h>
44 #include <stddef.h>
45 #include <stdio.h>
46 #include <stdlib.h>
47 
48 #include "../include/db.h"
49 #include "btree.h"
50 
51 static int __bt_first __P((BTREE *, const DBT *, EPG *, int *));
52 static int __bt_seqadv __P((BTREE *, EPG *, int));
53 static int __bt_seqset __P((BTREE *, EPG *, DBT *, int));
54 
55 /*
56  * Sequential scan support.
57  *
58  * The tree can be scanned sequentially, starting from either end of the
59  * tree or from any specific key. A scan request before any scanning is
60  * done is initialized as starting from the least node.
61  */
62 
63 /*
64  * __bt_seq --
65  * Btree sequential scan interface.
66  *
67  * Parameters:
68  * dbp: pointer to access method
69  * key: key for positioning and return value
70  * data: data return value
71  * flags: R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV.
72  *
73  * Returns:
74  * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
75  */
76 int
77 __bt_seq(dbp, key, data, flags)
78  const DB *dbp;
79  DBT *key, *data;
80  u_int flags;
81 {
82  BTREE *t;
83  EPG e;
84  int status;
85 
86  t = dbp->internal;
87 
88  /* Toss any page pinned across calls. */
89  if (t->bt_pinned != NULL) {
90  mpool_put(t->bt_mp, t->bt_pinned, 0);
91  t->bt_pinned = NULL;
92  }
93 
94  /*
95  * If scan uninitialized as yet, or starting at a specific record, set
96  * the scan to a specific key. Both __bt_seqset and __bt_seqadv pin
97  * the page the cursor references if they're successful.
98  */
99  switch (flags) {
100  case R_NEXT:
101  case R_PREV:
102  if (F_ISSET(&t->bt_cursor, CURS_INIT)) {
103  status = __bt_seqadv(t, &e, flags);
104  break;
105  }
106  /* FALLTHROUGH */
107  case R_FIRST:
108  case R_LAST:
109  case R_CURSOR:
110  status = __bt_seqset(t, &e, key, flags);
111  break;
112  default:
113  errno = EINVAL;
114  return (RET_ERROR);
115  }
116 
117  if (status == RET_SUCCESS) {
118  __bt_setcur(t, e.page->pgno, e.index);
119 
120  status =
121  __bt_ret(t, &e, key, &t->bt_rkey, data, &t->bt_rdata, 0);
122 
123  /*
124  * If the user is doing concurrent access, we copied the
125  * key/data, toss the page.
126  */
127  if (F_ISSET(t, B_DB_LOCK))
128  mpool_put(t->bt_mp, e.page, 0);
129  else
130  t->bt_pinned = e.page;
131  }
132  return (status);
133 }
134 
135 /*
136  * __bt_seqset --
137  * Set the sequential scan to a specific key.
138  *
139  * Parameters:
140  * t: tree
141  * ep: storage for returned key
142  * key: key for initial scan position
143  * flags: R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV
144  *
145  * Side effects:
146  * Pins the page the cursor references.
147  *
148  * Returns:
149  * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
150  */
151 static int
152 __bt_seqset(t, ep, key, flags)
153  BTREE *t;
154  EPG *ep;
155  DBT *key;
156  int flags;
157 {
158  PAGE *h;
159  pgno_t pg;
160  int exact;
161 
162  /*
163  * Find the first, last or specific key in the tree and point the
164  * cursor at it. The cursor may not be moved until a new key has
165  * been found.
166  */
167  switch (flags) {
168  case R_CURSOR: /* Keyed scan. */
169  /*
170  * Find the first instance of the key or the smallest key
171  * which is greater than or equal to the specified key.
172  */
173  if (key->data == NULL || key->size == 0) {
174  errno = EINVAL;
175  return (RET_ERROR);
176  }
177  return (__bt_first(t, key, ep, &exact));
178  case R_FIRST: /* First record. */
179  case R_NEXT:
180  /* Walk down the left-hand side of the tree. */
181  for (pg = P_ROOT;;) {
182  if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
183  return (RET_ERROR);
184 
185  /* Check for an empty tree. */
186  if (NEXTINDEX(h) == 0) {
187  mpool_put(t->bt_mp, h, 0);
188  return (RET_SPECIAL);
189  }
190 
191  if (h->flags & (P_BLEAF | P_RLEAF))
192  break;
193  pg = GETBINTERNAL(h, 0)->pgno;
194  mpool_put(t->bt_mp, h, 0);
195  }
196  ep->page = h;
197  ep->index = 0;
198  break;
199  case R_LAST: /* Last record. */
200  case R_PREV:
201  /* Walk down the right-hand side of the tree. */
202  for (pg = P_ROOT;;) {
203  if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
204  return (RET_ERROR);
205 
206  /* Check for an empty tree. */
207  if (NEXTINDEX(h) == 0) {
208  mpool_put(t->bt_mp, h, 0);
209  return (RET_SPECIAL);
210  }
211 
212  if (h->flags & (P_BLEAF | P_RLEAF))
213  break;
214  pg = GETBINTERNAL(h, NEXTINDEX(h) - 1)->pgno;
215  mpool_put(t->bt_mp, h, 0);
216  }
217 
218  ep->page = h;
219  ep->index = NEXTINDEX(h) - 1;
220  break;
221  }
222  return (RET_SUCCESS);
223 }
224 
225 /*
226  * __bt_seqadvance --
227  * Advance the sequential scan.
228  *
229  * Parameters:
230  * t: tree
231  * flags: R_NEXT, R_PREV
232  *
233  * Side effects:
234  * Pins the page the new key/data record is on.
235  *
236  * Returns:
237  * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
238  */
239 static int
240 __bt_seqadv(t, ep, flags)
241  BTREE *t;
242  EPG *ep;
243  int flags;
244 {
245  CURSOR *c;
246  PAGE *h;
247  indx_t index = 0;
248  pgno_t pg;
249  int exact;
250 
251  /*
252  * There are a couple of states that we can be in. The cursor has
253  * been initialized by the time we get here, but that's all we know.
254  */
255  c = &t->bt_cursor;
256 
257  /*
258  * The cursor was deleted where there weren't any duplicate records,
259  * so the key was saved. Find out where that key would go in the
260  * current tree. It doesn't matter if the returned key is an exact
261  * match or not -- if it's an exact match, the record was added after
262  * the delete so we can just return it. If not, as long as there's
263  * a record there, return it.
264  */
265  if (F_ISSET(c, CURS_ACQUIRE))
266  return (__bt_first(t, &c->key, ep, &exact));
267 
268  /* Get the page referenced by the cursor. */
269  if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL)
270  return (RET_ERROR);
271 
272  /*
273  * Find the next/previous record in the tree and point the cursor at
274  * it. The cursor may not be moved until a new key has been found.
275  */
276  switch (flags) {
277  case R_NEXT: /* Next record. */
278  /*
279  * The cursor was deleted in duplicate records, and moved
280  * forward to a record that has yet to be returned. Clear
281  * that flag, and return the record.
282  */
283  if (F_ISSET(c, CURS_AFTER))
284  goto usecurrent;
285  index = c->pg.index;
286  if (++index == NEXTINDEX(h)) {
287  pg = h->nextpg;
288  mpool_put(t->bt_mp, h, 0);
289  if (pg == P_INVALID)
290  return (RET_SPECIAL);
291  if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
292  return (RET_ERROR);
293  index = 0;
294  }
295  break;
296  case R_PREV: /* Previous record. */
297  /*
298  * The cursor was deleted in duplicate records, and moved
299  * backward to a record that has yet to be returned. Clear
300  * that flag, and return the record.
301  */
302  if (F_ISSET(c, CURS_BEFORE)) {
303 usecurrent: F_CLR(c, CURS_AFTER | CURS_BEFORE);
304  ep->page = h;
305  ep->index = c->pg.index;
306  return (RET_SUCCESS);
307  }
308  index = c->pg.index;
309  if (index == 0) {
310  pg = h->prevpg;
311  mpool_put(t->bt_mp, h, 0);
312  if (pg == P_INVALID)
313  return (RET_SPECIAL);
314  if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
315  return (RET_ERROR);
316  index = NEXTINDEX(h) - 1;
317  } else
318  --index;
319  break;
320  }
321 
322  ep->page = h;
323  ep->index = index;
324  return (RET_SUCCESS);
325 }
326 
327 /*
328  * __bt_first --
329  * Find the first entry.
330  *
331  * Parameters:
332  * t: the tree
333  * key: the key
334  * erval: return EPG
335  * exactp: pointer to exact match flag
336  *
337  * Returns:
338  * The first entry in the tree greater than or equal to key,
339  * or RET_SPECIAL if no such key exists.
340  */
341 static int
342 __bt_first(t, key, erval, exactp)
343  BTREE *t;
344  const DBT *key;
345  EPG *erval;
346  int *exactp;
347 {
348  PAGE *h;
349  EPG *ep, save;
350  pgno_t pg;
351 
352  /*
353  * Find any matching record; __bt_search pins the page.
354  *
355  * If it's an exact match and duplicates are possible, walk backwards
356  * in the tree until we find the first one. Otherwise, make sure it's
357  * a valid key (__bt_search may return an index just past the end of a
358  * page) and return it.
359  */
360  if ((ep = __bt_search(t, key, exactp)) == NULL)
361  return (RET_SPECIAL);
362  if (*exactp) {
363  if (F_ISSET(t, B_NODUPS)) {
364  *erval = *ep;
365  return (RET_SUCCESS);
366  }
367 
368  /*
369  * Walk backwards, as long as the entry matches and there are
370  * keys left in the tree. Save a copy of each match in case
371  * we go too far.
372  */
373  save = *ep;
374  h = ep->page;
375  do {
376  if (save.page->pgno != ep->page->pgno) {
377  mpool_put(t->bt_mp, save.page, 0);
378  save = *ep;
379  } else
380  save.index = ep->index;
381 
382  /*
383  * Don't unpin the page the last (or original) match
384  * was on, but make sure it's unpinned if an error
385  * occurs.
386  */
387  if (ep->index == 0) {
388  if (h->prevpg == P_INVALID)
389  break;
390  if (h->pgno != save.page->pgno)
391  mpool_put(t->bt_mp, h, 0);
392  if ((h = mpool_get(t->bt_mp,
393  h->prevpg, 0)) == NULL) {
394  if (h->pgno == save.page->pgno)
395  mpool_put(t->bt_mp,
396  save.page, 0);
397  return (RET_ERROR);
398  }
399  ep->page = h;
400  ep->index = NEXTINDEX(h);
401  }
402  --ep->index;
403  } while (__bt_cmp(t, key, ep) == 0);
404 
405  /*
406  * Reach here with the last page that was looked at pinned,
407  * which may or may not be the same as the last (or original)
408  * match page. If it's not useful, release it.
409  */
410  if (h->pgno != save.page->pgno)
411  mpool_put(t->bt_mp, h, 0);
412 
413  *erval = save;
414  return (RET_SUCCESS);
415  }
416 
417  /* If at the end of a page, find the next entry. */
418  if (ep->index == NEXTINDEX(ep->page)) {
419  h = ep->page;
420  pg = h->nextpg;
421  mpool_put(t->bt_mp, h, 0);
422  if (pg == P_INVALID)
423  return (RET_SPECIAL);
424  if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
425  return (RET_ERROR);
426  ep->index = 0;
427  ep->page = h;
428  }
429  *erval = *ep;
430  return (RET_SUCCESS);
431 }
432 
433 /*
434  * __bt_setcur --
435  * Set the cursor to an entry in the tree.
436  *
437  * Parameters:
438  * t: the tree
439  * pgno: page number
440  * index: page index
441  */
442 void
443 __bt_setcur(t, pgno, index)
444  BTREE *t;
445  pgno_t pgno;
446  u_int index;
447 {
448  /* Lose any already deleted key. */
449  if (t->bt_cursor.key.data != NULL) {
450  free(t->bt_cursor.key.data);
451  t->bt_cursor.key.size = 0;
452  t->bt_cursor.key.data = NULL;
453  }
455 
456  /* Update the cursor. */
457  t->bt_cursor.pg.pgno = pgno;
458  t->bt_cursor.pg.index = index;
459  F_SET(&t->bt_cursor, CURS_INIT);
460 }
#define R_CURSOR
Definition: db.h:91
Definition: btree.h:75
EPGNO pg
Definition: btree.h:284
void * data
Definition: db.h:86
#define NEXTINDEX(p)
Definition: btree.h:98
size_t size
Definition: db.h:87
#define RET_ERROR
Definition: db.h:51
pgno_t pgno
Definition: btree.h:76
#define F_SET(p, f)
Definition: btree.h:40
#define F_ISSET(p, f)
Definition: btree.h:42
int mpool_put(MPOOL *mp, void *page, u_int flags)
Definition: mpool.c:251
CURSOR bt_cursor
Definition: btree.h:320
static int __bt_seqadv(BTREE *t, EPG *ep, int flags)
Definition: bt_seq.c:240
Definition: btree.h:254
void * internal
Definition: db.h:137
indx_t index
Definition: btree.h:251
Definition: db.h:85
#define F_CLR(p, f)
Definition: btree.h:41
DBT bt_rkey
Definition: btree.h:332
static struct test_val c
#define NULL
Definition: resample.c:96
u_int16_t indx_t
Definition: db.h:80
#define GETBINTERNAL(pg, indx)
Definition: btree.h:138
Definition: btree.h:312
#define P_RLEAF
Definition: btree.h:84
int __bt_ret(BTREE *t, EPG *e, DBT *key, DBT *rkey, DBT *data, DBT *rdata, int copy)
Definition: bt_utils.c:67
#define R_LAST
Definition: db.h:96
void * mpool_get(MPOOL *mp, pgno_t pgno, u_int flags)
Definition: mpool.c:165
void free()
u_int32_t flags
Definition: btree.h:87
#define RET_SUCCESS
Definition: db.h:52
PAGE * bt_pinned
Definition: btree.h:318
DBT bt_rdata
Definition: btree.h:333
#define R_PREV
Definition: db.h:99
PAGE * page
Definition: btree.h:255
#define CURS_INIT
Definition: btree.h:291
MPOOL * bt_mp
Definition: btree.h:313
DBT key
Definition: btree.h:285
int __bt_cmp(BTREE *t, const DBT *k1, EPG *e)
Definition: bt_utils.c:153
static DB * dbp
Definition: hsearch.c:49
#define B_NODUPS
Definition: btree.h:374
u_int32_t pgno_t
Definition: db.h:78
Definition: btree.h:283
pgno_t nextpg
Definition: btree.h:78
indx_t index
Definition: btree.h:256
int errno
pgno_t prevpg
Definition: btree.h:77
static int __bt_first(BTREE *t, const DBT *key, EPG *erval, int *exactp)
Definition: bt_seq.c:342
#define CURS_AFTER
Definition: btree.h:289
#define R_NEXT
Definition: db.h:97
#define P_ROOT
Definition: btree.h:65
#define CURS_ACQUIRE
Definition: btree.h:288
#define R_FIRST
Definition: db.h:93
#define CURS_BEFORE
Definition: btree.h:290
pgno_t pgno
Definition: btree.h:250
void __bt_setcur(BTREE *t, pgno_t pgno, u_int index)
Definition: bt_seq.c:443
#define P_INVALID
Definition: btree.h:63
EPG * __bt_search(BTREE *t, const DBT *key, int *exactp)
Definition: bt_search.c:66
int __bt_seq(DB *dbp, DBT *key, DBT *data, u_int flags) const
Definition: bt_seq.c:77
Definition: db.h:129
#define RET_SPECIAL
Definition: db.h:53
static int __bt_seqset(BTREE *t, EPG *ep, DBT *key, int flags)
Definition: bt_seq.c:152
static int __bt_first __P((BTREE *, const DBT *, EPG *, int *))
#define P_BLEAF
Definition: btree.h:81
#define B_DB_LOCK
Definition: btree.h:385
jack_status_t status
Definition: app_jack.c:146