C graph data structure

graph.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <stdint.h>
#include <assert.h>

static const char* GRAPH_LABEL_FIELD = "_NLABEL";
static const char* GRAPH_ROOT_NAME = "_RGRAPH";
static const char* GRAPH_ROOT_VAL = "1";

struct byte_buf {
	unsigned char* data;
	size_t len;
	size_t cap;
};

typedef struct byte_buf byte_buf_t;

void byte_buf_init(byte_buf_t* buf, size_t cap) {
	buf->cap = cap;
	buf->len = 0;
	buf->data = malloc(cap);
}

void byte_buf_deinit(byte_buf_t* buf) {
	free(buf->data);
	buf->cap = 0;
}

void byte_buf_expand(byte_buf_t* buf, size_t amount) {
	buf->cap += amount;
	buf->data = realloc(buf->data, buf->cap);
}

void byte_buf_append(byte_buf_t* buf, void* obj, size_t size) {
	if ((buf->cap - buf->len) < size) {
		byte_buf_expand(buf, size * 2);
	}
	memcpy(buf->data + buf->len, obj, size);
	buf->len += size;
}

void byte_buf_write(byte_buf_t* buf, size_t offset, void* obj, size_t size) {
	if ((offset + size) < buf->cap) {
		byte_buf_expand(buf, (offset + size) * 2);
	}
	memcpy(buf->data + offset, obj, size);
}

struct kv_dict {
	char* key;
	char* val;
	struct kv_dict* next;
};

typedef struct kv_dict kv_dict_t;

// A convenience type for pairs of kv
//struct kv_pair_dict {
//	kv_dict_t* first;
//	kv_dict_t* second;
//};

typedef struct kv_pair_dict kv_pair_dict_t;

kv_dict_t* kv_dict_get_mut(kv_dict_t* dict, const char* key) {
	while (dict != NULL) {
		if (strcmp(dict->key, key) == 0) {
			break;
		}
		dict = dict->next;
	}
	return dict;
}

const kv_dict_t* kv_dict_get(const kv_dict_t* dict, const char* key) {
	while (dict != NULL) {
		if (strcmp(dict->key, key) == 0) {
			break;
		}
		dict = dict->next;
	}
	return dict;
}

void kv_dict_put_val(kv_dict_t* dict, const char* val) {
	size_t dval_size = strlen(dict->val);
	size_t newval_size = strlen(val);
	if (newval_size > dval_size) {
		dict->val = realloc(dict->val, newval_size + 1);
	}
	strcpy(dict->val, val);
}

void kv_dict_put_key(kv_dict_t* dict, const char* key) {
	size_t dkey_size = strlen(dict->key);
	size_t newkey_size = strlen(key);
	if (newkey_size > dkey_size) {
		dict->key = realloc(dict->key, newkey_size + 1);
	}
	strcpy(dict->key, key);
}

void kv_dict_put(kv_dict_t** dict, const char* key, const char* val) {
	kv_dict_t* put_slot = kv_dict_get_mut(*dict, key);

	if (put_slot != NULL) {
		kv_dict_put_val(put_slot, val);
	} else {
		kv_dict_t* new_entry = calloc(1, sizeof(kv_dict_t));
		size_t keysize = strlen(key);
		size_t valsize = strlen(val);
		new_entry->key = calloc(1, keysize + 1);
		new_entry->val = calloc(1, valsize + 1);
		kv_dict_put_key(new_entry, key);
		kv_dict_put_val(new_entry, val);
		new_entry->next = *dict;
		*dict = new_entry;
	}
}

void kv_dict_write_into(kv_dict_t** target, const kv_dict_t* other, int overwrite) {
	while (other != NULL) {
		if (overwrite) {
			kv_dict_put(target, other->key, other->val);
		} else {
			if (kv_dict_get(*target, other->key) == NULL) {
				kv_dict_put(target, other->key, other->val);
			}
		}
		other = other->next;
	}
}

void kv_dict_remove(kv_dict_t** dict, const char* key) {
	kv_dict_t* before = NULL;
	kv_dict_t* current = *dict;
	while (current != NULL) {
		if (strcmp(current->key, key) == 0) {
			break;
		}
		before = current;
		current = current->next;
	}
	if (current == NULL)
		return;
	free(current->key);
	free(current->val);
	if (before == NULL) {
		*dict = current->next;
	} else {
		before->next = current->next;
	}
	free(current);
}

void kv_dict_destroy(kv_dict_t* dict) {
	while (dict != NULL) {
		if (dict->key != NULL) {
			free(dict->key);
		}
		if (dict->val != NULL) {
			free(dict->val);
		}
		kv_dict_t* to_free = dict;
		dict = dict->next;
		free(to_free);
	}
}

size_t kv_dict_length(const kv_dict_t* dict) {
	size_t total = 0;
	while (dict != NULL) {
		++total;
		dict = dict->next;
	}
	return total;
}

int kv_dict_eq_field(const kv_dict_t* lhs, const kv_dict_t* rhs, const char* field) {
	const kv_dict_t* gotl = kv_dict_get(lhs, field);
	const kv_dict_t* gotr = kv_dict_get(rhs, field);
	return (gotl == NULL && gotr == NULL) || (strcmp(gotl->val, gotr->val) == 0);
}

int kv_dict_eq_all(const kv_dict_t* lhs, const kv_dict_t* rhs) {
	if ((lhs == NULL || rhs == NULL) && lhs != rhs)
		return 0;
	while (lhs != NULL && rhs != NULL) {
		const kv_dict_t* gotr = kv_dict_get(rhs, lhs->key);
		if ((gotr == NULL) || (strcmp(lhs->val, gotr->val) != 0))
			return 0;
		const kv_dict_t* gotl = kv_dict_get(lhs, rhs->key);
		if ((gotl == NULL) || (strcmp(rhs->val, gotl->val) != 0))
			return 0;
		lhs = lhs->next;
		rhs = rhs->next;
	}
	return 1;
}

// Find if all kvs in sub are equal in target (but not other way around)
int kv_dict_eq_sub(const kv_dict_t* target, const kv_dict_t* sub) {
	while (sub != NULL) {
		const kv_dict_t* got_target = kv_dict_get(target, sub->key);
		if ((got_target == NULL) || (strcmp(sub->val, got_target->val) != 0))
			return 0;
		sub = sub->next;
	}
	return 1;
}

void kv_dict_print(const kv_dict_t* dict, int newline) {
	printf("{");
	while (dict != NULL) {
		printf("\"%s\":\"%s\" ", dict->key, dict->val);
		dict = dict->next;
	}
	if (newline)
		printf("}\n");
	else
		printf("}");
}

size_t kv_dict_write_to(FILE* fp, const kv_dict_t* dict) {
	size_t total_bytes = 0;
	while (dict != NULL) {
		size_t keysize = strlen(dict->key);
		size_t valsize = strlen(dict->val);
		size_t total_size = keysize + valsize + (sizeof(size_t) * 2);
		total_bytes += fwrite(&total_size, sizeof(size_t), 1, fp);
		total_bytes += fwrite(&keysize, sizeof(size_t), 1, fp);
		total_bytes += fwrite(dict->key, keysize, 1, fp);
		total_bytes += fwrite(&valsize, sizeof(size_t), 1, fp);
		total_bytes += fwrite(dict->val, valsize, 1, fp);
		dict = dict->next;
	}
	return total_bytes;
}
// creates a copy of src.
void kv_dict_copy(kv_dict_t** dest, const kv_dict_t* src) {
	while (src != NULL) {
		kv_dict_put(dest, src->key, src->val);
		src = src->next;
	}
}

struct object_node {
	void* object;
	struct object_node* next;
};

typedef struct object_node object_node_t;

void object_node_default(object_node_t* node) {
	node->object = NULL;
	node->next = NULL;
}

void object_node_put(object_node_t** node, void* obj) {
	object_node_t* inner = *node;
	object_node_t* new_node = calloc(1, sizeof(object_node_t));
	new_node->object = obj;
	new_node->next = inner;
	*node = new_node;
}

void* object_node_pop(object_node_t** node) {
	object_node_t* inner = *node;
	if (inner != NULL) {
		*node = inner->next;
		inner->next = NULL;
	}
	return inner;
}

struct object_list {
	void* data;
	object_node_t* nodes;
};

typedef struct object_list object_list_t;

// edge --- v    v    v   v
//          -e e
//

object_list_t* object_list_new() {
	return calloc(1, sizeof(object_list_t));
}

void object_list_del(object_list_t* list) {
	free(list);
}

void* object_list_get_ptr(const object_list_t* list, const void* obj) {
	const object_node_t* current = list->nodes;
	while (current != NULL) {
		if (current->object == obj) {
			return current->object;
		}
		current = current->next;
	}
	return NULL;
}

void* object_list_get_fn(const object_list_t* list, int (*fn)(void*, void*), void* fnarg) {
	const object_node_t* current = list->nodes;
	while (current != NULL) {
		if (fn(current->object, fnarg)) {
			return current->object;
		}
		current = current->next;
	}
	return NULL;
}

void* object_list_remove_fn(object_list_t* list, int (*fn)(void*, void*), void* fnarg) {
	object_node_t* current = list->nodes;
	object_node_t* before = current;
	while (current != NULL) {
		if (fn(current->object, fnarg)) {
			break;
		}
		before = current;
		current = current->next;
	}
	if (current == NULL) {
		return NULL;
	} else if (before == current) {
		list->nodes = current->next;
	} else {
		before->next = current->next;
	}
	return current;
}

void* object_list_add_fn(object_list_t* list, void* obj, int (*fn)(void*, void*), void* fnarg) {
	void* got = object_list_get_fn(list, fn, fnarg); // todo, maybe not needed?
	if (got == NULL) {
		object_node_t* new_node = calloc(1, sizeof(object_node_t));
		new_node->object = obj;
		new_node->next = list->nodes;
		list->nodes = new_node;
		got = obj;
	}
	return got;
}

void* object_list_add_ptr(object_list_t* list, void* obj) {
	void* got = object_list_get_ptr(list, obj); // todo, maybe not needed?
	if (got == NULL) {
		object_node_t* new_node = calloc(1, sizeof(object_node_t));
		new_node->object = obj;
		new_node->next = list->nodes;
		list->nodes = new_node;
		got = obj;
	}
	return got;
}

void* object_list_add(object_list_t* list, void* obj) {
	object_node_t* new_node = calloc(1, sizeof(object_node_t));
	new_node->object = obj;
	new_node->next = list->nodes;
	list->nodes = new_node;
	return new_node;
}

int graph_node_eq_label_prd(void* obj, void* argtest) {
	object_list_t* lst = (object_list_t*)obj;
	const kv_dict_t* comp = (const kv_dict_t*)argtest;
	return kv_dict_eq_field(lst->data, comp, GRAPH_LABEL_FIELD);
}

int graph_node_eq_multi_prd(void* obj, void* argtest) {
	object_list_t* lst = (object_list_t*)obj;
	const kv_dict_t* comp = (const kv_dict_t*)argtest;
	return kv_dict_eq_sub(lst->data, comp);
}

int graph_node_gather_any_prd(void* obj, void* argument) {
	return 1;
}

enum query_op {
	QUERY_OP_MATCH,
	QUERY_OP_GATHER,
	QUERY_OP_WRITE_OVER
};

typedef enum query_op query_op_t;

enum query_result {
	QUERY_RESULT_FAIL,
	QUERY_RESULT_PASS,
	QUERY_RESULT_PASS_GATHER
};

typedef enum query_result query_result_t;

struct query {
	void* argument;
	int (*fnc)(void*, void*);
	query_op_t op;
	struct query* next;
};

typedef struct query query_t;

void query_put(query_t** q, int (*fnc)(void*, void*), void* argument, query_op_t op) {
	query_t* inner = *q;
	query_t* new_qnode = calloc(1, sizeof(query_t));
	new_qnode->fnc = fnc;
	new_qnode->argument = argument;
	new_qnode->op = op;
	new_qnode->next = inner;
	*q = new_qnode;
}

size_t query_length(const query_t* q) {
	size_t len = 0;
	while (q != NULL) {
		++len;
		q = q->next;
	}
	return len;
}

query_result_t query_process_node(const query_t* q, object_list_t* gnode) {
	int qfunc_result = q->fnc(gnode, q->argument);
	if (qfunc_result) {
		switch(q->op) {
		case QUERY_OP_MATCH:
			//printf("Returning a match!\n");
			return QUERY_RESULT_PASS;
			break;
		case QUERY_OP_GATHER:
			//printf("Returning a gather!\n");
			return QUERY_RESULT_PASS_GATHER;
			break;
		case QUERY_OP_WRITE_OVER:
			fprintf(stderr, "%s\n", "Unexpected write OP in read query");
			assert(0);
			break;
		default:
			assert(0);
		}
	}
	//printf("Returning failure!\n");
	return QUERY_RESULT_FAIL;
}

struct query_iter {
	query_t* query;
	query_t* write_query;
	size_t query_len;
	size_t write_query_len;
	object_list_t* graph;
	object_node_t* results;
	// These are node types because we want to increment them
	// directly relative to their parent.
	// e.g e1 is the list of the top level graph
	object_node_t* cur_e1;
	object_node_t* cur_vert;
	object_node_t* cur_e2;
};
typedef struct query_iter query_iter_t;

void query_iter_init_write(query_iter_t* it, query_t* write_query) {
	it->write_query = write_query;
	it->write_query_len = query_length(write_query);
}

int query_iter_has_write(const query_iter_t* it) {
	return it->write_query != NULL;
}

void query_iter_init(query_iter_t* it, object_list_t* g, query_t* q) {
	it->query = q;
	it->write_query = NULL;
	it->query_len = query_length(q);
	it->write_query_len = 0;
	it->graph = g;
	it->results = NULL;
	it->cur_e1 = NULL;
	it->cur_vert = NULL;
	it->cur_e2 = NULL;

	if (g != NULL) {
		it->cur_e1 = g->nodes;
		if (it->cur_e1 != NULL) {
			it->cur_vert = ((object_list_t*)it->cur_e1->object)->nodes;
			if (it->cur_vert != NULL) {
				it->cur_e2 = ((object_list_t*)it->cur_vert->object)->nodes;
			}
		}
	}
}

int query_iter_done(const query_iter_t* it) {
	return it->cur_e1 == NULL && it->cur_vert == NULL && it->cur_e2 == NULL;
}

void query_iter_inc_cur(query_iter_t* it) {
	if (it->cur_e2 != NULL) {
		it->cur_e2 = it->cur_e2->next;
		if (it->cur_e2 == NULL) {
			if (it->cur_vert != NULL) {
				it->cur_vert = it->cur_vert->next;

				if (it->cur_vert == NULL) {
					if (it->cur_e1 != NULL) {
						it->cur_e1 = it->cur_e1->next;

						if (it->cur_e1 == NULL) {
							// iteration is complete.
						} else {
							it->cur_vert = ((object_list_t*)it->cur_e1->object)->nodes;
						}
					}
				} else {
					// iterate through edges of next vert
					it->cur_e2 = ((object_list_t*)it->cur_vert->object)->nodes;
				}
			}
		}
	} else {
		assert(it->cur_vert == NULL); // can't have dangling vertices 
		if (it->cur_e1 != NULL) {
			it->cur_e1 = it->cur_e1->next;
			if (it->cur_e1 != NULL) {
				it->cur_vert = ((object_list_t*)it->cur_e1->object)->nodes;
				if (it->cur_vert != NULL) {
					it->cur_e2 = ((object_list_t*)it->cur_vert->object)->nodes;
					assert(it->cur_e2 != NULL); // no dangling verts
				}

			}
		}
	}
}

void query_iter_process(query_iter_t* it) {
	query_result_t e1_res = QUERY_RESULT_FAIL;
	object_list_t* e1_obj;
	query_result_t vert_res = QUERY_RESULT_FAIL;
	object_list_t* vert_obj;
	query_result_t e2_res = QUERY_RESULT_FAIL;
	object_list_t* e2_obj;
	if (it->cur_e1 != NULL) {
		e1_obj = ((object_list_t*)it->cur_e1->object);
		e1_res = query_process_node(it->query, e1_obj);
		if (e1_res == QUERY_RESULT_FAIL) {
			goto query_increment_routine;
		}
		if (it->cur_vert != NULL) {
			vert_obj = ((object_list_t*)it->cur_vert->object);
			vert_res = query_process_node(it->query->next, vert_obj);
			if (vert_res == QUERY_RESULT_FAIL) {
				goto query_increment_routine;
			}
			if (it->cur_e2 != NULL) {
				e2_obj = ((object_list_t*)it->cur_e2->object);
				e2_res = query_process_node(it->query->next->next, e2_obj);
				if (e2_res == QUERY_RESULT_FAIL)
					goto query_increment_routine;
			} else {
				if (it->query_len != 2)
					goto query_increment_routine;
			}
		} else {
			if (it->query_len != 1)
				goto query_increment_routine;
		}
	} else {
		goto query_increment_routine;
	}

	if (e1_res == QUERY_RESULT_PASS_GATHER) {
		object_node_put(&(it->results), e1_obj);
	}

	if (vert_res == QUERY_RESULT_PASS_GATHER) {
		object_node_put(&(it->results), vert_obj);
	}

	if (e2_res == QUERY_RESULT_PASS_GATHER) {
		object_node_put(&(it->results), e2_obj);
	}

query_increment_routine:
	query_iter_inc_cur(it);
}

/*void query_iter_do_writes(query_iter_t* it) {
	if (!query_iter_has_write(it))
		return;
	object_node_t* result_ptr = it->results;
	const query_t* wptr = it->write_query;
	while (result_ptr != NULL) {
		while (wptr != NULL) {
			wptr = wptr->next;
		}
		wptr = it->write_query;
	}
}*/

void query_iter_run_all(query_iter_t* it, object_list_t* g, query_t* q) {
	query_iter_init(it, g, q);
	while (!query_iter_done(it)) {
		query_iter_process(it);
	}
}

// graph level abstraction


void graph_nodes_print(const object_list_t* list, int newline) {
	printf("{");
	printf("\"data\":");
	kv_dict_print(list->data, 0);
	printf(", ");
	const object_node_t* children = list->nodes;
	while (children != NULL) {
		graph_nodes_print(children->object, 0);
		children = children->next;
		printf(", ");
	}
	if (newline)
		printf("}\n");
	else
		printf("}");
}

object_list_t* graph_root_create() {
	object_list_t* graph_root = object_list_new();
	kv_dict_put((kv_dict_t**)&(graph_root->data), GRAPH_ROOT_NAME, GRAPH_ROOT_VAL);
	return graph_root;
}

int graph_node_is_root(const object_list_t* target) {
	const kv_dict_t* got = kv_dict_get(target->data, GRAPH_ROOT_NAME);
	return strcmp(got->val, GRAPH_ROOT_VAL) == 0;
}

object_list_t* graph_node_create(const char* node_label) {
	object_list_t* graph_node = object_list_new();
	kv_dict_put((kv_dict_t**)&(graph_node->data), GRAPH_LABEL_FIELD, node_label);
	return graph_node;
}

object_list_t* graph_node_create_kv(const char* node_label, size_t amnt, ...) {
	object_list_t* graph_node = object_list_new();
	if (node_label != NULL) {
		kv_dict_put((kv_dict_t**)&(graph_node->data), GRAPH_LABEL_FIELD, node_label);
	}
	va_list args;
	va_start(args, amnt);
	while (amnt--) {
		const char* skey = va_arg(args, const char*);
		const char* sval = va_arg(args, const char*);
		kv_dict_put((kv_dict_t**)&(graph_node->data), skey, sval);
	}
	va_end(args);
	return graph_node;
}

void graph_node_flatten(object_list_t* target, object_list_t* flat_list) {
	if (target != NULL) {
		object_node_t* children = target->nodes;
		while (children != NULL) {
			graph_node_flatten(children->object, flat_list);
			children = children->next;
		}
		object_list_add_ptr(flat_list, target);
	}
}

size_t graph_node_destroy(object_list_t* target) {
	size_t total = 0;
	object_list_t* temp_list = object_list_new();
	graph_node_flatten(target, temp_list);
	object_node_t* flat_ptr = temp_list->nodes;
	while (flat_ptr != NULL) {
		++total;
		object_list_t* list_cast = (object_list_t*)(flat_ptr->object);
		kv_dict_destroy(list_cast->data);
		free(list_cast);
		object_node_t* flat_copy = flat_ptr;
		flat_ptr = flat_ptr->next;
		free(flat_copy);
	}
	object_list_del(temp_list);
	return total;
}

object_list_t* graph_target_find(const object_list_t* target, const object_list_t* match) {
	return object_list_get_fn(target, &graph_node_eq_label_prd, match->data);
}

object_list_t* graph_target_sub_add(object_list_t* target, object_list_t* sub) {
	return object_list_add_fn(target, sub, &graph_node_eq_label_prd, sub->data);
}

object_list_t* graph_edge_vert_edge_add(object_list_t* edge, object_list_t* vert, object_list_t* edge2) {
	object_list_t* got_vert = object_list_add_fn(edge, vert, &graph_node_eq_label_prd, vert->data);
	return object_list_add_fn(got_vert, edge2, &graph_node_eq_label_prd, edge2->data);
}

object_list_t* graph_root_rel_add(object_list_t* root, object_list_t* edge, object_list_t* vert, object_list_t* edge2) {
	object_list_t* got_edge = object_list_add_fn(root, edge, &graph_node_eq_label_prd, edge->data);
	object_list_t* got_edge2 = object_list_add_fn(root, edge2, &graph_node_eq_label_prd, edge2->data);
	object_list_t* got_vert = object_list_add_fn(got_edge, vert, &graph_node_eq_label_prd, vert->data);
	return object_list_add_fn(got_vert, got_edge2, &graph_node_eq_label_prd, got_edge2->data);
}

// Confirm if e - v - e relationship exists or not
const object_list_t* graph_edge_vert_edge_get(const object_list_t* edge, 
	                                          const object_list_t* vert, 
	                                          const object_list_t* edge2) {
	object_list_t* vert_res = object_list_get_fn(edge, &graph_node_eq_label_prd, vert->data);
	if (vert_res != NULL) {
		return object_list_get_fn(vert_res, &graph_node_eq_label_prd, edge2->data);
	}
	return NULL;
}



static void test_edge_v_edge(void) {
	object_list_t* elist = object_list_new();
	object_list_t* eliste = object_list_new();
	object_list_t* vlist = object_list_add_ptr(elist, object_list_new());
	object_list_t* elist2 = object_list_add_ptr(vlist, elist);
	object_list_t* elist3 = object_list_add_ptr(vlist, eliste);
	assert(elist == elist2);
	assert(eliste == elist3);
	assert(elist->nodes != NULL);
	assert(elist->nodes->object == vlist);

	object_list_t* casted = (object_list_t*)elist->nodes->object;
	assert(casted->nodes != NULL);
	assert(casted->nodes->object == eliste);

	assert(casted->nodes->next != NULL);
	assert(casted->nodes->next->object == elist2);

	object_list_t* vlist2 = object_list_add_ptr(eliste, object_list_new());
	object_list_t* elist4 = object_list_add_ptr(vlist2, elist);

	assert(elist4->nodes->object == elist->nodes->object);
}

static int fn_pred_test(void* obj, void* argtest) {
	return ((object_list_t*)obj)->data == argtest;
}

static void test_fn_get(void) {
	object_list_t* elist = object_list_new();
	object_list_t* vlist = object_list_add_ptr(elist, object_list_new());
	object_list_t* got = object_list_get_fn(elist, &fn_pred_test, NULL);
	assert(got != NULL && got == vlist);
}

static void test_fn_add(void) {
	object_list_t* elist = object_list_new();
	object_list_t* test = object_list_new();
	object_list_t* vlist = object_list_add_ptr(elist, object_list_new());
	object_list_t* got = object_list_add_fn(elist, test, &fn_pred_test, NULL);
	assert(got != NULL && got == vlist && got != test);
}

static void test_kv_dict_put(void) {
	kv_dict_t* d = NULL;
	kv_dict_put(&d, "foo", "bar");
	assert(strcmp(kv_dict_get(d, "foo")->val, "bar") == 0);
	kv_dict_put(&d, "foo", "moo");
	assert(strcmp(kv_dict_get(d, "foo")->val, "moo") == 0);
	kv_dict_put(&d, "doo", "bar");
	assert(strcmp(kv_dict_get(d, "doo")->val, "bar") == 0);
}

static void test_kv_dict_remove(void) {
	kv_dict_t* d = NULL;
	kv_dict_put(&d, "foo", "bar");
	kv_dict_put(&d, "moo", "bar");
	kv_dict_remove(&d, "foo");
	assert(kv_dict_get(d, "foo") == NULL);
}

static void test_kv_dict_eq(void) {
	kv_dict_t* d = NULL;
	kv_dict_t* c = NULL;
	kv_dict_put(&d, "foo", "bar");
	kv_dict_put(&c, "foo", "bar");
	assert(kv_dict_eq_all(c, d));
	kv_dict_put(&c, "moo", "bar");
	assert(!kv_dict_eq_all(c, d));
	kv_dict_put(&d, "moo", "bar");
	kv_dict_put(&c, "Apple", "1");
	assert(kv_dict_eq_sub(c, d));
}

static void test_kv_dict_destroy(void) {
	kv_dict_t* d = NULL;
	kv_dict_put(&d, "foo", "bar");
	kv_dict_put(&d, "goo", "bar");
	kv_dict_put(&d, "boo", "bar");
	kv_dict_destroy(d);
}

static void test_kv_dict_write_into(void) {
	kv_dict_t* d = NULL;
	kv_dict_t* c = NULL;
	kv_dict_put(&d, "foo", "bar");
	kv_dict_put(&d, "moo", "bar");
	kv_dict_put(&c, "foo", "3");
	kv_dict_put(&c, "moo", "4");
	kv_dict_write_into(&d, c, 1);
	assert(strcmp(kv_dict_get(d, "foo")->val, "3") == 0);
	assert(strcmp(kv_dict_get(d, "moo")->val, "4") == 0);
	kv_dict_destroy(d);
	kv_dict_destroy(c);
}

static void test_kv_dict_copy(void) {
	kv_dict_t* d = NULL;
	kv_dict_t* c = NULL;
	kv_dict_put(&d, "foo", "bar");
	kv_dict_put(&d, "moo", "bar");
	kv_dict_copy(&c, d);
	assert(strcmp(kv_dict_get(c, "foo")->val, "bar") == 0);
	assert(strcmp(kv_dict_get(c, "moo")->val, "bar") == 0);
	kv_dict_destroy(d);
	kv_dict_destroy(c);
}

static void test_graph_create_node(void) {
	object_list_t* g = graph_node_create("Person");
	kv_dict_t* data_dict = g->data;
	assert(data_dict != NULL);
	assert(strcmp(data_dict->key, GRAPH_LABEL_FIELD) == 0);
	kv_dict_print(data_dict, 1);
	assert(graph_node_destroy(g) == 1);
}

static void test_graph_create_node_kv(void) {
	object_list_t* g = graph_node_create_kv(NULL, 2, "foo", "bar", "name", "1");
	kv_dict_t* data_dict = g->data;
	assert(data_dict != NULL);
	const kv_dict_t* lookup = kv_dict_get(data_dict, "foo");
	assert(lookup != NULL && strcmp(lookup->val, "bar") == 0);
	const kv_dict_t* lookup2 = kv_dict_get(data_dict, "name");
	assert(lookup2 != NULL && strcmp(lookup2->val, "1") == 0);
	assert(graph_node_destroy(g) == 1);
}

static void test_graph_edge_vert_add(void) {
	object_list_t* g = graph_node_create("Person");
	object_list_t* v = graph_node_create("Likes");
	object_list_t* result =  graph_target_sub_add(g, v);
	assert(result != NULL && result == v);
	assert(g->nodes->object == v);
	assert(graph_node_destroy(g) == 2);
}

static void test_graph_edge_vert_edge_methods(void) {
	object_list_t* g = graph_node_create("Person");
	object_list_t* v = graph_node_create("Likes");
	object_list_t* v2 = graph_node_create("Likes");
	object_list_t* e1 = graph_node_create("Tom");
	object_list_t* result =  graph_edge_vert_edge_add(g, v, e1);
	assert(result != NULL && result == e1);
	assert(g->nodes->object == v);
	// test for not overwriting
	object_list_t* result2 =  graph_target_sub_add(g, v2);
	assert(result2 == v);
	const object_list_t* rel_test = graph_edge_vert_edge_get(g, v, e1);
	assert(rel_test == e1);
	assert(graph_node_destroy(g) == 3);
	assert(graph_node_destroy(v2) == 1);
}

static void test_graph_target_find(void) {
	object_list_t* g = graph_root_create();
	object_list_t* v = graph_node_create("Bob");
	object_list_t* result =  graph_target_sub_add(g, v);
	object_list_t* fresult = graph_target_find(g, v);
	assert(result == fresult && fresult == v);
	assert(graph_node_destroy(g) == 2);
}

static void test_graph_root_rel_add(void) {
	object_list_t* g = graph_root_create();
	object_list_t* e1 = graph_node_create("Tom");
	object_list_t* v = graph_node_create("Likes");
	object_list_t* e2 = graph_node_create("Bob");

	object_list_t* result =  graph_root_rel_add(g, e1, v, e2);
	assert(result != NULL && result == e2);
	assert(g->nodes->object == e2);

	assert(graph_node_destroy(g) == 4);
}

static void test_query_iter_inc(void) {
	query_iter_t it;
	object_list_t* g = graph_root_create();
	object_list_t* e1 = graph_node_create("Tom");
	object_list_t* v = graph_node_create("Likes");
	object_list_t* e2 = graph_node_create("Bob");
	object_list_t* e3 = graph_node_create("Bruce");

	object_list_t* result =  graph_root_rel_add(g, e1, v, e2);
	object_list_t* resultv = graph_root_rel_add(g, e1, v, e3);
	graph_nodes_print(g, 1);

	assert(result == e2 && resultv == e3);

	query_iter_init(&it, g, NULL);
	printf("g %p e1 %p v %p e2 %p e3 %p\n", g, e1, v, e2, e3);
	printf("cur e1 %p\n", it.cur_e1->object);
	printf("cur vert %p\n", it.cur_vert);
	printf("cur e2 %p\n", it.cur_e2);
	assert(it.cur_e1->object == e3);
	assert(it.cur_vert == NULL);
	assert(it.cur_e2 == NULL);

	query_iter_inc_cur(&it);
	assert(it.cur_e1->object == e2);
	assert(it.cur_vert == NULL);
	assert(it.cur_e2 == NULL);
	//printf("cur e1 %p\n", it.cur_e1->object);
	//printf("cur vert %p\n", it.cur_vert);
	//printf("cur e2 %p\n", it.cur_e2);

	query_iter_inc_cur(&it);
	//printf("cur e1 %p\n", it.cur_e1->object);
	//printf("cur vert %p\n", it.cur_vert->object);
	//printf("cur e2 %p\n", it.cur_e2->object);
	assert(it.cur_e1->object == e1);
	assert(it.cur_vert->object == v);
	assert(it.cur_e2->object == e3);

	query_iter_inc_cur(&it);
	//printf("cur e1 %p\n", it.cur_e1->object);
	//printf("cur vert %p\n", it.cur_vert->object);
	//printf("cur e2 %p\n", it.cur_e2->object);
	assert(it.cur_e1->object == e1);
	assert(it.cur_vert->object == v);
	assert(it.cur_e2->object == e2);

	query_iter_inc_cur(&it);
	assert(query_iter_done(&it));

	assert(graph_node_destroy(g) == 5);
}

static void test_query_process(void) {
	query_iter_t it;
	query_t* qpoint = NULL;
	kv_dict_t* d1 = NULL;
	kv_dict_put(&d1, GRAPH_LABEL_FIELD, "Tom");
	kv_dict_t* d2 = NULL;
	kv_dict_put(&d2, GRAPH_LABEL_FIELD, "Likes");
	
	query_put(&qpoint, &graph_node_gather_any_prd, NULL, QUERY_OP_GATHER);
	query_put(&qpoint, &graph_node_eq_label_prd, d2, QUERY_OP_MATCH);
	query_put(&qpoint, &graph_node_eq_label_prd, d1, QUERY_OP_MATCH);

	object_list_t* g = graph_root_create();
	object_list_t* e1 = graph_node_create("Tom");
	object_list_t* v = graph_node_create("Likes");
	object_list_t* e2 = graph_node_create("Bob");
	object_list_t* e3 = graph_node_create("Bruce");

	object_list_t* result =  graph_root_rel_add(g, e1, v, e2);
	object_list_t* resultv = graph_root_rel_add(g, e1, v, e3);

	query_iter_init(&it, g, qpoint);
	printf("------ g %p e1 %p v %p e2 %p e3 %p\n", g, e1, v, e2, e3);
	//printf("cur e1 %p\n", it.cur_e1->object);
	assert(it.query == qpoint);
	assert(it.results == NULL);
	assert(it.cur_e1 != NULL && it.cur_e1->object == e3);

	query_iter_process(&it);
	//printf("cur e1 %p\n", it.cur_e1->object);
	assert(it.results == NULL);
	assert(it.cur_e1 != NULL && it.cur_e1->object == e2);

	query_iter_process(&it);
	//printf("cur e1 %p\n", it.cur_e1->object);
	assert(it.results == NULL);
	assert(it.cur_e1 != NULL && it.cur_e1->object == e1);

	assert(it.cur_e2->object == e3);
	query_iter_process(&it);
	assert(it.results != NULL);
	assert(it.cur_e2->object == e2);
	query_iter_process(&it);
	assert(query_iter_done(&it));

	assert(it.results->object == e2);
	assert(it.results->next != NULL && it.results->next->object == e3);

	assert(graph_node_destroy(g) == 5);
}

static void test_query_process_mutli_field(void) {
	query_iter_t it;
	query_t* qpoint = NULL;
	kv_dict_t* d1 = NULL;
	kv_dict_put(&d1, GRAPH_LABEL_FIELD, "Person");
	kv_dict_put(&d1, "name", "Tom");
	
	query_put(&qpoint, &graph_node_gather_any_prd, NULL, QUERY_OP_GATHER);
	query_put(&qpoint, &graph_node_gather_any_prd, NULL, QUERY_OP_MATCH);
	query_put(&qpoint, &graph_node_eq_multi_prd, d1, QUERY_OP_MATCH);

	object_list_t* g = graph_root_create();
	object_list_t* e1 = graph_node_create_kv("Person", 1, "name", "Tom");
	object_list_t* v = graph_node_create("Likes");
	object_list_t* e2 = graph_node_create("Bob");

	object_list_t* result =  graph_root_rel_add(g, e1, v, e2);

	query_iter_init(&it, g, qpoint);
	printf("------ g %p e1 %p v %p e2 %p \n", g, e1, v, e2);
	//printf("cur e1 %p\n", it.cur_e1->object);
	assert(it.cur_e1 != NULL && it.cur_e1->object == e2);

	query_iter_process(&it);
	assert(it.results == NULL);
	assert(it.cur_e1 != NULL && it.cur_e1->object == e1);

	query_iter_process(&it);
	assert(it.results != NULL);

	assert(it.results->object == e2);
	assert(query_iter_done(&it));

	assert(graph_node_destroy(g) == 4);

}

int main(int argc, char const *argv[])
{
	test_edge_v_edge();
	test_fn_get();
	test_fn_add();
	test_kv_dict_put();
	test_kv_dict_remove();
	test_kv_dict_eq();
	test_kv_dict_destroy();
	test_kv_dict_write_into();
	test_kv_dict_copy();
	test_graph_create_node();
	test_graph_create_node_kv();
	test_graph_edge_vert_add();
	test_graph_edge_vert_edge_methods();
	test_graph_target_find();
	test_graph_root_rel_add();
	test_query_iter_inc();

	test_query_process();
	test_query_process_mutli_field();
	return 0;
}