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