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