From 463b175cdbe29f2741478b69646b65647278f46f Mon Sep 17 00:00:00 2001
From: Stephen Dolan <mu@netsoc.tcd.ie>
Date: Tue, 28 Aug 2012 18:09:43 +0100
Subject: [PATCH] Reference-counted copy-on-write JSON library.
Comes with tests and, presumably, bugs.
---
c/Makefile | 12 +-
c/jv.c | 764 +++++++++++++++++++++++++++++++++++++++++++++++++++
c/jv.h | 100 +++++++
c/jv_print.c | 45 +++
c/jvtest.c | 135 +++++++++
5 files changed, 1055 insertions(+), 1 deletion(-)
create mode 100644 c/jv.c
create mode 100644 c/jv_print.c
create mode 100644 c/jvtest.c
diff --git a/c/Makefile b/c/Makefile
index 01c3b54..b77971d 100644
--- a/c/Makefile
+++ b/c/Makefile
@@ -1,4 +1,4 @@
-CC=gcc -Wall -std=gnu99 -ggdb
+CC=gcc -Wall -std=gnu99 -ggdb -Wno-unused-function
.PHONY: all clean
all: parsertest
@@ -19,3 +19,13 @@ parser.tab.h: parser.tab.c
parsertest: parser.tab.c lexer.yy.c main.c opcode.c bytecode.c compile.c execute.c builtin.c
$(CC) -o $@ $^ -ljansson
+
+jvtest: jvtest.c jv.c jv_print.c
+ $(CC) -o $@ $^ -ljansson
+
+test: jvtest
+ valgrind --error-exitcode=1 -q --leak-check=full ./jvtest
+
+jsparse: jsparse.l jv.c
+ flex -o jsparse.c jsparse.l
+ gcc -o jsparse jsparse.c -ljansson
\ No newline at end of file
diff --git a/c/jv.c b/c/jv.c
new file mode 100644
index 0000000..09b600d
--- /dev/null
+++ b/c/jv.c
@@ -0,0 +1,764 @@
+#include <stdint.h>
+#include <stddef.h>
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "jv.h"
+
+/*
+ * Internal refcounting helpers
+ */
+
+static void jvp_refcnt_init(jv_complex* c) {
+ c->ptr->count = 1;
+}
+
+static void jvp_refcnt_inc(jv_complex* c) {
+ c->ptr->count++;
+}
+
+static int jvp_refcnt_dec(jv_complex* c) {
+ c->ptr->count--;
+ return c->ptr->count == 0;
+}
+
+static int jvp_refcnt_unshared(jv_complex* c) {
+ assert(c->ptr->count > 0);
+ return c->ptr->count == 1;
+}
+
+/*
+ * Simple values (true, false, null)
+ */
+
+jv_kind jv_get_kind(jv x) {
+ return x.kind;
+}
+
+static const jv JV_NULL = {JV_KIND_NULL, {0}};
+static const jv JV_FALSE = {JV_KIND_FALSE, {0}};
+static const jv JV_TRUE = {JV_KIND_TRUE, {0}};
+
+jv jv_true() {
+ return JV_TRUE;
+}
+
+jv jv_false() {
+ return JV_FALSE;
+}
+
+jv jv_null() {
+ return JV_NULL;
+}
+
+/*
+ * Numbers
+ */
+
+jv jv_number(double x) {
+ jv j;
+ j.kind = JV_KIND_NUMBER;
+ j.val.number = x;
+ return j;
+}
+
+double jv_number_value(jv j) {
+ assert(jv_get_kind(j) == JV_KIND_NUMBER);
+ return j.val.number;
+}
+
+
+/*
+ * Arrays (internal helpers)
+ */
+
+#define ARRAY_SIZE_ROUND_UP(n) (((n)*3)/2)
+
+static int imax(int a, int b) {
+ if (a>b) return a;
+ else return b;
+}
+
+//FIXME signed vs unsigned
+typedef struct {
+ jv_refcnt refcnt;
+ int length, alloc_length;
+ jv elements[];
+} jvp_array;
+
+static jvp_array* jvp_array_ptr(jv_complex* a) {
+ return (jvp_array*)a->ptr;
+}
+
+static jvp_array* jvp_array_alloc(unsigned size) {
+ jvp_array* a = malloc(sizeof(jvp_array) + sizeof(jv) * size);
+ a->refcnt.count = 1;
+ a->length = 0;
+ a->alloc_length = size;
+ return a;
+}
+
+static jv_complex jvp_array_new(unsigned size) {
+ jv_complex r = {&jvp_array_alloc(size)->refcnt, {0, 0}};
+ return r;
+}
+
+static void jvp_array_free(jv_complex* a) {
+ if (jvp_refcnt_dec(a)) {
+ jvp_array* array = jvp_array_ptr(a);
+ for (int i=0; i<array->length; i++) {
+ jv_free(array->elements[i]);
+ }
+ free(array);
+ }
+}
+
+static int jvp_array_length(jv_complex* a) {
+ return a->i[1] - a->i[0];
+}
+
+static jv* jvp_array_read(jv_complex* a, int i) {
+ assert(i >= 0 && i < jvp_array_length(a));
+ jvp_array* array = jvp_array_ptr(a);
+ assert(i + a->i[0] < array->length);
+ return &array->elements[i + a->i[0]];
+}
+
+static jv* jvp_array_write(jv_complex* a, int i) {
+ assert(i >= 0);
+ jvp_array* array = jvp_array_ptr(a);
+
+ int pos = i + a->i[0];
+ if (pos < array->alloc_length) {
+ // maybe we can update it in-place
+ // FIXME: this "optimisation" can cause circular references
+ #if 0
+ int can_write_past_end =
+ array->length <= pos && /* the end of this array has never been used */
+ a->i[1] == array->length; /* the current slice sees the end of the array */
+ #endif
+ int can_write_past_end = 0;
+ if (can_write_past_end || jvp_refcnt_unshared(a)) {
+ // extend the array
+ for (int j = array->length; j <= pos; j++) {
+ array->elements[j] = JV_NULL;
+ }
+ array->length = imax(pos + 1, array->length);
+ a->i[1] = imax(pos + 1, array->length);
+ return &array->elements[pos];
+ }
+ }
+
+
+ int new_length = imax(i + 1, jvp_array_length(a));
+ jvp_array* new_array = jvp_array_alloc(ARRAY_SIZE_ROUND_UP(new_length));
+ int j;
+ for (j = 0; j < jvp_array_length(a); j++) {
+ new_array->elements[j] = jv_copy(array->elements[j + a->i[0]]);
+ }
+ for (; j < new_length; j++) {
+ new_array->elements[j] = JV_NULL;
+ }
+ new_array->length = new_length;
+ jvp_array_free(a);
+ a->ptr = &new_array->refcnt;
+ a->i[0] = 0;
+ a->i[1] = new_length;
+ return &new_array->elements[i];
+}
+
+static int jvp_array_equal(jv_complex* a, jv_complex* b) {
+ if (jvp_array_length(a) != jvp_array_length(b))
+ return 0;
+ if (jvp_array_ptr(a) == jvp_array_ptr(b) &&
+ a->i[0] == b->i[0])
+ return 1;
+ for (int i=0; i<jvp_array_length(a); i++) {
+ if (!jv_equal(jv_copy(*jvp_array_read(a, i)),
+ jv_copy(*jvp_array_read(b,i))))
+ return 0;
+ }
+ return 1;
+}
+
+static jv_complex jvp_array_slice(jv_complex* a, int start, int end) {
+ // FIXME: maybe slice should reallocate if the slice is small enough
+ assert(start <= end);
+ jvp_array* array = jvp_array_ptr(a);
+ assert(a->i[1] + end < array->length);
+ jv_complex slice = *a;
+ slice.i[0] += start;
+ slice.i[1] = slice.i[0] + (end - start);
+ return slice;
+}
+
+/*
+ * Arrays (public interface)
+ */
+
+jv jv_array_sized(int n) {
+ jv j;
+ j.kind = JV_KIND_ARRAY;
+ j.val.complex = jvp_array_new(n);
+ return j;
+}
+
+jv jv_array() {
+ return jv_array_sized(16);
+}
+
+int jv_array_length(jv j) {
+ assert(jv_get_kind(j) == JV_KIND_ARRAY);
+ int len = jvp_array_length(&j.val.complex);
+ jv_free(j);
+ return len;
+}
+
+jv jv_array_get(jv j, int idx) {
+ assert(jv_get_kind(j) == JV_KIND_ARRAY);
+ jv val = jv_copy(*jvp_array_read(&j.val.complex, idx));
+ jv_free(j);
+ return val;
+}
+
+jv jv_array_set(jv j, int idx, jv val) {
+ assert(jv_get_kind(j) == JV_KIND_ARRAY);
+ // copy/free of val,j coalesced
+ *jvp_array_write(&j.val.complex, idx) = val;
+ return j;
+}
+
+jv jv_array_append(jv j, jv val) {
+ // copy/free of val,j coalesced
+ return jv_array_set(j, jv_array_length(jv_copy(j)), val);
+}
+
+jv jv_array_concat(jv a, jv b) {
+ assert(jv_get_kind(a) == JV_KIND_ARRAY);
+ assert(jv_get_kind(b) == JV_KIND_ARRAY);
+
+ // FIXME: could be much faster
+ for (int i=0; i<jv_array_length(b); i++) {
+ a = jv_array_append(a, jv_array_get(jv_copy(b), i));
+ }
+ jv_free(b);
+ return a;
+}
+
+jv jv_array_slice(jv a, int start, int end) {
+ assert(jv_get_kind(a) == JV_KIND_ARRAY);
+ // copy/free of a coalesced
+ a.val.complex = jvp_array_slice(&a.val.complex, start, end);
+ return a;
+}
+
+
+/*
+ * Strings (internal helpers)
+ */
+
+typedef struct {
+ jv_refcnt refcnt;
+ uint32_t hash;
+ // high 31 bits are length, low bit is a flag
+ // indicating whether hash has been computed.
+ uint32_t length_hashed;
+ char data[];
+} jvp_string;
+
+static jvp_string* jvp_string_ptr(jv_complex* a) {
+ return (jvp_string*)a->ptr;
+}
+
+static jvp_string* jvp_string_alloc(uint32_t size) {
+ jvp_string* s = malloc(sizeof(jvp_string) + size + 1);
+ s->refcnt.count = 1;
+ s->length_hashed = size << 1;
+ return s;
+}
+
+static jv_complex jvp_string_new(char* data, uint32_t length) {
+ jvp_string* s = jvp_string_alloc(length);
+ memcpy(s->data, data, length);
+ s->data[length] = 0;
+ jv_complex r = {&s->refcnt, {0,0}};
+ return r;
+}
+
+static void jvp_string_free(jv_complex* s) {
+ if (jvp_refcnt_dec(s)) {
+ jvp_string* str = jvp_string_ptr(s);
+ free(str);
+ }
+}
+
+static void jvp_string_free_p(jvp_string* s) {
+ jv_complex p = {&s->refcnt,{0,0}};
+ jvp_string_free(&p);
+}
+
+static jvp_string* jvp_string_copy_p(jvp_string* s) {
+ jv_complex p = {&s->refcnt,{0,0}};
+ jvp_refcnt_inc(&p);
+ return s;
+}
+
+static uint32_t jvp_string_length(jvp_string* s) {
+ return s->length_hashed >> 1;
+}
+
+static const uint32_t HASH_SEED = 0x432A9843;
+
+static uint32_t rotl32 (uint32_t x, int8_t r){
+ return (x << r) | (x >> (32 - r));
+}
+
+static uint32_t jvp_string_hash(jvp_string* str) {
+ if (str->length_hashed & 1)
+ return str->hash;
+
+ /* The following is based on MurmurHash3.
+ MurmurHash3 was written by Austin Appleby, and is placed
+ in the public domain. */
+
+ const uint8_t* data = (const uint8_t*)str->data;
+ int len = (int)jvp_string_length(str);
+ const int nblocks = len / 4;
+
+ uint32_t h1 = HASH_SEED;
+
+ const uint32_t c1 = 0xcc9e2d51;
+ const uint32_t c2 = 0x1b873593;
+ const uint32_t* blocks = (const uint32_t *)(data + nblocks*4);
+
+ for(int i = -nblocks; i; i++) {
+ uint32_t k1 = blocks[i]; //FIXME: endianness/alignment
+
+ k1 *= c1;
+ k1 = rotl32(k1,15);
+ k1 *= c2;
+
+ h1 ^= k1;
+ h1 = rotl32(h1,13);
+ h1 = h1*5+0xe6546b64;
+ }
+
+ const uint8_t* tail = (const uint8_t*)(data + nblocks*4);
+
+ uint32_t k1 = 0;
+
+ switch(len & 3) {
+ case 3: k1 ^= tail[2] << 16;
+ case 2: k1 ^= tail[1] << 8;
+ case 1: k1 ^= tail[0];
+ k1 *= c1; k1 = rotl32(k1,15); k1 *= c2; h1 ^= k1;
+ }
+
+ h1 ^= len;
+
+ h1 ^= h1 >> 16;
+ h1 *= 0x85ebca6b;
+ h1 ^= h1 >> 13;
+ h1 *= 0xc2b2ae35;
+ h1 ^= h1 >> 16;
+
+ str->length_hashed |= 1;
+ str->hash = h1;
+
+ return h1;
+}
+
+static int jvp_string_equal_hashed(jvp_string* a, jvp_string* b) {
+ assert(a->length_hashed & 1);
+ assert(b->length_hashed & 1);
+ if (a == b) return 1;
+ if (a->hash != b->hash) return 0;
+ if (a->length_hashed != b->length_hashed) return 0;
+ return memcmp(a->data, b->data, jvp_string_length(a)) == 0;
+}
+
+static int jvp_string_equal(jv_complex* a, jv_complex* b) {
+ jvp_string* stra = jvp_string_ptr(a);
+ jvp_string* strb = jvp_string_ptr(b);
+ if (jvp_string_length(stra) != jvp_string_length(strb)) return 0;
+ return memcmp(stra->data, strb->data, jvp_string_length(stra)) == 0;
+}
+
+/*
+ * Strings (public API)
+ */
+
+jv jv_string_sized(char* str, int len) {
+ jv j;
+ j.kind = JV_KIND_STRING;
+ j.val.complex = jvp_string_new(str, len);
+ return j;
+}
+
+jv jv_string(char* str) {
+ return jv_string_sized(str, strlen(str));
+}
+
+int jv_string_length(jv j) {
+ assert(jv_get_kind(j) == JV_KIND_STRING);
+ int r = jvp_string_length(jvp_string_ptr(&j.val.complex));
+ jv_free(j);
+ return r;
+}
+
+uint32_t jv_string_hash(jv j) {
+ assert(jv_get_kind(j) == JV_KIND_STRING);
+ uint32_t hash = jvp_string_hash(jvp_string_ptr(&j.val.complex));
+ jv_free(j);
+ return hash;
+}
+
+const char* jv_string_value(jv j) {
+ assert(jv_get_kind(j) == JV_KIND_STRING);
+ return jvp_string_ptr(&j.val.complex)->data;
+}
+
+/*
+ * Objects (internal helpers)
+ */
+
+struct object_slot {
+ int next;
+ jvp_string* string;
+ uint32_t hash;
+ jv value;
+};
+
+typedef struct {
+ jv_refcnt refcnt;
+ int first_free;
+ struct object_slot elements[];
+} jvp_object;
+
+
+/* warning: complex justification of alignment */
+static jv_complex jvp_object_new(int size) {
+ // Allocates an object of (size) slots and (size*2) hash buckets.
+
+ // size must be a power of two
+ assert(size > 0 && (size & (size - 1)) == 0);
+ jvp_object* obj = malloc(sizeof(jvp_object) +
+ sizeof(struct object_slot) * size +
+ sizeof(int) * (size * 2));
+ obj->refcnt.count = 1;
+ for (int i=0; i<size; i++) {
+ obj->elements[i].next = i - 1;
+ obj->elements[i].string = 0;
+ obj->elements[i].hash = 0;
+ obj->elements[i].value = JV_NULL;
+ }
+ obj->first_free = size - 1;
+ int* hashbuckets = (int*)(&obj->elements[size]);
+ jv_complex r = {&obj->refcnt,
+ {size*2 - 1, (char*)hashbuckets - (char*)obj}};
+ for (int i=0; i<size*2; i++) {
+ hashbuckets[i] = -1;
+ }
+ return r;
+}
+
+static jvp_object* jvp_object_ptr(jv_complex* o) {
+ return (jvp_object*)o->ptr;
+}
+
+static uint32_t jvp_object_mask(jv_complex* o) {
+ return o->i[0];
+}
+
+static int jvp_object_size(jv_complex* o) {
+ return (o->i[0] + 1) >> 1;
+}
+
+static int* jvp_object_buckets(jv_complex* o) {
+ int* buckets = (int*)((char*)o->ptr + o->i[1]);
+ assert(buckets == (int*)&jvp_object_ptr(o)->elements[jvp_object_size(o)]);
+ return buckets;
+}
+
+static int* jvp_object_find_bucket(jv_complex* object, jvp_string* key) {
+ return jvp_object_buckets(object) + (jvp_object_mask(object) & jvp_string_hash(key));
+}
+
+static struct object_slot* jvp_object_get_slot(jv_complex* object, int slot) {
+ assert(slot == -1 || (slot >= 0 && slot < jvp_object_size(object)));
+ if (slot == -1) return 0;
+ else return &jvp_object_ptr(object)->elements[slot];
+}
+
+static struct object_slot* jvp_object_next_slot(jv_complex* object, struct object_slot* slot) {
+ return jvp_object_get_slot(object, slot->next);
+}
+
+static struct object_slot* jvp_object_find_slot(jv_complex* object, jvp_string* keystr, int* bucket) {
+ for (struct object_slot* curr = jvp_object_get_slot(object, *bucket);
+ curr;
+ curr = jvp_object_next_slot(object, curr)) {
+ if (jvp_string_equal_hashed(keystr, curr->string)) {
+ return curr;
+ }
+ }
+ return 0;
+}
+
+static struct object_slot* jvp_object_add_slot(jv_complex* object, jvp_string* key, int* bucket) {
+ jvp_object* o = jvp_object_ptr(object);
+ int newslot_idx = o->first_free;
+ struct object_slot* newslot = jvp_object_get_slot(object, newslot_idx);
+ if (newslot == 0) return 0;
+ o->first_free = newslot->next;
+ newslot->next = *bucket;
+ *bucket = newslot_idx;
+ newslot->hash = jvp_string_hash(key);
+ newslot->string = key;
+ return newslot;
+}
+
+static void jvp_object_free_slot(jv_complex* object, struct object_slot* slot) {
+ jvp_object* o = jvp_object_ptr(object);
+ slot->next = o->first_free;
+ assert(slot->string);
+ jvp_string_free_p(slot->string);
+ slot->string = 0;
+ jv_free(slot->value);
+ o->first_free = slot - jvp_object_get_slot(object, 0);
+}
+
+static jv* jvp_object_read(jv_complex* object, jvp_string* key) {
+ int* bucket = jvp_object_find_bucket(object, key);
+ struct object_slot* slot = jvp_object_find_slot(object, key, bucket);
+ if (slot == 0) return 0;
+ else return &slot->value;
+}
+
+static void jvp_object_free(jv_complex* o) {
+ if (jvp_refcnt_dec(o)) {
+ for (int i=0; i<jvp_object_size(o); i++) {
+ struct object_slot* slot = jvp_object_get_slot(o, i);
+ if (slot->string) {
+ jvp_string_free_p(slot->string);
+ jv_free(slot->value);
+ }
+ }
+ free(jvp_object_ptr(o));
+ }
+}
+
+static void jvp_object_rehash(jv_complex* object) {
+ assert(jvp_refcnt_unshared(object));
+ int size = jvp_object_size(object);
+ jv_complex new_object = jvp_object_new(size * 2);
+ for (int i=0; i<size; i++) {
+ struct object_slot* slot = jvp_object_get_slot(object, i);
+ if (!slot->string) continue;
+
+ int* new_bucket = jvp_object_find_bucket(&new_object, slot->string);
+ assert(!jvp_object_find_slot(&new_object, slot->string, new_bucket));
+ struct object_slot* new_slot = jvp_object_add_slot(&new_object, slot->string, new_bucket);
+ assert(new_slot);
+ new_slot->value = slot->value;
+ }
+ // references are transported, just drop the old table
+ free(jvp_object_ptr(object));
+ *object = new_object;
+}
+
+static void jvp_object_unshare(jv_complex* object) {
+ if (jvp_refcnt_unshared(object))
+ return;
+
+ jv_complex new_object = jvp_object_new(jvp_object_size(object));
+ jvp_object_ptr(&new_object)->first_free = jvp_object_ptr(object)->first_free;
+ for (int i=0; i<jvp_object_size(&new_object); i++) {
+ struct object_slot* old_slot = jvp_object_get_slot(object, i);
+ struct object_slot* new_slot = jvp_object_get_slot(&new_object, i);
+ *new_slot = *old_slot;
+ if (old_slot->string) {
+ new_slot->string = jvp_string_copy_p(old_slot->string);
+ new_slot->value = jv_copy(old_slot->value);
+ }
+ }
+
+ int* old_buckets = jvp_object_buckets(object);
+ int* new_buckets = jvp_object_buckets(&new_object);
+ memcpy(new_buckets, old_buckets, sizeof(int) * jvp_object_size(&new_object)*2);
+
+ jvp_object_free(object);
+ *object = new_object;
+ assert(jvp_refcnt_unshared(object));
+}
+
+static jv* jvp_object_write(jv_complex* object, jvp_string* key) {
+ jvp_object_unshare(object);
+ int* bucket = jvp_object_find_bucket(object, key);
+ struct object_slot* slot = jvp_object_find_slot(object, key, bucket);
+ if (slot) {
+ // already has the key
+ jvp_string_free_p(key);
+ } else {
+ slot = jvp_object_add_slot(object, key, bucket);
+ }
+ if (slot == 0) {
+ jvp_object_rehash(object);
+ bucket = jvp_object_find_bucket(object, key);
+ assert(!jvp_object_find_slot(object, key, bucket));
+ slot = jvp_object_add_slot(object, key, bucket);
+ assert(slot);
+ }
+ return &slot->value;
+}
+
+static int jvp_object_delete(jv_complex* object, jvp_string* key) {
+ jvp_object_unshare(object);
+ int* bucket = jvp_object_find_bucket(object, key);
+ int* prev_ptr = bucket;
+ for (struct object_slot* curr = jvp_object_get_slot(object, *bucket);
+ curr;
+ curr = jvp_object_next_slot(object, curr)) {
+ if (jvp_string_equal_hashed(key, curr->string)) {
+ *prev_ptr = curr->next;
+ jvp_object_free_slot(object, curr);
+ return 1;
+ }
+ prev_ptr = &curr->next;
+ }
+ return 0;
+}
+
+/*
+ * Objects (public interface)
+ */
+#define DEFAULT_OBJECT_SIZE 8
+jv jv_object() {
+ jv j;
+ j.kind = JV_KIND_OBJECT;
+ j.val.complex = jvp_object_new(8);
+ return j;
+}
+
+jv jv_object_get(jv object, jv key) {
+ assert(jv_get_kind(object) == JV_KIND_OBJECT);
+ assert(jv_get_kind(key) == JV_KIND_STRING);
+ jv val = jv_copy(*jvp_object_read(&object.val.complex, jvp_string_ptr(&key.val.complex)));
+ jv_free(object);
+ jv_free(key);
+ return val;
+}
+
+jv jv_object_set(jv object, jv key, jv value) {
+ assert(jv_get_kind(object) == JV_KIND_OBJECT);
+ assert(jv_get_kind(key) == JV_KIND_STRING);
+ // copy/free of object, key, value coalesced
+ *jvp_object_write(&object.val.complex, jvp_string_ptr(&key.val.complex)) = value;
+ return object;
+}
+
+jv jv_object_delete(jv object, jv key) {
+ assert(jv_get_kind(object) == JV_KIND_OBJECT);
+ assert(jv_get_kind(key) == JV_KIND_STRING);
+ jvp_object_delete(&object.val.complex, jvp_string_ptr(&key.val.complex));
+ jv_free(key);
+ return object;
+}
+
+/*
+ * Object iteration (internal helpers)
+ */
+
+enum { ITER_FINISHED = -2 };
+
+int jv_object_iter_valid(jv object, int i) {
+ return i != ITER_FINISHED;
+}
+
+int jv_object_iter(jv object) {
+ assert(jv_get_kind(object) == JV_KIND_OBJECT);
+ return jv_object_iter_next(object, -1);
+}
+
+int jv_object_iter_next(jv object, int iter) {
+ assert(jv_get_kind(object) == JV_KIND_OBJECT);
+ assert(iter != ITER_FINISHED);
+ jv_complex* o = &object.val.complex;
+ struct object_slot* slot;
+ do {
+ iter++;
+ if (iter >= jvp_object_size(o))
+ return ITER_FINISHED;
+ slot = jvp_object_get_slot(o, iter);
+ } while (!slot->string);
+ return iter;
+}
+
+jv jv_object_iter_key(jv object, int iter) {
+ jvp_string* s = jvp_object_get_slot(&object.val.complex, iter)->string;
+ assert(s);
+ jv j;
+ j.kind = JV_KIND_STRING;
+ j.val.complex.ptr = &s->refcnt;
+ j.val.complex.i[0] = 0;
+ j.val.complex.i[1] = 0;
+ return jv_copy(j);
+}
+
+jv jv_object_iter_value(jv object, int iter) {
+ return jv_copy(jvp_object_get_slot(&object.val.complex, iter)->value);
+}
+
+/*
+ * Memory management
+ */
+jv jv_copy(jv j) {
+ if (jv_get_kind(j) == JV_KIND_ARRAY ||
+ jv_get_kind(j) == JV_KIND_STRING ||
+ jv_get_kind(j) == JV_KIND_OBJECT) {
+ jvp_refcnt_inc(&j.val.complex);
+ }
+ return j;
+}
+
+void jv_free(jv j) {
+ if (jv_get_kind(j) == JV_KIND_ARRAY) {
+ jvp_array_free(&j.val.complex);
+ } else if (jv_get_kind(j) == JV_KIND_STRING) {
+ jvp_string_free(&j.val.complex);
+ } else if (jv_get_kind(j) == JV_KIND_OBJECT) {
+ jvp_object_free(&j.val.complex);
+ }
+}
+
+/*
+ * Higher-level operations
+ */
+
+int jv_equal(jv a, jv b) {
+ int r;
+ if (jv_get_kind(a) != jv_get_kind(b)) {
+ r = 0;
+ } else {
+ switch (jv_get_kind(a)) {
+ case JV_KIND_NUMBER:
+ r = jv_number_value(a) == jv_number_value(b);
+ break;
+ case JV_KIND_ARRAY: {
+ r = jvp_array_equal(&a.val.complex, &b.val.complex);
+ break;
+ }
+ case JV_KIND_STRING: {
+ r = jvp_string_equal(&a.val.complex, &b.val.complex);
+ break;
+ }
+ default:
+ r = 1;
+ break;
+ }
+ }
+ jv_free(a);
+ jv_free(b);
+ return r;
+}
diff --git a/c/jv.h b/c/jv.h
index fc964fa..52158b7 100644
--- a/c/jv.h
+++ b/c/jv.h
@@ -2,6 +2,8 @@
#define JV_H
#include <jansson.h>
+#include <stdint.h>
+#include <assert.h>
static json_t* jv_lookup(json_t* t, json_t* k) {
json_t* v;
@@ -38,4 +40,102 @@ static json_t* jv_insert(json_t* root, json_t* value, json_t** path, int pathlen
}
+
+
+typedef enum {
+ JV_KIND_NULL,
+ JV_KIND_FALSE,
+ JV_KIND_TRUE,
+ JV_KIND_NUMBER,
+ JV_KIND_STRING,
+ JV_KIND_OBJECT,
+ JV_KIND_ARRAY
+} jv_kind;
+
+typedef struct {
+ size_t count;
+} jv_refcnt;
+
+typedef struct{
+ jv_refcnt* ptr;
+ int i[2];
+} jv_complex;
+
+typedef struct {
+ jv_kind kind;
+ union {
+ double number;
+ jv_complex complex;
+ } val;
+} jv;
+
+/*
+ * All jv_* functions consume (decref) input and produce (incref) output
+ * Except jv_copy
+ */
+
+jv_kind jv_get_kind(jv);
+
+jv jv_copy(jv);
+void jv_free(jv);
+
+int jv_equal(jv, jv);
+
+jv jv_null();
+jv jv_true();
+jv jv_false();
+
+jv jv_number(double);
+double jv_number_value(jv);
+
+jv jv_array();
+jv jv_array_sized(int);
+int jv_array_length(jv);
+jv jv_array_get(jv, int);
+jv jv_array_set(jv, int, jv);
+jv jv_array_append(jv, jv);
+jv jv_array_concat(jv, jv);
+jv jv_array_slice(jv, int, int);
+
+
+jv jv_string(char*);
+jv jv_string_sized(char*, int);
+int jv_string_length(jv);
+uint32_t jv_string_hash(jv);
+const char* jv_string_value(jv);
+
+jv jv_object();
+jv jv_object_get(jv object, jv key);
+jv jv_object_set(jv object, jv key, jv value);
+jv jv_object_delete(jv object, jv key);
+
+int jv_object_iter(jv);
+int jv_object_iter_next(jv, int);
+int jv_object_iter_valid(jv, int);
+jv jv_object_iter_key(jv, int);
+jv jv_object_iter_value(jv, int);
+
+
#endif
+
+
+/*
+
+true/false/null:
+check kind
+
+number:
+introduce/eliminate jv
+to integer
+
+array:
+copy
+free
+slice
+index
+update
+
+updateslice?
+
+
+ */
diff --git a/c/jv_print.c b/c/jv_print.c
new file mode 100644
index 0000000..b26d0b3
--- /dev/null
+++ b/c/jv_print.c
@@ -0,0 +1,45 @@
+#include "jv.h"
+#include <stdio.h>
+
+void jv_dump(jv x) {
+ switch (jv_get_kind(x)) {
+ case JV_KIND_NULL:
+ printf("null");
+ break;
+ case JV_KIND_FALSE:
+ printf("false");
+ break;
+ case JV_KIND_TRUE:
+ printf("true");
+ break;
+ case JV_KIND_NUMBER:
+ printf("%f", jv_number_value(x));
+ break;
+ case JV_KIND_STRING:
+ // FIXME: all sorts of broken
+ printf("\"%s\"", jv_string_value(x));
+ break;
+ case JV_KIND_ARRAY: {
+ printf("[");
+ for (int i=0; i<jv_array_length(jv_copy(x)); i++) {
+ if (i!=0) printf(", ");
+ jv_dump(jv_array_get(jv_copy(x), i));
+ }
+ printf("]");
+ break;
+ }
+ case JV_KIND_OBJECT: {
+ printf("{");
+ int first = 1;
+ for (int i = jv_object_iter(x); jv_object_iter_valid(x,i); i = jv_object_iter_next(x,i)) {
+ if (!first) printf(", ");
+ first = 0;
+ jv_dump(jv_object_iter_key(x, i));
+ printf(": ");
+ jv_dump(jv_object_iter_value(x, i));
+ }
+ printf("}");
+ }
+ }
+ jv_free(x);
+}
diff --git a/c/jvtest.c b/c/jvtest.c
new file mode 100644
index 0000000..667d706
--- /dev/null
+++ b/c/jvtest.c
@@ -0,0 +1,135 @@
+#include <assert.h>
+#include <stdio.h>
+#include <string.h>
+#include "jv.h"
+
+void jv_dump(jv);
+
+int main(){
+ /// Arrays and numbers
+ {
+ jv a = jv_array();
+ assert(jv_get_kind(a) == JV_KIND_ARRAY);
+ assert(jv_array_length(jv_copy(a)) == 0);
+ assert(jv_array_length(jv_copy(a)) == 0);
+
+ a = jv_array_append(a, jv_number(42));
+ assert(jv_array_length(jv_copy(a)) == 1);
+ assert(jv_number_value(jv_array_get(jv_copy(a), 0)) == 42);
+
+ jv a2 = jv_array_append(jv_array(), jv_number(42));
+ assert(jv_equal(jv_copy(a), jv_copy(a)));
+ assert(jv_equal(jv_copy(a2), jv_copy(a2)));
+ assert(jv_equal(jv_copy(a), jv_copy(a2)));
+ assert(jv_equal(jv_copy(a2), jv_copy(a)));
+ jv_free(a2);
+
+ a2 = jv_array_append(jv_array(), jv_number(19));
+ assert(!jv_equal(jv_copy(a), jv_copy(a2)));
+ assert(!jv_equal(jv_copy(a2), jv_copy(a)));
+ jv_free(a2);
+
+
+ assert(a.val.complex.ptr->count == 1);
+ a = jv_array_append(a, jv_copy(a));
+ assert(a.val.complex.ptr->count == 1);
+
+ assert(jv_array_length(jv_copy(a)) == 2);
+ assert(jv_number_value(jv_array_get(jv_copy(a), 0)) == 42);
+
+ for (int i=0; i<10; i++) {
+ jv subarray = jv_array_get(jv_copy(a), 1);
+ assert(jv_get_kind(subarray) == JV_KIND_ARRAY);
+ assert(jv_array_length(jv_copy(subarray)) == 1);
+ assert(jv_number_value(jv_array_get(jv_copy(subarray), 0)) == 42);
+ jv_free(subarray);
+ }
+
+
+ jv subarray = jv_array_get(jv_copy(a), 1);
+ assert(jv_get_kind(subarray) == JV_KIND_ARRAY);
+ assert(jv_array_length(jv_copy(subarray)) == 1);
+ assert(jv_number_value(jv_array_get(jv_copy(subarray), 0)) == 42);
+
+ jv sub2 = jv_copy(subarray);
+ sub2 = jv_array_append(sub2, jv_number(19));
+
+ assert(jv_get_kind(sub2) == JV_KIND_ARRAY);
+ assert(jv_array_length(jv_copy(sub2)) == 2);
+ assert(jv_number_value(jv_array_get(jv_copy(sub2), 0)) == 42);
+ assert(jv_number_value(jv_array_get(jv_copy(sub2), 1)) == 19);
+
+ assert(jv_get_kind(subarray) == JV_KIND_ARRAY);
+ assert(jv_array_length(jv_copy(subarray)) == 1);
+ assert(jv_number_value(jv_array_get(jv_copy(subarray), 0)) == 42);
+
+ jv_free(subarray);
+
+ void* before = sub2.val.complex.ptr;
+ sub2 = jv_array_append(sub2, jv_number(200));
+ void* after = sub2.val.complex.ptr;
+ assert(before == after);
+ jv_free(sub2);
+
+ jv a3 = jv_array_append(jv_copy(a), jv_number(19));
+ assert(jv_array_length(jv_copy(a3)) == 3);
+ assert(jv_number_value(jv_array_get(jv_copy(a3), 0)) == 42);
+ assert(jv_array_length(jv_array_get(jv_copy(a3), 1)) == 1);
+ assert(jv_number_value(jv_array_get(jv_copy(a3), 2)) == 19);
+ jv_free(a3);
+
+
+ assert(jv_array_length(jv_copy(a)) == 2);
+ assert(jv_number_value(jv_array_get(jv_copy(a), 0)) == 42);
+ assert(jv_array_length(jv_array_get(jv_copy(a), 1)) == 1);
+
+
+ jv_dump(jv_copy(a)); printf("\n");
+ jv_free(a);
+ }
+
+
+ /// Strings
+ {
+ assert(jv_equal(jv_string("foo"), jv_string_sized("foo", 3)));
+ char nasty[] = "foo\0";
+ jv shortstr = jv_string(nasty), longstr = jv_string_sized(nasty, sizeof(nasty));
+ assert(jv_string_length(shortstr) == strlen(nasty));
+ assert(jv_string_length(longstr) == sizeof(nasty));
+
+
+ char a1s[] = "hello", a2s[] = "hello", bs[] = "goodbye";
+ jv a1 = jv_string(a1s), a2 = jv_string(a2s), b = jv_string(bs);
+ assert(jv_equal(jv_copy(a1), jv_copy(a2)));
+ assert(jv_equal(jv_copy(a2), jv_copy(a1)));
+ assert(!jv_equal(jv_copy(a1), jv_copy(b)));
+
+ assert(jv_string_hash(jv_copy(a1)) == jv_string_hash(jv_copy(a1)));
+ assert(jv_string_hash(jv_copy(a1)) == jv_string_hash(jv_copy(a2)));
+ assert(jv_string_hash(jv_copy(b)) != jv_string_hash(jv_copy(a1)));
+ jv_free(a1);
+ jv_free(a2);
+ jv_free(b);
+ }
+
+ /// Objects
+ {
+ jv o1 = jv_object();
+ o1 = jv_object_set(o1, jv_string("foo"), jv_number(42));
+ o1 = jv_object_set(o1, jv_string("bar"), jv_number(24));
+ assert(jv_number_value(jv_object_get(jv_copy(o1), jv_string("foo"))) == 42);
+ assert(jv_number_value(jv_object_get(jv_copy(o1), jv_string("bar"))) == 24);
+
+ jv o2 = jv_object_set(jv_copy(o1), jv_string("foo"), jv_number(420));
+ o2 = jv_object_set(o2, jv_string("bar"), jv_number(240));
+ assert(jv_number_value(jv_object_get(jv_copy(o1), jv_string("foo"))) == 42);
+ assert(jv_number_value(jv_object_get(jv_copy(o1), jv_string("bar"))) == 24);
+ assert(jv_number_value(jv_object_get(jv_copy(o2), jv_string("foo"))) == 420);
+ jv_free(o1);
+ assert(jv_number_value(jv_object_get(jv_copy(o2), jv_string("bar"))) == 240);
+
+ jv_dump(jv_copy(o2)); printf("\n");
+
+ jv_free(o2);
+ }
+}
--
2.40.0