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 | |
42 | OSDefineMetaClassAndStructorsWithZone(OSSet, OSCollection, |
43 | ZC_ZFREE_CLEARMEM) |
44 | OSMetaClassDefineReservedUnused(OSSet, 0); |
45 | OSMetaClassDefineReservedUnused(OSSet, 1); |
46 | OSMetaClassDefineReservedUnused(OSSet, 2); |
47 | OSMetaClassDefineReservedUnused(OSSet, 3); |
48 | OSMetaClassDefineReservedUnused(OSSet, 4); |
49 | OSMetaClassDefineReservedUnused(OSSet, 5); |
50 | OSMetaClassDefineReservedUnused(OSSet, 6); |
51 | OSMetaClassDefineReservedUnused(OSSet, 7); |
52 | |
53 | #define EXT_CAST(obj) \ |
54 | reinterpret_cast<OSObject *>(const_cast<OSMetaClassBase *>(obj)) |
55 | |
56 | bool |
57 | OSSet::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 | |
71 | bool |
72 | OSSet::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 | |
102 | bool |
103 | OSSet::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 | |
114 | bool |
115 | OSSet::initWithSet(const OSSet *inSet, |
116 | unsigned int inCapacity) |
117 | { |
118 | return initWithArray(inArray: inSet->members.get(), inCapacity); |
119 | } |
120 | |
121 | OSSharedPtr<OSSet> |
122 | OSSet::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 | |
133 | OSSharedPtr<OSSet> |
134 | OSSet::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 | |
147 | OSSharedPtr<OSSet> |
148 | OSSet::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 | |
160 | OSSharedPtr<OSSet> |
161 | OSSet::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 | |
173 | void |
174 | OSSet::free() |
175 | { |
176 | if (members) { |
177 | (void) members->super::setOptions(options: 0, mask: kImmutable); |
178 | } |
179 | |
180 | super::free(); |
181 | } |
182 | |
183 | unsigned int |
184 | OSSet::getCount() const |
185 | { |
186 | return members->count; |
187 | } |
188 | |
189 | unsigned int |
190 | OSSet::getCapacity() const |
191 | { |
192 | return members->capacity; |
193 | } |
194 | |
195 | unsigned int |
196 | OSSet::getCapacityIncrement() const |
197 | { |
198 | return members->capacityIncrement; |
199 | } |
200 | |
201 | unsigned int |
202 | OSSet::setCapacityIncrement(unsigned int increment) |
203 | { |
204 | return members->setCapacityIncrement(increment); |
205 | } |
206 | |
207 | unsigned int |
208 | OSSet::ensureCapacity(unsigned int newCapacity) |
209 | { |
210 | return members->ensureCapacity(newCapacity); |
211 | } |
212 | |
213 | void |
214 | OSSet::flushCollection() |
215 | { |
216 | haveUpdated(); |
217 | members->flushCollection(); |
218 | } |
219 | |
220 | bool |
221 | OSSet::setObject(const OSMetaClassBase *anObject) |
222 | { |
223 | if (containsObject(anObject)) { |
224 | return false; |
225 | } else { |
226 | haveUpdated(); |
227 | return members->setObject(anObject); |
228 | } |
229 | } |
230 | |
231 | bool |
232 | OSSet::setObject(OSSharedPtr<const OSMetaClassBase> const& anObject) |
233 | { |
234 | return setObject(anObject.get()); |
235 | } |
236 | |
237 | bool |
238 | OSSet::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 | |
258 | bool |
259 | OSSet::merge(const OSSet * set) |
260 | { |
261 | return merge(array: set->members.get()); |
262 | } |
263 | |
264 | void |
265 | OSSet::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 | |
278 | void |
279 | OSSet::removeObject(OSSharedPtr<const OSMetaClassBase> const& anObject) |
280 | { |
281 | removeObject(anObject: anObject.get()); |
282 | } |
283 | |
284 | |
285 | bool |
286 | OSSet::containsObject(const OSMetaClassBase *anObject) const |
287 | { |
288 | return anObject && member(anObject); |
289 | } |
290 | |
291 | bool |
292 | OSSet::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 | |
305 | OSObject * |
306 | OSSet::getAnyObject() const |
307 | { |
308 | return members->getObject(index: 0); |
309 | } |
310 | |
311 | bool |
312 | OSSet::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 | |
346 | bool |
347 | OSSet::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 | |
359 | unsigned int |
360 | OSSet::iteratorSize() const |
361 | { |
362 | return sizeof(unsigned int); |
363 | } |
364 | |
365 | bool |
366 | OSSet::initIterator(void *inIterator) const |
367 | { |
368 | unsigned int *iteratorP = (unsigned int *) inIterator; |
369 | |
370 | *iteratorP = 0; |
371 | return true; |
372 | } |
373 | |
374 | bool |
375 | OSSet::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 | |
389 | bool |
390 | OSSet::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 | |
411 | unsigned |
412 | OSSet::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 | |
422 | OSSharedPtr<OSCollection> |
423 | OSSet::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 | |