Asterisk - The Open Source Telephony Project  18.5.0
Data Structures | Macros | Typedefs
btree.h File Reference
#include <mpool.h>
#include "extern.h"
Include dependency graph for btree.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  _binternal
 
struct  _bleaf
 
struct  _btmeta
 
struct  _btree
 
struct  _cursor
 
struct  _epg
 
struct  _epgno
 
struct  _page
 
struct  _rinternal
 
struct  _rleaf
 

Macros

#define B_DB_LOCK   0x04000 /* DB_LOCK specified. */
 
#define B_DB_SHMEM   0x08000 /* DB_SHMEM specified. */
 
#define B_DB_TXN   0x10000 /* DB_TXN specified. */
 
#define B_INMEM   0x00001 /* in-memory tree */
 
#define B_METADIRTY   0x00002 /* need to write metadata */
 
#define B_MODIFIED   0x00004 /* tree modified */
 
#define B_NEEDSWAP   0x00008 /* if byte order requires swapping */
 
#define B_NODUPS   0x00020 /* no duplicate keys permitted */
 
#define B_RDONLY   0x00010 /* read-only tree */
 
#define BT_CLR(t)   (t->bt_sp = t->bt_stack)
 
#define BT_POP(t)   (t->bt_sp == t->bt_stack ? NULL : --t->bt_sp)
 
#define BT_PUSH(t, p, i)
 
#define BTDATAOFF
 
#define CURS_ACQUIRE   0x01 /* B: Cursor needs to be reacquired. */
 
#define CURS_AFTER   0x02 /* B: Unreturned cursor after key. */
 
#define CURS_BEFORE   0x04 /* B: Unreturned cursor before key. */
 
#define CURS_INIT   0x08 /* RB: Cursor initialized. */
 
#define DEFMINKEYPAGE   (2) /* Minimum keys per page */
 
#define F_CLR(p, f)   (p)->flags &= ~(f)
 
#define F_ISSET(p, f)   ((p)->flags & (f))
 
#define F_SET(p, f)   (p)->flags |= (f)
 
#define GETBINTERNAL(pg, indx)   ((BINTERNAL *)((char *)(pg) + (pg)->linp[indx]))
 
#define GETBLEAF(pg, indx)   ((BLEAF *)((char *)(pg) + (pg)->linp[indx]))
 
#define GETRINTERNAL(pg, indx)   ((RINTERNAL *)((char *)(pg) + (pg)->linp[indx]))
 
#define GETRLEAF(pg, indx)   ((RLEAF *)((char *)(pg) + (pg)->linp[indx]))
 
#define LALIGN(n)   (((n) + sizeof(pgno_t) - 1) & ~(sizeof(pgno_t) - 1))
 
#define MINCACHE   (5) /* Minimum cached pages */
 
#define MINPSIZE   (512) /* Minimum page size */
 
#define mpool_close   __mpool_close
 
#define mpool_filter   __mpool_filter
 
#define mpool_get   __mpool_get
 
#define mpool_new   __mpool_new
 
#define mpool_open   __mpool_open
 
#define mpool_put   __mpool_put
 
#define mpool_sync   __mpool_sync
 
#define NBINTERNAL(len)   LALIGN(sizeof(u_int32_t) + sizeof(pgno_t) + sizeof(u_char) + (len))
 
#define NBLEAF(p)   NBLEAFDBT((p)->ksize, (p)->dsize)
 
#define NBLEAFDBT(ksize, dsize)
 
#define NEXTINDEX(p)   (((p)->lower - BTDATAOFF) / sizeof(indx_t))
 
#define NOVFLSIZE   (sizeof(pgno_t) + sizeof(u_int32_t))
 
#define NRINTERNAL   LALIGN(sizeof(recno_t) + sizeof(pgno_t))
 
#define NRLEAF(p)   NRLEAFDBT((p)->dsize)
 
#define NRLEAFDBT(dsize)   LALIGN(sizeof(u_int32_t) + sizeof(u_char) + (dsize))
 
#define P_BIGDATA   0x01 /* overflow data */
 
#define P_BIGKEY   0x02 /* overflow key */
 
#define P_BINTERNAL   0x01 /* btree internal page */
 
#define P_BLEAF   0x02 /* leaf page */
 
#define P_INVALID   0 /* Invalid tree page number. */
 
#define P_META   0 /* Tree metadata page number. */
 
#define P_OVERFLOW   0x04 /* overflow page */
 
#define P_PRESERVE   0x20 /* never delete this chain of pages */
 
#define P_RINTERNAL   0x08 /* recno internal page */
 
#define P_RLEAF   0x10 /* leaf page */
 
#define P_ROOT   1 /* Tree root page number. */
 
#define P_TYPE   0x1f /* type mask */
 
#define R_CLOSEFP   0x00040 /* opened a file pointer */
 
#define R_EOF   0x00100 /* end of input file reached. */
 
#define R_FIXLEN   0x00200 /* fixed length records */
 
#define R_INMEM   0x00800 /* in-memory file */
 
#define R_MEMMAPPED   0x00400 /* memory mapped file. */
 
#define R_MODIFIED   0x01000 /* modified file */
 
#define R_RDONLY   0x02000 /* read-only file */
 
#define R_RECNO   0x00080 /* record oriented tree */
 
#define SAVEMETA   (B_NODUPS | R_RECNO)
 
#define WR_BINTERNAL(p, size, pgno, flags)
 
#define WR_BLEAF(p, key, data, flags)
 
#define WR_RINTERNAL(p, nrecs, pgno)
 
#define WR_RLEAF(p, data, flags)
 

Typedefs

typedef struct _binternal BINTERNAL
 
typedef struct _bleaf BLEAF
 
typedef struct _btmeta BTMETA
 
typedef struct _btree BTREE
 
typedef struct _cursor CURSOR
 
typedef struct _epg EPG
 
typedef struct _epgno EPGNO
 
typedef struct _page PAGE
 
typedef struct _rinternal RINTERNAL
 
typedef struct _rleaf RLEAF
 

Macro Definition Documentation

◆ B_DB_LOCK

#define B_DB_LOCK   0x04000 /* DB_LOCK specified. */

Definition at line 385 of file btree.h.

Referenced by __bt_get(), __bt_open(), __bt_ret(), __bt_seq(), __rec_get(), __rec_ret(), and __rec_seq().

◆ B_DB_SHMEM

#define B_DB_SHMEM   0x08000 /* DB_SHMEM specified. */

Definition at line 386 of file btree.h.

Referenced by __bt_open().

◆ B_DB_TXN

#define B_DB_TXN   0x10000 /* DB_TXN specified. */

Definition at line 387 of file btree.h.

Referenced by __bt_open().

◆ B_INMEM

#define B_INMEM   0x00001 /* in-memory tree */

Definition at line 368 of file btree.h.

Referenced by __bt_fd(), __bt_open(), and __bt_sync().

◆ B_METADIRTY

#define B_METADIRTY   0x00002 /* need to write metadata */

Definition at line 369 of file btree.h.

Referenced by __bt_free(), __bt_new(), __bt_open(), and __bt_sync().

◆ B_MODIFIED

#define B_MODIFIED   0x00004 /* tree modified */

Definition at line 370 of file btree.h.

Referenced by __bt_delete(), __bt_put(), __bt_sync(), __rec_delete(), and __rec_iput().

◆ B_NEEDSWAP

#define B_NEEDSWAP   0x00008 /* if byte order requires swapping */

Definition at line 371 of file btree.h.

Referenced by __bt_open(), __bt_pgin(), and __bt_pgout().

◆ B_NODUPS

#define B_NODUPS   0x00020 /* no duplicate keys permitted */

Definition at line 374 of file btree.h.

Referenced by __bt_bdelete(), __bt_curdel(), __bt_first(), __bt_open(), __bt_put(), and __bt_search().

◆ B_RDONLY

#define B_RDONLY   0x00010 /* read-only tree */

Definition at line 372 of file btree.h.

Referenced by __bt_delete(), __bt_open(), __bt_put(), and __bt_sync().

◆ BT_CLR

#define BT_CLR (   t)    (t->bt_sp = t->bt_stack)

Definition at line 328 of file btree.h.

Referenced by __bt_search(), and __rec_search().

◆ BT_POP

#define BT_POP (   t)    (t->bt_sp == t->bt_stack ? NULL : --t->bt_sp)

Definition at line 327 of file btree.h.

Referenced by __bt_pdelete(), __bt_split(), __bt_stkacq(), and __rec_search().

◆ BT_PUSH

#define BT_PUSH (   t,
  p,
 
)
Value:
{ \
t->bt_sp->pgno = p; \
t->bt_sp->index = i; \
++t->bt_sp; \
}

Definition at line 322 of file btree.h.

Referenced by __bt_search(), __bt_stkacq(), and __rec_search().

◆ BTDATAOFF

#define BTDATAOFF
Value:
(sizeof(pgno_t) + sizeof(pgno_t) + sizeof(pgno_t) + \
sizeof(u_int32_t) + sizeof(indx_t) + sizeof(indx_t))
u_int16_t indx_t
Definition: db.h:80
u_int32_t pgno_t
Definition: db.h:78
unsigned int u_int32_t

Definition at line 95 of file btree.h.

Referenced by __bt_open(), __bt_pdelete(), __ovfl_delete(), __ovfl_get(), __ovfl_put(), bt_broot(), bt_page(), bt_psplit(), bt_root(), bt_rroot(), and nroot().

◆ CURS_ACQUIRE

#define CURS_ACQUIRE   0x01 /* B: Cursor needs to be reacquired. */

Definition at line 288 of file btree.h.

Referenced by __bt_curdel(), __bt_delete(), __bt_dleaf(), __bt_put(), __bt_seqadv(), and __bt_setcur().

◆ CURS_AFTER

#define CURS_AFTER   0x02 /* B: Unreturned cursor after key. */

Definition at line 289 of file btree.h.

Referenced by __bt_curdel(), __bt_delete(), __bt_put(), __bt_seqadv(), and __bt_setcur().

◆ CURS_BEFORE

#define CURS_BEFORE   0x04 /* B: Unreturned cursor before key. */

Definition at line 290 of file btree.h.

Referenced by __bt_curdel(), __bt_delete(), __bt_put(), __bt_seqadv(), and __bt_setcur().

◆ CURS_INIT

#define CURS_INIT   0x08 /* RB: Cursor initialized. */

◆ DEFMINKEYPAGE

#define DEFMINKEYPAGE   (2) /* Minimum keys per page */

Definition at line 54 of file btree.h.

Referenced by __bt_open().

◆ F_CLR

#define F_CLR (   p,
 
)    (p)->flags &= ~(f)

Definition at line 41 of file btree.h.

Referenced by __bt_curdel(), __bt_open(), __bt_seqadv(), __bt_setcur(), __bt_sync(), __rec_open(), and __rec_sync().

◆ F_ISSET

#define F_ISSET (   p,
 
)    ((p)->flags & (f))

◆ F_SET

#define F_SET (   p,
 
)    (p)->flags |= (f)

◆ GETBINTERNAL

#define GETBINTERNAL (   pg,
  indx 
)    ((BINTERNAL *)((char *)(pg) + (pg)->linp[indx]))

◆ GETBLEAF

#define GETBLEAF (   pg,
  indx 
)    ((BLEAF *)((char *)(pg) + (pg)->linp[indx]))

◆ GETRINTERNAL

#define GETRINTERNAL (   pg,
  indx 
)    ((RINTERNAL *)((char *)(pg) + (pg)->linp[indx]))

Definition at line 165 of file btree.h.

Referenced by __rec_search(), bt_psplit(), and rec_total().

◆ GETRLEAF

#define GETRLEAF (   pg,
  indx 
)    ((RLEAF *)((char *)(pg) + (pg)->linp[indx]))

Definition at line 220 of file btree.h.

Referenced by __rec_dleaf(), __rec_ret(), and bt_psplit().

◆ LALIGN

#define LALIGN (   n)    (((n) + sizeof(pgno_t) - 1) & ~(sizeof(pgno_t) - 1))

Definition at line 116 of file btree.h.

◆ MINCACHE

#define MINCACHE   (5) /* Minimum cached pages */

Definition at line 55 of file btree.h.

Referenced by __bt_open().

◆ MINPSIZE

#define MINPSIZE   (512) /* Minimum page size */

Definition at line 56 of file btree.h.

Referenced by __bt_open().

◆ mpool_close

#define mpool_close   __mpool_close

Definition at line 52 of file btree.h.

◆ mpool_filter

#define mpool_filter   __mpool_filter

Definition at line 47 of file btree.h.

◆ mpool_get

#define mpool_get   __mpool_get

Definition at line 49 of file btree.h.

◆ mpool_new

#define mpool_new   __mpool_new

Definition at line 48 of file btree.h.

◆ mpool_open

#define mpool_open   __mpool_open

Definition at line 46 of file btree.h.

◆ mpool_put

#define mpool_put   __mpool_put

Definition at line 50 of file btree.h.

◆ mpool_sync

#define mpool_sync   __mpool_sync

Definition at line 51 of file btree.h.

◆ NBINTERNAL

#define NBINTERNAL (   len)    LALIGN(sizeof(u_int32_t) + sizeof(pgno_t) + sizeof(u_char) + (len))

Definition at line 142 of file btree.h.

Referenced by __bt_pdelete(), __bt_split(), bt_broot(), and bt_psplit().

◆ NBLEAF

#define NBLEAF (   p)    NBLEAFDBT((p)->ksize, (p)->dsize)

Definition at line 192 of file btree.h.

Referenced by __bt_dleaf(), and bt_psplit().

◆ NBLEAFDBT

#define NBLEAFDBT (   ksize,
  dsize 
)
Value:
LALIGN(sizeof(u_int32_t) + sizeof(u_int32_t) + sizeof(u_char) + \
(ksize) + (dsize))
#define LALIGN(n)
Definition: btree.h:116
unsigned int u_int32_t

Definition at line 195 of file btree.h.

Referenced by __bt_open(), __bt_put(), and bt_fast().

◆ NEXTINDEX

#define NEXTINDEX (   p)    (((p)->lower - BTDATAOFF) / sizeof(indx_t))

◆ NOVFLSIZE

#define NOVFLSIZE   (sizeof(pgno_t) + sizeof(u_int32_t))

Definition at line 117 of file btree.h.

Referenced by __bt_open(), __bt_put(), and __rec_iput().

◆ NRINTERNAL

#define NRINTERNAL   LALIGN(sizeof(recno_t) + sizeof(pgno_t))

Definition at line 169 of file btree.h.

Referenced by __bt_split(), bt_psplit(), and bt_rroot().

◆ NRLEAF

#define NRLEAF (   p)    NRLEAFDBT((p)->dsize)

Definition at line 224 of file btree.h.

Referenced by __rec_dleaf(), and bt_psplit().

◆ NRLEAFDBT

#define NRLEAFDBT (   dsize)    LALIGN(sizeof(u_int32_t) + sizeof(u_char) + (dsize))

Definition at line 227 of file btree.h.

Referenced by __rec_iput().

◆ P_BIGDATA

#define P_BIGDATA   0x01 /* overflow data */

◆ P_BIGKEY

#define P_BIGKEY   0x02 /* overflow key */

◆ P_BINTERNAL

#define P_BINTERNAL   0x01 /* btree internal page */

Definition at line 80 of file btree.h.

Referenced by __bt_pgin(), __bt_pgout(), __bt_split(), bt_broot(), and bt_psplit().

◆ P_BLEAF

#define P_BLEAF   0x02 /* leaf page */

◆ P_INVALID

#define P_INVALID   0 /* Invalid tree page number. */

◆ P_META

#define P_META   0 /* Tree metadata page number. */

Definition at line 64 of file btree.h.

Referenced by __bt_pgin(), __bt_pgout(), and bt_meta().

◆ P_OVERFLOW

#define P_OVERFLOW   0x04 /* overflow page */

Definition at line 82 of file btree.h.

Referenced by __ovfl_put().

◆ P_PRESERVE

#define P_PRESERVE   0x20 /* never delete this chain of pages */

Definition at line 86 of file btree.h.

Referenced by __ovfl_delete(), and bt_preserve().

◆ P_RINTERNAL

#define P_RINTERNAL   0x08 /* recno internal page */

Definition at line 83 of file btree.h.

Referenced by __bt_split(), bt_psplit(), and bt_rroot().

◆ P_RLEAF

#define P_RLEAF   0x10 /* leaf page */

Definition at line 84 of file btree.h.

Referenced by __bt_seqset(), __bt_split(), __rec_open(), __rec_search(), bt_psplit(), and bt_rroot().

◆ P_ROOT

#define P_ROOT   1 /* Tree root page number. */

Definition at line 65 of file btree.h.

Referenced by __bt_pdelete(), __bt_search(), __bt_seqset(), __bt_split(), __rec_open(), __rec_search(), and nroot().

◆ P_TYPE

#define P_TYPE   0x1f /* type mask */

◆ R_CLOSEFP

#define R_CLOSEFP   0x00040 /* opened a file pointer */

Definition at line 377 of file btree.h.

Referenced by __rec_close(), and __rec_open().

◆ R_EOF

#define R_EOF   0x00100 /* end of input file reached. */

◆ R_FIXLEN

#define R_FIXLEN   0x00200 /* fixed length records */

Definition at line 379 of file btree.h.

Referenced by __rec_open(), __rec_put(), and __rec_sync().

◆ R_INMEM

#define R_INMEM   0x00800 /* in-memory file */

Definition at line 381 of file btree.h.

Referenced by __rec_close(), __rec_fd(), __rec_get(), __rec_open(), __rec_put(), __rec_seq(), and __rec_sync().

◆ R_MEMMAPPED

#define R_MEMMAPPED   0x00400 /* memory mapped file. */

Definition at line 380 of file btree.h.

Referenced by __rec_close(), and __rec_open().

◆ R_MODIFIED

#define R_MODIFIED   0x01000 /* modified file */

Definition at line 382 of file btree.h.

Referenced by __rec_delete(), __rec_put(), and __rec_sync().

◆ R_RDONLY

#define R_RDONLY   0x02000 /* read-only file */

Definition at line 383 of file btree.h.

Referenced by __rec_open(), and __rec_sync().

◆ R_RECNO

#define R_RECNO   0x00080 /* record oriented tree */

Definition at line 375 of file btree.h.

Referenced by __bt_split(), and __rec_open().

◆ SAVEMETA

#define SAVEMETA   (B_NODUPS | R_RECNO)

Definition at line 307 of file btree.h.

Referenced by __bt_open(), and bt_meta().

◆ WR_BINTERNAL

#define WR_BINTERNAL (   p,
  size,
  pgno,
  flags 
)

Definition at line 146 of file btree.h.

Referenced by __bt_split(), and bt_broot().

◆ WR_BLEAF

#define WR_BLEAF (   p,
  key,
  data,
  flags 
)

Definition at line 200 of file btree.h.

Referenced by __bt_put(), and __bt_split().

◆ WR_RINTERNAL

#define WR_RINTERNAL (   p,
  nrecs,
  pgno 
)
Value:
{ \
*(recno_t *)p = nrecs; \
p += sizeof(recno_t); \
*(pgno_t *)p = pgno; \
}
u_int32_t pgno_t
Definition: db.h:78
u_int32_t recno_t
Definition: db.h:82

Definition at line 173 of file btree.h.

Referenced by bt_rroot().

◆ WR_RLEAF

#define WR_RLEAF (   p,
  data,
  flags 
)

Definition at line 231 of file btree.h.

Referenced by __bt_split(), and __rec_iput().

Typedef Documentation

◆ BINTERNAL

typedef struct _binternal BINTERNAL

◆ BLEAF

typedef struct _bleaf BLEAF

◆ BTMETA

typedef struct _btmeta BTMETA

◆ BTREE

typedef struct _btree BTREE

◆ CURSOR

typedef struct _cursor CURSOR

◆ EPG

typedef struct _epg EPG

◆ EPGNO

typedef struct _epgno EPGNO

◆ PAGE

typedef struct _page PAGE

◆ RINTERNAL

typedef struct _rinternal RINTERNAL

◆ RLEAF

typedef struct _rleaf RLEAF