/*
- * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2003 Apple Computer, Inc. All rights reserved.
*
* @APPLE_LICENSE_HEADER_START@
*
*
* @APPLE_LICENSE_HEADER_END@
*/
-/*
- * 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
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
+ *
+ * @(#)btree.h 8.11 (Berkeley) 8/17/94
+ * $FreeBSD: src/lib/libc/db/btree/btree.h,v 1.3 2002/03/22 23:41:40 obrien Exp $
*/
+/* 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 */
} 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))
/*
* 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}
* 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 */
} 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); \
}
/*
} 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); \
}
/*
* 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 */
} 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 *));
+ int (*bt_cmp)(const DBT *, const DBT *);
/* B: prefix comparison function */
- size_t (*bt_pfx) __P((const DBT *, const DBT *));
+ size_t (*bt_pfx)(const DBT *, const DBT *);
/* R: recno input function */
- int (*bt_irec) __P((struct _btree *, recno_t));
+ int (*bt_irec)(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 "bt_extern.h"
+#include "extern.h"
projects / apple / libc.git / blobdiff