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>
37 #define HASHSIZE(LEN) ( (LEN)<<1 )
62 #define TBTPOINTERHRDSZ (offsetof(TBTPointer, key.fixed.key))
63 #define TBTPOINTERSIZE(db) PTRALIGN( (db->keylen) ? TBTPOINTERHRDSZ + db->keylen : sizeof(TBTPointer) )
64 #define ISINFPOINTER(db, page, ptr) ( (page)->isleaf==0 && (page)->rightlink == 0 && (char*)(ptr) == (page)->data + ((page)->npointer-1) * TBTPOINTERSIZE(db) )
66 /* can changed up to 65536 */
67 #define TBTREEPAGESIZE 8192
68 #define TBTPAGEHDRSZ (2*sizeof(u_int32_t))
73 freespace:16, /* correlate to TBTREEPAGESIZE */
76 char data[TBTREEPAGESIZE-TBTPAGEHDRSZ];
79 typedef struct TBTMemPage {
86 struct TBTMemPage *prev;
87 struct TBTMemPage *next;
88 struct TBTMemPage *link;
92 #define TBTMEMPAGEHDRSZ (sizeof(u_int32_t)*2 + sizeof(TBTMemPage*)*3 + TBTPAGEHDRSZ)
98 #define TBT_STATEGY_HALF 0
99 #define TBT_STATEGY_LEFTFILL 1
100 #define TBT_STATEGY_RIGHTFILL 2
103 int fd; /* file descriptor */
105 int (*cmpkey)(const TBTValue *, const TBTValue *);
114 /* cache page subsystem */
118 TBTMemPage *TimeCache;
119 TBTMemPage *TimeCacheLast;
120 u_int32_t lastpagenumber;
124 u_int32_t pageread; /* include cachehits */
132 #define TBTPAGEROOT 0
134 int TBTOpen(TBTree *db, char *file) ;
135 int TBTClose(TBTree *db) ;
136 int TBTSync(TBTree *db) ;
137 int TBTFind(TBTree *db, TBTValue *key, TBTValue *value);
138 int TBTInsert(TBTree *db, TBTValue *key, TBTValue *value);
139 int TBTDelete(TBTree *db, TBTValue *key);
141 /* debug function, assume key is int4 or string and values are strings */
142 void dumpTree(TBTree *db, u_int32_t pagenumber, int follow);
149 int TBTInitIterator(TBTree *db, TBTIterator *iterator );
150 int TBTIterate(TBTree *db, TBTIterator *iterator, TBTValue *key, TBTValue *value );
151 void TBTFreeIterator(TBTree *db, TBTIterator *iterator);
154 int TBTGetFirst(TBTree *db, TBTValue *key, TBTValue *value);
155 int TBTGetLast(TBTree *db, TBTValue *key, TBTValue *value);