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