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