#include <stdio.h>

#include <stdlib.h>

#include <stdint.h>

#include <string.h>

#include <assert.h>

#include <sys/errno.h>

#include <math.h>

#include <limits.h>

#include <objc/runtime.h>

#import "JSONKit.h"

#include <CoreFoundation/CFString.h>

#include <CoreFoundation/CFArray.h>

#include <CoreFoundation/CFDictionary.h>

#include <CoreFoundation/CFNumber.h>

#import <Foundation/NSArray.h>

#import <Foundation/NSAutoreleasePool.h>

#import <Foundation/NSData.h>

#import <Foundation/NSDictionary.h>

#import <Foundation/NSException.h>

#import <Foundation/NSNull.h>

#import <Foundation/NSObjCRuntime.h>

#ifdef JK_ENABLE_CF_TRANSFER_OWNERSHIP_CALLBACKS

#warning As of JSONKit v1.4, JK_ENABLE_CF_TRANSFER_OWNERSHIP_CALLBACKS is no longer required. It is no longer a valid option.

#endif

#ifdef __OBJC_GC__

#error JSONKit does not support Objective-C Garbage Collection

#endif

#if (UINT_MAX != 0xffffffffU) || (INT_MIN != (-0x7fffffff-1)) || (ULLONG_MAX != 0xffffffffffffffffULL) || (LLONG_MIN != (-0x7fffffffffffffffLL-1LL))

#error JSONKit requires the C 'int' and 'long long' types to be 32 and 64 bits respectively.

#endif

#if !defined(__LP64__) && ((UINT_MAX != ULONG_MAX) || (INT_MAX != LONG_MAX) || (INT_MIN != LONG_MIN) || (WORD_BIT != LONG_BIT))

#error JSONKit requires the C 'int' and 'long' types to be the same on 32-bit architectures.

#endif

#if (NSUIntegerMax != ULONG_MAX) || (NSIntegerMax != LONG_MAX) || (NSIntegerMin != LONG_MIN)

#error JSONKit requires NSInteger and NSUInteger to be the same size as the C 'long' type.

#endif

#if (NSUIntegerMax != SIZE_MAX) || (NSIntegerMax != SSIZE_MAX)

#error JSONKit requires NSInteger and NSUInteger to be the same size as the C 'size_t' type.

#endif

#define JK_HASH_INIT (1402737925UL)

#define JK_FAST_TRAILING_BYTES

#define JK_CACHE_SLOTS_BITS (10)

#define JK_CACHE_SLOTS (1UL << JK_CACHE_SLOTS_BITS)

#define JK_CACHE_PROBES (4UL)

#define JK_INIT_CACHE_AGE (0)

#define JK_TOKENBUFFER_SIZE (1024UL * 2UL)

#define JK_STACK_OBJS (1024UL * 1UL)

#define JK_JSONBUFFER_SIZE (1024UL * 4UL)

#define JK_UTF8BUFFER_SIZE (1024UL * 16UL)

#define JK_ENCODE_CACHE_SLOTS (1024UL)

#if defined (__GNUC__) && (__GNUC__ >= 4)

#define JK_ATTRIBUTES(attr, ...) __attribute__((attr, ##__VA_ARGS__))

#define JK_EXPECTED(cond, expect) __builtin_expect((long)(cond), (expect))

#define JK_EXPECT_T(cond) JK_EXPECTED(cond, 1U)

#define JK_EXPECT_F(cond) JK_EXPECTED(cond, 0U)

#define JK_PREFETCH(ptr) __builtin_prefetch(ptr)

#else // defined (__GNUC__) && (__GNUC__ >= 4)

#define JK_ATTRIBUTES(attr, ...)

#define JK_EXPECTED(cond, expect) (cond)

#define JK_EXPECT_T(cond) (cond)

#define JK_EXPECT_F(cond) (cond)

#define JK_PREFETCH(ptr)

#endif // defined (__GNUC__) && (__GNUC__ >= 4)

#define JK_STATIC_INLINE static __inline__ JK_ATTRIBUTES(always_inline)

#define JK_ALIGNED(arg) JK_ATTRIBUTES(aligned(arg))

#define JK_UNUSED_ARG JK_ATTRIBUTES(unused)

#define JK_WARN_UNUSED JK_ATTRIBUTES(warn_unused_result)

#define JK_WARN_UNUSED_CONST JK_ATTRIBUTES(warn_unused_result, const)

#define JK_WARN_UNUSED_PURE JK_ATTRIBUTES(warn_unused_result, pure)

#define JK_WARN_UNUSED_SENTINEL JK_ATTRIBUTES(warn_unused_result, sentinel)

#define JK_NONNULL_ARGS(arg, ...) JK_ATTRIBUTES(nonnull(arg, ##__VA_ARGS__))

#define JK_WARN_UNUSED_NONNULL_ARGS(arg, ...) JK_ATTRIBUTES(warn_unused_result, nonnull(arg, ##__VA_ARGS__))

#define JK_WARN_UNUSED_CONST_NONNULL_ARGS(arg, ...) JK_ATTRIBUTES(warn_unused_result, const, nonnull(arg, ##__VA_ARGS__))

#define JK_WARN_UNUSED_PURE_NONNULL_ARGS(arg, ...) JK_ATTRIBUTES(warn_unused_result, pure, nonnull(arg, ##__VA_ARGS__))

#if defined (__GNUC__) && (__GNUC__ >= 4) && (__GNUC_MINOR__ >= 3)

#define JK_ALLOC_SIZE_NON_NULL_ARGS_WARN_UNUSED(as, nn, ...) JK_ATTRIBUTES(warn_unused_result, nonnull(nn, ##__VA_ARGS__), alloc_size(as))

#else // defined (__GNUC__) && (__GNUC__ >= 4) && (__GNUC_MINOR__ >= 3)

#define JK_ALLOC_SIZE_NON_NULL_ARGS_WARN_UNUSED(as, nn, ...) JK_ATTRIBUTES(warn_unused_result, nonnull(nn, ##__VA_ARGS__))

#endif // defined (__GNUC__) && (__GNUC__ >= 4) && (__GNUC_MINOR__ >= 3)

@class JKArray, JKDictionaryEnumerator, JKDictionary;

enum {

JSONNumberStateStart = 0,

JSONNumberStateFinished = 1,

JSONNumberStateError = 2,

JSONNumberStateWholeNumberStart = 3,

JSONNumberStateWholeNumberMinus = 4,

JSONNumberStateWholeNumberZero = 5,

JSONNumberStateWholeNumber = 6,

JSONNumberStatePeriod = 7,

JSONNumberStateFractionalNumberStart = 8,

JSONNumberStateFractionalNumber = 9,

JSONNumberStateExponentStart = 10,

JSONNumberStateExponentPlusMinus = 11,

JSONNumberStateExponent = 12,

};

enum {

JSONStringStateStart = 0,

JSONStringStateParsing = 1,

JSONStringStateFinished = 2,

JSONStringStateError = 3,

JSONStringStateEscape = 4,

JSONStringStateEscapedUnicode1 = 5,

JSONStringStateEscapedUnicode2 = 6,

JSONStringStateEscapedUnicode3 = 7,

JSONStringStateEscapedUnicode4 = 8,

JSONStringStateEscapedUnicodeSurrogate1 = 9,

JSONStringStateEscapedUnicodeSurrogate2 = 10,

JSONStringStateEscapedUnicodeSurrogate3 = 11,

JSONStringStateEscapedUnicodeSurrogate4 = 12,

JSONStringStateEscapedNeedEscapeForSurrogate = 13,

JSONStringStateEscapedNeedEscapedUForSurrogate = 14,

};

enum {

JKParseAcceptValue = (1 << 0),

JKParseAcceptComma = (1 << 1),

JKParseAcceptEnd = (1 << 2),

JKParseAcceptValueOrEnd = (JKParseAcceptValue | JKParseAcceptEnd),

JKParseAcceptCommaOrEnd = (JKParseAcceptComma | JKParseAcceptEnd),

};

enum {

JKClassUnknown = 0,

JKClassString = 1,

JKClassNumber = 2,

JKClassArray = 3,

JKClassDictionary = 4,

JKClassNull = 5,

};

enum {

JKManagedBufferOnStack = 1,

JKManagedBufferOnHeap = 2,

JKManagedBufferLocationMask = (0x3),

JKManagedBufferLocationShift = (0),

JKManagedBufferMustFree = (1 << 2),

};

typedef JKFlags JKManagedBufferFlags;

enum {

JKObjectStackOnStack = 1,

JKObjectStackOnHeap = 2,

JKObjectStackLocationMask = (0x3),

JKObjectStackLocationShift = (0),

JKObjectStackMustFree = (1 << 2),

};

typedef JKFlags JKObjectStackFlags;

enum {

JKTokenTypeInvalid = 0,

JKTokenTypeNumber = 1,

JKTokenTypeString = 2,

JKTokenTypeObjectBegin = 3,

JKTokenTypeObjectEnd = 4,

JKTokenTypeArrayBegin = 5,

JKTokenTypeArrayEnd = 6,

JKTokenTypeSeparator = 7,

JKTokenTypeComma = 8,

JKTokenTypeTrue = 9,

JKTokenTypeFalse = 10,

JKTokenTypeNull = 11,

JKTokenTypeWhiteSpace = 12,

};

typedef NSUInteger JKTokenType;

enum {

JKValueTypeNone = 0,

JKValueTypeString = 5,

JKValueTypeLongLong = 7,

JKValueTypeUnsignedLongLong = 11,

JKValueTypeDouble = 13,

};

typedef NSUInteger JKValueType;

enum {

JKEncodeOptionAsData = 1,

JKEncodeOptionAsString = 2,

JKEncodeOptionAsTypeMask = 0x7,

JKEncodeOptionCollectionObj = (1 << 3),

JKEncodeOptionStringObj = (1 << 4),

JKEncodeOptionStringObjTrimQuotes = (1 << 5),

};

typedef NSUInteger JKEncodeOptionType;

typedef NSUInteger JKHash;

typedef struct JKTokenCacheItem JKTokenCacheItem;

typedef struct JKTokenCache JKTokenCache;

typedef struct JKTokenValue JKTokenValue;

typedef struct JKParseToken JKParseToken;

typedef struct JKPtrRange JKPtrRange;

typedef struct JKObjectStack JKObjectStack;

typedef struct JKBuffer JKBuffer;

typedef struct JKConstBuffer JKConstBuffer;

typedef struct JKConstPtrRange JKConstPtrRange;

typedef struct JKRange JKRange;

typedef struct JKManagedBuffer JKManagedBuffer;

typedef struct JKFastClassLookup JKFastClassLookup;

typedef struct JKEncodeCache JKEncodeCache;

typedef struct JKEncodeState JKEncodeState;

typedef struct JKObjCImpCache JKObjCImpCache;

typedef struct JKHashTableEntry JKHashTableEntry;

typedef id (*NSNumberAllocImp)(id receiver, SEL selector);

typedef id (*NSNumberInitWithUnsignedLongLongImp)(id receiver, SEL selector, unsigned long long value);

typedef id (*JKClassFormatterIMP)(id receiver, SEL selector, id object);

#ifdef __BLOCKS__

typedef id (^JKClassFormatterBlock)(id formatObject);

#endif

struct JKPtrRange {

unsigned char *ptr;

size_t length;

};

struct JKConstPtrRange {

const unsigned char *ptr;

size_t length;

};

struct JKRange {

size_t location, length;

};

struct JKManagedBuffer {

JKPtrRange bytes;

JKManagedBufferFlags flags;

size_t roundSizeUpToMultipleOf;

};

struct JKObjectStack {

void **objects, **keys;

CFHashCode *cfHashes;

size_t count, index, roundSizeUpToMultipleOf;

JKObjectStackFlags flags;

};

struct JKBuffer {

JKPtrRange bytes;

};

struct JKConstBuffer {

JKConstPtrRange bytes;

};

struct JKTokenValue {

JKConstPtrRange ptrRange;

JKValueType type;

JKHash hash;

union {

long long longLongValue;

unsigned long long unsignedLongLongValue;

double doubleValue;

} number;

JKTokenCacheItem *cacheItem;

};

struct JKParseToken {

JKConstPtrRange tokenPtrRange;

JKTokenType type;

JKTokenValue value;

JKManagedBuffer tokenBuffer;

};

struct JKTokenCacheItem {

void *object;

JKHash hash;

CFHashCode cfHash;

size_t size;

unsigned char *bytes;

JKValueType type;

};

struct JKTokenCache {

JKTokenCacheItem *items;

size_t count;

unsigned int prng_lfsr;

unsigned char age[JK_CACHE_SLOTS];

};

struct JKObjCImpCache {

Class NSNumberClass;

NSNumberAllocImp NSNumberAlloc;

NSNumberInitWithUnsignedLongLongImp NSNumberInitWithUnsignedLongLong;

};

struct JKParseState {

JKParseOptionFlags parseOptionFlags;

JKConstBuffer stringBuffer;

size_t atIndex, lineNumber, lineStartIndex;

size_t prev_atIndex, prev_lineNumber, prev_lineStartIndex;

JKParseToken token;

JKObjectStack objectStack;

JKTokenCache cache;

JKObjCImpCache objCImpCache;

NSError *error;

int errorIsPrev;

BOOL mutableCollections;

};

struct JKFastClassLookup {

void *stringClass;

void *numberClass;

void *arrayClass;

void *dictionaryClass;

void *nullClass;

};

struct JKEncodeCache {

id object;

size_t offset;

size_t length;

};

struct JKEncodeState {

JKManagedBuffer utf8ConversionBuffer;

JKManagedBuffer stringBuffer;

size_t atIndex;

JKFastClassLookup fastClassLookup;

JKEncodeCache cache[JK_ENCODE_CACHE_SLOTS];

JKSerializeOptionFlags serializeOptionFlags;

JKEncodeOptionType encodeOption;

size_t depth;

NSError *error;

id classFormatterDelegate;

SEL classFormatterSelector;

JKClassFormatterIMP classFormatterIMP;

#ifdef __BLOCKS__

JKClassFormatterBlock classFormatterBlock;

#endif

};

@interface JKSerializer : NSObject {

JKEncodeState *encodeState;

}

#ifdef __BLOCKS__

#define JKSERIALIZER_BLOCKS_PROTO id(^)(id object)

#else

#define JKSERIALIZER_BLOCKS_PROTO id

#endif

+ (id)serializeObject:(id)object options:(JKSerializeOptionFlags)optionFlags encodeOption:(JKEncodeOptionType)encodeOption block:(JKSERIALIZER_BLOCKS_PROTO)block delegate:(id)delegate selector:(SEL)selector error:(NSError **)error;

- (id)serializeObject:(id)object options:(JKSerializeOptionFlags)optionFlags encodeOption:(JKEncodeOptionType)encodeOption block:(JKSERIALIZER_BLOCKS_PROTO)block delegate:(id)delegate selector:(SEL)selector error:(NSError **)error;

- (void)releaseState;

struct JKHashTableEntry {

NSUInteger keyHash;

id key, object;

};

typedef uint32_t UTF32; /* at least 32 bits */

typedef uint16_t UTF16; /* at least 16 bits */

typedef uint8_t UTF8; /* typically 8 bits */

typedef enum {

conversionOK, /* conversion successful */

sourceExhausted, /* partial character in source, but hit end */

targetExhausted, /* insuff. room in target for conversion */

sourceIllegal /* source sequence is illegal/malformed */

} ConversionResult;

#define UNI_REPLACEMENT_CHAR (UTF32)0x0000FFFD

#define UNI_MAX_BMP (UTF32)0x0000FFFF

#define UNI_MAX_UTF16 (UTF32)0x0010FFFF

#define UNI_MAX_UTF32 (UTF32)0x7FFFFFFF

#define UNI_MAX_LEGAL_UTF32 (UTF32)0x0010FFFF

#define UNI_SUR_HIGH_START (UTF32)0xD800

#define UNI_SUR_HIGH_END (UTF32)0xDBFF

#define UNI_SUR_LOW_START (UTF32)0xDC00

#define UNI_SUR_LOW_END (UTF32)0xDFFF

#if !defined(JK_FAST_TRAILING_BYTES)

static const char trailingBytesForUTF8[256] = {

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,

2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, 3,3,3,3,3,3,3,3,4,4,4,4,5,5,5,5

};

#endif

static const UTF32 offsetsFromUTF8[6] = { 0x00000000UL, 0x00003080UL, 0x000E2080UL, 0x03C82080UL, 0xFA082080UL, 0x82082080UL };

static const UTF8 firstByteMark[7] = { 0x00, 0x00, 0xC0, 0xE0, 0xF0, 0xF8, 0xFC };

#define JK_AT_STRING_PTR(x) (&((x)->stringBuffer.bytes.ptr[(x)->atIndex]))

#define JK_END_STRING_PTR(x) (&((x)->stringBuffer.bytes.ptr[(x)->stringBuffer.bytes.length]))

static JKArray *_JKArrayCreate(id *objects, NSUInteger count, BOOL mutableCollection);

static void _JKArrayInsertObjectAtIndex(JKArray *array, id newObject, NSUInteger objectIndex);

static void _JKArrayReplaceObjectAtIndexWithObject(JKArray *array, NSUInteger objectIndex, id newObject);

static void _JKArrayRemoveObjectAtIndex(JKArray *array, NSUInteger objectIndex);

static NSUInteger _JKDictionaryCapacityForCount(NSUInteger count);

static JKDictionary *_JKDictionaryCreate(id *keys, NSUInteger *keyHashes, id *objects, NSUInteger count, BOOL mutableCollection);

static JKHashTableEntry *_JKDictionaryHashEntry(JKDictionary *dictionary);

static NSUInteger _JKDictionaryCapacity(JKDictionary *dictionary);

static void _JKDictionaryResizeIfNeccessary(JKDictionary *dictionary);

static void _JKDictionaryRemoveObjectWithEntry(JKDictionary *dictionary, JKHashTableEntry *entry);

static void _JKDictionaryAddObject(JKDictionary *dictionary, NSUInteger keyHash, id key, id object);

static JKHashTableEntry *_JKDictionaryHashTableEntryForKey(JKDictionary *dictionary, id aKey);

static void _JSONDecoderCleanup(JSONDecoder *decoder);

static id _NSStringObjectFromJSONString(NSString *jsonString, JKParseOptionFlags parseOptionFlags, NSError **error, BOOL mutableCollection);

static void jk_managedBuffer_release(JKManagedBuffer *managedBuffer);

static void jk_managedBuffer_setToStackBuffer(JKManagedBuffer *managedBuffer, unsigned char *ptr, size_t length);

static unsigned char *jk_managedBuffer_resize(JKManagedBuffer *managedBuffer, size_t newSize);

static void jk_objectStack_release(JKObjectStack *objectStack);

static void jk_objectStack_setToStackBuffer(JKObjectStack *objectStack, void **objects, void **keys, CFHashCode *cfHashes, size_t count);

static int jk_objectStack_resize(JKObjectStack *objectStack, size_t newCount);

static void jk_error(JKParseState *parseState, NSString *format, ...);

static int jk_parse_string(JKParseState *parseState);

static int jk_parse_number(JKParseState *parseState);

static size_t jk_parse_is_newline(JKParseState *parseState, const unsigned char *atCharacterPtr);

JK_STATIC_INLINE int jk_parse_skip_newline(JKParseState *parseState);

JK_STATIC_INLINE void jk_parse_skip_whitespace(JKParseState *parseState);

static int jk_parse_next_token(JKParseState *parseState);

static void jk_error_parse_accept_or3(JKParseState *parseState, int state, NSString *or1String, NSString *or2String, NSString *or3String);

static void *jk_create_dictionary(JKParseState *parseState, size_t startingObjectIndex);

static void *jk_parse_dictionary(JKParseState *parseState);

static void *jk_parse_array(JKParseState *parseState);

static void *jk_object_for_token(JKParseState *parseState);

static void *jk_cachedObjects(JKParseState *parseState);

JK_STATIC_INLINE void jk_cache_age(JKParseState *parseState);

JK_STATIC_INLINE void jk_set_parsed_token(JKParseState *parseState, const unsigned char *ptr, size_t length, JKTokenType type, size_t advanceBy);

static void jk_encode_error(JKEncodeState *encodeState, NSString *format, ...);

static int jk_encode_printf(JKEncodeState *encodeState, JKEncodeCache *cacheSlot, size_t startingAtIndex, id object, const char *format, ...);

static int jk_encode_write(JKEncodeState *encodeState, JKEncodeCache *cacheSlot, size_t startingAtIndex, id object, const char *format);

static int jk_encode_writePrettyPrintWhiteSpace(JKEncodeState *encodeState);

static int jk_encode_write1slow(JKEncodeState *encodeState, ssize_t depthChange, const char *format);

static int jk_encode_write1fast(JKEncodeState *encodeState, ssize_t depthChange JK_UNUSED_ARG, const char *format);

static int jk_encode_writen(JKEncodeState *encodeState, JKEncodeCache *cacheSlot, size_t startingAtIndex, id object, const char *format, size_t length);

JK_STATIC_INLINE JKHash jk_encode_object_hash(void *objectPtr);

JK_STATIC_INLINE void jk_encode_updateCache(JKEncodeState *encodeState, JKEncodeCache *cacheSlot, size_t startingAtIndex, id object);

static int jk_encode_add_atom_to_buffer(JKEncodeState *encodeState, void *objectPtr);

#define jk_encode_write1(es, dc, f) (JK_EXPECT_F(_jk_encode_prettyPrint) ? jk_encode_write1slow(es, dc, f) : jk_encode_write1fast(es, dc, f))

JK_STATIC_INLINE size_t jk_min(size_t a, size_t b);

JK_STATIC_INLINE size_t jk_max(size_t a, size_t b);

JK_STATIC_INLINE JKHash calculateHash(JKHash currentHash, unsigned char c);

#pragma mark -

@interface JKArray : NSMutableArray <NSCopying, NSMutableCopying, NSFastEnumeration> {

id *objects;

NSUInteger count, capacity, mutations;

}

@implementation JKArray

static Class _JKArrayClass = NULL;

static size_t _JKArrayInstanceSize = 0UL;

+ (void)load

{

NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init]; // Though technically not required, the run time environment at +load time may be less than ideal.

_JKArrayClass = objc_getClass("JKArray");

_JKArrayInstanceSize = jk_max(16UL, class_getInstanceSize(_JKArrayClass));

[pool release]; pool = NULL;

}

+ (id)allocWithZone:(NSZone *)zone

{

#pragma unused(zone)

[NSException raise:NSInvalidArgumentException format:@"*** - [%@ %@]: The %@ class is private to JSONKit and should not be used in this fashion.", NSStringFromClass([self class]), NSStringFromSelector(_cmd), NSStringFromClass([self class])];

return(NULL);

}

static JKArray *_JKArrayCreate(id *objects, NSUInteger count, BOOL mutableCollection) {

NSCParameterAssert((objects != NULL) && (_JKArrayClass != NULL) && (_JKArrayInstanceSize > 0UL));

JKArray *array = NULL;

if(JK_EXPECT_T((array = (JKArray *)calloc(1UL, _JKArrayInstanceSize)) != NULL)) { // Directly allocate the JKArray instance via calloc.

array->isa = _JKArrayClass;

if((array = [array init]) == NULL) { return(NULL); }

array->capacity = count;

array->count = count;

if(JK_EXPECT_F((array->objects = (id *)malloc(sizeof(id) * array->capacity)) == NULL)) { [array autorelease]; return(NULL); }

memcpy(array->objects, objects, array->capacity * sizeof(id));

array->mutations = (mutableCollection == NO) ? 0UL : 1UL;

}

return(array);

}

static void _JKArrayInsertObjectAtIndex(JKArray *array, id newObject, NSUInteger objectIndex) {

NSCParameterAssert((array != NULL) && (array->objects != NULL) && (array->count <= array->capacity) && (objectIndex <= array->count) && (newObject != NULL));

if(!((array != NULL) && (array->objects != NULL) && (objectIndex <= array->count) && (newObject != NULL))) { [newObject autorelease]; return; }

array->count++;

if(array->count >= array->capacity) {

array->capacity += 16UL;

id *newObjects = NULL;

if((newObjects = (id *)realloc(array->objects, sizeof(id) * array->capacity)) == NULL) { [NSException raise:NSMallocException format:@"Unable to resize objects array."]; }

array->objects = newObjects;

memset(&array->objects[array->count], 0, sizeof(id) * (array->capacity - array->count));

}

if((objectIndex + 1UL) < array->count) { memmove(&array->objects[objectIndex + 1UL], &array->objects[objectIndex], sizeof(id) * ((array->count - 1UL) - objectIndex)); array->objects[objectIndex] = NULL; }

array->objects[objectIndex] = newObject;

}

static void _JKArrayReplaceObjectAtIndexWithObject(JKArray *array, NSUInteger objectIndex, id newObject) {

NSCParameterAssert((array != NULL) && (array->objects != NULL) && (array->count <= array->capacity) && (objectIndex < array->count) && (array->objects[objectIndex] != NULL) && (newObject != NULL));

if(!((array != NULL) && (array->objects != NULL) && (objectIndex < array->count) && (array->objects[objectIndex] != NULL) && (newObject != NULL))) { [newObject autorelease]; return; }

CFRelease(array->objects[objectIndex]);

array->objects[objectIndex] = NULL;

array->objects[objectIndex] = newObject;

}

static void _JKArrayRemoveObjectAtIndex(JKArray *array, NSUInteger objectIndex) {

NSCParameterAssert((array != NULL) && (array->objects != NULL) && (array->count <= array->capacity) && (objectIndex < array->count) && (array->objects[objectIndex] != NULL));

if(!((array != NULL) && (array->objects != NULL) && (objectIndex < array->count) && (array->objects[objectIndex] != NULL))) { return; }

CFRelease(array->objects[objectIndex]);

array->objects[objectIndex] = NULL;

if((objectIndex + 1UL) < array->count) { memmove(&array->objects[objectIndex], &array->objects[objectIndex + 1UL], sizeof(id) * ((array->count - 1UL) - objectIndex)); array->objects[array->count] = NULL; }

array->count--;

}

- (void)dealloc

{

if(JK_EXPECT_T(objects != NULL)) {

NSUInteger atObject = 0UL;

for(atObject = 0UL; atObject < count; atObject++) { if(JK_EXPECT_T(objects[atObject] != NULL)) { CFRelease(objects[atObject]); objects[atObject] = NULL; } }

free(objects); objects = NULL;

}

[super dealloc];

}

- (NSUInteger)count

{

NSParameterAssert((objects != NULL) && (count <= capacity));

return(count);

}

- (void)getObjects:(id *)objectsPtr range:(NSRange)range

{

NSParameterAssert((objects != NULL) && (count <= capacity));

if((objectsPtr == NULL) && (NSMaxRange(range) > 0UL)) { [NSException raise:NSRangeException format:@"*** -[%@ %@]: pointer to objects array is NULL but range length is %lu", NSStringFromClass([self class]), NSStringFromSelector(_cmd), NSMaxRange(range)]; }

if((range.location > count) || (NSMaxRange(range) > count)) { [NSException raise:NSRangeException format:@"*** -[%@ %@]: index (%lu) beyond bounds (%lu)", NSStringFromClass([self class]), NSStringFromSelector(_cmd), NSMaxRange(range), count]; }

memcpy(objectsPtr, objects + range.location, range.length * sizeof(id));

}

- (id)objectAtIndex:(NSUInteger)objectIndex

{

if(objectIndex >= count) { [NSException raise:NSRangeException format:@"*** -[%@ %@]: index (%lu) beyond bounds (%lu)", NSStringFromClass([self class]), NSStringFromSelector(_cmd), objectIndex, count]; }

NSParameterAssert((objects != NULL) && (count <= capacity) && (objects[objectIndex] != NULL));

return(objects[objectIndex]);

}

- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id *)stackbuf count:(NSUInteger)len

{

NSParameterAssert((state != NULL) && (stackbuf != NULL) && (len > 0UL) && (objects != NULL) && (count <= capacity));

if(JK_EXPECT_F(state->state == 0UL)) { state->mutationsPtr = (unsigned long *)&mutations; state->itemsPtr = stackbuf; }

if(JK_EXPECT_F(state->state >= count)) { return(0UL); }

NSUInteger enumeratedCount = 0UL;

while(JK_EXPECT_T(enumeratedCount < len) && JK_EXPECT_T(state->state < count)) { NSParameterAssert(objects[state->state] != NULL); stackbuf[enumeratedCount++] = objects[state->state++]; }

return(enumeratedCount);

}

- (void)insertObject:(id)anObject atIndex:(NSUInteger)objectIndex

{

if(mutations == 0UL) { [NSException raise:NSInternalInconsistencyException format:@"*** -[%@ %@]: mutating method sent to immutable object", NSStringFromClass([self class]), NSStringFromSelector(_cmd)]; }

if(anObject == NULL) { [NSException raise:NSInvalidArgumentException format:@"*** -[%@ %@]: attempt to insert nil", NSStringFromClass([self class]), NSStringFromSelector(_cmd)]; }

if(objectIndex > count) { [NSException raise:NSRangeException format:@"*** -[%@ %@]: index (%lu) beyond bounds (%lu)", NSStringFromClass([self class]), NSStringFromSelector(_cmd), objectIndex, count + 1UL]; }

anObject = [anObject retain];

_JKArrayInsertObjectAtIndex(self, anObject, objectIndex);

mutations = (mutations == NSUIntegerMax) ? 1UL : mutations + 1UL;

}

- (void)removeObjectAtIndex:(NSUInteger)objectIndex

{

if(mutations == 0UL) { [NSException raise:NSInternalInconsistencyException format:@"*** -[%@ %@]: mutating method sent to immutable object", NSStringFromClass([self class]), NSStringFromSelector(_cmd)]; }

if(objectIndex >= count) { [NSException raise:NSRangeException format:@"*** -[%@ %@]: index (%lu) beyond bounds (%lu)", NSStringFromClass([self class]), NSStringFromSelector(_cmd), objectIndex, count]; }

_JKArrayRemoveObjectAtIndex(self, objectIndex);

mutations = (mutations == NSUIntegerMax) ? 1UL : mutations + 1UL;

}

- (void)replaceObjectAtIndex:(NSUInteger)objectIndex withObject:(id)anObject

{

if(mutations == 0UL) { [NSException raise:NSInternalInconsistencyException format:@"*** -[%@ %@]: mutating method sent to immutable object", NSStringFromClass([self class]), NSStringFromSelector(_cmd)]; }

if(anObject == NULL) { [NSException raise:NSInvalidArgumentException format:@"*** -[%@ %@]: attempt to insert nil", NSStringFromClass([self class]), NSStringFromSelector(_cmd)]; }

if(objectIndex >= count) { [NSException raise:NSRangeException format:@"*** -[%@ %@]: index (%lu) beyond bounds (%lu)", NSStringFromClass([self class]), NSStringFromSelector(_cmd), objectIndex, count]; }

anObject = [anObject retain];

_JKArrayReplaceObjectAtIndexWithObject(self, objectIndex, anObject);

mutations = (mutations == NSUIntegerMax) ? 1UL : mutations + 1UL;

}

- (id)copyWithZone:(NSZone *)zone

{

NSParameterAssert((objects != NULL) && (count <= capacity));

return((mutations == 0UL) ? [self retain] : [[NSArray allocWithZone:zone] initWithObjects:objects count:count]);

}

- (id)mutableCopyWithZone:(NSZone *)zone

{

NSParameterAssert((objects != NULL) && (count <= capacity));

return([[NSMutableArray allocWithZone:zone] initWithObjects:objects count:count]);

}

#pragma mark -

@interface JKDictionaryEnumerator : NSEnumerator {

id collection;

NSUInteger nextObject;

}

- (id)initWithJKDictionary:(JKDictionary *)initDictionary;

- (NSArray *)allObjects;

- (id)nextObject;

@implementation JKDictionaryEnumerator

- (id)initWithJKDictionary:(JKDictionary *)initDictionary

{

NSParameterAssert(initDictionary != NULL);

if((self = [super init]) == NULL) { return(NULL); }

if((collection = (id)CFRetain(initDictionary)) == NULL) { [self autorelease]; return(NULL); }

return(self);

}

- (void)dealloc

{

if(collection != NULL) { CFRelease(collection); collection = NULL; }

[super dealloc];

}

- (NSArray *)allObjects

{

NSParameterAssert(collection != NULL);

NSUInteger count = [collection count], atObject = 0UL;

id objects[count];

while((objects[atObject] = [self nextObject]) != NULL) { NSParameterAssert(atObject < count); atObject++; }

return([NSArray arrayWithObjects:objects count:atObject]);

}

- (id)nextObject

{

NSParameterAssert((collection != NULL) && (_JKDictionaryHashEntry(collection) != NULL));

JKHashTableEntry *entry = _JKDictionaryHashEntry(collection);

NSUInteger capacity = _JKDictionaryCapacity(collection);

id returnObject = NULL;

if(entry != NULL) { while((nextObject < capacity) && ((returnObject = entry[nextObject++].key) == NULL)) { /* ... */ } }

return(returnObject);

}

#pragma mark -

@interface JKDictionary : NSMutableDictionary <NSCopying, NSMutableCopying, NSFastEnumeration> {

NSUInteger count, capacity, mutations;

JKHashTableEntry *entry;

}

@implementation JKDictionary

static Class _JKDictionaryClass = NULL;

static size_t _JKDictionaryInstanceSize = 0UL;

+ (void)load

{

NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init]; // Though technically not required, the run time environment at +load time may be less than ideal.

_JKDictionaryClass = objc_getClass("JKDictionary");

_JKDictionaryInstanceSize = jk_max(16UL, class_getInstanceSize(_JKDictionaryClass));

[pool release]; pool = NULL;

}

+ (id)allocWithZone:(NSZone *)zone

{

#pragma unused(zone)

[NSException raise:NSInvalidArgumentException format:@"*** - [%@ %@]: The %@ class is private to JSONKit and should not be used in this fashion.", NSStringFromClass([self class]), NSStringFromSelector(_cmd), NSStringFromClass([self class])];

return(NULL);

}

static const NSUInteger jk_dictionaryCapacities[] = {

0UL, 3UL, 7UL, 13UL, 23UL, 41UL, 71UL, 127UL, 191UL, 251UL, 383UL, 631UL, 1087UL, 1723UL,

2803UL, 4523UL, 7351UL, 11959UL, 19447UL, 31231UL, 50683UL, 81919UL, 132607UL,

214519UL, 346607UL, 561109UL, 907759UL, 1468927UL, 2376191UL, 3845119UL,

6221311UL, 10066421UL, 16287743UL, 26354171UL, 42641881UL, 68996069UL,

111638519UL, 180634607UL, 292272623UL, 472907251UL

};

static NSUInteger _JKDictionaryCapacityForCount(NSUInteger count) {

NSUInteger bottom = 0UL, top = sizeof(jk_dictionaryCapacities) / sizeof(NSUInteger), mid = 0UL, tableSize = lround(floor((count) * 1.33));

while(top > bottom) { mid = (top + bottom) / 2UL; if(jk_dictionaryCapacities[mid] < tableSize) { bottom = mid + 1UL; } else { top = mid; } }

return(jk_dictionaryCapacities[bottom]);

}

static void _JKDictionaryResizeIfNeccessary(JKDictionary *dictionary) {

NSCParameterAssert((dictionary != NULL) && (dictionary->entry != NULL) && (dictionary->count <= dictionary->capacity));

NSUInteger capacityForCount = 0UL;

if(dictionary->capacity < (capacityForCount = _JKDictionaryCapacityForCount(dictionary->count + 1UL))) { // resize

NSUInteger oldCapacity = dictionary->capacity;

#ifndef NS_BLOCK_ASSERTIONS

NSUInteger oldCount = dictionary->count;

#endif

JKHashTableEntry *oldEntry = dictionary->entry;

if(JK_EXPECT_F((dictionary->entry = (JKHashTableEntry *)calloc(1UL, sizeof(JKHashTableEntry) * capacityForCount)) == NULL)) { [NSException raise:NSMallocException format:@"Unable to allocate memory for hash table."]; }

dictionary->capacity = capacityForCount;

dictionary->count = 0UL;

NSUInteger idx = 0UL;

for(idx = 0UL; idx < oldCapacity; idx++) { if(oldEntry[idx].key != NULL) { _JKDictionaryAddObject(dictionary, oldEntry[idx].keyHash, oldEntry[idx].key, oldEntry[idx].object); oldEntry[idx].keyHash = 0UL; oldEntry[idx].key = NULL; oldEntry[idx].object = NULL; } }

NSCParameterAssert((oldCount == dictionary->count));

free(oldEntry); oldEntry = NULL;

}

}

static JKDictionary *_JKDictionaryCreate(id *keys, NSUInteger *keyHashes, id *objects, NSUInteger count, BOOL mutableCollection) {

NSCParameterAssert((keys != NULL) && (keyHashes != NULL) && (objects != NULL) && (_JKDictionaryClass != NULL) && (_JKDictionaryInstanceSize > 0UL));

JKDictionary *dictionary = NULL;

if(JK_EXPECT_T((dictionary = (JKDictionary *)calloc(1UL, _JKDictionaryInstanceSize)) != NULL)) { // Directly allocate the JKDictionary instance via calloc.

dictionary->isa = _JKDictionaryClass;

if((dictionary = [dictionary init]) == NULL) { return(NULL); }

dictionary->capacity = _JKDictionaryCapacityForCount(count);

dictionary->count = 0UL;

if(JK_EXPECT_F((dictionary->entry = (JKHashTableEntry *)calloc(1UL, sizeof(JKHashTableEntry) * dictionary->capacity)) == NULL)) { [dictionary autorelease]; return(NULL); }

NSUInteger idx = 0UL;

for(idx = 0UL; idx < count; idx++) { _JKDictionaryAddObject(dictionary, keyHashes[idx], keys[idx], objects[idx]); }

dictionary->mutations = (mutableCollection == NO) ? 0UL : 1UL;

}

return(dictionary);

}

- (void)dealloc

{

if(JK_EXPECT_T(entry != NULL)) {

NSUInteger atEntry = 0UL;

for(atEntry = 0UL; atEntry < capacity; atEntry++) {

if(JK_EXPECT_T(entry[atEntry].key != NULL)) { CFRelease(entry[atEntry].key); entry[atEntry].key = NULL; }

if(JK_EXPECT_T(entry[atEntry].object != NULL)) { CFRelease(entry[atEntry].object); entry[atEntry].object = NULL; }

}

free(entry); entry = NULL;

}

[super dealloc];

}

static JKHashTableEntry *_JKDictionaryHashEntry(JKDictionary *dictionary) {

NSCParameterAssert(dictionary != NULL);

return(dictionary->entry);

}

static NSUInteger _JKDictionaryCapacity(JKDictionary *dictionary) {

NSCParameterAssert(dictionary != NULL);

return(dictionary->capacity);

}

static void _JKDictionaryRemoveObjectWithEntry(JKDictionary *dictionary, JKHashTableEntry *entry) {

NSCParameterAssert((dictionary != NULL) && (entry != NULL) && (entry->key != NULL) && (entry->object != NULL) && (dictionary->count > 0UL));

CFRelease(entry->key); entry->key = NULL;

CFRelease(entry->object); entry->object = NULL;

entry->keyHash = 0UL;

dictionary->count--;

}

static void _JKDictionaryAddObject(JKDictionary *dictionary, NSUInteger keyHash, id key, id object) {

NSCParameterAssert((dictionary != NULL) && (key != NULL) && (object != NULL) && (dictionary->count < dictionary->capacity) && (dictionary->entry != NULL));

NSUInteger keyEntry = keyHash % dictionary->capacity, idx = 0UL;

for(idx = 0UL; idx < dictionary->capacity; idx++) {

NSUInteger entryIdx = (keyEntry + idx) % dictionary->capacity;

JKHashTableEntry *atEntry = &dictionary->entry[entryIdx];

if(JK_EXPECT_F(atEntry->keyHash == keyHash) && JK_EXPECT_T(atEntry->key != NULL) && (JK_EXPECT_F(key == atEntry->key) || JK_EXPECT_F(CFEqual(atEntry->key, key)))) { _JKDictionaryRemoveObjectWithEntry(dictionary, atEntry); }

if(JK_EXPECT_T(atEntry->key == NULL)) { atEntry->key = key; atEntry->object = object; atEntry->keyHash = keyHash; dictionary->count++; return; }

}

// We should never get here. If we do, we -release the key / object because it's our responsibility.

CFRelease(key);

CFRelease(object);

}

- (NSUInteger)count

{

return(count);

}

static JKHashTableEntry *_JKDictionaryHashTableEntryForKey(JKDictionary *dictionary, id aKey) {

NSCParameterAssert((dictionary != NULL) && (dictionary->entry != NULL) && (dictionary->count <= dictionary->capacity));

if((aKey == NULL) || (dictionary->capacity == 0UL)) { return(NULL); }

NSUInteger keyHash = CFHash(aKey), keyEntry = (keyHash % dictionary->capacity), idx = 0UL;

JKHashTableEntry *atEntry = NULL;

for(idx = 0UL; idx < dictionary->capacity; idx++) {

atEntry = &dictionary->entry[(keyEntry + idx) % dictionary->capacity];

if(JK_EXPECT_T(atEntry->keyHash == keyHash) && JK_EXPECT_T(atEntry->key != NULL) && ((atEntry->key == aKey) || CFEqual(atEntry->key, aKey))) { NSCParameterAssert(atEntry->object != NULL); return(atEntry); break; }

if(JK_EXPECT_F(atEntry->key == NULL)) { NSCParameterAssert(atEntry->object == NULL); return(NULL); break; } // If the key was in the table, we would have found it by now.

}

return(NULL);

}

- (id)objectForKey:(id)aKey

{

NSParameterAssert((entry != NULL) && (count <= capacity));

JKHashTableEntry *entryForKey = _JKDictionaryHashTableEntryForKey(self, aKey);

return((entryForKey != NULL) ? entryForKey->object : NULL);

}

- (void)getObjects:(id *)objects andKeys:(id *)keys

{

NSParameterAssert((entry != NULL) && (count <= capacity));

NSUInteger atEntry = 0UL; NSUInteger arrayIdx = 0UL;

for(atEntry = 0UL; atEntry < capacity; atEntry++) {

if(JK_EXPECT_T(entry[atEntry].key != NULL)) {

NSCParameterAssert((entry[atEntry].object != NULL) && (arrayIdx < count));

if(JK_EXPECT_T(keys != NULL)) { keys[arrayIdx] = entry[atEntry].key; }

if(JK_EXPECT_T(objects != NULL)) { objects[arrayIdx] = entry[atEntry].object; }

arrayIdx++;

}

}

}