#include <libkern/c++/OSDictionary.h>
#include <libkern/c++/OSArray.h>
#include <libkern/c++/OSSymbol.h>
#include <libkern/c++/OSSerialize.h>
#include <libkern/c++/OSLib.h>
#include <libkern/c++/OSCollectionIterator.h>
#define super OSCollection
OSDefineMetaClassAndStructors(OSDictionary, OSCollection)
OSMetaClassDefineReservedUnused(OSDictionary, 0);
OSMetaClassDefineReservedUnused(OSDictionary, 1);
OSMetaClassDefineReservedUnused(OSDictionary, 2);
OSMetaClassDefineReservedUnused(OSDictionary, 3);
OSMetaClassDefineReservedUnused(OSDictionary, 4);
OSMetaClassDefineReservedUnused(OSDictionary, 5);
OSMetaClassDefineReservedUnused(OSDictionary, 6);
OSMetaClassDefineReservedUnused(OSDictionary, 7);
#define EXT_CAST(obj) \
reinterpret_cast<OSObject *>(const_cast<OSMetaClassBase *>(obj))
extern "C" {
void qsort(void *, size_t, size_t, int (*)(const void *, const void *));
}
int
OSDictionary::dictEntry::compare(const void *_e1, const void *_e2)
{
const OSDictionary::dictEntry *e1 = (const OSDictionary::dictEntry *)_e1;
const OSDictionary::dictEntry *e2 = (const OSDictionary::dictEntry *)_e2;
if ((uintptr_t)e1->key == (uintptr_t)e2->key) {
return 0;
}
return (uintptr_t)e1->key > (uintptr_t)e2->key ? 1 : -1;
}
void
OSDictionary::sortBySymbol(void)
{
qsort(dictionary, count, sizeof(OSDictionary::dictEntry),
&OSDictionary::dictEntry::compare);
}
bool
OSDictionary::initWithCapacity(unsigned int inCapacity)
{
if (!super::init()) {
return false;
}
if (inCapacity > (UINT_MAX / sizeof(dictEntry))) {
return false;
}
unsigned int size = inCapacity * sizeof(dictEntry);
dictionary = (dictEntry *) kalloc_container(size);
if (!dictionary) {
return false;
}
bzero(dictionary, size);
OSCONTAINER_ACCUMSIZE(size);
count = 0;
capacity = inCapacity;
capacityIncrement = (inCapacity)? inCapacity : 16;
return true;
}
bool
OSDictionary::initWithObjects(const OSObject *objects[],
const OSSymbol *keys[],
unsigned int theCount,
unsigned int theCapacity)
{
unsigned int newCapacity = theCount;
if (!objects || !keys) {
return false;
}
if (theCapacity) {
if (theCount > theCapacity) {
return false;
}
newCapacity = theCapacity;
}
if (!initWithCapacity(newCapacity)) {
return false;
}
for (unsigned int i = 0; i < theCount; i++) {
const OSMetaClassBase *newObject = *objects++;
if (!newObject || !keys[i] || !setObject(keys[i], newObject)) {
return false;
}
}
return true;
}
bool
OSDictionary::initWithObjects(const OSObject *objects[],
const OSString *keys[],
unsigned int theCount,
unsigned int theCapacity)
{
unsigned int newCapacity = theCount;
if (!objects || !keys) {
return false;
}
if (theCapacity) {
if (theCount > theCapacity) {
return false;
}
newCapacity = theCapacity;
}
if (!initWithCapacity(newCapacity)) {
return false;
}
for (unsigned int i = 0; i < theCount; i++) {
const OSSymbol *key = OSSymbol::withString(*keys++);
const OSMetaClassBase *newObject = *objects++;
if (!key) {
return false;
}
if (!newObject || !setObject(key, newObject)) {
key->release();
return false;
}
key->release();
}
return true;
}
bool
OSDictionary::initWithDictionary(const OSDictionary *dict,
unsigned int theCapacity)
{
unsigned int newCapacity;
if (!dict) {
return false;
}
newCapacity = dict->count;
if (theCapacity) {
if (dict->count > theCapacity) {
return false;
}
newCapacity = theCapacity;
}
if (!initWithCapacity(newCapacity)) {
return false;
}
count = dict->count;
bcopy(dict->dictionary, dictionary, count * sizeof(dictEntry));
for (unsigned int i = 0; i < count; i++) {
dictionary[i].key->taggedRetain(OSTypeID(OSCollection));
dictionary[i].value->taggedRetain(OSTypeID(OSCollection));
}
if ((kSort & fOptions) && !(kSort & dict->fOptions)) {
sortBySymbol();
}
return true;
}
OSDictionary *
OSDictionary::withCapacity(unsigned int capacity)
{
OSDictionary *me = new OSDictionary;
if (me && !me->initWithCapacity(capacity)) {
me->release();
return NULL;
}
return me;
}
OSDictionary *
OSDictionary::withObjects(const OSObject *objects[],
const OSSymbol *keys[],
unsigned int count,
unsigned int capacity)
{
OSDictionary *me = new OSDictionary;
if (me && !me->initWithObjects(objects, keys, count, capacity)) {
me->release();
return NULL;
}
return me;
}
OSDictionary *
OSDictionary::withObjects(const OSObject *objects[],
const OSString *keys[],
unsigned int count,
unsigned int capacity)
{
OSDictionary *me = new OSDictionary;
if (me && !me->initWithObjects(objects, keys, count, capacity)) {
me->release();
return NULL;
}
return me;
}
OSDictionary *
OSDictionary::withDictionary(const OSDictionary *dict,
unsigned int capacity)
{
OSDictionary *me = new OSDictionary;
if (me && !me->initWithDictionary(dict, capacity)) {
me->release();
return NULL;
}
return me;
}
void
OSDictionary::free()
{
(void) super::setOptions(0, kImmutable);
flushCollection();
if (dictionary) {
kfree(dictionary, capacity * sizeof(dictEntry));
OSCONTAINER_ACCUMSIZE( -(capacity * sizeof(dictEntry)));
}
super::free();
}
unsigned int
OSDictionary::getCount() const
{
return count;
}
unsigned int
OSDictionary::getCapacity() const
{
return capacity;
}
unsigned int
OSDictionary::getCapacityIncrement() const
{
return capacityIncrement;
}
unsigned int
OSDictionary::setCapacityIncrement(unsigned int increment)
{
capacityIncrement = (increment)? increment : 16;
return capacityIncrement;
}
unsigned int
OSDictionary::ensureCapacity(unsigned int newCapacity)
{
dictEntry *newDict;
unsigned int finalCapacity;
vm_size_t oldSize, newSize;
if (newCapacity <= capacity) {
return capacity;
}
finalCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
* capacityIncrement;
if (finalCapacity < newCapacity || (finalCapacity > (UINT_MAX / sizeof(dictEntry)))) {
return capacity;
}
newSize = sizeof(dictEntry) * finalCapacity;
newDict = (dictEntry *) kallocp_container(&newSize);
if (newDict) {
finalCapacity = newSize / sizeof(dictEntry);
oldSize = sizeof(dictEntry) * capacity;
bcopy(dictionary, newDict, oldSize);
bzero(&newDict[capacity], newSize - oldSize);
OSCONTAINER_ACCUMSIZE(((size_t)newSize) - ((size_t)oldSize));
kfree(dictionary, oldSize);
dictionary = newDict;
capacity = finalCapacity;
}
return capacity;
}
void
OSDictionary::flushCollection()
{
haveUpdated();
for (unsigned int i = 0; i < count; i++) {
dictionary[i].key->taggedRelease(OSTypeID(OSCollection));
dictionary[i].value->taggedRelease(OSTypeID(OSCollection));
}
count = 0;
}
bool
OSDictionary::
setObject(const OSSymbol *aKey, const OSMetaClassBase *anObject, bool onlyAdd)
{
unsigned int i;
bool exists;
if (!anObject || !aKey) {
return false;
}
if (fOptions & kSort) {
i = OSSymbol::bsearch(aKey, &dictionary[0], count, sizeof(dictionary[0]));
exists = (i < count) && (aKey == dictionary[i].key);
} else {
for (exists = false, i = 0; i < count; i++) {
if ((exists = (aKey == dictionary[i].key))) {
break;
}
}
}
if (exists) {
if (onlyAdd) {
return false;
}
const OSMetaClassBase *oldObject = dictionary[i].value;
haveUpdated();
anObject->taggedRetain(OSTypeID(OSCollection));
dictionary[i].value = anObject;
oldObject->taggedRelease(OSTypeID(OSCollection));
return true;
}
if (count >= capacity && count >= ensureCapacity(count + 1)) {
return false;
}
haveUpdated();
bcopy(&dictionary[i], &dictionary[i + 1], (count - i) * sizeof(dictionary[0]));
aKey->taggedRetain(OSTypeID(OSCollection));
anObject->taggedRetain(OSTypeID(OSCollection));
dictionary[i].key = aKey;
dictionary[i].value = anObject;
count++;
return true;
}
bool
OSDictionary::
setObject(const OSSymbol *aKey, const OSMetaClassBase *anObject)
{
return setObject(aKey, anObject, false);
}
void
OSDictionary::removeObject(const OSSymbol *aKey)
{
unsigned int i;
bool exists;
if (!aKey) {
return;
}
if (fOptions & kSort) {
i = OSSymbol::bsearch(aKey, &dictionary[0], count, sizeof(dictionary[0]));
exists = (i < count) && (aKey == dictionary[i].key);
} else {
for (exists = false, i = 0; i < count; i++) {
if ((exists = (aKey == dictionary[i].key))) {
break;
}
}
}
if (exists) {
dictEntry oldEntry = dictionary[i];
haveUpdated();
count--;
bcopy(&dictionary[i + 1], &dictionary[i], (count - i) * sizeof(dictionary[0]));
oldEntry.key->taggedRelease(OSTypeID(OSCollection));
oldEntry.value->taggedRelease(OSTypeID(OSCollection));
return;
}
}
bool
OSDictionary::merge(const OSDictionary *srcDict)
{
const OSSymbol * sym;
OSCollectionIterator * iter;
if (!OSDynamicCast(OSDictionary, srcDict)) {
return false;
}
iter = OSCollectionIterator::withCollection(const_cast<OSDictionary *>(srcDict));
if (!iter) {
return false;
}
while ((sym = (const OSSymbol *)iter->getNextObject())) {
const OSMetaClassBase * obj;
obj = srcDict->getObject(sym);
if (!setObject(sym, obj)) {
iter->release();
return false;
}
}
iter->release();
return true;
}
OSObject *
OSDictionary::getObject(const OSSymbol *aKey) const
{
unsigned int i, l = 0, r = count;
if (!aKey) {
return NULL;
}
if (count > 4 && (fOptions & kSort)) {
while (l < r) {
i = (l + r) / 2;
if (aKey == dictionary[i].key) {
return const_cast<OSObject *> ((const OSObject *)dictionary[i].value);
}
if ((uintptr_t)aKey < (uintptr_t)dictionary[i].key) {
r = i;
} else {
l = i + 1;
}
}
} else {
for (i = l; i < r; i++) {
if (aKey == dictionary[i].key) {
return const_cast<OSObject *> ((const OSObject *)dictionary[i].value);
}
}
}
return NULL;
}
#define OBJECT_WRAP_1(cmd, k) \
{ \
const OSSymbol *tmpKey = k; \
OSObject *retObj = NULL; \
if (tmpKey) { \
retObj = cmd(tmpKey); \
tmpKey->release(); \
} \
return retObj; \
}
#define OBJECT_WRAP_2(cmd, k, o) \
{ \
const OSSymbol *tmpKey = k; \
bool ret = cmd(tmpKey, o); \
\
tmpKey->release(); \
return ret; \
}
#define OBJECT_WRAP_3(cmd, k) \
{ \
const OSSymbol *tmpKey = k; \
if (tmpKey) { \
cmd(tmpKey); \
tmpKey->release(); \
} \
}
bool
OSDictionary::setObject(const OSString *aKey, const OSMetaClassBase *anObject)
OBJECT_WRAP_2(setObject, OSSymbol::withString(aKey), anObject)
bool
OSDictionary::setObject(const char *aKey, const OSMetaClassBase *anObject)
OBJECT_WRAP_2(setObject, OSSymbol::withCString(aKey), anObject)
OSObject *OSDictionary::getObject(const OSString * aKey) const
OBJECT_WRAP_1(getObject, OSSymbol::existingSymbolForString(aKey))
OSObject *OSDictionary::getObject(const char *aKey) const
OBJECT_WRAP_1(getObject, OSSymbol::existingSymbolForCString(aKey))
void
OSDictionary::removeObject(const OSString *aKey)
OBJECT_WRAP_3(removeObject, OSSymbol::existingSymbolForString(aKey))
void
OSDictionary::removeObject(const char *aKey)
OBJECT_WRAP_3(removeObject, OSSymbol::existingSymbolForCString(aKey))
bool
OSDictionary::isEqualTo(const OSDictionary *srcDict, const OSCollection *keys) const
{
OSCollectionIterator * iter;
unsigned int keysCount;
const OSMetaClassBase * obj1;
const OSMetaClassBase * obj2;
OSString * aKey;
bool ret;
if (this == srcDict) {
return true;
}
keysCount = keys->getCount();
if ((count < keysCount) || (srcDict->getCount() < keysCount)) {
return false;
}
iter = OSCollectionIterator::withCollection(keys);
if (!iter) {
return false;
}
ret = true;
while ((aKey = OSDynamicCast(OSString, iter->getNextObject()))) {
obj1 = getObject(aKey);
obj2 = srcDict->getObject(aKey);
if (!obj1 || !obj2) {
ret = false;
break;
}
if (!obj1->isEqualTo(obj2)) {
ret = false;
break;
}
}
iter->release();
return ret;
}
bool
OSDictionary::isEqualTo(const OSDictionary *srcDict) const
{
unsigned int i;
const OSMetaClassBase * obj;
if (this == srcDict) {
return true;
}
if (count != srcDict->getCount()) {
return false;
}
for (i = 0; i < count; i++) {
obj = srcDict->getObject(dictionary[i].key);
if (!obj) {
return false;
}
if (!dictionary[i].value->isEqualTo(obj)) {
return false;
}
}
return true;
}
bool
OSDictionary::isEqualTo(const OSMetaClassBase *anObject) const
{
OSDictionary *dict;
dict = OSDynamicCast(OSDictionary, anObject);
if (dict) {
return isEqualTo(dict);
} else {
return false;
}
}
unsigned int
OSDictionary::iteratorSize() const
{
return sizeof(unsigned int);
}
bool
OSDictionary::initIterator(void *inIterator) const
{
unsigned int *iteratorP = (unsigned int *) inIterator;
*iteratorP = 0;
return true;
}
bool
OSDictionary::getNextObjectForIterator(void *inIterator, OSObject **ret) const
{
unsigned int *iteratorP = (unsigned int *) inIterator;
unsigned int index = (*iteratorP)++;
if (index < count) {
*ret = (OSObject *) dictionary[index].key;
} else {
*ret = NULL;
}
return *ret != NULL;
}
bool
OSDictionary::serialize(OSSerialize *s) const
{
if (s->previouslySerialized(this)) {
return true;
}
if (!s->addXMLStartTag(this, "dict")) {
return false;
}
for (unsigned i = 0; i < count; i++) {
const OSSymbol *key = dictionary[i].key;
if (!key->metaCast("OSSymbol")) {
return false;
}
if (!s->addString("<key>")) {
return false;
}
const char *c = key->getCStringNoCopy();
while (*c) {
if (*c == '<') {
if (!s->addString("<")) {
return false;
}
} else if (*c == '>') {
if (!s->addString(">")) {
return false;
}
} else if (*c == '&') {
if (!s->addString("&")) {
return false;
}
} else {
if (!s->addChar(*c)) {
return false;
}
}
c++;
}
if (!s->addXMLEndTag("key")) {
return false;
}
if (!dictionary[i].value->serialize(s)) {
return false;
}
}
return s->addXMLEndTag("dict");
}
unsigned
OSDictionary::setOptions(unsigned options, unsigned mask, void *)
{
unsigned old = super::setOptions(options, mask);
if ((old ^ options) & mask) {
for (unsigned i = 0; i < count; i++) {
OSCollection *v = OSDynamicCast(OSCollection, dictionary[i].value);
if (v) {
v->setOptions(options, mask);
}
}
}
if (!(old & kSort) && (fOptions & kSort)) {
sortBySymbol();
}
return old;
}
OSCollection *
OSDictionary::copyCollection(OSDictionary *cycleDict)
{
bool allocDict = !cycleDict;
OSCollection *ret = NULL;
OSDictionary *newDict = NULL;
if (allocDict) {
cycleDict = OSDictionary::withCapacity(16);
if (!cycleDict) {
return NULL;
}
}
do {
ret = super::copyCollection(cycleDict);
if (ret) {
continue;
}
newDict = OSDictionary::withDictionary(this);
if (!newDict) {
continue;
}
cycleDict->setObject((const OSSymbol *) this, newDict);
for (unsigned int i = 0; i < count; i++) {
const OSMetaClassBase *obj = dictionary[i].value;
OSCollection *coll = OSDynamicCast(OSCollection, EXT_CAST(obj));
if (coll) {
OSCollection *newColl = coll->copyCollection(cycleDict);
if (!newColl) {
goto abortCopy;
}
newDict->dictionary[i].value = newColl;
coll->taggedRelease(OSTypeID(OSCollection));
newColl->taggedRetain(OSTypeID(OSCollection));
newColl->release();
}
;
}
ret = newDict;
newDict = NULL;
} while (false);
abortCopy:
if (newDict) {
newDict->release();
}
if (allocDict) {
cycleDict->release();
}
return ret;
}
OSArray *
OSDictionary::copyKeys(void)
{
OSArray * array;
array = OSArray::withCapacity(count);
if (!array) {
return NULL;
}
for (unsigned int i = 0; i < count; i++) {
if (!array->setObject(i, dictionary[i].key)) {
array->release();
array = NULL;
break;
}
}
return array;
}
bool
OSDictionary::iterateObjects(void * refcon, bool (*callback)(void * refcon, const OSSymbol * key, OSObject * object))
{
unsigned int initialUpdateStamp;
bool done;
initialUpdateStamp = updateStamp;
done = false;
for (unsigned int i = 0; i < count; i++) {
done = callback(refcon, dictionary[i].key, EXT_CAST(dictionary[i].value));
if (done) {
break;
}
if (initialUpdateStamp != updateStamp) {
break;
}
}
return initialUpdateStamp == updateStamp;
}
static bool
OSDictionaryIterateObjectsBlock(void * refcon, const OSSymbol * key, OSObject * object)
{
bool (^block)(const OSSymbol * key, OSObject * object) = (typeof(block))refcon;
return block(key, object);
}
bool
OSDictionary::iterateObjects(bool (^block)(const OSSymbol * key, OSObject * object))
{
return iterateObjects((void *)block, &OSDictionaryIterateObjectsBlock);
}