2 * Copyright (c) 2005 Teodor Sigaev <teodor@sigaev.ru>
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the author nor the names of any co-contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY CONTRIBUTORS ``AS IS'' AND ANY EXPRESS
18 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL CONTRIBUTORS BE LIABLE FOR ANY
21 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
23 * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
25 * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
26 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
27 * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 #include <sys/types.h>
38 #define offsetof(type, field) ((int) &((type *)0)->field)
41 #define TYPEALIGN(ALIGNVAL,LEN) \
42 (((long) (LEN) + (ALIGNVAL-1)) & ~((long) (ALIGNVAL-1)))
44 #define PTRALIGN(LEN) TYPEALIGN(sizeof(void*), (LEN))
46 /*#define HASHSIZE(LEN) ( TYPEALIGN(2, (int)((LEN)*2)) + 1 )*/
47 #define HASHSIZE(LEN) ( (LEN)<<1 )
72 #define TBTPOINTERHRDSZ (offsetof(TBTPointer, key.fixed.key))
73 #define TBTPOINTERSIZE(db) PTRALIGN( (db->keylen) ? TBTPOINTERHRDSZ + db->keylen : sizeof(TBTPointer) )
74 #define ISINFPOINTER(db, page, ptr) ( (page)->isleaf==0 && (page)->rightlink == 0 && (char*)(ptr) == (page)->data + ((page)->npointer-1) * TBTPOINTERSIZE(db) )
76 #define TBTREEPAGESIZE 8192
77 #define TBTPAGEHDRSZ (2*sizeof(u_int32_t))
82 freespace:13, /* correlate to BTREEPAGESIZE */
86 char data[TBTREEPAGESIZE-TBTPAGEHDRSZ];
89 typedef struct TBTMemPage {
96 struct TBTMemPage *prev;
97 struct TBTMemPage *next;
98 struct TBTMemPage *link;
102 #define TBTMEMPAGEHDRSZ (sizeof(u_int32_t)*2 + sizeof(TBTMemPage*)*3 + TBTPAGEHDRSZ)
108 #define TBT_STATEGY_HALF 0
109 #define TBT_STATEGY_LEFTFILL 1
110 #define TBT_STATEGY_RIGHTFILL 2
113 int fd; /* file descriptor */
115 int (*cmpkey)(const TBTValue *, const TBTValue *);
123 /* cache page subsystem */
127 TBTMemPage *TimeCache;
128 TBTMemPage *TimeCacheLast;
129 u_int32_t lastpagenumber;
133 u_int32_t pageread; /* include cachehits */
141 #define TBTPAGEROOT 0
143 int TBTOpen(TBTree *db, char *file) ;
144 int TBTClose(TBTree *db) ;
145 int TBTSync(TBTree *db) ;
146 int TBTFind(TBTree *db, TBTValue *key, TBTValue *value);
147 int TBTInsert(TBTree *db, TBTValue *key, TBTValue *value);
148 int TBTDelete(TBTree *db, TBTValue *key);
149 void dumpTree(TBTree *db, u_int32_t pagenumber, int follow);
156 int TBTInitIterator(TBTree *db, TBTIterator *iterator );
157 int TBTIterate(TBTree *db, TBTIterator *iterator, TBTValue *key, TBTValue *value );
158 void TBTFreeIterator(TBTree *db, TBTIterator *iterator);