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