Lite³
A JSON-Compatible Zero-Copy Serialization Format
Loading...
Searching...
No Matches
Arrays

Table of Contents

Introduction

The previous guide was about nesting. This guide will be cover arrays.

Basics first: arrays are ordered, while objects are unordered. Arrays also don't have keys, but indexes.

The performance characteristics of arrays in Lite³ are somewhat unusual. The following operations:

  1. appending an element
  2. getting element by index
  3. setting element by index (overwrite)

In Lite³ all have logarithmic time complexity of O(log N). The underlying datastructure is a B-tree where indexes are used as keys.

Typically, arrays are implemented as a contiguous set of elements. For fixed-sized elements, this provides constant time access O(1) for individual elements. However, JSON-like data often contains variable sized elements like strings. Also, appending is also not always possible due to neighbouring data and may require relocating elements. As a result, the above operations could all degrade to O(N) for 'naive arrays'.

Since Lite³ is mutable 'by design', O(N) time for single-element operations is not permittable. The O(log N) B-tree guarantee enables efficient mutation of serialized data, such that latency remains predictable even in a realtime setting. The implementation for objects and arrays is also shared inside the source code, both using the same B-tree structure. Despite this implementation, the user API is no different to what programmers are used to for arrays.

Example Code

This guide is based on an example inside the Lite³ repository found in examples/context_api/05-arrays.c:

1/*
2 Lite³: A JSON-Compatible Zero-Copy Serialization Format
3
4 Copyright © 2025 Elias de Jong <elias@fastserial.com>
5
6 Permission is hereby granted, free of charge, to any person obtaining a copy
7 of this software and associated documentation files (the "Software"), to deal
8 in the Software without restriction, including without limitation the rights
9 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 copies of the Software, and to permit persons to whom the Software is
11 furnished to do so, subject to the following conditions:
12
13 The above copyright notice and this permission notice shall be included in all
14 copies or substantial portions of the Software.
15
16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 SOFTWARE.
23
24 __ __________________ ____
25 _ ___ ___/ /___(_)_/ /_______|_ /
26 _ _____/ / __/ /_ __/ _ \_/_ <
27 ___ __/ /___/ / / /_ / __/____/
28 /_____/_/ \__/ \___/
29*/
30#include <stdio.h>
31#include <string.h>
32
33#include "lite3_context_api.h"
34
35
36int main() {
37 lite3_ctx *ctx = lite3_ctx_create();
38 if (!ctx) {
39 perror("Failed to create lite3_ctx *ctx");
40 return 1;
41 }
42
43 // Build message
44 if (lite3_ctx_init_arr(ctx) < 0
45 || lite3_ctx_arr_append_str(ctx, 0, "zebra") < 0
46 || lite3_ctx_arr_append_str(ctx, 0, "giraffe") < 0
47 || lite3_ctx_arr_append_str(ctx, 0, "buffalo") < 0
48 || lite3_ctx_arr_append_str(ctx, 0, "lion") < 0
49 || lite3_ctx_arr_append_str(ctx, 0, "rhino") < 0
50 || lite3_ctx_arr_append_str(ctx, 0, "elephant") < 0) {
51 perror("Failed to build message");
52 return 1;
53 }
54 printf("buflen: %zu\n", ctx->buflen);
55 if (lite3_ctx_json_print(ctx, 0) < 0) { // Print Lite³ as JSON
56 perror("Failed to print JSON");
57 return 1;
58 }
59
60 lite3_str element_2;
61 if (lite3_ctx_arr_get_str(ctx, 0, 2, &element_2) < 0) {
62 perror("Failed to get element");
63 return 1;
64 }
65 printf("Element at index 2: %s\n", LITE3_STR(ctx->buf, element_2));
66
67 uint32_t element_count;
68 if (lite3_ctx_count(ctx, 0, &element_count) < 0) {
69 perror("Failed to get element count");
70 return 1;
71 }
72 printf("Element count: %u\n", element_count);
73
74 lite3_str last_element;
75 if (lite3_ctx_arr_get_str(ctx, 0, element_count - 1, &last_element) < 0) {
76 perror("Failed to get element");
77 return 1;
78 }
79 printf("Last element: %s\n", LITE3_STR(ctx->buf, last_element));
80
81 printf("\nOverwriting index 2 with \"gnu\"\n");
82 if (lite3_ctx_arr_set_str(ctx, 0, 2, "gnu") < 0) {
83 perror("Failed to set element");
84 return 1;
85 }
86 printf("buflen: %zu\n", ctx->buflen);
87 if (lite3_ctx_json_print(ctx, 0) < 0) {
88 perror("Failed to print JSON");
89 return 1;
90 }
91
92 printf("\nOverwriting index 3 with \"springbok\"\n");
93 if (lite3_ctx_arr_set_str(ctx, 0, 3, "springbok") < 0) {
94 perror("Failed to set element");
95 return 1;
96 }
97 printf("buflen: %zu\n", ctx->buflen);
98 if (lite3_ctx_json_print(ctx, 0) < 0) {
99 perror("Failed to print JSON");
100 return 1;
101 }
102
103 lite3_ctx_destroy(ctx);
104 return 0;
105}
lite3_ctx_arr_append_str
static int lite3_ctx_arr_append_str(lite3_ctx *ctx, size_t ofs, const char *__restrict str)
Append string to array.
Definition lite3_context_api.h:848
lite3_ctx_arr_get_str
static int lite3_ctx_arr_get_str(lite3_ctx *ctx, size_t ofs, uint32_t index, lite3_str *out)
Get string value by index.
Definition lite3_context_api.h:1952
lite3_ctx_arr_set_str
static int lite3_ctx_arr_set_str(lite3_ctx *ctx, size_t ofs, uint32_t index, const char *__restrict str)
Set string in array.
Definition lite3_context_api.h:1083
lite3_ctx_init_arr
static int lite3_ctx_init_arr(lite3_ctx *ctx)
Initialize a Lite³ context as an array.
Definition lite3_context_api.h:287
lite3_ctx_json_print
static int lite3_ctx_json_print(lite3_ctx *ctx, size_t ofs)
Print Lite³ buffer as JSON to stdout
Definition lite3_context_api.h:2217
lite3_ctx_create
static lite3_ctx * lite3_ctx_create(void)
Create context with minimum size.
Definition lite3_context_api.h:214
lite3_ctx_destroy
void lite3_ctx_destroy(lite3_ctx *ctx)
Destroy context.
Definition ctx_api.c:229
lite3_ctx_count
static int lite3_ctx_count(lite3_ctx *ctx, size_t ofs, uint32_t *out)
Write back the number of object entries or array elements.
Definition lite3_context_api.h:1303
LITE3_STR
#define LITE3_STR(buf, val)
Generational pointer / safe access wrapper.
Definition lite3.h:666
lite3_context_api.h
Lite³ Context API Header.
lite3_ctx
Lite³ context struct.
Definition lite3_context_api.h:140
lite3_str
Struct holding a reference to a string inside a Lite³ buffer.
Definition lite3.h:601

Output:

buflen: 168
[
"zebra",
"giraffe",
"buffalo",
"lion",
"rhino",
"elephant"
]
Element at index 2: buffalo
Element count: 6
Last element: elephant
Overwriting index 2 with "gnu"
buflen: 168
[
"zebra",
"giraffe",
"gnu",
"lion",
"rhino",
"elephant"
]
Overwriting index 3 with "springbok"
buflen: 183
[
"zebra",
"giraffe",
"gnu",
"springbok",
"rhino",
"elephant"
]

Explanation

We will walk through the example code step-by-step, explaining the use of Lite³ library functions.

Lite³ messages are just bytes, stored contiguously inside a buffer. If you want to allocate these messages inside your own custom allocators, you can using the Buffer API. However in this guide, we will be using the Context API so that memory is managed automatically.

Note that Lite³ is a binary format, but the examples print message data as JSON to stdout for better readability.

Appending

As explained in the first guide, we use contexts to store Lite³ buffers (see: Context API):

lite3_ctx *ctx = lite3_ctx_create();
if (!ctx) {
perror("Failed to create lite3_ctx *ctx");
return 1;
}

Normally, we initilize the buffer as an object. This time for a change, it will be an array:

// Build message
if (lite3_ctx_init_arr(ctx) < 0
|| lite3_ctx_arr_append_str(ctx, 0, "zebra") < 0
|| lite3_ctx_arr_append_str(ctx, 0, "giraffe") < 0
|| lite3_ctx_arr_append_str(ctx, 0, "buffalo") < 0
|| lite3_ctx_arr_append_str(ctx, 0, "lion") < 0
|| lite3_ctx_arr_append_str(ctx, 0, "rhino") < 0
|| lite3_ctx_arr_append_str(ctx, 0, "elephant") < 0) {
perror("Failed to build message");
return 1;
}

Converting Lite³ to JSON shows us what this data looks like:

printf("buflen: %zu\n", ctx->buflen);
if (lite3_ctx_json_print(ctx, 0) < 0) { // Print Lite³ as JSON
perror("Failed to print JSON");
return 1;
}

Output:

buflen: 168
[
"zebra",
"giraffe",
"buffalo",
"lion",
"rhino",
"elephant"
]

Get by index

Array functions, for the most part, have 'arr' inside the name. Here is how to get an element by index:

lite3_str element_2;
if (lite3_ctx_arr_get_str(ctx, 0, 2, &element_2) < 0) {
perror("Failed to get element");
return 1;
}
printf("Element at index 2: %s\n", LITE3_STR(ctx->buf, element_2));

Output:

Element at index 2: buffalo

For the function lite3_ctx_arr_get_str(), the index is the 3rd parameter. The 2nd parameter is the ofs or 'offset' parameter (see Nesting).

Get element count

uint32_t element_count;
if (lite3_ctx_count(ctx, 0, &element_count) < 0) {
perror("Failed to get element count");
return 1;
}
printf("Element count: %u\n", element_count);

Output:

Element count: 6

One interesting fact about lite3_ctx_count() is that it does not have 'arr' in the name. This is because it works on both objects and arrays. For objects, the number of entries (key-value pairs) is returned. For arrays, the number of elements.

Note
Indexes and counts are typed (uint32_t), while buffer offsets and lengths are (size_t).

Get last element

Any real programmer should know that the first index is 0 and the last is (element_count - 1).

Luckily, if you are reading this then you probably are a real programmer:

lite3_str last_element;
if (lite3_ctx_arr_get_str(ctx, 0, element_count - 1, &last_element) < 0) {
perror("Failed to get element");
return 1;
}
printf("Last element: %s\n", LITE3_STR(ctx->buf, last_element));

Output:

Last element: elephant

Set by index

Now we get to the juicy part. Recall that Lite³ data is simulateously serialized and mutable. A read or write to any individual value can be satisfied without requiring parsing or processing of a message in full. This includes appending to- and setting elements inside arrays.

Let's demonstrate this by replacing the element at index 2 with the string "gnu":

"buffalo" ===> "gnu"

Here is the code:

printf("\nOverwriting index 2 with \"gnu\"\n");
if (lite3_ctx_arr_set_str(ctx, 0, 2, "gnu") < 0) {
perror("Failed to set element");
return 1;
}
printf("buflen: %zu\n", ctx->buflen);
if (lite3_ctx_json_print(ctx, 0) < 0) {
perror("Failed to print JSON");
return 1;
}

Output:

Overwriting index 2 with "gnu"
buflen: 168
[
"zebra",
"giraffe",
"gnu",
"lion",
"rhino",
"elephant"
]

Notice that the string got replaced. But also, that the buffer length (message size) stayed entirely unchanged at 168 bytes, which it also was before. This is the power of Lite³. No parsing. No processing. Change any value just like that. Serialized data is mutable.

Unfortunately, there is no magic. In this case, the new string value was smaller than the previous ("gnu" vs "buffalo"). If we override with a string that larger than the existing one, where do we get the extra space from? Inevitably, message size will have to increase.

Let's try the same thing, but instead we replace "lion" with "springbok":

printf("\nOverwriting index 3 with \"springbok\"\n");
if (lite3_ctx_arr_set_str(ctx, 0, 3, "springbok") < 0) {
perror("Failed to set element");
return 1;
}
printf("buflen: %zu\n", ctx->buflen);
if (lite3_ctx_json_print(ctx, 0) < 0) {
perror("Failed to print JSON");
return 1;
}

Output:

Overwriting index 3 with "springbok"
buflen: 183
[
"zebra",
"giraffe",
"gnu",
"springbok",
"rhino",
"elephant"
]

The operation succeeded, though at the cost of increasing message size.

Internally, situations like this cause the new data to be appended to the buffer. Unfortunately, this leaves an empty gap at the previous storage location of "lion". More unfortunate, this wasted space will never be recovered. Recovering it would require a sophisticated defragmentation or memory allocation system. This means that if we keep replacing variable sized strings, the buffer will eventually fragment and grow indefinitely.

To rid the buffer of these fragments, it must be rebuilt from scratch. Applications can choose to increase message size until the cost of carrying unused bytes outweighs the cost of rebuilding. If we had an array of integers or doubles however, we can keep overriding them forever without ever increasing buffer size. This works because those types are fixed-size.

All the above is equally valid for overwriting of values inside objects.

Array insert

One function commonly provided by dynamic programming languages is 'insert' in the middle of an array. That is, to set an alement at a target index and 'shift' all elements after it to make room.

This operation is not (yet) supported by Lite³. A workaround is to set all the elements individually, or to completely replace the array.

Cleaning up

We are good citizens, so we clean up after ourselves:

lite3_ctx_destroy(ctx);

This destroys the context, freeing all the internal buffers so that the memory is released. When you create contexts, don't forget to destroy them, or else you will be leaking memory.

Conclusion

This was the fifth guide covering arrays.

The next guide will show iterators: Next Guide: Iterators