Project: finder, src: BPTreeCore.h

#ifndef BPTREECORE_H_
#define BPTREECORE_H_

#include <vector>
#include <stack>
#include <string>
#include <unistd.h>
#include "Serializer.h"
#include "NGram.h"

#define BPTREE_ELEMENT_SIZE (256)

/**
 * B++ Tree の実装
 */
class BPTreeCore {
 public:
   struct Element : public Serializer {
     NGram key;
     off_t offset;
     Element(const NGram &key, off_t offset) : key(key), offset(offset) {}
     bool operator < (const Element &e) const {
       return key < e.key;
     }
     void writeObject(int fd) const;
     void readObject(int fd);
   };

   struct Node : public Serializer {
     std::vector<BPTreeCore::Element> elements;
     int level;
     int last;
     off_t offset;
     Node() : level(0), last(0), offset(0), elements() {}
     void writeObject(int fd) const;
     void readObject(int fd);
   };

 private:
   int fd;
   bool bCreated;
   void initialFill();
   void splitNode(std::stack<BPTreeCore::Node> &stack, BPTreeCore::Node &node, const NGram &key);
   static int bsearch(const std::vector<BPTreeCore::Element> &elements, const NGram &key);

 public:
   BPTreeCore(const std::string &filename, bool bTruncate = true);
   BPTreeCore(int fd);
   virtual ~BPTreeCore();

   void append(const NGram &key, off_t value);
   bool find(const NGram &key, off_t *pvalue) const;
};

#endif //BPTREECORE_H_