From 69fe21d6e2262d6fb2b14278b7a20364468cbdcf Mon Sep 17 00:00:00 2001 From: Vadim Dashevskiy Date: Fri, 12 Oct 2012 09:56:01 +0000 Subject: Dbx_tree: folders restructurization git-svn-id: http://svn.miranda-ng.org/main/trunk@1883 1316c22d-e87f-b044-9b9b-93d7a3e3ba9c --- plugins/Dbx_tree/BTree.h | 1358 ---------------------------------------------- 1 file changed, 1358 deletions(-) delete mode 100644 plugins/Dbx_tree/BTree.h (limited to 'plugins/Dbx_tree/BTree.h') diff --git a/plugins/Dbx_tree/BTree.h b/plugins/Dbx_tree/BTree.h deleted file mode 100644 index 20c2abfd71..0000000000 --- a/plugins/Dbx_tree/BTree.h +++ /dev/null @@ -1,1358 +0,0 @@ -/* - -dbx_tree: tree database driver for Miranda IM - -Copyright 2007-2010 Michael "Protogenes" Kunz, - -This program 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 2 -of the License, or (at your option) any later version. - -This program 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 this program; if not, write to the Free Software -Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. - -*/ - -#pragma once - -#include -#include "lockfree_hashmultimap.h" -#include "sigslot.h" -#ifdef _MSC_VER -#include "stdint.h" -#else -#include -#endif - -#include "Logger.h" - -#ifndef _MSC_VER -#ifdef offsetof -#undef offsetof -#endif -#define offsetof(TYPE, MEMBER) \ - ( (reinterpret_cast \ - (&reinterpret_cast \ - (static_cast (0)->MEMBER)))) -#endif - -template -class CBTree -{ -public: - typedef uint32_t TNodeRef; /// 32bit indices (not storing pointers) - typedef sigslot::signal2< void *, TNodeRef > TOnRootChanged; - - #pragma pack(push, 1) // push current alignment to stack, set alignment to 1 byte boundary - - typedef struct TNode { - uint16_t Info; /// Node information (IsLeaf and stored KeyCount) - uint16_t Signature; /// signature - TNodeRef Parent; /// Handle to the parent node - TKey Key[SizeParam * 2 - 1]; /// array with Keys - TNodeRef Child[SizeParam * 2]; /// array with child node handles - } TNode; - - #pragma pack(pop) - - class iterator - { - public: - iterator(); - iterator(CBTree* Tree, TNodeRef Node, uint16_t Index); - iterator(const iterator& Other); - ~iterator(); - - CBTree * Tree(); - - /** - \brief Keeps track of changes in the tree and refresh the iterator - **/ - void setManaged(); - bool wasDeleted(); - - operator bool() const; - bool operator !() const; - - const TKey & operator *(); - const TKey * operator->(); - - - bool operator == (iterator & Other); - bool operator < (iterator & Other); - bool operator > (iterator & Other); - - iterator& operator =(const iterator& Other); - - iterator& operator ++(); //pre ++i - iterator& operator --(); //pre --i - iterator operator ++(int); //post i++ - iterator operator --(int); //post i-- - - - protected: - friend class CBTree; - - TNodeRef m_Node; - uint16_t m_Index; - CBTree* m_Tree; - - bool m_Managed; - bool m_LoadedKey; - TKey m_ManagedKey; - bool m_ManagedDeleted; - - void Backup(); - void Dec(); - void Inc(); - void RemoveManaged(TNodeRef FromNode); - void InsertManaged(); - }; - - - CBTree(TNodeRef RootNode = 0); - virtual ~CBTree(); - - iterator Insert(const TKey & Key); - iterator Find(const TKey & Key); - iterator LowerBound(const TKey & Key); - iterator UpperBound(const TKey & Key); - bool Delete(const TKey & Key); - - typedef sigslot::signal3 TDeleteCallback; - void DeleteTree(TDeleteCallback * CallBack, uint32_t Param); - - TNodeRef getRoot(); - void setRoot(TNodeRef NewRoot); - - TOnRootChanged & sigRootChanged() {return m_sigRootChanged;}; - - -protected: - static const uint16_t cIsLeafMask = 0x8000; - static const uint16_t cKeyCountMask = 0x7FFF; - static const uint16_t cFullNode = SizeParam * 2 - 1; - static const uint16_t cEmptyNode = SizeParam - 1; - - typedef lockfree::hash_multimap TManagedMap; - - TNodeRef m_Root; - TOnRootChanged m_sigRootChanged; - TManagedMap m_ManagedIterators; - - bool m_DestroyTree; - - uint32_t m_AllocCount; - uint32_t m_Count; - uint32_t m_FreeIndex; - TNode * m_Alloc; - - virtual void PrepareInsertOperation(); - virtual TNode * CreateNewNode(TNodeRef & NodeRef); - virtual void DeleteNode(TNodeRef Node); - virtual TNode * Read(TNodeRef Node); - virtual void Write(TNodeRef Node); - - void DestroyTree(); - - -private: - friend class iterator; - - bool InNodeFind(const TNode * Node, const TKey & Key, uint16_t & GreaterEqual); - void SplitNode(TNodeRef Node, TNode * NodeData, TNodeRef & Left, TNodeRef & Right, TKey & UpKey, TNodeRef ParentNode, uint16_t ParentIndex); - TNodeRef MergeNodes(TNodeRef Left, TNode * LeftData, TNodeRef Right, TNode * RightData, const TKey & DownKey, TNodeRef ParentNode, uint16_t ParentIndex); - void KeyInsert(TNodeRef Node, TNode * NodeData, uint16_t Where); - void KeyDelete(TNodeRef Node, TNode * NodeData, uint16_t Where); - void KeyMove(TNodeRef Source, uint16_t SourceIndex, const TNode * SourceData, TNodeRef Dest, uint16_t DestIndex, TNode * DestData); -}; - - - - - - -template -CBTree::CBTree(TNodeRef RootNode = NULL) -: m_sigRootChanged(), - m_ManagedIterators() -{ - m_Root = RootNode; - m_DestroyTree = true; - - m_AllocCount = 0; - m_Count = 0; - m_FreeIndex = 0; - m_Alloc = NULL; -} - -template -CBTree::~CBTree() -{ - typename TManagedMap::iterator i = m_ManagedIterators.begin(); - while (i != m_ManagedIterators.end()) - { - i->second->m_Tree = NULL; - i++; - } - - if (m_DestroyTree) - DestroyTree(); -} - -template -inline bool CBTree::InNodeFind(const TNode * Node, const TKey & Key, uint16_t & GreaterEqual) -{ - uint16_t l = 0; - uint16_t r = (Node->Info & cKeyCountMask); - bool res = false; - GreaterEqual = 0; - while ((l < r) && !res) - { - GreaterEqual = (l + r) >> 1; - if (Node->Key[GreaterEqual] < Key) - { - GreaterEqual++; - l = GreaterEqual; - } else if (Node->Key[GreaterEqual] == Key) - { - //r = -1; - res = true; - } else { - r = GreaterEqual; - } - } - - return res; -} - - -template -inline void CBTree::SplitNode(TNodeRef Node, TNode * NodeData, TNodeRef & Left, TNodeRef & Right, TKey & UpKey, TNodeRef ParentNode, uint16_t ParentIndex) -{ - const uint16_t upindex = SizeParam - 1; - TNode *ldata, *rdata; - Left = Node; - ldata = NodeData; - rdata = CreateNewNode(Right); - - typename TManagedMap::iterator it = m_ManagedIterators.find(Node); - while ((it != m_ManagedIterators.end()) && (it->first == Node)) - { - if (it->second->m_Index == upindex) - { - it->second->m_Index = ParentIndex; - it->second->m_Node = ParentNode; - m_ManagedIterators.insert(std::make_pair(ParentNode, it->second)); - it = m_ManagedIterators.erase(it); - } else if (it->second->m_Index > upindex) - { - it->second->m_Index = it->second->m_Index - upindex - 1; - it->second->m_Node = Right; - m_ManagedIterators.insert(std::make_pair(Right, it->second)); - it = m_ManagedIterators.erase(it); - } else { - ++it; - } - } - - UpKey = NodeData->Key[upindex]; - - memcpy(&(rdata->Key[0]), &(NodeData->Key[upindex+1]), sizeof(TKey) * (cFullNode - upindex)); - if ((NodeData->Info & cIsLeafMask) == 0) - { - memcpy(&(rdata->Child[0]), &(NodeData->Child[upindex+1]), sizeof(TNodeRef) * (cFullNode - upindex + 1)); - - for (int i = 0; i <= upindex; i++) - { - TNode * tmp = Read(rdata->Child[i]); - tmp->Parent = Right; - Write(rdata->Child[i]); - } - } - - rdata->Info = (NodeData->Info & cIsLeafMask) | upindex; - NodeData->Info = rdata->Info; - rdata->Parent = NodeData->Parent; - - Write(Left); - Write(Right); -} - -template -inline typename CBTree::TNodeRef CBTree::MergeNodes(TNodeRef Left, TNode * LeftData, TNodeRef Right, TNode * RightData, const TKey & DownKey, TNodeRef ParentNode, uint16_t ParentIndex) -{ - uint16_t downindex = LeftData->Info & cKeyCountMask; - LeftData->Key[downindex] = DownKey; - - typename TManagedMap::iterator it = m_ManagedIterators.find(Right); - while ((it != m_ManagedIterators.end()) && (it->first == Right)) - { - it->second->m_Index = it->second->m_Index + downindex + 1; - it->second->m_Node = Left; - m_ManagedIterators.insert(std::make_pair(Left, it->second)); - it = m_ManagedIterators.erase(it); - } - - it = m_ManagedIterators.find(ParentNode); - while ((it != m_ManagedIterators.end()) && (it->first == ParentNode)) - { - if (it->second->m_Index == ParentIndex) - { - it->second->m_Index = downindex; - it->second->m_Node = Left; - m_ManagedIterators.insert(std::make_pair(Left, it->second)); - it = m_ManagedIterators.erase(it); - } else { - ++it; - } - } - - memcpy(&(LeftData->Key[downindex+1]), &(RightData->Key[0]), sizeof(TKey) * (RightData->Info & cKeyCountMask)); - if ((LeftData->Info & cIsLeafMask) == 0) - { - memcpy(&(LeftData->Child[downindex+1]), &(RightData->Child[0]), sizeof(TNodeRef) * ((RightData->Info & cKeyCountMask) + 1)); - - for (int i = 0; i <= (RightData->Info & cKeyCountMask); i++) - { - TNode * tmp = Read(RightData->Child[i]); - tmp->Parent = Left; - Write(RightData->Child[i]); - } - } - - LeftData->Info = ((LeftData->Info & cIsLeafMask) | (downindex + 1 + (RightData->Info & cKeyCountMask))); - - Write(Left); - DeleteNode(Right); - - return Left; -} - - -template -inline void CBTree::KeyInsert(TNodeRef Node, TNode * NodeData, uint16_t Where) -{ - memcpy(&(NodeData->Key[Where+1]), &(NodeData->Key[Where]), sizeof(TKey) * ((NodeData->Info & cKeyCountMask) - Where)); - - if ((NodeData->Info & cIsLeafMask) == 0) - memcpy(&(NodeData->Child[Where+1]), &(NodeData->Child[Where]), sizeof(TNodeRef) * ((NodeData->Info & cKeyCountMask) - Where + 1)); - - NodeData->Info++; - - typename TManagedMap::iterator it = m_ManagedIterators.find(Node); - while ((it != m_ManagedIterators.end()) && (it->first == Node)) - { - if (it->second->m_Index >= Where) - it->second->m_Index++; - - ++it; - } -} - -template -inline void CBTree::KeyDelete(TNodeRef Node, TNode * NodeData, uint16_t Where) -{ - NodeData->Info--; - - typename TManagedMap::iterator it = m_ManagedIterators.find(Node); - while ((it != m_ManagedIterators.end()) && (it->first == Node)) - { - if (it->second->m_Index == Where) - { - it->second->Backup(); - } else if (it->second->m_Index > Where) - { - it->second->m_Index--; - } - - ++it; - } - - memcpy(&(NodeData->Key[Where]), &(NodeData->Key[Where+1]), sizeof(TKey) * ((NodeData->Info & cKeyCountMask) - Where)); - - if ((NodeData->Info & cIsLeafMask) == 0) - memcpy(&(NodeData->Child[Where]), &(NodeData->Child[Where+1]), sizeof(TNodeRef) * ((NodeData->Info & cKeyCountMask) - Where + 1)); -} - - -template -inline void CBTree::KeyMove(TNodeRef Source, uint16_t SourceIndex, const TNode * SourceData, TNodeRef Dest, uint16_t DestIndex, TNode * DestData) -{ - DestData->Key[DestIndex] = SourceData->Key[SourceIndex]; - - typename TManagedMap::iterator it = m_ManagedIterators.find(Source); - while ((it != m_ManagedIterators.end()) && (it->first == Source)) - { - if (it->second->m_Index == SourceIndex) - { - it->second->m_Index = DestIndex; - it->second->m_Node = Dest; - m_ManagedIterators.insert(std::make_pair(Dest, it->second)); - it = m_ManagedIterators.erase(it); - } else { - ++it; - } - } -} - -template -typename CBTree::iterator -CBTree::Insert(const TKey & Key) -{ - TNode *node, *node2; - TNodeRef actnode; - TNodeRef nextnode; - bool exists; - uint16_t ge; - - PrepareInsertOperation(); - - if (!m_Root) - { - node = CreateNewNode(m_Root); - node->Info = cIsLeafMask; - Write(m_Root); - m_sigRootChanged.emit(this, m_Root); - } - - actnode = m_Root; - node = Read(actnode); - if ((node->Info & cKeyCountMask) == cFullNode) // root split - { - // be a little tricky and let the main code handle the actual splitting. - // just assign a new root with keycount to zero and one child = old root - // the InNode test will fail with GreaterEqual = 0 - node2 = CreateNewNode(nextnode); - node2->Info = 0; - node2->Child[0] = actnode; - Write(nextnode); - - node->Parent = nextnode; - Write(actnode); - - node = node2; - actnode = nextnode; - - m_Root = nextnode; - m_sigRootChanged.emit(this, m_Root); - } - - while (actnode) - { - exists = InNodeFind(node, Key, ge); - if (exists) // already exists - { - return iterator(this, actnode, ge); - } else { - if (node->Info & cIsLeafMask) // direct insert to leaf node - { - KeyInsert(actnode, node, ge); - - node->Key[ge] = Key; - - Write(actnode); - - return iterator(this, actnode, ge); - - } else { // middle node - nextnode = node->Child[ge]; - node2 = Read(nextnode); - - if ((node2->Info & cKeyCountMask) == cFullNode) // split the childnode - { - KeyInsert(actnode, node, ge); - SplitNode(nextnode, node2, node->Child[ge], node->Child[ge+1], node->Key[ge], actnode, ge); - - Write(actnode); - if (node->Key[ge] == Key) - { - return iterator(this, actnode, ge); - } else { - if (node->Key[ge] < Key) - { - nextnode = node->Child[ge+1]; - } else { - nextnode = node->Child[ge]; - } - } - - } - actnode = nextnode; - node = Read(actnode); - - } // if (node.Info & cIsLeafMask) - } // if (exists) - } // while (actnode) - - // something went wrong - return iterator(this, 0, 0xFFFF); -} - - -template -typename CBTree::iterator -CBTree::Find(const TKey & Key) -{ - TNode * node; - TNodeRef actnode = m_Root; - uint16_t ge; - - if (!m_Root) return iterator(this, 0, 0xFFFF); - - node = Read(actnode); - - while (actnode) - { - if (InNodeFind(node, Key, ge)) - { - return iterator(this, actnode, ge); - } - - if (!(node->Info & cIsLeafMask)) - { - actnode = node->Child[ge]; - node = Read(actnode); - } else { - actnode = 0; - } - } - - return iterator(this, 0, 0xFFFF); -} - -template -typename CBTree::iterator -CBTree::LowerBound(const TKey & Key) -{ - TNode * node; - TNodeRef actnode = m_Root; - uint16_t ge; - - if (!m_Root) return iterator(this, 0, 0xFFFF); - - node = Read(actnode); - - while (actnode) - { - if (InNodeFind(node, Key, ge)) - { - return iterator(this, actnode, ge); - } - - if (node->Info & cIsLeafMask) - { - if (ge >= (node->Info & cKeyCountMask)) - { - iterator i(this, actnode, ge - 1); - ++i; - return i; - } else { - return iterator(this, actnode, ge); - } - } else { - actnode = node->Child[ge]; - node = Read(actnode); - } - } - - return iterator(this, 0, 0xFFFF); -} - -template -typename CBTree::iterator -CBTree::UpperBound(const TKey & Key) -{ - TNode * node; - TNodeRef actnode = m_Root; - uint16_t ge; - if (!m_Root) return iterator(this, 0, 0xFFFF); - - node = Read(actnode); - - while (actnode) - { - if (InNodeFind(node, Key, ge)) - { - return iterator(this, actnode, ge); - } - - if (node->Info & cIsLeafMask) - { - if (ge == 0) - { - iterator i(this, actnode, 0); - --i; - return i; - } else { - return iterator(this, actnode, ge - 1); - } - } else { - actnode = node->Child[ge]; - node = Read(actnode); - } - } - - return iterator(this, 0, 0xFFFF); -} - -template -bool CBTree::Delete(const TKey& Key) -{ - if (!m_Root) return false; - - TNode *node, *node2, *lnode, *rnode; - - TNodeRef actnode = m_Root; - TNodeRef nextnode, l, r; - bool exists, skipread; - uint16_t ge; - - bool foundininnernode = false; - bool wantleftmost = false; - TNodeRef innernode = 0; - TNode * innernodedata = NULL; - uint16_t innerindex = 0xFFFF; - - node = Read(actnode); - - while (actnode) - { - skipread = false; - - if (foundininnernode) - { - exists = false; - if (wantleftmost) - ge = 0; - else - ge = node->Info & cKeyCountMask; - - } else { - exists = InNodeFind(node, Key, ge); - } - - if (exists) - { - if (node->Info & cIsLeafMask) // delete in leaf - { - KeyDelete(actnode, node, ge); - Write(actnode); - - return true; - - } else { // delete in inner node - l = node->Child[ge]; - r = node->Child[ge+1]; - lnode = Read(l); - rnode = Read(r); - - - if (((rnode->Info & cKeyCountMask) == cEmptyNode) && ((lnode->Info & cKeyCountMask) == cEmptyNode)) - { // merge childnodes and keep going - nextnode = MergeNodes(l, lnode, r, rnode, node->Key[ge], actnode, ge); - - KeyDelete(actnode, node, ge); - node->Child[ge] = nextnode; - - if ((actnode == m_Root) && ((node->Info & cKeyCountMask) == 0)) - { // root node is empty. delete it - DeleteNode(actnode); - m_Root = nextnode; - m_sigRootChanged.emit(this, m_Root); - } else { - Write(actnode); - } - - } else { // need a key-data-pair from a leaf to replace deleted pair -> save position - foundininnernode = true; - innernode = actnode; - innerindex = ge; - innernodedata = node; - - if ((lnode->Info & cKeyCountMask) == cEmptyNode) - { - wantleftmost = true; - nextnode = r; - } else { - wantleftmost = false; - nextnode = l; - } - } - } - - } else if (node->Info & cIsLeafMask) { // we are at the bottom. finish it - if (foundininnernode) - { - if (wantleftmost) - { - KeyMove(actnode, 0, node, innernode, innerindex, innernodedata); - Write(innernode); - - KeyDelete(actnode, node, 0); - Write(actnode); - - } else { - KeyMove(actnode, (node->Info & cKeyCountMask) - 1, node, innernode, innerindex, innernodedata); - Write(innernode); - - //KeyDelete(actnode, node, node.Info & cKeyCountMask); - node->Info--; - Write(actnode); - } - } - return foundininnernode; - - } else { // inner node. go on and check if moving or merging is neccessary - nextnode = node->Child[ge]; - node2 = Read(nextnode); - - if ((node2->Info & cKeyCountMask) == cEmptyNode) // move or merge - { - // set l and r for easier access - if (ge > 0) - { - l = node->Child[ge - 1]; - lnode = Read(l); - } else - l = 0; - - if (ge < (node->Info & cKeyCountMask)) - { - r = node->Child[ge + 1]; - rnode = Read(r); - } else - r = 0; - - if ((r != 0) && ((rnode->Info & cKeyCountMask) > cEmptyNode)) // move a Key-Data-pair from the right - { - // move key-data-pair down from current to the next node - KeyMove(actnode, ge, node, nextnode, node2->Info & cKeyCountMask, node2); - - // move the child from right to next node - node2->Child[(node2->Info & cKeyCountMask) + 1] = rnode->Child[0]; - - // move key-data-pair up from right to current node - KeyMove(r, 0, rnode, actnode, ge, node); - Write(actnode); - - // decrement right node key count and remove the first key-data-pair - KeyDelete(r, rnode, 0); - - // increment KeyCount of the next node - node2->Info++; - - if ((node2->Info & cIsLeafMask) == 0) // update the parent property of moved child - { - TNode * tmp = Read(node2->Child[node2->Info & cKeyCountMask]); - tmp->Parent = nextnode; - Write(node2->Child[node2->Info & cKeyCountMask]); - } - - - Write(r); - Write(nextnode); - node = node2; - skipread = true; - - } else if ((l != 0) && ((lnode->Info & cKeyCountMask) > cEmptyNode)) // move a Key-Data-pair from the left - { - // increment next node key count and make new first key-data-pair - KeyInsert(nextnode, node2, 0); - - // move key-data-pair down from current to the next node - KeyMove(actnode, ge - 1, node, nextnode, 0, node2); - - // move the child from left to next node - node2->Child[0] = lnode->Child[lnode->Info & cKeyCountMask]; - - // move key-data-pair up from left to current node - KeyMove(l, (lnode->Info & cKeyCountMask) - 1, lnode, actnode, ge - 1, node); - Write(actnode); - - // decrement left node key count - lnode->Info--; - Write(l); - - if ((node2->Info & cIsLeafMask) == 0) // update the parent property of moved child - { - TNode * tmp = Read(node2->Child[0]); - tmp->Parent = nextnode; - Write(node2->Child[0]); - } - - Write(nextnode); - node = node2; - skipread = true; - - } else { - if (l != 0) // merge with the left node - { - nextnode = MergeNodes(l, lnode, nextnode, node2, node->Key[ge - 1], actnode, ge - 1); - KeyDelete(actnode, node, ge - 1); - node->Child[ge - 1] = nextnode; - - } else { // merge with the right node - nextnode = MergeNodes(nextnode, node2, r, rnode, node->Key[ge], actnode, ge); - KeyDelete(actnode, node, ge); - node->Child[ge] = nextnode; - } - - if ((actnode == m_Root) && ((node->Info & cKeyCountMask) == 0)) - { - DeleteNode(actnode); - m_Root = nextnode; - m_sigRootChanged(this, nextnode); - } else { - Write(actnode); - } - } - } - } // if (exists) else if (node.Info & cIsLeafMask) - - actnode = nextnode; - if (!skipread) - node = Read(actnode); - - } // while(actnode) - - return false; -} - -template -typename CBTree::TNodeRef CBTree::getRoot() -{ - return m_Root; -} - -template -void CBTree::setRoot(TNodeRef NewRoot) -{ - m_Root = NewRoot; - return; -} - -template -void CBTree::PrepareInsertOperation() -{ - if (m_Count + 64 > m_AllocCount) - { - m_AllocCount += 64; - m_Alloc = (TNode *)realloc(m_Alloc, sizeof(TNode) * m_AllocCount); - - for (TNodeRef i = m_AllocCount - 64; i < m_AllocCount; ++i) - m_Alloc[i].Parent = i + 1; - - m_Alloc[m_AllocCount - 1].Parent = 0; - - if (m_FreeIndex) - { - TNodeRef i = m_FreeIndex; - while (m_Alloc[i].Parent) - i = m_Alloc[i].Parent; - - m_Alloc[i].Parent = m_AllocCount - 64; - - } else { - m_FreeIndex = m_AllocCount - 63; - } - - } -} - -template -typename CBTree::TNode * CBTree::CreateNewNode(TNodeRef & NodeRef) -{ - NodeRef = m_FreeIndex; - m_FreeIndex = m_Alloc[m_FreeIndex].Parent; - m_Count++; - memset(m_Alloc + NodeRef, 0, sizeof(TNode)); - return m_Alloc + NodeRef; -} - -template -void CBTree::DeleteNode(TNodeRef Node) -{ - CHECK((Node > 0) && (Node < m_AllocCount), logERROR, _T("Invalid Node")); - m_Alloc[Node].Parent = m_FreeIndex; - m_FreeIndex = Node; - m_Count--; -} - -template -typename CBTree::TNode * CBTree::Read(TNodeRef Node) -{ - CHECK((Node > 0) && (Node < m_AllocCount), logERROR, _T("Invalid Node")); - return m_Alloc + Node; -} - -template -void CBTree::Write(TNodeRef Node) -{ - return; -} - -template -void CBTree::DestroyTree() -{ - std::stack s; - TNodeRef node; - TNode* nodedata; - uint16_t i; - - if (m_Root) - s.push(m_Root); - while (!s.empty()) - { - node = s.top(); - nodedata = Read(node); - s.pop(); - - if ((nodedata->Info & cIsLeafMask) == 0) - { - for (i = 0; i <= (nodedata->Info & cKeyCountMask); i++) - s.push(nodedata->Child[i]); - } - - DeleteNode(node); - } - - if (m_Alloc) - free(m_Alloc); - m_Alloc = NULL; - m_AllocCount = 0; - m_Count = 0; - m_FreeIndex = 0; -} - - -template -void CBTree::DeleteTree(TDeleteCallback * CallBack, uint32_t Param) -{ - std::stack s; - TNodeRef actnode; - TNode * node; - uint16_t i; - - typename TManagedMap::iterator it = m_ManagedIterators.begin(); - while (it != m_ManagedIterators.end()) - { - it->second->m_Node = 0; - it->second->m_Index = 0xffff; - ++it; - } - - if (m_Root) - s.push(m_Root); - - m_Root = 0; - m_sigRootChanged.emit(this, m_Root); - - while (!s.empty()) - { - actnode = s.top(); - s.pop(); - - node = Read(actnode); - - if ((node->Info & cIsLeafMask) == 0) - { - for (i = 0; i <= (node->Info & cKeyCountMask); i++) - s.push(node->Child[i]); - - } - if (CallBack) - { - for (i = 0; i < (node->Info & cKeyCountMask); i++) - CallBack->emit(this, node->Key[i], Param); - } - - DeleteNode(actnode); - } -} - - - - - - - -template -CBTree::iterator::iterator() -{ - m_Tree = NULL; - m_Node = 0; - m_Index = 0xFFFF; - m_Managed = false; - m_ManagedDeleted = false; - m_LoadedKey = false; -} -template -CBTree::iterator::iterator(CBTree* Tree, TNodeRef Node, uint16_t Index) -{ - m_Tree = Tree; - m_Node = Node; - m_Index = Index; - m_Managed = false; - m_ManagedDeleted = false; - m_LoadedKey = false; -} -template -CBTree::iterator::iterator(const iterator& Other) -{ - m_Tree = Other.m_Tree; - m_Node = Other.m_Node; - m_Index = Other.m_Index; - m_ManagedDeleted = Other.m_ManagedDeleted; - m_Managed = Other.m_Managed; - m_LoadedKey = Other.m_LoadedKey; - m_ManagedKey = Other.m_ManagedKey; - - if (m_Managed) - InsertManaged(); -} - -template -CBTree::iterator::~iterator() -{ - RemoveManaged(m_Node); -} - - -template -void CBTree::iterator::setManaged() -{ - if (!m_Managed) - InsertManaged(); - - m_Managed = true; -} - -template -inline void CBTree::iterator::RemoveManaged(TNodeRef FromNode) -{ - if (m_Managed && m_Tree) - { - typename TManagedMap::iterator i = m_Tree->m_ManagedIterators.find(FromNode); - - while ((i != m_Tree->m_ManagedIterators.end()) && (i->second != this) && (i->first == FromNode)) - ++i; - - if ((i != m_Tree->m_ManagedIterators.end()) && (i->second == this)) - m_Tree->m_ManagedIterators.erase(i); - } -} -template -inline void CBTree::iterator::InsertManaged() -{ - if (m_Tree) - m_Tree->m_ManagedIterators.insert(std::make_pair(m_Node, this)); -} - -template -bool CBTree::iterator::wasDeleted() -{ - return m_ManagedDeleted; -} - -template -void CBTree::iterator::Backup() -{ - if ((!m_ManagedDeleted) && (*this)) - { - TNode * tmp; - if (!m_LoadedKey) - { - tmp = m_Tree->Read(m_Node); - m_ManagedKey = tmp->Key[m_Index]; - } - m_LoadedKey = true; - } - - m_ManagedDeleted = true; -} - -template -CBTree * CBTree::iterator::Tree() -{ - return m_Tree; -} - -template -const TKey& CBTree::iterator::operator *() -{ - if (!m_LoadedKey) - { - TNode * node; - node = m_Tree->Read(m_Node); - m_ManagedKey = node->Key[m_Index]; - m_LoadedKey = true; - } - return m_ManagedKey; -} - -template -const TKey* CBTree::iterator::operator ->() -{ - if (!m_LoadedKey) - { - TNode * node; - node = m_Tree->Read(m_Node); - m_ManagedKey = node->Key[m_Index]; - m_LoadedKey = true; - } - return &m_ManagedKey; -} - -template -inline CBTree::iterator::operator bool() const -{ - if (m_Tree && m_Node) - { - TNode * node; - node = m_Tree->Read(m_Node); - return (m_Index < (node->Info & cKeyCountMask)); - } else - return false; -} - -template -inline bool CBTree::iterator::operator !() const -{ - if (m_Tree && m_Node) - { - TNode * node; - node = m_Tree->Read(m_Node); - return (m_Index > (node->Info & cKeyCountMask)); - } else - return true; -} - -template -inline bool CBTree::iterator::operator ==(iterator & Other) -{ - //return (m_Tree == Other.m_Tree) && (m_Node == Other.m_Node) && (m_Index == Other.m_Index) && (!m_ManagedDeleted) && (!Other.m_ManagedDeleted); - return Key() == Other.Key(); -} - -template -inline bool CBTree::iterator::operator < (iterator & Other) -{ - return Key() < Other.Key(); -} -template -inline bool CBTree::iterator::operator > (iterator & Other) -{ - return Key() > Other.Key(); -} - - -template -typename CBTree::iterator& -CBTree::iterator::operator =(const iterator& Other) -{ - RemoveManaged(m_Node); - - m_Tree = Other.m_Tree; - m_Node = Other.m_Node; - m_Index = Other.m_Index; - m_ManagedDeleted = Other.m_ManagedDeleted; - m_Managed = Other.m_Managed; - m_LoadedKey = Other.m_LoadedKey; - m_ManagedKey = Other.m_ManagedKey; - - if (m_Managed) - InsertManaged(); - - return *this; -} - -template -typename CBTree::iterator& -CBTree::iterator::operator ++() //pre ++i -{ - TNodeRef oldnode = m_Node; - if (m_Managed && m_ManagedDeleted) - { - TKey oldkey = m_ManagedKey; - m_LoadedKey = false; - m_ManagedDeleted = false; - iterator other = m_Tree->LowerBound(m_ManagedKey); - m_Node = other.m_Node; - m_Index = other.m_Index; - while (((**this) == oldkey) && (*this)) - Inc(); - - } else - Inc(); - - if (m_Managed && (oldnode != m_Node)) - { - RemoveManaged(oldnode); - InsertManaged(); - } - return *this; -} - -template -typename CBTree::iterator& -CBTree::iterator::operator --() //pre --i -{ - TNodeRef oldnode = m_Node; - if (m_Managed && m_ManagedDeleted) - { - TKey oldkey = m_ManagedKey; - m_LoadedKey = false; - - m_ManagedDeleted = false; - iterator other = m_Tree->UpperBound(m_ManagedKey); - m_Node = other.m_Node; - m_Index = other.m_Index; - while (((**this) == oldkey) && (*this)) - Dec(); - } else - Dec(); - - if (m_Managed && (oldnode != m_Node)) - { - RemoveManaged(oldnode); - InsertManaged(); - } - return *this; -} - -template -typename CBTree::iterator -CBTree::iterator::operator ++(int) //post i++ -{ - iterator tmp(*this); - ++(*this); - return tmp; -} -template -typename CBTree::iterator -CBTree::iterator::operator --(int) //post i-- -{ - iterator tmp(*this); - --(*this); - return tmp; -} - -template -void CBTree::iterator::Inc() -{ - TNode * node; - TNodeRef nextnode; - node = m_Tree->Read(m_Node); - - m_LoadedKey = false; - - if ((node->Info & cIsLeafMask) && ((node->Info & cKeyCountMask) > m_Index + 1)) // leaf - { - m_Index++; - return; - } - - if ((node->Info & cIsLeafMask) == 0) // inner node. go down - { - m_Node = node->Child[m_Index + 1]; - node = m_Tree->Read(m_Node); - - m_Index = 0; - - while ((node->Info & cIsLeafMask) == 0) // go down to a leaf - { - m_Node = node->Child[0]; - node = m_Tree->Read(m_Node); - } - - return; - } - - while (m_Index >= (node->Info & cKeyCountMask) - 1) // go up - { - if (m_Node == m_Tree->m_Root) // the root is the top, we cannot go further - { - m_Index = 0xFFFF; - m_Node = 0; - return; - } - - nextnode = node->Parent; - node = m_Tree->Read(nextnode); - m_Index = 0; - - while ((m_Index <= (node->Info & cKeyCountMask)) && (node->Child[m_Index] != m_Node)) - m_Index++; - - m_Node = nextnode; - - if (m_Index < (node->Info & cKeyCountMask)) - return; - } - -} - -template -void CBTree::iterator::Dec() -{ - TNode * node; - TNodeRef nextnode; - node = m_Tree->Read(m_Node); - - m_LoadedKey = false; - - if ((node->Info & cIsLeafMask) && (m_Index > 0)) // leaf - { - m_Index--; - return; - } - - if ((node->Info & cIsLeafMask) == 0) // inner node. go down - { - m_Node = node->Child[m_Index]; - node = m_Tree->Read(m_Node); - m_Index = (node->Info & cKeyCountMask) - 1; - - while ((node->Info & cIsLeafMask) == 0) // go down to a leaf - { - m_Node = node->Child[node->Info & cKeyCountMask]; - node = m_Tree->Read(m_Node); - m_Index = (node->Info & cKeyCountMask) - 1; - } - - return; - } - - while (m_Index == 0) // go up - { - if (m_Node == m_Tree->m_Root) // the root is the top, we cannot go further - { - m_Index = 0xFFFF; - m_Node = 0; - return; - } - - nextnode = node->Parent; - node = m_Tree->Read(nextnode); - m_Index = 0; - - while ((m_Index <= (node->Info & cKeyCountMask)) && (node->Child[m_Index] != m_Node)) - m_Index++; - - m_Node = nextnode; - - if (m_Index > 0) - { - m_Index--; - return; - } - } -} -- cgit v1.2.3