src/NCollection/NCollection_SparseArrayBase.cxx

   1 // Created on: 2007-02-06
   2 // Created by: Andrey BETENEV
   3 // Copyright (c) 2007-2014 OPEN CASCADE SAS
   4 //
   5 // This file is part of Open CASCADE Technology software library.
   6 //
   7 // This library is free software; you can redistribute it and/or modify it under
   8 // the terms of the GNU Lesser General Public License version 2.1 as published
   9 // by the Free Software Foundation, with special exception defined in the file
  10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  11 // distribution for complete text of the license and disclaimer of any warranty.
  12 //
  13 // Alternatively, this file may be used under the terms of Open CASCADE
  14 // commercial license or contractual agreement.
  15
  16 #include <NCollection_SparseArrayBase.hxx>
  17 #include <Standard_ProgramError.hxx>
  18
  19 //=======================================================================
  20 //function : allocData
  21 //purpose  :
  22 //=======================================================================
  23
  24 void NCollection_SparseArrayBase::allocData (const Standard_Size iBlock)
  25 {
  26   if ( iBlock < myNbBlocks )
  27     return;
  28
  29   // the allocation of blocks starts from myBlockSize items
  30   // and then is multiplied by 2 every time reallocation is needed
  31   Standard_Size newNbBlocks = ( myNbBlocks ? myNbBlocks * 2 : myBlockSize );
  32   while (iBlock >= newNbBlocks) newNbBlocks *= 2;
  33
  34   Standard_Address* newData =
  35     (Standard_Address*)malloc(newNbBlocks*sizeof(Standard_Address));
  36   if ( myNbBlocks >0 )
  37     memcpy (newData, myData, myNbBlocks*sizeof(Standard_Address));
  38   memset (newData+myNbBlocks, 0, (newNbBlocks-myNbBlocks)*sizeof(Standard_Address));
  39
  40   free (myData);
  41   myData = newData;
  42   myNbBlocks = newNbBlocks;
  43 }
  44
  45 //=======================================================================
  46 //function : freeBlock
  47 //purpose  :
  48 //=======================================================================
  49
  50 void NCollection_SparseArrayBase::freeBlock (const Standard_Size iBlock)
  51 {
  52   Standard_Address & anAddr = myData[iBlock];
  53   Block aBlock = getBlock(anAddr);
  54   for (Standard_Size anInd=0; anInd < myBlockSize; anInd++)
  55     if ( aBlock.IsSet(anInd) )
  56     {
  57       destroyItem (getItem (aBlock, anInd));
  58       mySize--;
  59     }
  60   free (anAddr);
  61   anAddr = 0;
  62 }
  63
  64 //=======================================================================
  65 //function : Clear
  66 //purpose  :
  67 //=======================================================================
  68
  69 void NCollection_SparseArrayBase::Clear ()
  70 {
  71   // free block data
  72   for (Standard_Size iBlock=0; iBlock < myNbBlocks; iBlock++)
  73     if ( myData[iBlock] )
  74       freeBlock (iBlock);
  75
  76   // free blocks and reset counters
  77   free (myData);
  78   myData = 0;
  79   myNbBlocks = 0;
  80
  81   // consistency check
  82   Standard_ProgramError_Raise_if (mySize!=0,"NCollection_SparseArrayBase: Implementation error: inconsistent items count")
  83 }
  84
  85 //=======================================================================
  86 //function : assign
  87 //purpose  :
  88 //=======================================================================
  89
  90 void NCollection_SparseArrayBase::assign (const NCollection_SparseArrayBase& theOther)
  91 {
  92   if (this == &theOther)
  93     return;
  94
  95   // if block size is different, clear all data
  96   if ( myBlockSize != theOther.myBlockSize )
  97     Clear();
  98   myBlockSize = theOther.myBlockSize;
  99
 100   // iterate by blocks in theOther
 101   Standard_Size iBlock=0;
 102   for (; iBlock < theOther.myNbBlocks; iBlock++)
 103   {
 104     if ( ! theOther.myData[iBlock] )
 105     {
 106       // if other block is empty, just make sure to empty that block in "this"
 107       if ( iBlock < myNbBlocks && myData[iBlock] )
 108         freeBlock (iBlock);
 109       continue;
 110     }
 111
 112     if ( iBlock >= myNbBlocks )
 113       allocData(iBlock);
 114     Block anOtherBlock = getBlock(theOther.myData[iBlock]);
 115
 116     // if block not yet allocated, just allocate and fill
 117     Standard_Address & anAddr = myData[iBlock];
 118     if ( ! anAddr )
 119     {
 120       anAddr = calloc (Block::Size(myBlockSize, myItemSize), sizeof(char));
 121       Block aBlock ( getBlock(anAddr) );
 122       for (Standard_Size anInd=0; anInd < myBlockSize; anInd++)
 123         if ( anOtherBlock.IsSet(anInd) )
 124         {
 125           Standard_Address anItem = getItem (aBlock, anInd);
 126           aBlock.Set(anInd);
 127           (*aBlock.Count)++;
 128           mySize++;
 129           createItem (anItem, getItem(anOtherBlock, anInd));
 130         }
 131     }
 132     // else perform copying item-by-item
 133     else
 134     {
 135       Block aBlock ( getBlock(anAddr) );
 136       for (Standard_Size anInd=0; anInd < myBlockSize; anInd++)
 137       {
 138         Standard_Address anItem = getItem (aBlock, anInd);
 139         if ( anOtherBlock.IsSet(anInd) )
 140         {
 141           Standard_Address anOtherItem = getItem (anOtherBlock, anInd);
 142           if ( aBlock.IsSet(anInd) ) // copy
 143           {
 144             copyItem (anItem, anOtherItem);
 145           }
 146           else // create
 147           {
 148             aBlock.Set(anInd);
 149             (*aBlock.Count)++;
 150             mySize++;
 151             createItem (anItem, getItem(anOtherBlock, anInd));
 152           }
 153         }
 154         else if ( aBlock.IsSet(anInd) ) // delete
 155         {
 156           aBlock.Set(anInd);
 157           (*aBlock.Count)--;
 158           mySize--;
 159           destroyItem (anItem);
 160         }
 161       }
 162     }
 163   }
 164
 165   // clear any remaining blocks in this
 166   for (; iBlock < myNbBlocks; iBlock++)
 167     if ( myData[iBlock] )
 168       freeBlock (iBlock);
 169
 170   // consistency check
 171   Standard_ProgramError_Raise_if (mySize!=theOther.mySize,
 172                                  "NCollection_SparseArrayBase: Implementation error: inconsistent items count")
 173 }
 174
 175 //=======================================================================
 176 //function : exchange
 177 //purpose  :
 178 //=======================================================================
 179
 180 template<class T> static inline void sswap (T &a, T &b) { T c = a; a = b; b = c; }
 181
 182 void NCollection_SparseArrayBase::exchange (NCollection_SparseArrayBase& theOther)
 183 {
 184   if (this == &theOther)
 185     return;
 186
 187   // swap fields of this and theOther
 188   sswap (myItemSize, theOther.myItemSize);
 189   sswap (myBlockSize,theOther.myBlockSize);
 190   sswap (myNbBlocks, theOther.myNbBlocks);
 191   sswap (mySize,     theOther.mySize);
 192   sswap (myData,     theOther.myData);
 193 }
 194
 195 //=======================================================================
 196 //function : setValue
 197 //purpose  :
 198 //=======================================================================
 199
 200 Standard_Address NCollection_SparseArrayBase::setValue (const Standard_Size theIndex,
 201                                                         const Standard_Address theValue)
 202 {
 203   Standard_Size iBlock = theIndex / myBlockSize;
 204
 205   // resize blocks array if necessary
 206   if ( iBlock >= myNbBlocks )
 207     allocData (iBlock);
 208
 209   // allocate block if necessary
 210   Standard_Address & anAddr = myData[iBlock];
 211   if ( ! anAddr )
 212     anAddr = calloc (Block::Size(myBlockSize, myItemSize), sizeof(char));
 213
 214   // get a block
 215   Block aBlock (getBlock (anAddr));
 216
 217   // mark item as defined
 218   Standard_Size anInd = theIndex % myBlockSize;
 219   Standard_Address anItem = getItem (aBlock, anInd);
 220
 221   // either create an item by copy constructor if it is new, or assign it
 222   if ( aBlock.Set(anInd) )
 223   {
 224     (*aBlock.Count)++;
 225     mySize++;
 226     createItem (anItem, theValue);
 227   }
 228   else
 229     copyItem (anItem, theValue);
 230
 231   return anItem;
 232 }
 233
 234 //=======================================================================
 235 //function : HasValue
 236 //purpose  :
 237 //=======================================================================
 238
 239 Standard_Boolean NCollection_SparseArrayBase::HasValue (const Standard_Size theIndex) const
 240 {
 241   Standard_Size iBlock = theIndex / myBlockSize;
 242   if ( iBlock >= myNbBlocks ||
 243        ! myData[iBlock] )
 244     return Standard_False;
 245   return getBlock(myData[iBlock]).IsSet(theIndex % myBlockSize) ? Standard_True : Standard_False;
 246 }
 247
 248 //=======================================================================
 249 //function : UnsetValue
 250 //purpose  :
 251 //=======================================================================
 252
 253 Standard_Boolean NCollection_SparseArrayBase::UnsetValue (const Standard_Size theIndex)
 254 {
 255   // check that the item is defined
 256   Standard_Size iBlock = theIndex / myBlockSize;
 257   if ( iBlock >= myNbBlocks || ! myData[iBlock] )
 258     return Standard_False;
 259
 260   Block aBlock (getBlock(myData[iBlock]));
 261   Standard_Size anInd = theIndex % myBlockSize;
 262   if ( ! aBlock.Unset(anInd) )
 263     return Standard_False;
 264
 265   // destroy the item
 266   destroyItem (getItem (aBlock, anInd));
 267   (*aBlock.Count)--;
 268   mySize--;
 269
 270   // free block if it becomes empty
 271   if ( ! (*aBlock.Count) )
 272     freeBlock (iBlock);
 273
 274   return Standard_True;
 275 }
 276
 277 //=======================================================================
 278 //function : Iterator::Iterator
 279 //purpose  :
 280 //=======================================================================
 281
 282 NCollection_SparseArrayBase::Iterator::Iterator (const NCollection_SparseArrayBase* theArray)
 283 : myArr((NCollection_SparseArrayBase*)theArray),
 284   myHasMore(Standard_False), myIBlock(0), myInd(0),
 285   myBlock(0,0,0)
 286 {
 287   init(theArray);
 288 }
 289
 290 //=======================================================================
 291 //function : Iterator::Next
 292 //purpose  :
 293 //=======================================================================
 294
 295 void NCollection_SparseArrayBase::Iterator::Next ()
 296 {
 297   if ( ! myArr || ! myHasMore )
 298     return;
 299
 300   // iterate by items and blocks
 301   for ( myInd++; ; myInd++ ) {
 302     // if index is over the block size, advance to the next non-empty block
 303     if ( myInd >= myArr->myBlockSize )
 304     {
 305       for ( myIBlock++; ; myIBlock++ ) {
 306         if ( myIBlock >= myArr->myNbBlocks ) // end
 307         {
 308           myHasMore = Standard_False;
 309           return;
 310         }
 311         if ( myArr->myData[myIBlock] )
 312         {
 313           myInd = 0;
 314           myBlock = Block (myArr->myData[myIBlock], myArr->myBlockSize, myArr->myItemSize );
 315           break;
 316         }
 317       }
 318     }
 319     // check if item is defined
 320     if ( myBlock.IsSet (myInd) )
 321       return;
 322   }
 323 }
 324
 325 //=======================================================================
 326 //function : Iterator::init
 327 //purpose  :
 328 //=======================================================================
 329
 330 void NCollection_SparseArrayBase::Iterator::init (const NCollection_SparseArrayBase* theArray)
 331 {
 332   myArr = (NCollection_SparseArrayBase*)theArray;
 333   myHasMore = Standard_False;
 334   if ( myArr )
 335   {
 336     myInd = 0;
 337     // find first non-empty block
 338     for ( myIBlock=0; myIBlock < myArr->myNbBlocks; myIBlock++ )
 339     {
 340       if ( ! myArr->myData[myIBlock] )
 341         continue;
 342       myHasMore = Standard_True;
 343       myBlock = Block (myArr->myData[myIBlock], myArr->myBlockSize, myArr->myItemSize );
 344       // if first item in the block is not set, advance to the next defined item
 345       if ( ! myBlock.IsSet(myInd) )
 346         Next();
 347       return;
 348     }
 349   }
 350 }
 351