612913bffa5c06050c90cd0e36d28d9a537b73ea
[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
36 /* C-utils */
37 #ifndef offsetof
38 #define offsetof(type, field)   ((int) &((type *)0)->field)
39 #endif   /* offsetof */
40
41 #define TYPEALIGN(ALIGNVAL,LEN)  \
42         (((long) (LEN) + (ALIGNVAL-1)) & ~((long) (ALIGNVAL-1)))
43
44 #define PTRALIGN(LEN)     TYPEALIGN(sizeof(void*), (LEN))
45
46 /* end utils */
47
48
49 typedef struct {
50         union {
51                 struct {
52                         u_int16_t offset;
53                         u_int16_t length;
54                 } leaf;
55                 struct {
56                         u_int32_t link;
57                 } internal;
58         } pointer;
59         union {
60                 struct {
61                         u_int16_t       offset;
62                         u_int16_t       length;
63                 } varlen;
64                 struct {
65                         char key[1];
66                 } fixed;
67         } key;
68 } TBTPointer;
69
70 #define TBTPOINTERHRDSZ         (offsetof(TBTPointer, key.fixed.key))
71 #define TBTPOINTERSIZE(db)      PTRALIGN( (db->keylen) ? TBTPOINTERHRDSZ + db->keylen : sizeof(TBTPointer) )
72 #define ISINFPOINTER(db, page, ptr)  ( (page)->isleaf==0 && (page)->rightlink == 0 && (char*)(ptr) == (page)->data + ((page)->npointer-1) * TBTPOINTERSIZE(db) ) 
73
74 #define TBTREEPAGESIZE  8192
75 #define TBTPAGEHDRSZ    (2*sizeof(u_int32_t))
76
77 typedef struct {
78         u_int32_t       rightlink;
79         u_int32_t       
80                 freespace:13, /* correlate to BTREEPAGESIZE */
81                 npointer:10,
82                 isleaf:1,
83                 unused: 8;
84         char    data[TBTREEPAGESIZE-TBTPAGEHDRSZ];      
85 } TBTPage;
86
87 typedef struct TBTMemPage {
88         u_int32_t       pagenumber;
89         u_int32_t
90                 issynced:1,
91                 iscached:1,
92                 islocked:1,
93                 unused:29;
94         struct TBTMemPage *prev;
95         struct TBTMemPage *next;
96         TBTPage page;
97 } TBTMemPage;
98
99 #define TBTMEMPAGEHDRSZ (sizeof(u_int32_t)*2 + sizeof(TBTMemPage*)*2 + TBTPAGEHDRSZ)
100 typedef struct {
101         u_int16_t       length;
102         char            *value;
103 } TBTValue;
104
105 #define TBT_STATEGY_HALF        0
106 #define TBT_STATEGY_LEFTFILL    1
107 #define TBT_STATEGY_RIGHTFILL   2
108
109 typedef struct {
110         int     fd;     /* file descriptor */
111
112         int     (*cmpkey)(const TBTValue *, const TBTValue *);  
113
114         u_int32_t
115                 readonly:1,
116                 keylen:11,
117                 strategy:2,
118                 unused:18;
119
120         /* cache page subsystem */
121         u_int32_t       npage;
122         u_int32_t       curpage;
123         TBTMemPage      **Cache;
124         TBTMemPage      *TimeCache;
125         TBTMemPage      *TimeCacheLast;
126         u_int32_t       lastpagenumber;
127
128         /* stat subsystem */
129         u_int32_t       cachehits;
130         u_int32_t       pageread; /* include cachehits */
131         u_int32_t       pagewrite;
132 } TBTree;
133
134 #define TBT_OK          0
135 #define TBT_ERROR       1
136 #define TBT_HUGE        2
137
138 #define TBTPAGEROOT     0
139
140 int TBTOpen(TBTree *db, char *file) ;
141 int TBTClose(TBTree *db) ;
142 int TBTSync(TBTree *db) ;
143 int TBTFind(TBTree *db, TBTValue *key, TBTValue *value);
144 int TBTInsert(TBTree *db, TBTValue *key, TBTValue *value);
145 int TBTDelete(TBTree *db, TBTValue *key);
146 void dumpTree(TBTree *db, u_int32_t pagenumber, int follow);
147
148 typedef struct {
149         TBTMemPage      *page;
150         TBTPointer      *ptr;
151 } TBTIterator;
152
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);
156
157
158 #endif