Collections.subproj/CFStorage.c

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