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 {
61 typedef struct entry {
66 typedef struct inner {
85 unsigned short number;
89 Entry e[MAX_FANOUT]; /* allows access to entry array */
97 typedef int (*KeyCmp)(keyT, keyT, int);
98 #define EXACT_MATCH 0x01
101 typedef struct tree {
102 unsigned int flags; /* tree flags */
103 unsigned int poolsize; /* # of nodes allocated for tree */
104 Nptr root; /* pointer to root node */
105 Nptr leaf; /* pointer to first leaf node in B+tree */
106 unsigned int fanout; /* # of pointers to other nodes */
107 unsigned int minfanout; /* usually minfanout == ceil(fanout/2) */
108 unsigned int height; /* nodes traversed from root to leaves */
109 Nptr pool; /* list of all nodes */
110 Nptr empty; /* list of empty nodes */
111 union { /* nodes to change in insert and delete */
112 Nptr split; /* protected by scp->dirlock write-lock */
115 KeyCmp keycmp; /* pointer to function comparing two keys */
119 #define TREE_FLAGS_MASK 0x01
120 #define TREE_FLAG_UNIQUE_KEYS 0x01
122 /************************* B+ tree Public functions ****************/
123 Tree *initBtree(unsigned int poolsz, unsigned int fan, KeyCmp keyCmp);
124 void freeBtree(Tree *B);
127 void showNode(Tree *B, const char * str, Nptr node);
128 void showBtree(Tree *B);
129 void listBtreeValues(Tree *B, Nptr start, int count);
130 void listAllBtreeValues(Tree *B);
131 void listBtreeNodes(Tree *B, const char * where, Nptr node);
132 void findAllBtreeValues(Tree *B);
135 void insert(Tree *B, keyT key, dataT data);
136 void delete(Tree *B, keyT key);
137 Nptr lookup(Tree *B, keyT key);
139 /******************* cache manager directory operations ***************/
141 int cm_BPlusDirLookup(cm_dirOp_t * op, char *entry, cm_fid_t * cfid);
142 int cm_BPlusDirLookupOriginalName(cm_dirOp_t * op, char * entry, char ** originalNameRetp);
143 long cm_BPlusDirCreateEntry(cm_dirOp_t * op, char *entry, cm_fid_t * cfid);
144 int cm_BPlusDirDeleteEntry(cm_dirOp_t * op, char *entry);
145 long cm_BPlusDirBuildTree(cm_scache_t *scp, cm_user_t *userp, cm_req_t* reqp);
146 void cm_BPlusDumpStats(void);
147 int cm_MemDumpBPlusStats(FILE *outputFile, char *cookie, int lock);
150 /******************* directory enumeration operations ****************/
151 typedef struct cm_direnum_entry {
155 } cm_direnum_entry_t;
157 typedef struct cm_direnum {
160 cm_direnum_entry_t entry[1];
163 long cm_BPlusDirEnumerate(cm_scache_t *scp, afs_uint32 locked, char *maskp, cm_direnum_t **enumpp);
164 long cm_BPlusDirNextEnumEntry(cm_direnum_t *enump, cm_direnum_entry_t **entrypp);
165 long cm_BPlusDirFreeEnumeration(cm_direnum_t *enump);
166 long cm_BPlusDirEnumTest(cm_scache_t * dscp, afs_uint32 locked);
168 long cm_InitBPlusDir(void);
170 /************ Statistic Counter ***************************************/
172 extern afs_uint32 bplus_free_tree;
173 extern afs_uint32 bplus_dv_error;
174 extern afs_uint64 bplus_free_time;
177 /************ Accessor Macros *****************************************/
179 /* low level definition of Nptr value usage */
180 #define nAdr(n) (n)->X
182 /* access keys and pointers in a node */
183 #define getkey(j, q) (nAdr(j).e[(q)].key)
184 #define getnode(j, q) (nAdr(j).e[(q)].downNode)
185 #define setkey(j, q, v) ((q > 0) ? nAdr(j).e[(q)].key.name = strdup((v).name) : NULL)
186 #define setnode(j, q, v) (nAdr(j).e[(q)].downNode = (v))
188 /* access tree flag values */
189 #define settreeflags(B,v) (B->flags |= (v & TREE_FLAGS_MASK))
190 #define gettreeflags(B) (B->flags)
191 #define cleartreeflags(B) (B->flags = 0);
193 /* access node flag values */
194 #define setflag(j, v) ((j)->flags |= (v & FLAGS_MASK))
195 #define clrflag(j, v) ((j)->flags &= ~(v & FLAGS_MASK))
196 #define getflags(j) ((j)->flags & FLAGS_MASK)
197 #define getmagic(j) ((j)->magic & BTREE_MAGIC_MASK)
198 #define clearflags(j) ((j)->flags = 0, (j)->magic = BTREE_MAGIC)
201 /* check that a node is in fact a node */
202 #define isnode(j) (((j) != NONODE) && (((j)->magic & BTREE_MAGIC_MASK) == BTREE_MAGIC) && !((j)->flags & isDATA))
203 #define isntnode(j) ((j) == NONODE)
206 /* test individual flag values */
207 #define isinternal(j) (((j)->flags & isLEAF) == 0)
208 #define isleaf(j) (((j)->flags & isLEAF) == isLEAF)
209 #define isdata(j) (((j)->flags & isDATA) == isDATA)
211 #define isroot(j) (((j)->flags & isROOT) == isROOT)
212 #define isfull(j) (((j)->flags & isFULL) == isFULL)
213 #define isfew(j) (((j)->flags & FEWEST) == FEWEST)
215 #define isroot(j) _isRoot(B, j)
216 #define isfew(j) _isFew(B, j)
217 #define isfull(j) _isFull(B, j)
220 /* manage number of keys in a node */
221 #define numentries(j) (nAdr(j).i.pairs)
222 #define clearentries(j) (nAdr(j).i.pairs = 0)
223 #define incentries(j) (nAdr(j).i.pairs++)
224 #define decentries(j) (nAdr(j).i.pairs--)
227 /* manage first/last node pointers in internal nodes */
228 #define setfirstnode(j, v) (nAdr(j).i.firstNode = (v))
229 #define getfirstnode(j) (nAdr(j).i.firstNode)
230 #define getlastnode(j) (nAdr(j).e[nAdr(j).i.pairs].downNode)
233 /* manage pointers to next nodes in leaf nodes */
234 /* also used for free nodes list */
235 #define setnextnode(j, v) (nAdr(j).l.nextNode = (v))
236 #define getnextnode(j) (nAdr(j).l.nextNode)
238 /* manage pointers to all nodes list */
239 #define setallnode(j, v) ((j)->pool = (v))
240 #define getallnode(j) ((j)->pool)
242 /* manage access to data nodes */
243 #define getdata(j) (nAdr(j).d)
244 #define getdatavalue(j) (getdata(j).value)
245 #define getdatakey(j) (getdata(j).key)
246 #define getdatanext(j) (getdata(j).next)
248 /* shift/transfer entries for insertion/deletion */
249 #define clrentry(j, q) _clrentry(j,q)
250 #define pushentry(j, q, v) _pushentry(j, q, v)
251 #define pullentry(j, q, v) _pullentry(j, q, v)
252 #define xferentry(j, q, v, z) _xferentry(j, q, v, z)
253 #define setentry(j, q, v, z) _setentry(j, q, v, z)
255 /* define number of B+tree nodes for free node pool */
256 #define getpoolsize(B) ((B)->poolsize)
257 #define setpoolsize(B,v) ((B)->poolsize = (v))
259 /* locations from which tree access begins */
260 #define getroot(B) ((B)->root)
261 #define setroot(B,v) ((B)->root = (v))
262 #define getleaf(B) ((B)->leaf)
263 #define setleaf(B,v) ((B)->leaf = (v))
265 /* define max/min number of pointers per node */
266 #define getfanout(B) ((B)->fanout)
267 #define setfanout(B,v) ((B)->fanout = (v) - 1)
268 #define getminfanout(B,j) (isroot(j) ? (isleaf(j) ? 0 : 1) : (isleaf(j) ? (B)->fanout - (B)->minfanout: (B)->minfanout))
269 #define setminfanout(B,v) ((B)->minfanout = (v) - 1)
271 /* manage B+tree height */
272 #define inittreeheight(B) ((B)->height = 0)
273 #define inctreeheight(B) ((B)->height++)
274 #define dectreeheight(B) ((B)->height--)
275 #define gettreeheight(B) ((B)->height)
277 /* access pool of free nodes */
278 #define getfirstfreenode(B) ((B)->empty)
279 #define setfirstfreenode(B,v) ((B)->empty = (v))
281 /* access all node list */
282 #define getfirstallnode(B) ((B)->pool)
283 #define setfirstallnode(B,v) ((B)->pool = (v))
285 /* handle split/merge points during insert/delete */
286 #define getsplitpath(B) ((B)->branch.split)
287 #define setsplitpath(B,v) ((B)->branch.split = (v))
288 #define getmergepath(B) ((B)->branch.merge)
289 #define setmergepath(B,v) ((B)->branch.merge = (v))
291 /* exploit function to compare two B+tree keys */
292 #define comparekeys(B) (*(B)->keycmp)
293 #define setcomparekeys(B,v) ((B)->keycmp = (v))
295 /* location containing B+tree class variables */
296 #define setbplustree(B,v) ((B) = (Tree *)(v))
298 /* representation independent node numbering */
299 #define setnodenumber(B,v,q) ((v)->number = (q))
300 #define getnodenumber(B,v) ((v) != NONODE ? (v)->number : -1)
302 #endif /* BPLUSTREE_H */