Update libucl to git version 8d3b186

9 files changed, 584 insertions, 202 deletions

diff --git a/contrib/libucl/src/Makefile.am b/contrib/libucl/src/Makefile.am
index 417d34e..c3f0c9f 100644
--- a/contrib/libucl/src/Makefile.am
+++ b/contrib/libucl/src/Makefile.am
@@ -1,6 +1,7 @@
 libucl_common_cflags=	-I$(top_srcdir)/src \
 			-I$(top_srcdir)/include \
 			-I$(top_srcdir)/uthash \
+			-I$(top_srcdir)/klib \
 			-Wall -W -Wno-unused-parameter -Wno-pointer-sign
 lib_LTLIBRARIES=	libucl.la
 libucl_la_SOURCES=	ucl_emitter.c \
diff --git a/contrib/libucl/src/ucl_emitter.c b/contrib/libucl/src/ucl_emitter.c
index 8134d09..9ddf358 100644
--- a/contrib/libucl/src/ucl_emitter.c
+++ b/contrib/libucl/src/ucl_emitter.c
@@ -250,6 +250,7 @@ ucl_emitter_common_start_array (struct ucl_emitter_context *ctx,
 		const ucl_object_t *obj, bool print_key, bool compact)
 {
 	const ucl_object_t *cur;
+	ucl_object_iter_t iter = NULL;
 	const struct ucl_emitter_functions *func = ctx->func;
 	bool first = true;
 
@@ -266,18 +267,22 @@ ucl_emitter_common_start_array (struct ucl_emitter_context *ctx,
 
 	if (obj->type == UCL_ARRAY) {
 		/* explicit array */
-		cur = obj->value.av;
+		while ((cur = ucl_iterate_object (obj, &iter, true)) != NULL) {
+			ucl_emitter_common_elt (ctx, cur, first, false, compact);
+			first = false;
+		}
 	}
 	else {
 		/* implicit array */
 		cur = obj;
+		while (cur) {
+			ucl_emitter_common_elt (ctx, cur, first, false, compact);
+			first = false;
+			cur = cur->next;
+		}
 	}
 
-	while (cur) {
-		ucl_emitter_common_elt (ctx, cur, first, false, compact);
-		first = false;
-		cur = cur->next;
-	}
+
 }
 
 /**
diff --git a/contrib/libucl/src/ucl_emitter_utils.c b/contrib/libucl/src/ucl_emitter_utils.c
index da41209..91cad78 100644
--- a/contrib/libucl/src/ucl_emitter_utils.c
+++ b/contrib/libucl/src/ucl_emitter_utils.c
@@ -289,6 +289,7 @@ ucl_fd_append_character (unsigned char c, size_t len, void *ud)
 		else {
 			memset (buf, c, len);
 			if (write (fd, buf, len) == -1) {
+				free(buf);
 				return -1;
 			}
 			free (buf);
diff --git a/contrib/libucl/src/ucl_hash.c b/contrib/libucl/src/ucl_hash.c
index ea55491..275e84d 100644
--- a/contrib/libucl/src/ucl_hash.c
+++ b/contrib/libucl/src/ucl_hash.c
@@ -23,119 +23,331 @@
 
 #include "ucl_internal.h"
 #include "ucl_hash.h"
-#include "utlist.h"
+#include "khash.h"
+#include "kvec.h"
+
+struct ucl_hash_elt {
+	const ucl_object_t *obj;
+	size_t ar_idx;
+};
+
+struct ucl_hash_struct {
+	void *hash;
+	kvec_t(const ucl_object_t *) ar;
+	bool caseless;
+};
+
+static inline uint32_t
+ucl_hash_func (const ucl_object_t *o)
+{
+	return XXH32 (o->key, o->keylen, 0xdeadbeef);
+}
+
+static inline int
+ucl_hash_equal (const ucl_object_t *k1, const ucl_object_t *k2)
+{
+	if (k1->keylen == k2->keylen) {
+		return strncmp (k1->key, k2->key, k1->keylen) == 0;
+	}
+
+	return 0;
+}
+
+KHASH_INIT (ucl_hash_node, const ucl_object_t *, struct ucl_hash_elt, 1,
+		ucl_hash_func, ucl_hash_equal)
+
+static inline uint32_t
+ucl_hash_caseless_func (const ucl_object_t *o)
+{
+	void *xxh = XXH32_init (0xdeadbeef);
+	char hash_buf[64], *c;
+	const char *p;
+	ssize_t remain = o->keylen;
+
+	p = o->key;
+	c = &hash_buf[0];
+
+	while (remain > 0) {
+		*c++ = tolower (*p++);
+
+		if (c - &hash_buf[0] == sizeof (hash_buf)) {
+			XXH32_update (xxh, hash_buf, sizeof (hash_buf));
+			c = &hash_buf[0];
+		}
+		remain --;
+	}
+
+	if (c - &hash_buf[0] != 0) {
+		XXH32_update (xxh, hash_buf, c - &hash_buf[0]);
+	}
+
+	return XXH32_digest (xxh);
+}
+
+static inline int
+ucl_hash_caseless_equal (const ucl_object_t *k1, const ucl_object_t *k2)
+{
+	if (k1->keylen == k2->keylen) {
+		return strncasecmp (k1->key, k2->key, k1->keylen) == 0;
+	}
+
+	return 0;
+}
+
+KHASH_INIT (ucl_hash_caseless_node, const ucl_object_t *, struct ucl_hash_elt, 1,
+		ucl_hash_caseless_func, ucl_hash_caseless_equal)
 
 ucl_hash_t*
-ucl_hash_create (void)
+ucl_hash_create (bool ignore_case)
 {
 	ucl_hash_t *new;
 
 	new = UCL_ALLOC (sizeof (ucl_hash_t));
 	if (new != NULL) {
-		new->buckets = NULL;
+		kv_init (new->ar);
+
+		new->caseless = ignore_case;
+		if (ignore_case) {
+			khash_t(ucl_hash_caseless_node) *h = kh_init (ucl_hash_caseless_node);
+			new->hash = (void *)h;
+		}
+		else {
+			khash_t(ucl_hash_node) *h = kh_init (ucl_hash_node);
+			new->hash = (void *)h;
+		}
 	}
 	return new;
 }
 
 void ucl_hash_destroy (ucl_hash_t* hashlin, ucl_hash_free_func *func)
 {
-	ucl_hash_node_t *elt, *tmp;
-	const ucl_object_t *cur, *otmp;
-
-	HASH_ITER (hh, hashlin->buckets, elt, tmp) {
-		HASH_DELETE (hh, hashlin->buckets, elt);
-		if (func) {
-			DL_FOREACH_SAFE (elt->data, cur, otmp) {
-				/* Need to deconst here */
-				func (__DECONST (ucl_object_t *, cur));
+	const ucl_object_t *cur, *tmp;
+
+	if (hashlin == NULL) {
+		return;
+	}
+
+	if (func != NULL) {
+		/* Iterate over the hash first */
+		khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *)
+				hashlin->hash;
+		khiter_t k;
+
+		for (k = kh_begin (h); k != kh_end (h); ++k) {
+			if (kh_exist (h, k)) {
+				cur = (kh_value (h, k)).obj;
+				while (cur != NULL) {
+					tmp = cur->next;
+					func (__DECONST (ucl_object_t *, cur));
+					cur = tmp;
+				}
 			}
 		}
-		UCL_FREE (sizeof (ucl_hash_node_t), elt);
 	}
-	UCL_FREE (sizeof (ucl_hash_t), hashlin);
+
+	if (hashlin->caseless) {
+		khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *)
+			hashlin->hash;
+		kh_destroy (ucl_hash_caseless_node, h);
+	}
+	else {
+		khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *)
+			hashlin->hash;
+		kh_destroy (ucl_hash_node, h);
+	}
+
+	kv_destroy (hashlin->ar);
+	UCL_FREE (sizeof (*hashlin), hashlin);
 }
 
 void
 ucl_hash_insert (ucl_hash_t* hashlin, const ucl_object_t *obj,
 		const char *key, unsigned keylen)
 {
-	ucl_hash_node_t *node;
+	khiter_t k;
+	int ret;
+	struct ucl_hash_elt *elt;
+
+	if (hashlin == NULL) {
+		return;
+	}
 
-	node = UCL_ALLOC (sizeof (ucl_hash_node_t));
-	node->data = obj;
-	HASH_ADD_KEYPTR (hh, hashlin->buckets, key, keylen, node);
+	if (hashlin->caseless) {
+		khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *)
+				hashlin->hash;
+		k = kh_put (ucl_hash_caseless_node, h, obj, &ret);
+		if (ret > 0) {
+			elt = &kh_value (h, k);
+			kv_push (const ucl_object_t *, hashlin->ar, obj);
+			elt->obj = obj;
+			elt->ar_idx = kv_size (hashlin->ar) - 1;
+		}
+	}
+	else {
+		khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *)
+				hashlin->hash;
+		k = kh_put (ucl_hash_node, h, obj, &ret);
+		if (ret > 0) {
+			elt = &kh_value (h, k);
+			kv_push (const ucl_object_t *, hashlin->ar, obj);
+			elt->obj = obj;
+			elt->ar_idx = kv_size (hashlin->ar) - 1;
+		}
+	}
 }
 
 void ucl_hash_replace (ucl_hash_t* hashlin, const ucl_object_t *old,
 		const ucl_object_t *new)
 {
-	ucl_hash_node_t *node;
+	khiter_t k;
+	int ret;
+	struct ucl_hash_elt elt, *pelt;
 
-	HASH_FIND (hh, hashlin->buckets, old->key, old->keylen, node);
-	if (node != NULL) {
-		/* Direct replacement */
-		node->data = new;
-		node->hh.key = new->key;
-		node->hh.keylen = new->keylen;
+	if (hashlin == NULL) {
+		return;
+	}
+
+	if (hashlin->caseless) {
+		khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *)
+				hashlin->hash;
+		k = kh_put (ucl_hash_caseless_node, h, old, &ret);
+		if (ret == 0) {
+			elt = kh_value (h, k);
+			kh_del (ucl_hash_caseless_node, h, k);
+			k = kh_put (ucl_hash_caseless_node, h, new, &ret);
+			pelt = &kh_value (h, k);
+			pelt->obj = new;
+			pelt->ar_idx = elt.ar_idx;
+			kv_A (hashlin->ar, elt.ar_idx) = new;
+		}
+	}
+	else {
+		khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *)
+				hashlin->hash;
+		k = kh_put (ucl_hash_node, h, old, &ret);
+		if (ret == 0) {
+			elt = kh_value (h, k);
+			kh_del (ucl_hash_node, h, k);
+			k = kh_put (ucl_hash_node, h, new, &ret);
+			pelt = &kh_value (h, k);
+			pelt->obj = new;
+			pelt->ar_idx = elt.ar_idx;
+			kv_A (hashlin->ar, elt.ar_idx) = new;
+		}
 	}
 }
 
+struct ucl_hash_real_iter {
+	const ucl_object_t **cur;
+	const ucl_object_t **end;
+};
+
 const void*
 ucl_hash_iterate (ucl_hash_t *hashlin, ucl_hash_iter_t *iter)
 {
-	ucl_hash_node_t *elt = *iter;
+	struct ucl_hash_real_iter *it = (struct ucl_hash_real_iter *)(*iter);
+	const ucl_object_t *ret = NULL;
 
-	if (elt == NULL) {
-		if (hashlin == NULL || hashlin->buckets == NULL) {
-			return NULL;
-		}
-		elt = hashlin->buckets;
-		if (elt == NULL) {
-			return NULL;
-		}
+	if (hashlin == NULL) {
+		return NULL;
+	}
+
+	if (it == NULL) {
+		it = UCL_ALLOC (sizeof (*it));
+		it->cur = &hashlin->ar.a[0];
+		it->end = it->cur + hashlin->ar.n;
+	}
+
+	if (it->cur < it->end) {
+		ret = *it->cur++;
 	}
-	else if (elt == hashlin->buckets) {
+	else {
+		UCL_FREE (sizeof (*it), it);
+		*iter = NULL;
 		return NULL;
 	}
 
-	*iter = elt->hh.next ? elt->hh.next : hashlin->buckets;
-	return elt->data;
+	*iter = it;
+
+	return ret;
 }
 
 bool
-ucl_hash_iter_has_next (ucl_hash_iter_t iter)
+ucl_hash_iter_has_next (ucl_hash_t *hashlin, ucl_hash_iter_t iter)
 {
-	ucl_hash_node_t *elt = iter;
+	struct ucl_hash_real_iter *it = (struct ucl_hash_real_iter *)(iter);
 
-	return (elt == NULL || elt->hh.prev != NULL);
+	return it->cur < it->end - 1;
 }
 
 
 const ucl_object_t*
 ucl_hash_search (ucl_hash_t* hashlin, const char *key, unsigned keylen)
 {
-	ucl_hash_node_t *found;
+	khiter_t k;
+	const ucl_object_t *ret = NULL;
+	ucl_object_t search;
+	struct ucl_hash_elt *elt;
+
+	search.key = key;
+	search.keylen = keylen;
 
 	if (hashlin == NULL) {
 		return NULL;
 	}
-	HASH_FIND (hh, hashlin->buckets, key, keylen, found);
 
-	if (found) {
-		return found->data;
+	if (hashlin->caseless) {
+		khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *)
+						hashlin->hash;
+
+		k = kh_get (ucl_hash_caseless_node, h, &search);
+		if (k != kh_end (h)) {
+			elt = &kh_value (h, k);
+			ret = elt->obj;
+		}
 	}
-	return NULL;
+	else {
+		khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *)
+						hashlin->hash;
+		k = kh_get (ucl_hash_node, h, &search);
+		if (k != kh_end (h)) {
+			elt = &kh_value (h, k);
+			ret = elt->obj;
+		}
+	}
+
+	return ret;
 }
 
 void
 ucl_hash_delete (ucl_hash_t* hashlin, const ucl_object_t *obj)
 {
-	ucl_hash_node_t *found;
+	khiter_t k;
+	struct ucl_hash_elt *elt;
 
-	HASH_FIND (hh, hashlin->buckets, obj->key, obj->keylen, found);
+	if (hashlin == NULL) {
+		return;
+	}
 
-	if (found) {
-		HASH_DELETE (hh, hashlin->buckets, found);
-		UCL_FREE (sizeof (ucl_hash_node_t), found);
+	if (hashlin->caseless) {
+		khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *)
+			hashlin->hash;
+
+		k = kh_get (ucl_hash_caseless_node, h, obj);
+		if (k != kh_end (h)) {
+			elt = &kh_value (h, k);
+			kv_A (hashlin->ar, elt->ar_idx) = NULL;
+			kh_del (ucl_hash_caseless_node, h, k);
+		}
+	}
+	else {
+		khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *)
+			hashlin->hash;
+		k = kh_get (ucl_hash_node, h, obj);
+		if (k != kh_end (h)) {
+			elt = &kh_value (h, k);
+			kv_A (hashlin->ar, elt->ar_idx) = NULL;
+			kh_del (ucl_hash_node, h, k);
+		}
 	}
 }
diff --git a/contrib/libucl/src/ucl_hash.h b/contrib/libucl/src/ucl_hash.h
index ddbfdba..64c83ea 100644
--- a/contrib/libucl/src/ucl_hash.h
+++ b/contrib/libucl/src/ucl_hash.h
@@ -25,15 +25,11 @@
 #define __UCL_HASH_H
 
 #include "ucl.h"
-#include "uthash.h"
 
 /******************************************************************************/
 
-typedef struct ucl_hash_node_s
-{
-	const ucl_object_t *data;
-	UT_hash_handle hh;
-} ucl_hash_node_t;
+struct ucl_hash_node_s;
+typedef struct ucl_hash_node_s ucl_hash_node_t;
 
 typedef int ucl_hash_cmp_func (const void* void_a, const void* void_b);
 typedef void ucl_hash_free_func (void *ptr);
@@ -43,16 +39,14 @@ typedef void* ucl_hash_iter_t;
 /**
  * Linear chained hashtable.
  */
-typedef struct ucl_hash_struct
-{
-	ucl_hash_node_t *buckets; /**< array of hash buckets. One list for each hash modulus. */
-} ucl_hash_t;
+struct ucl_hash_struct;
+typedef struct ucl_hash_struct ucl_hash_t;
 
 
 /**
  * Initializes the hashtable.
  */
-ucl_hash_t* ucl_hash_create (void);
+ucl_hash_t* ucl_hash_create (bool ignore_case);
 
 /**
  * Deinitializes the hashtable.
@@ -94,6 +88,6 @@ const void* ucl_hash_iterate (ucl_hash_t *hashlin, ucl_hash_iter_t *iter);
 /**
  * Check whether an iterator has next element
  */
-bool ucl_hash_iter_has_next (ucl_hash_iter_t iter);
+bool ucl_hash_iter_has_next (ucl_hash_t *hashlin, ucl_hash_iter_t iter);
 
 #endif
diff --git a/contrib/libucl/src/ucl_internal.h b/contrib/libucl/src/ucl_internal.h
index 2f75872..bdbe691 100644
--- a/contrib/libucl/src/ucl_internal.h
+++ b/contrib/libucl/src/ucl_internal.h
@@ -339,14 +339,17 @@ ucl_hash_search_obj (ucl_hash_t* hashlin, ucl_object_t *obj)
 	return (const ucl_object_t *)ucl_hash_search (hashlin, obj->key, obj->keylen);
 }
 
-static inline ucl_hash_t *
-ucl_hash_insert_object (ucl_hash_t *hashlin, const ucl_object_t *obj) UCL_WARN_UNUSED_RESULT;
+static inline ucl_hash_t * ucl_hash_insert_object (ucl_hash_t *hashlin,
+		const ucl_object_t *obj,
+		bool ignore_case) UCL_WARN_UNUSED_RESULT;
 
 static inline ucl_hash_t *
-ucl_hash_insert_object (ucl_hash_t *hashlin, const ucl_object_t *obj)
+ucl_hash_insert_object (ucl_hash_t *hashlin,
+		const ucl_object_t *obj,
+		bool ignore_case)
 {
 	if (hashlin == NULL) {
-		hashlin = ucl_hash_create ();
+		hashlin = ucl_hash_create (ignore_case);
 	}
 	ucl_hash_insert (hashlin, obj, obj->key, obj->keylen);
 
diff --git a/contrib/libucl/src/ucl_parser.c b/contrib/libucl/src/ucl_parser.c
index 0d118d8..75acba8 100644
--- a/contrib/libucl/src/ucl_parser.c
+++ b/contrib/libucl/src/ucl_parser.c
@@ -570,7 +570,7 @@ ucl_add_parser_stack (ucl_object_t *obj, struct ucl_parser *parser, bool is_arra
 		else {
 			obj->type = UCL_OBJECT;
 		}
-		obj->value.ov = ucl_hash_create ();
+		obj->value.ov = ucl_hash_create (parser->flags & UCL_PARSER_KEY_LOWERCASE);
 		parser->state = UCL_STATE_KEY;
 	}
 	else {
@@ -975,7 +975,7 @@ ucl_parser_append_elt (struct ucl_parser *parser, ucl_hash_t *cont,
 	else {
 		if ((top->flags & UCL_OBJECT_MULTIVALUE) != 0) {
 			/* Just add to the explicit array */
-			DL_APPEND (top->value.av, elt);
+			ucl_array_append (top, elt);
 		}
 		else {
 			/* Convert to an array */
@@ -984,8 +984,8 @@ ucl_parser_append_elt (struct ucl_parser *parser, ucl_hash_t *cont,
 			nobj->key = top->key;
 			nobj->keylen = top->keylen;
 			nobj->flags |= UCL_OBJECT_MULTIVALUE;
-			DL_APPEND (nobj->value.av, top);
-			DL_APPEND (nobj->value.av, elt);
+			ucl_array_append (nobj, top);
+			ucl_array_append (nobj, elt);
 			ucl_hash_insert (cont, nobj, nobj->key, nobj->keylen);
 		}
 	}
@@ -1016,6 +1016,7 @@ ucl_parse_key (struct ucl_parser *parser, struct ucl_chunk *chunk, bool *next_ke
 		ucl_chunk_skipc (chunk, p);
 		parser->prev_state = parser->state;
 		parser->state = UCL_STATE_MACRO_NAME;
+		*end_of_object = false;
 		return true;
 	}
 	while (p < chunk->end) {
@@ -1195,7 +1196,8 @@ ucl_parse_key (struct ucl_parser *parser, struct ucl_chunk *chunk, bool *next_ke
 	nobj->keylen = keylen;
 	tobj = __DECONST (ucl_object_t *, ucl_hash_search_obj (container, nobj));
 	if (tobj == NULL) {
-		container = ucl_hash_insert_object (container, nobj);
+		container = ucl_hash_insert_object (container, nobj,
+				parser->flags & UCL_PARSER_KEY_LOWERCASE);
 		nobj->prev = nobj;
 		nobj->next = NULL;
 		parser->stack->obj->len ++;
@@ -1363,14 +1365,16 @@ ucl_get_value_object (struct ucl_parser *parser)
 {
 	ucl_object_t *t, *obj = NULL;
 
+	if (parser == NULL || parser->stack == NULL || parser->stack->obj == NULL) {
+		return NULL;
+	}
+
 	if (parser->stack->obj->type == UCL_ARRAY) {
 		/* Object must be allocated */
 		obj = ucl_object_new_full (UCL_NULL, parser->chunks->priority);
-		t = parser->stack->obj->value.av;
-		DL_APPEND (t, obj);
+		t = parser->stack->obj;
+		ucl_array_append (t, obj);
 		parser->cur_obj = obj;
-		parser->stack->obj->value.av = t;
-		parser->stack->obj->len ++;
 	}
 	else {
 		/* Object has been already allocated */
diff --git a/contrib/libucl/src/ucl_schema.c b/contrib/libucl/src/ucl_schema.c
index faffe86..834b62a 100644
--- a/contrib/libucl/src/ucl_schema.c
+++ b/contrib/libucl/src/ucl_schema.c
@@ -525,15 +525,16 @@ ucl_schema_validate_array (const ucl_object_t *schema,
 	ucl_object_iter_t iter = NULL, piter = NULL;
 	bool ret = true, allow_additional = true, need_unique = false;
 	int64_t minmax;
+	unsigned int idx = 0;
 
 	while (ret && (elt = ucl_iterate_object (schema, &iter, true)) != NULL) {
 		if (strcmp (ucl_object_key (elt), "items") == 0) {
 			if (elt->type == UCL_ARRAY) {
-				found = obj->value.av;
+				found = ucl_array_head (obj);
 				while (ret && (it = ucl_iterate_object (elt, &piter, true)) != NULL) {
 					if (found) {
 						ret = ucl_schema_validate (it, found, false, err, root);
-						found = found->next;
+						found = ucl_array_find_index (obj, ++idx);
 					}
 				}
 				if (found != NULL) {
@@ -608,14 +609,14 @@ ucl_schema_validate_array (const ucl_object_t *schema,
 					ret = false;
 				}
 				else if (additional_schema != NULL) {
-					elt = first_unvalidated;
+					elt = ucl_array_find_index (obj, idx);
 					while (elt) {
 						if (!ucl_schema_validate (additional_schema, elt, false,
 								err, root)) {
 							ret = false;
 							break;
 						}
-						elt = elt->next;
+						elt = ucl_array_find_index (obj, idx ++);
 					}
 				}
 			}
@@ -741,7 +742,7 @@ ucl_schema_resolve_ref_component (const ucl_object_t *cur,
 					"reference %s is invalid, invalid item number", refc);
 			return NULL;
 		}
-		res = cur->value.av;
+		res = ucl_array_head (cur);
 		i = 0;
 		while (res != NULL) {
 			if (i == num) {
diff --git a/contrib/libucl/src/ucl_util.c b/contrib/libucl/src/ucl_util.c
index 41702e9..41e012b 100644
--- a/contrib/libucl/src/ucl_util.c
+++ b/contrib/libucl/src/ucl_util.c
@@ -24,13 +24,21 @@
 #include "ucl.h"
 #include "ucl_internal.h"
 #include "ucl_chartable.h"
+#include "kvec.h"
 
+#ifndef _WIN32
 #include <glob.h>
+#endif
 
 #ifdef HAVE_LIBGEN_H
 #include <libgen.h> /* For dirname */
 #endif
 
+typedef kvec_t(ucl_object_t *) ucl_array_t;
+
+#define UCL_ARRAY_GET(ar, obj) ucl_array_t *ar = \
+	(ucl_array_t *)((obj) != NULL ? (obj)->value.av : NULL)
+
 #ifdef HAVE_OPENSSL
 #include <openssl/err.h>
 #include <openssl/sha.h>
@@ -68,6 +76,11 @@
 #define MAP_FAILED      ((void *) -1)
 #endif
 
+#ifdef _WIN32
+#include <limits.h>
+#define NBBY CHAR_BIT
+#endif
+
 static void *ucl_mmap(char *addr, size_t length, int prot, int access, int fd, off_t offset)
 {
 	void *map = NULL;
@@ -195,15 +208,27 @@ ucl_object_dtor_unref (ucl_object_t *obj)
 static void
 ucl_object_free_internal (ucl_object_t *obj, bool allow_rec, ucl_object_dtor dtor)
 {
-	ucl_object_t *sub, *tmp;
+	ucl_object_t *tmp, *sub;
 
 	while (obj != NULL) {
 		if (obj->type == UCL_ARRAY) {
-			sub = obj->value.av;
-			while (sub != NULL) {
-				tmp = sub->next;
-				dtor (sub);
-				sub = tmp;
+			UCL_ARRAY_GET (vec, obj);
+			unsigned int i;
+
+			if (vec != NULL) {
+				for (i = 0; i < vec->n; i ++) {
+					sub = kv_A (*vec, i);
+					if (sub != NULL) {
+						tmp = sub;
+						while (sub) {
+							tmp = sub->next;
+							dtor (sub);
+							sub = tmp;
+						}
+					}
+				}
+				kv_destroy (*vec);
+				UCL_FREE (sizeof (*vec), vec);
 			}
 		}
 		else if (obj->type == UCL_OBJECT) {
@@ -455,6 +480,15 @@ ucl_parser_get_error(struct ucl_parser *parser)
 	return utstring_body(parser->err);
 }
 
+UCL_EXTERN void
+ucl_parser_clear_error(struct ucl_parser *parser)
+{
+	if (parser != NULL && parser->err != NULL) {
+		utstring_free(parser->err);
+		parser->err = NULL;
+	}
+}
+
 UCL_EXTERN bool
 ucl_pubkey_add (struct ucl_parser *parser, const unsigned char *key, size_t len)
 {
@@ -933,10 +967,10 @@ ucl_include_file (const unsigned char *data, size_t len,
 	const unsigned char *p = data, *end = data + len;
 	bool need_glob = false;
 	int cnt = 0;
-	glob_t globbuf;
 	char glob_pattern[PATH_MAX];
 	size_t i;
 
+#ifndef _WIN32
 	if (!allow_glob) {
 		return ucl_include_file_single (data, len, parser, check_signature,
 			must_exist, priority);
@@ -951,6 +985,7 @@ ucl_include_file (const unsigned char *data, size_t len,
 			p ++;
 		}
 		if (need_glob) {
+			glob_t globbuf;
 			memset (&globbuf, 0, sizeof (globbuf));
 			ucl_strlcpy (glob_pattern, (const char *)data, sizeof (glob_pattern));
 			if (glob (glob_pattern, 0, NULL, &globbuf) != 0) {
@@ -978,7 +1013,13 @@ ucl_include_file (const unsigned char *data, size_t len,
 				must_exist, priority);
 		}
 	}
-
+#else
+	/* Win32 compilers do not support globbing. Therefore, for Win32,
+	   treat allow_glob/need_glob as a NOOP and just return */
+	return ucl_include_file_single (data, len, parser, check_signature,
+		must_exist, priority);
+#endif
+	
 	return true;
 }
 
@@ -1394,7 +1435,7 @@ ucl_object_insert_key_common (ucl_object_t *top, ucl_object_t *elt,
 	}
 
 	if (top->value.ov == NULL) {
-		top->value.ov = ucl_hash_create ();
+		top->value.ov = ucl_hash_create (false);
 	}
 
 	if (keylen == 0) {
@@ -1427,7 +1468,7 @@ ucl_object_insert_key_common (ucl_object_t *top, ucl_object_t *elt,
 	found = __DECONST (ucl_object_t *, ucl_hash_search_obj (top->value.ov, elt));
 
 	if (found == NULL) {
-		top->value.ov = ucl_hash_insert_object (top->value.ov, elt);
+		top->value.ov = ucl_hash_insert_object (top->value.ov, elt, false);
 		top->len ++;
 		if (replace) {
 			ret = false;
@@ -1444,7 +1485,7 @@ ucl_object_insert_key_common (ucl_object_t *top, ucl_object_t *elt,
 				ucl_object_insert_key_common (elt, found, found->key,
 						found->keylen, copy_key, false, false);
 				ucl_hash_delete (top->value.ov, found);
-				top->value.ov = ucl_hash_insert_object (top->value.ov, elt);
+				top->value.ov = ucl_hash_insert_object (top->value.ov, elt, false);
 			}
 			else if (found->type == UCL_OBJECT && elt->type != UCL_OBJECT) {
 				/* Insert new to old */
@@ -1568,7 +1609,7 @@ ucl_object_merge (ucl_object_t *top, ucl_object_t *elt, bool copy)
 		found = __DECONST(ucl_object_t *, ucl_hash_search (top->value.ov, cp->key, cp->keylen));
 		if (found == NULL) {
 			/* The key does not exist */
-			top->value.ov = ucl_hash_insert_object (top->value.ov, cp);
+			top->value.ov = ucl_hash_insert_object (top->value.ov, cp, false);
 			top->len ++;
 		}
 		else {
@@ -1610,7 +1651,7 @@ ucl_object_find_key (const ucl_object_t *obj, const char *key)
 const ucl_object_t*
 ucl_iterate_object (const ucl_object_t *obj, ucl_object_iter_t *iter, bool expand_values)
 {
-	const ucl_object_t *elt;
+	const ucl_object_t *elt = NULL;
 
 	if (obj == NULL || iter == NULL) {
 		return NULL;
@@ -1621,19 +1662,25 @@ ucl_iterate_object (const ucl_object_t *obj, ucl_object_iter_t *iter, bool expan
 		case UCL_OBJECT:
 			return (const ucl_object_t*)ucl_hash_iterate (obj->value.ov, iter);
 			break;
-		case UCL_ARRAY:
-			elt = *iter;
-			if (elt == NULL) {
-				elt = obj->value.av;
-				if (elt == NULL) {
-					return NULL;
+		case UCL_ARRAY: {
+			unsigned int idx;
+			UCL_ARRAY_GET (vec, obj);
+			idx = (unsigned int)(uintptr_t)(*iter);
+
+			if (vec != NULL) {
+				while (idx < kv_size (*vec)) {
+					if ((elt = kv_A (*vec, idx)) != NULL) {
+						idx ++;
+						break;
+					}
+					idx ++;
 				}
+				*iter = (void *)(uintptr_t)idx;
 			}
-			else if (elt == obj->value.av) {
-				return NULL;
-			}
-			*iter = elt->next ? elt->next : obj->value.av;
+
 			return elt;
+			break;
+		}
 		default:
 			/* Go to linear iteration */
 			break;
@@ -1654,6 +1701,95 @@ ucl_iterate_object (const ucl_object_t *obj, ucl_object_iter_t *iter, bool expan
 	return NULL;
 }
 
+const char safe_iter_magic[4] = {'u', 'i', 't', 'e'};
+struct ucl_object_safe_iter {
+	char magic[4]; /* safety check */
+	const ucl_object_t *impl_it; /* implicit object iteration */
+	ucl_object_iter_t expl_it; /* explicit iteration */
+};
+
+#define UCL_SAFE_ITER(ptr) (struct ucl_object_safe_iter *)(ptr)
+#define UCL_SAFE_ITER_CHECK(it) do { \
+	assert (it != NULL); \
+	assert (memcmp (it->magic, safe_iter_magic, sizeof (it->magic)) == 0); \
+ } while (0)
+
+ucl_object_iter_t
+ucl_object_iterate_new (const ucl_object_t *obj)
+{
+	struct ucl_object_safe_iter *it;
+
+	it = UCL_ALLOC (sizeof (*it));
+	if (it != NULL) {
+		memcpy (it->magic, safe_iter_magic, sizeof (it->magic));
+		it->expl_it = NULL;
+		it->impl_it = obj;
+	}
+
+	return (ucl_object_iter_t)it;
+}
+
+
+ucl_object_iter_t
+ucl_object_iterate_reset (ucl_object_iter_t it, const ucl_object_t *obj)
+{
+	struct ucl_object_safe_iter *rit = UCL_SAFE_ITER (it);
+
+	UCL_SAFE_ITER_CHECK (rit);
+
+	rit->impl_it = obj;
+	rit->expl_it = NULL;
+
+	return it;
+}
+
+const ucl_object_t*
+ucl_object_iterate_safe (ucl_object_iter_t it, bool expand_values)
+{
+	struct ucl_object_safe_iter *rit = UCL_SAFE_ITER (it);
+	const ucl_object_t *ret = NULL;
+
+	UCL_SAFE_ITER_CHECK (rit);
+
+	if (rit->impl_it == NULL) {
+		return NULL;
+	}
+
+	if (rit->impl_it->type == UCL_OBJECT || rit->impl_it->type == UCL_ARRAY) {
+		ret = ucl_iterate_object (rit->impl_it, &rit->expl_it, true);
+
+		if (ret == NULL) {
+			/* Need to switch to another implicit object in chain */
+			rit->impl_it = rit->impl_it->next;
+			rit->expl_it = NULL;
+			return ucl_object_iterate_safe (it, expand_values);
+		}
+	}
+	else {
+		/* Just iterate over the implicit array */
+		ret = rit->impl_it;
+		rit->impl_it = rit->impl_it->next;
+		if (expand_values) {
+			/* We flatten objects if need to expand values */
+			if (ret->type == UCL_OBJECT || ret->type == UCL_ARRAY) {
+				return ucl_object_iterate_safe (it, expand_values);
+			}
+		}
+	}
+
+	return ret;
+}
+
+void
+ucl_object_iterate_free (ucl_object_iter_t it)
+{
+	struct ucl_object_safe_iter *rit = UCL_SAFE_ITER (it);
+
+	UCL_SAFE_ITER_CHECK (rit);
+
+	UCL_FREE (sizeof (*rit), it);
+}
+
 const ucl_object_t *
 ucl_lookup_path (const ucl_object_t *top, const char *path_in) {
 	const ucl_object_t *o = NULL, *found;
@@ -1733,6 +1869,17 @@ ucl_object_new_full (ucl_type_t type, unsigned priority)
 			new->next = NULL;
 			new->prev = new;
 			ucl_object_set_priority (new, priority);
+
+			if (type == UCL_ARRAY) {
+				new->value.av = UCL_ALLOC (sizeof (ucl_array_t));
+				if (new->value.av) {
+					memset (new->value.av, 0, sizeof (ucl_array_t));
+					UCL_ARRAY_GET (vec, new);
+
+					/* Preallocate some space for arrays */
+					kv_resize (ucl_object_t *, *vec, 8);
+				}
+			}
 		}
 	}
 	else {
@@ -1826,23 +1973,20 @@ ucl_object_frombool (bool bv)
 bool
 ucl_array_append (ucl_object_t *top, ucl_object_t *elt)
 {
-	ucl_object_t *head;
+	UCL_ARRAY_GET (vec, top);
 
 	if (elt == NULL || top == NULL) {
 		return false;
 	}
 
-	head = top->value.av;
-	if (head == NULL) {
-		top->value.av = elt;
-		elt->prev = elt;
+	if (vec == NULL) {
+		vec = UCL_ALLOC (sizeof (*vec));
+		kv_init (*vec);
+		top->value.av = (void *)vec;
 	}
-	else {
-		elt->prev = head->prev;
-		head->prev->next = elt;
-		head->prev = elt;
-	}
-	elt->next = NULL;
+
+	kv_push (ucl_object_t *, *vec, elt);
+
 	top->len ++;
 
 	return true;
@@ -1851,24 +1995,23 @@ ucl_array_append (ucl_object_t *top, ucl_object_t *elt)
 bool
 ucl_array_prepend (ucl_object_t *top, ucl_object_t *elt)
 {
-	ucl_object_t *head;
+	UCL_ARRAY_GET (vec, top);
 
 	if (elt == NULL || top == NULL) {
 		return false;
 	}
 
-
-	head = top->value.av;
-	if (head == NULL) {
-		top->value.av = elt;
-		elt->prev = elt;
+	if (vec == NULL) {
+		vec = UCL_ALLOC (sizeof (*vec));
+		kv_init (*vec);
+		top->value.av = (void *)vec;
+		kv_push (ucl_object_t *, *vec, elt);
 	}
 	else {
-		elt->prev = head->prev;
-		head->prev = elt;
+		/* Slow O(n) algorithm */
+		kv_prepend (ucl_object_t *, *vec, elt);
 	}
-	elt->next = head;
-	top->value.av = elt;
+
 	top->len ++;
 
 	return true;
@@ -1877,21 +2020,29 @@ ucl_array_prepend (ucl_object_t *top, ucl_object_t *elt)
 bool
 ucl_array_merge (ucl_object_t *top, ucl_object_t *elt, bool copy)
 {
-	ucl_object_t *cur, *tmp, *cp;
+	unsigned i;
+	ucl_object_t **obj;
+	UCL_ARRAY_GET (v1, top);
+	UCL_ARRAY_GET (v2, elt);
 
 	if (elt == NULL || top == NULL || top->type != UCL_ARRAY || elt->type != UCL_ARRAY) {
 		return false;
 	}
 
-	DL_FOREACH_SAFE (elt->value.av, cur, tmp) {
+	kv_concat (ucl_object_t *, *v1, *v2);
+
+	for (i = v2->n; i < v1->n; i ++) {
+		obj = &kv_A (*v1, i);
+		if (*obj == NULL) {
+			continue;
+		}
+
+		top->len ++;
 		if (copy) {
-			cp = ucl_object_copy (cur);
+			*obj = ucl_object_copy (*obj);
 		}
 		else {
-			cp = ucl_object_ref (cur);
-		}
-		if (cp != NULL) {
-			ucl_array_append (top, cp);
+			ucl_object_ref (*obj);
 		}
 	}
 
@@ -1901,82 +2052,85 @@ ucl_array_merge (ucl_object_t *top, ucl_object_t *elt, bool copy)
 ucl_object_t *
 ucl_array_delete (ucl_object_t *top, ucl_object_t *elt)
 {
-	ucl_object_t *head;
-
-	if (top == NULL || top->type != UCL_ARRAY || top->value.av == NULL) {
-		return NULL;
-	}
-	head = top->value.av;
+	UCL_ARRAY_GET (vec, top);
+	ucl_object_t *ret = NULL;
+	unsigned i;
 
-	if (elt->prev == elt) {
-		top->value.av = NULL;
-	}
-	else if (elt == head) {
-		elt->next->prev = elt->prev;
-		top->value.av = elt->next;
-	}
-	else {
-		elt->prev->next = elt->next;
-		if (elt->next) {
-			elt->next->prev = elt->prev;
-		}
-		else {
-			head->prev = elt->prev;
+	for (i = 0; i < vec->n; i ++) {
+		if (kv_A (*vec, i) == elt) {
+			kv_del (ucl_object_t *, *vec, i);
+			ret = elt;
+			top->len --;
+			break;
 		}
 	}
-	elt->next = NULL;
-	elt->prev = elt;
-	top->len --;
 
-	return elt;
+	return ret;
 }
 
 const ucl_object_t *
 ucl_array_head (const ucl_object_t *top)
 {
+	UCL_ARRAY_GET (vec, top);
+
 	if (top == NULL || top->type != UCL_ARRAY || top->value.av == NULL) {
 		return NULL;
 	}
-	return top->value.av;
+
+	return (vec->n > 0 ? vec->a[0] : NULL);
 }
 
 const ucl_object_t *
 ucl_array_tail (const ucl_object_t *top)
 {
+	UCL_ARRAY_GET (vec, top);
+
 	if (top == NULL || top->type != UCL_ARRAY || top->value.av == NULL) {
 		return NULL;
 	}
-	return top->value.av->prev;
+
+	return (vec->n > 0 ? vec->a[vec->n - 1] : NULL);
 }
 
 ucl_object_t *
 ucl_array_pop_last (ucl_object_t *top)
 {
-	return ucl_array_delete (top, __DECONST(ucl_object_t *, ucl_array_tail (top)));
+	UCL_ARRAY_GET (vec, top);
+	ucl_object_t **obj, *ret = NULL;
+
+	if (vec != NULL && vec->n > 0) {
+		obj = &kv_A (*vec, vec->n - 1);
+		ret = *obj;
+		kv_del (ucl_object_t *, *vec, vec->n - 1);
+		top->len --;
+	}
+
+	return ret;
 }
 
 ucl_object_t *
 ucl_array_pop_first (ucl_object_t *top)
 {
-	return ucl_array_delete (top, __DECONST(ucl_object_t *, ucl_array_head (top)));
+	UCL_ARRAY_GET (vec, top);
+	ucl_object_t **obj, *ret = NULL;
+
+	if (vec != NULL && vec->n > 0) {
+		obj = &kv_A (*vec, 0);
+		ret = *obj;
+		kv_del (ucl_object_t *, *vec, 0);
+		top->len --;
+	}
+
+	return ret;
 }
 
 const ucl_object_t *
 ucl_array_find_index (const ucl_object_t *top, unsigned int index)
 {
-	ucl_object_iter_t it = NULL;
-	const ucl_object_t *ret;
-
-	if (top == NULL || top->type != UCL_ARRAY || top->len == 0 ||
-	    (index + 1) > top->len) {
-		return NULL;
-	}
+	UCL_ARRAY_GET (vec, top);
 
-	while ((ret = ucl_iterate_object (top, &it, true)) != NULL) {
-		if (index == 0) {
-			return ret;
-		}
-		--index;
+	if (vec != NULL && vec->n > 0 && index < vec->n) {
+		return kv_A (*vec, index);
 	}
 
 	return NULL;
@@ -1986,22 +2140,15 @@ ucl_object_t *
 ucl_array_replace_index (ucl_object_t *top, ucl_object_t *elt,
 	unsigned int index)
 {
-	ucl_object_t *cur, *tmp;
+	UCL_ARRAY_GET (vec, top);
+	ucl_object_t *ret = NULL;
 
-	if (top == NULL || top->type != UCL_ARRAY || elt == NULL ||
-			top->len == 0 || (index + 1) > top->len) {
-		return NULL;
+	if (vec != NULL && vec->n > 0 && index < vec->n) {
+		ret = kv_A (*vec, index);
+		kv_A (*vec, index) = elt;
 	}
 
-	DL_FOREACH_SAFE (top->value.av, cur, tmp) {
-		if (index == 0) {
-			DL_REPLACE_ELEM (top->value.av, cur, elt);
-			return cur;
-		}
-		--index;
-	}
-
-	return NULL;
+	return ret;
 }
 
 ucl_object_t *
@@ -2314,7 +2461,7 @@ ucl_object_compare (const ucl_object_t *o1, const ucl_object_t *o2)
 
 	switch (o1->type) {
 	case UCL_STRING:
-		if (o1->len == o2->len) {
+		if (o1->len == o2->len && o1->len > 0) {
 			ret = strcmp (ucl_object_tostring(o1), ucl_object_tostring(o2));
 		}
 		else {
@@ -2330,17 +2477,28 @@ ucl_object_compare (const ucl_object_t *o1, const ucl_object_t *o2)
 		ret = ucl_object_toboolean (o1) - ucl_object_toboolean (o2);
 		break;
 	case UCL_ARRAY:
-		if (o1->len == o2->len) {
-			it1 = o1->value.av;
-			it2 = o2->value.av;
+		if (o1->len == o2->len && o1->len > 0) {
+			UCL_ARRAY_GET (vec1, o1);
+			UCL_ARRAY_GET (vec2, o2);
+			unsigned i;
+
 			/* Compare all elements in both arrays */
-			while (it1 != NULL && it2 != NULL) {
-				ret = ucl_object_compare (it1, it2);
-				if (ret != 0) {
-					break;
+			for (i = 0; i < vec1->n; i ++) {
+				it1 = kv_A (*vec1, i);
+				it2 = kv_A (*vec2, i);
+
+				if (it1 == NULL && it2 != NULL) {
+					return -1;
+				}
+				else if (it2 == NULL && it1 != NULL) {
+					return 1;
+				}
+				else if (it1 != NULL && it2 != NULL) {
+					ret = ucl_object_compare (it1, it2);
+					if (ret != 0) {
+						break;
+					}
 				}
-				it1 = it1->next;
-				it2 = it2->next;
 			}
 		}
 		else {
@@ -2348,7 +2506,7 @@ ucl_object_compare (const ucl_object_t *o1, const ucl_object_t *o2)
 		}
 		break;
 	case UCL_OBJECT:
-		if (o1->len == o2->len) {
+		if (o1->len == o2->len && o1->len > 0) {
 			while ((it1 = ucl_iterate_object (o1, &iter, true)) != NULL) {
 				it2 = ucl_object_find_key (o2, ucl_object_key (it1));
 				if (it2 == NULL) {
@@ -2377,11 +2535,14 @@ void
 ucl_object_array_sort (ucl_object_t *ar,
 		int (*cmp)(const ucl_object_t *o1, const ucl_object_t *o2))
 {
+	UCL_ARRAY_GET (vec, ar);
+
 	if (cmp == NULL || ar == NULL || ar->type != UCL_ARRAY) {
 		return;
 	}
 
-	DL_SORT (ar->value.av, cmp);
+	qsort (vec->a, vec->n, sizeof (ucl_object_t *),
+			(int (*)(const void *, const void *))cmp);
 }
 
 #define PRIOBITS 4