2 * Copyright 2007 Secure Endpoints Inc.
6 * This software has been released under the terms of the IBM Public
7 * License. For details, see the LICENSE file in the top-level source
8 * directory or online at http://www.openafs.org/dl/license10.html
10 * Thanks to Jan Jannink for B+ tree algorithms.
16 /******** flag bits (5 of 16 used, 11 for magic value) ********/
18 /* bits set at node creation/split/merge */
23 /* bits set at key insertion/deletion */
26 #define FLAGS_MASK 0xFF
28 /* identifies data as being a B+tree node */
29 #define BTREE_MAGIC 0xBEE0BEE0
30 #define BTREE_MAGIC_MASK 0xFFFFFFFF
33 /************************* constants ************************/
35 /* The maximum number of Entrys in one Node */
38 /* corresponds to a NULL node pointer value */
41 /* special node slot values used in key search */
47 /************************* Data Types **********************************/
48 typedef struct node *Nptr;
55 typedef struct dirdata {
60 typedef struct entry {
65 typedef struct inner {
84 unsigned short number;
88 Entry e[MAX_FANOUT]; /* allows access to entry array */
96 typedef int (*KeyCmp)(keyT, keyT, int);
97 #define EXACT_MATCH 0x01
100 typedef struct tree {
101 unsigned int flags; /* tree flags */
102 unsigned int poolsize; /* # of nodes allocated for tree */
103 Nptr root; /* pointer to root node */
104 Nptr leaf; /* pointer to first leaf node in B+tree */
105 unsigned int fanout; /* # of pointers to other nodes */
106 unsigned int minfanout; /* usually minfanout == ceil(fanout/2) */
107 unsigned int height; /* nodes traversed from root to leaves */
108 Nptr pool; /* list of all nodes */
109 Nptr empty; /* list of empty nodes */
110 keyT theKey; /* the key value used in tree operations */
111 dataT theData; /* data used for insertions/deletions */
112 union { /* nodes to change in insert and delete */
116 KeyCmp keycmp; /* pointer to function comparing two keys */
120 #define TREE_FLAGS_MASK 0x01
121 #define TREE_FLAG_UNIQUE_KEYS 0x01
123 /************************* B+ tree Public functions ****************/
124 Tree *initBtree(unsigned int poolsz, unsigned int fan, KeyCmp keyCmp);
125 void freeBtree(Tree *B);
128 void showNode(Tree *B, const char * str, Nptr node);
129 void showBtree(Tree *B);
130 void listBtreeValues(Tree *B, Nptr start, int count);
131 void listAllBtreeValues(Tree *B);
132 void listBtreeNodes(Tree *B, const char * where, Nptr node);
133 void findAllBtreeValues(Tree *B);
136 void insert(Tree *B, keyT key, dataT data);
137 void delete(Tree *B, keyT key);
138 Nptr lookup(Tree *B, keyT key);
140 /******************* cache manager directory operations ***************/
141 int cm_BPlusDirLookup(cm_dirOp_t * op, char *entry, cm_fid_t * cfid);
142 long cm_BPlusDirCreateEntry(cm_dirOp_t * op, char *entry, cm_fid_t * cfid);
143 int cm_BPlusDirDeleteEntry(cm_dirOp_t * op, char *entry);
144 long cm_BPlusDirBuildTree(cm_scache_t *scp, cm_user_t *userp, cm_req_t* reqp);
145 void cm_BPlusDumpStats(void);
146 int cm_MemDumpBPlusStats(FILE *outputFile, char *cookie, int lock);
148 extern afs_uint32 bplus_free_tree;
149 extern afs_uint32 bplus_dv_error;
150 extern afs_uint64 bplus_free_time;
152 /************ Accessor Macros *****************************************/
154 /* low level definition of Nptr value usage */
155 #define nAdr(n) (n)->X
157 /* access keys and pointers in a node */
158 #define getkey(j, q) (nAdr(j).e[(q)].key)
159 #define getnode(j, q) (nAdr(j).e[(q)].downNode)
160 #define setkey(j, q, v) ((q > 0) ? nAdr(j).e[(q)].key.name = strdup((v).name) : NULL)
161 #define setnode(j, q, v) (nAdr(j).e[(q)].downNode = (v))
163 /* access tree flag values */
164 #define settreeflags(B,v) (B->flags |= (v & TREE_FLAGS_MASK))
165 #define gettreeflags(B) (B->flags)
166 #define cleartreeflags(B) (B->flags = 0);
168 /* access node flag values */
169 #define setflag(j, v) ((j)->flags |= (v & FLAGS_MASK))
170 #define clrflag(j, v) ((j)->flags &= ~(v & FLAGS_MASK))
171 #define getflags(j) ((j)->flags & FLAGS_MASK)
172 #define getmagic(j) ((j)->magic & BTREE_MAGIC_MASK)
173 #define clearflags(j) ((j)->flags = 0, (j)->magic = BTREE_MAGIC)
176 /* check that a node is in fact a node */
177 #define isnode(j) (((j) != NONODE) && (((j)->magic & BTREE_MAGIC_MASK) == BTREE_MAGIC) && !((j)->flags & isDATA))
178 #define isntnode(j) ((j) == NONODE)
181 /* test individual flag values */
182 #define isinternal(j) (((j)->flags & isLEAF) == 0)
183 #define isleaf(j) (((j)->flags & isLEAF) == isLEAF)
184 #define isdata(j) (((j)->flags & isDATA) == isDATA)
186 #define isroot(j) (((j)->flags & isROOT) == isROOT)
187 #define isfull(j) (((j)->flags & isFULL) == isFULL)
188 #define isfew(j) (((j)->flags & FEWEST) == FEWEST)
190 #define isroot(j) _isRoot(B, j)
191 #define isfew(j) _isFew(B, j)
192 #define isfull(j) _isFull(B, j)
195 /* manage number of keys in a node */
196 #define numentries(j) (nAdr(j).i.pairs)
197 #define clearentries(j) (nAdr(j).i.pairs = 0)
198 #define incentries(j) (nAdr(j).i.pairs++)
199 #define decentries(j) (nAdr(j).i.pairs--)
202 /* manage first/last node pointers in internal nodes */
203 #define setfirstnode(j, v) (nAdr(j).i.firstNode = (v))
204 #define getfirstnode(j) (nAdr(j).i.firstNode)
205 #define getlastnode(j) (nAdr(j).e[nAdr(j).i.pairs].downNode)
208 /* manage pointers to next nodes in leaf nodes */
209 /* also used for free nodes list */
210 #define setnextnode(j, v) (nAdr(j).l.nextNode = (v))
211 #define getnextnode(j) (nAdr(j).l.nextNode)
213 /* manage pointers to all nodes list */
214 #define setallnode(j, v) ((j)->pool = (v))
215 #define getallnode(j) ((j)->pool)
217 /* manage access to data nodes */
218 #define getdata(j) (nAdr(j).d)
219 #define getdatavalue(j) (getdata(j).value)
220 #define getdatakey(j) (getdata(j).key)
221 #define getdatanext(j) (getdata(j).next)
223 /* shift/transfer entries for insertion/deletion */
224 #define clrentry(j, q) _clrentry(j,q)
225 #define pushentry(j, q, v) _pushentry(j, q, v)
226 #define pullentry(j, q, v) _pullentry(j, q, v)
227 #define xferentry(j, q, v, z) _xferentry(j, q, v, z)
228 #define setentry(j, q, v, z) _setentry(j, q, v, z)
231 /* access key and data values for B+tree methods */
232 /* pass values to getSlot(), descend...() */
233 #define getfunkey(B) ((B)->theKey)
234 #define getfundata(B) ((B)->theData)
235 #define setfunkey(B,v) ((B)->theKey = (v))
236 #define setfundata(B,v) ((B)->theData = (v))
238 /* define number of B+tree nodes for free node pool */
239 #define getpoolsize(B) ((B)->poolsize)
240 #define setpoolsize(B,v) ((B)->poolsize = (v))
242 /* locations from which tree access begins */
243 #define getroot(B) ((B)->root)
244 #define setroot(B,v) ((B)->root = (v))
245 #define getleaf(B) ((B)->leaf)
246 #define setleaf(B,v) ((B)->leaf = (v))
248 /* define max/min number of pointers per node */
249 #define getfanout(B) ((B)->fanout)
250 #define setfanout(B,v) ((B)->fanout = (v) - 1)
251 #define getminfanout(B,j) (isroot(j) ? (isleaf(j) ? 0 : 1) : (isleaf(j) ? (B)->fanout - (B)->minfanout: (B)->minfanout))
252 #define setminfanout(B,v) ((B)->minfanout = (v) - 1)
254 /* manage B+tree height */
255 #define inittreeheight(B) ((B)->height = 0)
256 #define inctreeheight(B) ((B)->height++)
257 #define dectreeheight(B) ((B)->height--)
258 #define gettreeheight(B) ((B)->height)
260 /* access pool of free nodes */
261 #define getfirstfreenode(B) ((B)->empty)
262 #define setfirstfreenode(B,v) ((B)->empty = (v))
264 /* access all node list */
265 #define getfirstallnode(B) ((B)->pool)
266 #define setfirstallnode(B,v) ((B)->pool = (v))
268 /* handle split/merge points during insert/delete */
269 #define getsplitpath(B) ((B)->branch.split)
270 #define setsplitpath(B,v) ((B)->branch.split = (v))
271 #define getmergepath(B) ((B)->branch.merge)
272 #define setmergepath(B,v) ((B)->branch.merge = (v))
274 /* exploit function to compare two B+tree keys */
275 #define comparekeys(B) (*(B)->keycmp)
276 #define setcomparekeys(B,v) ((B)->keycmp = (v))
278 /* location containing B+tree class variables */
279 #define setbplustree(B,v) ((B) = (Tree *)(v))
281 /* representation independent node numbering */
282 #define setnodenumber(B,v,q) ((v)->number = (q))
283 #define getnodenumber(B,v) ((v) != NONODE ? (v)->number : -1)
285 #endif /* BPLUSTREE_H */