0029151: GCC 7.1 warnings "this statement may fall through" [-Wimplicit-fallthrough=]
[occt.git] / src / NCollection / NCollection_SparseArrayBase.cxx
CommitLineData
b311480e 1// Created on: 2007-02-06
2// Created by: Andrey BETENEV
973c2be1 3// Copyright (c) 2007-2014 OPEN CASCADE SAS
b311480e 4//
973c2be1 5// This file is part of Open CASCADE Technology software library.
b311480e 6//
d5f74e42 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
973c2be1 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.
b311480e 12//
973c2be1 13// Alternatively, this file may be used under the terms of Open CASCADE
14// commercial license or contractual agreement.
7fd59977 15
16#include <NCollection_SparseArrayBase.hxx>
17#include <Standard_ProgramError.hxx>
18
19//=======================================================================
20//function : allocData
21//purpose :
22//=======================================================================
23
24void 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
50void 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
69void 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
90void 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
180template<class T> static inline void sswap (T &a, T &b) { T c = a; a = b; b = c; }
181
182void 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
d93f7683 200Standard_Address NCollection_SparseArrayBase::setValue (const Standard_Size theIndex,
7fd59977 201 const Standard_Address theValue)
202{
d93f7683 203 Standard_Size iBlock = theIndex / myBlockSize;
7fd59977 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
d93f7683 218 Standard_Size anInd = theIndex % myBlockSize;
7fd59977 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
d93f7683 239Standard_Boolean NCollection_SparseArrayBase::HasValue (const Standard_Size theIndex) const
7fd59977 240{
d93f7683
P
241 Standard_Size iBlock = theIndex / myBlockSize;
242 if ( iBlock >= myNbBlocks ||
7fd59977 243 ! myData[iBlock] )
244 return Standard_False;
d93f7683 245 return getBlock(myData[iBlock]).IsSet(theIndex % myBlockSize) ? Standard_True : Standard_False;
7fd59977 246}
247
248//=======================================================================
249//function : UnsetValue
250//purpose :
251//=======================================================================
252
d93f7683 253Standard_Boolean NCollection_SparseArrayBase::UnsetValue (const Standard_Size theIndex)
7fd59977 254{
255 // check that the item is defined
d93f7683
P
256 Standard_Size iBlock = theIndex / myBlockSize;
257 if ( iBlock >= myNbBlocks || ! myData[iBlock] )
7fd59977 258 return Standard_False;
259
260 Block aBlock (getBlock(myData[iBlock]));
d93f7683 261 Standard_Size anInd = theIndex % myBlockSize;
7fd59977 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
282NCollection_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
295void 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
330void 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