Add resetMemoryContext()
[tedtools.git] / tbtree.h
1 /*
2  * Copyright (c) 2005 Teodor Sigaev <teodor@sigaev.ru>
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
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.
16  *
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.
28  */
29
30 #ifndef __TBTREE_H__
31 #define __TBTREE_H__
32
33
34 #include <sys/types.h>
35 #include "tools.h" 
36
37 #define HASHSIZE(LEN)   ( (LEN)<<1 )
38 /* end utils */
39
40
41 typedef struct {
42         union {
43                 struct {
44                         u_int16_t offset;
45                         u_int16_t length;
46                 } leaf;
47                 struct {
48                         u_int32_t link;
49                 } internal;
50         } pointer;
51         union {
52                 struct {
53                         u_int16_t       offset;
54                         u_int16_t       length;
55                 } varlen;
56                 struct {
57                         char key[1];
58                 } fixed;
59         } key;
60 } TBTPointer;
61
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) ) 
65
66 /* can changed up to 65536 */
67 #define TBTREEPAGESIZE  8192
68 #define TBTPAGEHDRSZ    (2*sizeof(u_int32_t))
69
70 typedef struct {
71         u_int32_t       rightlink;
72         u_int32_t       
73                 freespace:16, /* correlate to TBTREEPAGESIZE */
74                 npointer:15,
75                 isleaf:1;
76         char    data[TBTREEPAGESIZE-TBTPAGEHDRSZ];      
77 } TBTPage;
78
79 typedef struct TBTMemPage {
80         u_int32_t       pagenumber;
81         u_int32_t
82                 issynced:1,
83                 iscached:1,
84                 islocked:1,
85                 unused:29;
86         struct TBTMemPage *prev;
87         struct TBTMemPage *next;
88         struct TBTMemPage *link;
89         TBTPage page;
90 } TBTMemPage;
91
92 #define TBTMEMPAGEHDRSZ (sizeof(u_int32_t)*2 + sizeof(TBTMemPage*)*3 + TBTPAGEHDRSZ)
93 typedef struct {
94         u_int16_t       length;
95         char            *value;
96 } TBTValue;
97
98 #define TBT_STATEGY_HALF        0
99 #define TBT_STATEGY_LEFTFILL    1
100 #define TBT_STATEGY_RIGHTFILL   2
101
102 typedef struct {
103         int     fd;     /* file descriptor */
104
105         int     (*cmpkey)(const TBTValue *, const TBTValue *);  
106
107         u_int32_t
108                 readonly:1,
109                 keylen:11,
110                 strategy:2,
111                 unused:2,
112                 pointersize:16;
113
114         /* cache page subsystem */
115         u_int32_t       npage;
116         u_int32_t       curpage;
117         TBTMemPage      **Cache;
118         TBTMemPage      *TimeCache;
119         TBTMemPage      *TimeCacheLast;
120         u_int32_t       lastpagenumber;
121
122         /* stat subsystem */
123         u_int32_t       cachehits;
124         u_int32_t       pageread; /* include cachehits */
125         u_int32_t       pagewrite;
126 } TBTree;
127
128 #define TBT_OK          0
129 #define TBT_ERROR       1
130 #define TBT_HUGE        2
131
132 #define TBTPAGEROOT     0
133
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);
140
141 /* debug function, assume key is int4 or string and values are strings */
142 void dumpTree(TBTree *db, u_int32_t pagenumber, int follow);
143
144 typedef struct {
145         TBTMemPage      *page;
146         TBTPointer      *ptr;
147 } TBTIterator;
148
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);
152
153
154 int TBTGetFirst(TBTree *db, TBTValue *key, TBTValue *value);
155 int TBTGetLast(TBTree *db, TBTValue *key, TBTValue *value);
156
157 #endif