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