1 | /* |
2 | * Copyright (c) 2000 Apple Computer, Inc. All rights reserved. |
3 | * |
4 | * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ |
5 | * |
6 | * This file contains Original Code and/or Modifications of Original Code |
7 | * as defined in and that are subject to the Apple Public Source License |
8 | * Version 2.0 (the 'License'). You may not use this file except in |
9 | * compliance with the License. The rights granted to you under the License |
10 | * may not be used to create, or enable the creation or redistribution of, |
11 | * unlawful or unlicensed copies of an Apple operating system, or to |
12 | * circumvent, violate, or enable the circumvention or violation of, any |
13 | * terms of an Apple operating system software license agreement. |
14 | * |
15 | * Please obtain a copy of the License at |
16 | * http://www.opensource.apple.com/apsl/ and read it before using this file. |
17 | * |
18 | * The Original Code and all software distributed under the License are |
19 | * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER |
20 | * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, |
21 | * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, |
22 | * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. |
23 | * Please see the License for the specific language governing rights and |
24 | * limitations under the License. |
25 | * |
26 | * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ |
27 | */ |
28 | |
29 | #include <libkern/c++/OSDictionary.h> |
30 | #include <libkern/c++/OSOrderedSet.h> |
31 | #include <libkern/c++/OSLib.h> |
32 | |
33 | #define super OSCollection |
34 | |
35 | OSDefineMetaClassAndStructors(OSOrderedSet, OSCollection) |
36 | OSMetaClassDefineReservedUnused(OSOrderedSet, 0); |
37 | OSMetaClassDefineReservedUnused(OSOrderedSet, 1); |
38 | OSMetaClassDefineReservedUnused(OSOrderedSet, 2); |
39 | OSMetaClassDefineReservedUnused(OSOrderedSet, 3); |
40 | OSMetaClassDefineReservedUnused(OSOrderedSet, 4); |
41 | OSMetaClassDefineReservedUnused(OSOrderedSet, 5); |
42 | OSMetaClassDefineReservedUnused(OSOrderedSet, 6); |
43 | OSMetaClassDefineReservedUnused(OSOrderedSet, 7); |
44 | |
45 | |
46 | struct _Element { |
47 | const OSMetaClassBase * obj; |
48 | // unsigned int pri; |
49 | }; |
50 | |
51 | #define EXT_CAST(obj) \ |
52 | reinterpret_cast<OSObject *>(const_cast<OSMetaClassBase *>(obj)) |
53 | |
54 | bool OSOrderedSet:: |
55 | initWithCapacity(unsigned int inCapacity, |
56 | OSOrderFunction inOrdering, void *inOrderingRef) |
57 | { |
58 | unsigned int size; |
59 | |
60 | if (!super::init()) |
61 | return false; |
62 | |
63 | if (inCapacity > (UINT_MAX / sizeof(_Element))) |
64 | return false; |
65 | |
66 | size = sizeof(_Element) * inCapacity; |
67 | array = (_Element *) kalloc_container(size); |
68 | if (!array) |
69 | return false; |
70 | |
71 | count = 0; |
72 | capacity = inCapacity; |
73 | capacityIncrement = (inCapacity)? inCapacity : 16; |
74 | ordering = inOrdering; |
75 | orderingRef = inOrderingRef; |
76 | |
77 | bzero(array, size); |
78 | OSCONTAINER_ACCUMSIZE(size); |
79 | |
80 | return true; |
81 | } |
82 | |
83 | OSOrderedSet * OSOrderedSet:: |
84 | withCapacity(unsigned int capacity, |
85 | OSOrderFunction ordering, void * orderingRef) |
86 | { |
87 | OSOrderedSet *me = new OSOrderedSet; |
88 | |
89 | if (me && !me->initWithCapacity(capacity, ordering, orderingRef)) { |
90 | me->release(); |
91 | me = 0; |
92 | } |
93 | |
94 | return me; |
95 | } |
96 | |
97 | void OSOrderedSet::free() |
98 | { |
99 | (void) super::setOptions(0, kImmutable); |
100 | flushCollection(); |
101 | |
102 | if (array) { |
103 | kfree(array, sizeof(_Element) * capacity); |
104 | OSCONTAINER_ACCUMSIZE( -(sizeof(_Element) * capacity) ); |
105 | } |
106 | |
107 | super::free(); |
108 | } |
109 | |
110 | unsigned int OSOrderedSet::getCount() const { return count; } |
111 | unsigned int OSOrderedSet::getCapacity() const { return capacity; } |
112 | unsigned int OSOrderedSet::getCapacityIncrement() const |
113 | { return capacityIncrement; } |
114 | unsigned int OSOrderedSet::setCapacityIncrement(unsigned int increment) |
115 | { |
116 | capacityIncrement = (increment)? increment : 16; |
117 | return capacityIncrement; |
118 | } |
119 | |
120 | unsigned int OSOrderedSet::ensureCapacity(unsigned int newCapacity) |
121 | { |
122 | _Element *newArray; |
123 | unsigned int finalCapacity; |
124 | vm_size_t oldSize, newSize; |
125 | |
126 | if (newCapacity <= capacity) |
127 | return capacity; |
128 | |
129 | // round up |
130 | finalCapacity = (((newCapacity - 1) / capacityIncrement) + 1) |
131 | * capacityIncrement; |
132 | if ((finalCapacity < newCapacity) || |
133 | (finalCapacity > (UINT_MAX / sizeof(_Element)))) { |
134 | return capacity; |
135 | } |
136 | newSize = sizeof(_Element) * finalCapacity; |
137 | |
138 | newArray = (_Element *) kallocp_container(&newSize); |
139 | if (newArray) { |
140 | // use all of the actual allocation size |
141 | finalCapacity = newSize / sizeof(_Element); |
142 | |
143 | oldSize = sizeof(_Element) * capacity; |
144 | |
145 | OSCONTAINER_ACCUMSIZE(((size_t)newSize) - ((size_t)oldSize)); |
146 | |
147 | bcopy(array, newArray, oldSize); |
148 | bzero(&newArray[capacity], newSize - oldSize); |
149 | kfree(array, oldSize); |
150 | array = newArray; |
151 | capacity = finalCapacity; |
152 | } |
153 | |
154 | return capacity; |
155 | } |
156 | |
157 | void OSOrderedSet::flushCollection() |
158 | { |
159 | unsigned int i; |
160 | |
161 | haveUpdated(); |
162 | |
163 | for (i = 0; i < count; i++) |
164 | array[i].obj->taggedRelease(OSTypeID(OSCollection)); |
165 | |
166 | count = 0; |
167 | } |
168 | |
169 | /* internal */ |
170 | bool OSOrderedSet::setObject(unsigned int index, const OSMetaClassBase *anObject) |
171 | { |
172 | unsigned int i; |
173 | unsigned int newCount = count + 1; |
174 | |
175 | if ((index > count) || !anObject) |
176 | return false; |
177 | |
178 | if (containsObject(anObject)) |
179 | return false; |
180 | |
181 | // do we need more space? |
182 | if (newCount > capacity && newCount > ensureCapacity(newCount)) |
183 | return false; |
184 | |
185 | haveUpdated(); |
186 | if (index != count) { |
187 | for (i = count; i > index; i--) |
188 | array[i] = array[i-1]; |
189 | } |
190 | array[index].obj = anObject; |
191 | // array[index].pri = pri; |
192 | anObject->taggedRetain(OSTypeID(OSCollection)); |
193 | count++; |
194 | |
195 | return true; |
196 | } |
197 | |
198 | |
199 | bool OSOrderedSet::setFirstObject(const OSMetaClassBase *anObject) |
200 | { |
201 | return( setObject(0, anObject)); |
202 | } |
203 | |
204 | bool OSOrderedSet::setLastObject(const OSMetaClassBase *anObject) |
205 | { |
206 | return( setObject( count, anObject)); |
207 | } |
208 | |
209 | |
210 | #define ORDER(obj1,obj2) \ |
211 | (ordering ? ((*ordering)( (const OSObject *) obj1, (const OSObject *) obj2, orderingRef)) : 0) |
212 | |
213 | bool OSOrderedSet::setObject(const OSMetaClassBase *anObject ) |
214 | { |
215 | unsigned int i; |
216 | |
217 | // queue it behind those with same priority |
218 | for( i = 0; |
219 | (i < count) && (ORDER(array[i].obj, anObject) >= 0); |
220 | i++ ) {} |
221 | |
222 | return( setObject(i, anObject)); |
223 | } |
224 | |
225 | void OSOrderedSet::removeObject(const OSMetaClassBase *anObject) |
226 | { |
227 | bool deleted = false; |
228 | unsigned int i; |
229 | |
230 | for (i = 0; i < count; i++) { |
231 | |
232 | if (deleted) |
233 | array[i-1] = array[i]; |
234 | else if (array[i].obj == anObject) { |
235 | deleted = true; |
236 | haveUpdated(); // Pity we can't flush the log |
237 | array[i].obj->taggedRelease(OSTypeID(OSCollection)); |
238 | } |
239 | } |
240 | |
241 | if (deleted) |
242 | count--; |
243 | } |
244 | |
245 | bool OSOrderedSet::containsObject(const OSMetaClassBase *anObject) const |
246 | { |
247 | return anObject && member(anObject); |
248 | } |
249 | |
250 | bool OSOrderedSet::member(const OSMetaClassBase *anObject) const |
251 | { |
252 | unsigned int i; |
253 | |
254 | for( i = 0; |
255 | (i < count) && (array[i].obj != anObject); |
256 | i++ ) {} |
257 | |
258 | return( i < count); |
259 | } |
260 | |
261 | /* internal */ |
262 | OSObject *OSOrderedSet::getObject( unsigned int index ) const |
263 | { |
264 | if (index >= count) |
265 | return 0; |
266 | |
267 | // if( pri) |
268 | // *pri = array[index].pri; |
269 | |
270 | return( const_cast<OSObject *>((const OSObject *) array[index].obj) ); |
271 | } |
272 | |
273 | OSObject *OSOrderedSet::getFirstObject() const |
274 | { |
275 | if( count) |
276 | return( const_cast<OSObject *>((const OSObject *) array[0].obj) ); |
277 | else |
278 | return( 0 ); |
279 | } |
280 | |
281 | OSObject *OSOrderedSet::getLastObject() const |
282 | { |
283 | if( count) |
284 | return( const_cast<OSObject *>((const OSObject *) array[count-1].obj) ); |
285 | else |
286 | return( 0 ); |
287 | } |
288 | |
289 | SInt32 OSOrderedSet::orderObject( const OSMetaClassBase * anObject ) |
290 | { |
291 | return( ORDER( anObject, 0 )); |
292 | } |
293 | |
294 | void *OSOrderedSet::getOrderingRef() |
295 | { |
296 | return orderingRef; |
297 | } |
298 | |
299 | bool OSOrderedSet::isEqualTo(const OSOrderedSet *anOrderedSet) const |
300 | { |
301 | unsigned int i; |
302 | |
303 | if ( this == anOrderedSet ) |
304 | return true; |
305 | |
306 | if ( count != anOrderedSet->getCount() ) |
307 | return false; |
308 | |
309 | for ( i = 0; i < count; i++ ) { |
310 | if ( !array[i].obj->isEqualTo(anOrderedSet->getObject(i)) ) |
311 | return false; |
312 | } |
313 | |
314 | return true; |
315 | } |
316 | |
317 | bool OSOrderedSet::isEqualTo(const OSMetaClassBase *anObject) const |
318 | { |
319 | OSOrderedSet *oSet; |
320 | |
321 | oSet = OSDynamicCast(OSOrderedSet, anObject); |
322 | if ( oSet ) |
323 | return isEqualTo(oSet); |
324 | else |
325 | return false; |
326 | } |
327 | |
328 | unsigned int OSOrderedSet::iteratorSize() const |
329 | { |
330 | return( sizeof(unsigned int)); |
331 | } |
332 | |
333 | bool OSOrderedSet::initIterator(void *inIterator) const |
334 | { |
335 | unsigned int *iteratorP = (unsigned int *) inIterator; |
336 | |
337 | *iteratorP = 0; |
338 | return true; |
339 | } |
340 | |
341 | bool OSOrderedSet:: |
342 | getNextObjectForIterator(void *inIterator, OSObject **ret) const |
343 | { |
344 | unsigned int *iteratorP = (unsigned int *) inIterator; |
345 | unsigned int index = (*iteratorP)++; |
346 | |
347 | if (index < count) |
348 | *ret = const_cast<OSObject *>((const OSObject *) array[index].obj); |
349 | else |
350 | *ret = 0; |
351 | |
352 | return (*ret != 0); |
353 | } |
354 | |
355 | |
356 | unsigned OSOrderedSet::setOptions(unsigned options, unsigned mask, void *) |
357 | { |
358 | unsigned old = super::setOptions(options, mask); |
359 | if ((old ^ options) & mask) { |
360 | |
361 | // Value changed need to recurse over all of the child collections |
362 | for ( unsigned i = 0; i < count; i++ ) { |
363 | OSCollection *coll = OSDynamicCast(OSCollection, array[i].obj); |
364 | if (coll) |
365 | coll->setOptions(options, mask); |
366 | } |
367 | } |
368 | |
369 | return old; |
370 | } |
371 | |
372 | OSCollection * OSOrderedSet::copyCollection(OSDictionary *cycleDict) |
373 | { |
374 | bool allocDict = !cycleDict; |
375 | OSCollection *ret = 0; |
376 | OSOrderedSet *newSet = 0; |
377 | |
378 | if (allocDict) { |
379 | cycleDict = OSDictionary::withCapacity(16); |
380 | if (!cycleDict) |
381 | return 0; |
382 | } |
383 | |
384 | do { |
385 | // Check for a cycle |
386 | ret = super::copyCollection(cycleDict); |
387 | if (ret) |
388 | continue; |
389 | |
390 | // Duplicate the set with no contents |
391 | newSet = OSOrderedSet::withCapacity(capacity, ordering, orderingRef); |
392 | if (!newSet) |
393 | continue; |
394 | |
395 | // Insert object into cycle Dictionary |
396 | cycleDict->setObject((const OSSymbol *) this, newSet); |
397 | |
398 | newSet->capacityIncrement = capacityIncrement; |
399 | |
400 | // Now copy over the contents to the new duplicate |
401 | for (unsigned int i = 0; i < count; i++) { |
402 | OSObject *obj = EXT_CAST(array[i].obj); |
403 | OSCollection *coll = OSDynamicCast(OSCollection, obj); |
404 | if (coll) { |
405 | OSCollection *newColl = coll->copyCollection(cycleDict); |
406 | if (newColl) { |
407 | obj = newColl; // Rely on cycleDict ref for a bit |
408 | newColl->release(); |
409 | } |
410 | else |
411 | goto abortCopy; |
412 | }; |
413 | newSet->setLastObject(obj); |
414 | }; |
415 | |
416 | ret = newSet; |
417 | newSet = 0; |
418 | |
419 | } while (false); |
420 | |
421 | abortCopy: |
422 | if (newSet) |
423 | newSet->release(); |
424 | |
425 | if (allocDict) |
426 | cycleDict->release(); |
427 | |
428 | return ret; |
429 | } |
430 | |