#ifndef BTREE_H
#define BTREE_H

#include "superblock.h"
#include "inode.h"

#define B_NODE_MAGIC_1 0xDEADBEEF
#define B_NODE_MAGIC_2 0x1900BABE

#define B_MAX_KEYS 15
#define B_MAX_NAME_LENGTH 240
#define B_MAX_CHILD_COUNT 4

// if any of these structs change they have to be updated in the format
// utility too

typedef struct bNode { 
  uInt32  magic1                          __attribute__ ((packed));
  uInt32  used                            __attribute__ ((packed));
  bNode * parent                          __attribute__ ((packed));
  char    keys[B_MAX_KEYS][B_MAX_NAME_LENGTH]      __attribute__ ((packed));
  bool    present[B_MAX_KEYS+1]           __attribute__ ((packed));
  void *  head[(B_MAX_KEYS+1)*8/sizeof(void *)]   __attribute__ ((packed));
  void *  tail[(B_MAX_KEYS+1)*8/sizeof(void *)]  __attribute__ ((packed));
  uInt32   childCount[B_MAX_KEYS+1]        __attribute__ ((packed));
  uInt32  magic2                          __attribute__ ((packed));
  bool    leaf                            __attribute__ ((packed));
  char reserved[143] __attribute__ ((packed));
} bNode; // bNode


typedef struct bTreeHeader {
  uInt32 treeDepth;
  uInt32 treeWidth;
  uInt32 treeLeafCount;
  int32 firstDeleted;
} bTreeHeader; // bTreeHeader

class bTree {
 protected:
  bNode * root;
  uInt32 treeDepth;
  uInt32 treeWidth;
  uInt32 treeLeafCount;
  int32 firstDeleted;
  ubixfsInode * treeSearch(bNode *, const char *);
  ubixfsInode * inodeSearch(ubixfsInode *, const char *);
  void          splitNode(bNode *);
  bNode *       allocEmptyNode(void);
  void          insertNode(bNode *, const char *, void *, void *);
  bNode *       findLeafNode(bNode *, const char *);
  void          Print(bNode *);
 public:
                bTree(ubixfsInode *);
                bTree(void) : root(NULL), treeDepth(0) { };
  ubixfsInode * Find(const char *);
  ubixfsInode * GetFirstNode(void);
  ubixfsInode * GetFirstNode(bNode *);
  bool          Delete(const char *);
  void          Info(void);
  void          Info(const bNode *);
  bool          Insert(ubixfsInode *);
  bool          Save(const char *);
  bool          Load(const char *);
  void          Print(void);
  void          PrintWholeTree(void);
  bool          Verify(void);
               ~bTree(void);
}; // bTree
#endif // !BTREE_H