src/NCollection/NCollection_SparseArrayBase.cxx

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