sot/source/sdstor/stgavl.cxx

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