0023373: MSVC++ warnings issued during compilation for 64bits, 'Sparse Arrays'
[occt.git] / 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_Size theIndex,
206                                                         const Standard_Address theValue) 
207 {
208   Standard_Size iBlock = theIndex / myBlockSize;
209     
210   // resize blocks array if necessary
211   if ( iBlock >= myNbBlocks )
212     allocData (iBlock);
213
214   // allocate block if necessary
215   Standard_Address & anAddr = myData[iBlock];
216   if ( ! anAddr )
217     anAddr = calloc (Block::Size(myBlockSize, myItemSize), sizeof(char));
218
219   // get a block
220   Block aBlock (getBlock (anAddr));
221
222   // mark item as defined 
223   Standard_Size anInd = theIndex % myBlockSize;
224   Standard_Address anItem = getItem (aBlock, anInd);
225
226   // either create an item by copy constructor if it is new, or assign it
227   if ( aBlock.Set(anInd) )
228   {
229     (*aBlock.Count)++;
230     mySize++;
231     createItem (anItem, theValue);
232   }
233   else
234     copyItem (anItem, theValue);
235     
236   return anItem;
237 }
238
239 //=======================================================================
240 //function : HasValue
241 //purpose  : 
242 //=======================================================================
243
244 Standard_Boolean NCollection_SparseArrayBase::HasValue (const Standard_Size theIndex) const
245 {
246   Standard_Size iBlock = theIndex / myBlockSize;
247   if ( iBlock >= myNbBlocks ||
248        ! myData[iBlock] )
249     return Standard_False;
250   return getBlock(myData[iBlock]).IsSet(theIndex % myBlockSize) ? Standard_True : Standard_False;
251 }
252
253 //=======================================================================
254 //function : UnsetValue
255 //purpose  : 
256 //=======================================================================
257
258 Standard_Boolean NCollection_SparseArrayBase::UnsetValue (const Standard_Size theIndex)
259 {
260   // check that the item is defined
261   Standard_Size iBlock = theIndex / myBlockSize;
262   if ( iBlock >= myNbBlocks || ! myData[iBlock] )
263     return Standard_False;
264
265   Block aBlock (getBlock(myData[iBlock]));
266   Standard_Size anInd = theIndex % myBlockSize;
267   if ( ! aBlock.Unset(anInd) )
268     return Standard_False;
269
270   // destroy the item
271   destroyItem (getItem (aBlock, anInd));
272   (*aBlock.Count)--;
273   mySize--;
274
275   // free block if it becomes empty
276   if ( ! (*aBlock.Count) )
277     freeBlock (iBlock);
278
279   return Standard_True;
280 }
281
282 //=======================================================================
283 //function : Iterator::Iterator
284 //purpose  : 
285 //=======================================================================
286
287 NCollection_SparseArrayBase::Iterator::Iterator (const NCollection_SparseArrayBase* theArray)
288 : myArr((NCollection_SparseArrayBase*)theArray),
289   myHasMore(Standard_False), myIBlock(0), myInd(0), 
290   myBlock(0,0,0)
291 {
292   init(theArray);
293 }
294
295 //=======================================================================
296 //function : Iterator::Next
297 //purpose  : 
298 //=======================================================================
299
300 void NCollection_SparseArrayBase::Iterator::Next ()
301 {
302   if ( ! myArr || ! myHasMore )
303     return;
304
305   // iterate by items and blocks  
306   for ( myInd++; ; myInd++ ) {
307     // if index is over the block size, advance to the next non-empty block
308     if ( myInd >= myArr->myBlockSize )
309     {
310       for ( myIBlock++; ; myIBlock++ ) {
311         if ( myIBlock >= myArr->myNbBlocks ) // end
312         {
313           myHasMore = Standard_False;
314           return;
315         }
316         if ( myArr->myData[myIBlock] )
317         {
318           myInd = 0;
319           myBlock = Block (myArr->myData[myIBlock], myArr->myBlockSize, myArr->myItemSize );
320           break;
321         }
322       }
323     }
324     // check if item is defined
325     if ( myBlock.IsSet (myInd) )
326       return;
327   }
328 }
329
330 //=======================================================================
331 //function : Iterator::init
332 //purpose  : 
333 //=======================================================================
334
335 void NCollection_SparseArrayBase::Iterator::init (const NCollection_SparseArrayBase* theArray)
336 {
337   myArr = (NCollection_SparseArrayBase*)theArray;
338   myHasMore = Standard_False;
339   if ( myArr ) 
340   {
341     myInd = 0;
342     // find first non-empty block
343     for ( myIBlock=0; myIBlock < myArr->myNbBlocks; myIBlock++ )
344     {
345       if ( ! myArr->myData[myIBlock] ) 
346         continue;
347       myHasMore = Standard_True;
348       myBlock = Block (myArr->myData[myIBlock], myArr->myBlockSize, myArr->myItemSize );
349       // if first item in the block is not set, advance to the next defined item
350       if ( ! myBlock.IsSet(myInd) )
351         Next();
352       return;
353     }
354   }
355 }
356