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#if OSALLOCDEBUG
46extern "C" {
47    extern int debug_container_malloc_size;
48};
49#define ACCUMSIZE(s) do { debug_container_malloc_size += (s); } while(0)
50#else
51#define ACCUMSIZE(s)
52#endif
53
54struct _Element {
55    const OSMetaClassBase *		obj;
56//    unsigned int	pri;
57};
58
59#define EXT_CAST(obj) \
60    reinterpret_cast<OSObject *>(const_cast<OSMetaClassBase *>(obj))
61
62bool OSOrderedSet::
63initWithCapacity(unsigned int inCapacity,
64                 OSOrderFunction inOrdering, void *inOrderingRef)
65{
66    unsigned int size;
67
68    if (!super::init())
69        return false;
70
71    if (inCapacity > (UINT_MAX / sizeof(_Element)))
72        return false;
73
74    size = sizeof(_Element) * inCapacity;
75    array = (_Element *) kalloc(size);
76    if (!array)
77        return false;
78
79    count = 0;
80    capacity = inCapacity;
81    capacityIncrement = (inCapacity)? inCapacity : 16;
82    ordering = inOrdering;
83    orderingRef = inOrderingRef;
84
85    bzero(array, size);
86    ACCUMSIZE(size);
87
88    return this;
89}
90
91OSOrderedSet * OSOrderedSet::
92withCapacity(unsigned int capacity,
93             OSOrderFunction ordering, void * orderingRef)
94{
95    OSOrderedSet *me = new OSOrderedSet;
96
97    if (me && !me->initWithCapacity(capacity, ordering, orderingRef)) {
98        me->release();
99	me = 0;
100    }
101
102    return me;
103}
104
105void OSOrderedSet::free()
106{
107    (void) super::setOptions(0, kImmutable);
108    flushCollection();
109
110    if (array) {
111        kfree(array, sizeof(_Element) * capacity);
112        ACCUMSIZE( -(sizeof(_Element) * capacity) );
113    }
114
115    super::free();
116}
117
118unsigned int OSOrderedSet::getCount() const { return count; }
119unsigned int OSOrderedSet::getCapacity() const { return capacity; }
120unsigned int OSOrderedSet::getCapacityIncrement() const
121	{ return capacityIncrement; }
122unsigned int OSOrderedSet::setCapacityIncrement(unsigned int increment)
123{
124    capacityIncrement = (increment)? increment : 16;
125    return capacityIncrement;
126}
127
128unsigned int OSOrderedSet::ensureCapacity(unsigned int newCapacity)
129{
130    _Element *newArray;
131    unsigned int finalCapacity, oldSize, newSize;
132
133    if (newCapacity <= capacity)
134        return capacity;
135
136    // round up
137    finalCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
138                * capacityIncrement;
139    if ((finalCapacity < newCapacity) ||
140        (finalCapacity > (UINT_MAX / sizeof(_Element)))) {
141        return capacity;
142    }
143    newSize = sizeof(_Element) * finalCapacity;
144
145    newArray = (_Element *) kalloc(newSize);
146    if (newArray) {
147        oldSize = sizeof(_Element) * capacity;
148
149        ACCUMSIZE(newSize - oldSize);
150
151        bcopy(array, newArray, oldSize);
152        bzero(&newArray[capacity], newSize - oldSize);
153        kfree(array, oldSize);
154        array = newArray;
155        capacity = finalCapacity;
156    }
157
158    return capacity;
159}
160
161void OSOrderedSet::flushCollection()
162{
163    unsigned int i;
164
165    haveUpdated();
166
167    for (i = 0; i < count; i++)
168        array[i].obj->taggedRelease(OSTypeID(OSCollection));
169
170    count = 0;
171}
172
173/* internal */
174bool OSOrderedSet::setObject(unsigned int index, const OSMetaClassBase *anObject)
175{
176    unsigned int i;
177    unsigned int newCount = count + 1;
178
179    if ((index > count) || !anObject)
180        return false;
181
182    if (containsObject(anObject))
183        return false;
184
185    // do we need more space?
186    if (newCount > capacity && newCount > ensureCapacity(newCount))
187        return false;
188
189    haveUpdated();
190    if (index != count) {
191        for (i = count; i > index; i--)
192            array[i] = array[i-1];
193    }
194    array[index].obj = anObject;
195//    array[index].pri = pri;
196    anObject->taggedRetain(OSTypeID(OSCollection));
197    count++;
198
199    return true;
200}
201
202
203bool OSOrderedSet::setFirstObject(const OSMetaClassBase *anObject)
204{
205    return( setObject(0, anObject));
206}
207
208bool OSOrderedSet::setLastObject(const OSMetaClassBase *anObject)
209{
210    return( setObject( count, anObject));
211}
212
213
214#define ORDER(obj1,obj2) \
215    (ordering ? ((*ordering)( (const OSObject *) obj1, (const OSObject *) obj2, orderingRef)) : 0)
216
217bool OSOrderedSet::setObject(const OSMetaClassBase *anObject )
218{
219    unsigned int i;
220
221    // queue it behind those with same priority
222    for( i = 0;
223	(i < count) && (ORDER(array[i].obj, anObject) >= 0);
224	i++ ) {}
225
226    return( setObject(i, anObject));
227}
228
229void OSOrderedSet::removeObject(const OSMetaClassBase *anObject)
230{
231    bool		deleted = false;
232    unsigned int 	i;
233
234    for (i = 0; i < count; i++) {
235
236        if (deleted)
237            array[i-1] = array[i];
238        else if (array[i].obj == anObject) {
239            deleted = true;
240	    haveUpdated();	// Pity we can't flush the log
241            array[i].obj->taggedRelease(OSTypeID(OSCollection));
242        }
243    }
244
245    if (deleted)
246	count--;
247}
248
249bool OSOrderedSet::containsObject(const OSMetaClassBase *anObject) const
250{
251    return anObject && member(anObject);
252}
253
254bool OSOrderedSet::member(const OSMetaClassBase *anObject) const
255{
256    unsigned int i;
257
258    for( i = 0;
259	(i < count) && (array[i].obj != anObject);
260	i++ ) {}
261
262    return( i < count);
263}
264
265/* internal */
266OSObject *OSOrderedSet::getObject( unsigned int index ) const
267{
268    if (index >= count)
269        return 0;
270
271//    if( pri)
272//	*pri = array[index].pri;
273
274    return( const_cast<OSObject *>((const OSObject *) array[index].obj) );
275}
276
277OSObject *OSOrderedSet::getFirstObject() const
278{
279    if( count)
280        return( const_cast<OSObject *>((const OSObject *) array[0].obj) );
281    else
282	return( 0 );
283}
284
285OSObject *OSOrderedSet::getLastObject() const
286{
287    if( count)
288        return( const_cast<OSObject *>((const OSObject *) array[count-1].obj) );
289    else
290	return( 0 );
291}
292
293SInt32 OSOrderedSet::orderObject( const OSMetaClassBase * anObject )
294{
295    return( ORDER( anObject, 0 ));
296}
297
298void *OSOrderedSet::getOrderingRef()
299{
300    return orderingRef;
301}
302
303bool OSOrderedSet::isEqualTo(const OSOrderedSet *anOrderedSet) const
304{
305    unsigned int i;
306
307    if ( this == anOrderedSet )
308        return true;
309
310    if ( count != anOrderedSet->getCount() )
311        return false;
312
313    for ( i = 0; i < count; i++ ) {
314        if ( !array[i].obj->isEqualTo(anOrderedSet->getObject(i)) )
315            return false;
316    }
317
318    return true;
319}
320
321bool OSOrderedSet::isEqualTo(const OSMetaClassBase *anObject) const
322{
323    OSOrderedSet *oSet;
324
325    oSet = OSDynamicCast(OSOrderedSet, anObject);
326    if ( oSet )
327        return isEqualTo(oSet);
328    else
329        return false;
330}
331
332unsigned int OSOrderedSet::iteratorSize() const
333{
334    return( sizeof(unsigned int));
335}
336
337bool OSOrderedSet::initIterator(void *inIterator) const
338{
339    unsigned int *iteratorP = (unsigned int *) inIterator;
340
341    *iteratorP = 0;
342    return true;
343}
344
345bool OSOrderedSet::
346getNextObjectForIterator(void *inIterator, OSObject **ret) const
347{
348    unsigned int *iteratorP = (unsigned int *) inIterator;
349    unsigned int index = (*iteratorP)++;
350
351    if (index < count)
352        *ret = const_cast<OSObject *>((const OSObject *) array[index].obj);
353    else
354        *ret = 0;
355
356    return (*ret != 0);
357}
358
359
360unsigned OSOrderedSet::setOptions(unsigned options, unsigned mask, void *)
361{
362    unsigned old = super::setOptions(options, mask);
363    if ((old ^ options) & mask) {
364
365	// Value changed need to recurse over all of the child collections
366	for ( unsigned i = 0; i < count; i++ ) {
367	    OSCollection *coll = OSDynamicCast(OSCollection, array[i].obj);
368	    if (coll)
369		coll->setOptions(options, mask);
370	}
371    }
372
373    return old;
374}
375
376OSCollection * OSOrderedSet::copyCollection(OSDictionary *cycleDict)
377{
378    bool allocDict = !cycleDict;
379    OSCollection *ret = 0;
380    OSOrderedSet *newSet = 0;
381
382    if (allocDict) {
383	cycleDict = OSDictionary::withCapacity(16);
384	if (!cycleDict)
385	    return 0;
386    }
387
388    do {
389	// Check for a cycle
390	ret = super::copyCollection(cycleDict);
391	if (ret)
392	    continue;
393
394	// Duplicate the set with no contents
395	newSet = OSOrderedSet::withCapacity(capacity, ordering, orderingRef);
396	if (!newSet)
397	    continue;
398
399	// Insert object into cycle Dictionary
400	cycleDict->setObject((const OSSymbol *) this, newSet);
401
402	newSet->capacityIncrement = capacityIncrement;
403
404	// Now copy over the contents to the new duplicate
405	for (unsigned int i = 0; i < count; i++) {
406	    OSObject *obj = EXT_CAST(array[i].obj);
407	    OSCollection *coll = OSDynamicCast(OSCollection, obj);
408	    if (coll) {
409		OSCollection *newColl = coll->copyCollection(cycleDict);
410		if (newColl) {
411		    obj = newColl;	// Rely on cycleDict ref for a bit
412		    newColl->release();
413		}
414		else
415		    goto abortCopy;
416	    };
417	    newSet->setLastObject(obj);
418	};
419
420	ret = newSet;
421	newSet = 0;
422
423    } while (false);
424
425abortCopy:
426    if (newSet)
427	newSet->release();
428
429    if (allocDict)
430	cycleDict->release();
431
432    return ret;
433}
434