diff options
Diffstat (limited to 'MemTrie.cpp')
| -rw-r--r-- | MemTrie.cpp | 482 |
1 files changed, 0 insertions, 482 deletions
diff --git a/MemTrie.cpp b/MemTrie.cpp deleted file mode 100644 index ab5a13b6..00000000 --- a/MemTrie.cpp +++ /dev/null @@ -1,482 +0,0 @@ -/* - This file is part of cpp-ethereum. - - cpp-ethereum 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. - - cpp-ethereum 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. -*/ -/** @file MemTrie.cpp - * @author Gav Wood <i@gavwood.com> - * @date 2014 - */ - -#include "MemTrie.h" - -#include <libdevcrypto/TrieCommon.h> -#include <libdevcrypto/SHA3.h> -#include <libethcore/Common.h> -using namespace std; -using namespace dev; -using namespace dev::eth; - -namespace dev -{ - -#define ENABLE_DEBUG_PRINT 0 - -/*/ -#define APPEND_CHILD appendData -/*/ -#define APPEND_CHILD appendRaw -/**/ - -class MemTrieNode -{ -public: - MemTrieNode() {} - virtual ~MemTrieNode() {} - - virtual std::string const& at(bytesConstRef _key) const = 0; - virtual MemTrieNode* insert(bytesConstRef _key, std::string const& _value) = 0; - virtual MemTrieNode* remove(bytesConstRef _key) = 0; - void putRLP(RLPStream& _parentStream) const; - -#if ENABLE_DEBUG_PRINT - void debugPrint(std::string const& _indent = "") const { std::cerr << std::hex << hash256() << ":" << std::dec << std::endl; debugPrintBody(_indent); } -#endif - - /// 256-bit hash of the node - this is a SHA-3/256 hash of the RLP of the node. - h256 hash256() const { RLPStream s; makeRLP(s); return dev::sha3(s.out()); } - bytes rlp() const { RLPStream s; makeRLP(s); return s.out(); } - void mark() { m_hash256 = h256(); } - -protected: - virtual void makeRLP(RLPStream& _intoStream) const = 0; - -#if ENABLE_DEBUG_PRINT - virtual void debugPrintBody(std::string const& _indent = "") const = 0; -#endif - - static MemTrieNode* newBranch(bytesConstRef _k1, std::string const& _v1, bytesConstRef _k2, std::string const& _v2); - -private: - mutable h256 m_hash256; -}; - -static const std::string c_nullString; - -class TrieExtNode: public MemTrieNode -{ -public: - TrieExtNode(bytesConstRef _bytes): m_ext(_bytes.begin(), _bytes.end()) {} - - bytes m_ext; -}; - -class TrieBranchNode: public MemTrieNode -{ -public: - TrieBranchNode(std::string const& _value): m_value(_value) - { - memset(m_nodes.data(), 0, sizeof(MemTrieNode*) * 16); - } - - TrieBranchNode(byte _i1, MemTrieNode* _n1, std::string const& _value = std::string()): m_value(_value) - { - memset(m_nodes.data(), 0, sizeof(MemTrieNode*) * 16); - m_nodes[_i1] = _n1; - } - - TrieBranchNode(byte _i1, MemTrieNode* _n1, byte _i2, MemTrieNode* _n2) - { - memset(m_nodes.data(), 0, sizeof(MemTrieNode*) * 16); - m_nodes[_i1] = _n1; - m_nodes[_i2] = _n2; - } - - virtual ~TrieBranchNode() - { - for (auto i: m_nodes) - delete i; - } - -#if ENABLE_DEBUG_PRINT - virtual void debugPrintBody(std::string const& _indent) const - { - - if (m_value.size()) - std::cerr << _indent << "@: " << m_value << std::endl; - for (auto i = 0; i < 16; ++i) - if (m_nodes[i]) - { - std::cerr << _indent << std::hex << i << ": " << std::dec; - m_nodes[i]->debugPrint(_indent + " "); - } - } -#endif - - virtual std::string const& at(bytesConstRef _key) const override; - virtual MemTrieNode* insert(bytesConstRef _key, std::string const& _value) override; - virtual MemTrieNode* remove(bytesConstRef _key) override; - virtual void makeRLP(RLPStream& _parentStream) const override; - -private: - /// @returns (byte)-1 when no active branches, 16 when multiple active and the index of the active branch otherwise. - byte activeBranch() const; - - MemTrieNode* rejig(); - - std::array<MemTrieNode*, 16> m_nodes; - std::string m_value; -}; - -class TrieLeafNode: public TrieExtNode -{ -public: - TrieLeafNode(bytesConstRef _key, std::string const& _value): TrieExtNode(_key), m_value(_value) {} - -#if ENABLE_DEBUG_PRINT - virtual void debugPrintBody(std::string const& _indent) const - { - assert(m_value.size()); - std::cerr << _indent; - if (m_ext.size()) - std::cerr << toHex(m_ext, 1) << ": "; - else - std::cerr << "@: "; - std::cerr << m_value << std::endl; - } -#endif - - virtual std::string const& at(bytesConstRef _key) const override { return contains(_key) ? m_value : c_nullString; } - virtual MemTrieNode* insert(bytesConstRef _key, std::string const& _value) override; - virtual MemTrieNode* remove(bytesConstRef _key) override; - virtual void makeRLP(RLPStream& _parentStream) const override; - -private: - bool contains(bytesConstRef _key) const { return _key.size() == m_ext.size() && !memcmp(_key.data(), m_ext.data(), _key.size()); } - - std::string m_value; -}; - -class TrieInfixNode: public TrieExtNode -{ -public: - TrieInfixNode(bytesConstRef _key, MemTrieNode* _next): TrieExtNode(_key), m_next(_next) {} - virtual ~TrieInfixNode() { delete m_next; } - -#if ENABLE_DEBUG_PRINT - virtual void debugPrintBody(std::string const& _indent) const - { - std::cerr << _indent << toHex(m_ext, 1) << ": "; - m_next->debugPrint(_indent + " "); - } -#endif - - virtual std::string const& at(bytesConstRef _key) const override { assert(m_next); return contains(_key) ? m_next->at(_key.cropped(m_ext.size())) : c_nullString; } - virtual MemTrieNode* insert(bytesConstRef _key, std::string const& _value) override; - virtual MemTrieNode* remove(bytesConstRef _key) override; - virtual void makeRLP(RLPStream& _parentStream) const override; - -private: - bool contains(bytesConstRef _key) const { return _key.size() >= m_ext.size() && !memcmp(_key.data(), m_ext.data(), m_ext.size()); } - - MemTrieNode* m_next; -}; - -void MemTrieNode::putRLP(RLPStream& _parentStream) const -{ - RLPStream s; - makeRLP(s); - if (s.out().size() < 32) - _parentStream.APPEND_CHILD(s.out()); - else - _parentStream << dev::sha3(s.out()); -} - -void TrieBranchNode::makeRLP(RLPStream& _intoStream) const -{ - _intoStream.appendList(17); - for (auto i: m_nodes) - if (i) - i->putRLP(_intoStream); - else - _intoStream << ""; - _intoStream << m_value; -} - -void TrieLeafNode::makeRLP(RLPStream& _intoStream) const -{ - _intoStream.appendList(2) << hexPrefixEncode(m_ext, true) << m_value; -} - -void TrieInfixNode::makeRLP(RLPStream& _intoStream) const -{ - assert(m_next); - _intoStream.appendList(2); - _intoStream << hexPrefixEncode(m_ext, false); - m_next->putRLP(_intoStream); -} - -MemTrieNode* MemTrieNode::newBranch(bytesConstRef _k1, std::string const& _v1, bytesConstRef _k2, std::string const& _v2) -{ - unsigned prefix = commonPrefix(_k1, _k2); - - MemTrieNode* ret; - if (_k1.size() == prefix) - ret = new TrieBranchNode(_k2[prefix], new TrieLeafNode(_k2.cropped(prefix + 1), _v2), _v1); - else if (_k2.size() == prefix) - ret = new TrieBranchNode(_k1[prefix], new TrieLeafNode(_k1.cropped(prefix + 1), _v1), _v2); - else // both continue after split - ret = new TrieBranchNode(_k1[prefix], new TrieLeafNode(_k1.cropped(prefix + 1), _v1), _k2[prefix], new TrieLeafNode(_k2.cropped(prefix + 1), _v2)); - - if (prefix) - // have shared prefix - split. - ret = new TrieInfixNode(_k1.cropped(0, prefix), ret); - - return ret; -} - -std::string const& TrieBranchNode::at(bytesConstRef _key) const -{ - if (_key.empty()) - return m_value; - else if (m_nodes[_key[0]] != nullptr) - return m_nodes[_key[0]]->at(_key.cropped(1)); - return c_nullString; -} - -MemTrieNode* TrieBranchNode::insert(bytesConstRef _key, std::string const& _value) -{ - assert(_value.size()); - mark(); - if (_key.empty()) - m_value = _value; - else - if (!m_nodes[_key[0]]) - m_nodes[_key[0]] = new TrieLeafNode(_key.cropped(1), _value); - else - m_nodes[_key[0]] = m_nodes[_key[0]]->insert(_key.cropped(1), _value); - return this; -} - -MemTrieNode* TrieBranchNode::remove(bytesConstRef _key) -{ - if (_key.empty()) - if (m_value.size()) - { - m_value.clear(); - return rejig(); - } - else {} - else if (m_nodes[_key[0]] != nullptr) - { - m_nodes[_key[0]] = m_nodes[_key[0]]->remove(_key.cropped(1)); - return rejig(); - } - return this; -} - -MemTrieNode* TrieBranchNode::rejig() -{ - mark(); - byte n = activeBranch(); - - if (n == (byte)-1 && m_value.size()) - { - // switch to leaf - auto r = new TrieLeafNode(bytesConstRef(), m_value); - delete this; - return r; - } - else if (n < 16 && m_value.empty()) - { - // only branching to n... - if (auto b = dynamic_cast<TrieBranchNode*>(m_nodes[n])) - { - // switch to infix - m_nodes[n] = nullptr; - delete this; - return new TrieInfixNode(bytesConstRef(&n, 1), b); - } - else - { - auto x = dynamic_cast<TrieExtNode*>(m_nodes[n]); - assert(x); - // include in child - pushFront(x->m_ext, n); - m_nodes[n] = nullptr; - delete this; - return x; - } - } - - return this; -} - -byte TrieBranchNode::activeBranch() const -{ - byte n = (byte)-1; - for (int i = 0; i < 16; ++i) - if (m_nodes[i] != nullptr) - { - if (n == (byte)-1) - n = (byte)i; - else - return 16; - } - return n; -} - -MemTrieNode* TrieInfixNode::insert(bytesConstRef _key, std::string const& _value) -{ - assert(_value.size()); - mark(); - if (contains(_key)) - { - m_next = m_next->insert(_key.cropped(m_ext.size()), _value); - return this; - } - else - { - unsigned prefix = commonPrefix(_key, m_ext); - if (prefix) - { - // one infix becomes two infixes, then insert into the second - // instead of pop_front()... - trimFront(m_ext, prefix); - - return new TrieInfixNode(_key.cropped(0, prefix), insert(_key.cropped(prefix), _value)); - } - else - { - // split here. - auto f = m_ext[0]; - trimFront(m_ext, 1); - MemTrieNode* n = m_ext.empty() ? m_next : this; - if (n != this) - { - m_next = nullptr; - delete this; - } - TrieBranchNode* ret = new TrieBranchNode(f, n); - ret->insert(_key, _value); - return ret; - } - } -} - -MemTrieNode* TrieInfixNode::remove(bytesConstRef _key) -{ - if (contains(_key)) - { - mark(); - m_next = m_next->remove(_key.cropped(m_ext.size())); - if (auto p = dynamic_cast<TrieExtNode*>(m_next)) - { - // merge with child... - m_ext.reserve(m_ext.size() + p->m_ext.size()); - for (auto i: p->m_ext) - m_ext.push_back(i); - p->m_ext = m_ext; - p->mark(); - m_next = nullptr; - delete this; - return p; - } - if (!m_next) - { - delete this; - return nullptr; - } - } - return this; -} - -MemTrieNode* TrieLeafNode::insert(bytesConstRef _key, std::string const& _value) -{ - assert(_value.size()); - mark(); - if (contains(_key)) - { - m_value = _value; - return this; - } - else - { - // create new trie. - auto n = MemTrieNode::newBranch(_key, _value, bytesConstRef(&m_ext), m_value); - delete this; - return n; - } -} - -MemTrieNode* TrieLeafNode::remove(bytesConstRef _key) -{ - if (contains(_key)) - { - delete this; - return nullptr; - } - return this; -} - -MemTrie::~MemTrie() -{ - delete m_root; -} - -h256 MemTrie::hash256() const -{ - return m_root ? m_root->hash256() : sha3(dev::rlp(bytesConstRef())); -} - -bytes MemTrie::rlp() const -{ - return m_root ? m_root->rlp() : dev::rlp(bytesConstRef()); -} - -void MemTrie::debugPrint() -{ -#if ENABLE_DEBUG_PRINT - if (m_root) - m_root->debugPrint(); -#endif -} - -std::string const& MemTrie::at(std::string const& _key) const -{ - if (!m_root) - return c_nullString; - auto h = asNibbles(_key); - return m_root->at(bytesConstRef(&h)); -} - -void MemTrie::insert(std::string const& _key, std::string const& _value) -{ - if (_value.empty()) - remove(_key); - auto h = asNibbles(_key); - m_root = m_root ? m_root->insert(&h, _value) : new TrieLeafNode(bytesConstRef(&h), _value); -} - -void MemTrie::remove(std::string const& _key) -{ - if (m_root) - { - auto h = asNibbles(_key); - m_root = m_root->remove(&h); - } -} - -} - |