Adding upstream version 4:24.2.0.upstream/4%24.2.0

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

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 0000000000..98a86f3edb
--- /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: */