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 if (members) {
160 (void) members->super::setOptions(0, kImmutable);
161 members->release();
162 }
163
164 super::free();
165}
166
167unsigned int OSSet::getCount() const
168{
169 return members->count;
170}
171
172unsigned int OSSet::getCapacity() const
173{
174 return members->capacity;
175}
176
177unsigned int OSSet::getCapacityIncrement() const
178{
179 return members->capacityIncrement;
180}
181
182unsigned int OSSet::setCapacityIncrement(unsigned int increment)
183{
184 return members->setCapacityIncrement(increment);
185}
186
187unsigned int OSSet::ensureCapacity(unsigned int newCapacity)
188{
189 return members->ensureCapacity(newCapacity);
190}
191
192void OSSet::flushCollection()
193{
194 haveUpdated();
195 members->flushCollection();
196}
197
198bool OSSet::setObject(const OSMetaClassBase *anObject)
199{
200 if (containsObject(anObject)) {
201 return false;
202 } else {
203 haveUpdated();
204 return members->setObject(anObject);
205 }
206}
207
208bool OSSet::merge(const OSArray * array)
209{
210 const OSMetaClassBase * anObject = 0;
211 bool result = true;
212
213 for (int i = 0; (anObject = array->getObject(i)); i++) {
214
215 /* setObject() returns false if the object is already in the set,
216 * so we have to check beforehand here with containsObject().
217 */
218 if (containsObject(anObject)) {
219 continue;
220 }
221 if (!setObject(anObject)) {
222 result = false;
223 }
224 }
225
226 return result;
227}
228
229bool OSSet::merge(const OSSet * set)
230{
231 return merge(set->members);
232}
233
234void OSSet::removeObject(const OSMetaClassBase *anObject)
235{
236 const OSMetaClassBase *probeObject;
237
238 for (int i = 0; (probeObject = members->getObject(i)); i++)
239 if (probeObject == anObject) {
240 haveUpdated();
241 members->removeObject(i);
242 return;
243 }
244}
245
246
247bool OSSet::containsObject(const OSMetaClassBase *anObject) const
248{
249 return anObject && member(anObject);
250}
251
252bool OSSet::member(const OSMetaClassBase *anObject) const
253{
254 OSMetaClassBase *probeObject;
255
256 for (int i = 0; (probeObject = members->getObject(i)); i++)
257 if (probeObject == anObject)
258 return true;
259
260 return false;
261}
262
263OSObject *OSSet::getAnyObject() const
264{
265 return members->getObject(0);
266}
267
268bool OSSet::isEqualTo(const OSSet *aSet) const
269{
270 unsigned int count;
271 unsigned int i;
272 const OSMetaClassBase *obj1;
273 const OSMetaClassBase *obj2;
274
275 if ( this == aSet )
276 return true;
277
278 count = members->count;
279 if ( count != aSet->getCount() )
280 return false;
281
282 for ( i = 0; i < count; i++ ) {
283 obj1 = aSet->members->getObject(i);
284 if (containsObject(obj1))
285 continue;
286 obj2 = members->getObject(i);
287 if ( !obj1 || !obj2 )
288 return false;
289
290 if ( !obj1->isEqualTo(obj2) )
291 return false;
292 }
293
294 return true;
295}
296
297bool OSSet::isEqualTo(const OSMetaClassBase *anObject) const
298{
299 OSSet *otherSet;
300
301 otherSet = OSDynamicCast(OSSet, anObject);
302 if ( otherSet )
303 return isEqualTo(otherSet);
304 else
305 return false;
306}
307
308unsigned int OSSet::iteratorSize() const
309{
310 return sizeof(unsigned int);
311}
312
313bool OSSet::initIterator(void *inIterator) const
314{
315 unsigned int *iteratorP = (unsigned int *) inIterator;
316
317 *iteratorP = 0;
318 return true;
319}
320
321bool OSSet::getNextObjectForIterator(void *inIterator, OSObject **ret) const
322{
323 unsigned int *iteratorP = (unsigned int *) inIterator;
324 unsigned int index = (*iteratorP)++;
325
326 if (index < members->count)
327 *ret = members->getObject(index);
328 else
329 *ret = 0;
330
331 return (*ret != 0);
332}
333
334bool OSSet::serialize(OSSerialize *s) const
335{
336 const OSMetaClassBase *o;
337
338 if (s->previouslySerialized(this)) return true;
339
340 if (!s->addXMLStartTag(this, "set")) return false;
341
342 for (int i = 0; (o = members->getObject(i)); i++) {
343 if (!o->serialize(s)) return false;
344 }
345
346 return s->addXMLEndTag("set");
347}
348
349unsigned OSSet::setOptions(unsigned options, unsigned mask, void *)
350{
351 unsigned old = super::setOptions(options, mask);
352 if ((old ^ options) & mask)
353 members->setOptions(options, mask);
354
355 return old;
356}
357
358OSCollection * OSSet::copyCollection(OSDictionary *cycleDict)
359{
360 bool allocDict = !cycleDict;
361 OSCollection *ret = 0;
362 OSSet *newSet = 0;
363
364 if (allocDict) {
365 cycleDict = OSDictionary::withCapacity(16);
366 if (!cycleDict)
367 return 0;
368 }
369
370 do {
371 // Check for a cycle
372 ret = super::copyCollection(cycleDict);
373 if (ret)
374 continue; // Found it
375
376 newSet = OSSet::withCapacity(members->capacity);
377 if (!newSet)
378 continue; // Couldn't create new set abort
379
380 // Insert object into cycle Dictionary
381 cycleDict->setObject((const OSSymbol *) this, newSet);
382
383 OSArray *newMembers = newSet->members;
384 newMembers->capacityIncrement = members->capacityIncrement;
385
386 // Now copy over the contents into the new duplicate
387 for (unsigned int i = 0; i < members->count; i++) {
388 OSObject *obj = EXT_CAST(members->array[i]);
389 OSCollection *coll = OSDynamicCast(OSCollection, obj);
390 if (coll) {
391 OSCollection *newColl = coll->copyCollection(cycleDict);
392 if (newColl) {
393 obj = newColl; // Rely on cycleDict ref for a bit
394 newColl->release();
395 }
396 else
397 goto abortCopy;
398 };
399 newMembers->setObject(obj);
400 };
401
402 ret = newSet;
403 newSet = 0;
404
405 } while(false);
406
407abortCopy:
408 if (newSet)
409 newSet->release();
410
411 if (allocDict)
412 cycleDict->release();
413
414 return ret;
415}
416