Asterisk - The Open Source Telephony Project  GIT-master-b7027de
Functions
bt_seq.c File Reference
#include <sys/types.h>
#include <errno.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include "../include/db.h"
#include "btree.h"

Go to the source code of this file.

Functions

static int __bt_first (BTREE *t, const DBT *key, EPG *erval, int *exactp)
 
int __bt_seq (DB *dbp, DBT *key, DBT *data, u_int flags) const
 
static int __bt_seqadv (BTREE *t, EPG *ep, int flags)
 
static int __bt_seqset (BTREE *t, EPG *ep, DBT *key, int flags)
 
void __bt_setcur (BTREE *t, pgno_t pgno, u_int index)
 
static int __bt_first __P ((BTREE *, const DBT *, EPG *, int *))
 
static int __bt_seqadv __P ((BTREE *, EPG *, int))
 
static int __bt_seqset __P ((BTREE *, EPG *, DBT *, int))
 

Function Documentation

◆ __bt_first()

static int __bt_first ( BTREE t,
const DBT key,
EPG erval,
int *  exactp 
)
static

Definition at line 342 of file bt_seq.c.

References __bt_cmp(), __bt_search(), B_NODUPS, _btree::bt_mp, F_ISSET, _epg::index, mpool_get(), mpool_put(), NEXTINDEX, _page::nextpg, NULL, P_INVALID, _epg::page, _page::pgno, _page::prevpg, RET_ERROR, RET_SPECIAL, and RET_SUCCESS.

Referenced by __bt_seqadv(), and __bt_seqset().

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 }
Definition: btree.h:75
#define NEXTINDEX(p)
Definition: btree.h:98
#define RET_ERROR
Definition: db.h:51
pgno_t pgno
Definition: btree.h:76
#define F_ISSET(p, f)
Definition: btree.h:42
int mpool_put(MPOOL *mp, void *page, u_int flags)
Definition: mpool.c:251
Definition: btree.h:254
#define NULL
Definition: resample.c:96
void * mpool_get(MPOOL *mp, pgno_t pgno, u_int flags)
Definition: mpool.c:165
#define RET_SUCCESS
Definition: db.h:52
PAGE * page
Definition: btree.h:255
MPOOL * bt_mp
Definition: btree.h:313
int __bt_cmp(BTREE *t, const DBT *k1, EPG *e)
Definition: bt_utils.c:153
#define B_NODUPS
Definition: btree.h:374
u_int32_t pgno_t
Definition: db.h:78
pgno_t nextpg
Definition: btree.h:78
indx_t index
Definition: btree.h:256
pgno_t prevpg
Definition: btree.h:77
#define P_INVALID
Definition: btree.h:63
EPG * __bt_search(BTREE *t, const DBT *key, int *exactp)
Definition: bt_search.c:66
#define RET_SPECIAL
Definition: db.h:53

◆ __bt_seq()

int __bt_seq ( DB dbp,
DBT key,
DBT data,
u_int  flags 
) const

Definition at line 77 of file bt_seq.c.

References __bt_ret(), __bt_seqadv(), __bt_seqset(), __bt_setcur(), B_DB_LOCK, _btree::bt_cursor, _btree::bt_mp, _btree::bt_pinned, _btree::bt_rdata, _btree::bt_rkey, CURS_INIT, errno, F_ISSET, _epg::index, __db::internal, mpool_put(), NULL, _epg::page, _page::pgno, R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV, RET_ERROR, RET_SUCCESS, and status.

Referenced by __bt_open().

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 }
#define R_CURSOR
Definition: db.h:91
#define RET_ERROR
Definition: db.h:51
pgno_t pgno
Definition: btree.h:76
#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
DBT bt_rkey
Definition: btree.h:332
#define NULL
Definition: resample.c:96
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 R_LAST
Definition: db.h:96
#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
indx_t index
Definition: btree.h:256
int errno
#define R_NEXT
Definition: db.h:97
#define R_FIRST
Definition: db.h:93
void __bt_setcur(BTREE *t, pgno_t pgno, u_int index)
Definition: bt_seq.c:443
static int __bt_seqset(BTREE *t, EPG *ep, DBT *key, int flags)
Definition: bt_seq.c:152
#define B_DB_LOCK
Definition: btree.h:385
jack_status_t status
Definition: app_jack.c:146

◆ __bt_seqadv()

static int __bt_seqadv ( BTREE t,
EPG ep,
int  flags 
)
static

Definition at line 240 of file bt_seq.c.

References __bt_first(), _btree::bt_cursor, _btree::bt_mp, c, CURS_ACQUIRE, CURS_AFTER, CURS_BEFORE, F_CLR, F_ISSET, _epgno::index, _epg::index, _cursor::key, mpool_get(), mpool_put(), NEXTINDEX, _page::nextpg, NULL, P_INVALID, _epg::page, _cursor::pg, _epgno::pgno, _page::prevpg, R_NEXT, R_PREV, RET_ERROR, RET_SPECIAL, and RET_SUCCESS.

Referenced by __bt_seq().

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 }
Definition: btree.h:75
EPGNO pg
Definition: btree.h:284
#define NEXTINDEX(p)
Definition: btree.h:98
#define RET_ERROR
Definition: db.h:51
#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
indx_t index
Definition: btree.h:251
#define F_CLR(p, f)
Definition: btree.h:41
static struct test_val c
#define NULL
Definition: resample.c:96
u_int16_t indx_t
Definition: db.h:80
void * mpool_get(MPOOL *mp, pgno_t pgno, u_int flags)
Definition: mpool.c:165
#define RET_SUCCESS
Definition: db.h:52
#define R_PREV
Definition: db.h:99
PAGE * page
Definition: btree.h:255
MPOOL * bt_mp
Definition: btree.h:313
DBT key
Definition: btree.h:285
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
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 CURS_ACQUIRE
Definition: btree.h:288
#define CURS_BEFORE
Definition: btree.h:290
pgno_t pgno
Definition: btree.h:250
#define P_INVALID
Definition: btree.h:63
#define RET_SPECIAL
Definition: db.h:53

◆ __bt_seqset()

static int __bt_seqset ( BTREE t,
EPG ep,
DBT key,
int  flags 
)
static

Definition at line 152 of file bt_seq.c.

References __bt_first(), _btree::bt_mp, DBT::data, errno, _page::flags, GETBINTERNAL, _epg::index, mpool_get(), mpool_put(), NEXTINDEX, NULL, P_BLEAF, P_RLEAF, P_ROOT, _epg::page, R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV, RET_ERROR, RET_SPECIAL, RET_SUCCESS, and DBT::size.

Referenced by __bt_seq().

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 }
#define R_CURSOR
Definition: db.h:91
Definition: btree.h:75
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
int mpool_put(MPOOL *mp, void *page, u_int flags)
Definition: mpool.c:251
#define NULL
Definition: resample.c:96
#define GETBINTERNAL(pg, indx)
Definition: btree.h:138
#define P_RLEAF
Definition: btree.h:84
#define R_LAST
Definition: db.h:96
void * mpool_get(MPOOL *mp, pgno_t pgno, u_int flags)
Definition: mpool.c:165
u_int32_t flags
Definition: btree.h:87
#define RET_SUCCESS
Definition: db.h:52
#define R_PREV
Definition: db.h:99
PAGE * page
Definition: btree.h:255
MPOOL * bt_mp
Definition: btree.h:313
u_int32_t pgno_t
Definition: db.h:78
indx_t index
Definition: btree.h:256
int errno
static int __bt_first(BTREE *t, const DBT *key, EPG *erval, int *exactp)
Definition: bt_seq.c:342
#define R_NEXT
Definition: db.h:97
#define P_ROOT
Definition: btree.h:65
#define R_FIRST
Definition: db.h:93
#define RET_SPECIAL
Definition: db.h:53
#define P_BLEAF
Definition: btree.h:81

◆ __bt_setcur()

void __bt_setcur ( BTREE t,
pgno_t  pgno,
u_int  index 
)

Definition at line 443 of file bt_seq.c.

References _btree::bt_cursor, CURS_ACQUIRE, CURS_AFTER, CURS_BEFORE, CURS_INIT, DBT::data, F_CLR, F_SET, free(), _epgno::index, _cursor::key, NULL, _cursor::pg, _epgno::pgno, and DBT::size.

Referenced by __bt_put(), and __bt_seq().

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 }
EPGNO pg
Definition: btree.h:284
void * data
Definition: db.h:86
size_t size
Definition: db.h:87
#define F_SET(p, f)
Definition: btree.h:40
CURSOR bt_cursor
Definition: btree.h:320
indx_t index
Definition: btree.h:251
#define F_CLR(p, f)
Definition: btree.h:41
#define NULL
Definition: resample.c:96
void free()
#define CURS_INIT
Definition: btree.h:291
DBT key
Definition: btree.h:285
#define CURS_AFTER
Definition: btree.h:289
#define CURS_ACQUIRE
Definition: btree.h:288
#define CURS_BEFORE
Definition: btree.h:290
pgno_t pgno
Definition: btree.h:250

◆ __P() [1/3]

static int __bt_first __P ( (BTREE *, const DBT *, EPG *, int *)  )
static

◆ __P() [2/3]

static int __bt_seqadv __P ( (BTREE *, EPG *, int)  )
static

◆ __P() [3/3]

static int __bt_seqset __P ( (BTREE *, EPG *, DBT *, int)  )
static