Commit | Line | Data |
---|---|---|
b311480e | 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 | ||
7fd59977 | 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 | ||
d93f7683 | 205 | Standard_Address NCollection_SparseArrayBase::setValue (const Standard_Size theIndex, |
7fd59977 | 206 | const Standard_Address theValue) |
207 | { | |
d93f7683 | 208 | Standard_Size iBlock = theIndex / myBlockSize; |
7fd59977 | 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 | |
d93f7683 | 223 | Standard_Size anInd = theIndex % myBlockSize; |
7fd59977 | 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 | ||
d93f7683 | 244 | Standard_Boolean NCollection_SparseArrayBase::HasValue (const Standard_Size theIndex) const |
7fd59977 | 245 | { |
d93f7683 P |
246 | Standard_Size iBlock = theIndex / myBlockSize; |
247 | if ( iBlock >= myNbBlocks || | |
7fd59977 | 248 | ! myData[iBlock] ) |
249 | return Standard_False; | |
d93f7683 | 250 | return getBlock(myData[iBlock]).IsSet(theIndex % myBlockSize) ? Standard_True : Standard_False; |
7fd59977 | 251 | } |
252 | ||
253 | //======================================================================= | |
254 | //function : UnsetValue | |
255 | //purpose : | |
256 | //======================================================================= | |
257 | ||
d93f7683 | 258 | Standard_Boolean NCollection_SparseArrayBase::UnsetValue (const Standard_Size theIndex) |
7fd59977 | 259 | { |
260 | // check that the item is defined | |
d93f7683 P |
261 | Standard_Size iBlock = theIndex / myBlockSize; |
262 | if ( iBlock >= myNbBlocks || ! myData[iBlock] ) | |
7fd59977 | 263 | return Standard_False; |
264 | ||
265 | Block aBlock (getBlock(myData[iBlock])); | |
d93f7683 | 266 | Standard_Size anInd = theIndex % myBlockSize; |
7fd59977 | 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 |