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 int cm_BPlusDirFoo(struct cm_scache *scp, struct cm_dirEntry *dep, void *dummy, osi_hyper_t *entryOffsetp);
152 void cm_BPlusDumpStats(void);
153 int cm_MemDumpBPlusStats(FILE *outputFile, char *cookie, int lock);
155 /******************* directory enumeration operations ****************/
156 typedef struct cm_direnum_entry {
159 normchar_t shortName[13];
161 } cm_direnum_entry_t;
163 #define CM_DIRENUM_FLAG_GOT_STATUS 1
165 typedef struct cm_direnum {
171 afs_uint32 fetchStatus;
172 cm_direnum_entry_t entry[1];
175 long cm_BPlusDirEnumerate(cm_scache_t *dscp, cm_user_t *userp, cm_req_t *reqp,
176 afs_uint32 locked, clientchar_t *maskp, afs_uint32 fetchStatus, cm_direnum_t **enumpp);
177 long cm_BPlusDirNextEnumEntry(cm_direnum_t *enump, cm_direnum_entry_t **entrypp);
178 long cm_BPlusDirPeekNextEnumEntry(cm_direnum_t *enump, cm_direnum_entry_t **entrypp);
179 long cm_BPlusDirFreeEnumeration(cm_direnum_t *enump);
180 long cm_BPlusDirEnumTest(cm_scache_t * dscp, cm_user_t *userp, cm_req_t *reqp, afs_uint32 locked);
181 long cm_BPlusDirEnumBulkStat(cm_direnum_t *enump);
183 long cm_InitBPlusDir(void);
185 /************ Statistic Counter ***************************************/
187 extern afs_uint32 bplus_free_tree;
188 extern afs_uint32 bplus_dv_error;
189 extern afs_uint64 bplus_free_time;
192 /************ Accessor Macros *****************************************/
194 /* low level definition of Nptr value usage */
195 #define nAdr(n) (n)->X
197 /* access keys and pointers in a node */
198 #define getkey(j, q) (nAdr(j).e[(q)].key)
199 #define getnode(j, q) (nAdr(j).e[(q)].downNode)
200 #define setkey(j, q, v) ((q > 0) ? nAdr(j).e[(q)].key.name = cm_NormStrDup((v).name) : NULL)
201 #define setnode(j, q, v) (nAdr(j).e[(q)].downNode = (v))
203 /* access tree flag values */
204 #define settreeflags(B,v) (B->flags |= (v & TREE_FLAGS_MASK))
205 #define gettreeflags(B) (B->flags)
206 #define cleartreeflags(B) (B->flags = 0);
208 /* access node flag values */
209 #define setflag(j, v) ((j)->flags |= (v & FLAGS_MASK))
210 #define clrflag(j, v) ((j)->flags &= ~(v & FLAGS_MASK))
211 #define getflags(j) ((j)->flags & FLAGS_MASK)
212 #define getmagic(j) ((j)->magic & BTREE_MAGIC_MASK)
213 #define clearflags(j) ((j)->flags = 0, (j)->magic = BTREE_MAGIC)
216 /* check that a node is in fact a node */
217 #define isnode(j) (((j) != NONODE) && (((j)->magic & BTREE_MAGIC_MASK) == BTREE_MAGIC) && !((j)->flags & isDATA))
218 #define isntnode(j) ((j) == NONODE)
221 /* test individual flag values */
222 #define isinternal(j) (((j)->flags & isLEAF) == 0)
223 #define isleaf(j) (((j)->flags & isLEAF) == isLEAF)
224 #define isdata(j) (((j)->flags & isDATA) == isDATA)
226 #define isroot(j) (((j)->flags & isROOT) == isROOT)
227 #define isfull(j) (((j)->flags & isFULL) == isFULL)
228 #define isfew(j) (((j)->flags & FEWEST) == FEWEST)
230 #define isroot(j) _isRoot(B, j)
231 #define isfew(j) _isFew(B, j)
232 #define isfull(j) _isFull(B, j)
235 /* manage number of keys in a node */
236 #define numentries(j) (nAdr(j).i.pairs)
237 #define clearentries(j) (nAdr(j).i.pairs = 0)
238 #define incentries(j) (nAdr(j).i.pairs++)
239 #define decentries(j) (nAdr(j).i.pairs--)
242 /* manage first/last node pointers in internal nodes */
243 #define setfirstnode(j, v) (nAdr(j).i.firstNode = (v))
244 #define getfirstnode(j) (nAdr(j).i.firstNode)
245 #define getlastnode(j) (nAdr(j).e[nAdr(j).i.pairs].downNode)
248 /* manage pointers to next nodes in leaf nodes */
249 /* also used for free nodes list */
250 #define setnextnode(j, v) (nAdr(j).l.nextNode = (v))
251 #define getnextnode(j) (nAdr(j).l.nextNode)
253 /* manage pointers to all nodes list */
254 #define setallnode(j, v) ((j)->pool = (v))
255 #define getallnode(j) ((j)->pool)
257 /* manage access to data nodes */
258 #define getdata(j) (nAdr(j).d)
259 #define getdatavalue(j) (getdata(j).value)
260 #define getdatakey(j) (getdata(j).key)
261 #define getdatanext(j) (getdata(j).next)
263 /* shift/transfer entries for insertion/deletion */
264 #define clrentry(j, q) _clrentry(j,q)
265 #define pushentry(j, q, v) _pushentry(j, q, v)
266 #define pullentry(j, q, v) _pullentry(j, q, v)
267 #define xferentry(j, q, v, z) _xferentry(j, q, v, z)
268 #define setentry(j, q, v, z) _setentry(j, q, v, z)
270 /* define number of B+tree nodes for free node pool */
271 #define getpoolsize(B) ((B)->poolsize)
272 #define setpoolsize(B,v) ((B)->poolsize = (v))
274 /* locations from which tree access begins */
275 #define getroot(B) ((B)->root)
276 #define setroot(B,v) ((B)->root = (v))
277 #define getleaf(B) ((B)->leaf)
278 #define setleaf(B,v) ((B)->leaf = (v))
280 /* define max/min number of pointers per node */
281 #define getfanout(B) ((B)->fanout)
282 #define setfanout(B,v) ((B)->fanout = (v) - 1)
283 #define getminfanout(B,j) (isroot(j) ? (isleaf(j) ? 0 : 1) : (isleaf(j) ? (B)->fanout - (B)->minfanout: (B)->minfanout))
284 #define setminfanout(B,v) ((B)->minfanout = (v) - 1)
286 /* manage B+tree height */
287 #define inittreeheight(B) ((B)->height = 0)
288 #define inctreeheight(B) ((B)->height++)
289 #define dectreeheight(B) ((B)->height--)
290 #define gettreeheight(B) ((B)->height)
292 /* access pool of free nodes */
293 #define getfirstfreenode(B) ((B)->empty)
294 #define setfirstfreenode(B,v) ((B)->empty = (v))
296 /* access all node list */
297 #define getfirstallnode(B) ((B)->pool)
298 #define setfirstallnode(B,v) ((B)->pool = (v))
300 /* handle split/merge points during insert/delete */
301 #define getsplitpath(B) ((B)->branch.split)
302 #define setsplitpath(B,v) ((B)->branch.split = (v))
303 #define getmergepath(B) ((B)->branch.merge)
304 #define setmergepath(B,v) ((B)->branch.merge = (v))
306 /* exploit function to compare two B+tree keys */
307 #define comparekeys(B) (*(B)->keycmp)
308 #define setcomparekeys(B,v) ((B)->keycmp = (v))
310 /* location containing B+tree class variables */
311 #define setbplustree(B,v) ((B) = (Tree *)(v))
313 /* representation independent node numbering */
314 #define setnodenumber(B,v,q) ((v)->number = (q))
315 #define getnodenumber(B,v) ((v) != NONODE ? (v)->number : -1)
317 #endif /* BPLUSTREE_H */