diff options
Diffstat (limited to 'plugins/!Deprecated/Dbx_tree/src/BTree.h')
| -rw-r--r-- | plugins/!Deprecated/Dbx_tree/src/BTree.h | 1343 |
1 files changed, 0 insertions, 1343 deletions
diff --git a/plugins/!Deprecated/Dbx_tree/src/BTree.h b/plugins/!Deprecated/Dbx_tree/src/BTree.h deleted file mode 100644 index f1d44ccd27..0000000000 --- a/plugins/!Deprecated/Dbx_tree/src/BTree.h +++ /dev/null @@ -1,1343 +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 <stack>
-#include "lockfree_hashmultimap.h"
-#include "sigslot.h"
-#include <stdint.h>
-
-#include "Logger.h"
-
-template <typename TKey, uint16_t SizeParam = 4>
-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<void *, const TKey &, uint32_t> 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<TNodeRef, iterator*> 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 <typename TKey, uint16_t SizeParam>
-CBTree<TKey, SizeParam>::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 <typename TKey, uint16_t SizeParam>
-CBTree<TKey, SizeParam>::~CBTree()
-{
- typename TManagedMap::iterator i = m_ManagedIterators.begin();
- while (i != m_ManagedIterators.end())
- {
- i->second->m_Tree = NULL;
- ++i;
- }
-
- if (m_DestroyTree)
- DestroyTree();
-}
-
-template <typename TKey, uint16_t SizeParam>
-inline bool CBTree<TKey, SizeParam>::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 <typename TKey, uint16_t SizeParam>
-inline void CBTree<TKey, SizeParam>::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 <typename TKey, uint16_t SizeParam>
-inline typename CBTree<TKey, SizeParam>::TNodeRef CBTree<TKey, SizeParam>::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 <typename TKey, uint16_t SizeParam>
-inline void CBTree<TKey, SizeParam>::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 <typename TKey, uint16_t SizeParam>
-inline void CBTree<TKey, SizeParam>::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 <typename TKey, uint16_t SizeParam>
-inline void CBTree<TKey, SizeParam>::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 TKey, uint16_t SizeParam>
-typename CBTree<TKey, SizeParam>::iterator
-CBTree<TKey, SizeParam>::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 TKey, uint16_t SizeParam>
-typename CBTree<TKey, SizeParam>::iterator
-CBTree<TKey, SizeParam>::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 TKey, uint16_t SizeParam>
-typename CBTree<TKey, SizeParam>::iterator
-CBTree<TKey, SizeParam>::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 TKey, uint16_t SizeParam>
-typename CBTree<TKey, SizeParam>::iterator
-CBTree<TKey, SizeParam>::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 <typename TKey, uint16_t SizeParam>
-bool CBTree<TKey, SizeParam>::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 TKey, uint16_t SizeParam>
-typename CBTree<TKey, SizeParam>::TNodeRef CBTree<TKey, SizeParam>::getRoot()
-{
- return m_Root;
-}
-
-template <typename TKey, uint16_t SizeParam>
-void CBTree<TKey, SizeParam>::setRoot(TNodeRef NewRoot)
-{
- m_Root = NewRoot;
- return;
-}
-
-template <typename TKey, uint16_t SizeParam>
-void CBTree<TKey, SizeParam>::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 TKey, uint16_t SizeParam>
-typename CBTree<TKey, SizeParam>::TNode * CBTree<TKey, SizeParam>::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 <typename TKey, uint16_t SizeParam>
-void CBTree<TKey, SizeParam>::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 TKey, uint16_t SizeParam>
-typename CBTree<TKey, SizeParam>::TNode * CBTree<TKey, SizeParam>::Read(TNodeRef Node)
-{
- CHECK((Node > 0) && (Node < m_AllocCount), logERROR, _T("Invalid Node"));
- return m_Alloc + Node;
-}
-
-template <typename TKey, uint16_t SizeParam>
-void CBTree<TKey, SizeParam>::Write(TNodeRef Node)
-{
- return;
-}
-
-template <typename TKey, uint16_t SizeParam>
-void CBTree<TKey, SizeParam>::DestroyTree()
-{
- std::stack<TNodeRef> 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);
- }
-
- free(m_Alloc);
- m_Alloc = NULL;
- m_AllocCount = 0;
- m_Count = 0;
- m_FreeIndex = 0;
-}
-
-
-template <typename TKey, uint16_t SizeParam>
-void CBTree<TKey, SizeParam>::DeleteTree(TDeleteCallback * CallBack, uint32_t Param)
-{
- std::stack<TNodeRef> 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 <typename TKey, uint16_t SizeParam>
-CBTree<TKey, SizeParam>::iterator::iterator()
-{
- m_Tree = NULL;
- m_Node = 0;
- m_Index = 0xFFFF;
- m_Managed = false;
- m_ManagedDeleted = false;
- m_LoadedKey = false;
-}
-template <typename TKey, uint16_t SizeParam>
-CBTree<TKey, SizeParam>::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 <typename TKey, uint16_t SizeParam>
-CBTree<TKey, SizeParam>::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 <typename TKey, uint16_t SizeParam>
-CBTree<TKey, SizeParam>::iterator::~iterator()
-{
- RemoveManaged(m_Node);
-}
-
-
-template <typename TKey, uint16_t SizeParam>
-void CBTree<TKey, SizeParam>::iterator::setManaged()
-{
- if (!m_Managed)
- InsertManaged();
-
- m_Managed = true;
-}
-
-template <typename TKey, uint16_t SizeParam>
-inline void CBTree<TKey, SizeParam>::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 <typename TKey, uint16_t SizeParam>
-inline void CBTree<TKey, SizeParam>::iterator::InsertManaged()
-{
- if (m_Tree)
- m_Tree->m_ManagedIterators.insert(std::make_pair(m_Node, this));
-}
-
-template <typename TKey, uint16_t SizeParam>
-bool CBTree<TKey, SizeParam>::iterator::wasDeleted()
-{
- return m_ManagedDeleted;
-}
-
-template <typename TKey, uint16_t SizeParam>
-void CBTree<TKey, SizeParam>::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 <typename TKey, uint16_t SizeParam>
-CBTree<TKey, SizeParam> * CBTree<TKey, SizeParam>::iterator::Tree()
-{
- return m_Tree;
-}
-
-template <typename TKey, uint16_t SizeParam>
-const TKey& CBTree<TKey, SizeParam>::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 <typename TKey, uint16_t SizeParam>
-const TKey* CBTree<TKey, SizeParam>::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 <typename TKey, uint16_t SizeParam>
-inline CBTree<TKey, SizeParam>::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 <typename TKey, uint16_t SizeParam>
-inline bool CBTree<TKey, SizeParam>::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 <typename TKey, uint16_t SizeParam>
-inline bool CBTree<TKey, SizeParam>::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 <typename TKey, uint16_t SizeParam>
-inline bool CBTree<TKey, SizeParam>::iterator::operator < (iterator & Other)
-{
- return Key() < Other.Key();
-}
-template <typename TKey, uint16_t SizeParam>
-inline bool CBTree<TKey, SizeParam>::iterator::operator > (iterator & Other)
-{
- return Key() > Other.Key();
-}
-
-
-template <typename TKey, uint16_t SizeParam>
-typename CBTree<TKey, SizeParam>::iterator&
-CBTree<TKey, SizeParam>::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 TKey, uint16_t SizeParam>
-typename CBTree<TKey, SizeParam>::iterator&
-CBTree<TKey, SizeParam>::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 TKey, uint16_t SizeParam>
-typename CBTree<TKey, SizeParam>::iterator&
-CBTree<TKey, SizeParam>::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 TKey, uint16_t SizeParam>
-typename CBTree<TKey, SizeParam>::iterator
-CBTree<TKey, SizeParam>::iterator::operator ++(int) //post i++
-{
- iterator tmp(*this);
- ++(*this);
- return tmp;
-}
-template <typename TKey, uint16_t SizeParam>
-typename CBTree<TKey, SizeParam>::iterator
-CBTree<TKey, SizeParam>::iterator::operator --(int) //post i--
-{
- iterator tmp(*this);
- --(*this);
- return tmp;
-}
-
-template <typename TKey, uint16_t SizeParam>
-void CBTree<TKey, SizeParam>::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 <typename TKey, uint16_t SizeParam>
-void CBTree<TKey, SizeParam>::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;
- }
- }
-}
|