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