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
29 #define IOKIT_ENABLE_SHARED_PTR
30
31 #include <libkern/c++/OSDictionary.h>
32 #include <libkern/c++/OSLib.h>
33 #include <libkern/c++/OSOrderedSet.h>
34 #include <libkern/c++/OSSharedPtr.h>
35 #include <os/cpp_util.h>
36
37 #define super OSCollection
38
39 OSDefineMetaClassAndStructors(OSOrderedSet, OSCollection)
40 OSMetaClassDefineReservedUnused(OSOrderedSet, 0);
41 OSMetaClassDefineReservedUnused(OSOrderedSet, 1);
42 OSMetaClassDefineReservedUnused(OSOrderedSet, 2);
43 OSMetaClassDefineReservedUnused(OSOrderedSet, 3);
44 OSMetaClassDefineReservedUnused(OSOrderedSet, 4);
45 OSMetaClassDefineReservedUnused(OSOrderedSet, 5);
46 OSMetaClassDefineReservedUnused(OSOrderedSet, 6);
47 OSMetaClassDefineReservedUnused(OSOrderedSet, 7);
48
49
50 struct _Element {
51 OSTaggedPtr<const OSMetaClassBase> obj;
52 };
53
54 #define EXT_CAST(obj) \
55 reinterpret_cast<OSObject *>(const_cast<OSMetaClassBase *>(obj))
56
57 bool
58 OSOrderedSet::
initWithCapacity(unsigned int inCapacity,OSOrderFunction inOrdering,void * inOrderingRef)59 initWithCapacity(unsigned int inCapacity,
60 OSOrderFunction inOrdering, void *inOrderingRef)
61 {
62 if (!super::init()) {
63 return false;
64 }
65
66 if (inCapacity > (UINT_MAX / sizeof(_Element))) {
67 return false;
68 }
69
70 array = kallocp_type_container(_Element, &inCapacity, Z_WAITOK_ZERO);
71 if (!array) {
72 return false;
73 }
74
75 count = 0;
76 capacity = inCapacity;
77 capacityIncrement = (inCapacity)? inCapacity : 16;
78 ordering = inOrdering;
79 orderingRef = inOrderingRef;
80
81 OSCONTAINER_ACCUMSIZE(sizeof(_Element) * inCapacity);
82
83 return true;
84 }
85
86 OSSharedPtr<OSOrderedSet>
87 OSOrderedSet::
withCapacity(unsigned int capacity,OSOrderFunction ordering,void * orderingRef)88 withCapacity(unsigned int capacity,
89 OSOrderFunction ordering, void * orderingRef)
90 {
91 auto me = OSMakeShared<OSOrderedSet>();
92
93 if (me && !me->initWithCapacity(capacity, ordering, orderingRef)) {
94 return nullptr;
95 }
96
97 return me;
98 }
99
100 static SInt32
OSOrderedSetBlockToFunc(const OSMetaClassBase * obj1,const OSMetaClassBase * obj2,void * context)101 OSOrderedSetBlockToFunc(const OSMetaClassBase * obj1,
102 const OSMetaClassBase * obj2,
103 void * context)
104 {
105 OSOrderedSet::OSOrderBlock ordering = (typeof(ordering))context;
106
107 return ordering(obj1, obj2);
108 }
109
110
111 OSSharedPtr<OSOrderedSet>
withCapacity(unsigned int capacity,OSOrderBlock ordering)112 OSOrderedSet::withCapacity(unsigned int capacity, OSOrderBlock ordering)
113 {
114 auto me = OSMakeShared<OSOrderedSet>();
115
116 if (me && !me->initWithCapacity(capacity, &OSOrderedSetBlockToFunc, ordering)) {
117 return nullptr;
118 }
119
120 return me;
121 }
122
123 void
free()124 OSOrderedSet::free()
125 {
126 (void) super::setOptions(0, kImmutable);
127 flushCollection();
128
129 if (array) {
130 kfree_type(_Element, capacity, array);
131 OSCONTAINER_ACCUMSIZE( -(sizeof(_Element) * capacity));
132 }
133
134 super::free();
135 }
136
137 unsigned int
getCount() const138 OSOrderedSet::getCount() const
139 {
140 return count;
141 }
142 unsigned int
getCapacity() const143 OSOrderedSet::getCapacity() const
144 {
145 return capacity;
146 }
147 unsigned int
getCapacityIncrement() const148 OSOrderedSet::getCapacityIncrement() const
149 {
150 return capacityIncrement;
151 }
152 unsigned int
setCapacityIncrement(unsigned int increment)153 OSOrderedSet::setCapacityIncrement(unsigned int increment)
154 {
155 capacityIncrement = (increment)? increment : 16;
156 return capacityIncrement;
157 }
158
159 unsigned int
ensureCapacity(unsigned int newCapacity)160 OSOrderedSet::ensureCapacity(unsigned int newCapacity)
161 {
162 _Element *newArray;
163 unsigned int finalCapacity;
164
165 if (newCapacity <= capacity) {
166 return capacity;
167 }
168
169 // round up
170 finalCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
171 * capacityIncrement;
172 if (finalCapacity < newCapacity) {
173 return capacity;
174 }
175
176 newArray = kreallocp_type_container(_Element, array,
177 capacity, &finalCapacity, Z_WAITOK_ZERO);
178 if (newArray) {
179 OSCONTAINER_ACCUMSIZE(sizeof(_Element) * (finalCapacity - capacity));
180 array = newArray;
181 capacity = finalCapacity;
182 }
183
184 return capacity;
185 }
186
187 void
flushCollection()188 OSOrderedSet::flushCollection()
189 {
190 unsigned int i;
191
192 haveUpdated();
193
194 for (i = 0; i < count; i++) {
195 array[i].obj.reset();
196 }
197
198 count = 0;
199 }
200
201 /* internal */
202 bool
setObject(unsigned int index,const OSMetaClassBase * anObject)203 OSOrderedSet::setObject(unsigned int index, const OSMetaClassBase *anObject)
204 {
205 unsigned int i;
206 unsigned int newCount = count + 1;
207
208 if ((index > count) || !anObject) {
209 return false;
210 }
211
212 if (containsObject(anObject)) {
213 return false;
214 }
215
216 // do we need more space?
217 if (newCount > capacity && newCount > ensureCapacity(newCount)) {
218 return false;
219 }
220
221 haveUpdated();
222 if (index != count) {
223 for (i = count; i > index; i--) {
224 array[i] = os::move(array[i - 1]);
225 }
226 }
227 array[index].obj.reset(anObject, OSRetain);
228 count++;
229
230 return true;
231 }
232
233 bool
setObject(unsigned int index,OSSharedPtr<const OSMetaClassBase> const & anObject)234 OSOrderedSet::setObject(unsigned int index, OSSharedPtr<const OSMetaClassBase> const& anObject)
235 {
236 return setObject(index, anObject.get());
237 }
238
239 bool
setFirstObject(const OSMetaClassBase * anObject)240 OSOrderedSet::setFirstObject(const OSMetaClassBase *anObject)
241 {
242 return setObject(0, anObject);
243 }
244
245 bool
setFirstObject(OSSharedPtr<const OSMetaClassBase> const & anObject)246 OSOrderedSet::setFirstObject(OSSharedPtr<const OSMetaClassBase> const& anObject)
247 {
248 return setFirstObject(anObject.get());
249 }
250
251 bool
setLastObject(const OSMetaClassBase * anObject)252 OSOrderedSet::setLastObject(const OSMetaClassBase *anObject)
253 {
254 return setObject( count, anObject);
255 }
256
257 bool
setLastObject(OSSharedPtr<const OSMetaClassBase> const & anObject)258 OSOrderedSet::setLastObject(OSSharedPtr<const OSMetaClassBase> const& anObject)
259 {
260 return setLastObject(anObject.get());
261 }
262
263
264 #define ORDER(obj1, obj2) \
265 (ordering ? ((*ordering)( (const OSObject *) obj1, (const OSObject *) obj2, orderingRef)) : 0)
266
267 bool
setObject(const OSMetaClassBase * anObject)268 OSOrderedSet::setObject(const OSMetaClassBase *anObject )
269 {
270 unsigned int i;
271
272 // queue it behind those with same priority
273 for (i = 0;
274 (i < count) && (ORDER(array[i].obj.get(), anObject) >= 0);
275 i++) {
276 }
277
278 return setObject(i, anObject);
279 }
280
281 bool
setObject(OSSharedPtr<const OSMetaClassBase> const & anObject)282 OSOrderedSet::setObject(OSSharedPtr<const OSMetaClassBase> const& anObject)
283 {
284 return setObject(anObject.get());
285 }
286
287 void
removeObject(const OSMetaClassBase * anObject)288 OSOrderedSet::removeObject(const OSMetaClassBase *anObject)
289 {
290 bool deleted = false;
291 unsigned int i;
292
293 for (i = 0; i < count; i++) {
294 if (deleted) {
295 array[i - 1] = os::move(array[i]);
296 } else if (array[i].obj == anObject) {
297 deleted = true;
298 haveUpdated(); // Pity we can't flush the log
299 array[i].obj.reset();
300 }
301 }
302
303 if (deleted) {
304 count--;
305 }
306 }
307
308 void
removeObject(OSSharedPtr<const OSMetaClassBase> const & anObject)309 OSOrderedSet::removeObject(OSSharedPtr<const OSMetaClassBase> const& anObject)
310 {
311 return removeObject(anObject.get());
312 }
313
314 bool
containsObject(const OSMetaClassBase * anObject) const315 OSOrderedSet::containsObject(const OSMetaClassBase *anObject) const
316 {
317 return anObject && member(anObject);
318 }
319
320 bool
member(const OSMetaClassBase * anObject) const321 OSOrderedSet::member(const OSMetaClassBase *anObject) const
322 {
323 unsigned int i;
324
325 for (i = 0;
326 (i < count) && (array[i].obj != anObject);
327 i++) {
328 }
329
330 return i < count;
331 }
332
333 /* internal */
334 OSObject *
getObject(unsigned int index) const335 OSOrderedSet::getObject( unsigned int index ) const
336 {
337 if (index >= count) {
338 return NULL;
339 }
340
341 return const_cast<OSObject *>((const OSObject *) array[index].obj.get());
342 }
343
344 OSObject *
getFirstObject() const345 OSOrderedSet::getFirstObject() const
346 {
347 if (count) {
348 return const_cast<OSObject *>((const OSObject *) array[0].obj.get());
349 } else {
350 return NULL;
351 }
352 }
353
354 OSObject *
getLastObject() const355 OSOrderedSet::getLastObject() const
356 {
357 if (count) {
358 return const_cast<OSObject *>((const OSObject *) array[count - 1].obj.get());
359 } else {
360 return NULL;
361 }
362 }
363
364 SInt32
orderObject(const OSMetaClassBase * anObject)365 OSOrderedSet::orderObject( const OSMetaClassBase * anObject )
366 {
367 return ORDER( anObject, NULL );
368 }
369
370 void *
getOrderingRef()371 OSOrderedSet::getOrderingRef()
372 {
373 return orderingRef;
374 }
375
376 bool
isEqualTo(const OSOrderedSet * anOrderedSet) const377 OSOrderedSet::isEqualTo(const OSOrderedSet *anOrderedSet) const
378 {
379 unsigned int i;
380
381 if (this == anOrderedSet) {
382 return true;
383 }
384
385 if (count != anOrderedSet->getCount()) {
386 return false;
387 }
388
389 for (i = 0; i < count; i++) {
390 if (!array[i].obj->isEqualTo(anOrderedSet->getObject(i))) {
391 return false;
392 }
393 }
394
395 return true;
396 }
397
398 bool
isEqualTo(const OSMetaClassBase * anObject) const399 OSOrderedSet::isEqualTo(const OSMetaClassBase *anObject) const
400 {
401 OSOrderedSet *oSet;
402
403 oSet = OSDynamicCast(OSOrderedSet, anObject);
404 if (oSet) {
405 return isEqualTo(oSet);
406 } else {
407 return false;
408 }
409 }
410
411 unsigned int
iteratorSize() const412 OSOrderedSet::iteratorSize() const
413 {
414 return sizeof(unsigned int);
415 }
416
417 bool
initIterator(void * inIterator) const418 OSOrderedSet::initIterator(void *inIterator) const
419 {
420 unsigned int *iteratorP = (unsigned int *) inIterator;
421
422 *iteratorP = 0;
423 return true;
424 }
425
426 bool
427 OSOrderedSet::
getNextObjectForIterator(void * inIterator,OSObject ** ret) const428 getNextObjectForIterator(void *inIterator, OSObject **ret) const
429 {
430 unsigned int *iteratorP = (unsigned int *) inIterator;
431 unsigned int index = (*iteratorP)++;
432
433 if (index < count) {
434 *ret = const_cast<OSObject *>((const OSObject *) array[index].obj.get());
435 } else {
436 *ret = NULL;
437 }
438
439 return *ret != NULL;
440 }
441
442
443 unsigned
setOptions(unsigned options,unsigned mask,void *)444 OSOrderedSet::setOptions(unsigned options, unsigned mask, void *)
445 {
446 unsigned old = super::setOptions(options, mask);
447 if ((old ^ options) & mask) {
448 // Value changed need to recurse over all of the child collections
449 for (unsigned i = 0; i < count; i++) {
450 OSCollection *coll = OSDynamicCast(OSCollection, array[i].obj.get());
451 if (coll) {
452 coll->setOptions(options, mask);
453 }
454 }
455 }
456
457 return old;
458 }
459
460 OSSharedPtr<OSCollection>
copyCollection(OSDictionary * cycleDict)461 OSOrderedSet::copyCollection(OSDictionary *cycleDict)
462 {
463 OSSharedPtr<OSDictionary> ourCycleDict;
464 OSSharedPtr<OSCollection> ret;
465 OSSharedPtr<OSOrderedSet> newSet;
466
467 if (!cycleDict) {
468 ourCycleDict = OSDictionary::withCapacity(16);
469 if (!ourCycleDict) {
470 return nullptr;
471 }
472 cycleDict = ourCycleDict.get();
473 }
474
475 do {
476 // Check for a cycle
477 ret = super::copyCollection(cycleDict);
478 if (ret) {
479 continue;
480 }
481
482 // Duplicate the set with no contents
483 newSet = OSOrderedSet::withCapacity(capacity, ordering, orderingRef);
484 if (!newSet) {
485 continue;
486 }
487
488 // Insert object into cycle Dictionary
489 cycleDict->setObject((const OSSymbol *) this, newSet.get());
490
491 newSet->capacityIncrement = capacityIncrement;
492
493 // Now copy over the contents to the new duplicate
494 for (unsigned int i = 0; i < count; i++) {
495 OSObject *obj = EXT_CAST(array[i].obj.get());
496 OSCollection *coll = OSDynamicCast(OSCollection, obj);
497 if (coll) {
498 OSSharedPtr<OSCollection> newColl = coll->copyCollection(cycleDict);
499 if (newColl) {
500 obj = newColl.get(); // Rely on cycleDict ref for a bit
501 } else {
502 return ret;
503 }
504 }
505
506 newSet->setLastObject(obj);
507 }
508
509 ret = os::move(newSet);
510 } while (false);
511
512 return ret;
513 }
514