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