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
35OSDefineMetaClassAndStructors(OSOrderedSet, OSCollection)
36OSMetaClassDefineReservedUnused(OSOrderedSet, 0);
37OSMetaClassDefineReservedUnused(OSOrderedSet, 1);
38OSMetaClassDefineReservedUnused(OSOrderedSet, 2);
39OSMetaClassDefineReservedUnused(OSOrderedSet, 3);
40OSMetaClassDefineReservedUnused(OSOrderedSet, 4);
41OSMetaClassDefineReservedUnused(OSOrderedSet, 5);
42OSMetaClassDefineReservedUnused(OSOrderedSet, 6);
43OSMetaClassDefineReservedUnused(OSOrderedSet, 7);
44
45
46struct _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
54bool OSOrderedSet::
55initWithCapacity(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
83OSOrderedSet * OSOrderedSet::
84withCapacity(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
97void 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
110unsigned int OSOrderedSet::getCount() const { return count; }
111unsigned int OSOrderedSet::getCapacity() const { return capacity; }
112unsigned int OSOrderedSet::getCapacityIncrement() const
113 { return capacityIncrement; }
114unsigned int OSOrderedSet::setCapacityIncrement(unsigned int increment)
115{
116 capacityIncrement = (increment)? increment : 16;
117 return capacityIncrement;
118}
119
120unsigned 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
157void 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 */
170bool 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
199bool OSOrderedSet::setFirstObject(const OSMetaClassBase *anObject)
200{
201 return( setObject(0, anObject));
202}
203
204bool 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
213bool 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
225void 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
245bool OSOrderedSet::containsObject(const OSMetaClassBase *anObject) const
246{
247 return anObject && member(anObject);
248}
249
250bool 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 */
262OSObject *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
273OSObject *OSOrderedSet::getFirstObject() const
274{
275 if( count)
276 return( const_cast<OSObject *>((const OSObject *) array[0].obj) );
277 else
278 return( 0 );
279}
280
281OSObject *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
289SInt32 OSOrderedSet::orderObject( const OSMetaClassBase * anObject )
290{
291 return( ORDER( anObject, 0 ));
292}
293
294void *OSOrderedSet::getOrderingRef()
295{
296 return orderingRef;
297}
298
299bool 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
317bool 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
328unsigned int OSOrderedSet::iteratorSize() const
329{
330 return( sizeof(unsigned int));
331}
332
333bool OSOrderedSet::initIterator(void *inIterator) const
334{
335 unsigned int *iteratorP = (unsigned int *) inIterator;
336
337 *iteratorP = 0;
338 return true;
339}
340
341bool OSOrderedSet::
342getNextObjectForIterator(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
356unsigned 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
372OSCollection * 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
421abortCopy:
422 if (newSet)
423 newSet->release();
424
425 if (allocDict)
426 cycleDict->release();
427
428 return ret;
429}
430