Sat, 06 Dec 2025 16:30:11 +0100
replace JSON object member array with kv-list - resolves #762
| CHANGELOG | file | annotate | diff | comparison | revisions | |
| docs/Writerside/topics/about.md | file | annotate | diff | comparison | revisions | |
| docs/Writerside/topics/json.h.md | file | annotate | diff | comparison | revisions | |
| src/cx/json.h | file | annotate | diff | comparison | revisions | |
| src/json.c | file | annotate | diff | comparison | revisions | |
| tests/test_json.c | file | annotate | diff | comparison | revisions |
--- a/CHANGELOG Sat Dec 06 16:22:19 2025 +0100 +++ b/CHANGELOG Sat Dec 06 16:30:11 2025 +0100 @@ -4,6 +4,8 @@ * adds cx_system_page_size() to allocator.h * changes cxBufferReserve() to allow reducing the capacity * changes the members of CxJson and CxJsonValue + * changes the return value of cxJsonObjIter() to CxMapIterator + * removes the sort_members feature from CxJsonWriter * fixes critical memory leak when using cxMapFree() on a kv-list that is using destructors * fixes that overwriting items with cxMapPut() in a kv-list did not work * fixes that cxReallocate(), cxReallocateArray(), cx_reallocate(), and cx_reallocatearray()
--- a/docs/Writerside/topics/about.md Sat Dec 06 16:22:19 2025 +0100 +++ b/docs/Writerside/topics/about.md Sat Dec 06 16:30:11 2025 +0100 @@ -31,6 +31,8 @@ * adds cx_system_page_size() to allocator.h * changes cxBufferReserve() to allow reducing the capacity * changes the members of CxJson and CxJsonValue +* changes the return value of cxJsonObjIter() to CxMapIterator +* removes the sort_members feature from CxJsonWriter * fixes critical memory leak when using cxMapFree() on a kv-list that is using destructors * fixes that overwriting items with cxMapPut() in a kv-list did not work * fixes that cxReallocate(), cxReallocateArray(), cx_reallocate(), and cx_reallocatearray()
--- a/docs/Writerside/topics/json.h.md Sat Dec 06 16:22:19 2025 +0100 +++ b/docs/Writerside/topics/json.h.md Sat Dec 06 16:30:11 2025 +0100 @@ -321,7 +321,6 @@ typedef struct cx_json_writer_s { bool pretty; - bool sort_members; uint8_t frac_max_digits; bool indent_space; uint8_t indent; @@ -346,7 +345,6 @@ | Setting | Compact Default | Pretty Default | Description | |-------------------|-----------------|----------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------| | `pretty` | `false` | `true` | If true, the JSON will be formatted with line breaks and tabs or spaces. If false, output is as compact as possible without extra characters. | -| `sort_members` | `true` | `true` | If false members are written in the order in which they were added. If true, they are sorted lexicographically. | | `frac_max_digits` | 6 | 6 | The maximum number of fractional digits in a number value. | | `indent_space` | ignored | depends on `use_spaces` argument | If true, use spaces for indentation, otherwise use tabs. | | `indent` | ignored | 4 | If `indent_space` is `true`, this is the number of spaces per tab. Ignored otherwise. |
--- a/src/cx/json.h Sat Dec 06 16:22:19 2025 +0100 +++ b/src/cx/json.h Sat Dec 06 16:30:11 2025 +0100 @@ -41,6 +41,7 @@ #include "string.h" #include "buffer.h" #include "array_list.h" +#include "map.h" #include <string.h> @@ -188,9 +189,10 @@ */ typedef struct cx_json_array_s CxJsonArray; /** - * Type alias for the JSON object struct. + * Type alias for the map representing a JSON object. + * The map contains pointers of type @c CxJsonValue. */ -typedef struct cx_json_object_s CxJsonObject; +typedef CxMap* CxJsonObject; /** * Type alias for a JSON string. */ @@ -209,11 +211,6 @@ typedef enum cx_json_literal CxJsonLiteral; /** - * Type alias for a key/value pair in a JSON object. - */ -typedef struct cx_json_obj_value_s CxJsonObjValue; - -/** * JSON array structure. */ struct cx_json_array_s { @@ -224,34 +221,6 @@ }; /** - * JSON object structure. - */ -struct cx_json_object_s { - /** - * The key/value entries. - */ - CX_ARRAY_DECLARE(CxJsonObjValue, values); - /** - * The original indices to reconstruct the order in which the members were added. - */ - size_t *indices; -}; - -/** - * Structure for a key/value entry in a JSON object. - */ -struct cx_json_obj_value_s { - /** - * The key (or name in JSON terminology) of the value. - */ - cxmutstr name; - /** - * The value. - */ - CxJsonValue *value; -}; - -/** * Structure for a JSON value. */ struct cx_json_value_s { @@ -349,11 +318,11 @@ CxJsonValue *parsed; /** - * A pointer to an intermediate state of a currently parsed object member. + * The name of a not yet completely parsed object member. * * Never access this value manually. */ - CxJsonObjValue uncompleted_member; + cxmutstr uncompleted_member_name; /** * State stack. @@ -439,10 +408,6 @@ */ bool pretty; /** - * Set false to output the members in the order in which they were added. - */ - bool sort_members; - /** * The maximum number of fractional digits in a number value. * The default value is 6 and values larger than 15 are reduced to 15. * Note that the actual number of digits may be lower, depending on the concrete number. @@ -1277,14 +1242,14 @@ */ cx_attr_nonnull CX_INLINE size_t cxJsonObjSize(const CxJsonValue *value) { - return value->object.values_size; + return cxCollectionSize(value->object); } /** - * Returns an iterator over the JSON object members. + * Returns a map iterator over the JSON object members. * - * The iterator yields values of type @c CxJsonObjValue* which - * contain the name and value of the member. + * The iterator yields values of type @c CxMapEntry* which + * contain the name and the @c CxJsonObjValue* of the member. * * If the @p value is not a JSON object, the behavior is undefined. * @@ -1293,7 +1258,7 @@ * @see cxJsonIsObject() */ cx_attr_nonnull cx_attr_nodiscard -CX_EXPORT CxIterator cxJsonObjIter(const CxJsonValue *value); +CX_EXPORT CxMapIterator cxJsonObjIter(const CxJsonValue *value); /** * Internal function, do not use.
--- a/src/json.c Sat Dec 06 16:22:19 2025 +0100 +++ b/src/json.c Sat Dec 06 16:30:11 2025 +0100 @@ -27,6 +27,7 @@ */ #include "cx/json.h" +#include "cx/kv_list.h" #include <string.h> #include <assert.h> @@ -41,87 +42,6 @@ static CxJsonValue cx_json_value_nothing = {.type = CX_JSON_NOTHING}; -static int json_cmp_objvalue(const void *l, const void *r) { - const CxJsonObjValue *left = l; - const CxJsonObjValue *right = r; - return cx_strcmp(cx_strcast(left->name), cx_strcast(right->name)); -} - -static size_t json_find_objvalue(const CxJsonValue *obj, cxstring name) { - assert(obj->type == CX_JSON_OBJECT); - CxJsonObjValue kv_dummy; - kv_dummy.name = cx_mutstrn((char*) name.ptr, name.length); - return cx_array_binary_search( - obj->object.values, - obj->object.values_size, - sizeof(CxJsonObjValue), - &kv_dummy, - json_cmp_objvalue - ); -} - -static int json_add_objvalue(CxJsonValue *objv, CxJsonObjValue member) { - assert(objv->type == CX_JSON_OBJECT); - const CxAllocator * const al = objv->allocator; - CxJsonObject *obj = &(objv->object); - - // determine the index where we need to insert the new member - size_t index = cx_array_binary_search_sup( - obj->values, - obj->values_size, - sizeof(CxJsonObjValue), - &member, json_cmp_objvalue - ); - - // is the name already present? - if (index < obj->values_size && 0 == json_cmp_objvalue(&member, &obj->values[index])) { - // free the original value - cx_strfree_a(al, &obj->values[index].name); - cxJsonValueFree(obj->values[index].value); - // replace the item - obj->values[index] = member; - - // nothing more to do - return 0; - } - - // determine the old capacity and reserve for one more element - CxArrayReallocator arealloc = cx_array_reallocator(al, NULL); - size_t oldcap = obj->values_capacity; - if (cx_array_simple_reserve_a(&arealloc, obj->values, 1)) return 1; - - // check the new capacity, if we need to realloc the index array - size_t newcap = obj->values_capacity; - if (newcap > oldcap) { - if (cxReallocateArray(al, &obj->indices, newcap, sizeof(size_t))) { - return 1; // LCOV_EXCL_LINE - } - } - - // check if append or insert - if (index < obj->values_size) { - // move the other elements - memmove( - &obj->values[index+1], - &obj->values[index], - (obj->values_size - index) * sizeof(CxJsonObjValue) - ); - // increase indices for the moved elements - for (size_t i = 0; i < obj->values_size ; i++) { - if (obj->indices[i] >= index) { - obj->indices[i]++; - } - } - } - - // insert the element and set the index - obj->values[index] = member; - obj->indices[obj->values_size] = index; - obj->values_size++; - - return 0; -} - static void token_destroy(CxJsonToken *token) { if (token->allocated) { cx_strfree(&token->content); @@ -473,7 +393,7 @@ return result; } -static cxmutstr escape_string(cxmutstr str, bool escape_slash) { +static cxmutstr escape_string(cxstring str, bool escape_slash) { // note: this function produces the string without enclosing quotes // the reason is that we don't want to allocate memory just for that CxBuffer buf = {0}; @@ -519,11 +439,27 @@ cxBufferPut(&buf, c); } } - if (!all_printable) { - str = cx_mutstrn(buf.space, buf.size); + cxmutstr ret; + if (all_printable) { + // don't copy the string when we don't need to escape anything + ret = cx_mutstrn((char*)str.ptr, str.length); + } else { + ret = cx_mutstrn(buf.space, buf.size); } cxBufferDestroy(&buf); - return str; + return ret; +} + +static CxJsonObject json_create_object_map(const CxAllocator *allocator) { + // TODO: we might want to add a comparator that is sorting the elements by their key + CxMap *map = cxKvListCreateAsMap(allocator, NULL, CX_STORE_POINTERS); + if (map == NULL) return NULL; // LCOV_EXCL_LINE + cxDefineDestructor(map, cxJsonValueFree); + return map; +} + +static void json_free_object_map(CxJsonObject obj) { + cxMapFree(obj); } static CxJsonValue* json_create_value(CxJson *json, CxJsonValueType type) { @@ -537,11 +473,8 @@ cx_array_initialize_a(json->allocator, v->array.array, 16); if (v->array.array == NULL) goto create_json_value_exit_error; // LCOV_EXCL_LINE } else if (type == CX_JSON_OBJECT) { - cx_array_initialize_a(json->allocator, v->object.values, 16); - v->object.indices = cxCalloc(json->allocator, 16, sizeof(size_t)); - if (v->object.values == NULL || - v->object.indices == NULL) - goto create_json_value_exit_error; // LCOV_EXCL_LINE + v->object = json_create_object_map(json->allocator); + if (v->object == NULL) goto create_json_value_exit_error; // LCOV_EXCL_LINE } // add the new value to a possible parent @@ -555,12 +488,12 @@ } } else if (parent->type == CX_JSON_OBJECT) { // the member was already created after parsing the name - assert(json->uncompleted_member.name.ptr != NULL); - json->uncompleted_member.value = v; - if (json_add_objvalue(parent, json->uncompleted_member)) { + // store the pointer of the uncompleted value in the map + assert(json->uncompleted_member_name.ptr != NULL); + if (cxMapPut(parent->object, json->uncompleted_member_name, v)) { goto create_json_value_exit_error; // LCOV_EXCL_LINE } - json->uncompleted_member.name = (cxmutstr) {NULL, 0}; + cx_strfree_a(json->allocator, &json->uncompleted_member_name); } else { assert(false); // LCOV_EXCL_LINE } @@ -624,10 +557,7 @@ } cxJsonValueFree(json->parsed); json->parsed = NULL; - if (json->uncompleted_member.name.ptr != NULL) { - cx_strfree_a(json->allocator, &json->uncompleted_member.name); - json->uncompleted_member = (CxJsonObjValue){{NULL, 0}, NULL}; - } + cx_strfree_a(json->allocator, &json->uncompleted_member_name); } void cxJsonReset(CxJson *json) { @@ -786,8 +716,8 @@ if (name.ptr == NULL) { return_rec(CX_JSON_VALUE_ALLOC_FAILED); // LCOV_EXCL_LINE } - assert(json->uncompleted_member.name.ptr == NULL); - json->uncompleted_member.name = name; + assert(json->uncompleted_member_name.ptr == NULL); + json->uncompleted_member_name = name; assert(json->vbuf_size > 0); // next state @@ -864,13 +794,7 @@ if (value == NULL || value->type == CX_JSON_NOTHING) return; switch (value->type) { case CX_JSON_OBJECT: { - CxJsonObject obj = value->object; - for (size_t i = 0; i < obj.values_size; i++) { - cxJsonValueFree(obj.values[i].value); - cx_strfree_a(value->allocator, &obj.values[i].name); - } - cxFree(value->allocator, obj.values); - cxFree(value->allocator, obj.indices); + json_free_object_map(value->object); break; } case CX_JSON_ARRAY: { @@ -898,15 +822,8 @@ if (v == NULL) return NULL; v->allocator = allocator; v->type = CX_JSON_OBJECT; - cx_array_initialize_a(allocator, v->object.values, 16); - if (v->object.values == NULL) { // LCOV_EXCL_START - cxFree(allocator, v); - return NULL; - // LCOV_EXCL_STOP - } - v->object.indices = cxCalloc(allocator, 16, sizeof(size_t)); - if (v->object.indices == NULL) { // LCOV_EXCL_START - cxFree(allocator, v->object.values); + v->object = json_create_object_map(allocator); + if (v->object == NULL) { // LCOV_EXCL_START cxFree(allocator, v); return NULL; // LCOV_EXCL_STOP @@ -1049,17 +966,7 @@ } int cx_json_obj_put(CxJsonValue* obj, cxstring name, CxJsonValue* child) { - cxmutstr k = cx_strdup_a(obj->allocator, name); - if (k.ptr == NULL) return -1; - CxJsonObjValue kv = {k, child}; - if (json_add_objvalue(obj, kv)) { - // LCOV_EXCL_START - cx_strfree_a(obj->allocator, &k); - return 1; - // LCOV_EXCL_STOP - } else { - return 0; - } + return cxMapPut(obj->object, name, child); } CxJsonValue* cx_json_obj_put_obj(CxJsonValue* obj, cxstring name) { @@ -1161,42 +1068,28 @@ ); } -CxIterator cxJsonObjIter(const CxJsonValue *value) { - return cxIterator( - value->object.values, - sizeof(CxJsonObjValue), - value->object.values_size, - true // TODO: objects do not always need to keep order - ); +CxMapIterator cxJsonObjIter(const CxJsonValue *value) { + return cxMapIterator(value->object); } CxJsonValue *cx_json_obj_get(const CxJsonValue *value, cxstring name) { - size_t index = json_find_objvalue(value, name); - if (index >= value->object.values_size) { + CxJsonValue *v = cxMapGet(value->object, name); + if (v == NULL) { return &cx_json_value_nothing; } else { - return value->object.values[index].value; + return v; } } CxJsonValue *cx_json_obj_remove(CxJsonValue *value, cxstring name) { - size_t index = json_find_objvalue(value, name); - if (index >= value->object.values_size) { - return NULL; - } else { - CxJsonObjValue kv = value->object.values[index]; - cx_strfree_a(value->allocator, &kv.name); - // TODO: replace with cx_array_remove() / cx_array_remove_fast() - value->object.values_size--; - memmove(value->object.values + index, value->object.values + index + 1, (value->object.values_size - index) * sizeof(CxJsonObjValue)); - return kv.value; - } + CxJsonValue *v = NULL; + cxMapRemoveAndGet(value->object, name, &v); + return v; } CxJsonWriter cxJsonWriterCompact(void) { return (CxJsonWriter) { false, - true, 6, false, 4, @@ -1207,7 +1100,6 @@ CxJsonWriter cxJsonWriterPretty(bool use_spaces) { return (CxJsonWriter) { true, - true, 6, use_spaces, 4, @@ -1272,14 +1164,8 @@ expected++; } depth++; - size_t elem_count = value->object.values_size; - for (size_t look_idx = 0; look_idx < elem_count; look_idx++) { - // get the member either via index array or directly - size_t elem_idx = settings->sort_members - ? look_idx - : value->object.indices[look_idx]; - CxJsonObjValue *member = &value->object.values[elem_idx]; - + CxMapIterator member_iter = cxJsonObjIter(value); + cx_foreach(const CxMapEntry *, member, member_iter) { // possible indentation if (settings->pretty) { if (cx_json_writer_indent(target, wfunc, settings, depth)) { @@ -1289,26 +1175,29 @@ // the name actual += wfunc("\"", 1, 1, target); - cxmutstr name = escape_string(member->name, settings->escape_slash); + cxstring key = cx_strn(member->key->data, member->key->len); + cxmutstr name = escape_string(key, settings->escape_slash); actual += wfunc(name.ptr, 1, name.length, target); - if (name.ptr != member->name.ptr) { + if (name.ptr != key.ptr) { cx_strfree(&name); } actual += wfunc("\"", 1, 1, target); const char *obj_name_sep = ": "; if (settings->pretty) { actual += wfunc(obj_name_sep, 1, 2, target); - expected += 4 + member->name.length; + // FIXME: is this really correct? should be the (escaped) name.length + expected += 4 + key.length; } else { actual += wfunc(obj_name_sep, 1, 1, target); - expected += 3 + member->name.length; + // FIXME: is this really correct? should be the (escaped) name.length + expected += 3 + key.length; } // the value if (cx_json_write_rec(target, member->value, wfunc, settings, depth)) return 1; // end of object-value - if (look_idx < elem_count - 1) { + if (member_iter.index < member_iter.elem_count - 1) { const char *obj_value_sep = ",\n"; if (settings->pretty) { actual += wfunc(obj_value_sep, 1, 2, target); @@ -1361,7 +1250,8 @@ } case CX_JSON_STRING: { actual += wfunc("\"", 1, 1, target); - cxmutstr str = escape_string(value->string, settings->escape_slash); + cxmutstr str = escape_string(cx_strcast(value->string), + settings->escape_slash); actual += wfunc(str.ptr, 1, str.length, target); if (str.ptr != value->string.ptr) { cx_strfree(&str);
--- a/tests/test_json.c Sat Dec 06 16:22:19 2025 +0100 +++ b/tests/test_json.c Sat Dec 06 16:30:11 2025 +0100 @@ -1116,9 +1116,9 @@ cxJsonObjPutInteger(obj, "test2", 0); // verify the values - CxIterator iter = cxJsonObjIter(obj); + CxMapIterator iter = cxJsonObjIter(obj); bool found[5] = {0}; - cx_foreach(CxJsonObjValue *, ov, iter) { + cx_foreach(CxMapEntry *, ov, iter) { CxJsonValue *v = ov->value; CX_TEST_ASSERT(cxJsonIsInteger(v)); int64_t i = cxJsonAsInteger(v); @@ -1192,19 +1192,19 @@ cxstring expected = cx_str( "{\"bool\":false," "\"int\":47," +"\"strings\":[\"hello\",\"world\"]," "\"nested\":{" -"\"floats\":[3.1415,47.11,8.15]," -"\"ints\":[4,8,15,[16,23],42]," -"\"literals\":[true,null,false]," "\"objects\":[{" "\"name1\":1," "\"name2\":3" "},{" -"\"name1\":3," -"\"name2\":7" -"}]" -"}," -"\"strings\":[\"hello\",\"world\"]" +"\"name2\":7," +"\"name1\":3" +"}]," +"\"floats\":[3.1415,47.11,8.15]," +"\"literals\":[true,null,false]," +"\"ints\":[4,8,15,[16,23],42]" +"}" "}" ); @@ -1226,69 +1226,6 @@ "{\n" " \"bool\": false,\n" " \"int\": 47,\n" -" \"nested\": {\n" -" \"floats\": [3.1415, 47.11, 8.15],\n" -" \"ints\": [4, 8, 15, [16, 23], 42],\n" -" \"literals\": [true, null, false],\n" -" \"objects\": [{\n" -" \"name1\": 1,\n" -" \"name2\": 3\n" -" }, {\n" -" \"name1\": 3,\n" -" \"name2\": 7\n" -" }]\n" -" },\n" -" \"strings\": [\"hello\", \"world\"]\n" -"}" - ); - - CxJsonWriter writer = cxJsonWriterPretty(true); - CX_TEST_CALL_SUBROUTINE(test_json_write_sub, allocator, expected, &writer); - CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); - } - cx_testing_allocator_destroy(&talloc); -} - -CX_TEST(test_json_write_pretty_default_tabs) { - CxTestingAllocator talloc; - cx_testing_allocator_init(&talloc); - CxAllocator *allocator = &talloc.base; - CX_TEST_DO { - cxstring expected = cx_str( -"{\n" -"\t\"bool\": false,\n" -"\t\"int\": 47,\n" -"\t\"nested\": {\n" -"\t\t\"floats\": [3.1415, 47.11, 8.15],\n" -"\t\t\"ints\": [4, 8, 15, [16, 23], 42],\n" -"\t\t\"literals\": [true, null, false],\n" -"\t\t\"objects\": [{\n" -"\t\t\t\"name1\": 1,\n" -"\t\t\t\"name2\": 3\n" -"\t\t}, {\n" -"\t\t\t\"name1\": 3,\n" -"\t\t\t\"name2\": 7\n" -"\t\t}]\n" -"\t},\n" -"\t\"strings\": [\"hello\", \"world\"]\n" -"}" - ); - CxJsonWriter writer = cxJsonWriterPretty(false); - CX_TEST_CALL_SUBROUTINE(test_json_write_sub, allocator, expected, &writer); - CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); - } - cx_testing_allocator_destroy(&talloc); -} - -CX_TEST(test_json_write_pretty_preserve_order) { - CxTestingAllocator talloc; - cx_testing_allocator_init(&talloc); - CxAllocator *allocator = &talloc.base; - CX_TEST_DO { - cxstring expected = cx_str( -"{\n" -" \"bool\": false,\n" -" \"int\": 47,\n" " \"strings\": [\"hello\", \"world\"],\n" " \"nested\": {\n" " \"objects\": [{\n" @@ -1306,7 +1243,37 @@ ); CxJsonWriter writer = cxJsonWriterPretty(true); - writer.sort_members = false; + CX_TEST_CALL_SUBROUTINE(test_json_write_sub, allocator, expected, &writer); + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); + } + cx_testing_allocator_destroy(&talloc); +} + +CX_TEST(test_json_write_pretty_default_tabs) { + CxTestingAllocator talloc; + cx_testing_allocator_init(&talloc); + CxAllocator *allocator = &talloc.base; + CX_TEST_DO { + cxstring expected = cx_str( +"{\n" +"\t\"bool\": false,\n" +"\t\"int\": 47,\n" +"\t\"strings\": [\"hello\", \"world\"],\n" +"\t\"nested\": {\n" +"\t\t\"objects\": [{\n" +"\t\t\t\"name1\": 1,\n" +"\t\t\t\"name2\": 3\n" +"\t\t}, {\n" +"\t\t\t\"name2\": 7,\n" +"\t\t\t\"name1\": 3\n" +"\t\t}],\n" +"\t\t\"floats\": [3.1415, 47.11, 8.15],\n" +"\t\t\"literals\": [true, null, false],\n" +"\t\t\"ints\": [4, 8, 15, [16, 23], 42]\n" +"\t}\n" +"}" + ); + CxJsonWriter writer = cxJsonWriterPretty(false); CX_TEST_CALL_SUBROUTINE(test_json_write_sub, allocator, expected, &writer); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } @@ -1521,7 +1488,6 @@ cx_test_register(suite, test_json_write_default_format); cx_test_register(suite, test_json_write_pretty_default_spaces); cx_test_register(suite, test_json_write_pretty_default_tabs); - cx_test_register(suite, test_json_write_pretty_preserve_order); cx_test_register(suite, test_json_write_pretty_deep_nesting); cx_test_register(suite, test_json_write_frac_max_digits); cx_test_register(suite, test_json_write_string_escape);