# btree.h

Go to the documentation of this file.

    00001 #ifndef BTREE_H
    00002 #define BTREE_H
    00003
    00004 #include <stdio.h>
    00005
    00006 #include "ubixfs.h"
    00007 #include "btreeheader.h"
    00008 #include "file.h"
    00009
    00010 #define B_NODE_MAGIC_1 0xDEADBEEF
    00011 #define B_NODE_MAGIC_2 0x1900BABE
    00012
    00013 #define B_MAX_KEYS 15
    00014 #define B_MAX_NAME_LENGTH 240
    00015 #define B_MAX_CHILD_COUNT 4
    00016
    00017 // if any of these structs change they have to be updated in the format
    00018 // utility too
    00019
    00020 typedef struct bNode {
    00021   uInt32  magic1                          __attribute__ ((packed));
    00022   uInt32  used                            __attribute__ ((packed));
    00023   uPtr    parent                          __attribute__ ((packed));
    00024   uInt64  tag                             __attribute__ ((packed));
    00025   char    keys[B_MAX_KEYS][B_MAX_NAME_LENGTH]      __attribute__ ((packed));
    00026   bool    present[B_MAX_KEYS+1]           __attribute__ ((packed));
    00027   uPtr    head[B_MAX_KEYS+1]              __attribute__ ((packed));
    00028   uPtr    tail[B_MAX_KEYS+1]              __attribute__ ((packed));
    00029   uInt32   childCount[B_MAX_KEYS+1]        __attribute__ ((packed));
    00030   uInt32  magic2                          __attribute__ ((packed));
    00031   bool    leaf                            __attribute__ ((packed));
    00032   char reserved[131] __attribute__ ((packed));
    00033 } bNode; // bNode
    00034
    00035 struct ubixfsInode;
    00036
    00037 class bTree {
    00038  protected:
    00039   bNode          * root;
    00040   UbixFS         * fs;
    00041   bTreeHeader    * header;
    00042   fileDescriptor * fd;
    00043   uInt32           tag;
    00044   ubixfsInode    * treeSearch(bNode *, const char *);
    00045   ubixfsInode    * inodeSearch(ubixfsInode *, const char *);
    00046   void             splitNode(bNode *);
    00047   bNode          * allocEmptyNode(void);
    00048   void             insertNode(bNode *, const char *, bNode *);
    00049   bNode          * findLeafNode(bNode *, const char *);
    00050   void             Print(bNode *);
    00051   void             saveNode(FILE *, bNode *, void *);
    00052  public:
    00053                    bTree(const char *, ubixfsInode *);
    00054                    bTree(UbixFS *, fileDescriptor *);
    00055   ubixfsInode    * Find(const char *);
    00056   ubixfsInode    * GetFirstNode(void);
    00057   ubixfsInode    * GetFirstNode(bNode *);
    00058   bool             Delete(const char *);
    00059   void             Info(void);
    00060   void             Info(const bNode *);
    00061   bool             Insert(const char *, ubixfsInode *);
    00062   bool             Save(const char *);
    00063   bool             Load(const char *);
    00064   void             Print(void);
    00065   void             PrintWholeTree(void);
    00066   bool             Verify(void);
    00067                   ~bTree(void);
    00068   friend class UbixFS;
    00069 }; // bTree
    00070 #endif // !BTREE_H