--- xnu/xnu-1228/libkern/c++/OSDictionary.cpp
+++ xnu/xnu-2050.9.2/libkern/c++/OSDictionary.cpp
@@ -68,6 +68,8 @@
 
     int size = inCapacity * sizeof(dictEntry);
 
+//fOptions |= kSort;
+
     dictionary = (dictEntry *) kalloc(size);
     if (!dictionary)
         return false;
@@ -87,7 +89,7 @@
                                    unsigned int theCount,
                                    unsigned int theCapacity)
 {
-    unsigned int capacity = theCount;
+    unsigned int newCapacity = theCount;
 
     if (!objects || !keys)
         return false;
@@ -96,10 +98,10 @@
         if (theCount > theCapacity)
             return false;
         
-        capacity = theCapacity;
-    }
-
-    if (!initWithCapacity(capacity))
+        newCapacity = theCapacity;
+    }
+
+    if (!initWithCapacity(newCapacity))
         return false;
 
     for (unsigned int i = 0; i < theCount; i++) {
@@ -117,7 +119,7 @@
                                    unsigned int theCount,
                                    unsigned int theCapacity)
 {
-    unsigned int capacity = theCount;
+    unsigned int newCapacity = theCount;
 
     if (!objects || !keys)
         return false;
@@ -126,10 +128,10 @@
         if (theCount > theCapacity)
             return false;
 
-        capacity = theCapacity;
-    }
-
-    if (!initWithCapacity(capacity))
+        newCapacity = theCapacity;
+    }
+
+    if (!initWithCapacity(newCapacity))
         return false;
 
     for (unsigned int i = 0; i < theCount; i++) {
@@ -153,22 +155,31 @@
 bool OSDictionary::initWithDictionary(const OSDictionary *dict,
                                       unsigned int theCapacity)
 {
-    unsigned int capacity;
+    unsigned int newCapacity;
 
     if ( !dict )
         return false;
 
-    capacity = dict->count;
+    newCapacity = dict->count;
 
     if ( theCapacity ) {
         if ( dict->count > theCapacity )
             return false;
         
-        capacity = theCapacity;
-    }
-
-    if (!initWithCapacity(capacity))
-        return false;
+        newCapacity = theCapacity;
+    }
+
+    if (!initWithCapacity(newCapacity))
+        return false;
+
+    if ((kSort & fOptions) && !(kSort & dict->fOptions)) {
+	for (unsigned int i = 0; i < dict->count; i++) {
+	    if (!setObject(dict->dictionary[i].key, dict->dictionary[i].value)) {
+		return false;
+	    }
+	}
+	return true;
+    }
 
     count = dict->count;
     bcopy(dict->dictionary, dictionary, count * sizeof(dictEntry));
@@ -306,34 +317,45 @@
 bool OSDictionary::
 setObject(const OSSymbol *aKey, const OSMetaClassBase *anObject)
 {
+    unsigned int i;
+    bool exists;
+
     if (!anObject || !aKey)
         return false;
 
     // if the key exists, replace the object
-    for (unsigned int i = 0; i < count; i++) {
-        if (aKey == dictionary[i].key) {
-            const OSMetaClassBase *oldObject = dictionary[i].value;
-
-            haveUpdated();
-
-            anObject->taggedRetain(OSTypeID(OSCollection));
-            dictionary[i].value = anObject;
-
-            oldObject->taggedRelease(OSTypeID(OSCollection));
-            return true;
-        }
+
+    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) {
+	const OSMetaClassBase *oldObject = dictionary[i].value;
+    
+	haveUpdated();
+    
+	anObject->taggedRetain(OSTypeID(OSCollection));
+	dictionary[i].value = anObject;
+    
+	oldObject->taggedRelease(OSTypeID(OSCollection));
+	return true;
     }
 
     // add new key, possibly extending our capacity
     if (count >= capacity && count >= ensureCapacity(count+1))
-        return 0;
+        return false;
 
     haveUpdated();
+
+    bcopy(&dictionary[i], &dictionary[i+1], (count - i) * sizeof(dictionary[0]));
 
     aKey->taggedRetain(OSTypeID(OSCollection));
     anObject->taggedRetain(OSTypeID(OSCollection));
-    dictionary[count].key = aKey;
-    dictionary[count].value = anObject;
+    dictionary[i].key = aKey;
+    dictionary[i].value = anObject;
     count++;
 
     return true;
@@ -341,24 +363,33 @@
 
 void OSDictionary::removeObject(const OSSymbol *aKey)
 {
+    unsigned int i;
+    bool exists;
+
     if (!aKey)
         return;
 
     // if the key exists, remove the object
-    for (unsigned int i = 0; i < count; i++)
-        if (aKey == dictionary[i].key) {
-            dictEntry oldEntry = dictionary[i];
-
-            haveUpdated();
-
-            count--;
-            for (; i < count; i++)
-                dictionary[i] = dictionary[i+1];
-
-            oldEntry.key->taggedRelease(OSTypeID(OSCollection));
-            oldEntry.value->taggedRelease(OSTypeID(OSCollection));
-            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;
+    }
 }
 
 
@@ -371,7 +402,7 @@
     if ( !OSDynamicCast(OSDictionary, srcDict) )
         return false;
 
-    iter = OSCollectionIterator::withCollection((OSDictionary *)srcDict);
+    iter = OSCollectionIterator::withCollection(const_cast<OSDictionary *>(srcDict));
     if ( !iter )
         return false;
 
@@ -391,13 +422,24 @@
 
 OSObject *OSDictionary::getObject(const OSSymbol *aKey) const
 {
+    unsigned int i;
+    bool exists;
+
     if (!aKey)
         return 0;
 
-    // if the key exists, remove the object
-    for (unsigned int i = 0; i < count; i++)
-        if (aKey == dictionary[i].key)
-            return (OSObject *) dictionary[i].value;
+    // if the key exists, return the object
+
+    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) {
+	return (const_cast<OSObject *> ((const OSObject *)dictionary[i].value));
+    }
 
     return 0;
 }