src/WINNT/afsd/cm_btree.h

   1 /*
   2  * Copyright 2007 Secure Endpoints Inc.
   3  *
   4  * All Rights Reserved.
   5  *
   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
   9  *
  10  * Thanks to Jan Jannink for B+ tree algorithms.
  11  */
  12
  13 #ifndef BPLUSTREE_H
  14 #define BPLUSTREE_H 1
  15
  16 /********       flag bits (5 of 16 used, 11 for magic value)    ********/
  17
  18 /* bits set at node creation/split/merge */
  19 #define isLEAF          0x01
  20 #define isROOT          0x02
  21 #define isDATA          0x04
  22
  23 /* bits set at key insertion/deletion */
  24 #define isFULL          0x08
  25 #define FEWEST          0x10
  26 #define FLAGS_MASK      0xFF
  27
  28 /* identifies data as being a B+tree node */
  29 #define BTREE_MAGIC           0xBEE0BEE0
  30 #define BTREE_MAGIC_MASK      0xFFFFFFFF
  31
  32
  33 /*************************      constants       ************************/
  34
  35 /* The maximum number of Entrys in one Node */
  36 #define MAX_FANOUT      9
  37
  38 /* corresponds to a NULL node pointer value */
  39 #define NONODE          NULL
  40
  41 /* special node slot values used in key search */
  42 #define BTERROR         -1
  43 #define BTUPPER         -2
  44 #define BTLOWER         -3
  45
  46
  47 /************************* Data Types **********************************/
  48 typedef struct node     *Nptr;
  49
  50 typedef struct key {
  51     normchar_t  *name;           /* Normalized name */
  52 } keyT;
  53
  54 typedef struct dirdata {
  55     cm_fid_t    fid;
  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
  60                                    this fid. */
  61     clientchar_t  *cname;          /* Client name (long) */
  62     fschar_t * fsname;         /* FileServer name */
  63 } dataT;
  64
  65 typedef struct entry {
  66     keyT        key;
  67     Nptr        downNode;
  68 } Entry;
  69
  70 typedef struct inner {
  71     short       pairs;
  72     Nptr        firstNode;
  73 } Inner;
  74
  75
  76 typedef struct leaf {
  77     short       pairs;
  78     Nptr        nextNode;
  79 } Leaf;
  80
  81 typedef struct btree_data {
  82     keyT        key;
  83     dataT       value;
  84     Nptr        next;
  85 } Data;
  86
  87 typedef struct node {
  88     Nptr                pool;
  89     unsigned short      number;
  90     unsigned short      flags;
  91     unsigned long       magic;
  92     union {
  93         Entry   e[MAX_FANOUT];  /* allows access to entry array */
  94         Inner   i;
  95         Leaf    l;
  96         Data    d;
  97     } X;
  98 } Node;
  99
 100
 101 typedef int (*KeyCmp)(keyT, keyT, int);
 102 #define EXACT_MATCH 0x01
 103
 104
 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 */
 117         Nptr    merge;
 118     } branch;
 119     KeyCmp      keycmp;                 /* pointer to function comparing two keys */
 120     char message[1024];
 121 } Tree;
 122
 123 #define TREE_FLAGS_MASK                 0x01
 124 #define TREE_FLAG_UNIQUE_KEYS           0x01
 125
 126 /************************* B+ tree Public functions ****************/
 127 Tree    *initBtree(unsigned int poolsz, unsigned int fan, KeyCmp keyCmp);
 128 void    freeBtree(Tree *B);
 129
 130 #ifdef DEBUG_BTREE
 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);
 137 #endif
 138
 139 void    insert(Tree *B, keyT key, dataT data);
 140 void    delete(Tree *B, keyT key);
 141 Nptr    lookup(Tree *B, keyT key);
 142
 143 /******************* cache manager directory operations ***************/
 144
 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);
 154
 155 /******************* directory enumeration operations ****************/
 156 typedef struct cm_direnum_entry {
 157     clientchar_t *name;
 158     cm_fid_t     fid;
 159     normchar_t   shortName[13];
 160     afs_uint32   flags;
 161     afs_uint32   errorCode;
 162 } cm_direnum_entry_t;
 163
 164 #define CM_DIRENUM_FLAG_GOT_STATUS     1
 165
 166 typedef struct cm_direnum {
 167     cm_scache_t        *dscp;
 168     cm_user_t          *userp;
 169     afs_uint64          dataVersion;    /* enumeration snapshot dir version */
 170     afs_uint32          reqFlags;
 171     afs_uint32          count;
 172     afs_uint32          next;
 173     afs_uint32          fetchStatus;
 174     cm_direnum_entry_t  entry[1];
 175 } cm_direnum_t;
 176
 177 long cm_BPlusDirEnumerate(cm_scache_t *dscp, cm_user_t *userp, cm_req_t *reqp,
 178                           afs_uint32 locked, clientchar_t *maskp, afs_uint32 fetchStatus, cm_direnum_t **enumpp);
 179 long cm_BPlusDirNextEnumEntry(cm_direnum_t *enump, cm_direnum_entry_t **entrypp);
 180 long cm_BPlusDirPeekNextEnumEntry(cm_direnum_t *enump, cm_direnum_entry_t **entrypp);
 181 long cm_BPlusDirFreeEnumeration(cm_direnum_t *enump);
 182 long cm_BPlusDirEnumTest(cm_scache_t * dscp, cm_user_t *userp, cm_req_t *reqp, afs_uint32 locked);
 183 long cm_BPlusDirEnumBulkStat(cm_direnum_t *enump);
 184 long cm_BPlusDirEnumBulkStatOne(cm_direnum_t *enump, cm_scache_t *scp);
 185
 186 long cm_InitBPlusDir(void);
 187
 188 /************ Statistic Counter ***************************************/
 189
 190 extern afs_uint32 bplus_free_tree;
 191 extern afs_uint32 bplus_dv_error;
 192 extern afs_uint64 bplus_free_time;
 193
 194
 195 /************ Accessor Macros *****************************************/
 196
 197 /* low level definition of Nptr value usage */
 198 #define nAdr(n) (n)->X
 199
 200 /* access keys and pointers in a node */
 201 #define getkey(j, q) (nAdr(j).e[(q)].key)
 202 #define getnode(j, q) (nAdr(j).e[(q)].downNode)
 203 #define setkey(j, q, v) ((q > 0) ? nAdr(j).e[(q)].key.name = cm_NormStrDup((v).name) : NULL)
 204 #define setnode(j, q, v) (nAdr(j).e[(q)].downNode = (v))
 205
 206 /* access tree flag values */
 207 #define settreeflags(B,v) (B->flags |= (v & TREE_FLAGS_MASK))
 208 #define gettreeflags(B)   (B->flags)
 209 #define cleartreeflags(B) (B->flags = 0);
 210
 211 /* access node flag values */
 212 #define setflag(j, v) ((j)->flags |= (v & FLAGS_MASK))
 213 #define clrflag(j, v) ((j)->flags &= ~(v & FLAGS_MASK))
 214 #define getflags(j) ((j)->flags & FLAGS_MASK)
 215 #define getmagic(j)  ((j)->magic & BTREE_MAGIC_MASK)
 216 #define clearflags(j) ((j)->flags = 0, (j)->magic = BTREE_MAGIC)
 217
 218
 219 /* check that a node is in fact a node */
 220 #define isnode(j) (((j) != NONODE) && (((j)->magic & BTREE_MAGIC_MASK) == BTREE_MAGIC) && !((j)->flags & isDATA))
 221 #define isntnode(j) ((j) == NONODE)
 222
 223
 224 /* test individual flag values */
 225 #define isinternal(j) (((j)->flags & isLEAF) == 0)
 226 #define isleaf(j) (((j)->flags & isLEAF) == isLEAF)
 227 #define isdata(j) (((j)->flags & isDATA) == isDATA)
 228 #ifndef DEBUG_BTREE
 229 #define isroot(j) (((j)->flags & isROOT) == isROOT)
 230 #define isfull(j) (((j)->flags & isFULL) == isFULL)
 231 #define isfew(j) (((j)->flags & FEWEST) == FEWEST)
 232 #else
 233 #define isroot(j) _isRoot(B, j)
 234 #define isfew(j) _isFew(B, j)
 235 #define isfull(j) _isFull(B, j)
 236 #endif
 237
 238 /* manage number of keys in a node */
 239 #define numentries(j) (nAdr(j).i.pairs)
 240 #define clearentries(j) (nAdr(j).i.pairs = 0)
 241 #define incentries(j) (nAdr(j).i.pairs++)
 242 #define decentries(j) (nAdr(j).i.pairs--)
 243
 244
 245 /* manage first/last node pointers in internal nodes */
 246 #define setfirstnode(j, v) (nAdr(j).i.firstNode = (v))
 247 #define getfirstnode(j) (nAdr(j).i.firstNode)
 248 #define getlastnode(j) (nAdr(j).e[nAdr(j).i.pairs].downNode)
 249
 250
 251 /* manage pointers to next nodes in leaf nodes */
 252 /* also used for free nodes list */
 253 #define setnextnode(j, v) (nAdr(j).l.nextNode = (v))
 254 #define getnextnode(j) (nAdr(j).l.nextNode)
 255
 256 /* manage pointers to all nodes list */
 257 #define setallnode(j, v) ((j)->pool = (v))
 258 #define getallnode(j) ((j)->pool)
 259
 260 /* manage access to data nodes */
 261 #define getdata(j) (nAdr(j).d)
 262 #define getdatavalue(j) (getdata(j).value)
 263 #define getdatakey(j)   (getdata(j).key)
 264 #define getdatanext(j)  (getdata(j).next)
 265
 266 /* shift/transfer entries for insertion/deletion */
 267 #define clrentry(j, q) _clrentry(j,q)
 268 #define pushentry(j, q, v) _pushentry(j, q, v)
 269 #define pullentry(j, q, v) _pullentry(j, q, v)
 270 #define xferentry(j, q, v, z) _xferentry(j, q, v, z)
 271 #define setentry(j, q, v, z) _setentry(j, q, v, z)
 272
 273 /* define number of B+tree nodes for free node pool */
 274 #define getpoolsize(B) ((B)->poolsize)
 275 #define setpoolsize(B,v) ((B)->poolsize = (v))
 276
 277 /* locations from which tree access begins */
 278 #define getroot(B) ((B)->root)
 279 #define setroot(B,v) ((B)->root = (v))
 280 #define getleaf(B) ((B)->leaf)
 281 #define setleaf(B,v) ((B)->leaf = (v))
 282
 283 /* define max/min number of pointers per node */
 284 #define getfanout(B) ((B)->fanout)
 285 #define setfanout(B,v) ((B)->fanout = (v) - 1)
 286 #define getminfanout(B,j) (isroot(j) ? (isleaf(j) ? 0 : 1) : (isleaf(j) ? (B)->fanout - (B)->minfanout: (B)->minfanout))
 287 #define setminfanout(B,v) ((B)->minfanout = (v) - 1)
 288
 289 /* manage B+tree height */
 290 #define inittreeheight(B) ((B)->height = 0)
 291 #define inctreeheight(B) ((B)->height++)
 292 #define dectreeheight(B) ((B)->height--)
 293 #define gettreeheight(B) ((B)->height)
 294
 295 /* access pool of free nodes */
 296 #define getfirstfreenode(B) ((B)->empty)
 297 #define setfirstfreenode(B,v) ((B)->empty = (v))
 298
 299 /* access all node list */
 300 #define getfirstallnode(B) ((B)->pool)
 301 #define setfirstallnode(B,v) ((B)->pool = (v))
 302
 303 /* handle split/merge points during insert/delete */
 304 #define getsplitpath(B) ((B)->branch.split)
 305 #define setsplitpath(B,v) ((B)->branch.split = (v))
 306 #define getmergepath(B) ((B)->branch.merge)
 307 #define setmergepath(B,v) ((B)->branch.merge = (v))
 308
 309 /* exploit function to compare two B+tree keys */
 310 #define comparekeys(B) (*(B)->keycmp)
 311 #define setcomparekeys(B,v) ((B)->keycmp = (v))
 312
 313 /* location containing B+tree class variables */
 314 #define setbplustree(B,v) ((B) = (Tree *)(v))
 315
 316 /* representation independent node numbering */
 317 #define setnodenumber(B,v,q) ((v)->number = (q))
 318 #define getnodenumber(B,v) ((v) != NONODE ? (v)->number : -1)
 319
 320 #endif /* BPLUSTREE_H */
 321