summaryrefslogtreecommitdiffstats
path: root/sot/source/sdstor/stgavl.cxx
diff options
context:
space:
mode:
Diffstat (limited to 'sot/source/sdstor/stgavl.cxx')
-rw-r--r--sot/source/sdstor/stgavl.cxx411
1 files changed, 411 insertions, 0 deletions
diff --git a/sot/source/sdstor/stgavl.cxx b/sot/source/sdstor/stgavl.cxx
new file mode 100644
index 000000000..98a86f3ed
--- /dev/null
+++ b/sot/source/sdstor/stgavl.cxx
@@ -0,0 +1,411 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed
+ * with this work for additional information regarding copyright
+ * ownership. The ASF licenses this file to you under the Apache
+ * License, Version 2.0 (the "License"); you may not use this file
+ * except in compliance with the License. You may obtain a copy of
+ * the License at http://www.apache.org/licenses/LICENSE-2.0 .
+ */
+
+#include <osl/diagnose.h>
+#include "stgavl.hxx"
+#include <assert.h>
+
+StgAvlNode::StgAvlNode()
+{
+ m_pLeft = m_pRight = nullptr;
+ m_nBalance = m_nId = 0;
+}
+
+StgAvlNode::~StgAvlNode()
+{
+ delete m_pLeft;
+ delete m_pRight;
+}
+
+StgAvlNode* StgAvlNode::Find( StgAvlNode const * pFind )
+{
+ if ( pFind )
+ {
+ StgAvlNode* p = this;
+ while( p )
+ {
+ sal_Int32 nRes = p->Compare( pFind );
+ if( !nRes )
+ return p;
+ else p = ( nRes < 0 ) ? p->m_pLeft : p->m_pRight;
+ }
+ }
+ return nullptr;
+}
+
+// find point to add node to AVL tree and returns
+// +/0/- for >/=/< previous
+
+sal_Int32 StgAvlNode::Locate
+ ( StgAvlNode const * pFind,
+ StgAvlNode** pPivot, StgAvlNode **pParent, StgAvlNode** pPrev )
+{
+ sal_Int32 nRes = 0;
+ StgAvlNode* pCur = this;
+
+ OSL_ENSURE( pPivot && pParent && pPrev, "The pointers may not be NULL!" );
+ *pParent = *pPrev = nullptr;
+ *pPivot = this;
+
+ // search tree for insertion point
+ if ( pFind )
+ {
+ while( pCur != nullptr )
+ {
+ // check for pPivot
+ if( pCur->m_nBalance != 0 )
+ {
+ *pPivot = pCur;
+ *pParent = *pPrev;
+ }
+ // save pPrev location and see what direction to go
+ *pPrev = pCur;
+ nRes = pCur->Compare( pFind );
+ if( nRes == 0 )
+ break;
+ else pCur = ( nRes < 0 ) ? pCur->m_pLeft : pCur->m_pRight;
+ }
+ }
+
+ return nRes;
+}
+
+// adjust balance factors in AVL tree from pivot down.
+// Returns delta balance.
+
+short StgAvlNode::Adjust( StgAvlNode** pHeavy, StgAvlNode const * pNew )
+{
+ StgAvlNode* pCur = this;
+ short nDelta;
+ // no traversing
+ OSL_ENSURE( pHeavy && pNew, "The pointers is not allowed to be NULL!" );
+ if( pCur == pNew || !pNew )
+ return m_nBalance;
+
+ sal_Int32 nRes = Compare( pNew );
+ if( nRes > 0 )
+ {
+ *pHeavy = pCur = m_pRight;
+ nDelta = -1;
+ }
+ else
+ {
+ *pHeavy = pCur = m_pLeft;
+ nDelta = 1;
+ }
+ m_nBalance = 0;
+ while( pCur != pNew )
+ {
+ nRes = pCur->Compare( pNew );
+ if( nRes > 0 )
+ {
+ // height of right increases by 1
+ pCur->m_nBalance = -1;
+ pCur = pCur->m_pRight;
+ }
+ else
+ {
+ // height of left increases by 1
+ pCur->m_nBalance = 1;
+ pCur = pCur->m_pLeft;
+ }
+ }
+ m_nBalance = m_nBalance + nDelta;
+ return nDelta;
+}
+
+// perform LL rotation and return new root
+
+StgAvlNode* StgAvlNode::RotLL()
+{
+ assert(m_pLeft && "The pointer is not allowed to be NULL!");
+ StgAvlNode *pHeavy = m_pLeft;
+ m_pLeft = pHeavy->m_pRight;
+ pHeavy->m_pRight = this;
+ pHeavy->m_nBalance = m_nBalance = 0;
+ return pHeavy;
+}
+
+// perform LR rotation and return new root
+
+StgAvlNode* StgAvlNode::RotLR()
+{
+ assert(m_pLeft && m_pLeft->m_pRight && "The pointer is not allowed to be NULL!");
+ StgAvlNode* pHeavy = m_pLeft;
+ StgAvlNode* pNewRoot = pHeavy->m_pRight;
+
+ pHeavy->m_pRight = pNewRoot->m_pLeft;
+ m_pLeft = pNewRoot->m_pRight;
+ pNewRoot->m_pLeft = pHeavy;
+ pNewRoot->m_pRight = this;
+
+ switch( pNewRoot->m_nBalance )
+ {
+ case 1: // LR( b )
+ m_nBalance = -1;
+ pHeavy->m_nBalance = 0;
+ break;
+ case -1: // LR( c )
+ pHeavy->m_nBalance = 1;
+ m_nBalance = 0;
+ break;
+ case 0: // LR( a )
+ m_nBalance = 0;
+ pHeavy->m_nBalance = 0;
+ break;
+ }
+ pNewRoot->m_nBalance = 0;
+ return pNewRoot;
+}
+
+// perform RR rotation and return new root
+StgAvlNode* StgAvlNode::RotRR()
+{
+ assert(m_pRight && "The pointer is not allowed to be NULL!" );
+ StgAvlNode* pHeavy = m_pRight;
+ m_pRight = pHeavy->m_pLeft;
+ pHeavy->m_pLeft = this;
+ m_nBalance = pHeavy->m_nBalance = 0;
+ return pHeavy;
+}
+
+// perform the RL rotation and return the new root
+StgAvlNode* StgAvlNode::RotRL()
+{
+ assert(m_pRight && m_pRight->m_pLeft && "The pointer is not allowed to be NULL!");
+ StgAvlNode* pHeavy = m_pRight;
+ StgAvlNode* pNewRoot = pHeavy->m_pLeft;
+ pHeavy->m_pLeft = pNewRoot->m_pRight;
+ m_pRight = pNewRoot->m_pLeft;
+ pNewRoot->m_pRight = pHeavy;
+ pNewRoot->m_pLeft = this;
+ switch( pNewRoot->m_nBalance )
+ {
+ case -1: // RL( b )
+ m_nBalance = 1;
+ pHeavy->m_nBalance = 0;
+ break;
+ case 1: // RL( c )
+ pHeavy->m_nBalance = -1;
+ m_nBalance = 0;
+ break;
+ case 0: // RL( a )
+ m_nBalance = 0;
+ pHeavy->m_nBalance = 0;
+ break;
+ }
+ pNewRoot->m_nBalance = 0;
+ return pNewRoot;
+}
+
+// Remove a tree element. Return the removed element or NULL.
+
+StgAvlNode* StgAvlNode::Rem( StgAvlNode** p, StgAvlNode* pDel, bool bPtrs )
+{
+ if( p && *p && pDel )
+ {
+ StgAvlNode* pCur = *p;
+ sal_Int32 nRes = bPtrs ? sal_Int32( pCur == pDel ) : pCur->Compare( pDel );
+ if( !nRes )
+ {
+ // Element found: remove
+ if( !pCur->m_pRight )
+ {
+ *p = pCur->m_pLeft; pCur->m_pLeft = nullptr;
+ }
+ else if( !pCur->m_pLeft )
+ {
+ *p = pCur->m_pRight; pCur->m_pRight = nullptr;
+ }
+ else
+ {
+ // The damn element has two leaves. Get the
+ // rightmost element of the left subtree (which
+ // is lexically before this element) and replace
+ // this element with the element found.
+ StgAvlNode* last = pCur;
+ StgAvlNode* l;
+ for( l = pCur->m_pLeft;
+ l->m_pRight; last = l, l = l->m_pRight ) {}
+ // remove the element from chain
+ if( l == last->m_pRight )
+ last->m_pRight = l->m_pLeft;
+ else
+ last->m_pLeft = l->m_pLeft;
+ // perform the replacement
+ l->m_pLeft = pCur->m_pLeft;
+ l->m_pRight = pCur->m_pRight;
+ *p = l;
+ // delete the element
+ pCur->m_pLeft = pCur->m_pRight = nullptr;
+ }
+ return pCur;
+ }
+ else
+ {
+ if( nRes < 0 )
+ return Rem( &pCur->m_pLeft, pDel, bPtrs );
+ else
+ return Rem( &pCur->m_pRight, pDel, bPtrs );
+ }
+ }
+ return nullptr;
+}
+
+// Enumerate the tree for later iteration
+
+void StgAvlNode::StgEnum( short& n )
+{
+ if( m_pLeft )
+ m_pLeft->StgEnum( n );
+ m_nId = n++;
+ if( m_pRight )
+ m_pRight->StgEnum( n );
+}
+
+// Add node to AVL tree.
+// Return false if the element already exists.
+
+bool StgAvlNode::Insert( StgAvlNode** pRoot, StgAvlNode* pIns )
+{
+ StgAvlNode* pPivot, *pHeavy, *pParent, *pPrev;
+ if ( !pRoot )
+ return false;
+
+ // special case - empty tree
+ if( *pRoot == nullptr )
+ {
+ *pRoot = pIns;
+ return true;
+ }
+ // find insertion point and return if already present
+ sal_Int32 nRes = (*pRoot)->Locate( pIns, &pPivot, &pParent, &pPrev );
+ if( !nRes )
+ return false;
+
+ assert(pPivot && pPrev && "The pointers may not be NULL!");
+
+ // add new node
+ if( nRes < 0 )
+ pPrev->m_pLeft = pIns;
+ else
+ pPrev->m_pRight = pIns;
+ // rebalance tree
+ short nDelta = pPivot->Adjust( &pHeavy, pIns );
+ if( pPivot->m_nBalance >= 2 || pPivot->m_nBalance <= -2 )
+ {
+ StgAvlNode* pNewRoot;
+ pHeavy = ( nDelta < 0 ) ? pPivot->m_pRight : pPivot->m_pLeft;
+ // left imbalance
+ if( nDelta > 0 )
+ if( pHeavy->m_nBalance == 1 )
+ pNewRoot = pPivot->RotLL();
+ else
+ pNewRoot = pPivot->RotLR();
+ // right imbalance
+ else if( pHeavy->m_nBalance == -1 )
+ pNewRoot = pPivot->RotRR();
+ else
+ pNewRoot = pPivot->RotRL();
+ // relink balanced subtree
+ if( pParent == nullptr )
+ *pRoot = pNewRoot;
+ else if( pPivot == pParent->m_pLeft )
+ pParent->m_pLeft = pNewRoot;
+ else if( pPivot == pParent->m_pRight )
+ pParent->m_pRight = pNewRoot;
+ }
+ return true;
+}
+
+// Remove node from tree. Returns true is found and removed.
+// Actually delete if bDel
+
+bool StgAvlNode::Remove( StgAvlNode** pRoot, StgAvlNode* pDel, bool bDel )
+{
+ if ( !pRoot )
+ return false;
+
+ // special case - empty tree
+ if( *pRoot == nullptr )
+ return false;
+ // delete the element
+ pDel = Rem( pRoot, pDel, false );
+ if( pDel )
+ {
+ if( bDel )
+ delete pDel;
+ // Rebalance the tree the hard way
+ // OS 22.09.95: On MD's request commented out due to crash
+/* StgAvlNode* pNew = NULL;
+ while( *pRoot )
+ {
+ StgAvlNode* p = Rem( pRoot, *pRoot, false );
+ Insert( &pNew, p );
+ }
+ *pRoot = pNew;*/
+ return true;
+ }
+ else
+ return false;
+}
+
+// Move node to a different tree. Returns true is found and moved. This routine
+// may be called when the key has changed.
+
+
+////////////////////////// class AvlIterator
+
+// The iterator walks through a tree one entry by one.
+
+StgAvlIterator::StgAvlIterator( StgAvlNode* p )
+{
+ m_pRoot = p;
+ m_nCur = 0;
+ if( p )
+ {
+ short nCount = 0; // tree size
+ p->StgEnum( nCount );
+ }
+}
+
+StgAvlNode* StgAvlIterator::Find( short n )
+{
+ StgAvlNode* p = m_pRoot;
+ while( p )
+ {
+ if( n == p->m_nId )
+ break;
+ else p = ( n < p->m_nId ) ? p->m_pLeft : p->m_pRight;
+ }
+ return p;
+}
+
+StgAvlNode* StgAvlIterator::First()
+{
+ m_nCur = -1;
+ return Next();
+}
+
+StgAvlNode* StgAvlIterator::Next()
+{
+ return Find( ++m_nCur );
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */