CoreFoundation/String.subproj/CFRunArray.c - third_party/swift-corelibs-foundation - Git at Google

 // This source file is part of the Swift.org open source project
 //
 // Copyright (c) 2014 - 2015 Apple Inc. and the Swift project authors
 // Licensed under Apache License v2.0 with Runtime Library Exception
 //
 // See http://swift.org/LICENSE.txt for license information
 // See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
 //


 /*	CFRunArray.c
 	Copyright (c) 2004-2015, Apple Inc. All rights reserved.
 */

 #include "CFRunArray.h"
 #include <CoreFoundation/CFString.h>
 #include "CFInternal.h"

 /* CFRunArrayGuts (which holds an array of CFRunArrayItems) is the actual data keeper; the objects just point at these... CFRunArrayGuts has copy-on-write behavior.
 */
 typedef struct {
     CFIndex length;
     CFTypeRef obj;
 } CFRunArrayItem;

 typedef struct _CFRunArrayGuts {	/* Variable sized block. */
     CFIndex numRefs;                        /* For "copy on write" behavior */
     CFIndex length;                         /* Total count of values stored by the CFRunArrayItems in list */
     CFIndex numBlocks, maxBlocks;           /* These describe the number of CFRunArrayItems in list */
     CFIndex cachedBlock, cachedLocation;    /* Cache from last lookup */
     CFRunArrayItem list[0]; /* GCC */
 } CFRunArrayGuts;

 /* Definition of the CF struct for CFRunArray
 */
 struct __CFRunArray {
     CFRuntimeBase base;
     CFRunArrayGuts *guts;
 };

 /* EXTERNCOPY is used with objects coming in from the outside world, COPY is used with objects that have already been EXTERNCOPY'ed once.
 */
 #define FREE(obj) CFRelease(obj)
 #define COPY(obj) CFRetain(obj)
 #define EXTERNCOPY(obj) CFRetain(obj)
 #define ISSAME(obj1, obj2) (CFEqual(obj1, obj2))

 /* To protect accesses to the refcounts of shared CFRunArrayGuts
 */
 static CFLock_t runArrayLock = CFLockInit;
 #define RLEARRAYLOCK {__CFLock(&runArrayLock);}
 #define RLEARRAYUNLOCK {__CFUnlock(&runArrayLock);}


 /*** Internal utility ***/

 /* Return the block number in the run array. Use cache if possible.
 */
 static CFIndex blockForLocation(CFRunArrayGuts *guts, CFIndex location, CFRange *effectiveRange) {
     CFIndex loc, block;
     if (location > (guts->cachedLocation / 2)) {	/* Yes, we can use the cached values as our starting point */
         loc = guts->cachedLocation;
         block = guts->cachedBlock;
     } else {
         loc = block = 0;
     }
     if (loc <= location) {	/* Going forwards */
         while (loc + guts->list[block].length <= location) loc += guts->list[block++].length;
     } else {	/* Going backwards */
         do loc -= guts->list[--block].length; while ((block > 0) && (loc > location));
     }
     guts->cachedLocation = loc;
     guts->cachedBlock = block;
     if (effectiveRange) {
         effectiveRange->location = loc;
         effectiveRange->length = guts->list[block].length;
     }
     return block;
 }

 /* Gives the receiver its own copy of the argument list, reduces the ref count of the original. The original list is assumed to have a ref count > 1 (it's not freed). If oldGuts is not NULL, should be called when protected by a lock. Note that this may change array->guts, so any caches of this should be refreshed!
 */
 static void __CFRunArrayMakeNewList(CFRunArrayRef array, CFRunArrayGuts *oldGuts) {
     CFIndex maxBlocks = (oldGuts ? oldGuts->numBlocks : 2);
     CFRunArrayGuts *newGuts = (CFRunArrayGuts *)CFAllocatorAllocate(CFGetAllocator(array), sizeof(CFRunArrayGuts) + maxBlocks * sizeof(CFRunArrayItem), 0);
     newGuts->maxBlocks = maxBlocks;
     if (oldGuts) {
 	CFIndex cnt;
 	for (cnt = 0; cnt < oldGuts->numBlocks; cnt++) {
 	    newGuts->list[cnt].length = oldGuts->list[cnt].length;
 	    newGuts->list[cnt].obj = COPY(oldGuts->list[cnt].obj);
 	}
 	newGuts->numBlocks = oldGuts->numBlocks;
 	newGuts->cachedBlock = oldGuts->cachedBlock;
 	newGuts->cachedLocation = oldGuts->cachedLocation;
 	newGuts->length = oldGuts->length;
 	oldGuts->numRefs--;	// !!! We assume the caller has locked; if we have separate locks per RLEArray, need one here
     } else {
 	newGuts->length = newGuts->numBlocks = newGuts->cachedBlock = newGuts->cachedLocation = 0;
     }
     newGuts->numRefs = 1;
     ((struct __CFRunArray *)array)->guts = newGuts;
 }

 /* When you call this, don't forget to recache guts afterwards, if it was cached in a local
 */
 static void __CFRunArraySetBlockCapacity(CFRunArrayRef array, CFIndex desiredCount) {
     #define MINSIZE 1
     if (desiredCount < MINSIZE) desiredCount = MINSIZE;
     /* We realloc either when there isn't enough room, or when the needed size is less than half of what's there. In both cases we allocate 33% extra. */
     if ((array->guts->maxBlocks < desiredCount) || (array->guts->maxBlocks / 2) > desiredCount) {
 	CFIndex newCapacity = ((desiredCount + 3) / 3) * 4;
 	((struct __CFRunArray *)array)->guts = (CFRunArrayGuts *)CFAllocatorReallocate(CFGetAllocator(array), array->guts, sizeof(CFRunArrayGuts) + newCapacity * sizeof(CFRunArrayItem), 0);
 	array->guts->maxBlocks = newCapacity;
     }
 }


 /*** "Polymorphic" functions ***/

 static Boolean __CFRunArrayEqual(CFTypeRef cf1, CFTypeRef cf2) {
     return false;   // ???
 }

 static CFHashCode __CFRunArrayHash(CFTypeRef cf) {
     CFRunArrayRef array = (CFRunArrayRef)cf;
     return CFRunArrayGetCount(array); // ???
 }

 static CFStringRef __CFRunArrayCopyDescription(CFTypeRef cf) {
     CFRunArrayRef array = (CFRunArrayRef)cf;
     CFRunArrayGuts *guts = array->guts;
     CFIndex cnt;
     CFMutableStringRef string = CFStringCreateMutable(kCFAllocatorSystemDefault, 0);
     CFStringAppendFormat(string, NULL, CFSTR("%ld blocks used, total length %ld (%ld blocks, block %ld is at %ld)\n"), (long)guts->numBlocks, (long)guts->length, (long)guts->maxBlocks, (long)guts->cachedBlock, (long)guts->cachedLocation);
     for (cnt = 0; cnt < guts->numBlocks; cnt++) CFStringAppendFormat(string, NULL, CFSTR(" %ld %p %@\n"), (long)guts->list[cnt].length, guts->list[cnt].obj, guts->list[cnt].obj);
     return string;
 }

 static void __CFRunArrayDeallocate(CFTypeRef cf) {
     CFRunArrayRef array = (CFRunArrayRef)cf;
     CFRunArrayGuts *guts = array->guts;

     RLEARRAYLOCK;
     if (guts->numRefs <= 1) {
         RLEARRAYUNLOCK;
         CFIndex cnt;
         for (cnt = 0; cnt < guts->numBlocks; cnt++) {
             FREE(guts->list[cnt].obj);
         }
         CFAllocatorDeallocate(CFGetAllocator(array), guts);
     } else {
         guts->numRefs--;
         RLEARRAYUNLOCK;
     }
 }

 static CFTypeID __kCFRunArrayTypeID = _kCFRuntimeNotATypeID;

 static const CFRuntimeClass __CFRunArrayClass = {
     0,
     "CFRunArray",
     NULL,	// init
     NULL,	// copy
     __CFRunArrayDeallocate,
     __CFRunArrayEqual,
     __CFRunArrayHash,
     NULL,	//
     __CFRunArrayCopyDescription
 };

 CFTypeID CFRunArrayGetTypeID(void) {
     static dispatch_once_t initOnce;
     dispatch_once(&initOnce, ^{ __kCFRunArrayTypeID = _CFRuntimeRegisterClass(&__CFRunArrayClass); });
     return __kCFRunArrayTypeID;
 }


 /*** CFRunArray ***/

 CFRunArrayRef _CFRunArrayCreateWithGuts(CFAllocatorRef allocator, struct _CFRunArrayGuts *runArrayGuts) {
     CFIndex size = sizeof(struct __CFRunArray) - sizeof(CFRuntimeBase);
     CFRunArrayRef array = (CFRunArrayRef)_CFRuntimeCreateInstance(allocator, CFRunArrayGetTypeID(), size, NULL);
     if (array == NULL) return NULL;

     if (runArrayGuts) {
         array->guts = runArrayGuts;
         RLEARRAYLOCK;
         array->guts->numRefs++;
         RLEARRAYUNLOCK;
     } else {
         __CFRunArrayMakeNewList(array, NULL);
     }

     return array;
 }


 CFRunArrayRef CFRunArrayCreate(CFAllocatorRef allocator) {
     CFRunArrayRef array = _CFRunArrayCreateWithGuts(allocator, NULL);
     return array;
 }

 CFIndex CFRunArrayGetCount(CFRunArrayRef array) {
     return array->guts->length;
 }

 CFTypeRef CFRunArrayGetValueAtIndex(CFRunArrayRef array, CFIndex loc, CFRange *effectiveRange, CFIndex *blockIndexPtr) {
     // ??? if (loc >= array->guts->length) BoundsError;
     CFIndex blockIndex = blockForLocation(array->guts, loc, effectiveRange);
     if (blockIndexPtr) *blockIndexPtr = blockIndex;
     return array->guts->list[blockIndex].obj;
 }

 CFTypeRef CFRunArrayGetValueAtRunArrayIndex(CFRunArrayRef array, CFIndex blockIndex, CFIndex *lengthPtr) {
     if (blockIndex >= array->guts->numBlocks) return NULL;
     if (lengthPtr) *lengthPtr = array->guts->list[blockIndex].length;
     return array->guts->list[blockIndex].obj;
 }

 void CFRunArrayInsert(CFRunArrayRef array, CFRange range, CFTypeRef obj) {
     CFRunArrayGuts *guts = array->guts;

     // ??? if (range.location > guts->length) BoundsError;
     if (range.length == 0) return;

     RLEARRAYLOCK;
     if (guts->numRefs > 1) {
 	__CFRunArrayMakeNewList(array, guts);
 	guts = array->guts;	// Refresh
     }
     RLEARRAYUNLOCK;


     if (range.location == guts->length) {	// Append
 	if (guts->length > 0) {	// The list isn't empty
 	    if (ISSAME(obj, guts->list[guts->numBlocks - 1].obj)) {
 		guts->list[guts->numBlocks - 1].length += range.length;
 		// We might have invalidated the cached info, fix it up!
 		if (guts->cachedBlock >= guts->numBlocks) guts->cachedLocation += range.length;
 	    } else {
                 __CFRunArraySetBlockCapacity(array, guts->numBlocks + 1);
 		guts = array->guts; // Recache
 		guts->list[guts->numBlocks].obj = EXTERNCOPY(obj);
 		guts->list[guts->numBlocks].length = range.length;
 		guts->numBlocks++;
 	    }
 	} else {	// The list is empty...
             __CFRunArraySetBlockCapacity(array, 1);
 	    guts = array->guts; // Recache
 	    guts->list[0].obj = EXTERNCOPY(obj);
 	    guts->list[0].length = range.length;
 	    guts->numBlocks++;
 	}
     } else {	// At this stage we are inserting, and the length of the list is > 0.
 	CFRange blockRange;
 	CFIndex cnt, block = blockForLocation(guts, range.location, &blockRange);
 	if (ISSAME(obj, guts->list[block].obj)) {
 	    guts->list[block].length += range.length;
 	} else if ((block > 0) && (blockRange.location == range.location) && (ISSAME(obj, guts->list[block - 1].obj))) {
 	    guts->list[block - 1].length += range.length;
 	    // We might have invalidated the cached info, fix it up!
 	    if (guts->cachedBlock >= block) guts->cachedLocation += range.length;
 	} else if (blockRange.location == range.location) {
             __CFRunArraySetBlockCapacity(array, guts->numBlocks + 1);
 	    guts = array->guts; // Recache
 	    for (cnt = guts->numBlocks; cnt > block; cnt--) guts->list[cnt] = guts->list[cnt - 1];
 	    guts->list[block].obj = EXTERNCOPY(obj);
 	    guts->list[block].length = range.length;
 	    guts->numBlocks++;
 	} else {
             __CFRunArraySetBlockCapacity(array, guts->numBlocks + 2);
 	    guts = array->guts; // Recache
 	    for (cnt = guts->numBlocks + 1; cnt >= block + 2; cnt--) guts->list[cnt] = guts->list[cnt - 2];
 	    guts->list[block + 1].obj = EXTERNCOPY(obj);
 	    guts->list[block + 1].length = range.length;
 	    guts->list[block].length = (range.location - blockRange.location);
 	    guts->list[block + 2].obj = COPY(guts->list[block].obj);
 	    guts->list[block + 2].length = blockRange.length - (range.location - blockRange.location);
 	    guts->numBlocks += 2;
 	}
     }
     guts->length += range.length;
 }

 void CFRunArrayDelete(CFRunArrayRef array, CFRange range) {
     CFRunArrayReplace(array, range, NULL, 0);
 }

 void CFRunArrayReplace(CFRunArrayRef array, CFRange range, CFTypeRef newObject, CFIndex newLength) {
     CFRunArrayGuts *guts = array->guts;
     CFRange blockRange;
     CFIndex block, toBeDeleted, firstEmptyBlock, lastEmptyBlock;

     // ??? if (range.location + range.length > guts->length) BoundsError;
     if (range.length == 0) return;

     if (newLength == 0) newObject = NULL;

     RLEARRAYLOCK;
     if (guts->numRefs > 1) {
 	__CFRunArrayMakeNewList(array, guts);
 	guts = array->guts;	// Refresh
     }
     RLEARRAYUNLOCK;

     /* This call also sets the cache to point to this block */
     block = blockForLocation(guts, range.location, &blockRange);
     guts->length -= range.length;

     /* Figure out how much to delete from this block */
     toBeDeleted = blockRange.length - (range.location - blockRange.location);
     if (toBeDeleted > range.length) toBeDeleted = range.length;

     /* Delete that count */
     if ((guts->list[block].length -= toBeDeleted) == 0) FREE(guts->list[block].obj);
     range.length -= toBeDeleted;
     firstEmptyBlock = (guts->list[block].length == 0) ? block : block + 1;

     while (range.length) {
 	block++;
 	toBeDeleted = range.length;
 	if (toBeDeleted >= guts->list[block].length) toBeDeleted = guts->list[block].length;
 	if ((guts->list[block].length -= toBeDeleted) == 0) FREE(guts->list[block].obj);
 	range.length -= toBeDeleted;
     }

     lastEmptyBlock = (block == 0 || guts->list[block].length == 0) ? block : block - 1;

     if (firstEmptyBlock <= lastEmptyBlock) {	/* Do we have any blocks that need to be removed? */
         /* One assumption at this point is that the cache isn't beyond firstEmptyBlock */
         if ((firstEmptyBlock > 0) && (firstEmptyBlock == guts->cachedBlock)) {	/* Update the cachedBlock it's pointing at the hole */
             guts->cachedLocation -= guts->list[firstEmptyBlock - 1].length;
             guts->cachedBlock--;	/* Simply make the cached block be the previous one */
         }
         if (newObject) {	/* See if the new object can be merged with one of the end blocks */
             if ((firstEmptyBlock > 0) && ISSAME(guts->list[firstEmptyBlock - 1].obj, newObject)) {
                 guts->list[firstEmptyBlock - 1].length += newLength;
                 guts->length += newLength;
 		newObject = NULL;
             } else if ((lastEmptyBlock + 1 < guts->numBlocks) && ISSAME(guts->list[lastEmptyBlock + 1].obj, newObject)) {
                 guts->list[lastEmptyBlock + 1].length += newLength;
                 guts->length += newLength;
                 newObject = NULL;
             }
         }
         if (!newObject && (firstEmptyBlock > 0) && (lastEmptyBlock + 1 < guts->numBlocks) && ISSAME(guts->list[firstEmptyBlock - 1].obj, guts->list[lastEmptyBlock + 1].obj)) {	/* Can we merge the blocks around the empty space? */
 	    /* Often the cachedBlock will point before the firstEmptyBlock; however, if it happens to be pointing at the firstEmptyBlock, we need to move it back. */
 	    lastEmptyBlock++;
 	    guts->list[firstEmptyBlock - 1].length += guts->list[lastEmptyBlock].length;
 	    FREE(guts->list[lastEmptyBlock].obj);
 	}
         if (newObject && (firstEmptyBlock < guts->numBlocks) /* Sanity check */) {	/* Slip this into the first empty block */
             guts->list[firstEmptyBlock].obj = EXTERNCOPY(newObject);
             guts->list[firstEmptyBlock].length = newLength;
             guts->length += newLength;
             firstEmptyBlock++;
             newObject = NULL;
         }
         if (firstEmptyBlock <= lastEmptyBlock) {	/* Do we still need to shift anything over? */
             CFIndex toBeMoved = guts->numBlocks - lastEmptyBlock - 1;
             CFIndex firstFullBlock = lastEmptyBlock + 1;
             for (block = 0; block < toBeMoved; block++) {
                 guts->list[firstEmptyBlock + block] = guts->list[firstFullBlock + block];
             }
             guts->numBlocks -= (firstFullBlock - firstEmptyBlock);
             __CFRunArraySetBlockCapacity(array, guts->numBlocks);
         }
     }
     if (newObject) {	/* If this is still set, that means we didn't get to insert it... Do it now. */
         CFRunArrayInsert(array, CFRangeMake(range.location, newLength), newObject);
     }
 }
	// This source file is part of the Swift.org open source project
	//
	// Copyright (c) 2014 - 2015 Apple Inc. and the Swift project authors
	// Licensed under Apache License v2.0 with Runtime Library Exception
	//
	// See http://swift.org/LICENSE.txt for license information
	// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
	//


	/* CFRunArray.c
	Copyright (c) 2004-2015, Apple Inc. All rights reserved.
	*/

	#include "CFRunArray.h"
	#include <CoreFoundation/CFString.h>
	#include "CFInternal.h"

	/* CFRunArrayGuts (which holds an array of CFRunArrayItems) is the actual data keeper; the objects just point at these... CFRunArrayGuts has copy-on-write behavior.
	*/
	typedef struct {
	CFIndex length;
	CFTypeRef obj;
	} CFRunArrayItem;

	typedef struct _CFRunArrayGuts { /* Variable sized block. */
	CFIndex numRefs; /* For "copy on write" behavior */
	CFIndex length; /* Total count of values stored by the CFRunArrayItems in list */
	CFIndex numBlocks, maxBlocks; /* These describe the number of CFRunArrayItems in list */
	CFIndex cachedBlock, cachedLocation; /* Cache from last lookup */
	CFRunArrayItem list[0]; /* GCC */
	} CFRunArrayGuts;

	/* Definition of the CF struct for CFRunArray
	*/
	struct __CFRunArray {
	CFRuntimeBase base;
	CFRunArrayGuts *guts;
	};

	/* EXTERNCOPY is used with objects coming in from the outside world, COPY is used with objects that have already been EXTERNCOPY'ed once.
	*/
	#define FREE(obj) CFRelease(obj)
	#define COPY(obj) CFRetain(obj)
	#define EXTERNCOPY(obj) CFRetain(obj)
	#define ISSAME(obj1, obj2) (CFEqual(obj1, obj2))

	/* To protect accesses to the refcounts of shared CFRunArrayGuts
	*/
	static CFLock_t runArrayLock = CFLockInit;
	#define RLEARRAYLOCK {__CFLock(&runArrayLock);}
	#define RLEARRAYUNLOCK {__CFUnlock(&runArrayLock);}



	/* Internal utility */

	/* Return the block number in the run array. Use cache if possible.
	*/
	static CFIndex blockForLocation(CFRunArrayGuts guts, CFIndex location, CFRange effectiveRange) {
	CFIndex loc, block;
	if (location > (guts->cachedLocation / 2)) { /* Yes, we can use the cached values as our starting point */
	loc = guts->cachedLocation;
	block = guts->cachedBlock;
	} else {
	loc = block = 0;
	}
	if (loc <= location) { /* Going forwards */
	while (loc + guts->list[block].length <= location) loc += guts->list[block++].length;
	} else { /* Going backwards */
	do loc -= guts->list[--block].length; while ((block > 0) && (loc > location));
	}
	guts->cachedLocation = loc;
	guts->cachedBlock = block;
	if (effectiveRange) {
	effectiveRange->location = loc;
	effectiveRange->length = guts->list[block].length;
	}
	return block;
	}

	/* Gives the receiver its own copy of the argument list, reduces the ref count of the original. The original list is assumed to have a ref count > 1 (it's not freed). If oldGuts is not NULL, should be called when protected by a lock. Note that this may change array->guts, so any caches of this should be refreshed!
	*/
	static void __CFRunArrayMakeNewList(CFRunArrayRef array, CFRunArrayGuts *oldGuts) {
	CFIndex maxBlocks = (oldGuts ? oldGuts->numBlocks : 2);
	CFRunArrayGuts newGuts = (CFRunArrayGuts )CFAllocatorAllocate(CFGetAllocator(array), sizeof(CFRunArrayGuts) + maxBlocks * sizeof(CFRunArrayItem), 0);
	newGuts->maxBlocks = maxBlocks;
	if (oldGuts) {
	CFIndex cnt;
	for (cnt = 0; cnt < oldGuts->numBlocks; cnt++) {
	newGuts->list[cnt].length = oldGuts->list[cnt].length;
	newGuts->list[cnt].obj = COPY(oldGuts->list[cnt].obj);
	}
	newGuts->numBlocks = oldGuts->numBlocks;
	newGuts->cachedBlock = oldGuts->cachedBlock;
	newGuts->cachedLocation = oldGuts->cachedLocation;
	newGuts->length = oldGuts->length;
	oldGuts->numRefs--; // !!! We assume the caller has locked; if we have separate locks per RLEArray, need one here
	} else {
	newGuts->length = newGuts->numBlocks = newGuts->cachedBlock = newGuts->cachedLocation = 0;
	}
	newGuts->numRefs = 1;
	((struct __CFRunArray *)array)->guts = newGuts;
	}

	/* When you call this, don't forget to recache guts afterwards, if it was cached in a local
	*/
	static void __CFRunArraySetBlockCapacity(CFRunArrayRef array, CFIndex desiredCount) {
	#define MINSIZE 1
	if (desiredCount < MINSIZE) desiredCount = MINSIZE;
	/* We realloc either when there isn't enough room, or when the needed size is less than half of what's there. In both cases we allocate 33% extra. */
	if ((array->guts->maxBlocks < desiredCount) \|\| (array->guts->maxBlocks / 2) > desiredCount) {
	CFIndex newCapacity = ((desiredCount + 3) / 3) * 4;
	((struct __CFRunArray )array)->guts = (CFRunArrayGuts )CFAllocatorReallocate(CFGetAllocator(array), array->guts, sizeof(CFRunArrayGuts) + newCapacity * sizeof(CFRunArrayItem), 0);
	array->guts->maxBlocks = newCapacity;
	}
	}



	/* "Polymorphic" functions */

	static Boolean __CFRunArrayEqual(CFTypeRef cf1, CFTypeRef cf2) {
	return false; // ???
	}

	static CFHashCode __CFRunArrayHash(CFTypeRef cf) {
	CFRunArrayRef array = (CFRunArrayRef)cf;
	return CFRunArrayGetCount(array); // ???
	}

	static CFStringRef __CFRunArrayCopyDescription(CFTypeRef cf) {
	CFRunArrayRef array = (CFRunArrayRef)cf;
	CFRunArrayGuts *guts = array->guts;
	CFIndex cnt;
	CFMutableStringRef string = CFStringCreateMutable(kCFAllocatorSystemDefault, 0);
	CFStringAppendFormat(string, NULL, CFSTR("%ld blocks used, total length %ld (%ld blocks, block %ld is at %ld)\n"), (long)guts->numBlocks, (long)guts->length, (long)guts->maxBlocks, (long)guts->cachedBlock, (long)guts->cachedLocation);
	for (cnt = 0; cnt < guts->numBlocks; cnt++) CFStringAppendFormat(string, NULL, CFSTR(" %ld %p %@\n"), (long)guts->list[cnt].length, guts->list[cnt].obj, guts->list[cnt].obj);
	return string;
	}

	static void __CFRunArrayDeallocate(CFTypeRef cf) {
	CFRunArrayRef array = (CFRunArrayRef)cf;
	CFRunArrayGuts *guts = array->guts;

	RLEARRAYLOCK;
	if (guts->numRefs <= 1) {
	RLEARRAYUNLOCK;
	CFIndex cnt;
	for (cnt = 0; cnt < guts->numBlocks; cnt++) {
	FREE(guts->list[cnt].obj);
	}
	CFAllocatorDeallocate(CFGetAllocator(array), guts);
	} else {
	guts->numRefs--;
	RLEARRAYUNLOCK;
	}
	}

	static CFTypeID __kCFRunArrayTypeID = _kCFRuntimeNotATypeID;

	static const CFRuntimeClass __CFRunArrayClass = {
	0,
	"CFRunArray",
	NULL, // init
	NULL, // copy
	__CFRunArrayDeallocate,
	__CFRunArrayEqual,
	__CFRunArrayHash,
	NULL, //
	__CFRunArrayCopyDescription
	};

	CFTypeID CFRunArrayGetTypeID(void) {
	static dispatch_once_t initOnce;
	dispatch_once(&initOnce, ^{ __kCFRunArrayTypeID = _CFRuntimeRegisterClass(&__CFRunArrayClass); });
	return __kCFRunArrayTypeID;
	}


	/* CFRunArray */

	CFRunArrayRef _CFRunArrayCreateWithGuts(CFAllocatorRef allocator, struct _CFRunArrayGuts *runArrayGuts) {
	CFIndex size = sizeof(struct __CFRunArray) - sizeof(CFRuntimeBase);
	CFRunArrayRef array = (CFRunArrayRef)_CFRuntimeCreateInstance(allocator, CFRunArrayGetTypeID(), size, NULL);
	if (array == NULL) return NULL;

	if (runArrayGuts) {
	array->guts = runArrayGuts;
	RLEARRAYLOCK;
	array->guts->numRefs++;
	RLEARRAYUNLOCK;
	} else {
	__CFRunArrayMakeNewList(array, NULL);
	}

	return array;
	}


	CFRunArrayRef CFRunArrayCreate(CFAllocatorRef allocator) {
	CFRunArrayRef array = _CFRunArrayCreateWithGuts(allocator, NULL);
	return array;
	}

	CFIndex CFRunArrayGetCount(CFRunArrayRef array) {
	return array->guts->length;
	}

	CFTypeRef CFRunArrayGetValueAtIndex(CFRunArrayRef array, CFIndex loc, CFRange effectiveRange, CFIndex blockIndexPtr) {
	// ??? if (loc >= array->guts->length) BoundsError;
	CFIndex blockIndex = blockForLocation(array->guts, loc, effectiveRange);
	if (blockIndexPtr) *blockIndexPtr = blockIndex;
	return array->guts->list[blockIndex].obj;
	}

	CFTypeRef CFRunArrayGetValueAtRunArrayIndex(CFRunArrayRef array, CFIndex blockIndex, CFIndex *lengthPtr) {
	if (blockIndex >= array->guts->numBlocks) return NULL;
	if (lengthPtr) *lengthPtr = array->guts->list[blockIndex].length;
	return array->guts->list[blockIndex].obj;
	}

	void CFRunArrayInsert(CFRunArrayRef array, CFRange range, CFTypeRef obj) {
	CFRunArrayGuts *guts = array->guts;

	// ??? if (range.location > guts->length) BoundsError;
	if (range.length == 0) return;

	RLEARRAYLOCK;
	if (guts->numRefs > 1) {
	__CFRunArrayMakeNewList(array, guts);
	guts = array->guts; // Refresh
	}
	RLEARRAYUNLOCK;


	if (range.location == guts->length) { // Append
	if (guts->length > 0) { // The list isn't empty
	if (ISSAME(obj, guts->list[guts->numBlocks - 1].obj)) {
	guts->list[guts->numBlocks - 1].length += range.length;
	// We might have invalidated the cached info, fix it up!
	if (guts->cachedBlock >= guts->numBlocks) guts->cachedLocation += range.length;
	} else {
	__CFRunArraySetBlockCapacity(array, guts->numBlocks + 1);
	guts = array->guts; // Recache
	guts->list[guts->numBlocks].obj = EXTERNCOPY(obj);
	guts->list[guts->numBlocks].length = range.length;
	guts->numBlocks++;
	}
	} else { // The list is empty...
	__CFRunArraySetBlockCapacity(array, 1);
	guts = array->guts; // Recache
	guts->list[0].obj = EXTERNCOPY(obj);
	guts->list[0].length = range.length;
	guts->numBlocks++;
	}
	} else { // At this stage we are inserting, and the length of the list is > 0.
	CFRange blockRange;
	CFIndex cnt, block = blockForLocation(guts, range.location, &blockRange);
	if (ISSAME(obj, guts->list[block].obj)) {
	guts->list[block].length += range.length;
	} else if ((block > 0) && (blockRange.location == range.location) && (ISSAME(obj, guts->list[block - 1].obj))) {
	guts->list[block - 1].length += range.length;
	// We might have invalidated the cached info, fix it up!
	if (guts->cachedBlock >= block) guts->cachedLocation += range.length;
	} else if (blockRange.location == range.location) {
	__CFRunArraySetBlockCapacity(array, guts->numBlocks + 1);
	guts = array->guts; // Recache
	for (cnt = guts->numBlocks; cnt > block; cnt--) guts->list[cnt] = guts->list[cnt - 1];
	guts->list[block].obj = EXTERNCOPY(obj);
	guts->list[block].length = range.length;
	guts->numBlocks++;
	} else {
	__CFRunArraySetBlockCapacity(array, guts->numBlocks + 2);
	guts = array->guts; // Recache
	for (cnt = guts->numBlocks + 1; cnt >= block + 2; cnt--) guts->list[cnt] = guts->list[cnt - 2];
	guts->list[block + 1].obj = EXTERNCOPY(obj);
	guts->list[block + 1].length = range.length;
	guts->list[block].length = (range.location - blockRange.location);
	guts->list[block + 2].obj = COPY(guts->list[block].obj);
	guts->list[block + 2].length = blockRange.length - (range.location - blockRange.location);
	guts->numBlocks += 2;
	}
	}
	guts->length += range.length;
	}

	void CFRunArrayDelete(CFRunArrayRef array, CFRange range) {
	CFRunArrayReplace(array, range, NULL, 0);
	}

	void CFRunArrayReplace(CFRunArrayRef array, CFRange range, CFTypeRef newObject, CFIndex newLength) {
	CFRunArrayGuts *guts = array->guts;
	CFRange blockRange;
	CFIndex block, toBeDeleted, firstEmptyBlock, lastEmptyBlock;

	// ??? if (range.location + range.length > guts->length) BoundsError;
	if (range.length == 0) return;

	if (newLength == 0) newObject = NULL;

	RLEARRAYLOCK;
	if (guts->numRefs > 1) {
	__CFRunArrayMakeNewList(array, guts);
	guts = array->guts; // Refresh
	}
	RLEARRAYUNLOCK;

	/* This call also sets the cache to point to this block */
	block = blockForLocation(guts, range.location, &blockRange);
	guts->length -= range.length;

	/* Figure out how much to delete from this block */
	toBeDeleted = blockRange.length - (range.location - blockRange.location);
	if (toBeDeleted > range.length) toBeDeleted = range.length;

	/* Delete that count */
	if ((guts->list[block].length -= toBeDeleted) == 0) FREE(guts->list[block].obj);
	range.length -= toBeDeleted;
	firstEmptyBlock = (guts->list[block].length == 0) ? block : block + 1;

	while (range.length) {
	block++;
	toBeDeleted = range.length;
	if (toBeDeleted >= guts->list[block].length) toBeDeleted = guts->list[block].length;
	if ((guts->list[block].length -= toBeDeleted) == 0) FREE(guts->list[block].obj);
	range.length -= toBeDeleted;
	}

	lastEmptyBlock = (block == 0 \|\| guts->list[block].length == 0) ? block : block - 1;

	if (firstEmptyBlock <= lastEmptyBlock) { /* Do we have any blocks that need to be removed? */
	/* One assumption at this point is that the cache isn't beyond firstEmptyBlock */
	if ((firstEmptyBlock > 0) && (firstEmptyBlock == guts->cachedBlock)) { /* Update the cachedBlock it's pointing at the hole */
	guts->cachedLocation -= guts->list[firstEmptyBlock - 1].length;
	guts->cachedBlock--; /* Simply make the cached block be the previous one */
	}
	if (newObject) { /* See if the new object can be merged with one of the end blocks */
	if ((firstEmptyBlock > 0) && ISSAME(guts->list[firstEmptyBlock - 1].obj, newObject)) {
	guts->list[firstEmptyBlock - 1].length += newLength;
	guts->length += newLength;
	newObject = NULL;
	} else if ((lastEmptyBlock + 1 < guts->numBlocks) && ISSAME(guts->list[lastEmptyBlock + 1].obj, newObject)) {
	guts->list[lastEmptyBlock + 1].length += newLength;
	guts->length += newLength;
	newObject = NULL;
	}
	}
	if (!newObject && (firstEmptyBlock > 0) && (lastEmptyBlock + 1 < guts->numBlocks) && ISSAME(guts->list[firstEmptyBlock - 1].obj, guts->list[lastEmptyBlock + 1].obj)) { /* Can we merge the blocks around the empty space? */
	/* Often the cachedBlock will point before the firstEmptyBlock; however, if it happens to be pointing at the firstEmptyBlock, we need to move it back. */
	lastEmptyBlock++;
	guts->list[firstEmptyBlock - 1].length += guts->list[lastEmptyBlock].length;
	FREE(guts->list[lastEmptyBlock].obj);
	}
	if (newObject && (firstEmptyBlock < guts->numBlocks) /* Sanity check /) { / Slip this into the first empty block */
	guts->list[firstEmptyBlock].obj = EXTERNCOPY(newObject);
	guts->list[firstEmptyBlock].length = newLength;
	guts->length += newLength;
	firstEmptyBlock++;
	newObject = NULL;
	}
	if (firstEmptyBlock <= lastEmptyBlock) { /* Do we still need to shift anything over? */
	CFIndex toBeMoved = guts->numBlocks - lastEmptyBlock - 1;
	CFIndex firstFullBlock = lastEmptyBlock + 1;
	for (block = 0; block < toBeMoved; block++) {
	guts->list[firstEmptyBlock + block] = guts->list[firstFullBlock + block];
	}
	guts->numBlocks -= (firstFullBlock - firstEmptyBlock);
	__CFRunArraySetBlockCapacity(array, guts->numBlocks);
	}
	}
	if (newObject) { /* If this is still set, that means we didn't get to insert it... Do it now. */
	CFRunArrayInsert(array, CFRangeMake(range.location, newLength), newObject);
	}
	}