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;
51 normchar_t *name; /* Normalized name */
54 typedef struct dirdata {
56 int shortform; /* This is the short form entry. If
57 this value is non-zero, then there
58 is another entry in the B-Plus tree
59 corresponding to the long name of
61 clientchar_t *cname; /* Client name (long) */
62 fschar_t * fsname; /* FileServer name */
65 typedef struct entry {
70 typedef struct inner {
89 unsigned short number;
93 Entry e[MAX_FANOUT]; /* allows access to entry array */
101 typedef int (*KeyCmp)(keyT, keyT, int);
102 #define EXACT_MATCH 0x01
105 typedef struct tree {
106 unsigned int flags; /* tree flags */
107 unsigned int poolsize; /* # of nodes allocated for tree */
108 Nptr root; /* pointer to root node */
109 Nptr leaf; /* pointer to first leaf node in B+tree */
110 unsigned int fanout; /* # of pointers to other nodes */
111 unsigned int minfanout; /* usually minfanout == ceil(fanout/2) */
112 unsigned int height; /* nodes traversed from root to leaves */
113 Nptr pool; /* list of all nodes */
114 Nptr empty; /* list of empty nodes */
115 union { /* nodes to change in insert and delete */
116 Nptr split; /* protected by scp->dirlock write-lock */
119 KeyCmp keycmp; /* pointer to function comparing two keys */
123 #define TREE_FLAGS_MASK 0x01
124 #define TREE_FLAG_UNIQUE_KEYS 0x01
126 /************************* B+ tree Public functions ****************/
127 Tree *initBtree(unsigned int poolsz, unsigned int fan, KeyCmp keyCmp);
128 void freeBtree(Tree *B);
131 void showNode(Tree *B, const char * str, Nptr node);
132 void showBtree(Tree *B);
133 void listBtreeValues(Tree *B, Nptr start, int count);
134 void listAllBtreeValues(Tree *B);
135 void listBtreeNodes(Tree *B, const char * where, Nptr node);
136 void findAllBtreeValues(Tree *B);
139 void insert(Tree *B, keyT key, dataT data);
140 void delete(Tree *B, keyT key);
141 Nptr lookup(Tree *B, keyT key);
143 /******************* cache manager directory operations ***************/
145 int cm_BPlusCompareNormalizedKeys(keyT key1, keyT key2, int flags);
146 int cm_BPlusDirLookup(cm_dirOp_t * op, clientchar_t *entry, cm_fid_t * cfid);
147 int cm_BPlusDirLookupOriginalName(cm_dirOp_t * op, clientchar_t *entry, fschar_t **originalNameRetp);
148 long cm_BPlusDirCreateEntry(cm_dirOp_t * op, clientchar_t *entry, cm_fid_t * cfid);
149 int cm_BPlusDirDeleteEntry(cm_dirOp_t * op, clientchar_t *entry);
150 long cm_BPlusDirBuildTree(cm_scache_t *scp, cm_user_t *userp, cm_req_t* reqp);
151 void cm_BPlusDumpStats(void);
152 int cm_MemDumpBPlusStats(FILE *outputFile, char *cookie, int lock);
154 /******************* directory enumeration operations ****************/
155 typedef struct cm_direnum_entry {
158 normchar_t shortName[13];
160 } cm_direnum_entry_t;
162 #define CM_DIRENUM_FLAG_GOT_STATUS 1
164 typedef struct cm_direnum {
170 cm_direnum_entry_t entry[1];
173 long cm_BPlusDirEnumerate(cm_scache_t *dscp, cm_user_t *userp, cm_req_t *reqp,
174 afs_uint32 locked, clientchar_t *maskp, cm_direnum_t **enumpp);
175 long cm_BPlusDirNextEnumEntry(cm_direnum_t *enump, cm_direnum_entry_t **entrypp);
176 long cm_BPlusDirFreeEnumeration(cm_direnum_t *enump);
177 long cm_BPlusDirEnumTest(cm_scache_t * dscp, cm_user_t *userp, cm_req_t *reqp, afs_uint32 locked);
178 long cm_BPlusDirEnumBulkStat(cm_direnum_t *enump);
180 long cm_InitBPlusDir(void);
182 /************ Statistic Counter ***************************************/
184 extern afs_uint32 bplus_free_tree;
185 extern afs_uint32 bplus_dv_error;
186 extern afs_uint64 bplus_free_time;
189 /************ Accessor Macros *****************************************/
191 /* low level definition of Nptr value usage */
192 #define nAdr(n) (n)->X
194 /* access keys and pointers in a node */
195 #define getkey(j, q) (nAdr(j).e[(q)].key)
196 #define getnode(j, q) (nAdr(j).e[(q)].downNode)
197 #define setkey(j, q, v) ((q > 0) ? nAdr(j).e[(q)].key.name = cm_NormStrDup((v).name) : NULL)
198 #define setnode(j, q, v) (nAdr(j).e[(q)].downNode = (v))
200 /* access tree flag values */
201 #define settreeflags(B,v) (B->flags |= (v & TREE_FLAGS_MASK))
202 #define gettreeflags(B) (B->flags)
203 #define cleartreeflags(B) (B->flags = 0);
205 /* access node flag values */
206 #define setflag(j, v) ((j)->flags |= (v & FLAGS_MASK))
207 #define clrflag(j, v) ((j)->flags &= ~(v & FLAGS_MASK))
208 #define getflags(j) ((j)->flags & FLAGS_MASK)
209 #define getmagic(j) ((j)->magic & BTREE_MAGIC_MASK)
210 #define clearflags(j) ((j)->flags = 0, (j)->magic = BTREE_MAGIC)
213 /* check that a node is in fact a node */
214 #define isnode(j) (((j) != NONODE) && (((j)->magic & BTREE_MAGIC_MASK) == BTREE_MAGIC) && !((j)->flags & isDATA))
215 #define isntnode(j) ((j) == NONODE)
218 /* test individual flag values */
219 #define isinternal(j) (((j)->flags & isLEAF) == 0)
220 #define isleaf(j) (((j)->flags & isLEAF) == isLEAF)
221 #define isdata(j) (((j)->flags & isDATA) == isDATA)
223 #define isroot(j) (((j)->flags & isROOT) == isROOT)
224 #define isfull(j) (((j)->flags & isFULL) == isFULL)
225 #define isfew(j) (((j)->flags & FEWEST) == FEWEST)
227 #define isroot(j) _isRoot(B, j)
228 #define isfew(j) _isFew(B, j)
229 #define isfull(j) _isFull(B, j)
232 /* manage number of keys in a node */
233 #define numentries(j) (nAdr(j).i.pairs)
234 #define clearentries(j) (nAdr(j).i.pairs = 0)
235 #define incentries(j) (nAdr(j).i.pairs++)
236 #define decentries(j) (nAdr(j).i.pairs--)
239 /* manage first/last node pointers in internal nodes */
240 #define setfirstnode(j, v) (nAdr(j).i.firstNode = (v))
241 #define getfirstnode(j) (nAdr(j).i.firstNode)
242 #define getlastnode(j) (nAdr(j).e[nAdr(j).i.pairs].downNode)
245 /* manage pointers to next nodes in leaf nodes */
246 /* also used for free nodes list */
247 #define setnextnode(j, v) (nAdr(j).l.nextNode = (v))
248 #define getnextnode(j) (nAdr(j).l.nextNode)
250 /* manage pointers to all nodes list */
251 #define setallnode(j, v) ((j)->pool = (v))
252 #define getallnode(j) ((j)->pool)
254 /* manage access to data nodes */
255 #define getdata(j) (nAdr(j).d)
256 #define getdatavalue(j) (getdata(j).value)
257 #define getdatakey(j) (getdata(j).key)
258 #define getdatanext(j) (getdata(j).next)
260 /* shift/transfer entries for insertion/deletion */
261 #define clrentry(j, q) _clrentry(j,q)
262 #define pushentry(j, q, v) _pushentry(j, q, v)
263 #define pullentry(j, q, v) _pullentry(j, q, v)
264 #define xferentry(j, q, v, z) _xferentry(j, q, v, z)
265 #define setentry(j, q, v, z) _setentry(j, q, v, z)
267 /* define number of B+tree nodes for free node pool */
268 #define getpoolsize(B) ((B)->poolsize)
269 #define setpoolsize(B,v) ((B)->poolsize = (v))
271 /* locations from which tree access begins */
272 #define getroot(B) ((B)->root)
273 #define setroot(B,v) ((B)->root = (v))
274 #define getleaf(B) ((B)->leaf)
275 #define setleaf(B,v) ((B)->leaf = (v))
277 /* define max/min number of pointers per node */
278 #define getfanout(B) ((B)->fanout)
279 #define setfanout(B,v) ((B)->fanout = (v) - 1)
280 #define getminfanout(B,j) (isroot(j) ? (isleaf(j) ? 0 : 1) : (isleaf(j) ? (B)->fanout - (B)->minfanout: (B)->minfanout))
281 #define setminfanout(B,v) ((B)->minfanout = (v) - 1)
283 /* manage B+tree height */
284 #define inittreeheight(B) ((B)->height = 0)
285 #define inctreeheight(B) ((B)->height++)
286 #define dectreeheight(B) ((B)->height--)
287 #define gettreeheight(B) ((B)->height)
289 /* access pool of free nodes */
290 #define getfirstfreenode(B) ((B)->empty)
291 #define setfirstfreenode(B,v) ((B)->empty = (v))
293 /* access all node list */
294 #define getfirstallnode(B) ((B)->pool)
295 #define setfirstallnode(B,v) ((B)->pool = (v))
297 /* handle split/merge points during insert/delete */
298 #define getsplitpath(B) ((B)->branch.split)
299 #define setsplitpath(B,v) ((B)->branch.split = (v))
300 #define getmergepath(B) ((B)->branch.merge)
301 #define setmergepath(B,v) ((B)->branch.merge = (v))
303 /* exploit function to compare two B+tree keys */
304 #define comparekeys(B) (*(B)->keycmp)
305 #define setcomparekeys(B,v) ((B)->keycmp = (v))
307 /* location containing B+tree class variables */
308 #define setbplustree(B,v) ((B) = (Tree *)(v))
310 /* representation independent node numbering */
311 #define setnodenumber(B,v,q) ((v)->number = (q))
312 #define getnodenumber(B,v) ((v) != NONODE ? (v)->number : -1)
314 #endif /* BPLUSTREE_H */