Optimize mcrealloc
[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 HASHSIZE(LEN)   ( (LEN)<<1 )
42 /* end utils */
43
44
45 typedef struct {
46         union {
47                 struct {
48                         u_int16_t offset;
49                         u_int16_t length;
50                 } leaf;
51                 struct {
52                         u_int32_t link;
53                 } internal;
54         } pointer;
55         union {
56                 struct {
57                         u_int16_t       offset;
58                         u_int16_t       length;
59                 } varlen;
60                 struct {
61                         char key[1];
62                 } fixed;
63         } key;
64 } TBTPointer;
65
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) ) 
69
70 /* can changed up to 65536 */
71 #define TBTREEPAGESIZE  8192
72 #define TBTPAGEHDRSZ    (2*sizeof(u_int32_t))
73
74 typedef struct {
75         u_int32_t       rightlink;
76         u_int32_t       
77                 freespace:16, /* correlate to TBTREEPAGESIZE */
78                 npointer:15,
79                 isleaf:1;
80         char    data[TBTREEPAGESIZE-TBTPAGEHDRSZ];      
81 } TBTPage;
82
83 typedef struct TBTMemPage {
84         u_int32_t       pagenumber;
85         u_int32_t
86                 issynced:1,
87                 iscached:1,
88                 islocked:1,
89                 unused:29;
90         struct TBTMemPage *prev;
91         struct TBTMemPage *next;
92         struct TBTMemPage *link;
93         TBTPage page;
94 } TBTMemPage;
95
96 #define TBTMEMPAGEHDRSZ (sizeof(u_int32_t)*2 + sizeof(TBTMemPage*)*3 + TBTPAGEHDRSZ)
97 typedef struct {
98         u_int16_t       length;
99         char            *value;
100 } TBTValue;
101
102 #define TBT_STATEGY_HALF        0
103 #define TBT_STATEGY_LEFTFILL    1
104 #define TBT_STATEGY_RIGHTFILL   2
105
106 typedef struct {
107         int     fd;     /* file descriptor */
108
109         int     (*cmpkey)(const TBTValue *, const TBTValue *);  
110
111         u_int32_t
112                 readonly:1,
113                 keylen:11,
114                 strategy:2,
115                 unused:2,
116                 pointersize:16;
117
118         /* cache page subsystem */
119         u_int32_t       npage;
120         u_int32_t       curpage;
121         TBTMemPage      **Cache;
122         TBTMemPage      *TimeCache;
123         TBTMemPage      *TimeCacheLast;
124         u_int32_t       lastpagenumber;
125
126         /* stat subsystem */
127         u_int32_t       cachehits;
128         u_int32_t       pageread; /* include cachehits */
129         u_int32_t       pagewrite;
130 } TBTree;
131
132 #define TBT_OK          0
133 #define TBT_ERROR       1
134 #define TBT_HUGE        2
135
136 #define TBTPAGEROOT     0
137
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);
144
145 /* debug function, assume key is int4 or string and values are strings */
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 int TBTGetFirst(TBTree *db, TBTValue *key, TBTValue *value);
159 int TBTGetLast(TBTree *db, TBTValue *key, TBTValue *value);
160
161 #endif