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/* IOSet.m created by rsulack on Thu 11-Jun-1998 */
29
30#include <libkern/c++/OSDictionary.h>
31#include <libkern/c++/OSArray.h>
32#include <libkern/c++/OSSerialize.h>
33#include <libkern/c++/OSSet.h>
34
35#define super OSCollection
36
37OSDefineMetaClassAndStructors(OSSet, OSCollection)
38OSMetaClassDefineReservedUnused(OSSet, 0);
39OSMetaClassDefineReservedUnused(OSSet, 1);
40OSMetaClassDefineReservedUnused(OSSet, 2);
41OSMetaClassDefineReservedUnused(OSSet, 3);
42OSMetaClassDefineReservedUnused(OSSet, 4);
43OSMetaClassDefineReservedUnused(OSSet, 5);
44OSMetaClassDefineReservedUnused(OSSet, 6);
45OSMetaClassDefineReservedUnused(OSSet, 7);
46
47#define EXT_CAST(obj) \
48    reinterpret_cast<OSObject *>(const_cast<OSMetaClassBase *>(obj))
49
50bool OSSet::initWithCapacity(unsigned int inCapacity)
51{
52    if ( !super::init() )
53        return false;
54
55    members = OSArray::withCapacity(inCapacity);
56    if (!members)
57        return false;
58
59    return true;
60}
61
62bool OSSet::initWithObjects(const OSObject *inObjects[],
63                              unsigned int inCount,
64                              unsigned int inCapacity)
65{
66    unsigned int capacity = inCount;
67
68    if ( inCapacity ) {
69        if ( inCount > inCapacity )
70            return false;
71
72        capacity = inCapacity;
73    }
74
75    if (!inObjects || !initWithCapacity(capacity))
76        return false;
77
78    for ( unsigned int i = 0; i < inCount; i++ ) {
79        if (members->getCount() < inCapacity)
80            setObject(inObjects[i]);
81        else
82            return false;
83    }
84
85    return true;
86}
87
88bool OSSet::initWithArray(const OSArray *inArray,
89                          unsigned int inCapacity)
90{
91    if ( !inArray )
92        return false;
93
94    return initWithObjects((const OSObject **) inArray->array,
95                           inArray->count, inCapacity);
96}
97
98bool OSSet::initWithSet(const OSSet *inSet,
99                        unsigned int inCapacity)
100{
101    return initWithArray(inSet->members, inCapacity);
102}
103
104OSSet *OSSet::withCapacity(unsigned int capacity)
105{
106    OSSet *me = new OSSet;
107
108    if (me && !me->initWithCapacity(capacity)) {
109        me->release();
110        return 0;
111    }
112
113    return me;
114}
115
116OSSet *OSSet::withObjects(const OSObject *objects[],
117                          unsigned int count,
118                          unsigned int capacity)
119{
120    OSSet *me = new OSSet;
121
122    if (me && !me->initWithObjects(objects, count, capacity)) {
123        me->release();
124        return 0;
125    }
126
127    return me;
128}
129
130OSSet *OSSet::withArray(const OSArray *array,
131                        unsigned int capacity)
132{
133    OSSet *me = new OSSet;
134
135    if (me && !me->initWithArray(array, capacity)) {
136        me->release();
137        return 0;
138    }
139
140    return me;
141}
142
143OSSet *OSSet::withSet(const OSSet *set,
144                      unsigned int capacity)
145{
146    OSSet *me = new OSSet;
147
148    if (me && !me->initWithSet(set, capacity)) {
149        me->release();
150        return 0;
151    }
152
153    return me;
154}
155
156void OSSet::free()
157{
158    (void) members->super::setOptions(0, kImmutable);
159    if (members)
160        members->release();
161
162    super::free();
163}
164
165unsigned int OSSet::getCount() const
166{
167    return members->count;
168}
169
170unsigned int OSSet::getCapacity() const
171{
172    return members->capacity;
173}
174
175unsigned int OSSet::getCapacityIncrement() const
176{
177    return members->capacityIncrement;
178}
179
180unsigned int OSSet::setCapacityIncrement(unsigned int increment)
181{
182    return members->setCapacityIncrement(increment);
183}
184
185unsigned int OSSet::ensureCapacity(unsigned int newCapacity)
186{
187    return members->ensureCapacity(newCapacity);
188}
189
190void OSSet::flushCollection()
191{
192    haveUpdated();
193    members->flushCollection();
194}
195
196bool OSSet::setObject(const OSMetaClassBase *anObject)
197{
198    if (containsObject(anObject))
199        return false;
200    else {
201        haveUpdated();
202        return members->setObject(anObject);
203    }
204}
205
206bool OSSet::merge(const OSArray *array)
207{
208    const OSMetaClassBase *anObject;
209    bool retVal = false;
210
211    for (int i = 0; (anObject = array->getObject(i)); i++)
212        if (setObject(anObject))
213            retVal = true;
214
215    return retVal;
216}
217
218bool OSSet::merge(const OSSet *set)
219{
220    return merge(set->members);
221}
222
223void OSSet::removeObject(const OSMetaClassBase *anObject)
224{
225    const OSMetaClassBase *probeObject;
226
227    for (int i = 0; (probeObject = members->getObject(i)); i++)
228        if (probeObject == anObject) {
229            haveUpdated();
230            members->removeObject(i);
231            return;
232        }
233}
234
235
236bool OSSet::containsObject(const OSMetaClassBase *anObject) const
237{
238    return anObject && member(anObject);
239}
240
241bool OSSet::member(const OSMetaClassBase *anObject) const
242{
243    OSMetaClassBase *probeObject;
244
245    for (int i = 0; (probeObject = members->getObject(i)); i++)
246        if (probeObject == anObject)
247            return true;
248
249    return false;
250}
251
252OSObject *OSSet::getAnyObject() const
253{
254    return members->getObject(0);
255}
256
257bool OSSet::isEqualTo(const OSSet *aSet) const
258{
259    unsigned int count;
260    unsigned int i;
261    const OSMetaClassBase *obj1;
262    const OSMetaClassBase *obj2;
263
264    if ( this == aSet )
265        return true;
266
267    count = members->count;
268    if ( count != aSet->getCount() )
269        return false;
270
271    for ( i = 0; i < count; i++ ) {
272        obj1 = aSet->members->getObject(i);
273        obj2 = members->getObject(i);
274        if ( !obj1 || !obj2 )
275                return false;
276
277        if ( !obj1->isEqualTo(obj2) )
278            return false;
279    }
280
281    return true;
282}
283
284bool OSSet::isEqualTo(const OSMetaClassBase *anObject) const
285{
286    OSSet *otherSet;
287
288    otherSet = OSDynamicCast(OSSet, anObject);
289    if ( otherSet )
290        return isEqualTo(otherSet);
291    else
292        return false;
293}
294
295unsigned int OSSet::iteratorSize() const
296{
297    return sizeof(unsigned int);
298}
299
300bool OSSet::initIterator(void *inIterator) const
301{
302    unsigned int *iteratorP = (unsigned int *) inIterator;
303
304    *iteratorP = 0;
305    return true;
306}
307
308bool OSSet::getNextObjectForIterator(void *inIterator, OSObject **ret) const
309{
310    unsigned int *iteratorP = (unsigned int *) inIterator;
311    unsigned int index = (*iteratorP)++;
312
313    if (index < members->count)
314        *ret = members->getObject(index);
315    else
316        *ret = 0;
317
318    return (*ret != 0);
319}
320
321bool OSSet::serialize(OSSerialize *s) const
322{
323    const OSMetaClassBase *o;
324
325    if (s->previouslySerialized(this)) return true;
326
327    if (!s->addXMLStartTag(this, "set")) return false;
328
329    for (int i = 0; (o = members->getObject(i)); i++) {
330        if (!o->serialize(s)) return false;
331    }
332
333    return s->addXMLEndTag("set");
334}
335
336unsigned OSSet::setOptions(unsigned options, unsigned mask, void *)
337{
338    unsigned old = super::setOptions(options, mask);
339    if ((old ^ options) & mask)
340	members->setOptions(options, mask);
341
342    return old;
343}
344
345OSCollection * OSSet::copyCollection(OSDictionary *cycleDict)
346{
347    bool allocDict = !cycleDict;
348    OSCollection *ret = 0;
349    OSSet *newSet = 0;
350
351    if (allocDict) {
352	cycleDict = OSDictionary::withCapacity(16);
353	if (!cycleDict)
354	    return 0;
355    }
356
357    do {
358	// Check for a cycle
359	ret = super::copyCollection(cycleDict);
360	if (ret)
361	    continue;	// Found it
362
363	newSet = OSSet::withCapacity(members->capacity);
364	if (!newSet)
365	    continue;	// Couldn't create new set abort
366
367	// Insert object into cycle Dictionary
368	cycleDict->setObject((const OSSymbol *) this, newSet);
369
370	OSArray *newMembers = newSet->members;
371	newMembers->capacityIncrement = members->capacityIncrement;
372
373	// Now copy over the contents into the new duplicate
374	for (unsigned int i = 0; i < members->count; i++) {
375	    OSObject *obj = EXT_CAST(members->array[i]);
376	    OSCollection *coll = OSDynamicCast(OSCollection, obj);
377	    if (coll) {
378		OSCollection *newColl = coll->copyCollection(cycleDict);
379		if (newColl) {
380		    obj = newColl;	// Rely on cycleDict ref for a bit
381		    newColl->release();
382		}
383		else
384		    goto abortCopy;
385	    };
386	    newMembers->setObject(obj);
387	};
388
389	ret = newSet;
390	newSet = 0;
391
392    } while(false);
393
394abortCopy:
395    if (newSet)
396	newSet->release();
397
398    if (allocDict)
399	cycleDict->release();
400
401    return ret;
402}
403