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