core: Add Mtree
Change-Id: I80205fb0d1f4ee5bcbc6c73651bb697fe854bf53
diff --git a/core/merkle-tree-cache.hpp b/core/merkle-tree-cache.hpp
new file mode 100644
index 0000000..97e8908
--- /dev/null
+++ b/core/merkle-tree-cache.hpp
@@ -0,0 +1,176 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014, Regents of the University of California
+ *
+ * This file is part of NSL (NDN Signature Logger).
+ * See AUTHORS.md for complete list of NSL authors and contributors.
+ *
+ * NSL is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NSL is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NSL, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * @author Peizhen Guo <patrick.guopz@gmail.com>
+ */
+#ifndef NLS_CORE_MERKLE_TREE_CACHE_HPP
+#define NLS_CORE_MERKLE_TREE_CACHE_HPP
+
+#include <map>
+#include <vector>
+
+#include "sub-tree.hpp"
+#include "leaf.hpp"
+#include "intermediate-node.hpp"
+#include "merkle-tree-sqlite3.hpp"
+
+
+namespace nsl {
+
+
+typedef ndn::shared_ptr<const SubTree> ConstSubTreePtr;
+typedef ndn::shared_ptr<SubTree> SubTreePtr;
+typedef ndn::shared_ptr<const Node> ConstNodePtr;
+typedef ndn::shared_ptr<Node> NodePtr;
+
+class MerkleTreeCache
+{
+public:
+
+ MerkleTreeCache()
+ :m_nLevels(0),
+ m_nLeaves(0)
+ {
+ }
+
+ ~MerkleTreeCache()
+ {
+ }
+
+ uint8_t
+ getLevel()
+ {
+ return m_nLevels;
+ }
+
+ uint64_t
+ getLeaves()
+ {
+ return m_nLeaves;
+ }
+
+ SubTreePtr
+ getSubTree(Index rootIndex)
+ {
+ if (m_cachedTree.count(rootIndex) > 0)
+ {
+ //std::cout<<"I'm here!"<<int(m_cachedTree[rootIndex]->getRemainPosition())<<std::endl;
+ return m_cachedTree[rootIndex];
+ }
+ else
+ {
+ std::string treeString = m_database.getSubTree(rootIndex);
+ SubTreePtr newtree = decoding(treeString);
+ return newtree;
+ }
+ }
+
+ // Do the update when a subtree is full
+ // Iteratively: find parent --> check full --> ... --> if not full -->
+ // create subtree --> create subsubtree --> ... --> until down to the leaf
+ // invoke a subtree.updateHash(), and decide whether to add new subtrees according to the callback
+ // remainPosition value.
+ void
+ update(Index subRootIndex, uint8_t subRemainNum, ndn::ConstBufferPtr subRootHash);
+
+ void
+ addLeaf(Leaf newLeaf);
+
+ NodePtr
+ queryNode(Index nodeIndex);
+
+ bool
+ doesNodeExist(Index nodeIndex);
+
+ void
+ loadSubTreeFromDatabase(Index rootIndex);
+
+ void
+ loadLeafFromDatabase(uint64_t sequence);
+
+
+
+ SubTreePtr
+ decoding(std::string subTreeInfo);
+
+ // remove the comment to test sqlite3 function
+ // MerkleTreeSqlite3 m_database;
+
+ // To show the exact size of the cache
+ // std::map<Index, SubTreePtr> m_cachedTree;
+ // std::map<uint64_t, ndn::ConstBufferPtr> m_leavesData;
+
+
+private:
+
+ // find which subTree the node belongs to (not include root node)
+ Index
+ findSubTree(Index nodeIndex);
+
+ // find a subTree's parent root index
+ Index
+ getParentRootIndex(Index thisRootIndex);
+
+
+ // To be finished
+ uint8_t
+ doesCacheFull()
+ {
+ if (m_cachedTree.size() >= 3 && m_leavesData.size() >= 64)
+ {
+ return 3;
+ }
+ else if (m_cachedTree.size() >= 3 && m_leavesData.size() < 64)
+ {
+ return 2;
+ }
+ else if (m_cachedTree.size() < 3 && m_leavesData.size() >= 64)
+ {
+ return 1;
+ }
+ else
+ {
+ return 0;
+ }
+ }
+
+ // choose a cache item to remove,
+ // exactly remove items from cache only when: 1)have full subtrees 2)cache is full
+ void
+ removeSubTree();
+
+ void
+ removeLeaf();
+
+private:
+ // partly in cache, completely in db
+ std::map<Index, SubTreePtr> m_cachedTree;
+ std::map<uint64_t, ndn::ConstBufferPtr> m_leavesData; //starts from 0(same as leaf)
+
+ // completely in memory, add & delete with time
+ std::map<Index, int> m_timeFromLastUse;
+ uint8_t m_nLevels; // levels counted based on subtree unit
+ uint64_t m_nLeaves; // sequence number + 1
+
+ // sqlite3 database
+ MerkleTreeSqlite3 m_database;
+};
+
+} // namespace nsl
+
+#endif // NLS_CORE_MERKLE_TREE_CACHE_HPP