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
33#include <libkern/c++/OSDictionary.h>
34#include <libkern/c++/OSArray.h>
35#include <libkern/c++/OSSymbol.h>
36#include <libkern/c++/OSSerialize.h>
37#include <libkern/c++/OSLib.h>
38#include <libkern/c++/OSCollectionIterator.h>
39
40#define super OSCollection
41
42OSDefineMetaClassAndStructors(OSDictionary, OSCollection)
43OSMetaClassDefineReservedUnused(OSDictionary, 0);
44OSMetaClassDefineReservedUnused(OSDictionary, 1);
45OSMetaClassDefineReservedUnused(OSDictionary, 2);
46OSMetaClassDefineReservedUnused(OSDictionary, 3);
47OSMetaClassDefineReservedUnused(OSDictionary, 4);
48OSMetaClassDefineReservedUnused(OSDictionary, 5);
49OSMetaClassDefineReservedUnused(OSDictionary, 6);
50OSMetaClassDefineReservedUnused(OSDictionary, 7);
51
52#define EXT_CAST(obj) \
53 reinterpret_cast<OSObject *>(const_cast<OSMetaClassBase *>(obj))
54
55bool OSDictionary::initWithCapacity(unsigned int inCapacity)
56{
57 if (!super::init())
58 return false;
59
60 if (inCapacity > (UINT_MAX / sizeof(dictEntry)))
61 return false;
62
63 unsigned int size = inCapacity * sizeof(dictEntry);
64//fOptions |= kSort;
65
66 dictionary = (dictEntry *) kalloc_container(size);
67 if (!dictionary)
68 return false;
69
70 bzero(dictionary, size);
71 OSCONTAINER_ACCUMSIZE(size);
72
73 count = 0;
74 capacity = inCapacity;
75 capacityIncrement = (inCapacity)? inCapacity : 16;
76
77 return true;
78}
79
80bool OSDictionary::initWithObjects(const OSObject *objects[],
81 const OSSymbol *keys[],
82 unsigned int theCount,
83 unsigned int theCapacity)
84{
85 unsigned int newCapacity = theCount;
86
87 if (!objects || !keys)
88 return false;
89
90 if ( theCapacity ) {
91 if (theCount > theCapacity)
92 return false;
93
94 newCapacity = theCapacity;
95 }
96
97 if (!initWithCapacity(newCapacity))
98 return false;
99
100 for (unsigned int i = 0; i < theCount; i++) {
101 const OSMetaClassBase *newObject = *objects++;
102
103 if (!newObject || !keys[i] || !setObject(keys[i], newObject))
104 return false;
105 }
106
107 return true;
108}
109
110bool OSDictionary::initWithObjects(const OSObject *objects[],
111 const OSString *keys[],
112 unsigned int theCount,
113 unsigned int theCapacity)
114{
115 unsigned int newCapacity = theCount;
116
117 if (!objects || !keys)
118 return false;
119
120 if ( theCapacity ) {
121 if (theCount > theCapacity)
122 return false;
123
124 newCapacity = theCapacity;
125 }
126
127 if (!initWithCapacity(newCapacity))
128 return false;
129
130 for (unsigned int i = 0; i < theCount; i++) {
131 const OSSymbol *key = OSSymbol::withString(*keys++);
132 const OSMetaClassBase *newObject = *objects++;
133
134 if (!key)
135 return false;
136
137 if (!newObject || !setObject(key, newObject)) {
138 key->release();
139 return false;
140 }
141
142 key->release();
143 }
144
145 return true;
146}
147
148bool OSDictionary::initWithDictionary(const OSDictionary *dict,
149 unsigned int theCapacity)
150{
151 unsigned int newCapacity;
152
153 if ( !dict )
154 return false;
155
156 newCapacity = dict->count;
157
158 if ( theCapacity ) {
159 if ( dict->count > theCapacity )
160 return false;
161
162 newCapacity = theCapacity;
163 }
164
165 if (!initWithCapacity(newCapacity))
166 return false;
167
168 if ((kSort & fOptions) && !(kSort & dict->fOptions)) {
169 for (unsigned int i = 0; i < dict->count; i++) {
170 if (!setObject(dict->dictionary[i].key, dict->dictionary[i].value)) {
171 return false;
172 }
173 }
174 return true;
175 }
176
177 count = dict->count;
178 bcopy(dict->dictionary, dictionary, count * sizeof(dictEntry));
179 for (unsigned int i = 0; i < count; i++) {
180 dictionary[i].key->taggedRetain(OSTypeID(OSCollection));
181 dictionary[i].value->taggedRetain(OSTypeID(OSCollection));
182 }
183
184 return true;
185}
186
187OSDictionary *OSDictionary::withCapacity(unsigned int capacity)
188{
189 OSDictionary *me = new OSDictionary;
190
191 if (me && !me->initWithCapacity(capacity)) {
192 me->release();
193 return 0;
194 }
195
196 return me;
197}
198
199OSDictionary *OSDictionary::withObjects(const OSObject *objects[],
200 const OSSymbol *keys[],
201 unsigned int count,
202 unsigned int capacity)
203{
204 OSDictionary *me = new OSDictionary;
205
206 if (me && !me->initWithObjects(objects, keys, count, capacity)) {
207 me->release();
208 return 0;
209 }
210
211 return me;
212}
213
214OSDictionary *OSDictionary::withObjects(const OSObject *objects[],
215 const OSString *keys[],
216 unsigned int count,
217 unsigned int capacity)
218{
219 OSDictionary *me = new OSDictionary;
220
221 if (me && !me->initWithObjects(objects, keys, count, capacity)) {
222 me->release();
223 return 0;
224 }
225
226 return me;
227}
228
229OSDictionary *OSDictionary::withDictionary(const OSDictionary *dict,
230 unsigned int capacity)
231{
232 OSDictionary *me = new OSDictionary;
233
234 if (me && !me->initWithDictionary(dict, capacity)) {
235 me->release();
236 return 0;
237 }
238
239 return me;
240}
241
242void OSDictionary::free()
243{
244 (void) super::setOptions(0, kImmutable);
245 flushCollection();
246 if (dictionary) {
247 kfree(dictionary, capacity * sizeof(dictEntry));
248 OSCONTAINER_ACCUMSIZE( -(capacity * sizeof(dictEntry)) );
249 }
250
251 super::free();
252}
253
254unsigned int OSDictionary::getCount() const { return count; }
255unsigned int OSDictionary::getCapacity() const { return capacity; }
256
257unsigned int OSDictionary::getCapacityIncrement() const
258{
259 return capacityIncrement;
260}
261
262unsigned int OSDictionary::setCapacityIncrement(unsigned int increment)
263{
264 capacityIncrement = (increment)? increment : 16;
265
266 return capacityIncrement;
267}
268
269unsigned int OSDictionary::ensureCapacity(unsigned int newCapacity)
270{
271 dictEntry *newDict;
272 unsigned int finalCapacity;
273 vm_size_t oldSize, newSize;
274
275 if (newCapacity <= capacity)
276 return capacity;
277
278 // round up
279 finalCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
280 * capacityIncrement;
281
282 // integer overflow check
283 if (finalCapacity < newCapacity || (finalCapacity > (UINT_MAX / sizeof(dictEntry))))
284 return capacity;
285
286 newSize = sizeof(dictEntry) * finalCapacity;
287
288 newDict = (dictEntry *) kallocp_container(&newSize);
289 if (newDict) {
290 // use all of the actual allocation size
291 finalCapacity = newSize / sizeof(dictEntry);
292
293 oldSize = sizeof(dictEntry) * capacity;
294
295 bcopy(dictionary, newDict, oldSize);
296 bzero(&newDict[capacity], newSize - oldSize);
297
298 OSCONTAINER_ACCUMSIZE(((size_t)newSize) - ((size_t)oldSize));
299 kfree(dictionary, oldSize);
300
301 dictionary = newDict;
302 capacity = finalCapacity;
303 }
304
305 return capacity;
306}
307
308void OSDictionary::flushCollection()
309{
310 haveUpdated();
311
312 for (unsigned int i = 0; i < count; i++) {
313 dictionary[i].key->taggedRelease(OSTypeID(OSCollection));
314 dictionary[i].value->taggedRelease(OSTypeID(OSCollection));
315 }
316 count = 0;
317}
318
319bool OSDictionary::
320setObject(const OSSymbol *aKey, const OSMetaClassBase *anObject, bool onlyAdd)
321{
322 unsigned int i;
323 bool exists;
324
325 if (!anObject || !aKey)
326 return false;
327
328 // if the key exists, replace the object
329
330 if (fOptions & kSort) {
331 i = OSSymbol::bsearch(aKey, &dictionary[0], count, sizeof(dictionary[0]));
332 exists = (i < count) && (aKey == dictionary[i].key);
333 } else for (exists = false, i = 0; i < count; i++) {
334 if ((exists = (aKey == dictionary[i].key))) break;
335 }
336
337 if (exists) {
338
339 if (onlyAdd) return false;
340
341 const OSMetaClassBase *oldObject = dictionary[i].value;
342
343 haveUpdated();
344
345 anObject->taggedRetain(OSTypeID(OSCollection));
346 dictionary[i].value = anObject;
347
348 oldObject->taggedRelease(OSTypeID(OSCollection));
349 return true;
350 }
351
352 // add new key, possibly extending our capacity
353 if (count >= capacity && count >= ensureCapacity(count+1))
354 return false;
355
356 haveUpdated();
357
358 bcopy(&dictionary[i], &dictionary[i+1], (count - i) * sizeof(dictionary[0]));
359
360 aKey->taggedRetain(OSTypeID(OSCollection));
361 anObject->taggedRetain(OSTypeID(OSCollection));
362 dictionary[i].key = aKey;
363 dictionary[i].value = anObject;
364 count++;
365
366 return true;
367}
368
369bool OSDictionary::
370setObject(const OSSymbol *aKey, const OSMetaClassBase *anObject)
371{
372 return (setObject(aKey, anObject, false));
373}
374
375void OSDictionary::removeObject(const OSSymbol *aKey)
376{
377 unsigned int i;
378 bool exists;
379
380 if (!aKey)
381 return;
382
383 // if the key exists, remove 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 for (exists = false, i = 0; i < count; i++) {
389 if ((exists = (aKey == dictionary[i].key))) break;
390 }
391
392 if (exists) {
393 dictEntry oldEntry = dictionary[i];
394
395 haveUpdated();
396
397 count--;
398 bcopy(&dictionary[i+1], &dictionary[i], (count - i) * sizeof(dictionary[0]));
399
400 oldEntry.key->taggedRelease(OSTypeID(OSCollection));
401 oldEntry.value->taggedRelease(OSTypeID(OSCollection));
402 return;
403 }
404}
405
406
407// Returns true on success, false on an error condition.
408bool OSDictionary::merge(const OSDictionary *srcDict)
409{
410 const OSSymbol * sym;
411 OSCollectionIterator * iter;
412
413 if ( !OSDynamicCast(OSDictionary, srcDict) )
414 return false;
415
416 iter = OSCollectionIterator::withCollection(const_cast<OSDictionary *>(srcDict));
417 if ( !iter )
418 return false;
419
420 while ( (sym = (const OSSymbol *)iter->getNextObject()) ) {
421 const OSMetaClassBase * obj;
422
423 obj = srcDict->getObject(sym);
424 if ( !setObject(sym, obj) ) {
425 iter->release();
426 return false;
427 }
428 }
429 iter->release();
430
431 return true;
432}
433
434OSObject *OSDictionary::getObject(const OSSymbol *aKey) const
435{
436 unsigned int i;
437 bool exists;
438
439 if (!aKey)
440 return 0;
441
442 // if the key exists, return the object
443
444 if (fOptions & kSort) {
445 i = OSSymbol::bsearch(aKey, &dictionary[0], count, sizeof(dictionary[0]));
446 exists = (i < count) && (aKey == dictionary[i].key);
447 } else for (exists = false, i = 0; i < count; i++) {
448 if ((exists = (aKey == dictionary[i].key))) break;
449 }
450
451 if (exists) {
452 return (const_cast<OSObject *> ((const OSObject *)dictionary[i].value));
453 }
454
455 return 0;
456}
457
458// Wrapper macros
459#define OBJECT_WRAP_1(cmd, k) \
460{ \
461 const OSSymbol *tmpKey = k; \
462 OSObject *retObj = cmd(tmpKey); \
463 \
464 tmpKey->release(); \
465 return retObj; \
466}
467
468#define OBJECT_WRAP_2(cmd, k, o) \
469{ \
470 const OSSymbol *tmpKey = k; \
471 bool ret = cmd(tmpKey, o); \
472 \
473 tmpKey->release(); \
474 return ret; \
475}
476
477#define OBJECT_WRAP_3(cmd, k) \
478{ \
479 const OSSymbol *tmpKey = k; \
480 cmd(tmpKey); \
481 tmpKey->release(); \
482}
483
484
485bool OSDictionary::setObject(const OSString *aKey, const OSMetaClassBase *anObject)
486 OBJECT_WRAP_2(setObject, OSSymbol::withString(aKey), anObject)
487bool OSDictionary::setObject(const char *aKey, const OSMetaClassBase *anObject)
488 OBJECT_WRAP_2(setObject, OSSymbol::withCString(aKey), anObject)
489
490OSObject *OSDictionary::getObject(const OSString *aKey) const
491 OBJECT_WRAP_1(getObject, OSSymbol::withString(aKey))
492OSObject *OSDictionary::getObject(const char *aKey) const
493 OBJECT_WRAP_1(getObject, OSSymbol::withCString(aKey))
494
495void OSDictionary::removeObject(const OSString *aKey)
496 OBJECT_WRAP_3(removeObject, OSSymbol::withString(aKey))
497void OSDictionary::removeObject(const char *aKey)
498 OBJECT_WRAP_3(removeObject, OSSymbol::withCString(aKey))
499
500bool
501OSDictionary::isEqualTo(const OSDictionary *srcDict, const OSCollection *keys) const
502{
503 OSCollectionIterator * iter;
504 unsigned int keysCount;
505 const OSMetaClassBase * obj1;
506 const OSMetaClassBase * obj2;
507 OSString * aKey;
508 bool ret;
509
510 if ( this == srcDict )
511 return true;
512
513 keysCount = keys->getCount();
514 if ( (count < keysCount) || (srcDict->getCount() < keysCount) )
515 return false;
516
517 iter = OSCollectionIterator::withCollection(keys);
518 if ( !iter )
519 return false;
520
521 ret = true;
522 while ( (aKey = OSDynamicCast(OSString, iter->getNextObject())) ) {
523 obj1 = getObject(aKey);
524 obj2 = srcDict->getObject(aKey);
525 if ( !obj1 || !obj2 ) {
526 ret = false;
527 break;
528 }
529
530 if ( !obj1->isEqualTo(obj2) ) {
531 ret = false;
532 break;
533 }
534 }
535 iter->release();
536
537 return ret;
538}
539
540bool OSDictionary::isEqualTo(const OSDictionary *srcDict) const
541{
542 unsigned int i;
543 const OSMetaClassBase * obj;
544
545 if ( this == srcDict )
546 return true;
547
548 if ( count != srcDict->getCount() )
549 return false;
550
551 for ( i = 0; i < count; i++ ) {
552 obj = srcDict->getObject(dictionary[i].key);
553 if ( !obj )
554 return false;
555
556 if ( !dictionary[i].value->isEqualTo(obj) )
557 return false;
558 }
559
560 return true;
561}
562
563bool OSDictionary::isEqualTo(const OSMetaClassBase *anObject) const
564{
565 OSDictionary *dict;
566
567 dict = OSDynamicCast(OSDictionary, anObject);
568 if ( dict )
569 return isEqualTo(dict);
570 else
571 return false;
572}
573
574unsigned int OSDictionary::iteratorSize() const
575{
576 return sizeof(unsigned int);
577}
578
579bool OSDictionary::initIterator(void *inIterator) const
580{
581 unsigned int *iteratorP = (unsigned int *) inIterator;
582
583 *iteratorP = 0;
584 return true;
585}
586
587bool OSDictionary::getNextObjectForIterator(void *inIterator, OSObject **ret) const
588{
589 unsigned int *iteratorP = (unsigned int *) inIterator;
590 unsigned int index = (*iteratorP)++;
591
592 if (index < count)
593 *ret = (OSObject *) dictionary[index].key;
594 else
595 *ret = 0;
596
597 return (*ret != 0);
598}
599
600bool OSDictionary::serialize(OSSerialize *s) const
601{
602 if (s->previouslySerialized(this)) return true;
603
604 if (!s->addXMLStartTag(this, "dict")) return false;
605
606 for (unsigned i = 0; i < count; i++) {
607 const OSSymbol *key = dictionary[i].key;
608
609 // due the nature of the XML syntax, this must be a symbol
610 if (!key->metaCast("OSSymbol")) {
611 return false;
612 }
613 if (!s->addString("<key>")) return false;
614 const char *c = key->getCStringNoCopy();
615 while (*c) {
616 if (*c == '<') {
617 if (!s->addString("&lt;")) return false;
618 } else if (*c == '>') {
619 if (!s->addString("&gt;")) return false;
620 } else if (*c == '&') {
621 if (!s->addString("&amp;")) return false;
622 } else {
623 if (!s->addChar(*c)) return false;
624 }
625 c++;
626 }
627 if (!s->addXMLEndTag("key")) return false;
628
629 if (!dictionary[i].value->serialize(s)) return false;
630 }
631
632 return s->addXMLEndTag("dict");
633}
634
635unsigned OSDictionary::setOptions(unsigned options, unsigned mask, void *)
636{
637 unsigned old = super::setOptions(options, mask);
638 if ((old ^ options) & mask) {
639
640 // Value changed need to recurse over all of the child collections
641 for ( unsigned i = 0; i < count; i++ ) {
642 OSCollection *v = OSDynamicCast(OSCollection, dictionary[i].value);
643 if (v)
644 v->setOptions(options, mask);
645 }
646 }
647
648 return old;
649}
650
651OSCollection * OSDictionary::copyCollection(OSDictionary *cycleDict)
652{
653 bool allocDict = !cycleDict;
654 OSCollection *ret = 0;
655 OSDictionary *newDict = 0;
656
657 if (allocDict) {
658 cycleDict = OSDictionary::withCapacity(16);
659 if (!cycleDict)
660 return 0;
661 }
662
663 do {
664 // Check for a cycle
665 ret = super::copyCollection(cycleDict);
666 if (ret)
667 continue;
668
669 newDict = OSDictionary::withDictionary(this);
670 if (!newDict)
671 continue;
672
673 // Insert object into cycle Dictionary
674 cycleDict->setObject((const OSSymbol *) this, newDict);
675
676 for (unsigned int i = 0; i < count; i++) {
677 const OSMetaClassBase *obj = dictionary[i].value;
678 OSCollection *coll = OSDynamicCast(OSCollection, EXT_CAST(obj));
679
680 if (coll) {
681 OSCollection *newColl = coll->copyCollection(cycleDict);
682 if (!newColl)
683 goto abortCopy;
684
685 newDict->dictionary[i].value = newColl;
686
687 coll->taggedRelease(OSTypeID(OSCollection));
688 newColl->taggedRetain(OSTypeID(OSCollection));
689 newColl->release();
690 };
691 }
692
693 ret = newDict;
694 newDict = 0;
695
696 } while (false);
697
698abortCopy:
699 if (newDict)
700 newDict->release();
701
702 if (allocDict)
703 cycleDict->release();
704
705 return ret;
706}
707
708OSArray * OSDictionary::copyKeys(void)
709{
710 OSArray * array;
711
712 array = OSArray::withCapacity(count);
713 if (!array) return (0);
714
715 for (unsigned int i = 0; i < count; i++)
716 {
717 if (!array->setObject(i, dictionary[i].key))
718 {
719 array->release();
720 array = 0;
721 break;
722 }
723 }
724 return (array);
725}
726
727bool OSDictionary::iterateObjects(void * refcon, bool (*callback)(void * refcon, const OSSymbol * key, OSObject * object))
728{
729 unsigned int initialUpdateStamp;
730 bool done;
731
732 initialUpdateStamp = updateStamp;
733 done = false;
734 for (unsigned int i = 0; i < count; i++)
735 {
736 done = callback(refcon, dictionary[i].key, EXT_CAST(dictionary[i].value));
737 if (done) break;
738 if (initialUpdateStamp != updateStamp) break;
739 }
740
741 return initialUpdateStamp == updateStamp;
742}
743
744static bool OSDictionaryIterateObjectsBlock(void * refcon, const OSSymbol * key, OSObject * object)
745{
746 bool (^block)(const OSSymbol * key, OSObject * object) = (typeof(block)) refcon;
747 return (block(key, object));
748}
749
750bool OSDictionary::iterateObjects(bool (^block)(const OSSymbol * key, OSObject * object))
751{
752 return (iterateObjects((void *)block, &OSDictionaryIterateObjectsBlock));
753}
754