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 HASHSIZE(LEN) ( (LEN)<<1 )
66 #define TBTPOINTERHRDSZ (offsetof(TBTPointer, key.fixed.key))
67 #define TBTPOINTERSIZE(db) PTRALIGN( (db->keylen) ? TBTPOINTERHRDSZ + db->keylen : sizeof(TBTPointer) )
68 #define ISINFPOINTER(db, page, ptr) ( (page)->isleaf==0 && (page)->rightlink == 0 && (char*)(ptr) == (page)->data + ((page)->npointer-1) * TBTPOINTERSIZE(db) )
70 /* can changed up to 65536 */
71 #define TBTREEPAGESIZE 8192
72 #define TBTPAGEHDRSZ (2*sizeof(u_int32_t))
77 freespace:16, /* correlate to TBTREEPAGESIZE */
80 char data[TBTREEPAGESIZE-TBTPAGEHDRSZ];
83 typedef struct TBTMemPage {
90 struct TBTMemPage *prev;
91 struct TBTMemPage *next;
92 struct TBTMemPage *link;
96 #define TBTMEMPAGEHDRSZ (sizeof(u_int32_t)*2 + sizeof(TBTMemPage*)*3 + TBTPAGEHDRSZ)
102 #define TBT_STATEGY_HALF 0
103 #define TBT_STATEGY_LEFTFILL 1
104 #define TBT_STATEGY_RIGHTFILL 2
107 int fd; /* file descriptor */
109 int (*cmpkey)(const TBTValue *, const TBTValue *);
118 /* cache page subsystem */
122 TBTMemPage *TimeCache;
123 TBTMemPage *TimeCacheLast;
124 u_int32_t lastpagenumber;
128 u_int32_t pageread; /* include cachehits */
136 #define TBTPAGEROOT 0
138 int TBTOpen(TBTree *db, char *file) ;
139 int TBTClose(TBTree *db) ;
140 int TBTSync(TBTree *db) ;
141 int TBTFind(TBTree *db, TBTValue *key, TBTValue *value);
142 int TBTInsert(TBTree *db, TBTValue *key, TBTValue *value);
143 int TBTDelete(TBTree *db, TBTValue *key);
145 /* debug function, assume key is int4 or string and values are strings */
146 void dumpTree(TBTree *db, u_int32_t pagenumber, int follow);
153 int TBTInitIterator(TBTree *db, TBTIterator *iterator );
154 int TBTIterate(TBTree *db, TBTIterator *iterator, TBTValue *key, TBTValue *value );
155 void TBTFreeIterator(TBTree *db, TBTIterator *iterator);
158 int TBTGetFirst(TBTree *db, TBTValue *key, TBTValue *value);
159 int TBTGetLast(TBTree *db, TBTValue *key, TBTValue *value);