src/vppinfra/cJSON.c

   1 /*
   2   Copyright (c) 2009-2017 Dave Gamble and cJSON contributors
   3
   4   Permission is hereby granted, free of charge, to any person obtaining a copy
   5   of this software and associated documentation files (the "Software"), to deal
   6   in the Software without restriction, including without limitation the rights
   7   to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   8   copies of the Software, and to permit persons to whom the Software is
   9   furnished to do so, subject to the following conditions:
  10
  11   The above copyright notice and this permission notice shall be included in
  12   all copies or substantial portions of the Software.
  13
  14   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15   IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16   FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17   AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18   LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19   OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  20   THE SOFTWARE.
  21 */
  22 /* clang-format off */
  23 /* cJSON */
  24 /* JSON parser in C. */
  25
  26 /* disable warnings about old C89 functions in MSVC */
  27 #if !defined(_CRT_SECURE_NO_DEPRECATE) && defined(_MSC_VER)
  28 #define _CRT_SECURE_NO_DEPRECATE
  29 #endif
  30
  31 #ifdef __GNUC__
  32 #pragma GCC visibility push(default)
  33 #endif
  34 #if defined(_MSC_VER)
  35 #pragma warning (push)
  36 /* disable warning about single line comments in system headers */
  37 #pragma warning (disable : 4001)
  38 #endif
  39
  40 #include <string.h>
  41 #include <stdio.h>
  42 #include <math.h>
  43 #include <stdlib.h>
  44 #include <limits.h>
  45 #include <ctype.h>
  46 #include <float.h>
  47
  48 #ifdef ENABLE_LOCALES
  49 #include <locale.h>
  50 #endif
  51
  52 #if defined(_MSC_VER)
  53 #pragma warning (pop)
  54 #endif
  55 #ifdef __GNUC__
  56 #pragma GCC visibility pop
  57 #endif
  58
  59 #include "cJSON.h"
  60
  61 /* define our own boolean type */
  62 #ifdef true
  63 #undef true
  64 #endif
  65 #define true ((cJSON_bool)1)
  66
  67 #ifdef false
  68 #undef false
  69 #endif
  70 #define false ((cJSON_bool)0)
  71
  72 /* define isnan and isinf for ANSI C, if in C99 or above, isnan and isinf has been defined in math.h */
  73 #ifndef isinf
  74 #define isinf(d) (isnan((d - d)) && !isnan(d))
  75 #endif
  76 #ifndef isnan
  77 #define isnan(d) (d != d)
  78 #endif
  79
  80 #ifndef NAN
  81 #ifdef _WIN32
  82 #define NAN sqrt (-1.0)
  83 #else
  84 #define NAN 0.0/0.0
  85 #endif
  86 #endif
  87
  88 typedef struct {
  89     const unsigned char *json;
  90     size_t position;
  91 } error;
  92 static error global_error = { NULL, 0 };
  93
  94 CJSON_PUBLIC(const char *) cJSON_GetErrorPtr(void)
  95 {
  96     return (const char*) (global_error.json + global_error.position);
  97 }
  98
  99 CJSON_PUBLIC(char *) cJSON_GetStringValue(const cJSON * const item)
 100 {
 101     if (!cJSON_IsString(item))
 102     {
 103         return NULL;
 104     }
 105
 106     return item->valuestring;
 107 }
 108
 109 CJSON_PUBLIC(double) cJSON_GetNumberValue(const cJSON * const item)
 110 {
 111     if (!cJSON_IsNumber(item))
 112     {
 113         return (double) NAN;
 114     }
 115
 116     return item->valuedouble;
 117 }
 118
 119 /* This is a safeguard to prevent copy-pasters from using incompatible C and header files */
 120 #if (CJSON_VERSION_MAJOR != 1) || (CJSON_VERSION_MINOR != 7) || (CJSON_VERSION_PATCH != 14)
 121     #error cJSON.h and cJSON.c have different versions. Make sure that both have the same.
 122 #endif
 123
 124 CJSON_PUBLIC(const char*) cJSON_Version(void)
 125 {
 126     static char version[15];
 127     sprintf(version, "%i.%i.%i", CJSON_VERSION_MAJOR, CJSON_VERSION_MINOR, CJSON_VERSION_PATCH);
 128
 129     return version;
 130 }
 131
 132 /* Case insensitive string comparison, doesn't consider two NULL pointers equal though */
 133 static int case_insensitive_strcmp(const unsigned char *string1, const unsigned char *string2)
 134 {
 135     if ((string1 == NULL) || (string2 == NULL))
 136     {
 137         return 1;
 138     }
 139
 140     if (string1 == string2)
 141     {
 142         return 0;
 143     }
 144
 145     for(; tolower(*string1) == tolower(*string2); (void)string1++, string2++)
 146     {
 147         if (*string1 == '\0')
 148         {
 149             return 0;
 150         }
 151     }
 152
 153     return tolower(*string1) - tolower(*string2);
 154 }
 155
 156 typedef struct internal_hooks
 157 {
 158     void *(CJSON_CDECL *allocate)(size_t size);
 159     void (CJSON_CDECL *deallocate)(void *pointer);
 160     void *(CJSON_CDECL *reallocate)(void *pointer, size_t new_size, size_t old_size);
 161 } internal_hooks;
 162
 163 #if defined(_MSC_VER)
 164 /* work around MSVC error C2322: '...' address of dllimport '...' is not static */
 165 static void * CJSON_CDECL internal_malloc(size_t size)
 166 {
 167     return malloc(size);
 168 }
 169 static void CJSON_CDECL internal_free(void *pointer)
 170 {
 171     free(pointer);
 172 }
 173 #else
 174 #define internal_malloc malloc
 175 #define internal_free free
 176 #endif
 177
 178 static void * CJSON_CDECL internal_realloc(void *pointer, size_t new_size,
 179     size_t old_size)
 180 {
 181     return realloc(pointer, new_size);
 182 }
 183
 184 static void *
 185 cjson_realloc_internal (void *ptr, size_t new_size, size_t old_size);
 186
 187 /* strlen of character literals resolved at compile time */
 188 #define static_strlen(string_literal) (sizeof(string_literal) - sizeof(""))
 189
 190 static internal_hooks global_hooks = { internal_malloc, internal_free, internal_realloc };
 191
 192 static unsigned char* cJSON_strdup(const unsigned char* string, const internal_hooks * const hooks)
 193 {
 194     size_t length = 0;
 195     unsigned char *copy = NULL;
 196
 197     if (string == NULL)
 198     {
 199         return NULL;
 200     }
 201
 202     length = strlen((const char*)string) + sizeof("");
 203     copy = (unsigned char*)hooks->allocate(length);
 204     if (copy == NULL)
 205     {
 206         return NULL;
 207     }
 208     memcpy(copy, string, length);
 209
 210     return copy;
 211 }
 212
 213 CJSON_PUBLIC(void) cJSON_InitHooks(cJSON_Hooks* hooks)
 214 {
 215     if (hooks == NULL)
 216     {
 217         /* Reset hooks */
 218         global_hooks.allocate = malloc;
 219         global_hooks.deallocate = free;
 220         global_hooks.reallocate = internal_realloc;
 221         return;
 222     }
 223
 224     global_hooks.allocate = malloc;
 225     if (hooks->malloc_fn != NULL)
 226     {
 227         global_hooks.allocate = hooks->malloc_fn;
 228     }
 229
 230     global_hooks.deallocate = free;
 231     if (hooks->free_fn != NULL)
 232     {
 233         global_hooks.deallocate = hooks->free_fn;
 234     }
 235
 236     /* use realloc only if both free and malloc are used */
 237     global_hooks.reallocate = NULL;
 238     if ((global_hooks.allocate == malloc) && (global_hooks.deallocate == free))
 239     {
 240         global_hooks.reallocate = internal_realloc;
 241     }
 242     else
 243     {
 244         global_hooks.reallocate = cjson_realloc_internal;
 245     }
 246 }
 247
 248 /* Internal constructor. */
 249 static cJSON *cJSON_New_Item(const internal_hooks * const hooks)
 250 {
 251     cJSON* node = (cJSON*)hooks->allocate(sizeof(cJSON));
 252     if (node)
 253     {
 254         memset(node, '\0', sizeof(cJSON));
 255     }
 256
 257     return node;
 258 }
 259
 260 /* Delete a cJSON structure. */
 261 CJSON_PUBLIC(void) cJSON_Delete(cJSON *item)
 262 {
 263     cJSON *next = NULL;
 264     while (item != NULL)
 265     {
 266         next = item->next;
 267         if (!(item->type & cJSON_IsReference) && (item->child != NULL))
 268         {
 269             cJSON_Delete(item->child);
 270         }
 271         if (!(item->type & cJSON_IsReference) && (item->valuestring != NULL))
 272         {
 273             global_hooks.deallocate(item->valuestring);
 274         }
 275         if (!(item->type & cJSON_StringIsConst) && (item->string != NULL))
 276         {
 277             global_hooks.deallocate(item->string);
 278         }
 279         global_hooks.deallocate(item);
 280         item = next;
 281     }
 282 }
 283
 284 /* get the decimal point character of the current locale */
 285 static unsigned char get_decimal_point(void)
 286 {
 287 #ifdef ENABLE_LOCALES
 288     struct lconv *lconv = localeconv();
 289     return (unsigned char) lconv->decimal_point[0];
 290 #else
 291     return '.';
 292 #endif
 293 }
 294
 295 typedef struct
 296 {
 297     const unsigned char *content;
 298     size_t length;
 299     size_t offset;
 300     size_t depth; /* How deeply nested (in arrays/objects) is the input at the current offset. */
 301     internal_hooks hooks;
 302 } parse_buffer;
 303
 304 /* check if the given size is left to read in a given parse buffer (starting with 1) */
 305 #define can_read(buffer, size) ((buffer != NULL) && (((buffer)->offset + size) <= (buffer)->length))
 306 /* check if the buffer can be accessed at the given index (starting with 0) */
 307 #define can_access_at_index(buffer, index) ((buffer != NULL) && (((buffer)->offset + index) < (buffer)->length))
 308 #define cannot_access_at_index(buffer, index) (!can_access_at_index(buffer, index))
 309 /* get a pointer to the buffer at the position */
 310 #define buffer_at_offset(buffer) ((buffer)->content + (buffer)->offset)
 311
 312 /* Parse the input text to generate a number, and populate the result into item. */
 313 static cJSON_bool parse_number(cJSON * const item, parse_buffer * const input_buffer)
 314 {
 315     double number = 0;
 316     unsigned char *after_end = NULL;
 317     unsigned char number_c_string[64];
 318     unsigned char decimal_point = get_decimal_point();
 319     size_t i = 0;
 320
 321     if ((input_buffer == NULL) || (input_buffer->content == NULL))
 322     {
 323         return false;
 324     }
 325
 326     /* copy the number into a temporary buffer and replace '.' with the decimal point
 327      * of the current locale (for strtod)
 328      * This also takes care of '\0' not necessarily being available for marking the end of the input */
 329     for (i = 0; (i < (sizeof(number_c_string) - 1)) && can_access_at_index(input_buffer, i); i++)
 330     {
 331         switch (buffer_at_offset(input_buffer)[i])
 332         {
 333             case '0':
 334             case '1':
 335             case '2':
 336             case '3':
 337             case '4':
 338             case '5':
 339             case '6':
 340             case '7':
 341             case '8':
 342             case '9':
 343             case '+':
 344             case '-':
 345             case 'e':
 346             case 'E':
 347                 number_c_string[i] = buffer_at_offset(input_buffer)[i];
 348                 break;
 349
 350             case '.':
 351                 number_c_string[i] = decimal_point;
 352                 break;
 353
 354             default:
 355                 goto loop_end;
 356         }
 357     }
 358 loop_end:
 359     number_c_string[i] = '\0';
 360
 361     number = strtod((const char*)number_c_string, (char**)&after_end);
 362     if (number_c_string == after_end)
 363     {
 364         return false; /* parse_error */
 365     }
 366
 367     item->valuedouble = number;
 368
 369     /* use saturation in case of overflow */
 370     if (number >= INT_MAX)
 371     {
 372         item->valueint = INT_MAX;
 373     }
 374     else if (number <= (double)INT_MIN)
 375     {
 376         item->valueint = INT_MIN;
 377     }
 378     else
 379     {
 380         item->valueint = (int)number;
 381     }
 382
 383     item->type = cJSON_Number;
 384
 385     input_buffer->offset += (size_t)(after_end - number_c_string);
 386     return true;
 387 }
 388
 389 /* don't ask me, but the original cJSON_SetNumberValue returns an integer or double */
 390 CJSON_PUBLIC(double) cJSON_SetNumberHelper(cJSON *object, double number)
 391 {
 392     if (number >= INT_MAX)
 393     {
 394         object->valueint = INT_MAX;
 395     }
 396     else if (number <= (double)INT_MIN)
 397     {
 398         object->valueint = INT_MIN;
 399     }
 400     else
 401     {
 402         object->valueint = (int)number;
 403     }
 404
 405     return object->valuedouble = number;
 406 }
 407
 408 CJSON_PUBLIC(char*) cJSON_SetValuestring(cJSON *object, const char *valuestring)
 409 {
 410     char *copy = NULL;
 411     /* if object's type is not cJSON_String or is cJSON_IsReference, it should not set valuestring */
 412     if (!(object->type & cJSON_String) || (object->type & cJSON_IsReference))
 413     {
 414         return NULL;
 415     }
 416     if (strlen(valuestring) <= strlen(object->valuestring))
 417     {
 418         strcpy(object->valuestring, valuestring);
 419         return object->valuestring;
 420     }
 421     copy = (char*) cJSON_strdup((const unsigned char*)valuestring, &global_hooks);
 422     if (copy == NULL)
 423     {
 424         return NULL;
 425     }
 426     if (object->valuestring != NULL)
 427     {
 428         cJSON_free(object->valuestring);
 429     }
 430     object->valuestring = copy;
 431
 432     return copy;
 433 }
 434
 435 typedef struct
 436 {
 437     unsigned char *buffer;
 438     size_t length;
 439     size_t offset;
 440     size_t depth; /* current nesting depth (for formatted printing) */
 441     cJSON_bool noalloc;
 442     cJSON_bool format; /* is this print a formatted print */
 443     internal_hooks hooks;
 444 } printbuffer;
 445
 446 static void *
 447 cjson_realloc_internal (void *ptr, size_t new_size, size_t old_size)
 448 {
 449     size_t copy_size;
 450     if (old_size < new_size)
 451       copy_size = old_size;
 452     else
 453       copy_size = new_size;
 454
 455     unsigned char *newbuffer = global_hooks.allocate(new_size);
 456     if (!newbuffer)
 457     {
 458         global_hooks.deallocate(ptr);
 459         return NULL;
 460     }
 461
 462     memcpy (newbuffer, ptr, copy_size);
 463     global_hooks.deallocate (ptr);
 464     return newbuffer;
 465 }
 466
 467 /* realloc printbuffer if necessary to have at least "needed" bytes more */
 468 static unsigned char* ensure(printbuffer * const p, size_t needed)
 469 {
 470     unsigned char *newbuffer = NULL;
 471     size_t newsize = 0;
 472
 473     if ((p == NULL) || (p->buffer == NULL))
 474     {
 475         return NULL;
 476     }
 477
 478     if ((p->length > 0) && (p->offset >= p->length))
 479     {
 480         /* make sure that offset is valid */
 481         return NULL;
 482     }
 483
 484     if (needed > INT_MAX)
 485     {
 486         /* sizes bigger than INT_MAX are currently not supported */
 487         return NULL;
 488     }
 489
 490     needed += p->offset + 1;
 491     if (needed <= p->length)
 492     {
 493         return p->buffer + p->offset;
 494     }
 495
 496     if (p->noalloc) {
 497         return NULL;
 498     }
 499
 500     /* calculate new buffer size */
 501     if (needed > (INT_MAX / 2))
 502     {
 503         /* overflow of int, use INT_MAX if possible */
 504         if (needed <= INT_MAX)
 505         {
 506             newsize = INT_MAX;
 507         }
 508         else
 509         {
 510             return NULL;
 511         }
 512     }
 513     else
 514     {
 515         newsize = needed * 2;
 516     }
 517
 518     newbuffer = p->hooks.reallocate (p->buffer, newsize, p->length);
 519     if (newbuffer == NULL)
 520     {
 521         p->hooks.deallocate(p->buffer);
 522         p->length = 0;
 523         p->buffer = NULL;
 524         return NULL;
 525     }
 526     p->length = newsize;
 527     p->buffer = newbuffer;
 528
 529     return newbuffer + p->offset;
 530 }
 531
 532 /* calculate the new length of the string in a printbuffer and update the offset */
 533 static void update_offset(printbuffer * const buffer)
 534 {
 535     const unsigned char *buffer_pointer = NULL;
 536     if ((buffer == NULL) || (buffer->buffer == NULL))
 537     {
 538         return;
 539     }
 540     buffer_pointer = buffer->buffer + buffer->offset;
 541
 542     buffer->offset += strlen((const char*)buffer_pointer);
 543 }
 544
 545 /* securely comparison of floating-point variables */
 546 static cJSON_bool compare_double(double a, double b)
 547 {
 548     double maxVal = fabs(a) > fabs(b) ? fabs(a) : fabs(b);
 549     return (fabs(a - b) <= maxVal * DBL_EPSILON);
 550 }
 551
 552 /* Render the number nicely from the given item into a string. */
 553 static cJSON_bool print_number(const cJSON * const item, printbuffer * const output_buffer)
 554 {
 555     unsigned char *output_pointer = NULL;
 556     double d = item->valuedouble;
 557     int length = 0;
 558     size_t i = 0;
 559     unsigned char number_buffer[26] = {0}; /* temporary buffer to print the number into */
 560     unsigned char decimal_point = get_decimal_point();
 561     double test = 0.0;
 562
 563     if (output_buffer == NULL)
 564     {
 565         return false;
 566     }
 567
 568     /* This checks for NaN and Infinity */
 569     if (isnan(d) || isinf(d))
 570     {
 571         length = sprintf((char*)number_buffer, "null");
 572     }
 573     else
 574     {
 575         /* Try 15 decimal places of precision to avoid nonsignificant nonzero digits */
 576         length = sprintf((char*)number_buffer, "%1.15g", d);
 577
 578         /* Check whether the original double can be recovered */
 579         if ((sscanf((char*)number_buffer, "%lg", &test) != 1) || !compare_double((double)test, d))
 580         {
 581             /* If not, print with 17 decimal places of precision */
 582             length = sprintf((char*)number_buffer, "%1.17g", d);
 583         }
 584     }
 585
 586     /* sprintf failed or buffer overrun occurred */
 587     if ((length < 0) || (length > (int)(sizeof(number_buffer) - 1)))
 588     {
 589         return false;
 590     }
 591
 592     /* reserve appropriate space in the output */
 593     output_pointer = ensure(output_buffer, (size_t)length + sizeof(""));
 594     if (output_pointer == NULL)
 595     {
 596         return false;
 597     }
 598
 599     /* copy the printed number to the output and replace locale
 600      * dependent decimal point with '.' */
 601     for (i = 0; i < ((size_t)length); i++)
 602     {
 603         if (number_buffer[i] == decimal_point)
 604         {
 605             output_pointer[i] = '.';
 606             continue;
 607         }
 608
 609         output_pointer[i] = number_buffer[i];
 610     }
 611     output_pointer[i] = '\0';
 612
 613     output_buffer->offset += (size_t)length;
 614
 615     return true;
 616 }
 617
 618 /* parse 4 digit hexadecimal number */
 619 static unsigned parse_hex4(const unsigned char * const input)
 620 {
 621     unsigned int h = 0;
 622     size_t i = 0;
 623
 624     for (i = 0; i < 4; i++)
 625     {
 626         /* parse digit */
 627         if ((input[i] >= '0') && (input[i] <= '9'))
 628         {
 629             h += (unsigned int) input[i] - '0';
 630         }
 631         else if ((input[i] >= 'A') && (input[i] <= 'F'))
 632         {
 633             h += (unsigned int) 10 + input[i] - 'A';
 634         }
 635         else if ((input[i] >= 'a') && (input[i] <= 'f'))
 636         {
 637             h += (unsigned int) 10 + input[i] - 'a';
 638         }
 639         else /* invalid */
 640         {
 641             return 0;
 642         }
 643
 644         if (i < 3)
 645         {
 646             /* shift left to make place for the next nibble */
 647             h = h << 4;
 648         }
 649     }
 650
 651     return h;
 652 }
 653
 654 /* converts a UTF-16 literal to UTF-8
 655  * A literal can be one or two sequences of the form \uXXXX */
 656 static unsigned char utf16_literal_to_utf8(const unsigned char * const input_pointer, const unsigned char * const input_end, unsigned char **output_pointer)
 657 {
 658     long unsigned int codepoint = 0;
 659     unsigned int first_code = 0;
 660     const unsigned char *first_sequence = input_pointer;
 661     unsigned char utf8_length = 0;
 662     unsigned char utf8_position = 0;
 663     unsigned char sequence_length = 0;
 664     unsigned char first_byte_mark = 0;
 665
 666     if ((input_end - first_sequence) < 6)
 667     {
 668         /* input ends unexpectedly */
 669         goto fail;
 670     }
 671
 672     /* get the first utf16 sequence */
 673     first_code = parse_hex4(first_sequence + 2);
 674
 675     /* check that the code is valid */
 676     if (((first_code >= 0xDC00) && (first_code <= 0xDFFF)))
 677     {
 678         goto fail;
 679     }
 680
 681     /* UTF16 surrogate pair */
 682     if ((first_code >= 0xD800) && (first_code <= 0xDBFF))
 683     {
 684         const unsigned char *second_sequence = first_sequence + 6;
 685         unsigned int second_code = 0;
 686         sequence_length = 12; /* \uXXXX\uXXXX */
 687
 688         if ((input_end - second_sequence) < 6)
 689         {
 690             /* input ends unexpectedly */
 691             goto fail;
 692         }
 693
 694         if ((second_sequence[0] != '\\') || (second_sequence[1] != 'u'))
 695         {
 696             /* missing second half of the surrogate pair */
 697             goto fail;
 698         }
 699
 700         /* get the second utf16 sequence */
 701         second_code = parse_hex4(second_sequence + 2);
 702         /* check that the code is valid */
 703         if ((second_code < 0xDC00) || (second_code > 0xDFFF))
 704         {
 705             /* invalid second half of the surrogate pair */
 706             goto fail;
 707         }
 708
 709
 710         /* calculate the unicode codepoint from the surrogate pair */
 711         codepoint = 0x10000 + (((first_code & 0x3FF) << 10) | (second_code & 0x3FF));
 712     }
 713     else
 714     {
 715         sequence_length = 6; /* \uXXXX */
 716         codepoint = first_code;
 717     }
 718
 719     /* encode as UTF-8
 720      * takes at maximum 4 bytes to encode:
 721      * 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx */
 722     if (codepoint < 0x80)
 723     {
 724         /* normal ascii, encoding 0xxxxxxx */
 725         utf8_length = 1;
 726     }
 727     else if (codepoint < 0x800)
 728     {
 729         /* two bytes, encoding 110xxxxx 10xxxxxx */
 730         utf8_length = 2;
 731         first_byte_mark = 0xC0; /* 11000000 */
 732     }
 733     else if (codepoint < 0x10000)
 734     {
 735         /* three bytes, encoding 1110xxxx 10xxxxxx 10xxxxxx */
 736         utf8_length = 3;
 737         first_byte_mark = 0xE0; /* 11100000 */
 738     }
 739     else if (codepoint <= 0x10FFFF)
 740     {
 741         /* four bytes, encoding 1110xxxx 10xxxxxx 10xxxxxx 10xxxxxx */
 742         utf8_length = 4;
 743         first_byte_mark = 0xF0; /* 11110000 */
 744     }
 745     else
 746     {
 747         /* invalid unicode codepoint */
 748         goto fail;
 749     }
 750
 751     /* encode as utf8 */
 752     for (utf8_position = (unsigned char)(utf8_length - 1); utf8_position > 0; utf8_position--)
 753     {
 754         /* 10xxxxxx */
 755         (*output_pointer)[utf8_position] = (unsigned char)((codepoint | 0x80) & 0xBF);
 756         codepoint >>= 6;
 757     }
 758     /* encode first byte */
 759     if (utf8_length > 1)
 760     {
 761         (*output_pointer)[0] = (unsigned char)((codepoint | first_byte_mark) & 0xFF);
 762     }
 763     else
 764     {
 765         (*output_pointer)[0] = (unsigned char)(codepoint & 0x7F);
 766     }
 767
 768     *output_pointer += utf8_length;
 769
 770     return sequence_length;
 771
 772 fail:
 773     return 0;
 774 }
 775
 776 /* Parse the input text into an unescaped cinput, and populate item. */
 777 static cJSON_bool parse_string(cJSON * const item, parse_buffer * const input_buffer)
 778 {
 779     const unsigned char *input_pointer = buffer_at_offset(input_buffer) + 1;
 780     const unsigned char *input_end = buffer_at_offset(input_buffer) + 1;
 781     unsigned char *output_pointer = NULL;
 782     unsigned char *output = NULL;
 783
 784     /* not a string */
 785     if (buffer_at_offset(input_buffer)[0] != '\"')
 786     {
 787         goto fail;
 788     }
 789
 790     {
 791         /* calculate approximate size of the output (overestimate) */
 792         size_t allocation_length = 0;
 793         size_t skipped_bytes = 0;
 794         while (((size_t)(input_end - input_buffer->content) < input_buffer->length) && (*input_end != '\"'))
 795         {
 796             /* is escape sequence */
 797             if (input_end[0] == '\\')
 798             {
 799                 if ((size_t)(input_end + 1 - input_buffer->content) >= input_buffer->length)
 800                 {
 801                     /* prevent buffer overflow when last input character is a backslash */
 802                     goto fail;
 803                 }
 804                 skipped_bytes++;
 805                 input_end++;
 806             }
 807             input_end++;
 808         }
 809         if (((size_t)(input_end - input_buffer->content) >= input_buffer->length) || (*input_end != '\"'))
 810         {
 811             goto fail; /* string ended unexpectedly */
 812         }
 813
 814         /* This is at most how much we need for the output */
 815         allocation_length = (size_t) (input_end - buffer_at_offset(input_buffer)) - skipped_bytes;
 816         output = (unsigned char*)input_buffer->hooks.allocate(allocation_length + sizeof(""));
 817         if (output == NULL)
 818         {
 819             goto fail; /* allocation failure */
 820         }
 821     }
 822
 823     output_pointer = output;
 824     /* loop through the string literal */
 825     while (input_pointer < input_end)
 826     {
 827         if (*input_pointer != '\\')
 828         {
 829             *output_pointer++ = *input_pointer++;
 830         }
 831         /* escape sequence */
 832         else
 833         {
 834             unsigned char sequence_length = 2;
 835             if ((input_end - input_pointer) < 1)
 836             {
 837                 goto fail;
 838             }
 839
 840             switch (input_pointer[1])
 841             {
 842                 case 'b':
 843                     *output_pointer++ = '\b';
 844                     break;
 845                 case 'f':
 846                     *output_pointer++ = '\f';
 847                     break;
 848                 case 'n':
 849                     *output_pointer++ = '\n';
 850                     break;
 851                 case 'r':
 852                     *output_pointer++ = '\r';
 853                     break;
 854                 case 't':
 855                     *output_pointer++ = '\t';
 856                     break;
 857                 case '\"':
 858                 case '\\':
 859                 case '/':
 860                     *output_pointer++ = input_pointer[1];
 861                     break;
 862
 863                 /* UTF-16 literal */
 864                 case 'u':
 865                     sequence_length = utf16_literal_to_utf8(input_pointer, input_end, &output_pointer);
 866                     if (sequence_length == 0)
 867                     {
 868                         /* failed to convert UTF16-literal to UTF-8 */
 869                         goto fail;
 870                     }
 871                     break;
 872
 873                 default:
 874                     goto fail;
 875             }
 876             input_pointer += sequence_length;
 877         }
 878     }
 879
 880     /* zero terminate the output */
 881     *output_pointer = '\0';
 882
 883     item->type = cJSON_String;
 884     item->valuestring = (char*)output;
 885
 886     input_buffer->offset = (size_t) (input_end - input_buffer->content);
 887     input_buffer->offset++;
 888
 889     return true;
 890
 891 fail:
 892     if (output != NULL)
 893     {
 894         input_buffer->hooks.deallocate(output);
 895     }
 896
 897     if (input_pointer != NULL)
 898     {
 899         input_buffer->offset = (size_t)(input_pointer - input_buffer->content);
 900     }
 901
 902     return false;
 903 }
 904
 905 /* Render the cstring provided to an escaped version that can be printed. */
 906 static cJSON_bool print_string_ptr(const unsigned char * const input, printbuffer * const output_buffer)
 907 {
 908     const unsigned char *input_pointer = NULL;
 909     unsigned char *output = NULL;
 910     unsigned char *output_pointer = NULL;
 911     size_t output_length = 0;
 912     /* numbers of additional characters needed for escaping */
 913     size_t escape_characters = 0;
 914
 915     if (output_buffer == NULL)
 916     {
 917         return false;
 918     }
 919
 920     /* empty string */
 921     if (input == NULL)
 922     {
 923         output = ensure(output_buffer, sizeof("\"\""));
 924         if (output == NULL)
 925         {
 926             return false;
 927         }
 928         strcpy((char*)output, "\"\"");
 929
 930         return true;
 931     }
 932
 933     /* set "flag" to 1 if something needs to be escaped */
 934     for (input_pointer = input; *input_pointer; input_pointer++)
 935     {
 936         switch (*input_pointer)
 937         {
 938             case '\"':
 939             case '\\':
 940             case '\b':
 941             case '\f':
 942             case '\n':
 943             case '\r':
 944             case '\t':
 945                 /* one character escape sequence */
 946                 escape_characters++;
 947                 break;
 948             default:
 949                 if (*input_pointer < 32)
 950                 {
 951                     /* UTF-16 escape sequence uXXXX */
 952                     escape_characters += 5;
 953                 }
 954                 break;
 955         }
 956     }
 957     output_length = (size_t)(input_pointer - input) + escape_characters;
 958
 959     output = ensure(output_buffer, output_length + sizeof("\"\""));
 960     if (output == NULL)
 961     {
 962         return false;
 963     }
 964
 965     /* no characters have to be escaped */
 966     if (escape_characters == 0)
 967     {
 968         output[0] = '\"';
 969         memcpy(output + 1, input, output_length);
 970         output[output_length + 1] = '\"';
 971         output[output_length + 2] = '\0';
 972
 973         return true;
 974     }
 975
 976     output[0] = '\"';
 977     output_pointer = output + 1;
 978     /* copy the string */
 979     for (input_pointer = input; *input_pointer != '\0'; (void)input_pointer++, output_pointer++)
 980     {
 981         if ((*input_pointer > 31) && (*input_pointer != '\"') && (*input_pointer != '\\'))
 982         {
 983             /* normal character, copy */
 984             *output_pointer = *input_pointer;
 985         }
 986         else
 987         {
 988             /* character needs to be escaped */
 989             *output_pointer++ = '\\';
 990             switch (*input_pointer)
 991             {
 992                 case '\\':
 993                     *output_pointer = '\\';
 994                     break;
 995                 case '\"':
 996                     *output_pointer = '\"';
 997                     break;
 998                 case '\b':
 999                     *output_pointer = 'b';
1000                     break;
1001                 case '\f':
1002                     *output_pointer = 'f';
1003                     break;
1004                 case '\n':
1005                     *output_pointer = 'n';
1006                     break;
1007                 case '\r':
1008                     *output_pointer = 'r';
1009                     break;
1010                 case '\t':
1011                     *output_pointer = 't';
1012                     break;
1013                 default:
1014                     /* escape and print as unicode codepoint */
1015                     sprintf((char*)output_pointer, "u%04x", *input_pointer);
1016                     output_pointer += 4;
1017                     break;
1018             }
1019         }
1020     }
1021     output[output_length + 1] = '\"';
1022     output[output_length + 2] = '\0';
1023
1024     return true;
1025 }
1026
1027 /* Invoke print_string_ptr (which is useful) on an item. */
1028 static cJSON_bool print_string(const cJSON * const item, printbuffer * const p)
1029 {
1030     return print_string_ptr((unsigned char*)item->valuestring, p);
1031 }
1032
1033 /* Predeclare these prototypes. */
1034 static cJSON_bool parse_value(cJSON * const item, parse_buffer * const input_buffer);
1035 static cJSON_bool print_value(const cJSON * const item, printbuffer * const output_buffer);
1036 static cJSON_bool parse_array(cJSON * const item, parse_buffer * const input_buffer);
1037 static cJSON_bool print_array(const cJSON * const item, printbuffer * const output_buffer);
1038 static cJSON_bool parse_object(cJSON * const item, parse_buffer * const input_buffer);
1039 static cJSON_bool print_object(const cJSON * const item, printbuffer * const output_buffer);
1040
1041 /* Utility to jump whitespace and cr/lf */
1042 static parse_buffer *buffer_skip_whitespace(parse_buffer * const buffer)
1043 {
1044     if ((buffer == NULL) || (buffer->content == NULL))
1045     {
1046         return NULL;
1047     }
1048
1049     if (cannot_access_at_index(buffer, 0))
1050     {
1051         return buffer;
1052     }
1053
1054     while (can_access_at_index(buffer, 0) && (buffer_at_offset(buffer)[0] <= 32))
1055     {
1056        buffer->offset++;
1057     }
1058
1059     if (buffer->offset == buffer->length)
1060     {
1061         buffer->offset--;
1062     }
1063
1064     return buffer;
1065 }
1066
1067 /* skip the UTF-8 BOM (byte order mark) if it is at the beginning of a buffer */
1068 static parse_buffer *skip_utf8_bom(parse_buffer * const buffer)
1069 {
1070     if ((buffer == NULL) || (buffer->content == NULL) || (buffer->offset != 0))
1071     {
1072         return NULL;
1073     }
1074
1075     if (can_access_at_index(buffer, 4) && (strncmp((const char*)buffer_at_offset(buffer), "\xEF\xBB\xBF", 3) == 0))
1076     {
1077         buffer->offset += 3;
1078     }
1079
1080     return buffer;
1081 }
1082
1083 CJSON_PUBLIC(cJSON *) cJSON_ParseWithOpts(const char *value, const char **return_parse_end, cJSON_bool require_null_terminated)
1084 {
1085     size_t buffer_length;
1086
1087     if (NULL == value)
1088     {
1089         return NULL;
1090     }
1091
1092     /* Adding null character size due to require_null_terminated. */
1093     buffer_length = strlen(value) + sizeof("");
1094
1095     return cJSON_ParseWithLengthOpts(value, buffer_length, return_parse_end, require_null_terminated);
1096 }
1097
1098 /* Parse an object - create a new root, and populate. */
1099 CJSON_PUBLIC(cJSON *) cJSON_ParseWithLengthOpts(const char *value, size_t buffer_length, const char **return_parse_end, cJSON_bool require_null_terminated)
1100 {
1101     parse_buffer buffer = { 0, 0, 0, 0, { 0, 0, 0 } };
1102     cJSON *item = NULL;
1103
1104     /* reset error position */
1105     global_error.json = NULL;
1106     global_error.position = 0;
1107
1108     if (value == NULL || 0 == buffer_length)
1109     {
1110         goto fail;
1111     }
1112
1113     buffer.content = (const unsigned char*)value;
1114     buffer.length = buffer_length;
1115     buffer.offset = 0;
1116     buffer.hooks = global_hooks;
1117
1118     item = cJSON_New_Item(&global_hooks);
1119     if (item == NULL) /* memory fail */
1120     {
1121         goto fail;
1122     }
1123
1124     if (!parse_value(item, buffer_skip_whitespace(skip_utf8_bom(&buffer))))
1125     {
1126         /* parse failure. ep is set. */
1127         goto fail;
1128     }
1129
1130     /* if we require null-terminated JSON without appended garbage, skip and then check for a null terminator */
1131     if (require_null_terminated)
1132     {
1133         buffer_skip_whitespace(&buffer);
1134         if ((buffer.offset >= buffer.length) || buffer_at_offset(&buffer)[0] != '\0')
1135         {
1136             goto fail;
1137         }
1138     }
1139     if (return_parse_end)
1140     {
1141         *return_parse_end = (const char*)buffer_at_offset(&buffer);
1142     }
1143
1144     return item;
1145
1146 fail:
1147     if (item != NULL)
1148     {
1149         cJSON_Delete(item);
1150     }
1151
1152     if (value != NULL)
1153     {
1154         error local_error;
1155         local_error.json = (const unsigned char*)value;
1156         local_error.position = 0;
1157
1158         if (buffer.offset < buffer.length)
1159         {
1160             local_error.position = buffer.offset;
1161         }
1162         else if (buffer.length > 0)
1163         {
1164             local_error.position = buffer.length - 1;
1165         }
1166
1167         if (return_parse_end != NULL)
1168         {
1169             *return_parse_end = (const char*)local_error.json + local_error.position;
1170         }
1171
1172         global_error = local_error;
1173     }
1174
1175     return NULL;
1176 }
1177
1178 /* Default options for cJSON_Parse */
1179 CJSON_PUBLIC(cJSON *) cJSON_Parse(const char *value)
1180 {
1181     return cJSON_ParseWithOpts(value, 0, 0);
1182 }
1183
1184 CJSON_PUBLIC(cJSON *) cJSON_ParseWithLength(const char *value, size_t buffer_length)
1185 {
1186     return cJSON_ParseWithLengthOpts(value, buffer_length, 0, 0);
1187 }
1188
1189 #define cjson_min(a, b) (((a) < (b)) ? (a) : (b))
1190
1191 static unsigned char *print(const cJSON * const item, cJSON_bool format, const internal_hooks * const hooks)
1192 {
1193     static const size_t default_buffer_size = 256;
1194     printbuffer buffer[1];
1195     unsigned char *printed = NULL;
1196
1197     memset(buffer, 0, sizeof(buffer));
1198
1199     /* create buffer */
1200     buffer->buffer = (unsigned char*) hooks->allocate(default_buffer_size);
1201     buffer->length = default_buffer_size;
1202     buffer->format = format;
1203     buffer->hooks = *hooks;
1204     if (buffer->buffer == NULL)
1205     {
1206         goto fail;
1207     }
1208
1209     /* print the value */
1210     if (!print_value(item, buffer))
1211     {
1212         goto fail;
1213     }
1214     update_offset(buffer);
1215
1216     /* check if reallocate is available */
1217     if (hooks->reallocate != NULL)
1218     {
1219         printed = (unsigned char*) hooks->reallocate(buffer->buffer, buffer->offset + 1, default_buffer_size);
1220         if (printed == NULL) {
1221             goto fail;
1222         }
1223         buffer->buffer = NULL;
1224     }
1225     else /* otherwise copy the JSON over to a new buffer */
1226     {
1227         printed = (unsigned char*) hooks->allocate(buffer->offset + 1);
1228         if (printed == NULL)
1229         {
1230             goto fail;
1231         }
1232         memcpy(printed, buffer->buffer, cjson_min(buffer->length, buffer->offset + 1));
1233         printed[buffer->offset] = '\0'; /* just to be sure */
1234
1235         /* free the buffer */
1236         hooks->deallocate(buffer->buffer);
1237     }
1238
1239     return printed;
1240
1241 fail:
1242     if (buffer->buffer != NULL)
1243     {
1244         hooks->deallocate(buffer->buffer);
1245     }
1246
1247     if (printed != NULL)
1248     {
1249         hooks->deallocate(printed);
1250     }
1251
1252     return NULL;
1253 }
1254
1255 /* Render a cJSON item/entity/structure to text. */
1256 CJSON_PUBLIC(char *) cJSON_Print(const cJSON *item)
1257 {
1258     return (char*)print(item, true, &global_hooks);
1259 }
1260
1261 CJSON_PUBLIC(char *) cJSON_PrintUnformatted(const cJSON *item)
1262 {
1263     return (char*)print(item, false, &global_hooks);
1264 }
1265
1266 CJSON_PUBLIC(char *) cJSON_PrintBuffered(const cJSON *item, int prebuffer, cJSON_bool fmt)
1267 {
1268     printbuffer p = { 0, 0, 0, 0, 0, 0, { 0, 0, 0 } };
1269
1270     if (prebuffer < 0)
1271     {
1272         return NULL;
1273     }
1274
1275     p.buffer = (unsigned char*)global_hooks.allocate((size_t)prebuffer);
1276     if (!p.buffer)
1277     {
1278         return NULL;
1279     }
1280
1281     p.length = (size_t)prebuffer;
1282     p.offset = 0;
1283     p.noalloc = false;
1284     p.format = fmt;
1285     p.hooks = global_hooks;
1286
1287     if (!print_value(item, &p))
1288     {
1289         global_hooks.deallocate(p.buffer);
1290         return NULL;
1291     }
1292
1293     return (char*)p.buffer;
1294 }
1295
1296 CJSON_PUBLIC(cJSON_bool) cJSON_PrintPreallocated(cJSON *item, char *buffer, const int length, const cJSON_bool format)
1297 {
1298     printbuffer p = { 0, 0, 0, 0, 0, 0, { 0, 0, 0 } };
1299
1300     if ((length < 0) || (buffer == NULL))
1301     {
1302         return false;
1303     }
1304
1305     p.buffer = (unsigned char*)buffer;
1306     p.length = (size_t)length;
1307     p.offset = 0;
1308     p.noalloc = true;
1309     p.format = format;
1310     p.hooks = global_hooks;
1311
1312     return print_value(item, &p);
1313 }
1314
1315 /* Parser core - when encountering text, process appropriately. */
1316 static cJSON_bool parse_value(cJSON * const item, parse_buffer * const input_buffer)
1317 {
1318     if ((input_buffer == NULL) || (input_buffer->content == NULL))
1319     {
1320         return false; /* no input */
1321     }
1322
1323     /* parse the different types of values */
1324     /* null */
1325     if (can_read(input_buffer, 4) && (strncmp((const char*)buffer_at_offset(input_buffer), "null", 4) == 0))
1326     {
1327         item->type = cJSON_NULL;
1328         input_buffer->offset += 4;
1329         return true;
1330     }
1331     /* false */
1332     if (can_read(input_buffer, 5) && (strncmp((const char*)buffer_at_offset(input_buffer), "false", 5) == 0))
1333     {
1334         item->type = cJSON_False;
1335         input_buffer->offset += 5;
1336         return true;
1337     }
1338     /* true */
1339     if (can_read(input_buffer, 4) && (strncmp((const char*)buffer_at_offset(input_buffer), "true", 4) == 0))
1340     {
1341         item->type = cJSON_True;
1342         item->valueint = 1;
1343         input_buffer->offset += 4;
1344         return true;
1345     }
1346     /* string */
1347     if (can_access_at_index(input_buffer, 0) && (buffer_at_offset(input_buffer)[0] == '\"'))
1348     {
1349         return parse_string(item, input_buffer);
1350     }
1351     /* number */
1352     if (can_access_at_index(input_buffer, 0) && ((buffer_at_offset(input_buffer)[0] == '-') || ((buffer_at_offset(input_buffer)[0] >= '0') && (buffer_at_offset(input_buffer)[0] <= '9'))))
1353     {
1354         return parse_number(item, input_buffer);
1355     }
1356     /* array */
1357     if (can_access_at_index(input_buffer, 0) && (buffer_at_offset(input_buffer)[0] == '['))
1358     {
1359         return parse_array(item, input_buffer);
1360     }
1361     /* object */
1362     if (can_access_at_index(input_buffer, 0) && (buffer_at_offset(input_buffer)[0] == '{'))
1363     {
1364         return parse_object(item, input_buffer);
1365     }
1366
1367     return false;
1368 }
1369
1370 /* Render a value to text. */
1371 static cJSON_bool print_value(const cJSON * const item, printbuffer * const output_buffer)
1372 {
1373     unsigned char *output = NULL;
1374
1375     if ((item == NULL) || (output_buffer == NULL))
1376     {
1377         return false;
1378     }
1379
1380     switch ((item->type) & 0xFF)
1381     {
1382         case cJSON_NULL:
1383             output = ensure(output_buffer, 5);
1384             if (output == NULL)
1385             {
1386                 return false;
1387             }
1388             strcpy((char*)output, "null");
1389             return true;
1390
1391         case cJSON_False:
1392             output = ensure(output_buffer, 6);
1393             if (output == NULL)
1394             {
1395                 return false;
1396             }
1397             strcpy((char*)output, "false");
1398             return true;
1399
1400         case cJSON_True:
1401             output = ensure(output_buffer, 5);
1402             if (output == NULL)
1403             {
1404                 return false;
1405             }
1406             strcpy((char*)output, "true");
1407             return true;
1408
1409         case cJSON_Number:
1410             return print_number(item, output_buffer);
1411
1412         case cJSON_Raw:
1413         {
1414             size_t raw_length = 0;
1415             if (item->valuestring == NULL)
1416             {
1417                 return false;
1418             }
1419
1420             raw_length = strlen(item->valuestring) + sizeof("");
1421             output = ensure(output_buffer, raw_length);
1422             if (output == NULL)
1423             {
1424                 return false;
1425             }
1426             memcpy(output, item->valuestring, raw_length);
1427             return true;
1428         }
1429
1430         case cJSON_String:
1431             return print_string(item, output_buffer);
1432
1433         case cJSON_Array:
1434             return print_array(item, output_buffer);
1435
1436         case cJSON_Object:
1437             return print_object(item, output_buffer);
1438
1439         default:
1440             return false;
1441     }
1442 }
1443
1444 /* Build an array from input text. */
1445 static cJSON_bool parse_array(cJSON * const item, parse_buffer * const input_buffer)
1446 {
1447     cJSON *head = NULL; /* head of the linked list */
1448     cJSON *current_item = NULL;
1449
1450     if (input_buffer->depth >= CJSON_NESTING_LIMIT)
1451     {
1452         return false; /* to deeply nested */
1453     }
1454     input_buffer->depth++;
1455
1456     if (buffer_at_offset(input_buffer)[0] != '[')
1457     {
1458         /* not an array */
1459         goto fail;
1460     }
1461
1462     input_buffer->offset++;
1463     buffer_skip_whitespace(input_buffer);
1464     if (can_access_at_index(input_buffer, 0) && (buffer_at_offset(input_buffer)[0] == ']'))
1465     {
1466         /* empty array */
1467         goto success;
1468     }
1469
1470     /* check if we skipped to the end of the buffer */
1471     if (cannot_access_at_index(input_buffer, 0))
1472     {
1473         input_buffer->offset--;
1474         goto fail;
1475     }
1476
1477     /* step back to character in front of the first element */
1478     input_buffer->offset--;
1479     /* loop through the comma separated array elements */
1480     do
1481     {
1482         /* allocate next item */
1483         cJSON *new_item = cJSON_New_Item(&(input_buffer->hooks));
1484         if (new_item == NULL)
1485         {
1486             goto fail; /* allocation failure */
1487         }
1488
1489         /* attach next item to list */
1490         if (head == NULL)
1491         {
1492             /* start the linked list */
1493             current_item = head = new_item;
1494         }
1495         else
1496         {
1497             /* add to the end and advance */
1498             current_item->next = new_item;
1499             new_item->prev = current_item;
1500             current_item = new_item;
1501         }
1502
1503         /* parse next value */
1504         input_buffer->offset++;
1505         buffer_skip_whitespace(input_buffer);
1506         if (!parse_value(current_item, input_buffer))
1507         {
1508             goto fail; /* failed to parse value */
1509         }
1510         buffer_skip_whitespace(input_buffer);
1511     }
1512     while (can_access_at_index(input_buffer, 0) && (buffer_at_offset(input_buffer)[0] == ','));
1513
1514     if (cannot_access_at_index(input_buffer, 0) || buffer_at_offset(input_buffer)[0] != ']')
1515     {
1516         goto fail; /* expected end of array */
1517     }
1518
1519 success:
1520     input_buffer->depth--;
1521
1522     if (head != NULL) {
1523         head->prev = current_item;
1524     }
1525
1526     item->type = cJSON_Array;
1527     item->child = head;
1528
1529     input_buffer->offset++;
1530
1531     return true;
1532
1533 fail:
1534     if (head != NULL)
1535     {
1536         cJSON_Delete(head);
1537     }
1538
1539     return false;
1540 }
1541
1542 /* Render an array to text */
1543 static cJSON_bool print_array(const cJSON * const item, printbuffer * const output_buffer)
1544 {
1545     unsigned char *output_pointer = NULL;
1546     size_t length = 0;
1547     cJSON *current_element = item->child;
1548
1549     if (output_buffer == NULL)
1550     {
1551         return false;
1552     }
1553
1554     /* Compose the output array. */
1555     /* opening square bracket */
1556     output_pointer = ensure(output_buffer, 1);
1557     if (output_pointer == NULL)
1558     {
1559         return false;
1560     }
1561
1562     *output_pointer = '[';
1563     output_buffer->offset++;
1564     output_buffer->depth++;
1565
1566     while (current_element != NULL)
1567     {
1568         if (!print_value(current_element, output_buffer))
1569         {
1570             return false;
1571         }
1572         update_offset(output_buffer);
1573         if (current_element->next)
1574         {
1575             length = (size_t) (output_buffer->format ? 2 : 1);
1576             output_pointer = ensure(output_buffer, length + 1);
1577             if (output_pointer == NULL)
1578             {
1579                 return false;
1580             }
1581             *output_pointer++ = ',';
1582             if(output_buffer->format)
1583             {
1584                 *output_pointer++ = ' ';
1585             }
1586             *output_pointer = '\0';
1587             output_buffer->offset += length;
1588         }
1589         current_element = current_element->next;
1590     }
1591
1592     output_pointer = ensure(output_buffer, 2);
1593     if (output_pointer == NULL)
1594     {
1595         return false;
1596     }
1597     *output_pointer++ = ']';
1598     *output_pointer = '\0';
1599     output_buffer->depth--;
1600
1601     return true;
1602 }
1603
1604 /* Build an object from the text. */
1605 static cJSON_bool parse_object(cJSON * const item, parse_buffer * const input_buffer)
1606 {
1607     cJSON *head = NULL; /* linked list head */
1608     cJSON *current_item = NULL;
1609
1610     if (input_buffer->depth >= CJSON_NESTING_LIMIT)
1611     {
1612         return false; /* to deeply nested */
1613     }
1614     input_buffer->depth++;
1615
1616     if (cannot_access_at_index(input_buffer, 0) || (buffer_at_offset(input_buffer)[0] != '{'))
1617     {
1618         goto fail; /* not an object */
1619     }
1620
1621     input_buffer->offset++;
1622     buffer_skip_whitespace(input_buffer);
1623     if (can_access_at_index(input_buffer, 0) && (buffer_at_offset(input_buffer)[0] == '}'))
1624     {
1625         goto success; /* empty object */
1626     }
1627
1628     /* check if we skipped to the end of the buffer */
1629     if (cannot_access_at_index(input_buffer, 0))
1630     {
1631         input_buffer->offset--;
1632         goto fail;
1633     }
1634
1635     /* step back to character in front of the first element */
1636     input_buffer->offset--;
1637     /* loop through the comma separated array elements */
1638     do
1639     {
1640         /* allocate next item */
1641         cJSON *new_item = cJSON_New_Item(&(input_buffer->hooks));
1642         if (new_item == NULL)
1643         {
1644             goto fail; /* allocation failure */
1645         }
1646
1647         /* attach next item to list */
1648         if (head == NULL)
1649         {
1650             /* start the linked list */
1651             current_item = head = new_item;
1652         }
1653         else
1654         {
1655             /* add to the end and advance */
1656             current_item->next = new_item;
1657             new_item->prev = current_item;
1658             current_item = new_item;
1659         }
1660
1661         /* parse the name of the child */
1662         input_buffer->offset++;
1663         buffer_skip_whitespace(input_buffer);
1664         if (!parse_string(current_item, input_buffer))
1665         {
1666             goto fail; /* failed to parse name */
1667         }
1668         buffer_skip_whitespace(input_buffer);
1669
1670         /* swap valuestring and string, because we parsed the name */
1671         current_item->string = current_item->valuestring;
1672         current_item->valuestring = NULL;
1673
1674         if (cannot_access_at_index(input_buffer, 0) || (buffer_at_offset(input_buffer)[0] != ':'))
1675         {
1676             goto fail; /* invalid object */
1677         }
1678
1679         /* parse the value */
1680         input_buffer->offset++;
1681         buffer_skip_whitespace(input_buffer);
1682         if (!parse_value(current_item, input_buffer))
1683         {
1684             goto fail; /* failed to parse value */
1685         }
1686         buffer_skip_whitespace(input_buffer);
1687     }
1688     while (can_access_at_index(input_buffer, 0) && (buffer_at_offset(input_buffer)[0] == ','));
1689
1690     if (cannot_access_at_index(input_buffer, 0) || (buffer_at_offset(input_buffer)[0] != '}'))
1691     {
1692         goto fail; /* expected end of object */
1693     }
1694
1695 success:
1696     input_buffer->depth--;
1697
1698     if (head != NULL) {
1699         head->prev = current_item;
1700     }
1701
1702     item->type = cJSON_Object;
1703     item->child = head;
1704
1705     input_buffer->offset++;
1706     return true;
1707
1708 fail:
1709     if (head != NULL)
1710     {
1711         cJSON_Delete(head);
1712     }
1713
1714     return false;
1715 }
1716
1717 /* Render an object to text. */
1718 static cJSON_bool print_object(const cJSON * const item, printbuffer * const output_buffer)
1719 {
1720     unsigned char *output_pointer = NULL;
1721     size_t length = 0;
1722     cJSON *current_item = item->child;
1723
1724     if (output_buffer == NULL)
1725     {
1726         return false;
1727     }
1728
1729     /* Compose the output: */
1730     length = (size_t) (output_buffer->format ? 2 : 1); /* fmt: {\n */
1731     output_pointer = ensure(output_buffer, length + 1);
1732     if (output_pointer == NULL)
1733     {
1734         return false;
1735     }
1736
1737     *output_pointer++ = '{';
1738     output_buffer->depth++;
1739     if (output_buffer->format)
1740     {
1741         *output_pointer++ = '\n';
1742     }
1743     output_buffer->offset += length;
1744
1745     while (current_item)
1746     {
1747         if (output_buffer->format)
1748         {
1749             size_t i;
1750             output_pointer = ensure(output_buffer, output_buffer->depth);
1751             if (output_pointer == NULL)
1752             {
1753                 return false;
1754             }
1755             for (i = 0; i < output_buffer->depth; i++)
1756             {
1757                 *output_pointer++ = '\t';
1758             }
1759             output_buffer->offset += output_buffer->depth;
1760         }
1761
1762         /* print key */
1763         if (!print_string_ptr((unsigned char*)current_item->string, output_buffer))
1764         {
1765             return false;
1766         }
1767         update_offset(output_buffer);
1768
1769         length = (size_t) (output_buffer->format ? 2 : 1);
1770         output_pointer = ensure(output_buffer, length);
1771         if (output_pointer == NULL)
1772         {
1773             return false;
1774         }
1775         *output_pointer++ = ':';
1776         if (output_buffer->format)
1777         {
1778             *output_pointer++ = '\t';
1779         }
1780         output_buffer->offset += length;
1781
1782         /* print value */
1783         if (!print_value(current_item, output_buffer))
1784         {
1785             return false;
1786         }
1787         update_offset(output_buffer);
1788
1789         /* print comma if not last */
1790         length = ((size_t)(output_buffer->format ? 1 : 0) + (size_t)(current_item->next ? 1 : 0));
1791         output_pointer = ensure(output_buffer, length + 1);
1792         if (output_pointer == NULL)
1793         {
1794             return false;
1795         }
1796         if (current_item->next)
1797         {
1798             *output_pointer++ = ',';
1799         }
1800
1801         if (output_buffer->format)
1802         {
1803             *output_pointer++ = '\n';
1804         }
1805         *output_pointer = '\0';
1806         output_buffer->offset += length;
1807
1808         current_item = current_item->next;
1809     }
1810
1811     output_pointer = ensure(output_buffer, output_buffer->format ? (output_buffer->depth + 1) : 2);
1812     if (output_pointer == NULL)
1813     {
1814         return false;
1815     }
1816     if (output_buffer->format)
1817     {
1818         size_t i;
1819         for (i = 0; i < (output_buffer->depth - 1); i++)
1820         {
1821             *output_pointer++ = '\t';
1822         }
1823     }
1824     *output_pointer++ = '}';
1825     *output_pointer = '\0';
1826     output_buffer->depth--;
1827
1828     return true;
1829 }
1830
1831 /* Get Array size/item / object item. */
1832 CJSON_PUBLIC(int) cJSON_GetArraySize(const cJSON *array)
1833 {
1834     cJSON *child = NULL;
1835     size_t size = 0;
1836
1837     if (array == NULL)
1838     {
1839         return 0;
1840     }
1841
1842     child = array->child;
1843
1844     while(child != NULL)
1845     {
1846         size++;
1847         child = child->next;
1848     }
1849
1850     /* FIXME: Can overflow here. Cannot be fixed without breaking the API */
1851
1852     return (int)size;
1853 }
1854
1855 static cJSON* get_array_item(const cJSON *array, size_t index)
1856 {
1857     cJSON *current_child = NULL;
1858
1859     if (array == NULL)
1860     {
1861         return NULL;
1862     }
1863
1864     current_child = array->child;
1865     while ((current_child != NULL) && (index > 0))
1866     {
1867         index--;
1868         current_child = current_child->next;
1869     }
1870
1871     return current_child;
1872 }
1873
1874 CJSON_PUBLIC(cJSON *) cJSON_GetArrayItem(const cJSON *array, int index)
1875 {
1876     if (index < 0)
1877     {
1878         return NULL;
1879     }
1880
1881     return get_array_item(array, (size_t)index);
1882 }
1883
1884 static cJSON *get_object_item(const cJSON * const object, const char * const name, const cJSON_bool case_sensitive)
1885 {
1886     cJSON *current_element = NULL;
1887
1888     if ((object == NULL) || (name == NULL))
1889     {
1890         return NULL;
1891     }
1892
1893     current_element = object->child;
1894     if (case_sensitive)
1895     {
1896         while ((current_element != NULL) && (current_element->string != NULL) && (strcmp(name, current_element->string) != 0))
1897         {
1898             current_element = current_element->next;
1899         }
1900     }
1901     else
1902     {
1903         while ((current_element != NULL) && (case_insensitive_strcmp((const unsigned char*)name, (const unsigned char*)(current_element->string)) != 0))
1904         {
1905             current_element = current_element->next;
1906         }
1907     }
1908
1909     if ((current_element == NULL) || (current_element->string == NULL)) {
1910         return NULL;
1911     }
1912
1913     return current_element;
1914 }
1915
1916 CJSON_PUBLIC(cJSON *) cJSON_GetObjectItem(const cJSON * const object, const char * const string)
1917 {
1918     return get_object_item(object, string, false);
1919 }
1920
1921 CJSON_PUBLIC(cJSON *) cJSON_GetObjectItemCaseSensitive(const cJSON * const object, const char * const string)
1922 {
1923     return get_object_item(object, string, true);
1924 }
1925
1926 CJSON_PUBLIC(cJSON_bool) cJSON_HasObjectItem(const cJSON *object, const char *string)
1927 {
1928     return cJSON_GetObjectItem(object, string) ? 1 : 0;
1929 }
1930
1931 /* Utility for array list handling. */
1932 static void suffix_object(cJSON *prev, cJSON *item)
1933 {
1934     prev->next = item;
1935     item->prev = prev;
1936 }
1937
1938 /* Utility for handling references. */
1939 static cJSON *create_reference(const cJSON *item, const internal_hooks * const hooks)
1940 {
1941     cJSON *reference = NULL;
1942     if (item == NULL)
1943     {
1944         return NULL;
1945     }
1946
1947     reference = cJSON_New_Item(hooks);
1948     if (reference == NULL)
1949     {
1950         return NULL;
1951     }
1952
1953     memcpy(reference, item, sizeof(cJSON));
1954     reference->string = NULL;
1955     reference->type |= cJSON_IsReference;
1956     reference->next = reference->prev = NULL;
1957     return reference;
1958 }
1959
1960 static cJSON_bool add_item_to_array(cJSON *array, cJSON *item)
1961 {
1962     cJSON *child = NULL;
1963
1964     if ((item == NULL) || (array == NULL) || (array == item))
1965     {
1966         return false;
1967     }
1968
1969     child = array->child;
1970     /*
1971      * To find the last item in array quickly, we use prev in array
1972      */
1973     if (child == NULL)
1974     {
1975         /* list is empty, start new one */
1976         array->child = item;
1977         item->prev = item;
1978         item->next = NULL;
1979     }
1980     else
1981     {
1982         /* append to the end */
1983         if (child->prev)
1984         {
1985             suffix_object(child->prev, item);
1986             array->child->prev = item;
1987         }
1988     }
1989
1990     return true;
1991 }
1992
1993 /* Add item to array/object. */
1994 CJSON_PUBLIC(cJSON_bool) cJSON_AddItemToArray(cJSON *array, cJSON *item)
1995 {
1996     return add_item_to_array(array, item);
1997 }
1998
1999 #if defined(__clang__) || (defined(__GNUC__)  && ((__GNUC__ > 4) || ((__GNUC__ == 4) && (__GNUC_MINOR__ > 5))))
2000     #pragma GCC diagnostic push
2001 #endif
2002 #ifdef __GNUC__
2003 #pragma GCC diagnostic ignored "-Wcast-qual"
2004 #endif
2005 /* helper function to cast away const */
2006 static void* cast_away_const(const void* string)
2007 {
2008     return (void*)string;
2009 }
2010 #if defined(__clang__) || (defined(__GNUC__)  && ((__GNUC__ > 4) || ((__GNUC__ == 4) && (__GNUC_MINOR__ > 5))))
2011     #pragma GCC diagnostic pop
2012 #endif
2013
2014
2015 static cJSON_bool add_item_to_object(cJSON * const object, const char * const string, cJSON * const item, const internal_hooks * const hooks, const cJSON_bool constant_key)
2016 {
2017     char *new_key = NULL;
2018     int new_type = cJSON_Invalid;
2019
2020     if ((object == NULL) || (string == NULL) || (item == NULL) || (object == item))
2021     {
2022         return false;
2023     }
2024
2025     if (constant_key)
2026     {
2027         new_key = (char*)cast_away_const(string);
2028         new_type = item->type | cJSON_StringIsConst;
2029     }
2030     else
2031     {
2032         new_key = (char*)cJSON_strdup((const unsigned char*)string, hooks);
2033         if (new_key == NULL)
2034         {
2035             return false;
2036         }
2037
2038         new_type = item->type & ~cJSON_StringIsConst;
2039     }
2040
2041     if (!(item->type & cJSON_StringIsConst) && (item->string != NULL))
2042     {
2043         hooks->deallocate(item->string);
2044     }
2045
2046     item->string = new_key;
2047     item->type = new_type;
2048
2049     return add_item_to_array(object, item);
2050 }
2051
2052 CJSON_PUBLIC(cJSON_bool) cJSON_AddItemToObject(cJSON *object, const char *string, cJSON *item)
2053 {
2054     return add_item_to_object(object, string, item, &global_hooks, false);
2055 }
2056
2057 /* Add an item to an object with constant string as key */
2058 CJSON_PUBLIC(cJSON_bool) cJSON_AddItemToObjectCS(cJSON *object, const char *string, cJSON *item)
2059 {
2060     return add_item_to_object(object, string, item, &global_hooks, true);
2061 }
2062
2063 CJSON_PUBLIC(cJSON_bool) cJSON_AddItemReferenceToArray(cJSON *array, cJSON *item)
2064 {
2065     if (array == NULL)
2066     {
2067         return false;
2068     }
2069
2070     return add_item_to_array(array, create_reference(item, &global_hooks));
2071 }
2072
2073 CJSON_PUBLIC(cJSON_bool) cJSON_AddItemReferenceToObject(cJSON *object, const char *string, cJSON *item)
2074 {
2075     if ((object == NULL) || (string == NULL))
2076     {
2077         return false;
2078     }
2079
2080     return add_item_to_object(object, string, create_reference(item, &global_hooks), &global_hooks, false);
2081 }
2082
2083 CJSON_PUBLIC(cJSON*) cJSON_AddNullToObject(cJSON * const object, const char * const name)
2084 {
2085     cJSON *null = cJSON_CreateNull();
2086     if (add_item_to_object(object, name, null, &global_hooks, false))
2087     {
2088         return null;
2089     }
2090
2091     cJSON_Delete(null);
2092     return NULL;
2093 }
2094
2095 CJSON_PUBLIC(cJSON*) cJSON_AddTrueToObject(cJSON * const object, const char * const name)
2096 {
2097     cJSON *true_item = cJSON_CreateTrue();
2098     if (add_item_to_object(object, name, true_item, &global_hooks, false))
2099     {
2100         return true_item;
2101     }
2102
2103     cJSON_Delete(true_item);
2104     return NULL;
2105 }
2106
2107 CJSON_PUBLIC(cJSON*) cJSON_AddFalseToObject(cJSON * const object, const char * const name)
2108 {
2109     cJSON *false_item = cJSON_CreateFalse();
2110     if (add_item_to_object(object, name, false_item, &global_hooks, false))
2111     {
2112         return false_item;
2113     }
2114
2115     cJSON_Delete(false_item);
2116     return NULL;
2117 }
2118
2119 CJSON_PUBLIC(cJSON*) cJSON_AddBoolToObject(cJSON * const object, const char * const name, const cJSON_bool boolean)
2120 {
2121     cJSON *bool_item = cJSON_CreateBool(boolean);
2122     if (add_item_to_object(object, name, bool_item, &global_hooks, false))
2123     {
2124         return bool_item;
2125     }
2126
2127     cJSON_Delete(bool_item);
2128     return NULL;
2129 }
2130
2131 CJSON_PUBLIC(cJSON*) cJSON_AddNumberToObject(cJSON * const object, const char * const name, const double number)
2132 {
2133     cJSON *number_item = cJSON_CreateNumber(number);
2134     if (add_item_to_object(object, name, number_item, &global_hooks, false))
2135     {
2136         return number_item;
2137     }
2138
2139     cJSON_Delete(number_item);
2140     return NULL;
2141 }
2142
2143 CJSON_PUBLIC(cJSON*) cJSON_AddStringToObject(cJSON * const object, const char * const name, const char * const string)
2144 {
2145     cJSON *string_item = cJSON_CreateString(string);
2146     if (add_item_to_object(object, name, string_item, &global_hooks, false))
2147     {
2148         return string_item;
2149     }
2150
2151     cJSON_Delete(string_item);
2152     return NULL;
2153 }
2154
2155 CJSON_PUBLIC(cJSON*) cJSON_AddRawToObject(cJSON * const object, const char * const name, const char * const raw)
2156 {
2157     cJSON *raw_item = cJSON_CreateRaw(raw);
2158     if (add_item_to_object(object, name, raw_item, &global_hooks, false))
2159     {
2160         return raw_item;
2161     }
2162
2163     cJSON_Delete(raw_item);
2164     return NULL;
2165 }
2166
2167 CJSON_PUBLIC(cJSON*) cJSON_AddObjectToObject(cJSON * const object, const char * const name)
2168 {
2169     cJSON *object_item = cJSON_CreateObject();
2170     if (add_item_to_object(object, name, object_item, &global_hooks, false))
2171     {
2172         return object_item;
2173     }
2174
2175     cJSON_Delete(object_item);
2176     return NULL;
2177 }
2178
2179 CJSON_PUBLIC(cJSON*) cJSON_AddArrayToObject(cJSON * const object, const char * const name)
2180 {
2181     cJSON *array = cJSON_CreateArray();
2182     if (add_item_to_object(object, name, array, &global_hooks, false))
2183     {
2184         return array;
2185     }
2186
2187     cJSON_Delete(array);
2188     return NULL;
2189 }
2190
2191 CJSON_PUBLIC(cJSON *) cJSON_DetachItemViaPointer(cJSON *parent, cJSON * const item)
2192 {
2193     if ((parent == NULL) || (item == NULL))
2194     {
2195         return NULL;
2196     }
2197
2198     if (item != parent->child)
2199     {
2200         /* not the first element */
2201         item->prev->next = item->next;
2202     }
2203     if (item->next != NULL)
2204     {
2205         /* not the last element */
2206         item->next->prev = item->prev;
2207     }
2208
2209     if (item == parent->child)
2210     {
2211         /* first element */
2212         parent->child = item->next;
2213     }
2214     else if (item->next == NULL)
2215     {
2216         /* last element */
2217         parent->child->prev = item->prev;
2218     }
2219
2220     /* make sure the detached item doesn't point anywhere anymore */
2221     item->prev = NULL;
2222     item->next = NULL;
2223
2224     return item;
2225 }
2226
2227 CJSON_PUBLIC(cJSON *) cJSON_DetachItemFromArray(cJSON *array, int which)
2228 {
2229     if (which < 0)
2230     {
2231         return NULL;
2232     }
2233
2234     return cJSON_DetachItemViaPointer(array, get_array_item(array, (size_t)which));
2235 }
2236
2237 CJSON_PUBLIC(void) cJSON_DeleteItemFromArray(cJSON *array, int which)
2238 {
2239     cJSON_Delete(cJSON_DetachItemFromArray(array, which));
2240 }
2241
2242 CJSON_PUBLIC(cJSON *) cJSON_DetachItemFromObject(cJSON *object, const char *string)
2243 {
2244     cJSON *to_detach = cJSON_GetObjectItem(object, string);
2245
2246     return cJSON_DetachItemViaPointer(object, to_detach);
2247 }
2248
2249 CJSON_PUBLIC(cJSON *) cJSON_DetachItemFromObjectCaseSensitive(cJSON *object, const char *string)
2250 {
2251     cJSON *to_detach = cJSON_GetObjectItemCaseSensitive(object, string);
2252
2253     return cJSON_DetachItemViaPointer(object, to_detach);
2254 }
2255
2256 CJSON_PUBLIC(void) cJSON_DeleteItemFromObject(cJSON *object, const char *string)
2257 {
2258     cJSON_Delete(cJSON_DetachItemFromObject(object, string));
2259 }
2260
2261 CJSON_PUBLIC(void) cJSON_DeleteItemFromObjectCaseSensitive(cJSON *object, const char *string)
2262 {
2263     cJSON_Delete(cJSON_DetachItemFromObjectCaseSensitive(object, string));
2264 }
2265
2266 /* Replace array/object items with new ones. */
2267 CJSON_PUBLIC(cJSON_bool) cJSON_InsertItemInArray(cJSON *array, int which, cJSON *newitem)
2268 {
2269     cJSON *after_inserted = NULL;
2270
2271     if (which < 0)
2272     {
2273         return false;
2274     }
2275
2276     after_inserted = get_array_item(array, (size_t)which);
2277     if (after_inserted == NULL)
2278     {
2279         return add_item_to_array(array, newitem);
2280     }
2281
2282     newitem->next = after_inserted;
2283     newitem->prev = after_inserted->prev;
2284     after_inserted->prev = newitem;
2285     if (after_inserted == array->child)
2286     {
2287         array->child = newitem;
2288     }
2289     else
2290     {
2291         newitem->prev->next = newitem;
2292     }
2293     return true;
2294 }
2295
2296 CJSON_PUBLIC(cJSON_bool) cJSON_ReplaceItemViaPointer(cJSON * const parent, cJSON * const item, cJSON * replacement)
2297 {
2298     if ((parent == NULL) || (replacement == NULL) || (item == NULL))
2299     {
2300         return false;
2301     }
2302
2303     if (replacement == item)
2304     {
2305         return true;
2306     }
2307
2308     replacement->next = item->next;
2309     replacement->prev = item->prev;
2310
2311     if (replacement->next != NULL)
2312     {
2313         replacement->next->prev = replacement;
2314     }
2315     if (parent->child == item)
2316     {
2317         if (parent->child->prev == parent->child)
2318         {
2319             replacement->prev = replacement;
2320         }
2321         parent->child = replacement;
2322     }
2323     else
2324     {   /*
2325          * To find the last item in array quickly, we use prev in array.
2326          * We can't modify the last item's next pointer where this item was the parent's child
2327          */
2328         if (replacement->prev != NULL)
2329         {
2330             replacement->prev->next = replacement;
2331         }
2332         if (replacement->next == NULL)
2333         {
2334             parent->child->prev = replacement;
2335         }
2336     }
2337
2338     item->next = NULL;
2339     item->prev = NULL;
2340     cJSON_Delete(item);
2341
2342     return true;
2343 }
2344
2345 CJSON_PUBLIC(cJSON_bool) cJSON_ReplaceItemInArray(cJSON *array, int which, cJSON *newitem)
2346 {
2347     if (which < 0)
2348     {
2349         return false;
2350     }
2351
2352     return cJSON_ReplaceItemViaPointer(array, get_array_item(array, (size_t)which), newitem);
2353 }
2354
2355 static cJSON_bool replace_item_in_object(cJSON *object, const char *string, cJSON *replacement, cJSON_bool case_sensitive)
2356 {
2357     if ((replacement == NULL) || (string == NULL))
2358     {
2359         return false;
2360     }
2361
2362     /* replace the name in the replacement */
2363     if (!(replacement->type & cJSON_StringIsConst) && (replacement->string != NULL))
2364     {
2365         cJSON_free(replacement->string);
2366     }
2367     replacement->string = (char*)cJSON_strdup((const unsigned char*)string, &global_hooks);
2368     replacement->type &= ~cJSON_StringIsConst;
2369
2370     return cJSON_ReplaceItemViaPointer(object, get_object_item(object, string, case_sensitive), replacement);
2371 }
2372
2373 CJSON_PUBLIC(cJSON_bool) cJSON_ReplaceItemInObject(cJSON *object, const char *string, cJSON *newitem)
2374 {
2375     return replace_item_in_object(object, string, newitem, false);
2376 }
2377
2378 CJSON_PUBLIC(cJSON_bool) cJSON_ReplaceItemInObjectCaseSensitive(cJSON *object, const char *string, cJSON *newitem)
2379 {
2380     return replace_item_in_object(object, string, newitem, true);
2381 }
2382
2383 /* Create basic types: */
2384 CJSON_PUBLIC(cJSON *) cJSON_CreateNull(void)
2385 {
2386     cJSON *item = cJSON_New_Item(&global_hooks);
2387     if(item)
2388     {
2389         item->type = cJSON_NULL;
2390     }
2391
2392     return item;
2393 }
2394
2395 CJSON_PUBLIC(cJSON *) cJSON_CreateTrue(void)
2396 {
2397     cJSON *item = cJSON_New_Item(&global_hooks);
2398     if(item)
2399     {
2400         item->type = cJSON_True;
2401     }
2402
2403     return item;
2404 }
2405
2406 CJSON_PUBLIC(cJSON *) cJSON_CreateFalse(void)
2407 {
2408     cJSON *item = cJSON_New_Item(&global_hooks);
2409     if(item)
2410     {
2411         item->type = cJSON_False;
2412     }
2413
2414     return item;
2415 }
2416
2417 CJSON_PUBLIC(cJSON *) cJSON_CreateBool(cJSON_bool boolean)
2418 {
2419     cJSON *item = cJSON_New_Item(&global_hooks);
2420     if(item)
2421     {
2422         item->type = boolean ? cJSON_True : cJSON_False;
2423     }
2424
2425     return item;
2426 }
2427
2428 CJSON_PUBLIC(cJSON *) cJSON_CreateNumber(double num)
2429 {
2430     cJSON *item = cJSON_New_Item(&global_hooks);
2431     if(item)
2432     {
2433         item->type = cJSON_Number;
2434         item->valuedouble = num;
2435
2436         /* use saturation in case of overflow */
2437         if (num >= INT_MAX)
2438         {
2439             item->valueint = INT_MAX;
2440         }
2441         else if (num <= (double)INT_MIN)
2442         {
2443             item->valueint = INT_MIN;
2444         }
2445         else
2446         {
2447             item->valueint = (int)num;
2448         }
2449     }
2450
2451     return item;
2452 }
2453
2454 CJSON_PUBLIC(cJSON *) cJSON_CreateString(const char *string)
2455 {
2456     cJSON *item = cJSON_New_Item(&global_hooks);
2457     if(item)
2458     {
2459         item->type = cJSON_String;
2460         item->valuestring = (char*)cJSON_strdup((const unsigned char*)string, &global_hooks);
2461         if(!item->valuestring)
2462         {
2463             cJSON_Delete(item);
2464             return NULL;
2465         }
2466     }
2467
2468     return item;
2469 }
2470
2471 CJSON_PUBLIC(cJSON *) cJSON_CreateStringReference(const char *string)
2472 {
2473     cJSON *item = cJSON_New_Item(&global_hooks);
2474     if (item != NULL)
2475     {
2476         item->type = cJSON_String | cJSON_IsReference;
2477         item->valuestring = (char*)cast_away_const(string);
2478     }
2479
2480     return item;
2481 }
2482
2483 CJSON_PUBLIC(cJSON *) cJSON_CreateObjectReference(const cJSON *child)
2484 {
2485     cJSON *item = cJSON_New_Item(&global_hooks);
2486     if (item != NULL) {
2487         item->type = cJSON_Object | cJSON_IsReference;
2488         item->child = (cJSON*)cast_away_const(child);
2489     }
2490
2491     return item;
2492 }
2493
2494 CJSON_PUBLIC(cJSON *) cJSON_CreateArrayReference(const cJSON *child) {
2495     cJSON *item = cJSON_New_Item(&global_hooks);
2496     if (item != NULL) {
2497         item->type = cJSON_Array | cJSON_IsReference;
2498         item->child = (cJSON*)cast_away_const(child);
2499     }
2500
2501     return item;
2502 }
2503
2504 CJSON_PUBLIC(cJSON *) cJSON_CreateRaw(const char *raw)
2505 {
2506     cJSON *item = cJSON_New_Item(&global_hooks);
2507     if(item)
2508     {
2509         item->type = cJSON_Raw;
2510         item->valuestring = (char*)cJSON_strdup((const unsigned char*)raw, &global_hooks);
2511         if(!item->valuestring)
2512         {
2513             cJSON_Delete(item);
2514             return NULL;
2515         }
2516     }
2517
2518     return item;
2519 }
2520
2521 CJSON_PUBLIC(cJSON *) cJSON_CreateArray(void)
2522 {
2523     cJSON *item = cJSON_New_Item(&global_hooks);
2524     if(item)
2525     {
2526         item->type=cJSON_Array;
2527     }
2528
2529     return item;
2530 }
2531
2532 CJSON_PUBLIC(cJSON *) cJSON_CreateObject(void)
2533 {
2534     cJSON *item = cJSON_New_Item(&global_hooks);
2535     if (item)
2536     {
2537         item->type = cJSON_Object;
2538     }
2539
2540     return item;
2541 }
2542
2543 /* Create Arrays: */
2544 CJSON_PUBLIC(cJSON *) cJSON_CreateIntArray(const int *numbers, int count)
2545 {
2546     size_t i = 0;
2547     cJSON *n = NULL;
2548     cJSON *p = NULL;
2549     cJSON *a = NULL;
2550
2551     if ((count < 0) || (numbers == NULL))
2552     {
2553         return NULL;
2554     }
2555
2556     a = cJSON_CreateArray();
2557
2558     for(i = 0; a && (i < (size_t)count); i++)
2559     {
2560         n = cJSON_CreateNumber(numbers[i]);
2561         if (!n)
2562         {
2563             cJSON_Delete(a);
2564             return NULL;
2565         }
2566         if(!i)
2567         {
2568             a->child = n;
2569         }
2570         else
2571         {
2572             suffix_object(p, n);
2573         }
2574         p = n;
2575     }
2576
2577     if (a && a->child)
2578       {
2579         a->child->prev = n;
2580       }
2581
2582     return a;
2583 }
2584
2585 CJSON_PUBLIC(cJSON *) cJSON_CreateFloatArray(const float *numbers, int count)
2586 {
2587     size_t i = 0;
2588     cJSON *n = NULL;
2589     cJSON *p = NULL;
2590     cJSON *a = NULL;
2591
2592     if ((count < 0) || (numbers == NULL))
2593     {
2594         return NULL;
2595     }
2596
2597     a = cJSON_CreateArray();
2598
2599     for(i = 0; a && (i < (size_t)count); i++)
2600     {
2601         n = cJSON_CreateNumber((double)numbers[i]);
2602         if(!n)
2603         {
2604             cJSON_Delete(a);
2605             return NULL;
2606         }
2607         if(!i)
2608         {
2609             a->child = n;
2610         }
2611         else
2612         {
2613             suffix_object(p, n);
2614         }
2615         p = n;
2616     }
2617
2618     if (a && a->child)
2619       {
2620         a->child->prev = n;
2621       }
2622
2623     return a;
2624 }
2625
2626 CJSON_PUBLIC(cJSON *) cJSON_CreateDoubleArray(const double *numbers, int count)
2627 {
2628     size_t i = 0;
2629     cJSON *n = NULL;
2630     cJSON *p = NULL;
2631     cJSON *a = NULL;
2632
2633     if ((count < 0) || (numbers == NULL))
2634     {
2635         return NULL;
2636     }
2637
2638     a = cJSON_CreateArray();
2639
2640     for (i = 0; a && (i < (size_t) count); i++)
2641       {
2642         n = cJSON_CreateNumber(numbers[i]);
2643         if(!n)
2644         {
2645             cJSON_Delete(a);
2646             return NULL;
2647         }
2648         if(!i)
2649         {
2650             a->child = n;
2651         }
2652         else
2653         {
2654             suffix_object(p, n);
2655         }
2656         p = n;
2657       }
2658
2659     if (a && a->child)
2660       {
2661         a->child->prev = n;
2662       }
2663
2664     return a;
2665 }
2666
2667 CJSON_PUBLIC(cJSON *) cJSON_CreateStringArray(const char *const *strings, int count)
2668 {
2669     size_t i = 0;
2670     cJSON *n = NULL;
2671     cJSON *p = NULL;
2672     cJSON *a = NULL;
2673
2674     if ((count < 0) || (strings == NULL))
2675     {
2676         return NULL;
2677     }
2678
2679     a = cJSON_CreateArray();
2680
2681     for (i = 0; a && (i < (size_t)count); i++)
2682     {
2683         n = cJSON_CreateString(strings[i]);
2684         if(!n)
2685         {
2686             cJSON_Delete(a);
2687             return NULL;
2688         }
2689         if(!i)
2690         {
2691             a->child = n;
2692         }
2693         else
2694         {
2695             suffix_object(p,n);
2696         }
2697         p = n;
2698     }
2699
2700     if (a && a->child)
2701       {
2702         a->child->prev = n;
2703       }
2704
2705     return a;
2706 }
2707
2708 /* Duplication */
2709 CJSON_PUBLIC(cJSON *) cJSON_Duplicate(const cJSON *item, cJSON_bool recurse)
2710 {
2711     cJSON *newitem = NULL;
2712     cJSON *child = NULL;
2713     cJSON *next = NULL;
2714     cJSON *newchild = NULL;
2715
2716     /* Bail on bad ptr */
2717     if (!item)
2718     {
2719         goto fail;
2720     }
2721     /* Create new item */
2722     newitem = cJSON_New_Item(&global_hooks);
2723     if (!newitem)
2724     {
2725         goto fail;
2726     }
2727     /* Copy over all vars */
2728     newitem->type = item->type & (~cJSON_IsReference);
2729     newitem->valueint = item->valueint;
2730     newitem->valuedouble = item->valuedouble;
2731     if (item->valuestring)
2732     {
2733         newitem->valuestring = (char*)cJSON_strdup((unsigned char*)item->valuestring, &global_hooks);
2734         if (!newitem->valuestring)
2735         {
2736             goto fail;
2737         }
2738     }
2739     if (item->string)
2740     {
2741         newitem->string = (item->type&cJSON_StringIsConst) ? item->string : (char*)cJSON_strdup((unsigned char*)item->string, &global_hooks);
2742         if (!newitem->string)
2743         {
2744             goto fail;
2745         }
2746     }
2747     /* If non-recursive, then we're done! */
2748     if (!recurse)
2749     {
2750         return newitem;
2751     }
2752     /* Walk the ->next chain for the child. */
2753     child = item->child;
2754     while (child != NULL)
2755     {
2756         newchild = cJSON_Duplicate(child, true); /* Duplicate (with recurse) each item in the ->next chain */
2757         if (!newchild)
2758         {
2759             goto fail;
2760         }
2761         if (next != NULL)
2762         {
2763             /* If newitem->child already set, then crosswire ->prev and ->next and move on */
2764             next->next = newchild;
2765             newchild->prev = next;
2766             next = newchild;
2767         }
2768         else
2769         {
2770             /* Set newitem->child and move to it */
2771             newitem->child = newchild;
2772             next = newchild;
2773         }
2774         child = child->next;
2775     }
2776     if (newitem && newitem->child)
2777     {
2778         newitem->child->prev = newchild;
2779     }
2780
2781     return newitem;
2782
2783 fail:
2784     if (newitem != NULL)
2785     {
2786         cJSON_Delete(newitem);
2787     }
2788
2789     return NULL;
2790 }
2791
2792 static void skip_oneline_comment(char **input)
2793 {
2794     *input += static_strlen("//");
2795
2796     for (; (*input)[0] != '\0'; ++(*input))
2797     {
2798         if ((*input)[0] == '\n') {
2799             *input += static_strlen("\n");
2800             return;
2801         }
2802     }
2803 }
2804
2805 static void skip_multiline_comment(char **input)
2806 {
2807     *input += static_strlen("/*");
2808
2809     for (; (*input)[0] != '\0'; ++(*input))
2810     {
2811         if (((*input)[0] == '*') && ((*input)[1] == '/'))
2812         {
2813             *input += static_strlen("*/");
2814             return;
2815         }
2816     }
2817 }
2818
2819 static void minify_string(char **input, char **output) {
2820     (*output)[0] = (*input)[0];
2821     *input += static_strlen("\"");
2822     *output += static_strlen("\"");
2823
2824
2825     for (; (*input)[0] != '\0'; (void)++(*input), ++(*output)) {
2826         (*output)[0] = (*input)[0];
2827
2828         if ((*input)[0] == '\"') {
2829             (*output)[0] = '\"';
2830             *input += static_strlen("\"");
2831             *output += static_strlen("\"");
2832             return;
2833         } else if (((*input)[0] == '\\') && ((*input)[1] == '\"')) {
2834             (*output)[1] = (*input)[1];
2835             *input += static_strlen("\"");
2836             *output += static_strlen("\"");
2837         }
2838     }
2839 }
2840
2841 CJSON_PUBLIC(void) cJSON_Minify(char *json)
2842 {
2843     char *into = json;
2844
2845     if (json == NULL)
2846     {
2847         return;
2848     }
2849
2850     while (json[0] != '\0')
2851     {
2852         switch (json[0])
2853         {
2854             case ' ':
2855             case '\t':
2856             case '\r':
2857             case '\n':
2858                 json++;
2859                 break;
2860
2861             case '/':
2862                 if (json[1] == '/')
2863                 {
2864                     skip_oneline_comment(&json);
2865                 }
2866                 else if (json[1] == '*')
2867                 {
2868                     skip_multiline_comment(&json);
2869                 } else {
2870                     json++;
2871                 }
2872                 break;
2873
2874             case '\"':
2875                 minify_string(&json, (char**)&into);
2876                 break;
2877
2878             default:
2879                 into[0] = json[0];
2880                 json++;
2881                 into++;
2882         }
2883     }
2884
2885     /* and null-terminate. */
2886     *into = '\0';
2887 }
2888
2889 CJSON_PUBLIC(cJSON_bool) cJSON_IsInvalid(const cJSON * const item)
2890 {
2891     if (item == NULL)
2892     {
2893         return false;
2894     }
2895
2896     return (item->type & 0xFF) == cJSON_Invalid;
2897 }
2898
2899 CJSON_PUBLIC(cJSON_bool) cJSON_IsFalse(const cJSON * const item)
2900 {
2901     if (item == NULL)
2902     {
2903         return false;
2904     }
2905
2906     return (item->type & 0xFF) == cJSON_False;
2907 }
2908
2909 CJSON_PUBLIC(cJSON_bool) cJSON_IsTrue(const cJSON * const item)
2910 {
2911     if (item == NULL)
2912     {
2913         return false;
2914     }
2915
2916     return (item->type & 0xff) == cJSON_True;
2917 }
2918
2919
2920 CJSON_PUBLIC(cJSON_bool) cJSON_IsBool(const cJSON * const item)
2921 {
2922     if (item == NULL)
2923     {
2924         return false;
2925     }
2926
2927     return (item->type & (cJSON_True | cJSON_False)) != 0;
2928 }
2929 CJSON_PUBLIC(cJSON_bool) cJSON_IsNull(const cJSON * const item)
2930 {
2931     if (item == NULL)
2932     {
2933         return false;
2934     }
2935
2936     return (item->type & 0xFF) == cJSON_NULL;
2937 }
2938
2939 CJSON_PUBLIC(cJSON_bool) cJSON_IsNumber(const cJSON * const item)
2940 {
2941     if (item == NULL)
2942     {
2943         return false;
2944     }
2945
2946     return (item->type & 0xFF) == cJSON_Number;
2947 }
2948
2949 CJSON_PUBLIC(cJSON_bool) cJSON_IsString(const cJSON * const item)
2950 {
2951     if (item == NULL)
2952     {
2953         return false;
2954     }
2955
2956     return (item->type & 0xFF) == cJSON_String;
2957 }
2958
2959 CJSON_PUBLIC(cJSON_bool) cJSON_IsArray(const cJSON * const item)
2960 {
2961     if (item == NULL)
2962     {
2963         return false;
2964     }
2965
2966     return (item->type & 0xFF) == cJSON_Array;
2967 }
2968
2969 CJSON_PUBLIC(cJSON_bool) cJSON_IsObject(const cJSON * const item)
2970 {
2971     if (item == NULL)
2972     {
2973         return false;
2974     }
2975
2976     return (item->type & 0xFF) == cJSON_Object;
2977 }
2978
2979 CJSON_PUBLIC(cJSON_bool) cJSON_IsRaw(const cJSON * const item)
2980 {
2981     if (item == NULL)
2982     {
2983         return false;
2984     }
2985
2986     return (item->type & 0xFF) == cJSON_Raw;
2987 }
2988
2989 CJSON_PUBLIC(cJSON_bool) cJSON_Compare(const cJSON * const a, const cJSON * const b, const cJSON_bool case_sensitive)
2990 {
2991     if ((a == NULL) || (b == NULL) || ((a->type & 0xFF) != (b->type & 0xFF)) || cJSON_IsInvalid(a))
2992     {
2993         return false;
2994     }
2995
2996     /* check if type is valid */
2997     switch (a->type & 0xFF)
2998     {
2999         case cJSON_False:
3000         case cJSON_True:
3001         case cJSON_NULL:
3002         case cJSON_Number:
3003         case cJSON_String:
3004         case cJSON_Raw:
3005         case cJSON_Array:
3006         case cJSON_Object:
3007             break;
3008
3009         default:
3010             return false;
3011     }
3012
3013     /* identical objects are equal */
3014     if (a == b)
3015     {
3016         return true;
3017     }
3018
3019     switch (a->type & 0xFF)
3020     {
3021         /* in these cases and equal type is enough */
3022         case cJSON_False:
3023         case cJSON_True:
3024         case cJSON_NULL:
3025             return true;
3026
3027         case cJSON_Number:
3028             if (compare_double(a->valuedouble, b->valuedouble))
3029             {
3030                 return true;
3031             }
3032             return false;
3033
3034         case cJSON_String:
3035         case cJSON_Raw:
3036             if ((a->valuestring == NULL) || (b->valuestring == NULL))
3037             {
3038                 return false;
3039             }
3040             if (strcmp(a->valuestring, b->valuestring) == 0)
3041             {
3042                 return true;
3043             }
3044
3045             return false;
3046
3047         case cJSON_Array:
3048         {
3049             cJSON *a_element = a->child;
3050             cJSON *b_element = b->child;
3051
3052             for (; (a_element != NULL) && (b_element != NULL);)
3053             {
3054                 if (!cJSON_Compare(a_element, b_element, case_sensitive))
3055                 {
3056                     return false;
3057                 }
3058
3059                 a_element = a_element->next;
3060                 b_element = b_element->next;
3061             }
3062
3063             /* one of the arrays is longer than the other */
3064             if (a_element != b_element) {
3065                 return false;
3066             }
3067
3068             return true;
3069         }
3070
3071         case cJSON_Object:
3072         {
3073             cJSON *a_element = NULL;
3074             cJSON *b_element = NULL;
3075             cJSON_ArrayForEach(a_element, a)
3076             {
3077                 /* TODO This has O(n^2) runtime, which is horrible! */
3078                 b_element = get_object_item(b, a_element->string, case_sensitive);
3079                 if (b_element == NULL)
3080                 {
3081                     return false;
3082                 }
3083
3084                 if (!cJSON_Compare(a_element, b_element, case_sensitive))
3085                 {
3086                     return false;
3087                 }
3088             }
3089
3090             /* doing this twice, once on a and b to prevent true comparison if a subset of b
3091              * TODO: Do this the proper way, this is just a fix for now */
3092             cJSON_ArrayForEach(b_element, b)
3093             {
3094                 a_element = get_object_item(a, b_element->string, case_sensitive);
3095                 if (a_element == NULL)
3096                 {
3097                     return false;
3098                 }
3099
3100                 if (!cJSON_Compare(b_element, a_element, case_sensitive))
3101                 {
3102                     return false;
3103                 }
3104             }
3105
3106             return true;
3107         }
3108
3109         default:
3110             return false;
3111     }
3112 }
3113
3114 CJSON_PUBLIC(void *) cJSON_malloc(size_t size)
3115 {
3116     return global_hooks.allocate(size);
3117 }
3118
3119 CJSON_PUBLIC(void) cJSON_free(void *object)
3120 {
3121     global_hooks.deallocate(object);
3122 }
3123
3124 CJSON_PUBLIC(void *) cJSON_realloc(void *object, size_t new_size, size_t old_size)
3125 {
3126     return global_hooks.reallocate(object, new_size, old_size);
3127 }