diff options
Diffstat (limited to 'lib/libc/db/btree/btree.h')
| -rw-r--r-- | lib/libc/db/btree/btree.h | 262 |
1 files changed, 146 insertions, 116 deletions
diff --git a/lib/libc/db/btree/btree.h b/lib/libc/db/btree/btree.h index dd798ec..36d35c9 100644 --- a/lib/libc/db/btree/btree.h +++ b/lib/libc/db/btree/btree.h @@ -1,5 +1,5 @@ /*- - * Copyright (c) 1991, 1993 + * Copyright (c) 1991, 1993, 1994 * The Regents of the University of California. All rights reserved. * * This code is derived from software contributed to Berkeley by @@ -33,9 +33,14 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * @(#)btree.h 8.5 (Berkeley) 2/21/94 + * @(#)btree.h 8.11 (Berkeley) 8/17/94 */ +/* Macros to set/clear/test flags. */ +#define F_SET(p, f) (p)->flags |= (f) +#define F_CLR(p, f) (p)->flags &= ~(f) +#define F_ISSET(p, f) ((p)->flags & (f)) + #include <mpool.h> #define DEFMINKEYPAGE (2) /* Minimum keys per page */ @@ -79,8 +84,9 @@ typedef struct _page { } PAGE; /* First and next index. */ -#define BTDATAOFF (sizeof(pgno_t) + sizeof(pgno_t) + sizeof(pgno_t) + \ - sizeof(u_int32_t) + sizeof(indx_t) + sizeof(indx_t)) +#define BTDATAOFF \ + (sizeof(pgno_t) + sizeof(pgno_t) + sizeof(pgno_t) + \ + sizeof(u_int32_t) + sizeof(indx_t) + sizeof(indx_t)) #define NEXTINDEX(p) (((p)->lower - BTDATAOFF) / sizeof(indx_t)) /* @@ -99,9 +105,8 @@ typedef struct _page { * be manipulated without copying. (This presumes that 32 bit items can be * manipulated on this system.) */ -#define LALIGN(n) \ - (((n) + sizeof(pgno_t) - 1) & ~(sizeof(pgno_t) - 1)) -#define NOVFLSIZE (sizeof(pgno_t) + sizeof(size_t)) +#define LALIGN(n) (((n) + sizeof(pgno_t) - 1) & ~(sizeof(pgno_t) - 1)) +#define NOVFLSIZE (sizeof(pgno_t) + sizeof(u_int32_t)) /* * For the btree internal pages, the item is a key. BINTERNALs are {key, pgno} @@ -113,7 +118,7 @@ typedef struct _page { * some minor modifications of the above rule. */ typedef struct _binternal { - size_t ksize; /* key size */ + u_int32_t ksize; /* key size */ pgno_t pgno; /* page number stored on */ #define P_BIGDATA 0x01 /* overflow data */ #define P_BIGKEY 0x02 /* overflow key */ @@ -122,21 +127,21 @@ typedef struct _binternal { } BINTERNAL; /* Get the page's BINTERNAL structure at index indx. */ -#define GETBINTERNAL(pg, indx) \ +#define GETBINTERNAL(pg, indx) \ ((BINTERNAL *)((char *)(pg) + (pg)->linp[indx])) /* Get the number of bytes in the entry. */ -#define NBINTERNAL(len) \ - LALIGN(sizeof(size_t) + sizeof(pgno_t) + sizeof(u_char) + (len)) +#define NBINTERNAL(len) \ + LALIGN(sizeof(u_int32_t) + sizeof(pgno_t) + sizeof(u_char) + (len)) /* Copy a BINTERNAL entry to the page. */ -#define WR_BINTERNAL(p, size, pgno, flags) { \ - *(size_t *)p = size; \ - p += sizeof(size_t); \ - *(pgno_t *)p = pgno; \ - p += sizeof(pgno_t); \ - *(u_char *)p = flags; \ - p += sizeof(u_char); \ +#define WR_BINTERNAL(p, size, pgno, flags) { \ + *(u_int32_t *)p = size; \ + p += sizeof(u_int32_t); \ + *(pgno_t *)p = pgno; \ + p += sizeof(pgno_t); \ + *(u_char *)p = flags; \ + p += sizeof(u_char); \ } /* @@ -149,78 +154,78 @@ typedef struct _rinternal { } RINTERNAL; /* Get the page's RINTERNAL structure at index indx. */ -#define GETRINTERNAL(pg, indx) \ +#define GETRINTERNAL(pg, indx) \ ((RINTERNAL *)((char *)(pg) + (pg)->linp[indx])) /* Get the number of bytes in the entry. */ -#define NRINTERNAL \ +#define NRINTERNAL \ LALIGN(sizeof(recno_t) + sizeof(pgno_t)) /* Copy a RINTERAL entry to the page. */ -#define WR_RINTERNAL(p, nrecs, pgno) { \ - *(recno_t *)p = nrecs; \ - p += sizeof(recno_t); \ - *(pgno_t *)p = pgno; \ +#define WR_RINTERNAL(p, nrecs, pgno) { \ + *(recno_t *)p = nrecs; \ + p += sizeof(recno_t); \ + *(pgno_t *)p = pgno; \ } /* For the btree leaf pages, the item is a key and data pair. */ typedef struct _bleaf { - size_t ksize; /* size of key */ - size_t dsize; /* size of data */ + u_int32_t ksize; /* size of key */ + u_int32_t dsize; /* size of data */ u_char flags; /* P_BIGDATA, P_BIGKEY */ char bytes[1]; /* data */ } BLEAF; /* Get the page's BLEAF structure at index indx. */ -#define GETBLEAF(pg, indx) \ +#define GETBLEAF(pg, indx) \ ((BLEAF *)((char *)(pg) + (pg)->linp[indx])) /* Get the number of bytes in the entry. */ #define NBLEAF(p) NBLEAFDBT((p)->ksize, (p)->dsize) /* Get the number of bytes in the user's key/data pair. */ -#define NBLEAFDBT(ksize, dsize) \ - LALIGN(sizeof(size_t) + sizeof(size_t) + sizeof(u_char) + \ +#define NBLEAFDBT(ksize, dsize) \ + LALIGN(sizeof(u_int32_t) + sizeof(u_int32_t) + sizeof(u_char) + \ (ksize) + (dsize)) /* Copy a BLEAF entry to the page. */ -#define WR_BLEAF(p, key, data, flags) { \ - *(size_t *)p = key->size; \ - p += sizeof(size_t); \ - *(size_t *)p = data->size; \ - p += sizeof(size_t); \ - *(u_char *)p = flags; \ - p += sizeof(u_char); \ - memmove(p, key->data, key->size); \ - p += key->size; \ - memmove(p, data->data, data->size); \ +#define WR_BLEAF(p, key, data, flags) { \ + *(u_int32_t *)p = key->size; \ + p += sizeof(u_int32_t); \ + *(u_int32_t *)p = data->size; \ + p += sizeof(u_int32_t); \ + *(u_char *)p = flags; \ + p += sizeof(u_char); \ + memmove(p, key->data, key->size); \ + p += key->size; \ + memmove(p, data->data, data->size); \ } /* For the recno leaf pages, the item is a data entry. */ typedef struct _rleaf { - size_t dsize; /* size of data */ + u_int32_t dsize; /* size of data */ u_char flags; /* P_BIGDATA */ char bytes[1]; } RLEAF; /* Get the page's RLEAF structure at index indx. */ -#define GETRLEAF(pg, indx) \ +#define GETRLEAF(pg, indx) \ ((RLEAF *)((char *)(pg) + (pg)->linp[indx])) /* Get the number of bytes in the entry. */ #define NRLEAF(p) NRLEAFDBT((p)->dsize) /* Get the number of bytes from the user's data. */ -#define NRLEAFDBT(dsize) \ - LALIGN(sizeof(size_t) + sizeof(u_char) + (dsize)) +#define NRLEAFDBT(dsize) \ + LALIGN(sizeof(u_int32_t) + sizeof(u_char) + (dsize)) /* Copy a RLEAF entry to the page. */ -#define WR_RLEAF(p, data, flags) { \ - *(size_t *)p = data->size; \ - p += sizeof(size_t); \ - *(u_char *)p = flags; \ - p += sizeof(u_char); \ - memmove(p, data->data, data->size); \ +#define WR_RLEAF(p, data, flags) { \ + *(u_int32_t *)p = data->size; \ + p += sizeof(u_int32_t); \ + *(u_char *)p = flags; \ + p += sizeof(u_char); \ + memmove(p, data->data, data->size); \ } /* @@ -232,12 +237,6 @@ typedef struct _rleaf { * record less than key in the tree so that descents work. Leaf page searches * must find the smallest record greater than key so that the returned index * is the record's correct position for insertion. - * - * One comment about cursors. The cursor key is never removed from the tree, - * even if deleted. This is because it is quite difficult to decide where the - * cursor should be when other keys have been inserted/deleted in the tree; - * duplicate keys make it impossible. This scheme does require extra work - * though, to make sure that we don't perform an operation on a deleted key. */ typedef struct _epgno { pgno_t pgno; /* the page number */ @@ -250,53 +249,90 @@ typedef struct _epg { } EPG; /* - * The metadata of the tree. The m_nrecs field is used only by the RECNO code. + * About cursors. The cursor (and the page that contained the key/data pair + * that it referenced) can be deleted, which makes things a bit tricky. If + * there are no duplicates of the cursor key in the tree (i.e. B_NODUPS is set + * or there simply aren't any duplicates of the key) we copy the key that it + * referenced when it's deleted, and reacquire a new cursor key if the cursor + * is used again. If there are duplicates keys, we move to the next/previous + * key, and set a flag so that we know what happened. NOTE: if duplicate (to + * the cursor) keys are added to the tree during this process, it is undefined + * if they will be returned or not in a cursor scan. + * + * The flags determine the possible states of the cursor: + * + * CURS_INIT The cursor references *something*. + * CURS_ACQUIRE The cursor was deleted, and a key has been saved so that + * we can reacquire the right position in the tree. + * CURS_AFTER, CURS_BEFORE + * The cursor was deleted, and now references a key/data pair + * that has not yet been returned, either before or after the + * deleted key/data pair. + * XXX + * This structure is broken out so that we can eventually offer multiple + * cursors as part of the DB interface. + */ +typedef struct _cursor { + EPGNO pg; /* B: Saved tree reference. */ + DBT key; /* B: Saved key, or key.data == NULL. */ + recno_t rcursor; /* R: recno cursor (1-based) */ + +#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. */ + u_int8_t flags; +} CURSOR; + +/* + * The metadata of the tree. The nrecs field is used only by the RECNO code. * This is because the btree doesn't really need it and it requires that every * put or delete call modify the metadata. */ typedef struct _btmeta { - u_int32_t m_magic; /* magic number */ - u_int32_t m_version; /* version */ - u_int32_t m_psize; /* page size */ - u_int32_t m_free; /* page number of first free page */ - u_int32_t m_nrecs; /* R: number of records */ + u_int32_t magic; /* magic number */ + u_int32_t version; /* version */ + u_int32_t psize; /* page size */ + u_int32_t free; /* page number of first free page */ + u_int32_t nrecs; /* R: number of records */ + #define SAVEMETA (B_NODUPS | R_RECNO) - u_int32_t m_flags; /* bt_flags & SAVEMETA */ - u_int32_t m_unused; /* unused */ + u_int32_t flags; /* bt_flags & SAVEMETA */ } BTMETA; /* The in-memory btree/recno data structure. */ typedef struct _btree { - MPOOL *bt_mp; /* memory pool cookie */ + MPOOL *bt_mp; /* memory pool cookie */ - DB *bt_dbp; /* pointer to enclosing DB */ + DB *bt_dbp; /* pointer to enclosing DB */ - EPG bt_cur; /* current (pinned) page */ - PAGE *bt_pinned; /* page pinned across calls */ + EPG bt_cur; /* current (pinned) page */ + PAGE *bt_pinned; /* page pinned across calls */ - EPGNO bt_bcursor; /* B: btree cursor */ - recno_t bt_rcursor; /* R: recno cursor (1-based) */ + CURSOR bt_cursor; /* cursor */ -#define BT_POP(t) (t->bt_sp ? t->bt_stack + --t->bt_sp : NULL) -#define BT_CLR(t) (t->bt_sp = 0) - EPGNO *bt_stack; /* stack of parent pages */ - u_int bt_sp; /* current stack pointer */ - u_int bt_maxstack; /* largest stack */ +#define BT_PUSH(t, p, i) { \ + t->bt_sp->pgno = p; \ + t->bt_sp->index = i; \ + ++t->bt_sp; \ +} +#define BT_POP(t) (t->bt_sp == t->bt_stack ? NULL : --t->bt_sp) +#define BT_CLR(t) (t->bt_sp = t->bt_stack) + EPGNO bt_stack[50]; /* stack of parent pages */ + EPGNO *bt_sp; /* current stack pointer */ - char *bt_kbuf; /* key buffer */ - size_t bt_kbufsz; /* key buffer size */ - char *bt_dbuf; /* data buffer */ - size_t bt_dbufsz; /* data buffer size */ + DBT bt_rkey; /* returned key */ + DBT bt_rdata; /* returned data */ - int bt_fd; /* tree file descriptor */ + int bt_fd; /* tree file descriptor */ - pgno_t bt_free; /* next free page */ + pgno_t bt_free; /* next free page */ u_int32_t bt_psize; /* page size */ - indx_t bt_ovflsize; /* cut-off for key/data overflow */ - int bt_lorder; /* byte order */ + indx_t bt_ovflsize; /* cut-off for key/data overflow */ + int bt_lorder; /* byte order */ /* sorted order */ enum { NOT, BACK, FORWARD } bt_order; - EPGNO bt_last; /* last insert */ + EPGNO bt_last; /* last insert */ /* B: key comparison function */ int (*bt_cmp) __P((const DBT *, const DBT *)); @@ -305,49 +341,43 @@ typedef struct _btree { /* R: recno input function */ int (*bt_irec) __P((struct _btree *, recno_t)); - FILE *bt_rfp; /* R: record FILE pointer */ - int bt_rfd; /* R: record file descriptor */ + FILE *bt_rfp; /* R: record FILE pointer */ + int bt_rfd; /* R: record file descriptor */ - caddr_t bt_cmap; /* R: current point in mapped space */ - caddr_t bt_smap; /* R: start of mapped space */ - caddr_t bt_emap; /* R: end of mapped space */ - size_t bt_msize; /* R: size of mapped region. */ + caddr_t bt_cmap; /* R: current point in mapped space */ + caddr_t bt_smap; /* R: start of mapped space */ + caddr_t bt_emap; /* R: end of mapped space */ + size_t bt_msize; /* R: size of mapped region. */ - recno_t bt_nrecs; /* R: number of records */ - size_t bt_reclen; /* R: fixed record length */ - u_char bt_bval; /* R: delimiting byte/pad character */ + recno_t bt_nrecs; /* R: number of records */ + size_t bt_reclen; /* R: fixed record length */ + u_char bt_bval; /* R: delimiting byte/pad character */ /* * NB: * B_NODUPS and R_RECNO are stored on disk, and may not be changed. */ -#define B_DELCRSR 0x00001 /* cursor has been deleted */ -#define B_INMEM 0x00002 /* in-memory tree */ -#define B_METADIRTY 0x00004 /* need to write metadata */ -#define B_MODIFIED 0x00008 /* tree modified */ -#define B_NEEDSWAP 0x00010 /* if byte order requires swapping */ +#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_RDONLY 0x00010 /* read-only tree */ + #define B_NODUPS 0x00020 /* no duplicate keys permitted */ -#define B_RDONLY 0x00040 /* read-only tree */ #define R_RECNO 0x00080 /* record oriented tree */ -#define B_SEQINIT 0x00100 /* sequential scan initialized */ - -#define R_CLOSEFP 0x00200 /* opened a file pointer */ -#define R_EOF 0x00400 /* end of input file reached. */ -#define R_FIXLEN 0x00800 /* fixed length records */ -#define R_MEMMAPPED 0x01000 /* memory mapped file. */ -#define R_INMEM 0x02000 /* in-memory file */ -#define R_MODIFIED 0x04000 /* modified file */ -#define R_RDONLY 0x08000 /* read-only file */ -#define B_DB_LOCK 0x10000 /* DB_LOCK specified. */ -#define B_DB_SHMEM 0x20000 /* DB_SHMEM specified. */ -#define B_DB_TXN 0x40000 /* DB_TXN specified. */ - - u_int32_t bt_flags; /* btree state */ +#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_MEMMAPPED 0x00400 /* memory mapped file. */ +#define R_INMEM 0x00800 /* in-memory file */ +#define R_MODIFIED 0x01000 /* modified file */ +#define R_RDONLY 0x02000 /* read-only file */ + +#define B_DB_LOCK 0x04000 /* DB_LOCK specified. */ +#define B_DB_SHMEM 0x08000 /* DB_SHMEM specified. */ +#define B_DB_TXN 0x10000 /* DB_TXN specified. */ + u_int32_t flags; } BTREE; -#define SET(t, f) ((t)->bt_flags |= (f)) -#define CLR(t, f) ((t)->bt_flags &= ~(f)) -#define ISSET(t, f) ((t)->bt_flags & (f)) - #include "extern.h" |
