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 /* OSDictionary.m created by rsulack on Fri 12-Sep-1997 */
29 /* OSDictionary.cpp converted to C++ by gvdl on Fri 1998-10-30 */
30 /* OSDictionary.cpp rewritten by gvdl on Fri 1998-10-30 */
31
32 #define IOKIT_ENABLE_SHARED_PTR
33
34 #include <libkern/c++/OSArray.h>
35 #include <libkern/c++/OSCollectionIterator.h>
36 #include <libkern/c++/OSDictionary.h>
37 #include <libkern/c++/OSLib.h>
38 #include <libkern/c++/OSSerialize.h>
39 #include <libkern/c++/OSSharedPtr.h>
40 #include <libkern/c++/OSSymbol.h>
41 #include <os/cpp_util.h>
42
43 #define super OSCollection
44
45 OSDefineMetaClassAndStructorsWithZone(OSDictionary, OSCollection,
46 (zone_create_flags_t) (ZC_CACHING | ZC_ZFREE_CLEARMEM))
47 OSMetaClassDefineReservedUnused(OSDictionary, 0);
48 OSMetaClassDefineReservedUnused(OSDictionary, 1);
49 OSMetaClassDefineReservedUnused(OSDictionary, 2);
50 OSMetaClassDefineReservedUnused(OSDictionary, 3);
51 OSMetaClassDefineReservedUnused(OSDictionary, 4);
52 OSMetaClassDefineReservedUnused(OSDictionary, 5);
53 OSMetaClassDefineReservedUnused(OSDictionary, 6);
54 OSMetaClassDefineReservedUnused(OSDictionary, 7);
55
56 #define EXT_CAST(obj) \
57 reinterpret_cast<OSObject *>(const_cast<OSMetaClassBase *>(obj))
58
59 extern "C" {
60 void qsort(void *, size_t, size_t, int (*)(const void *, const void *));
61 }
62
63 int
compare(const void * _e1,const void * _e2)64 OSDictionary::dictEntry::compare(const void *_e1, const void *_e2)
65 {
66 const OSDictionary::dictEntry *e1 = (const OSDictionary::dictEntry *)_e1;
67 const OSDictionary::dictEntry *e2 = (const OSDictionary::dictEntry *)_e2;
68
69 if ((uintptr_t)e1->key.get() == (uintptr_t)e2->key.get()) {
70 return 0;
71 }
72
73 return (uintptr_t)e1->key.get() > (uintptr_t)e2->key.get() ? 1 : -1;
74 }
75
76 void
sortBySymbol(void)77 OSDictionary::sortBySymbol(void)
78 {
79 qsort(dictionary, count, sizeof(OSDictionary::dictEntry),
80 &OSDictionary::dictEntry::compare);
81 }
82
83 bool
initWithCapacity(unsigned int inCapacity)84 OSDictionary::initWithCapacity(unsigned int inCapacity)
85 {
86 if (!super::init()) {
87 return false;
88 }
89
90 if (inCapacity > (UINT_MAX / sizeof(dictEntry))) {
91 return false;
92 }
93
94 //fOptions |= kSort;
95
96 dictionary = kallocp_type_container(dictEntry, &inCapacity, Z_WAITOK_ZERO);
97 if (!dictionary) {
98 return false;
99 }
100
101 os::uninitialized_value_construct(dictionary, dictionary + inCapacity);
102 OSCONTAINER_ACCUMSIZE(inCapacity * sizeof(dictEntry));
103
104 count = 0;
105 capacity = inCapacity;
106 capacityIncrement = (inCapacity)? inCapacity : 16;
107
108 return true;
109 }
110
111 bool
initWithObjects(const OSObject * objects[],const OSSymbol * keys[],unsigned int theCount,unsigned int theCapacity)112 OSDictionary::initWithObjects(const OSObject *objects[],
113 const OSSymbol *keys[],
114 unsigned int theCount,
115 unsigned int theCapacity)
116 {
117 unsigned int newCapacity = theCount;
118
119 if (!objects || !keys) {
120 return false;
121 }
122
123 if (theCapacity) {
124 if (theCount > theCapacity) {
125 return false;
126 }
127
128 newCapacity = theCapacity;
129 }
130
131 if (!initWithCapacity(newCapacity)) {
132 return false;
133 }
134
135 for (unsigned int i = 0; i < theCount; i++) {
136 const OSMetaClassBase *newObject = *objects++;
137
138 if (!newObject || !keys[i] || !setObject(keys[i], newObject)) {
139 return false;
140 }
141 }
142
143 return true;
144 }
145
146 bool
initWithObjects(const OSObject * objects[],const OSString * keys[],unsigned int theCount,unsigned int theCapacity)147 OSDictionary::initWithObjects(const OSObject *objects[],
148 const OSString *keys[],
149 unsigned int theCount,
150 unsigned int theCapacity)
151 {
152 unsigned int newCapacity = theCount;
153
154 if (!objects || !keys) {
155 return false;
156 }
157
158 if (theCapacity) {
159 if (theCount > theCapacity) {
160 return false;
161 }
162
163 newCapacity = theCapacity;
164 }
165
166 if (!initWithCapacity(newCapacity)) {
167 return false;
168 }
169
170 for (unsigned int i = 0; i < theCount; i++) {
171 OSSharedPtr<const OSSymbol> key = OSSymbol::withString(*keys++);
172 const OSMetaClassBase *newObject = *objects++;
173
174 if (!key) {
175 return false;
176 }
177
178 if (!newObject || !setObject(key.get(), newObject)) {
179 return false;
180 }
181 }
182
183 return true;
184 }
185
186 bool
initWithDictionary(const OSDictionary * dict,unsigned int theCapacity)187 OSDictionary::initWithDictionary(const OSDictionary *dict,
188 unsigned int theCapacity)
189 {
190 unsigned int newCapacity;
191
192 if (!dict) {
193 return false;
194 }
195
196 newCapacity = dict->count;
197
198 if (theCapacity) {
199 if (dict->count > theCapacity) {
200 return false;
201 }
202
203 newCapacity = theCapacity;
204 }
205
206 if (!initWithCapacity(newCapacity)) {
207 return false;
208 }
209
210 count = dict->count;
211 for (unsigned int i = 0; i < count; i++) {
212 dictionary[i].key = dict->dictionary[i].key;
213 dictionary[i].value = dict->dictionary[i].value;
214 }
215
216 if ((kSort & fOptions) && !(kSort & dict->fOptions)) {
217 sortBySymbol();
218 }
219
220 return true;
221 }
222
223 OSSharedPtr<OSDictionary>
withCapacity(unsigned int capacity)224 OSDictionary::withCapacity(unsigned int capacity)
225 {
226 OSSharedPtr<OSDictionary> me = OSMakeShared<OSDictionary>();
227
228 if (me && !me->initWithCapacity(capacity)) {
229 return nullptr;
230 }
231
232 return me;
233 }
234
235 OSSharedPtr<OSDictionary>
withObjects(const OSObject * objects[],const OSSymbol * keys[],unsigned int count,unsigned int capacity)236 OSDictionary::withObjects(const OSObject *objects[],
237 const OSSymbol *keys[],
238 unsigned int count,
239 unsigned int capacity)
240 {
241 OSSharedPtr<OSDictionary> me = OSMakeShared<OSDictionary>();
242
243 if (me && !me->initWithObjects(objects, keys, count, capacity)) {
244 return nullptr;
245 }
246
247 return me;
248 }
249
250 OSSharedPtr<OSDictionary>
withObjects(const OSObject * objects[],const OSString * keys[],unsigned int count,unsigned int capacity)251 OSDictionary::withObjects(const OSObject *objects[],
252 const OSString *keys[],
253 unsigned int count,
254 unsigned int capacity)
255 {
256 OSSharedPtr<OSDictionary> me = OSMakeShared<OSDictionary>();
257
258 if (me && !me->initWithObjects(objects, keys, count, capacity)) {
259 return nullptr;
260 }
261
262 return me;
263 }
264
265 OSSharedPtr<OSDictionary>
withDictionary(const OSDictionary * dict,unsigned int capacity)266 OSDictionary::withDictionary(const OSDictionary *dict,
267 unsigned int capacity)
268 {
269 OSSharedPtr<OSDictionary> me = OSMakeShared<OSDictionary>();
270
271 if (me && !me->initWithDictionary(dict, capacity)) {
272 return nullptr;
273 }
274
275 return me;
276 }
277
278 void
free()279 OSDictionary::free()
280 {
281 (void) super::setOptions(0, kImmutable);
282 flushCollection();
283 if (dictionary) {
284 kfree_type(dictEntry, capacity, dictionary);
285 OSCONTAINER_ACCUMSIZE( -(capacity * sizeof(dictEntry)));
286 }
287
288 super::free();
289 }
290
291 unsigned int
getCount() const292 OSDictionary::getCount() const
293 {
294 return count;
295 }
296 unsigned int
getCapacity() const297 OSDictionary::getCapacity() const
298 {
299 return capacity;
300 }
301
302 unsigned int
getCapacityIncrement() const303 OSDictionary::getCapacityIncrement() const
304 {
305 return capacityIncrement;
306 }
307
308 unsigned int
setCapacityIncrement(unsigned int increment)309 OSDictionary::setCapacityIncrement(unsigned int increment)
310 {
311 capacityIncrement = (increment)? increment : 16;
312
313 return capacityIncrement;
314 }
315
316 unsigned int
ensureCapacity(unsigned int newCapacity)317 OSDictionary::ensureCapacity(unsigned int newCapacity)
318 {
319 dictEntry *newDict;
320 unsigned int finalCapacity;
321
322 if (newCapacity <= capacity) {
323 return capacity;
324 }
325
326 // round up
327 finalCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
328 * capacityIncrement;
329
330 // integer overflow check
331 if (finalCapacity < newCapacity) {
332 return capacity;
333 }
334
335 newDict = kallocp_type_container(dictEntry, &finalCapacity, Z_WAITOK);
336 if (newDict) {
337 os::uninitialized_move(dictionary, dictionary + capacity, newDict);
338 os::uninitialized_value_construct(newDict + capacity, newDict + finalCapacity);
339 os::destroy(dictionary, dictionary + capacity);
340
341 OSCONTAINER_ACCUMSIZE(sizeof(dictEntry) * (finalCapacity - capacity));
342
343 kfree_type(dictEntry, capacity, dictionary);
344 dictionary = newDict;
345 capacity = finalCapacity;
346 }
347
348 return capacity;
349 }
350
351 void
flushCollection()352 OSDictionary::flushCollection()
353 {
354 haveUpdated();
355
356 for (unsigned int i = 0; i < count; i++) {
357 dictionary[i].key->taggedRelease(OSTypeID(OSCollection));
358 dictionary[i].value->taggedRelease(OSTypeID(OSCollection));
359 }
360 count = 0;
361 }
362
363 bool
364 OSDictionary::
setObject(const OSSymbol * aKey,const OSMetaClassBase * anObject,bool onlyAdd)365 setObject(const OSSymbol *aKey, const OSMetaClassBase *anObject, bool onlyAdd)
366 {
367 unsigned int i;
368 bool exists;
369
370 if (!anObject || !aKey) {
371 return false;
372 }
373
374 // if the key exists, replace the object
375
376 if (fOptions & kSort) {
377 i = OSSymbol::bsearch(aKey, &dictionary[0], count, sizeof(dictionary[0]));
378 exists = (i < count) && (aKey == dictionary[i].key);
379 } else {
380 for (exists = false, i = 0; i < count; i++) {
381 if ((exists = (aKey == dictionary[i].key))) {
382 break;
383 }
384 }
385 }
386
387 if (exists) {
388 if (onlyAdd) {
389 return false;
390 }
391
392 OSTaggedSharedPtr<const OSMetaClassBase, OSCollection> oldObject;
393
394 haveUpdated();
395
396 dictionary[i].value.reset(anObject, OSRetain);
397 return true;
398 }
399
400 // add new key, possibly extending our capacity
401 if (count >= capacity && count >= ensureCapacity(count + 1)) {
402 return false;
403 }
404
405 haveUpdated();
406
407 new (&dictionary[count]) dictEntry();
408 os::move_backward(&dictionary[i], &dictionary[count], &dictionary[count + 1]);
409
410 dictionary[i].key.reset(aKey, OSRetain);
411 dictionary[i].value.reset(anObject, OSRetain);
412 count++;
413
414 return true;
415 }
416
417 bool
418 OSDictionary::
setObject(const OSSymbol * aKey,const OSMetaClassBase * anObject)419 setObject(const OSSymbol *aKey, const OSMetaClassBase *anObject)
420 {
421 return setObject(aKey, anObject, false);
422 }
423
424 bool
setObject(OSSharedPtr<const OSSymbol> const & aKey,OSSharedPtr<const OSMetaClassBase> const & anObject)425 OSDictionary::setObject(OSSharedPtr<const OSSymbol> const& aKey, OSSharedPtr<const OSMetaClassBase> const& anObject)
426 {
427 return setObject(aKey.get(), anObject.get());
428 }
429
430 bool
setObject(const OSString * aKey,OSSharedPtr<const OSMetaClassBase> const & anObject)431 OSDictionary::setObject(const OSString* aKey, OSSharedPtr<const OSMetaClassBase> const& anObject)
432 {
433 return setObject(aKey, anObject.get());
434 }
435
436 bool
setObject(const char * aKey,OSSharedPtr<const OSMetaClassBase> const & anObject)437 OSDictionary::setObject(const char* aKey, OSSharedPtr<const OSMetaClassBase> const& anObject)
438 {
439 return setObject(aKey, anObject.get());
440 }
441
442 void
removeObject(const OSSymbol * aKey)443 OSDictionary::removeObject(const OSSymbol *aKey)
444 {
445 unsigned int i;
446 bool exists;
447
448 if (!aKey) {
449 return;
450 }
451
452 // if the key exists, remove the object
453
454 if (fOptions & kSort) {
455 i = OSSymbol::bsearch(aKey, &dictionary[0], count, sizeof(dictionary[0]));
456 exists = (i < count) && (aKey == dictionary[i].key);
457 } else {
458 for (exists = false, i = 0; i < count; i++) {
459 if ((exists = (aKey == dictionary[i].key))) {
460 break;
461 }
462 }
463 }
464
465 if (exists) {
466 dictEntry oldEntry = dictionary[i];
467
468 haveUpdated();
469
470 count--;
471 bcopy(&dictionary[i + 1], &dictionary[i], (count - i) * sizeof(dictionary[0]));
472
473 oldEntry.key->taggedRelease(OSTypeID(OSCollection));
474 oldEntry.value->taggedRelease(OSTypeID(OSCollection));
475 return;
476 }
477 }
478
479
480 // Returns true on success, false on an error condition.
481 bool
merge(const OSDictionary * srcDict)482 OSDictionary::merge(const OSDictionary *srcDict)
483 {
484 const OSSymbol * sym;
485 OSSharedPtr<OSCollectionIterator> iter;
486
487 if (!OSDynamicCast(OSDictionary, srcDict)) {
488 return false;
489 }
490
491 iter = OSCollectionIterator::withCollection(const_cast<OSDictionary *>(srcDict));
492 if (!iter) {
493 return false;
494 }
495
496 while ((sym = (const OSSymbol *)iter->getNextObject())) {
497 const OSMetaClassBase * obj;
498
499 obj = srcDict->getObject(sym);
500 if (!setObject(sym, obj)) {
501 return false;
502 }
503 }
504
505 return true;
506 }
507
508 OSObject *
getObject(const OSSymbol * aKey) const509 OSDictionary::getObject(const OSSymbol *aKey) const
510 {
511 unsigned int i, l = 0, r = count;
512
513 if (!aKey) {
514 return NULL;
515 }
516
517 // if the key exists, return the object
518 //
519 // inline OSSymbol::bsearch in this performance critical codepath
520 // for performance, the compiler can't do that due to the genericity
521 // of OSSymbol::bsearch
522 //
523 // If we have less than 4 objects, scanning is faster.
524 if (count > 4 && (fOptions & kSort)) {
525 while (l < r) {
526 i = (l + r) / 2;
527 if (aKey == dictionary[i].key) {
528 return const_cast<OSObject *> ((const OSObject *)dictionary[i].value.get());
529 }
530
531 if ((uintptr_t)aKey < (uintptr_t)dictionary[i].key.get()) {
532 r = i;
533 } else {
534 l = i + 1;
535 }
536 }
537 } else {
538 for (i = l; i < r; i++) {
539 if (aKey == dictionary[i].key) {
540 return const_cast<OSObject *> ((const OSObject *)dictionary[i].value.get());
541 }
542 }
543 }
544
545 return NULL;
546 }
547
548 // Wrapper macros
549 #define OBJECT_WRAP_1(cmd, k) \
550 { \
551 OSSharedPtr<const OSSymbol> tmpKey = k; \
552 OSObject *retObj = NULL; \
553 if (tmpKey) { \
554 retObj = cmd(tmpKey.get()); \
555 } \
556 return retObj; \
557 }
558
559 #define OBJECT_WRAP_2(cmd, k, o) \
560 { \
561 OSSharedPtr<const OSSymbol> tmpKey = k; \
562 bool ret = cmd(tmpKey.get(), o); \
563 \
564 return ret; \
565 }
566
567 #define OBJECT_WRAP_3(cmd, k) \
568 { \
569 OSSharedPtr<const OSSymbol> tmpKey = k; \
570 if (tmpKey) { \
571 cmd(tmpKey.get()); \
572 } \
573 }
574
575
576 bool
setObject(const OSString * aKey,const OSMetaClassBase * anObject)577 OSDictionary::setObject(const OSString *aKey, const OSMetaClassBase *anObject)
578 OBJECT_WRAP_2(setObject, OSSymbol::withString(aKey), anObject)
579 bool
580 OSDictionary::setObject(const char *aKey, const OSMetaClassBase *anObject)
581 OBJECT_WRAP_2(setObject, OSSymbol::withCString(aKey), anObject)
582
583 OSObject *OSDictionary::getObject(const OSString * aKey) const
584 OBJECT_WRAP_1(getObject, OSSymbol::existingSymbolForString(aKey))
585 OSObject *OSDictionary::getObject(const char *aKey) const
586 OBJECT_WRAP_1(getObject, OSSymbol::existingSymbolForCString(aKey))
587
588 void
589 OSDictionary::removeObject(const OSString *aKey)
590 OBJECT_WRAP_3(removeObject, OSSymbol::existingSymbolForString(aKey))
591 void
592 OSDictionary::removeObject(const char *aKey)
593 OBJECT_WRAP_3(removeObject, OSSymbol::existingSymbolForCString(aKey))
594
595 bool
596 OSDictionary::isEqualTo(const OSDictionary *srcDict, const OSCollection *keys) const
597 {
598 OSSharedPtr<OSCollectionIterator> iter;
599 unsigned int keysCount;
600 const OSMetaClassBase * obj1;
601 const OSMetaClassBase * obj2;
602 OSString * aKey;
603 bool ret;
604
605 if (this == srcDict) {
606 return true;
607 }
608
609 keysCount = keys->getCount();
610 if ((count < keysCount) || (srcDict->getCount() < keysCount)) {
611 return false;
612 }
613
614 iter = OSCollectionIterator::withCollection(keys);
615 if (!iter) {
616 return false;
617 }
618
619 ret = true;
620 while ((aKey = OSDynamicCast(OSString, iter->getNextObject()))) {
621 obj1 = getObject(aKey);
622 obj2 = srcDict->getObject(aKey);
623 if (!obj1 || !obj2) {
624 ret = false;
625 break;
626 }
627
628 if (!obj1->isEqualTo(obj2)) {
629 ret = false;
630 break;
631 }
632 }
633
634 return ret;
635 }
636
637 bool
isEqualTo(const OSDictionary * srcDict) const638 OSDictionary::isEqualTo(const OSDictionary *srcDict) const
639 {
640 unsigned int i;
641 const OSMetaClassBase * obj;
642
643 if (this == srcDict) {
644 return true;
645 }
646
647 if (count != srcDict->getCount()) {
648 return false;
649 }
650
651 for (i = 0; i < count; i++) {
652 obj = srcDict->getObject(dictionary[i].key.get());
653 if (!obj) {
654 return false;
655 }
656
657 if (!dictionary[i].value->isEqualTo(obj)) {
658 return false;
659 }
660 }
661
662 return true;
663 }
664
665 bool
isEqualTo(const OSMetaClassBase * anObject) const666 OSDictionary::isEqualTo(const OSMetaClassBase *anObject) const
667 {
668 OSDictionary *dict;
669
670 dict = OSDynamicCast(OSDictionary, anObject);
671 if (dict) {
672 return isEqualTo(dict);
673 } else {
674 return false;
675 }
676 }
677
678 unsigned int
iteratorSize() const679 OSDictionary::iteratorSize() const
680 {
681 return sizeof(unsigned int);
682 }
683
684 bool
initIterator(void * inIterator) const685 OSDictionary::initIterator(void *inIterator) const
686 {
687 unsigned int *iteratorP = (unsigned int *) inIterator;
688
689 *iteratorP = 0;
690 return true;
691 }
692
693 bool
getNextObjectForIterator(void * inIterator,OSObject ** ret) const694 OSDictionary::getNextObjectForIterator(void *inIterator, OSObject **ret) const
695 {
696 unsigned int *iteratorP = (unsigned int *) inIterator;
697 unsigned int index = (*iteratorP)++;
698
699 if (index < count) {
700 *ret = const_cast<OSSymbol*>(dictionary[index].key.get());
701 } else {
702 *ret = NULL;
703 }
704
705 return *ret != NULL;
706 }
707
708 bool
serialize(OSSerialize * s) const709 OSDictionary::serialize(OSSerialize *s) const
710 {
711 if (s->previouslySerialized(this)) {
712 return true;
713 }
714
715 if (!s->addXMLStartTag(this, "dict")) {
716 return false;
717 }
718
719 for (unsigned i = 0; i < count; i++) {
720 const OSSymbol *key = dictionary[i].key.get();
721
722 // due the nature of the XML syntax, this must be a symbol
723 if (!key->metaCast("OSSymbol")) {
724 return false;
725 }
726 if (!s->addString("<key>")) {
727 return false;
728 }
729 const char *c = key->getCStringNoCopy();
730 while (*c) {
731 if (*c == '<') {
732 if (!s->addString("<")) {
733 return false;
734 }
735 } else if (*c == '>') {
736 if (!s->addString(">")) {
737 return false;
738 }
739 } else if (*c == '&') {
740 if (!s->addString("&")) {
741 return false;
742 }
743 } else {
744 if (!s->addChar(*c)) {
745 return false;
746 }
747 }
748 c++;
749 }
750 if (!s->addXMLEndTag("key")) {
751 return false;
752 }
753
754 if (!dictionary[i].value->serialize(s)) {
755 return false;
756 }
757 }
758
759 return s->addXMLEndTag("dict");
760 }
761
762 unsigned
setOptions(unsigned options,unsigned mask,void *)763 OSDictionary::setOptions(unsigned options, unsigned mask, void *)
764 {
765 unsigned old = super::setOptions(options, mask);
766 if ((old ^ options) & mask) {
767 // Value changed need to recurse over all of the child collections
768 for (unsigned i = 0; i < count; i++) {
769 OSCollection *v = OSDynamicCast(OSCollection, dictionary[i].value.get());
770 if (v) {
771 v->setOptions(options, mask);
772 }
773 }
774 }
775
776 if (!(old & kSort) && (fOptions & kSort)) {
777 sortBySymbol();
778 }
779
780 return old;
781 }
782
783 OSSharedPtr<OSCollection>
copyCollection(OSDictionary * cycleDict)784 OSDictionary::copyCollection(OSDictionary *cycleDict)
785 {
786 OSSharedPtr<OSDictionary> ourCycleDict;
787 OSSharedPtr<OSCollection> ret;
788 OSSharedPtr<OSDictionary> newDict;
789
790 if (!cycleDict) {
791 ourCycleDict = OSDictionary::withCapacity(16);
792 if (!ourCycleDict) {
793 return nullptr;
794 }
795 cycleDict = ourCycleDict.get();
796 }
797
798 do {
799 // Check for a cycle
800 ret = super::copyCollection(cycleDict);
801 if (ret) {
802 continue;
803 }
804
805 newDict = OSDictionary::withDictionary(this);
806 if (!newDict) {
807 continue;
808 }
809
810 // Insert object into cycle Dictionary
811 cycleDict->setObject((const OSSymbol *) this, newDict.get());
812
813 for (unsigned int i = 0; i < count; i++) {
814 const OSMetaClassBase *obj = dictionary[i].value.get();
815 OSTaggedSharedPtr<OSCollection, OSCollection> coll(OSDynamicCast(OSCollection, EXT_CAST(obj)), OSNoRetain);
816
817 if (coll) {
818 OSSharedPtr<OSCollection> newColl = coll->copyCollection(cycleDict);
819 if (!newColl) {
820 return ret;
821 }
822 newDict->dictionary[i].value.detach();
823 newDict->dictionary[i].value.reset(newColl.get(), OSRetain);
824 }
825 }
826
827 ret = os::move(newDict);
828 } while (false);
829
830 return ret;
831 }
832
833 OSSharedPtr<OSArray>
copyKeys(void)834 OSDictionary::copyKeys(void)
835 {
836 OSSharedPtr<OSArray> array;
837
838 array = OSArray::withCapacity(count);
839 if (!array) {
840 return nullptr;
841 }
842
843 for (unsigned int i = 0; i < count; i++) {
844 if (!array->setObject(i, dictionary[i].key.get())) {
845 return nullptr;
846 }
847 }
848 return array;
849 }
850
851 bool
iterateObjects(void * refcon,bool (* callback)(void * refcon,const OSSymbol * key,OSObject * object))852 OSDictionary::iterateObjects(void * refcon, bool (*callback)(void * refcon, const OSSymbol * key, OSObject * object))
853 {
854 unsigned int initialUpdateStamp;
855 bool done;
856
857 initialUpdateStamp = updateStamp;
858 done = false;
859 for (unsigned int i = 0; i < count; i++) {
860 done = callback(refcon, dictionary[i].key.get(), EXT_CAST(dictionary[i].value.get()));
861 if (done) {
862 break;
863 }
864 if (initialUpdateStamp != updateStamp) {
865 break;
866 }
867 }
868
869 return initialUpdateStamp == updateStamp;
870 }
871
872 static bool
OSDictionaryIterateObjectsBlock(void * refcon,const OSSymbol * key,OSObject * object)873 OSDictionaryIterateObjectsBlock(void * refcon, const OSSymbol * key, OSObject * object)
874 {
875 bool (^block)(const OSSymbol * key, OSObject * object) = (typeof(block))refcon;
876 return block(key, object);
877 }
878
879 bool
880 OSDictionary::iterateObjects(bool (^block)(const OSSymbol * key, OSObject * object))
881 {
882 return iterateObjects((void *)block, &OSDictionaryIterateObjectsBlock);
883 }
884