Collections.subproj/CFStorage.c

   1 /*
   2  * Copyright (c) 2005 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_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. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23 /*      CFStorage.c
  24         Copyright 1999-2002, Apple, Inc. All rights reserved.
  25         Responsibility: Ali Ozer
  26 */
  27
  28 /*
  29 2-3 tree storing arbitrary sized values.
  30 ??? Currently elementSize cannot be greater than storage->maxLeafCapacity, which is less than or equal to __CFStorageMaxLeafCapacity
  31 */
  32
  33 #include "CFStorage.h"
  34 #include "CFInternal.h"
  35
  36 #if defined(__MACH__)
  37 #include <mach/mach.h>
  38 #else
  39 enum {
  40     vm_page_size = 4096
  41 };
  42 #endif
  43
  44 enum {
  45     __CFStorageMaxLeafCapacity = 65536
  46 };
  47
  48 #define COPYMEM(src,dst,n) CF_WRITE_BARRIER_MEMMOVE((dst), (src), (n))
  49 #define PAGE_LIMIT ((CFIndex)vm_page_size / 2)
  50
  51 CF_INLINE int roundToPage(int num) {
  52     return (num + vm_page_size - 1) & ~(vm_page_size - 1);
  53 }
  54
  55 typedef struct __CFStorageNode {
  56     CFIndex numBytes;   /* Number of actual bytes in this node and all its children */
  57     bool isLeaf;
  58     union {
  59         struct {
  60             CFIndex capacityInBytes;    // capacityInBytes is capacity of memory; this is either 0, or >= numBytes
  61             uint8_t *memory;
  62         } leaf;
  63         struct {
  64             struct __CFStorageNode *child[3];
  65         } notLeaf;
  66     } info;
  67 } CFStorageNode;
  68
  69 struct __CFStorage {
  70     CFRuntimeBase base;
  71     CFIndex valueSize;
  72     CFRange cachedRange;        // In terms of values, not bytes
  73     CFStorageNode *cachedNode;  // If cachedRange is valid, then either this or
  74     uint8_t *cachedNodeMemory;  //    this should be non-NULL
  75     CFIndex maxLeafCapacity;    // In terms of bytes
  76     CFStorageNode rootNode;
  77     CFOptionFlags nodeHint;     // auto_memory_type_t, AUTO_MEMORY_SCANNED or AUTO_MEMORY_UNSCANNED.
  78 };
  79
  80 /* Allocates the memory and initializes the capacity in a leaf. __CFStorageAllocLeafNodeMemory() is the entry point; __CFStorageAllocLeafNodeMemoryAux is called if actual reallocation is needed.
  81 */
  82 static void __CFStorageAllocLeafNodeMemoryAux(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex cap) {
  83     CF_WRITE_BARRIER_ASSIGN(allocator, node->info.leaf.memory, _CFAllocatorReallocateGC(allocator, node->info.leaf.memory, cap, storage->nodeHint));    // This will free... ??? Use allocator
  84     if (__CFOASafe) __CFSetLastAllocationEventName(node->info.leaf.memory, "CFStorage (node bytes)");
  85     node->info.leaf.capacityInBytes = cap;
  86 }
  87
  88 CF_INLINE void __CFStorageAllocLeafNodeMemory(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex cap, bool compact) {
  89     if (cap > PAGE_LIMIT) {
  90         cap = roundToPage(cap);
  91         if (cap > storage->maxLeafCapacity) cap = storage->maxLeafCapacity;
  92     } else {
  93         cap = (((cap + 63) / 64) * 64);
  94     }
  95     if (compact ? (cap != node->info.leaf.capacityInBytes) : (cap > node->info.leaf.capacityInBytes)) __CFStorageAllocLeafNodeMemoryAux(allocator, storage, node, cap);
  96 }
  97
  98 /* Sets the cache to point at the specified node or memory. loc and len are in terms of values, not bytes. To clear the cache set these two to 0.
  99    At least one of node or memory should be non-NULL. memory is consulted first when using the cache.
 100 */
 101 CF_INLINE void __CFStorageSetCache(CFStorageRef storage, CFStorageNode *node, uint8_t *memory, CFIndex loc, CFIndex len) {
 102     CFAllocatorRef allocator = __CFGetAllocator(storage);
 103     storage->cachedRange.location = loc;
 104     storage->cachedRange.length = len;
 105     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, storage, storage->cachedNode, node);
 106     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, storage, storage->cachedNodeMemory, memory);
 107 }
 108
 109 /* Gets the location for the specified absolute loc from the cached info; call only after verifying that the cache is OK to use.
 110    Note that we assume if !storage->cachedNodeMemory, then storage->cachedNode must be non-NULL.
 111    However, it is possible to have storage->cachedNodeMemory without storage->cachedNode.  We check the memory before node.
 112 */
 113 CF_INLINE uint8_t *__CFStorageGetFromCache(CFStorageRef storage, CFIndex loc) {
 114     if (!storage->cachedNodeMemory && !(storage->cachedNodeMemory = storage->cachedNode->info.leaf.memory)) {
 115         CFAllocatorRef allocator = CFGetAllocator(storage);
 116         __CFStorageAllocLeafNodeMemory(allocator, storage, storage->cachedNode, storage->cachedNode->numBytes, false);
 117         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, storage, storage->cachedNodeMemory, storage->cachedNode->info.leaf.memory);
 118     }
 119     return storage->cachedNodeMemory + (loc - storage->cachedRange.location) * storage->valueSize;
 120 }
 121
 122 /* Returns the number of the child containing the desired value and the relative index of the value in that child.
 123    forInsertion = true means that we are looking for the child in which to insert; this changes the behavior when the index is at the end of a child
 124    relativeByteNum (not optional, for performance reasons) returns the relative byte number of the specified byte in the child.
 125    Don't call with leaf nodes!
 126 */
 127 CF_INLINE void __CFStorageFindChild(CFStorageNode *node, CFIndex byteNum, bool forInsertion, CFIndex *childNum, CFIndex *relativeByteNum) {
 128     if (forInsertion) byteNum--;        /* If for insertion, we do <= checks, not <, so this accomplishes the same thing */
 129     if (byteNum < node->info.notLeaf.child[0]->numBytes) *childNum = 0;
 130     else {
 131         byteNum -= node->info.notLeaf.child[0]->numBytes;
 132         if (byteNum < node->info.notLeaf.child[1]->numBytes) *childNum = 1;
 133         else {
 134             byteNum -= node->info.notLeaf.child[1]->numBytes;
 135             *childNum = 2;
 136         }
 137     }
 138     if (forInsertion) byteNum++;
 139     *relativeByteNum = byteNum;
 140 }
 141
 142 /* Finds the location where the specified byte is stored. If validConsecutiveByteRange is not NULL, returns
 143    the range of bytes that are consecutive with this one.
 144    !!! Assumes the byteNum is within the range of this node.
 145 */
 146 static void *__CFStorageFindByte(CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFRange *validConsecutiveByteRange) {
 147     if (node->isLeaf) {
 148         if (validConsecutiveByteRange) *validConsecutiveByteRange = CFRangeMake(0, node->numBytes);
 149         __CFStorageAllocLeafNodeMemory(CFGetAllocator(storage), storage, node, node->numBytes, false);
 150         return node->info.leaf.memory + byteNum;
 151     } else {
 152         void *result;
 153         CFIndex childNum;
 154         CFIndex relativeByteNum;
 155         __CFStorageFindChild(node, byteNum, false, &childNum, &relativeByteNum);
 156         result = __CFStorageFindByte(storage, node->info.notLeaf.child[childNum], relativeByteNum, validConsecutiveByteRange);
 157         if (validConsecutiveByteRange) {
 158             if (childNum > 0) validConsecutiveByteRange->location += node->info.notLeaf.child[0]->numBytes;
 159             if (childNum > 1) validConsecutiveByteRange->location += node->info.notLeaf.child[1]->numBytes;
 160         }
 161         return result;
 162     }
 163 }
 164
 165 /* Guts of CFStorageGetValueAtIndex(); note that validConsecutiveValueRange is not optional.
 166    Consults and updates cache.
 167 */
 168 CF_INLINE void *__CFStorageGetValueAtIndex(CFStorageRef storage, CFIndex idx, CFRange *validConsecutiveValueRange) {
 169     uint8_t *result;
 170     if (idx < storage->cachedRange.location + storage->cachedRange.length && idx >= storage->cachedRange.location) {
 171         result = __CFStorageGetFromCache(storage, idx);
 172     } else {
 173         CFRange range;
 174         result = __CFStorageFindByte(storage, &storage->rootNode, idx * storage->valueSize, &range);
 175         __CFStorageSetCache(storage, NULL, result - (idx * storage->valueSize - range.location), range.location / storage->valueSize, range.length / storage->valueSize);
 176     }
 177     *validConsecutiveValueRange = storage->cachedRange;
 178     return result;
 179 }
 180
 181 static CFStorageNode *__CFStorageCreateNode(CFAllocatorRef allocator, bool isLeaf, CFIndex numBytes) {
 182     CFStorageNode *newNode = _CFAllocatorAllocateGC(allocator, sizeof(CFStorageNode), 0);
 183     if (__CFOASafe) __CFSetLastAllocationEventName(newNode, "CFStorage (node)");
 184     newNode->isLeaf = isLeaf;
 185     newNode->numBytes = numBytes;
 186     if (isLeaf) {
 187         newNode->info.leaf.capacityInBytes = 0;
 188         newNode->info.leaf.memory = NULL;
 189     } else {
 190         newNode->info.notLeaf.child[0] = newNode->info.notLeaf.child[1] = newNode->info.notLeaf.child[2] = NULL;
 191     }
 192     return newNode;
 193 }
 194
 195 static void __CFStorageNodeDealloc(CFAllocatorRef allocator, CFStorageNode *node, bool freeNodeItself) {
 196     if (node->isLeaf) {
 197         _CFAllocatorDeallocateGC(allocator, node->info.leaf.memory);
 198     } else {
 199         int cnt;
 200         for (cnt = 0; cnt < 3; cnt++) if (node->info.notLeaf.child[cnt]) __CFStorageNodeDealloc(allocator, node->info.notLeaf.child[cnt], true);
 201     }
 202     if (freeNodeItself) _CFAllocatorDeallocateGC(allocator, node);
 203 }
 204
 205 static CFIndex __CFStorageGetNumChildren(CFStorageNode *node) {
 206     if (!node || node->isLeaf) return 0;
 207     if (node->info.notLeaf.child[2]) return 3;
 208     if (node->info.notLeaf.child[1]) return 2;
 209     if (node->info.notLeaf.child[0]) return 1;
 210     return 0;
 211 }
 212
 213 /* The boolean compact indicates whether leaf nodes that get smaller should be realloced.
 214 */
 215 static void __CFStorageDelete(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFRange range, bool compact) {
 216     if (node->isLeaf) {
 217         node->numBytes -= range.length;
 218         // If this node had memory allocated, readjust the bytes...
 219         if (node->info.leaf.memory) {
 220             COPYMEM(node->info.leaf.memory + range.location + range.length, node->info.leaf.memory + range.location, node->numBytes - range.location);
 221             if (compact) __CFStorageAllocLeafNodeMemory(allocator, storage, node, node->numBytes, true);
 222         }
 223    } else {
 224         bool childrenAreLeaves = node->info.notLeaf.child[0]->isLeaf;
 225         node->numBytes -= range.length;
 226         while (range.length > 0) {
 227             CFRange rangeToDelete;
 228             CFIndex relativeByteNum;
 229             CFIndex childNum;
 230             __CFStorageFindChild(node, range.location + range.length, true, &childNum, &relativeByteNum);
 231             if (range.length > relativeByteNum) {
 232                 rangeToDelete.length = relativeByteNum;
 233                 rangeToDelete.location = 0;
 234             } else {
 235                 rangeToDelete.length = range.length;
 236                 rangeToDelete.location = relativeByteNum - range.length;
 237             }
 238             __CFStorageDelete(allocator, storage, node->info.notLeaf.child[childNum], rangeToDelete, compact);
 239             if (node->info.notLeaf.child[childNum]->numBytes == 0) {            // Delete empty node and compact
 240                 int cnt;
 241                 _CFAllocatorDeallocateGC(allocator, node->info.notLeaf.child[childNum]);
 242                 for (cnt = childNum; cnt < 2; cnt++) {
 243                     CF_WRITE_BARRIER_ASSIGN(allocator, node->info.notLeaf.child[cnt], node->info.notLeaf.child[cnt+1]);
 244                 }
 245                 node->info.notLeaf.child[2] = NULL;
 246             }
 247             range.length -= rangeToDelete.length;
 248         }
 249         // At this point the remaining children are packed
 250         if (childrenAreLeaves) {
 251             // Children are leaves; if their total bytes is smaller than a leaf's worth, collapse into one...
 252             if (node->numBytes > 0 && node->numBytes <= storage->maxLeafCapacity) {
 253                 __CFStorageAllocLeafNodeMemory(allocator, storage, node->info.notLeaf.child[0], node->numBytes, false);
 254                 if (node->info.notLeaf.child[1] && node->info.notLeaf.child[1]->numBytes) {
 255                     COPYMEM(node->info.notLeaf.child[1]->info.leaf.memory, node->info.notLeaf.child[0]->info.leaf.memory + node->info.notLeaf.child[0]->numBytes, node->info.notLeaf.child[1]->numBytes);
 256                     if (node->info.notLeaf.child[2] && node->info.notLeaf.child[2]->numBytes) {
 257                         COPYMEM(node->info.notLeaf.child[2]->info.leaf.memory, node->info.notLeaf.child[0]->info.leaf.memory + node->info.notLeaf.child[0]->numBytes + node->info.notLeaf.child[1]->numBytes, node->info.notLeaf.child[2]->numBytes);
 258                         __CFStorageNodeDealloc(allocator, node->info.notLeaf.child[2], true);
 259                         node->info.notLeaf.child[2] = NULL;
 260                     }
 261                     __CFStorageNodeDealloc(allocator, node->info.notLeaf.child[1], true);
 262                     node->info.notLeaf.child[1] = NULL;
 263                 }
 264                 node->info.notLeaf.child[0]->numBytes = node->numBytes;
 265             }
 266         } else {
 267             // Children are not leaves; combine their children to assure each node has 2 or 3 children...
 268             // (Could try to bypass all this by noting up above whether the number of grandchildren changed...)
 269             CFStorageNode *gChildren[9];
 270             CFIndex cCnt, gCnt, cnt;
 271             CFIndex totalG = 0; // Total number of grandchildren
 272             for (cCnt = 0; cCnt < 3; cCnt++) {
 273                 CFStorageNode *child = node->info.notLeaf.child[cCnt];
 274                 if (child) {
 275                     for (gCnt = 0; gCnt < 3; gCnt++) if (child->info.notLeaf.child[gCnt]) {
 276                         gChildren[totalG++] = child->info.notLeaf.child[gCnt];
 277                         child->info.notLeaf.child[gCnt] = NULL;
 278                     }
 279                     child->numBytes = 0;
 280                 }
 281             }
 282             gCnt = 0;   // Total number of grandchildren placed
 283             for (cCnt = 0; cCnt < 3; cCnt++) {
 284                 // These tables indicate how many children each child should have, given the total number of grandchildren (last child gets remainder)
 285                 static const unsigned char forChild0[10] = {0, 1, 2, 3, 2, 3, 3, 3, 3, 3};
 286                 static const unsigned char forChild1[10] = {0, 0, 0, 0, 2, 2, 3, 2, 3, 3};
 287                 // sCnt is the number of grandchildren to be placed into child cCnt
 288                 // Depending on child number, pick the right number
 289                 CFIndex sCnt = (cCnt == 0) ? forChild0[totalG] : ((cCnt == 1) ? forChild1[totalG] : totalG);
 290                 // Assure we have that many grandchildren...
 291                 if (sCnt > totalG - gCnt) sCnt = totalG - gCnt;
 292                 if (sCnt) {
 293                     if (!node->info.notLeaf.child[cCnt]) {
 294                         CFStorageNode *newNode = __CFStorageCreateNode(allocator, false, 0);
 295                         CF_WRITE_BARRIER_ASSIGN(allocator, node->info.notLeaf.child[cCnt], newNode);
 296                     }
 297                     for (cnt = 0; cnt < sCnt; cnt++) {
 298                         node->info.notLeaf.child[cCnt]->numBytes += gChildren[gCnt]->numBytes;
 299                         CF_WRITE_BARRIER_ASSIGN(allocator, node->info.notLeaf.child[cCnt]->info.notLeaf.child[cnt], gChildren[gCnt++]);
 300                     }
 301                 } else {
 302                     if (node->info.notLeaf.child[cCnt]) {
 303                         _CFAllocatorDeallocateGC(allocator, node->info.notLeaf.child[cCnt]);
 304                         node->info.notLeaf.child[cCnt] = NULL;
 305                     }
 306                 }
 307             }
 308         }
 309     }
 310 }
 311
 312
 313 /* Returns NULL or additional node to come after this node
 314    Assumption: size is never > storage->maxLeafCapacity
 315 */
 316 static CFStorageNode *__CFStorageInsert(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
 317     if (node->isLeaf) {
 318         if (size + node->numBytes > storage->maxLeafCapacity) { // Need to create more child nodes
 319             if (byteNum == node->numBytes) {    // Inserting at end; easy...
 320                 CFStorageNode *newNode = __CFStorageCreateNode(allocator, true, size);
 321                 __CFStorageSetCache(storage, newNode, NULL, absoluteByteNum / storage->valueSize, size / storage->valueSize);
 322                 return newNode;
 323             } else if (byteNum == 0) {  // Inserting at front; also easy, but we need to swap node and newNode
 324                 CFStorageNode *newNode = __CFStorageCreateNode(allocator, true, 0);
 325                 CF_WRITE_BARRIER_MEMMOVE(newNode, node, sizeof(CFStorageNode));
 326                 node->isLeaf = true;
 327                 node->numBytes = size;
 328                 node->info.leaf.capacityInBytes = 0;
 329                 node->info.leaf.memory = NULL;
 330                 __CFStorageSetCache(storage, node, NULL, absoluteByteNum / storage->valueSize, size / storage->valueSize);
 331                 return newNode;
 332             } else if (byteNum + size <= storage->maxLeafCapacity) {    // Inserting at middle; inserted region will fit into existing child
 333                 // Create new node to hold the overflow
 334                 CFStorageNode *newNode = __CFStorageCreateNode(allocator, true, node->numBytes - byteNum);
 335                 if (node->info.leaf.memory) {   // We allocate memory lazily...
 336                     __CFStorageAllocLeafNodeMemory(allocator, storage, newNode, node->numBytes - byteNum, false);
 337                     COPYMEM(node->info.leaf.memory + byteNum, newNode->info.leaf.memory, node->numBytes - byteNum);
 338                     __CFStorageAllocLeafNodeMemory(allocator, storage, node, byteNum + size, false);
 339                 }
 340                 node->numBytes = byteNum + size;
 341                 __CFStorageSetCache(storage, node, node->info.leaf.memory, (absoluteByteNum - byteNum) / storage->valueSize, node->numBytes / storage->valueSize);
 342                 return newNode;
 343             } else {    // Inserting some of new into one node, rest into another; remember that the assumption is size <= storage->maxLeafCapacity
 344                 CFStorageNode *newNode = __CFStorageCreateNode(allocator, true, node->numBytes + size - storage->maxLeafCapacity);      // New stuff
 345                 if (node->info.leaf.memory) {   // We allocate memory lazily...
 346                     __CFStorageAllocLeafNodeMemory(allocator, storage, newNode, node->numBytes + size - storage->maxLeafCapacity, false);
 347                     COPYMEM(node->info.leaf.memory + byteNum, newNode->info.leaf.memory + byteNum + size - storage->maxLeafCapacity, node->numBytes - byteNum);
 348                     __CFStorageAllocLeafNodeMemory(allocator, storage, node, storage->maxLeafCapacity, false);
 349                 }
 350                 node->numBytes = storage->maxLeafCapacity;
 351                 __CFStorageSetCache(storage, node, node->info.leaf.memory, (absoluteByteNum - byteNum) / storage->valueSize, node->numBytes / storage->valueSize);
 352                 //__CFStorageSetCache(storage, NULL, NULL, 0, 0);
 353                 return newNode;
 354             }
 355         } else {        // No need to create new nodes!
 356             if (node->info.leaf.memory) {
 357                 __CFStorageAllocLeafNodeMemory(allocator, storage, node, node->numBytes + size, false);
 358                 COPYMEM(node->info.leaf.memory + byteNum, node->info.leaf.memory + byteNum + size, node->numBytes - byteNum);
 359             }
 360             node->numBytes += size;
 361             __CFStorageSetCache(storage, node, node->info.leaf.memory, (absoluteByteNum - byteNum) / storage->valueSize, node->numBytes / storage->valueSize);
 362             return NULL;
 363         }
 364     } else {
 365         CFIndex relativeByteNum;
 366         CFIndex childNum;
 367         CFStorageNode *newNode;
 368         __CFStorageFindChild(node, byteNum, true, &childNum, &relativeByteNum);
 369         newNode = __CFStorageInsert(allocator, storage, node->info.notLeaf.child[childNum], relativeByteNum, size, absoluteByteNum);
 370         if (newNode) {
 371             if (node->info.notLeaf.child[2] == NULL) {  // There's an empty slot for the new node, cool
 372                 if (childNum == 0) CF_WRITE_BARRIER_ASSIGN(allocator, node->info.notLeaf.child[2], node->info.notLeaf.child[1]);        // Make room
 373                 CF_WRITE_BARRIER_ASSIGN(allocator, node->info.notLeaf.child[childNum + 1], newNode);
 374                 node->numBytes += size;
 375                 return NULL;
 376             } else {
 377                 CFStorageNode *anotherNode = __CFStorageCreateNode(allocator, false, 0);        // Create another node
 378                 if (childNum == 0) {    // Last two children go to new node
 379                     CF_WRITE_BARRIER_ASSIGN(allocator, anotherNode->info.notLeaf.child[0], node->info.notLeaf.child[1]);
 380                     CF_WRITE_BARRIER_ASSIGN(allocator, anotherNode->info.notLeaf.child[1], node->info.notLeaf.child[2]);
 381                     CF_WRITE_BARRIER_ASSIGN(allocator, node->info.notLeaf.child[1], newNode);
 382                     node->info.notLeaf.child[2] = NULL;
 383                 } else if (childNum == 1) {     // Last child goes to new node
 384                     CF_WRITE_BARRIER_ASSIGN(allocator, anotherNode->info.notLeaf.child[0], newNode);
 385                     CF_WRITE_BARRIER_ASSIGN(allocator, anotherNode->info.notLeaf.child[1], node->info.notLeaf.child[2]);
 386                     node->info.notLeaf.child[2] = NULL;
 387                 } else {        // New node contains the new comers...
 388                     CF_WRITE_BARRIER_ASSIGN(allocator, anotherNode->info.notLeaf.child[0], node->info.notLeaf.child[2]);
 389                     CF_WRITE_BARRIER_ASSIGN(allocator, anotherNode->info.notLeaf.child[1], newNode);
 390                     node->info.notLeaf.child[2] = NULL;
 391                 }
 392                 node->numBytes = node->info.notLeaf.child[0]->numBytes + node->info.notLeaf.child[1]->numBytes;
 393                 anotherNode->numBytes = anotherNode->info.notLeaf.child[0]->numBytes + anotherNode->info.notLeaf.child[1]->numBytes;
 394                 return anotherNode;
 395             }
 396         } else {
 397             node->numBytes += size;
 398         }
 399     }
 400     return NULL;
 401 }
 402
 403 CF_INLINE CFIndex __CFStorageGetCount(CFStorageRef storage) {
 404     return storage->rootNode.numBytes / storage->valueSize;
 405 }
 406
 407 static bool __CFStorageEqual(CFTypeRef cf1, CFTypeRef cf2) {
 408     CFStorageRef storage1 = (CFStorageRef)cf1;
 409     CFStorageRef storage2 = (CFStorageRef)cf2;
 410     CFIndex loc, count, valueSize;
 411     CFRange range1, range2;
 412     uint8_t *ptr1, *ptr2;
 413
 414     count = __CFStorageGetCount(storage1);
 415     if (count != __CFStorageGetCount(storage2)) return false;
 416
 417     valueSize = __CFStorageGetValueSize(storage1);
 418     if (valueSize != __CFStorageGetValueSize(storage2)) return false;
 419
 420     loc = range1.location = range1.length = range2.location = range2.length = 0;
 421     ptr1 = ptr2 = NULL;
 422
 423     while (loc < count) {
 424         CFIndex cntThisTime;
 425         if (loc >= range1.location + range1.length) ptr1 = CFStorageGetValueAtIndex(storage1, loc, &range1);
 426         if (loc >= range2.location + range2.length) ptr2 = CFStorageGetValueAtIndex(storage2, loc, &range2);
 427         cntThisTime = range1.location + range1.length;
 428         if (range2.location + range2.length < cntThisTime) cntThisTime = range2.location + range2.length;
 429         cntThisTime -= loc;
 430         if (memcmp(ptr1, ptr2, valueSize * cntThisTime) != 0) return false;
 431         ptr1 += valueSize * cntThisTime;
 432         ptr2 += valueSize * cntThisTime;
 433         loc += cntThisTime;
 434     }
 435     return true;
 436 }
 437
 438 static CFHashCode __CFStorageHash(CFTypeRef cf) {
 439     CFStorageRef Storage = (CFStorageRef)cf;
 440     return __CFStorageGetCount(Storage);
 441 }
 442
 443 static void __CFStorageDescribeNode(CFStorageNode *node, CFMutableStringRef str, CFIndex level) {
 444     int cnt;
 445     for (cnt = 0; cnt < level; cnt++) CFStringAppendCString(str, "  ", CFStringGetSystemEncoding());
 446
 447     if (node->isLeaf) {
 448         CFStringAppendFormat(str, NULL, CFSTR("Leaf %d/%d\n"), node->numBytes, node->info.leaf.capacityInBytes);
 449     } else {
 450         CFStringAppendFormat(str, NULL, CFSTR("Node %d\n"), node->numBytes);
 451         for (cnt = 0; cnt < 3; cnt++) if (node->info.notLeaf.child[cnt]) __CFStorageDescribeNode(node->info.notLeaf.child[cnt], str, level+1);
 452     }
 453 }
 454
 455 static CFIndex __CFStorageGetNodeCapacity(CFStorageNode *node) {
 456     if (!node) return 0;
 457     if (node->isLeaf) return node->info.leaf.capacityInBytes;
 458     return __CFStorageGetNodeCapacity(node->info.notLeaf.child[0]) + __CFStorageGetNodeCapacity(node->info.notLeaf.child[1]) + __CFStorageGetNodeCapacity(node->info.notLeaf.child[2]);
 459 }
 460
 461 CFIndex __CFStorageGetCapacity(CFStorageRef storage) {
 462     return __CFStorageGetNodeCapacity(&storage->rootNode) / storage->valueSize;
 463 }
 464
 465 CFIndex __CFStorageGetValueSize(CFStorageRef storage) {
 466     return storage->valueSize;
 467 }
 468
 469 static CFStringRef __CFStorageCopyDescription(CFTypeRef cf) {
 470     CFStorageRef storage = (CFStorageRef)cf;
 471     CFMutableStringRef result;
 472     CFAllocatorRef allocator = CFGetAllocator(storage);
 473     result = CFStringCreateMutable(allocator, 0);
 474     CFStringAppendFormat(result, NULL, CFSTR("<CFStorage %p [%p]>[count = %u, capacity = %u]\n"), storage, allocator, __CFStorageGetCount(storage), __CFStorageGetCapacity(storage));
 475     __CFStorageDescribeNode(&storage->rootNode, result, 0);
 476     return result;
 477 }
 478
 479 static void __CFStorageDeallocate(CFTypeRef cf) {
 480     CFStorageRef storage = (CFStorageRef)cf;
 481     CFAllocatorRef allocator = CFGetAllocator(storage);
 482     if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) return; // XXX_PCB GC will take care of us.
 483     __CFStorageNodeDealloc(allocator, &storage->rootNode, false);
 484 }
 485
 486 static CFTypeID __kCFStorageTypeID = _kCFRuntimeNotATypeID;
 487
 488 static const CFRuntimeClass __CFStorageClass = {
 489     _kCFRuntimeScannedObject,
 490     "CFStorage",
 491     NULL,       // init
 492     NULL,       // copy
 493     __CFStorageDeallocate,
 494     (void *)__CFStorageEqual,
 495     __CFStorageHash,
 496     NULL,       //
 497     __CFStorageCopyDescription
 498 };
 499
 500 __private_extern__ void __CFStorageInitialize(void) {
 501     __kCFStorageTypeID = _CFRuntimeRegisterClass(&__CFStorageClass);
 502 }
 503
 504 /*** Public API ***/
 505
 506 CFStorageRef CFStorageCreate(CFAllocatorRef allocator, CFIndex valueSize) {
 507     CFStorageRef storage;
 508     CFIndex size = sizeof(struct __CFStorage) - sizeof(CFRuntimeBase);
 509     storage = (CFStorageRef)_CFRuntimeCreateInstance(allocator, __kCFStorageTypeID, size, NULL);
 510     if (NULL == storage) {
 511         return NULL;
 512     }
 513     storage->valueSize = valueSize;
 514     storage->cachedRange.location = 0;
 515     storage->cachedRange.length = 0;
 516     storage->cachedNode = NULL;
 517     storage->cachedNodeMemory = NULL;
 518     storage->maxLeafCapacity = __CFStorageMaxLeafCapacity;
 519     if (valueSize && ((storage->maxLeafCapacity % valueSize) != 0)) {
 520         storage->maxLeafCapacity = (storage->maxLeafCapacity / valueSize) * valueSize;  // Make it fit perfectly (3406853)
 521     }
 522     memset(&(storage->rootNode), 0, sizeof(CFStorageNode));
 523     storage->rootNode.isLeaf = true;
 524     storage->nodeHint = AUTO_MEMORY_SCANNED;
 525     if (__CFOASafe) __CFSetLastAllocationEventName(storage, "CFStorage");
 526     return storage;
 527 }
 528
 529 CFTypeID CFStorageGetTypeID(void) {
 530     return __kCFStorageTypeID;
 531 }
 532
 533 CFIndex CFStorageGetCount(CFStorageRef storage) {
 534     return __CFStorageGetCount(storage);
 535 }
 536
 537 /* Returns pointer to the specified value
 538    index and validConsecutiveValueRange are in terms of values
 539 */
 540 void *CFStorageGetValueAtIndex(CFStorageRef storage, CFIndex idx, CFRange *validConsecutiveValueRange) {
 541     CFRange range;
 542     return __CFStorageGetValueAtIndex(storage, idx, validConsecutiveValueRange ? validConsecutiveValueRange : &range);
 543 }
 544
 545 /* Makes space for range.length values at location range.location
 546    This function deepens the tree if necessary...
 547 */
 548 void CFStorageInsertValues(CFStorageRef storage, CFRange range) {
 549     CFIndex numBytesToInsert = range.length * storage->valueSize;
 550     CFIndex byteNum = range.location * storage->valueSize;
 551     while (numBytesToInsert > 0) {
 552         CFStorageNode *newNode;
 553         CFAllocatorRef allocator = CFGetAllocator(storage);
 554         CFIndex insertThisTime = numBytesToInsert;
 555         if (insertThisTime > storage->maxLeafCapacity) {
 556             insertThisTime = (storage->maxLeafCapacity / storage->valueSize) * storage->valueSize;
 557         }
 558         newNode = __CFStorageInsert(allocator, storage, &storage->rootNode, byteNum, insertThisTime, byteNum);
 559         if (newNode) {
 560             CFStorageNode *tempRootNode = __CFStorageCreateNode(allocator, false, 0);   // Will copy the (static) rootNode over to this
 561             CF_WRITE_BARRIER_MEMMOVE(tempRootNode, &storage->rootNode, sizeof(CFStorageNode));
 562             storage->rootNode.isLeaf = false;
 563             CF_WRITE_BARRIER_BASE_ASSIGN(allocator, storage, storage->rootNode.info.notLeaf.child[0], tempRootNode);
 564             CF_WRITE_BARRIER_BASE_ASSIGN(allocator, storage, storage->rootNode.info.notLeaf.child[1], newNode);
 565             storage->rootNode.info.notLeaf.child[2] = NULL;
 566             storage->rootNode.numBytes = tempRootNode->numBytes + newNode->numBytes;
 567             if (storage->cachedNode == &(storage->rootNode))
 568                 CF_WRITE_BARRIER_BASE_ASSIGN(allocator, storage, storage->cachedNode, tempRootNode);    // The cache should follow the node
 569         }
 570         numBytesToInsert -= insertThisTime;
 571         byteNum += insertThisTime;
 572     }
 573 }
 574
 575 /* Deletes the values in the specified range
 576    This function gets rid of levels if necessary...
 577 */
 578 void CFStorageDeleteValues(CFStorageRef storage, CFRange range) {
 579     CFAllocatorRef allocator = CFGetAllocator(storage);
 580     range.location *= storage->valueSize;
 581     range.length *= storage->valueSize;
 582     __CFStorageDelete(allocator, storage, &storage->rootNode, range, true);
 583     while (__CFStorageGetNumChildren(&storage->rootNode) == 1) {
 584         CFStorageNode *child = storage->rootNode.info.notLeaf.child[0]; // The single child
 585         CF_WRITE_BARRIER_MEMMOVE(&storage->rootNode, child, sizeof(CFStorageNode));
 586         _CFAllocatorDeallocateGC(allocator, child);
 587     }
 588     if (__CFStorageGetNumChildren(&storage->rootNode) == 0 && !storage->rootNode.isLeaf) {
 589         storage->rootNode.isLeaf = true;
 590         storage->rootNode.info.leaf.capacityInBytes = 0;
 591         storage->rootNode.info.leaf.memory = NULL;
 592     }
 593     // ??? Need to update the cache
 594     storage->cachedRange = CFRangeMake(0, 0);
 595 }
 596
 597 void CFStorageGetValues(CFStorageRef storage, CFRange range, void *values) {
 598     while (range.length > 0) {
 599         CFRange leafRange;
 600         void *storagePtr = __CFStorageGetValueAtIndex(storage, range.location, &leafRange);
 601         CFIndex cntThisTime = range.length;
 602         if (cntThisTime > leafRange.length - (range.location - leafRange.location)) cntThisTime = leafRange.length - (range.location - leafRange.location);
 603         COPYMEM(storagePtr, values, cntThisTime * storage->valueSize);
 604                 ((uint8_t *)values) += cntThisTime * storage->valueSize;
 605         range.location += cntThisTime;
 606         range.length -= cntThisTime;
 607     }
 608 }
 609
 610 void CFStorageApplyFunction(CFStorageRef storage, CFRange range, CFStorageApplierFunction applier, void *context) {
 611     while (0 < range.length) {
 612         CFRange leafRange;
 613         const void *storagePtr;
 614         CFIndex idx, cnt;
 615         storagePtr = CFStorageGetValueAtIndex(storage, range.location, &leafRange);
 616         cnt = __CFMin(range.length, leafRange.location + leafRange.length - range.location);
 617         for (idx = 0; idx < cnt; idx++) {
 618             applier(storagePtr, context);
 619             storagePtr = (const char *)storagePtr + storage->valueSize;
 620         }
 621         range.length -= cnt;
 622         range.location += cnt;
 623     }
 624 }
 625
 626 void CFStorageReplaceValues(CFStorageRef storage, CFRange range, const void *values) {
 627     while (range.length > 0) {
 628         CFRange leafRange;
 629         void *storagePtr = __CFStorageGetValueAtIndex(storage, range.location, &leafRange);
 630         CFIndex cntThisTime = range.length;
 631         if (cntThisTime > leafRange.length - (range.location - leafRange.location)) cntThisTime = leafRange.length - (range.location - leafRange.location);
 632         COPYMEM(values, storagePtr, cntThisTime * storage->valueSize);
 633         ((const uint8_t *)values) += cntThisTime * storage->valueSize;
 634         range.location += cntThisTime;
 635         range.length -= cntThisTime;
 636     }
 637 }
 638
 639 /* Used by CFArray.c */
 640
 641 static void __CFStorageNodeSetLayoutType(CFStorageNode *node, auto_zone_t *zone, auto_memory_type_t type) {
 642     if (node->isLeaf) {
 643         auto_zone_set_layout_type(zone, node->info.leaf.memory, type);
 644     } else {
 645         CFStorageNode **children = node->info.notLeaf.child;
 646         if (children[0]) __CFStorageNodeSetLayoutType(children[0], zone, type);
 647         if (children[1]) __CFStorageNodeSetLayoutType(children[1], zone, type);
 648         if (children[2]) __CFStorageNodeSetLayoutType(children[2], zone, type);
 649     }
 650 }
 651
 652 __private_extern__ void _CFStorageSetWeak(CFStorageRef storage) {
 653     storage->nodeHint = AUTO_MEMORY_UNSCANNED;
 654     __CFStorageNodeSetLayoutType(&storage->rootNode, __CFCollectableZone, storage->nodeHint);
 655 }
 656
 657 #undef COPYMEM
 658 #undef PAGE_LIMIT
 659