-
Notifications
You must be signed in to change notification settings - Fork 20
/
CFStorage.c
1479 lines (1299 loc) · 76.4 KB
/
CFStorage.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/*
* Copyright (c) 2015 Apple Inc. All rights reserved.
*
* @APPLE_LICENSE_HEADER_START@
*
* This file contains Original Code and/or Modifications of Original Code
* as defined in and that are subject to the Apple Public Source License
* Version 2.0 (the 'License'). You may not use this file except in
* compliance with the License. Please obtain a copy of the License at
* http://www.opensource.apple.com/apsl/ and read it before using this
* file.
*
* The Original Code and all software distributed under the License are
* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
* Please see the License for the specific language governing rights and
* limitations under the License.
*
* @APPLE_LICENSE_HEADER_END@
*/
/* CFStorage.c
Copyright (c) 1999-2014, Apple Inc. All rights reserved.
Responsibility: Ali Ozer
*/
/*
2-3 tree storing arbitrary sized values.
??? Currently elementSize cannot be greater than storage->maxLeafCapacity, which is less than or equal to __CFStorageMaxLeafCapacity
CFStorage is thread-safe for multiple readers, but not thread safe for simultaneous reading and writing.
*/
/* pammon notes on FrozenStorage
A CFStorage can be frozen, or more specifically, some or all of the nodes can be frozen. Frozen nodes can be safely shared between CFStorage instances. CFStorages containing frozen nodes are still considered mutable: frozen nodes are discarded and recreated on demand. It is a form of copy-on-write.
Freezing is usually one-way: there is no going back. However, if a node's reference count is 1, we know that no other CFStorage can reference it; and if we are in a mutating function, we know that it can be safely unfrozen.
If a node is frozen, all of its descendants should be considered frozen.
The root node, which is defined inline within the CFStorage struct itself, can never be frozen.
*/
#define NO_SHIFTER ((uint32_t)(-1))
#include <CoreFoundation/CFStorage.h>
#include "CFInternal.h"
#if DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED || DEPLOYMENT_TARGET_WINDOWS
#include <dispatch/dispatch.h>
#endif
#if DEPLOYMENT_TARGET_WINDOWS
// No C99 support
#define restrict
// Replace bzero
#define bzero(dst, size) ZeroMemory(dst, size)
#endif
#if !defined(PAGE_SIZE)
#define PAGE_SIZE 4096
#endif
// Above 15K, malloc switches (??? or used to in early Leopard) to using vm allocates for blocks; it seems best to avoid that.
// Also, tests with StorageTimer.c done in 4/07 indicate that 4096 * 3 is better than smaller or larger node sizes.
#define __CFStorageMaxLeafCapacity (4096 * 3)
#define COPYMEM(src,dst,n) objc_memmove_collectable((dst), (src), (n))
#define PAGE_LIMIT ((CFIndex)PAGE_SIZE / 2)
CF_INLINE int32_t roundToPage(int32_t num) {
return (num + PAGE_SIZE - 1) & ~(PAGE_SIZE - 1);
}
typedef const struct __CFStorage *ConstCFStorageRef;
/* Each node in the storage. isLeaf determines whether the node is a leaf node or a node inside the tree. If latter, number of children are determined by the number of non-NULL entries in child[]. (NULL entries are at the end.)
*/
typedef struct __CFStorageNode {
CFIndex numBytes; /* Number of actual bytes in this node and all its children */
uint32_t refCount; /* Refcount of the node. Is always at least 1 for a normal node. For root nodes, which are stored directly in the CFStorage, this is 0. CFStorageRetain/ReleaseNode checks for a refcount of 0 and does not retain/release such nodes. */
bool isFrozen; /* Indicates that the node is frozen, i.e. may be shared. */
bool isLeaf;
union {
struct {
CFIndex capacityInBytes; // capacityInBytes is capacity of memory; this is either 0, or >= numBytes
uint8_t *memory;
CFRange cachedRange; //the absolute range of this node, in "value" units. This is valid only if this node is referenced by storage->cacheNode, and used by the cache. In general this is not valid, and the offset needs to be passed down from the tree
} leaf;
struct {
struct __CFStorageNode *child[3];
} notLeaf;
} info;
} CFStorageNode;
/* A struct used for insertion into frozen nodes, which may need to return a new version of themselves, and a new friend! The child field is a replacement for the child that was inserted into; if the child does not need to be replaced (i.e. it was unfrozen and there was space to perform the insertion) then the child that was inserted into is returned here. The sibling field is a new child that should also be inserted (or NULL if none). */
typedef struct {
CFStorageNode *child;
CFStorageNode *sibling;
} CFStorageDoubleNodeReturn;
CF_INLINE CFStorageDoubleNodeReturn CFStorageDoubleNodeReturnMake(CFStorageNode *child, CFStorageNode *sibling) {
CFStorageDoubleNodeReturn v;
v.child = child;
v.sibling = sibling;
return v;
}
/* The CFStorage object.
*/
struct __CFStorage {
CFRuntimeBase base;
CFIndex valueSize;
uint32_t byteToValueShifter;
CFLock_t cacheReaderMemoryAllocationLock;
bool alwaysFrozen;
CFStorageNode * volatile cacheNode;
CFIndex maxLeafCapacity; // In terms of bytes
CFStorageNode rootNode;
CFOptionFlags nodeHint; // __kCFAllocatorGCScannedMemory or 0.
};
/* Helper function to return the intersection of two ranges */
static inline CFRange intersectionRange(CFRange a, CFRange b) {
CFIndex start = __CFMax(a.location, b.location);
CFIndex end = __CFMin(a.location + a.length, b.location + b.length);
if (end <= start) {
return CFRangeMake(0, 0);
}
else {
return CFRangeMake(start, end - start);
}
}
/* Allocates the memory and initializes the capacity in a leaf. This locks not for mutations (mutations are not thread-safe in general), but for lazy allocation of storage during reading.
*/
CF_INLINE void __CFStorageAllocLeafNodeMemory(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex cap, bool compact) {
if (cap > PAGE_LIMIT) {
cap = roundToPage(cap);
if (cap > storage->maxLeafCapacity) cap = storage->maxLeafCapacity;
} else {
cap = (((cap + 63) / 64) * 64);
}
/* We must be careful here, because another thread may be trying to allocate this memory at the same time (8203146). This may happen if two threads both attempt to read from a lazily-allocated node. */
if ((compact ? (cap != node->info.leaf.capacityInBytes) : (cap > node->info.leaf.capacityInBytes))) {
__CFLock(&(storage->cacheReaderMemoryAllocationLock));
/* Check again now that we've acquired the lock. We know that we can do this because two simulaneous readers will always pass the same capacity. This is the fix for 8203146. This probably needs a memory barrier. */
if ((compact ? (cap != node->info.leaf.capacityInBytes) : (cap > node->info.leaf.capacityInBytes))) {
__CFAssignWithWriteBarrier((void **)&node->info.leaf.memory, _CFAllocatorReallocateGC(allocator, node->info.leaf.memory, cap, storage->nodeHint)); // This will free...
if (__CFOASafe) __CFSetLastAllocationEventName(node->info.leaf.memory, "CFStorage (node bytes)");
node->info.leaf.capacityInBytes = cap;
}
__CFUnlock(&(storage->cacheReaderMemoryAllocationLock));
}
}
#if 0
#define ASSERT(x) do { if (! (x)) { fprintf(stderr, "Assertion %s failed on line %d\n", #x, __LINE__); HALT; } } while (0)
#else
#define ASSERT(x) do { if (0 && ! (x)) { } } while(0)
#endif
static void __CFStorageCheckIntegrity(CFStorageRef storage);
#define CHECK_INTEGRITY() do { if (0) __CFStorageCheckIntegrity(storage); } while (0)
static void __CFStorageCheckNodeIntegrity(ConstCFStorageRef storage, const CFStorageNode *node);
#define CHECK_NODE_INTEGRITY(X) do { if (0) __CFStorageCheckNodeIntegrity(storage, X); } while (0)
#pragma mark Byte <-> Value Functions
CF_INLINE CFIndex __CFStorageConvertByteToValue(ConstCFStorageRef storage, CFIndex byte) {
if (storage->byteToValueShifter != NO_SHIFTER) {
return byte >> storage->byteToValueShifter;
}
return byte / storage->valueSize;
}
CF_INLINE CFRange __CFStorageConvertBytesToValueRange(ConstCFStorageRef storage, CFIndex offset, CFIndex length) {
if (storage->byteToValueShifter != NO_SHIFTER) {
return CFRangeMake(offset >> storage->byteToValueShifter, length >> storage->byteToValueShifter);
}
return CFRangeMake(offset / storage->valueSize, length / storage->valueSize);
}
CF_INLINE CFIndex __CFStorageConvertValueToByte(ConstCFStorageRef storage, CFIndex value) {
if (storage->byteToValueShifter != NO_SHIFTER) {
return value << storage->byteToValueShifter;
}
return value * storage->valueSize;
}
CF_INLINE CFRange __CFStorageConvertValuesToByteRange(ConstCFStorageRef storage, CFIndex offset, CFIndex length) {
if (storage->byteToValueShifter != NO_SHIFTER) {
return CFRangeMake(offset << storage->byteToValueShifter, length << storage->byteToValueShifter);
}
return CFRangeMake(offset * storage->valueSize, length * storage->valueSize);
}
#pragma mark Node reference counting and freezing
CF_INLINE CFStorageNode *__CFStorageRetainNode(CFStorageNode *node) {
if (node->refCount > 0) OSAtomicIncrement32((int32_t *)&node->refCount);
return node;
}
/* A faster version of __CFStorageRetainNode that is not thread safe. This can be used from the Unfrozen (aka unshared) calls, or when a node was just allocated and there's no opportunity for it to have escaped yet */
CF_INLINE CFStorageNode *__CFStorageRetainNodeThreadUnsafe(CFStorageNode *node) {
if (node->refCount > 0) node->refCount++;
return node;
}
static void __CFStorageDeallocateNode(CFStorageRef storage, CFStorageNode *node);
CF_INLINE void __CFStorageReleaseNode(CFStorageRef storage, CFStorageNode *node) {
if (node->refCount > 0) {
uint32_t newRefCount = OSAtomicDecrement32((int32_t *)&node->refCount);
if (newRefCount == 0) {
__CFStorageDeallocateNode(storage, node);
}
}
}
CF_INLINE void __CFStorageReleaseNodeWithNullCheck(CFStorageRef storage, CFStorageNode *node) {
if (node) __CFStorageReleaseNode(storage, node);
}
static void __CFStorageDeallocateNode(CFStorageRef storage, CFStorageNode *node) {
CFAllocatorRef allocator = CFGetAllocator(storage);
if (node->isLeaf) {
if (node->info.leaf.memory) _CFAllocatorDeallocateGC(allocator, node->info.leaf.memory);
} else {
__CFStorageReleaseNodeWithNullCheck(storage, node->info.notLeaf.child[0]);
__CFStorageReleaseNodeWithNullCheck(storage, node->info.notLeaf.child[1]);
__CFStorageReleaseNodeWithNullCheck(storage, node->info.notLeaf.child[2]);
}
_CFAllocatorDeallocateGC(allocator, node);
}
static inline void __CFStorageFreezeNode(CFStorageNode *node) {
node->isFrozen = true;
}
/* If a node is frozen, but its reference count is 1, then we are the only reference to it and we can unfreeze it. In general, it's unsafe to do this because it may race with other threads that depend on it being frozen (e.g. we are about to copy the node). However, we do not support concurrent access while mutating a CFStorage, so if we are in a mutation function, know we have exclusive access and we can unfreeze the node. */
static inline bool __CFStorageThawNodeDuringMutation(CFStorageRef storage, CFStorageNode *node) {
if (node->refCount == 1) {
node->isFrozen = false;
return true;
}
return false;
}
static inline void __CFStorageSetChild(CFStorageNode *parentNode, CFIndex childIndex, CFStorageNode *newChild) {
ASSERT(! parentNode->isLeaf);
ASSERT(childIndex < 3);
__CFAssignWithWriteBarrier((void **)&parentNode->info.notLeaf.child[childIndex], newChild);
}
static inline void __CFStorageGetChildren(const CFStorageNode *parent, CFStorageNode ** restrict resultArray, bool shouldRetain, bool shouldFreeze) {
ASSERT(! parent->isLeaf);
CFIndex i;
for (i=0; i < 3; i++) {
CFStorageNode *node = parent->info.notLeaf.child[i];
if (node != NULL && shouldRetain) __CFStorageRetainNode(node);
if (node != NULL && shouldFreeze) __CFStorageFreezeNode(node);
resultArray[i] = node;
}
}
#pragma mark Storage cache handling
/* Sets the cache to point at the specified node. loc and len are in terms of values, not bytes. To clear the cache set these two to 0.
At least one of node or memory should be non-NULL. memory is consulted first when using the cache.
*/
CF_INLINE void __CFStorageSetCache(CFStorageRef storage, CFStorageNode *node, CFIndex locInBytes) {
if (node) {
ASSERT(node->isLeaf);
node->info.leaf.cachedRange = __CFStorageConvertBytesToValueRange(storage, locInBytes, node->numBytes);
}
storage->cacheNode = node;
}
/* Gets the location for the specified absolute loc from the cached info.
Returns NULL if the location is not in the cache.
*/
CF_INLINE uint8_t *__CFStorageGetFromCache(CFStorageRef storage, CFIndex loc, CFRange * restrict validConsecutiveValueRange, bool requireUnfrozenNode) {
CFStorageNode * const cachedNode = storage->cacheNode; /* It's important we read from this field no more than once, for thread safety with other concurrent reads; that is why the field is marked volatile. */
if (! cachedNode) return NULL; /* No cache */
/* We only allow caching leaf nodes. */
ASSERT(cachedNode->isLeaf);
/* If the node is frozen, and we require an unfrozen node, then return NULL */
if (requireUnfrozenNode && cachedNode->isFrozen) return NULL;
/* If there's no memory allocated yet, then allocate it now*/
if (! cachedNode->info.leaf.memory) {
__CFStorageAllocLeafNodeMemory(CFGetAllocator(storage), storage, cachedNode, cachedNode->numBytes, false);
}
/* If the node's range starts after loc, or ends before or at loc, return NULL */
CFIndex nodeOffset = cachedNode->info.leaf.cachedRange.location;
CFIndex nodeLength = cachedNode->info.leaf.cachedRange.length;
if (loc < nodeOffset || loc >= nodeOffset + nodeLength) {
return NULL;
}
/* The cache is valid, so return it */
validConsecutiveValueRange->location = nodeOffset;
validConsecutiveValueRange->length = nodeLength;
uint8_t *result = cachedNode->info.leaf.memory + __CFStorageConvertValueToByte(storage, loc - nodeOffset);
return result;
}
/* Returns the number of the child containing the desired value and the relative index of the value in that child.
forInsertion = true means that we are looking for the child in which to insert or delete; this changes the behavior when the index is at the end of a child
relativeByteNum (not optional, for performance reasons) returns the relative byte number of the specified byte in the child.
Don't call with leaf nodes!
*/
CF_INLINE CFStorageNode *__CFStorageFindChild(const CFStorageNode * restrict node, CFIndex byteNum, bool forInsertionOrDeletion, CFIndex * restrict childNum, CFIndex * restrict relativeByteNum) {
if (forInsertionOrDeletion) byteNum--; /* If for insertion, we do <= checks, not <, so this accomplishes the same thing */
CFStorageNode *result;
result = node->info.notLeaf.child[0];
if (byteNum < result->numBytes) *childNum = 0;
else {
byteNum -= result->numBytes;
result = node->info.notLeaf.child[1];
if (byteNum < result->numBytes) *childNum = 1;
else {
byteNum -= result->numBytes;
*childNum = 2;
result = node->info.notLeaf.child[2];
}
}
if (forInsertionOrDeletion) byteNum++;
*relativeByteNum = byteNum;
return result;
}
static CFStorageNode *__CFStorageCopyNode(CFStorageRef storage, const CFStorageNode *node);
/* Finds the location where the specified byte is stored. If validConsecutiveByteRange is not NULL, returns
the range of bytes that are consecutive with this one.
!!! Assumes the byteNum is within the range of this node.
*/
static void *__CFStorageFindByte(CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex absoluteByteOffsetOfNode, CFStorageNode **resultNode, CFRange *validConsecutiveByteRange, bool requireUnfreezing) {
if (node->isLeaf) {
*validConsecutiveByteRange = CFRangeMake(absoluteByteOffsetOfNode, node->numBytes);
*resultNode = node;
__CFStorageAllocLeafNodeMemory(CFGetAllocator(storage), storage, node, node->numBytes, false);
return node->info.leaf.memory + byteNum;
} else {
CFIndex childNum;
CFIndex relativeByteNum;
CFStorageNode *child = __CFStorageFindChild(node, byteNum, false, &childNum, &relativeByteNum);
if (requireUnfreezing && child->isFrozen && ! __CFStorageThawNodeDuringMutation(storage, child)) {
/* Replace the child with an unfrozen variant */
CFStorageNode *unfrozenReplacement = __CFStorageCopyNode(storage, child);
/* Release the old node, set the new one */
__CFStorageSetChild(node, childNum, unfrozenReplacement);
__CFStorageReleaseNode(storage, child);
child = unfrozenReplacement;
}
return __CFStorageFindByte(storage, child, relativeByteNum, absoluteByteOffsetOfNode + (byteNum - relativeByteNum), resultNode, validConsecutiveByteRange, requireUnfreezing);
}
}
/* Guts of CFStorageGetValueAtIndex(); note that validConsecutiveValueRange is not optional.
Consults and updates cache.
*/
CF_INLINE void *__CFStorageGetValueAtIndex(CFStorageRef storage, CFIndex idx, CFRange *validConsecutiveValueRange, bool requireUnfreezing) {
uint8_t *result;
if (!(result = __CFStorageGetFromCache(storage, idx, validConsecutiveValueRange, requireUnfreezing))) {
CFStorageNode *resultNode;
CFRange rangeInBytes;
result = (uint8_t *)__CFStorageFindByte(storage, &storage->rootNode, __CFStorageConvertValueToByte(storage, idx), 0, &resultNode, &rangeInBytes, requireUnfreezing);
__CFStorageSetCache(storage, resultNode, rangeInBytes.location);
*validConsecutiveValueRange = __CFStorageConvertBytesToValueRange(storage, rangeInBytes.location, rangeInBytes.length);
}
return result;
}
/* Copies data in the range srcRange from srcLeaf to index dstLocation in dstLeaf. Both srcLeaf and dstLeaf must be leaf nodes, and dstLeaf must not be frozen. If srcRange has a nonzero length, then both must have their memory properly allocated. This does not modify the numBytes of srcLeaf or dstLeaf.
*/
static void __CFLeafCopyRangeToOffset(const CFStorageNode *srcLeaf, CFRange srcRange, CFStorageNode *dstLeaf, CFIndex dstLocation) {
ASSERT(srcLeaf->isLeaf);
ASSERT(dstLeaf->isLeaf);
if (srcRange.length > 0) {
ASSERT(srcLeaf->info.leaf.memory != NULL);
ASSERT(dstLeaf->info.leaf.memory != NULL);
ASSERT(srcRange.location + srcRange.length <= srcLeaf->numBytes);
ASSERT(dstLocation + srcRange.length <= dstLeaf->info.leaf.capacityInBytes);
COPYMEM(srcLeaf->info.leaf.memory + srcRange.location, dstLeaf->info.leaf.memory + dstLocation, srcRange.length);
}
}
#pragma mark Node creation and destruction
// returns a node with a refCount of 1, and an auto_zone_retain() under GC
static CFStorageNode *__CFStorageCreateNode(CFAllocatorRef allocator, CFStorageRef storage, bool isLeaf, CFIndex numBytes) {
CFStorageNode *newNode = (CFStorageNode *)CFAllocatorAllocate(allocator, sizeof(CFStorageNode), __kCFAllocatorGCScannedMemory);
if (__CFOASafe) __CFSetLastAllocationEventName(newNode, "CFStorage (node)");
if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
auto_zone_release(objc_collectableZone(), newNode); //remove the implicit retain so we can be collected
}
newNode->refCount = 1;
newNode->isFrozen = storage->alwaysFrozen;
newNode->isLeaf = isLeaf;
newNode->numBytes = numBytes;
if (isLeaf) {
newNode->info.leaf.capacityInBytes = 0;
newNode->info.leaf.memory = NULL;
} else {
newNode->info.notLeaf.child[0] = newNode->info.notLeaf.child[1] = newNode->info.notLeaf.child[2] = NULL;
}
return newNode;
}
/* Creates an (unfrozen) copy of the given node. This is shallow in the sense that it shares children for branches, but deep in that it copies memory for leaves. */
static CFStorageNode *__CFStorageCopyNode(CFStorageRef storage, const CFStorageNode *node) {
CFAllocatorRef allocator = CFGetAllocator(storage);
CFStorageNode *result = __CFStorageCreateNode(allocator, storage, node->isLeaf, node->numBytes);
if (node->isLeaf) {
if (node->info.leaf.memory != NULL) {
__CFStorageAllocLeafNodeMemory(allocator, storage, result, result->numBytes, false);
COPYMEM(node->info.leaf.memory, result->info.leaf.memory, result->numBytes);
}
}
else {
CFStorageNode *child = node->info.notLeaf.child[0];
__CFStorageSetChild(result, 0, __CFStorageRetainNode(child));
if ((child = node->info.notLeaf.child[1])) __CFStorageSetChild(result, 1, __CFStorageRetainNode(child));
if ((child = node->info.notLeaf.child[2])) __CFStorageSetChild(result, 2, __CFStorageRetainNode(child));
/* If we are copying children from a frozen node to an unfrozen node, we need to freeze the children */
if (node->isFrozen) {
__CFStorageFreezeNode(result->info.notLeaf.child[0]);
if ((child = result->info.notLeaf.child[1])) __CFStorageFreezeNode(child);
if ((child = result->info.notLeaf.child[2])) __CFStorageFreezeNode(child);
}
}
return result;
}
static void __CFStorageDeallocateNode(CFStorageRef storage, CFStorageNode *node);
#pragma mark Insertion and Deletion prototypes
/* Prototypes for deletion and insertion. The *Frozen and *Unfrozen variants should only be called for nodes that we know are frozen or unfrozen. Frozen nodes may only have frozen children, so it makes sense for the Frozen functions to call other Frozen functions. Unfrozen nodes may have frozen or unfrozen children, so they should call the non-suffixed variants (which dispatch on whether the node is frozen or not).
The only acceptable time to directly call the Unfrozen variant is for the root node of a CFStorage, because root nodes may never be frozen. The isRootNode parameter determines whether we are in this case.
The Insertion functions return two nodes. As an awful performance hack, if the first node returned from __CFStorageInsert* is the same as the node passed in, that node is *not* retained, so should not be relased. If it is a different node, it is retained.
*/
static CFStorageDoubleNodeReturn __CFStorageInsert(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum);
static CFStorageNode *__CFStorageDelete(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFRange range, bool compact);
static CFStorageDoubleNodeReturn __CFStorageInsertFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum);
static CFStorageNode *__CFStorageDeleteFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFRange range);
static CFStorageDoubleNodeReturn __CFStorageInsertUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum);
static CFStorageNode *__CFStorageDeleteUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFRange range, bool compact, bool isRootNode);
#pragma mark Frozen Deletion
static CFStorageNode *__CFStorageDeleteLeafFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFRange range) {
ASSERT(node->isLeaf);
const CFIndex rangeToDeleteEnd = range.location + range.length;
ASSERT(rangeToDeleteEnd <= node->numBytes);
CFIndex remainingBytes = node->numBytes - range.length;
if (remainingBytes == 0) {
/* The range to delete encompasses our entire range of bytes. Return NULL to indicate that we should be deleted. */
return NULL;
}
else {
/* Need to create a new node */
CFStorageNode *newNode = __CFStorageCreateNode(allocator, storage, true, remainingBytes);
if (node->info.leaf.memory) {
/* Our node had memory allocated, so copy in the non-deleted portion */
CFRange nonDeletedPrefix = CFRangeMake(0, range.location);
CFRange nonDeletedSuffix = CFRangeMake(rangeToDeleteEnd, node->numBytes - rangeToDeleteEnd);
ASSERT(nonDeletedPrefix.length + nonDeletedSuffix.length == remainingBytes);
__CFStorageAllocLeafNodeMemory(allocator, storage, newNode, remainingBytes, false); // no point in compacting since we're freshly allocated
__CFLeafCopyRangeToOffset(node, nonDeletedPrefix, newNode, 0);
__CFLeafCopyRangeToOffset(node, nonDeletedSuffix, newNode, nonDeletedPrefix.length);
}
return newNode;
}
}
/* Helper function for both frozen and unfrozen branch deletion. Walks the children of the node, calling __CFStorageDelete (or __CFStorageDeleteFrozen if childrenAreDefinitelyFrozen is YES), and assigning the results back to newChildren. Returns the number of new children. The newChildren nodes all acquire a reference count!
*/
static inline CFIndex __CFStoragePopulateBranchChildrenAfterDeletion(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFRange range, CFStorageNode *newChildren[3], bool childrenAreDefinitelyFrozen, bool compact) {
CFIndex newChildIndex = 0;
CFIndex childByteOffset = 0; //will track the current start byte of this child
for (CFIndex existingChildIndex = 0; existingChildIndex < 3; existingChildIndex++) {
CFStorageNode *existingChild = node->info.notLeaf.child[existingChildIndex];
if (! existingChild) break; //no more children
const CFIndex existingChildLength = existingChild->numBytes;
/* The child's range is {byteOffset, existingChildLength}. Figure out what part of the range to delete is intersected by this child's range */
CFRange deletionRangeIntersectedByChild = intersectionRange(range, CFRangeMake(childByteOffset, existingChildLength));
if (! deletionRangeIntersectedByChild.length) {
/* The range to delete does not overlap this child's range, so preserve the child */
newChildren[newChildIndex++] = __CFStorageRetainNode(existingChild); //bump the refcount like we promised we would
if (childrenAreDefinitelyFrozen) {
/* Because we are about to add this child from a frozen node to a possibly unfrozen node, mark the child as frozen */
__CFStorageFreezeNode(existingChild);
}
}
else {
/* We have something from this child to delete */
CFRange rangeOfChildToDelete = CFRangeMake(deletionRangeIntersectedByChild.location - childByteOffset, deletionRangeIntersectedByChild.length);
CFStorageNode *newChild;
if (childrenAreDefinitelyFrozen) {
newChild = __CFStorageDeleteFrozen(allocator, storage, existingChild, rangeOfChildToDelete);
}
else {
newChild = __CFStorageDelete(allocator, storage, existingChild, rangeOfChildToDelete, compact);
}
/* We may get null back if we deleted the entire child */
if (newChild != NULL) {
newChildren[newChildIndex++] = newChild; // Transfers the reference count
}
if (rangeOfChildToDelete.length == existingChildLength) {
ASSERT(newChild == NULL); //should have deleted everything
}
else {
ASSERT(newChild != NULL);
ASSERT(newChild->numBytes == existingChildLength - rangeOfChildToDelete.length);
}
}
childByteOffset += existingChildLength;
}
return newChildIndex;
}
static CFStorageNode *__CFStorageDeleteBranchFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFRange range) {
ASSERT(! node->isLeaf);
ASSERT(range.location + range.length <= node->numBytes);
if (range.length == node->numBytes) {
/* They're deleting everything, so return NULL to indicate that this node should be deleted. */
return NULL;
}
/* Construct our new children in this array. */
CFStorageNode *newChildren[3];
CFIndex newChildIndex = __CFStoragePopulateBranchChildrenAfterDeletion(allocator, storage, node, range, newChildren, true/*childrenAreDefinitelyFrozen*/, false/*compact*/);
/* We do not have to freeze anything in newChildren. __CFStoragePopulateBranchChildrenAfterDeletion() will properly freeze any existing children, and new children we get should not be marked frozen. */
/* Now we have the children of the new node in newChildren. We expect to have at least one child (if we got no children, we should have returned NULL up above because they deleted everything. */
ASSERT(newChildIndex >= 1);
if (newChildIndex == 1) {
/* Only one child, so just return it, transferring its retain count */
return newChildren[0];
}
else {
CFStorageNode *result = __CFStorageCreateNode(allocator, storage, false, 0);
while (newChildIndex--) {
__CFStorageSetChild(result, newChildIndex, newChildren[newChildIndex]); //transfers the reference count
}
result->numBytes = node->numBytes - range.length;
return result;
}
}
/* Returns a new node, or NULL if the entire thing was deleted.
*/
static CFStorageNode *__CFStorageDeleteFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFRange range) {
if (node->isLeaf) {
return __CFStorageDeleteLeafFrozen(allocator, storage, node, range);
}
else {
return __CFStorageDeleteBranchFrozen(allocator, storage, node, range);
}
}
#pragma mark Unfrozen Deletion
/* The boolean compact indicates whether leaf nodes that get smaller should be realloced.
*/
static CFStorageNode *__CFStorageDeleteUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFRange range, bool compact, bool isRootNode) {
ASSERT(! node->isFrozen);
ASSERT(range.location + range.length <= node->numBytes);
CHECK_NODE_INTEGRITY(node);
if (range.length == node->numBytes) {
/* We are deleting everything, so return NULL */
return NULL;
}
if (node->isLeaf) {
node->numBytes -= range.length;
// If this node had memory allocated, readjust the bytes...
if (node->info.leaf.memory) {
COPYMEM(node->info.leaf.memory + range.location + range.length, node->info.leaf.memory + range.location, node->numBytes - range.location);
if (compact) __CFStorageAllocLeafNodeMemory(allocator, storage, node, node->numBytes, true);
}
CHECK_NODE_INTEGRITY(node);
return __CFStorageRetainNodeThreadUnsafe(node); //we can use the ThreadUnsafe calls because this is the Unfrozen variant, so we are not shared
} else {
CFStorageNode *newChildren[3] = {NULL, NULL, NULL};
CFIndex newChildIndex = __CFStoragePopulateBranchChildrenAfterDeletion(allocator, storage, node, range, newChildren, false/*childrenAreDefinitelyFrozen*/, compact);
node->numBytes -= range.length;
ASSERT(newChildIndex >= 1); //we expect to have at least one child; else we would have deleted everything up above
/* Release all of our existing children. Either we are about to return a new child in place of us; or we are about to set our children to the new ones */
__CFStorageReleaseNode(storage, node->info.notLeaf.child[0]);
__CFStorageReleaseNodeWithNullCheck(storage, node->info.notLeaf.child[1]);
__CFStorageReleaseNodeWithNullCheck(storage, node->info.notLeaf.child[2]);
node->info.notLeaf.child[0] = node->info.notLeaf.child[1] = node->info.notLeaf.child[2] = NULL;
if (newChildIndex == 1) {
/* We have only one child, so return it, transferring the refcount that __CFStoragePopulate gives it */
return newChildren[0];
}
else {
CFIndex i;
for (i=0; i < 3; i++) {
__CFStorageSetChild(node, i, newChildren[i]); //set the new child, transferring the refcount to us (or set NULL)
}
CHECK_NODE_INTEGRITY(node);
return __CFStorageRetainNodeThreadUnsafe(node);
}
}
}
#pragma mark Frozen Insertion
/* Insertion into an frozen leaf. We return two nodes, either of which may be 'node', or possibly two new nodes. This always sets the cache. */
static CFStorageDoubleNodeReturn __CFStorageInsertLeafFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
/* Inserting into a frozen leaf. If we can fit the new data along with our existing data into a single node, then do so (i.e. if we can return one node, do it). Otherwise, all of the data would have to fit into a second node (we are never called with more data than storage->maxLeafCapacity) so just make a new node with the data and return that. */
CFStorageNode *leftResult, *rightResult;
CHECK_NODE_INTEGRITY(node);
ASSERT(byteNum <= node->numBytes);
CFIndex newTotalSize = size + node->numBytes;
if (newTotalSize <= storage->maxLeafCapacity) {
/* We can fit into a single node */
rightResult = NULL;
leftResult = __CFStorageCreateNode(allocator, storage, true, newTotalSize);
if (node->info.leaf.memory != NULL) { // Beware lazy memory allocation
__CFStorageAllocLeafNodeMemory(allocator, storage, leftResult, newTotalSize, false);
COPYMEM(node->info.leaf.memory, leftResult->info.leaf.memory, byteNum); //copy first byteNum bytes from existing node
//middle we don't touch
COPYMEM(node->info.leaf.memory + byteNum, leftResult->info.leaf.memory + byteNum + size, node->numBytes - byteNum); //copy last part from existing node
}
__CFStorageSetCache(storage, leftResult, absoluteByteNum - byteNum);
}
else {
/* We cannot fit into a single node. See if we can preserve self (i.e. we're inserting at beginning or end). */
if (byteNum == node->numBytes) {
/* Inserting at end, so left is our existing node and right is the new node. Do not retain left node, because it is the same as the given node */
leftResult = (CFStorageNode *)node;
rightResult = __CFStorageCreateNode(allocator, storage, true, size);
__CFStorageSetCache(storage, rightResult, absoluteByteNum);
}
else if (byteNum == 0) {
/* Inserting at beginning, so right is our existing node and left is the new node. Do retain left node, because it is different than the given node. */
rightResult = __CFStorageRetainNode((CFStorageNode *)node);
leftResult = __CFStorageCreateNode(allocator, storage, true, size);
__CFStorageSetCache(storage, leftResult, absoluteByteNum);
}
else {
/* Inserting in middle. We will need to create two nodes because we overflow one. We could be lazy and only allocate up to byteNum, but since it's likely that they're about to insert into us and we'd have to reallocate, just allocate everything requested up front. */
CFIndex leftAmount = storage->maxLeafCapacity, rightAmount = newTotalSize - storage->maxLeafCapacity;
leftResult = __CFStorageCreateNode(allocator, storage, true, leftAmount);
rightResult = __CFStorageCreateNode(allocator, storage, true, rightAmount);
__CFStorageAllocLeafNodeMemory(allocator, storage, leftResult, leftAmount, false);
__CFStorageAllocLeafNodeMemory(allocator, storage, rightResult, rightAmount, false);
ASSERT(node->info.leaf.capacityInBytes >= node->numBytes);
/* The existing node has length node->numBytes, so it has the following range: {0, node->numBytes}
We are inserting (garbage) data of length 'size' into offset 'byteNum'. Therefore we end up with the following two logical ranges, expressed as {start, length}:
{0, byteNum}, {byteNum + size, node->numBytes - byteNum}
We need to divide these among our new nodes with the following logical ranges:
{0, leftAmount}, {leftAmount, rightAmount}
The first range must be fit entirely within the left node (byteNum <= leftAmount). The second range may or may be divided between the left and right nodes.
*/
ASSERT(byteNum <= leftAmount);
COPYMEM(node->info.leaf.memory, leftResult->info.leaf.memory, byteNum);
const CFRange leftNodeRange = {0, leftAmount}, rightNodeRange = {leftAmount, rightAmount};
const CFRange preservedData = {byteNum + size, node->numBytes - byteNum};
CFRange overlap;
if ((overlap = intersectionRange(leftNodeRange, preservedData)).length > 0) COPYMEM(node->info.leaf.memory + overlap.location - size, leftResult->info.leaf.memory + overlap.location, overlap.length);
if ((overlap = intersectionRange(rightNodeRange, preservedData)).length > 0) COPYMEM(node->info.leaf.memory + overlap.location - size, rightResult->info.leaf.memory + overlap.location - leftAmount, overlap.length);
__CFStorageSetCache(storage, leftResult, absoluteByteNum - byteNum);
}
}
return CFStorageDoubleNodeReturnMake(leftResult, rightResult);
}
static CFStorageDoubleNodeReturn __CFStorageInsertBranchFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
/* Inserting into a frozen branch. We definitely will need to make a new copy of us, so make that up front. We may or may not need to make a new sibling. Note that in some cases, we may be able to get away with not creating a new copy of us, e.g. inserting at the very end of the tree. In that case, we could preserve us and make a sibling containing exactly one node. However, we do not really want to have branches with exactly one child; because then why not just return the child? And then the whole tree can become unbalanced. So then instead, always distribute the children equally among our nodes. */
CHECK_NODE_INTEGRITY(node);
CFStorageNode *copyOfMe = __CFStorageCreateNode(allocator, storage, false, 0);
CFStorageNode *siblingOfMe = NULL;
CFIndex relativeByteNum;
CFIndex childNum;
CFStorageNode *child = __CFStorageFindChild(node, byteNum, true, &childNum, &relativeByteNum);
ASSERT(childNum >= 0 && childNum <= 2);
CFStorageDoubleNodeReturn childReturn = __CFStorageInsertFrozen(allocator, storage, child, relativeByteNum, size, absoluteByteNum);
ASSERT(childReturn.child); //we always get at least one back
/* Make a local array of all new children (retained). We'll then move them to the new nodes. */
CFStorageNode *newChildren[4] = {NULL};
__CFStorageGetChildren(node, newChildren, true/*retain*/, true/*freeze*/);
if (newChildren[childNum] != childReturn.child) {
__CFStorageReleaseNode(storage, newChildren[childNum]);
newChildren[childNum] = childReturn.child; // Transfers the retain
}
if (childReturn.sibling != NULL) {
if (childNum < 2) newChildren[3] = newChildren[2];
if (childNum < 1) newChildren[2] = newChildren[1];
newChildren[childNum + 1] = childReturn.sibling; // Transfers the retain
}
/* First two always go to our clone */
__CFStorageSetChild(copyOfMe, 0, newChildren[0]);
__CFStorageSetChild(copyOfMe, 1, newChildren[1]);
if (newChildren[3] == NULL) {
/* We have three or fewer children to distribute, i.e. we don't need a sibling. Put them all into copy of me. Our clone's byte count is larger than our own by 'size'. */
__CFStorageSetChild(copyOfMe, 2, newChildren[2]);
copyOfMe->numBytes = node->numBytes + size;
}
else {
/* We have four children to distribute. The first two go to us, the last two go to our new sibling. */
siblingOfMe = __CFStorageCreateNode(allocator, storage, false, 0);
__CFStorageSetChild(siblingOfMe, 0, newChildren[2]);
__CFStorageSetChild(siblingOfMe, 1, newChildren[3]);
copyOfMe->numBytes = newChildren[0]->numBytes + newChildren[1]->numBytes;
siblingOfMe->numBytes = newChildren[2]->numBytes + newChildren[3]->numBytes;
}
CHECK_NODE_INTEGRITY(node);
CHECK_NODE_INTEGRITY(copyOfMe);
if (siblingOfMe) CHECK_NODE_INTEGRITY(siblingOfMe);
return CFStorageDoubleNodeReturnMake(copyOfMe, siblingOfMe);
}
static CFStorageDoubleNodeReturn __CFStorageInsertFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
if (node->isLeaf) {
return __CFStorageInsertLeafFrozen(allocator, storage, node, byteNum, size, absoluteByteNum);
}
else {
return __CFStorageInsertBranchFrozen(allocator, storage, node, byteNum, size, absoluteByteNum);
}
}
#pragma mark Unfrozen Insertion
/* Insertion into an unfrozen leaf. We return two nodes, one of which is 'node'. This always sets the cache. */
static CFStorageDoubleNodeReturn __CFStorageInsertLeafUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
if (size + node->numBytes > storage->maxLeafCapacity) { // Need to create more child nodes
CFStorageNode *newNode;
if (byteNum == node->numBytes) { // Inserting at end; easy...
newNode = __CFStorageCreateNode(allocator, storage, true, size);
__CFStorageSetCache(storage, newNode, absoluteByteNum);
} else if (byteNum == 0) { // Inserting at front; also easy, but we need to swap node and newNode
newNode = __CFStorageCreateNode(allocator, storage, true, 0);
/* Transfer our memory to the new node */
newNode->numBytes = node->numBytes;
newNode->info.leaf.capacityInBytes = node->info.leaf.capacityInBytes;
__CFAssignWithWriteBarrier((void **)&newNode->info.leaf.memory, node->info.leaf.memory);
/* Stomp on our existing node */
node->numBytes = size;
node->info.leaf.capacityInBytes = 0;
node->info.leaf.memory = NULL;
/* Cache our existing node */
__CFStorageSetCache(storage, node, absoluteByteNum);
} else if (byteNum + size <= storage->maxLeafCapacity) { // Inserting at middle; inserted region will fit into existing child
// Create new node to hold the overflow
newNode = __CFStorageCreateNode(allocator, storage, true, node->numBytes - byteNum);
if (node->info.leaf.memory) { // We allocate memory lazily...
__CFStorageAllocLeafNodeMemory(allocator, storage, newNode, node->numBytes - byteNum, false);
COPYMEM(node->info.leaf.memory + byteNum, newNode->info.leaf.memory, node->numBytes - byteNum);
__CFStorageAllocLeafNodeMemory(allocator, storage, node, byteNum + size, false);
}
node->numBytes = byteNum + size;
__CFStorageSetCache(storage, node, absoluteByteNum - byteNum);
} else { // Inserting some of new into one node, rest into another; remember that the assumption is size <= storage->maxLeafCapacity
newNode = __CFStorageCreateNode(allocator, storage, true, node->numBytes + size - storage->maxLeafCapacity); // New stuff
if (node->info.leaf.memory) { // We allocate memory lazily...
__CFStorageAllocLeafNodeMemory(allocator, storage, newNode, node->numBytes + size - storage->maxLeafCapacity, false);
COPYMEM(node->info.leaf.memory + byteNum, newNode->info.leaf.memory + byteNum + size - storage->maxLeafCapacity, node->numBytes - byteNum);
__CFStorageAllocLeafNodeMemory(allocator, storage, node, storage->maxLeafCapacity, false);
}
__CFStorageSetCache(storage, node, absoluteByteNum - byteNum);
node->numBytes = storage->maxLeafCapacity;
}
return CFStorageDoubleNodeReturnMake(node, newNode); // We do not retain 'node' because it is the given node.
} else { // No need to create new nodes!
if (node->info.leaf.memory) {
__CFStorageAllocLeafNodeMemory(allocator, storage, node, node->numBytes + size, false);
COPYMEM(node->info.leaf.memory + byteNum, node->info.leaf.memory + byteNum + size, node->numBytes - byteNum);
}
node->numBytes += size;
__CFStorageSetCache(storage, node, absoluteByteNum - byteNum);
return CFStorageDoubleNodeReturnMake(node, NULL); //return the existing node, meaning the parent does not have to do anything. Do not retain it because it is the given node.
}
}
static CFStorageDoubleNodeReturn __CFStorageInsertBranchUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
CFIndex relativeByteNum;
CFIndex childNum; // we will insert after childNum, i.e. if childNum is 0, any new node becomes index 1. This can have value 0, 1, or 2.
CFStorageNode *childNode = __CFStorageFindChild(node, byteNum, true, &childNum, &relativeByteNum);
CFStorageDoubleNodeReturn newNodes = __CFStorageInsert(allocator, storage, childNode, relativeByteNum, size, absoluteByteNum);
CFStorageDoubleNodeReturn result = {node, NULL}; // the default return value meaning we did all of the work ourselves and our parent does not need to do anything
ASSERT(childNode != NULL);
ASSERT(newNodes.child != NULL);
if (newNodes.child != childNode) {
/* We got back a replacement for the current child, so replace it. */
__CFStorageReleaseNode(storage, childNode);
__CFStorageSetChild(node, childNum, newNodes.child);
}
if (newNodes.sibling == NULL) {
/* The insertion happened successfully without requiring us to add any new nodes. */
node->numBytes += size;
} else {
/* We got back an additional node to insert. */
CFStorageNode *newChild = newNodes.sibling;
if (node->info.notLeaf.child[2] == NULL) { // There's an empty slot for the new node, cool
if (childNum == 0) __CFStorageSetChild(node, 2, node->info.notLeaf.child[1]); // Make room
__CFStorageSetChild(node, childNum+1, newChild);
node->numBytes += size;
} else {
CFStorageNode *anotherNode = __CFStorageCreateNode(allocator, storage, false, 0); // Create another node
if (childNum == 0) { // Last two children go to new node
__CFStorageSetChild(anotherNode, 0, node->info.notLeaf.child[1]);
__CFStorageSetChild(anotherNode, 1, node->info.notLeaf.child[2]);
__CFStorageSetChild(node, 1, newChild);
node->info.notLeaf.child[2] = NULL;
} else if (childNum == 1) { // Last child goes to new node
__CFStorageSetChild(anotherNode, 0, newChild);
__CFStorageSetChild(anotherNode, 1, node->info.notLeaf.child[2]);
node->info.notLeaf.child[2] = NULL;
} else { // New node contains the new comers...
__CFStorageSetChild(anotherNode, 0, node->info.notLeaf.child[2]);
__CFStorageSetChild(anotherNode, 1, newChild);
node->info.notLeaf.child[2] = NULL;
}
node->numBytes = node->info.notLeaf.child[0]->numBytes + node->info.notLeaf.child[1]->numBytes;
anotherNode->numBytes = anotherNode->info.notLeaf.child[0]->numBytes + anotherNode->info.notLeaf.child[1]->numBytes;
/* node should not be retained because it is the passed in node. anotherNode was created so we transfer its retain count */
result.sibling = anotherNode;
}
}
return result;
}
/* Returns NULL or additional node to come after this node
Assumption: size is never > storage->maxLeafCapacity
*/
static CFStorageDoubleNodeReturn __CFStorageInsertUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
ASSERT(! node->isFrozen);
if (node->isLeaf) {
return __CFStorageInsertLeafUnfrozen(allocator, storage, node, byteNum, size, absoluteByteNum);
} else {
return __CFStorageInsertBranchUnfrozen(allocator, storage, node, byteNum, size, absoluteByteNum);
}
}
#pragma mark Frozen or Unfrozen Dispatch Functions
static CFStorageDoubleNodeReturn __CFStorageInsert(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
if (node->isFrozen && ! __CFStorageThawNodeDuringMutation(storage, node)) {
return __CFStorageInsertFrozen(allocator, storage, node, byteNum, size, absoluteByteNum);
}
else {
return __CFStorageInsertUnfrozen(allocator, storage, node, byteNum, size, absoluteByteNum);
}
}
static CFStorageNode *__CFStorageDelete(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFRange range, bool compact) {
if (node->isFrozen && ! __CFStorageThawNodeDuringMutation(storage, node)) {
return __CFStorageDeleteFrozen(allocator, storage, node, range);
}
else {
return __CFStorageDeleteUnfrozen(allocator, storage, node, range, compact, false/*isRootNode*/);
}
}
#pragma mark Utility functions
CF_INLINE CFIndex __CFStorageGetCount(CFStorageRef storage) {
return __CFStorageConvertByteToValue(storage, storage->rootNode.numBytes);
}
static Boolean __CFStorageEqual(CFTypeRef cf1, CFTypeRef cf2) {
CFStorageRef storage1 = (CFStorageRef)cf1;
CFStorageRef storage2 = (CFStorageRef)cf2;
CFIndex loc, count, valueSize;
CFRange range1, range2;
uint8_t *ptr1, *ptr2;
count = __CFStorageGetCount(storage1);
if (count != __CFStorageGetCount(storage2)) return false;
valueSize = __CFStorageGetValueSize(storage1);
if (valueSize != __CFStorageGetValueSize(storage2)) return false;
loc = range1.location = range1.length = range2.location = range2.length = 0;
ptr1 = ptr2 = NULL;
while (loc < count) {
CFIndex cntThisTime;
if (loc >= range1.location + range1.length) ptr1 = (uint8_t *)CFStorageGetValueAtIndex(storage1, loc, &range1);
if (loc >= range2.location + range2.length) ptr2 = (uint8_t *)CFStorageGetValueAtIndex(storage2, loc, &range2);
cntThisTime = range1.location + range1.length;
if (range2.location + range2.length < cntThisTime) cntThisTime = range2.location + range2.length;
cntThisTime -= loc;
if (memcmp(ptr1, ptr2, valueSize * cntThisTime) != 0) return false;
ptr1 += valueSize * cntThisTime;
ptr2 += valueSize * cntThisTime;
loc += cntThisTime;
}
return true;
}
static CFHashCode __CFStorageHash(CFTypeRef cf) {
CFStorageRef Storage = (CFStorageRef)cf;
return __CFStorageGetCount(Storage);
}
static void __CFStorageDescribeNode(CFStorageNode *node, CFMutableStringRef str, CFIndex level) {
int cnt;
for (cnt = 0; cnt < level; cnt++) CFStringAppendCString(str, " ", CFStringGetSystemEncoding());
if (node->isLeaf) {
CFStringAppendFormat(str, NULL, CFSTR("Leaf %ld/%ld (%p) refcount: %u frozen: %s\n"), node->numBytes, node->info.leaf.capacityInBytes, node, node->refCount, node->isFrozen ? "yes" : "no");
} else {
CFStringAppendFormat(str, NULL, CFSTR("Node %ld (%p) refcount: %u frozen: %s\n"), node->numBytes, node, node->refCount, node->isFrozen ? "yes" : "no");
for (cnt = 0; cnt < 3; cnt++) if (node->info.notLeaf.child[cnt]) __CFStorageDescribeNode(node->info.notLeaf.child[cnt], str, level+1);
}
}
static CFIndex __CFStorageGetNodeCapacity(CFStorageNode *node) {
if (!node) return 0;
if (node->isLeaf) return node->info.leaf.capacityInBytes;
return __CFStorageGetNodeCapacity(node->info.notLeaf.child[0]) + __CFStorageGetNodeCapacity(node->info.notLeaf.child[1]) + __CFStorageGetNodeCapacity(node->info.notLeaf.child[2]);
}
CFIndex __CFStorageGetCapacity(CFStorageRef storage) {
return __CFStorageConvertByteToValue(storage, __CFStorageGetNodeCapacity(&storage->rootNode));
}
CFIndex __CFStorageGetValueSize(CFStorageRef storage) {
return storage->valueSize;
}
static CFStringRef __CFStorageCopyDescription(CFTypeRef cf) {
CFStorageRef storage = (CFStorageRef)cf;
CFMutableStringRef result;
CFAllocatorRef allocator = CFGetAllocator(storage);
result = CFStringCreateMutable(allocator, 0);
CFStringAppendFormat(result, NULL, CFSTR("<CFStorage %p [%p]>[count = %lu, capacity = %lu]\n"), storage, allocator, (unsigned long)__CFStorageGetCount(storage), (unsigned long)__CFStorageGetCapacity(storage));
__CFStorageDescribeNode(&storage->rootNode, result, 0);
return result;
}
/* Returns true if enumeration should stop, false if it should continue. */
static bool __CFStorageEnumerateNodesInByteRangeWithBlock(CFStorageRef storage, CFStorageNode *node, CFIndex globalOffsetOfNode, CFRange range, CFIndex concurrencyToken, CFStorageApplierBlock applier) {
bool stop = false;
if (node->isLeaf) {
CFIndex start = range.location;
CFIndex length = __CFMin(range.length, node->numBytes - start);
if (! node->info.leaf.memory) {
__CFStorageAllocLeafNodeMemory(CFGetAllocator(storage), storage, node, node->numBytes, false);
}
applier(node->info.leaf.memory + start, __CFStorageConvertBytesToValueRange(storage, globalOffsetOfNode + start, length), &stop);
}
else {
CFStorageNode *children[3] = {node->info.notLeaf.child[0], node->info.notLeaf.child[1], node->info.notLeaf.child[2]};
const CFIndex lengths[3] = {children[0]->numBytes, children[1] ? children[1]->numBytes : 0, children[2] ? children[2]->numBytes : 0};
const CFIndex offsets[3] = {0, lengths[0], lengths[0] + lengths[1]};
const CFRange overlaps[3] = {intersectionRange(CFRangeMake(offsets[0], lengths[0]), range), intersectionRange(CFRangeMake(offsets[1], lengths[1]), range), intersectionRange(CFRangeMake(offsets[2], lengths[2]), range)};
CFIndex numOverlappingChildren = (!! overlaps[0].length + !! overlaps[1].length + !! overlaps[2].length);