UbixOS V2  2.0
btree.h
Go to the documentation of this file.
1 /*
2 #ifndef BTREE_H
3 #define BTREE_H
4 
5 #include <stdio.h>
6 
7 #include "ubixfs.h"
8 #include "btreeheader.h"
9 #include "file.h"
10 
11 #define B_NODE_MAGIC_1 0xDEADBEEF
12 #define B_NODE_MAGIC_2 0x1900BABE
13 
14 #define B_MAX_KEYS 15
15 #define B_MAX_NAME_LENGTH 240
16 #define B_MAX_CHILD_COUNT 4
17 
18 // if any of these structs change they have to be updated in the format
19 // utility too
20 
21 typedef struct bNode {
22  uInt32 magic1 __attribute__ ((packed));
23  uInt32 used __attribute__ ((packed));
24  uPtr parent __attribute__ ((packed));
25  uInt64 tag __attribute__ ((packed));
26  char keys[B_MAX_KEYS][B_MAX_NAME_LENGTH] __attribute__ ((packed));
27  bool present[B_MAX_KEYS+1] __attribute__ ((packed));
28  uPtr head[B_MAX_KEYS+1] __attribute__ ((packed));
29  uPtr tail[B_MAX_KEYS+1] __attribute__ ((packed));
30  uInt32 childCount[B_MAX_KEYS+1] __attribute__ ((packed));
31  uInt32 magic2 __attribute__ ((packed));
32  bool leaf __attribute__ ((packed));
33  char reserved[131] __attribute__ ((packed));
34 } bNode; // bNode
35 
36 struct ubixfsInode;
37 
38 class bTree {
39  protected:
40  bNode * root;
41  UbixFS * fs;
42  bTreeHeader * header;
43  fileDescriptor * fd;
44  uInt32 tag;
45  ubixfsInode * treeSearch(bNode *, const char *);
46  ubixfsInode * inodeSearch(ubixfsInode *, const char *);
47  void splitNode(bNode *);
48  bNode * allocEmptyNode(void);
49  void insertNode(bNode *, const char *, bNode *);
50  bNode * findLeafNode(bNode *, const char *);
51  void Print(bNode *);
52  void saveNode(FILE *, bNode *, void *);
53  public:
54  bTree(const char *, ubixfsInode *);
55  bTree(UbixFS *, fileDescriptor *);
56  ubixfsInode * Find(const char *);
57  ubixfsInode * GetFirstNode(void);
58  ubixfsInode * GetFirstNode(bNode *);
59  bool Delete(const char *);
60  void Info(void);
61  void Info(const bNode *);
62  bool Insert(const char *, ubixfsInode *);
63  bool Save(const char *);
64  bool Load(const char *);
65  void Print(void);
66  void PrintWholeTree(void);
67  bool Verify(void);
68  ~bTree(void);
69  friend class UbixFS;
70 }; // bTree
71 #endif // !BTREE_H
72 */