LCOV - code coverage report
Current view: top level - sot/source/sdstor - stgavl.cxx (source / functions) Hit Total Coverage
Test: commit e02a6cb2c3e2b23b203b422e4e0680877f232636 Lines: 0 200 0.0 %
Date: 2014-04-14 Functions: 0 19 0.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
       2             : /*
       3             :  * This file is part of the LibreOffice project.
       4             :  *
       5             :  * This Source Code Form is subject to the terms of the Mozilla Public
       6             :  * License, v. 2.0. If a copy of the MPL was not distributed with this
       7             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
       8             :  *
       9             :  * This file incorporates work covered by the following license notice:
      10             :  *
      11             :  *   Licensed to the Apache Software Foundation (ASF) under one or more
      12             :  *   contributor license agreements. See the NOTICE file distributed
      13             :  *   with this work for additional information regarding copyright
      14             :  *   ownership. The ASF licenses this file to you under the Apache
      15             :  *   License, Version 2.0 (the "License"); you may not use this file
      16             :  *   except in compliance with the License. You may obtain a copy of
      17             :  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
      18             :  */
      19             : 
      20             : #include <osl/diagnose.h>
      21             : #include "stgavl.hxx"
      22             : 
      23           0 : StgAvlNode::StgAvlNode()
      24             : {
      25           0 :     pLeft = pRight = NULL;
      26           0 :     nBalance = nId = 0;
      27           0 : }
      28             : 
      29           0 : StgAvlNode::~StgAvlNode()
      30             : {
      31           0 :     delete pLeft;
      32           0 :     delete pRight;
      33           0 : }
      34             : 
      35           0 : StgAvlNode* StgAvlNode::Find( StgAvlNode* pFind )
      36             : {
      37           0 :     if ( pFind )
      38             :     {
      39           0 :         StgAvlNode* p = this;
      40           0 :         while( p )
      41             :         {
      42           0 :             short nRes = p->Compare( pFind );
      43           0 :             if( !nRes )
      44           0 :                 return p;
      45           0 :             else p = ( nRes < 0 ) ? p->pLeft : p->pRight;
      46             :         }
      47             :     }
      48           0 :     return NULL;
      49             : }
      50             : 
      51             : // find point to add node to AVL tree and returns
      52             : // +/0/- for >/=/< previous
      53             : 
      54           0 : short StgAvlNode::Locate
      55             :     ( StgAvlNode* pFind,
      56             :       StgAvlNode** pPivot, StgAvlNode **pParent, StgAvlNode** pPrev )
      57             : {
      58           0 :     short nRes = 0;
      59           0 :     StgAvlNode* pCur = this;
      60             : 
      61             :     OSL_ENSURE( pPivot && pParent && pPrev, "The pointers may not be NULL!" );
      62           0 :     *pParent = *pPrev = NULL;
      63           0 :     *pPivot = this;
      64             : 
      65             :     // search tree for insertion point
      66           0 :     if ( pFind )
      67             :     {
      68           0 :         while( pCur != NULL )
      69             :         {
      70             :             // check for pPivot
      71           0 :             if( pCur->nBalance != 0 )
      72           0 :                 *pPivot = pCur, *pParent = *pPrev;
      73             :             // save pPrev location and see what direction to go
      74           0 :             *pPrev = pCur;
      75           0 :             nRes = pCur->Compare( pFind );
      76           0 :             if( nRes == 0 )
      77           0 :                 break;
      78           0 :             else pCur = ( nRes < 0 ) ? pCur->pLeft : pCur->pRight;
      79             :         }
      80             :     }
      81             : 
      82           0 :     return( nRes );
      83             : }
      84             : 
      85             : // adjust balance factors in AVL tree from pivot down.
      86             : // Returns delta balance.
      87             : 
      88           0 : short StgAvlNode::Adjust( StgAvlNode** pHeavy, StgAvlNode* pNew )
      89             : {
      90           0 :     StgAvlNode* pCur = this;
      91             :     short nDelta;
      92             :     // no traversing
      93             :     OSL_ENSURE( pHeavy && pNew, "The pointers is not allowed to be NULL!" );
      94           0 :     if( pCur == pNew || !pNew )
      95           0 :         return nBalance;
      96             : 
      97           0 :     short nRes = Compare( pNew );
      98           0 :     if( nRes > 0 )
      99             :     {
     100           0 :         *pHeavy = pCur = pRight;
     101           0 :         nDelta = -1;
     102             :     }
     103             :     else
     104             :     {
     105           0 :         *pHeavy = pCur = pLeft;
     106           0 :         nDelta = 1;
     107             :     }
     108           0 :     nBalance = 0;
     109           0 :     while( pCur != pNew )
     110             :     {
     111           0 :         nRes = pCur->Compare( pNew );
     112           0 :         if( nRes > 0 )
     113             :         {
     114             :             // height of right increases by 1
     115           0 :             pCur->nBalance = -1;
     116           0 :             pCur = pCur->pRight;
     117             :         }
     118             :         else
     119             :         {
     120             :             // height of left increases by 1
     121           0 :             pCur->nBalance = 1;
     122           0 :             pCur = pCur->pLeft;
     123             :         }
     124             :     }
     125           0 :     nBalance = nBalance + nDelta;
     126           0 :     return nDelta;
     127             : }
     128             : 
     129             : // perform LL rotation and return new root
     130             : 
     131           0 : StgAvlNode* StgAvlNode::RotLL()
     132             : {
     133             :     OSL_ENSURE( pLeft, "The pointer is not allowed to be NULL!" );
     134           0 :     StgAvlNode *pHeavy = pLeft;
     135           0 :     pLeft = pHeavy->pRight;
     136           0 :     pHeavy->pRight = this;
     137           0 :     pHeavy->nBalance = nBalance = 0;
     138           0 :     return pHeavy;
     139             : }
     140             : 
     141             : // perform LR rotation and return new root
     142             : 
     143           0 : StgAvlNode* StgAvlNode::RotLR()
     144             : {
     145             :     OSL_ENSURE( pLeft && pLeft->pRight, "The pointer is not allowed to be NULL!" );
     146           0 :     StgAvlNode* pHeavy = pLeft;
     147           0 :     StgAvlNode* pNewRoot = pHeavy->pRight;
     148             : 
     149           0 :     pHeavy->pRight = pNewRoot->pLeft;
     150           0 :     pLeft = pNewRoot->pRight;
     151           0 :     pNewRoot->pLeft = pHeavy;
     152           0 :     pNewRoot->pRight = this;
     153             : 
     154           0 :     switch( pNewRoot->nBalance )
     155             :     {
     156             :         case 1:     // LR( b )
     157           0 :             nBalance = -1;
     158           0 :             pHeavy->nBalance = 0;
     159           0 :             break;
     160             :         case -1:    // LR( c )
     161           0 :             pHeavy->nBalance = 1;
     162           0 :             nBalance = 0;
     163           0 :             break;
     164             :         case 0:     // LR( a )
     165           0 :             nBalance = 0;
     166           0 :             pHeavy->nBalance = 0;
     167           0 :             break;
     168             :     }
     169           0 :     pNewRoot->nBalance = 0;
     170           0 :     return pNewRoot;
     171             : }
     172             : 
     173             : // perform RR rotation and return new root
     174             : 
     175           0 : StgAvlNode* StgAvlNode::RotRR()
     176             : {
     177             :     OSL_ENSURE( pRight, "The pointer is not allowed to be NULL!" );
     178           0 :     StgAvlNode* pHeavy = pRight;
     179           0 :     pRight = pHeavy->pLeft;
     180           0 :     pHeavy->pLeft = this;
     181           0 :     nBalance = pHeavy->nBalance = 0;
     182           0 :     return pHeavy;
     183             : }
     184             : 
     185             : // perform the RL rotation and return the new root
     186             : 
     187           0 : StgAvlNode* StgAvlNode::RotRL()
     188             : {
     189             :     OSL_ENSURE( pRight && pRight->pLeft, "The pointer is not allowed to be NULL!" );
     190           0 :     StgAvlNode* pHeavy = pRight;
     191           0 :     StgAvlNode* pNewRoot = pHeavy->pLeft;
     192           0 :     pHeavy->pLeft = pNewRoot->pRight;
     193           0 :     pRight = pNewRoot->pLeft;
     194           0 :     pNewRoot->pRight = pHeavy;
     195           0 :     pNewRoot->pLeft = this;
     196           0 :     switch( pNewRoot->nBalance )
     197             :     {
     198             :         case -1:    // RL( b )
     199           0 :             nBalance = 1;
     200           0 :             pHeavy->nBalance = 0;
     201           0 :             break;
     202             :         case 1:     // RL( c )
     203           0 :             pHeavy->nBalance = -1;
     204           0 :             nBalance = 0;
     205           0 :             break;
     206             :         case 0:     // RL( a )
     207           0 :             nBalance = 0;
     208           0 :             pHeavy->nBalance = 0;
     209           0 :             break;
     210             :     }
     211           0 :     pNewRoot->nBalance = 0;
     212           0 :     return pNewRoot;
     213             : }
     214             : 
     215             : // Remove a tree element. Return the removed element or NULL.
     216             : 
     217           0 : StgAvlNode* StgAvlNode::Rem( StgAvlNode** p, StgAvlNode* pDel, bool bPtrs )
     218             : {
     219           0 :     if( p && *p && pDel )
     220             :     {
     221           0 :         StgAvlNode* pCur = *p;
     222           0 :         short nRes = bPtrs ? short( pCur == pDel ) : short(pCur->Compare( pDel ));
     223           0 :         if( !nRes )
     224             :         {
     225             :             // Element found: remove
     226           0 :             if( !pCur->pRight )
     227             :             {
     228           0 :                 *p = pCur->pLeft; pCur->pLeft = NULL;
     229             :             }
     230           0 :             else if( !pCur->pLeft )
     231             :             {
     232           0 :                 *p = pCur->pRight; pCur->pRight = NULL;
     233             :             }
     234             :             else
     235             :             {
     236             :                 // The damn element has two leaves. Get the
     237             :                 // rightmost element of the left subtree (which
     238             :                 // is lexically before this element) and replace
     239             :                 // this element with the element found.
     240           0 :                 StgAvlNode* last = pCur;
     241             :                 StgAvlNode* l;
     242           0 :                 for( l = pCur->pLeft;
     243             :                      l->pRight; last = l, l = l->pRight ) {}
     244             :                 // remove the element from chain
     245           0 :                 if( l == last->pRight )
     246           0 :                     last->pRight = l->pLeft;
     247             :                 else
     248           0 :                     last->pLeft = l->pLeft;
     249             :                 // perform the replacement
     250           0 :                 l->pLeft = pCur->pLeft;
     251           0 :                 l->pRight = pCur->pRight;
     252           0 :                 *p = l;
     253             :                 // delete the element
     254           0 :                 pCur->pLeft = pCur->pRight = NULL;
     255             :             }
     256           0 :             return pCur;
     257             :         }
     258             :         else
     259             :         {
     260           0 :             if( nRes < 0 )
     261           0 :                 return Rem( &pCur->pLeft, pDel, bPtrs );
     262             :             else
     263           0 :                 return Rem( &pCur->pRight, pDel, bPtrs );
     264             :         }
     265             :     }
     266           0 :     return NULL;
     267             : }
     268             : 
     269             : // Enumerate the tree for later iteration
     270             : 
     271           0 : void StgAvlNode::StgEnum( short& n )
     272             : {
     273           0 :     if( pLeft )
     274           0 :         pLeft->StgEnum( n );
     275           0 :     nId = n++;
     276           0 :     if( pRight )
     277           0 :         pRight->StgEnum( n );
     278           0 : }
     279             : 
     280             : // Add node to AVL tree.
     281             : // Return false if the element already exists.
     282             : 
     283           0 : bool StgAvlNode::Insert( StgAvlNode** pRoot, StgAvlNode* pIns )
     284             : {
     285             :     StgAvlNode* pPivot, *pHeavy, *pNewRoot, *pParent, *pPrev;
     286           0 :     if ( !pRoot )
     287           0 :         return false;
     288             : 
     289             :     // special case - empty tree
     290           0 :     if( *pRoot == NULL )
     291             :     {
     292           0 :         *pRoot = pIns;
     293           0 :         return true;
     294             :     }
     295             :     // find insertion point and return if already present
     296           0 :     short nRes = (*pRoot)->Locate( pIns, &pPivot, &pParent, &pPrev );
     297           0 :     if( !nRes )
     298           0 :         return false;
     299             :     OSL_ENSURE( pPivot && pPrev, "The pointers may not be NULL!" );
     300             : 
     301             :     // add new node
     302           0 :     if( nRes < 0 )
     303           0 :         pPrev->pLeft = pIns;
     304             :     else
     305           0 :         pPrev->pRight = pIns;
     306             :     // rebalance tree
     307           0 :     short nDelta = pPivot->Adjust( &pHeavy, pIns );
     308           0 :     if( pPivot->nBalance >= 2 || pPivot->nBalance <= -2 )
     309             :     {
     310           0 :         pHeavy = ( nDelta < 0 ) ? pPivot->pRight : pPivot->pLeft;
     311             :         // left imbalance
     312           0 :         if( nDelta > 0 )
     313           0 :             if( pHeavy->nBalance == 1 )
     314           0 :                 pNewRoot = pPivot->RotLL();
     315             :             else
     316           0 :                 pNewRoot = pPivot->RotLR();
     317             :         // right imbalance
     318           0 :         else if( pHeavy->nBalance == -1 )
     319           0 :             pNewRoot = pPivot->RotRR();
     320             :         else
     321           0 :             pNewRoot = pPivot->RotRL();
     322             :         // relink balanced subtree
     323           0 :         if( pParent == NULL )
     324           0 :             *pRoot = pNewRoot;
     325           0 :         else if( pPivot == pParent->pLeft )
     326           0 :             pParent->pLeft = pNewRoot;
     327           0 :         else if( pPivot == pParent->pRight )
     328           0 :             pParent->pRight = pNewRoot;
     329             :     }
     330           0 :     return true;
     331             : }
     332             : 
     333             : // Remove node from tree. Returns true is found and removed.
     334             : // Actually delete if bDel
     335             : 
     336           0 : bool StgAvlNode::Remove( StgAvlNode** pRoot, StgAvlNode* pDel, bool bDel )
     337             : {
     338           0 :     if ( !pRoot )
     339           0 :         return false;
     340             : 
     341             :     // special case - empty tree
     342           0 :     if( *pRoot == NULL )
     343           0 :         return false;
     344             :     // delete the element
     345           0 :     pDel = Rem( pRoot, pDel, false );
     346           0 :     if( pDel )
     347             :     {
     348           0 :         if( bDel )
     349           0 :             delete pDel;
     350             :         // Rebalance the tree the hard way
     351             :         // OS 22.09.95: Auf MD's Wunsch auskommentiert wg. Absturz
     352             : /*      StgAvlNode* pNew = NULL;
     353             :         while( *pRoot )
     354             :         {
     355             :             StgAvlNode* p = Rem( pRoot, *pRoot, false );
     356             :             Insert( &pNew, p );
     357             :         }
     358             :         *pRoot = pNew;*/
     359           0 :         return true;
     360             :     }
     361             :     else
     362           0 :         return false;
     363             : }
     364             : 
     365             : // Move node to a different tree. Returns true is found and moved. This routine
     366             : // may be called when the key has changed.
     367             : 
     368           0 : bool StgAvlNode::Move( StgAvlNode** pRoot1, StgAvlNode** pRoot2, StgAvlNode* pMove )
     369             : {
     370           0 :     if ( !pRoot1 )
     371           0 :         return false;
     372             : 
     373             :     // special case - empty tree
     374           0 :     if( *pRoot1 == NULL )
     375           0 :         return false;
     376           0 :     pMove = Rem( pRoot1, pMove, false );
     377           0 :     if( pMove )
     378           0 :         return Insert( pRoot2, pMove );
     379             :     else
     380           0 :         return false;
     381             : }
     382             : 
     383             : ////////////////////////// class AvlIterator
     384             : 
     385             : // The iterator walks through a tree one entry by one.
     386             : 
     387           0 : StgAvlIterator::StgAvlIterator( StgAvlNode* p )
     388             : {
     389           0 :     pRoot = p;
     390           0 :     nCount = 0;
     391           0 :     nCur = 0;
     392           0 :     if( p )
     393           0 :         p->StgEnum( nCount );
     394           0 : }
     395             : 
     396           0 : StgAvlNode* StgAvlIterator::Find( short n )
     397             : {
     398           0 :     StgAvlNode* p = pRoot;
     399           0 :     while( p )
     400             :     {
     401           0 :         if( n == p->nId )
     402           0 :             break;
     403           0 :         else p = ( n < p->nId ) ? p->pLeft : p->pRight;
     404             :     }
     405           0 :     return p;
     406             : }
     407             : 
     408           0 : StgAvlNode* StgAvlIterator::First()
     409             : {
     410           0 :     nCur = -1;
     411           0 :     return Next();
     412             : }
     413             : 
     414           0 : StgAvlNode* StgAvlIterator::Next()
     415             : {
     416           0 :     return Find( ++nCur );
     417             : }
     418             : 
     419             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.10