f6e4117cb6a1c26eb046527f4f0e32546e04615a
[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 /*#define HASHSIZE(LEN) ( TYPEALIGN(2, (int)((LEN)*2)) + 1 )*/
47 #define HASHSIZE(LEN)   ( (LEN)<<1 )
48 /* end utils */
49
50
51 typedef struct {
52         union {
53                 struct {
54                         u_int16_t offset;
55                         u_int16_t length;
56                 } leaf;
57                 struct {
58                         u_int32_t link;
59                 } internal;
60         } pointer;
61         union {
62                 struct {
63                         u_int16_t       offset;
64                         u_int16_t       length;
65                 } varlen;
66                 struct {
67                         char key[1];
68                 } fixed;
69         } key;
70 } TBTPointer;
71
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) ) 
75
76 #define TBTREEPAGESIZE  8192
77 #define TBTPAGEHDRSZ    (2*sizeof(u_int32_t))
78
79 typedef struct {
80         u_int32_t       rightlink;
81         u_int32_t       
82                 freespace:13, /* correlate to BTREEPAGESIZE */
83                 npointer:10,
84                 isleaf:1,
85                 unused: 8;
86         char    data[TBTREEPAGESIZE-TBTPAGEHDRSZ];      
87 } TBTPage;
88
89 typedef struct TBTMemPage {
90         u_int32_t       pagenumber;
91         u_int32_t
92                 issynced:1,
93                 iscached:1,
94                 islocked:1,
95                 unused:29;
96         struct TBTMemPage *prev;
97         struct TBTMemPage *next;
98         struct TBTMemPage *link;
99         TBTPage page;
100 } TBTMemPage;
101
102 #define TBTMEMPAGEHDRSZ (sizeof(u_int32_t)*2 + sizeof(TBTMemPage*)*3 + TBTPAGEHDRSZ)
103 typedef struct {
104         u_int16_t       length;
105         char            *value;
106 } TBTValue;
107
108 #define TBT_STATEGY_HALF        0
109 #define TBT_STATEGY_LEFTFILL    1
110 #define TBT_STATEGY_RIGHTFILL   2
111
112 typedef struct {
113         int     fd;     /* file descriptor */
114
115         int     (*cmpkey)(const TBTValue *, const TBTValue *);  
116
117         u_int32_t
118                 readonly:1,
119                 keylen:11,
120                 strategy:2,
121                 unused:18;
122
123         /* cache page subsystem */
124         u_int32_t       npage;
125         u_int32_t       curpage;
126         TBTMemPage      **Cache;
127         TBTMemPage      *TimeCache;
128         TBTMemPage      *TimeCacheLast;
129         u_int32_t       lastpagenumber;
130
131         /* stat subsystem */
132         u_int32_t       cachehits;
133         u_int32_t       pageread; /* include cachehits */
134         u_int32_t       pagewrite;
135 } TBTree;
136
137 #define TBT_OK          0
138 #define TBT_ERROR       1
139 #define TBT_HUGE        2
140
141 #define TBTPAGEROOT     0
142
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);
150
151 typedef struct {
152         TBTMemPage      *page;
153         TBTPointer      *ptr;
154 } TBTIterator;
155
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);
159
160
161 #endif