Mercurial > libjeffpc > bad-patches

changeset 0:3e042207d646

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first batch of patches
author Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
date Sat, 17 Nov 2018 12:02:16 -0500
parents
children 2df0a7f85837
files 2018-11-17-1-WIP__rope.patch 2018-11-17-2-array__reimplement_as_an_explicitly_wrapped_array.patch 2018-11-17-3-WIP__buffer__remove_byte_slice.patch 2018-11-17-4-WIP__array__implement_a_remove_element_function.patch 2018-11-17-5-exlist__a_non_intrusive_circular_doubly_linked_list.patch
diffstat 5 files changed, 1129 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/2018-11-17-1-WIP__rope.patch	Sat Nov 17 12:02:16 2018 -0500
@@ -0,0 +1,278 @@
+# HG changeset patch
+# User Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+# Date 1492309700 14400
+#      Sat Apr 15 22:28:20 2017 -0400
+# Node ID fe935c48619d33820fda3c20c3548be5516e3351
+# Parent  a25ff7b067d556fe3f0af72133f2bf2f87633a7e
+# EXP-Topic rope
+WIP: rope
+
+Sometimes a string is just not good enough.  For some of those times, a rope
+will work much better.
+
+Signed-off-by: Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+
+diff --git a/CMakeLists.txt b/CMakeLists.txt
+--- a/CMakeLists.txt
++++ b/CMakeLists.txt
+@@ -105,6 +105,7 @@ add_library(jeffpc SHARED
+ 	padding.c
+ 	qstring.c
+ 	rand.c
++	rope.c
+ 	sexpr.c
+ 	sexpr_dump.c
+ 	sexpr_eval.c
+diff --git a/include/jeffpc/rope.h b/include/jeffpc/rope.h
+new file mode 100644
+--- /dev/null
++++ b/include/jeffpc/rope.h
+@@ -0,0 +1,51 @@
++/*
++ * Copyright (c) 2016-2017 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
++ *
++ * Permission is hereby granted, free of charge, to any person obtaining a copy
++ * of this software and associated documentation files (the "Software"), to deal
++ * in the Software without restriction, including without limitation the rights
++ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
++ * copies of the Software, and to permit persons to whom the Software is
++ * furnished to do so, subject to the following conditions:
++ *
++ * The above copyright notice and this permission notice shall be included in
++ * all copies or substantial portions of the Software.
++ *
++ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
++ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
++ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
++ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
++ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
++ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
++ * SOFTWARE.
++ */
++
++#ifndef __JEFFPC_ROPE_H
++#define __JEFFPC_ROPE_H
++
++#include <jeffpc/refcnt.h>
++#include <jeffpc/str.h>
++#include <jeffpc/list.h>
++
++/* scatter-gather string */
++
++struct rope_node {
++	struct list_node node;
++	struct str *str;
++};
++
++struct rope {
++	struct list_node list;
++	size_t nodes;		/* length of list */
++	size_t len;		/* length of string */
++};
++
++extern struct rope *rope_alloc(void);
++extern void rope_free(struct rope *rope);
++extern int rope_append_rope(struct rope *a, struct rope *b);
++extern int rope_append_str(struct rope *a, struct str *b);
++extern int rope_append_cstr(struct rope *a, const char *b);
++extern char *rope_cstr(struct rope *a);
++extern int write_rope(struct rope *a);
++
++#endif
+diff --git a/rope.c b/rope.c
+new file mode 100644
+--- /dev/null
++++ b/rope.c
+@@ -0,0 +1,192 @@
++/*
++ * Copyright (c) 2016-2017 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
++ *
++ * Permission is hereby granted, free of charge, to any person obtaining a copy
++ * of this software and associated documentation files (the "Software"), to deal
++ * in the Software without restriction, including without limitation the rights
++ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
++ * copies of the Software, and to permit persons to whom the Software is
++ * furnished to do so, subject to the following conditions:
++ *
++ * The above copyright notice and this permission notice shall be included in
++ * all copies or substantial portions of the Software.
++ *
++ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
++ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
++ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
++ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
++ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
++ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
++ * SOFTWARE.
++ */
++
++#include <jeffpc/rope.h>
++#include <jeffpc/jeffpc.h>
++#include <jeffpc/io.h>
++
++static struct rope_node *rope_node_alloc(struct str *str)
++{
++	struct rope_node *rn;
++
++	rn = malloc(sizeof(struct rope_node));
++	if (!rn)
++		return NULL;
++
++	rn->str = str;
++	slist_init(&rn->node);
++
++	return rn;
++}
++
++static void rope_node_free(struct rope_node *rn)
++{
++	str_putref(rn->str);
++	free(rn);
++}
++
++struct rope *rope_alloc(void)
++{
++	struct rope *rope;
++
++	rope = malloc(sizeof(struct rope));
++	if (!rope)
++		return NULL;
++
++	slist_init(&rope->list);
++	rope->nodes = 0;
++	rope->len = 0;
++
++	return rope;
++}
++
++void rope_free(struct rope *rope)
++{
++	struct rope_node *rn, *tmp;
++
++	slist_for_each_entry_safe(rn, tmp, &rope->list, node)
++		rope_node_free(rn);
++
++	free(rope);
++}
++
++/* move contents of b at the end of a */
++int rope_append_rope(struct rope *a, struct rope *b)
++{
++#warning "move slist contents"
++
++	a->nodes += b->nodes;
++	b->nodes = 0;
++	a->len += b->len;
++	b->len = 0;
++
++	rope_free(b);
++
++	return 0;
++}
++
++int rope_append_str(struct rope *a, struct str *b)
++{
++	struct rope_node *rn;
++
++	rn = rope_node_alloc(b);
++	if (!rn)
++		return -ENOMEM;
++
++	slist_insert_tail(&a->list, &rn->node);
++	a->nodes++;
++	a->len += str_len(b);
++
++	return 0;
++}
++
++int rope_append_cstr(struct rope *a, const char *b)
++{
++	struct str *str;
++
++	str = str_dup(b);
++	if (IS_ERR(str))
++		return PTR_ERR(str);
++
++	return rope_append_str(a, str);
++}
++
++char *rope_cstr(struct rope *a)
++{
++	int ret;
++
++	ret = rope_flatten(a);
++	if (ret)
++		return ERR_PTR(ret);
++
++	/* no node - empty string */
++	if (a->nodes == 0)
++		return NULL;
++
++	VERIFY3U(a->nodes, ==, 1);
++
++	/* one node - just return it */
++	return str_cstr(slist_head_entry(&a->list, struct rope_node, node)->str);
++}
++
++int rope_flatten(struct rope *rope)
++{
++	struct rope_node *rn;
++	struct str *str;
++	const char *tmp;
++
++	if (rope->nodes <= 1)
++		return 0;
++
++	tmp = malloc(rope->len + 1);
++	if (!tmp)
++		goto err;
++
++	off = 0;
++	slist_for_each_entry(rn, &a->list, node) {
++		size_t slen = str_len(rn->str);
++
++		memcpy(tmp + off, str_cstr(rn->str), slen);
++
++		off += slen;
++	}
++
++	ret[a->len] = '\0';
++
++	str = str_alloc(ret);
++	if (!str)
++		goto err_cstr;
++
++	rn = rope_node_alloc(str);
++	if (!rn)
++		goto err_str;
++
++	slist_for_each_entry_safe(rn, safe, &rope->list, node)
++		rope_node_free(rn);
++
++	slist_
++
++	rope->nodes = 1;
++
++	return ret;
++
++err_str:
++	str_putref(str);
++err_cstr:
++	free(tmp);
++err:
++	return -ENOMEM;
++}
++
++int xwrite_rope(int fd, struct rope *a)
++{
++	struct rope_node *rn;
++	int ret;
++
++	slist_for_each_entry(rn, &a->list, node) {
++		ret = xwrite_str(fd, str_cstr(rn->str));
++		if (ret)
++			return ret;
++	}
++
++	return 0;
++}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/2018-11-17-2-array__reimplement_as_an_explicitly_wrapped_array.patch	Sat Nov 17 12:02:16 2018 -0500
@@ -0,0 +1,484 @@
+# HG changeset patch
+# User Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+# Date 1541776905 18000
+#      Fri Nov 09 10:21:45 2018 -0500
+# Node ID 7b73a1dd0a54f89713008239cf69188e32ea80b9
+# Parent  dfbcf2a05902cd768c8cf28c518c76b5606e0a56
+array: reimplement as an explicitly wrapped array
+
+Instead of being a glorified realloc wrapper, this commit rewrites the whole
+array API to work on typed array structures.  This maintains the type safety
+we had before, but it is now more obvious that we must not free the array by
+calling free(3) but rather array_free.
+
+Signed-off-by: Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+
+diff --git a/CMakeLists.txt b/CMakeLists.txt
+--- a/CMakeLists.txt
++++ b/CMakeLists.txt
+@@ -147,6 +147,7 @@ install(TARGETS	jeffpc
+ 	PERMISSIONS OWNER_WRITE OWNER_READ GROUP_READ WORLD_READ)
+ install(FILES	include/jeffpc/atomic.h
+ 		include/jeffpc/array.h
++		include/jeffpc/array_private.h
+ 		include/jeffpc/bst.h
+ 		include/jeffpc/buffer.h
+ 		include/jeffpc/cstr.h
+diff --git a/array.c b/array.c
+--- a/array.c
++++ b/array.c
+@@ -25,96 +25,70 @@
+ #include <jeffpc/array.h>
+ #include <jeffpc/error.h>
+ 
+-struct array {
+-	size_t elem_size;		/* size of each element */
+-	size_t elem_count;		/* number of visible elements */
+-	size_t preallocated;		/* number of allocated elements */
+-	uint8_t raw[];
+-};
++static inline size_t current_num_elem(struct array *array)
++{
++	return buffer_used(array->data) / array->elem_size;
++}
+ 
+ static inline size_t total_size(size_t elem_size, size_t count)
+ {
+-	return sizeof(struct array) + elem_size * count;
+-}
+-
+-static inline void *get_ptr(struct array *array, size_t idx)
+-{
+-	return &array->raw[array->elem_size * idx];
+-}
+-
+-void *array_alloc(size_t elem_size, size_t prealloc_count)
+-{
+-	struct array *array;
+-
+-	array = malloc(total_size(elem_size, prealloc_count));
+-	if (!array)
+-		return NULL;
+-
+-	array->elem_size = elem_size;
+-	array->elem_count = 0;
+-	array->preallocated = prealloc_count;
+-
+-	return array->raw;
++	/* TODO: check for overflows */
++	return elem_size * count;
+ }
+ 
+-void array_free(void *raw)
+-{
+-	if (!raw)
+-		return;
+-
+-	free(container_of(raw, struct array, raw));
+-}
+-
+-static struct array *__array_truncate(struct array *array,
+-				      size_t new_elem_count)
++struct array *array_alloc_i(size_t elem_size, size_t prealloc_count)
+ {
+-	struct array *newarray;
+-
+-	if (new_elem_count <= array->elem_count)
+-		goto done; /* shrinking or no change */
++	struct array *array;
++	struct buffer *buf;
+ 
+-	if (new_elem_count <= array->preallocated)
+-		goto clear; /* growing into preallocated space */
+-
+-	/* grow the allocation */
+-
+-	newarray = realloc(array, total_size(array->elem_size, new_elem_count));
+-	if (!newarray)
++	array = malloc(sizeof(struct array));
++	if (!array)
+ 		return ERR_PTR(-ENOMEM);
+ 
+-	array = newarray;
+-
+-	array->preallocated = new_elem_count;
++	buf = buffer_alloc(total_size(elem_size, prealloc_count));
++	if (IS_ERR(buf)) {
++		free(array);
++		return ERR_CAST(buf);
++	}
+ 
+-clear:
+-	memset(get_ptr(array, array->elem_count), 0,
+-	       total_size(array->elem_size, new_elem_count) -
+-	       total_size(array->elem_size, array->elem_count));
+-
+-done:
+-	array->elem_count = new_elem_count;
++	array->elem_size = elem_size;
++	array->data = buf;
+ 
+ 	return array;
+ }
+ 
+-#undef array_truncate
+-int array_truncate(void **raw, size_t idx)
++void array_free_i(struct array *array)
+ {
+-	struct array *array = container_of(*raw, struct array, raw);
++	if (!array)
++		return;
+ 
+-	array = __array_truncate(array, idx);
+-	if (IS_ERR(array))
+-		return PTR_ERR(array);
++	buffer_free(array->data);
++	free(array);
++}
+ 
+-	*raw = array->raw;
+-
+-	return 0;
++int array_truncate_i(struct array *array, size_t new_elem_count)
++{
++	return buffer_truncate(array->data,
++			       total_size(array->elem_size, new_elem_count));
+ }
+ 
+-size_t array_size(void *raw)
++size_t array_size_i(struct array *array)
+ {
+-	if (!raw)
++	if (!array)
+ 		return 0;
+ 
+-	return container_of(raw, struct array, raw)->elem_count;
++	return current_num_elem(array);
+ }
++
++int array_set_i(struct array *array, size_t idx, void *v, bool fatal)
++{
++	int ret;
++
++	ret = buffer_pwrite(array->data, v, array->elem_size,
++			    idx * array->elem_size);
++	if ((ret < 0) && fatal)
++		panic("failed to set array[%zu] to value at %p: %s",
++		      idx, v, xstrerror(ret));
++
++	return (ret < 0) ? ret : 0;
++}
+diff --git a/include/jeffpc/array.h b/include/jeffpc/array.h
+--- a/include/jeffpc/array.h
++++ b/include/jeffpc/array.h
+@@ -1,5 +1,5 @@
+ /*
+- * Copyright (c) 2017 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
++ * Copyright (c) 2017-2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+  *
+  * Permission is hereby granted, free of charge, to any person obtaining a copy
+  * of this software and associated documentation files (the "Software"), to deal
+@@ -23,25 +23,111 @@
+ #ifndef __JEFFPC_ARRAY_H
+ #define __JEFFPC_ARRAY_H
+ 
+-#include <jeffpc/types.h>
++#include <jeffpc/array_private.h>
+ 
+-extern void *array_alloc(size_t elem_size, size_t prealloc_count);
+-extern void array_free(void *raw);
++#define array_alloc(type_name, elem_count)				\
++	({								\
++		union {							\
++			ARRAY_TYPE(type_name) *typed;			\
++			struct array *plain;				\
++		} u;							\
++									\
++		u.plain = array_alloc_i(sizeof(*u.typed->dummy),	\
++					(elem_count));			\
++									\
++		u.typed;						\
++	})
+ 
+-extern int array_truncate(void **raw, size_t idx);
+-extern size_t array_size(void *raw);
++#define array_free(typed)						\
++	array_free_i(&(typed)->array)
++#define array_truncate(typed, new_elem_count)				\
++	array_truncate_i(&(typed)->array, (new_elem_count))
++#define array_size(typed)						\
++	array_size_i(&(typed)->array)
++#define array_get_ptr(typed, idx)					\
++	((typeof((typed)->dummy)) array_get_void_ptr_i(&(typed)->array, \
++						       (idx)))
++#define array_get(typed, idx)						\
++	(*array_get_ptr((typed), (idx)))
+ 
+ /*
+- * This silly wrapper lets us have a void ** argument, yet users can pass in
+- * a struct foo **.
++ * There are multiple ways to set and append elements:
++ *
++ *   array_{set,append}{,_by_ptr}{,_fatal}(...)
++ *
++ * The three parts are defined as:
++ *
++ *   Operation:
++ *     - "set" sets an element at an index
++ *     - "append" appends a new element at the end of the array
++ *
++ *   Value type:
++ *     - "" passes the new element by value
++ *     - "by_ptr" passes the new element by reference
++ *
++ *   Error handling:
++ *     - "" returns a negated errno
++ *     - "fatal" panics on error
+  */
+-#define array_truncate(raw, idx)				\
+-	({							\
+-		void *_tmp = *(raw);				\
+-		int ret;					\
+-		ret = array_truncate(&_tmp, (idx));		\
+-		*(raw) = _tmp;					\
+-		ret;						\
+-	})
++#define array_set_by_ptr(typed, idx, v)					\
++	array_set_helper_i((typed)->dummy, false, false,		\
++			   &(typed)->array, (idx), (v))
++#define array_set_by_ptr_fatal(typed, idx, v)				\
++	do {								\
++		array_set_helper_i((typed)->dummy, false, true,		\
++				   &(typed)->array, (idx), (v));	\
++	} while (0)
++#define array_append_by_ptr(typed, v)					\
++	array_set_helper_i((typed)->dummy, true, false,			\
++			   &(typed)->array, 0, (v))
++#define array_append_by_ptr_fatal(typed, v)				\
++	do {								\
++		array_set_helper_i((typed)->dummy, true, true,		\
++				   &(typed)->array, 0, (v));		\
++	} while (0)
++
++#define array_set(typed, idx, v)					\
++	array_set_helper_i(*(typed)->dummy, false, false,		\
++			   &(typed)->array, (idx), (v))
++#define array_set_fatal(typed, idx, v)					\
++	do {								\
++		array_set_helper_i(*(typed)->dummy, false, true,	\
++				   &(typed)->array, (idx), (v));	\
++	} while (0)
++#define array_append(typed, v)						\
++	array_set_helper_i(*(typed)->dummy, true, false,		\
++			   &(typed)->array, 0, (v))
++#define array_append_fatal(typed, v)					\
++	do {								\
++		array_set_helper_i(*(typed)->dummy, true, true,		\
++				   &(typed)->array, 0, (v));		\
++	} while (0)
++
++ARRAY_DECL_TYPE(ulonglong, unsigned long long);
++ARRAY_DECL_TYPE(ulong, unsigned long);
++ARRAY_DECL_TYPE(uint, unsigned int);
++ARRAY_DECL_TYPE(ushort, unsigned short);
++ARRAY_DECL_TYPE(uchar, unsigned char);
++
++ARRAY_DECL_TYPE(longlong, long long);
++ARRAY_DECL_TYPE(long, long);
++ARRAY_DECL_TYPE(int, int);
++ARRAY_DECL_TYPE(short, short);
++ARRAY_DECL_TYPE(char, char);
++
++ARRAY_DECL_TYPE(size_t, size_t);
++ARRAY_DECL_TYPE(ssize_t, ssize_t);
++
++ARRAY_DECL_TYPE(uintptr_t, uintptr_t);
++ARRAY_DECL_TYPE(uint64_t, uint64_t);
++ARRAY_DECL_TYPE(uint32_t, uint32_t);
++ARRAY_DECL_TYPE(uint16_t, uint16_t);
++ARRAY_DECL_TYPE(uint8_t, uint8_t);
++
++ARRAY_DECL_TYPE(intptr_t, intptr_t);
++ARRAY_DECL_TYPE(int64_t, int64_t);
++ARRAY_DECL_TYPE(int32_t, int32_t);
++ARRAY_DECL_TYPE(int16_t, int16_t);
++ARRAY_DECL_TYPE(int8_t, int8_t);
+ 
+ #endif
+diff --git a/include/jeffpc/array_private.h b/include/jeffpc/array_private.h
+new file mode 100644
+--- /dev/null
++++ b/include/jeffpc/array_private.h
+@@ -0,0 +1,80 @@
++/*
++ * Copyright (c) 2017-2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
++ *
++ * Permission is hereby granted, free of charge, to any person obtaining a copy
++ * of this software and associated documentation files (the "Software"), to deal
++ * in the Software without restriction, including without limitation the rights
++ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
++ * copies of the Software, and to permit persons to whom the Software is
++ * furnished to do so, subject to the following conditions:
++ *
++ * The above copyright notice and this permission notice shall be included in
++ * all copies or substantial portions of the Software.
++ *
++ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
++ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
++ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
++ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
++ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
++ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
++ * SOFTWARE.
++ */
++
++#ifndef __JEFFPC_ARRAY_IMPL_H
++#define __JEFFPC_ARRAY_IMPL_H
++
++#include <jeffpc/types.h>
++#include <jeffpc/buffer.h>
++
++struct array {
++	struct buffer *data;
++	size_t elem_size;
++};
++
++#define ARRAY_TYPE(name) \
++	union array_##name
++
++#define ARRAY_DECL_TYPE(name, type) \
++	union array_##name { \
++		struct array array; \
++		type *dummy; \
++	}
++
++#define array_set_helper_i(dummy, append, fatal, array, idx, v)		\
++	({								\
++		/* this type checks the passed in value */		\
++		typeof(dummy) value = (v);				\
++		int ret;						\
++									\
++		if (append)						\
++			ret = array_append_i((array), &value, fatal);	\
++		else							\
++			ret = array_set_i((array), (idx), &value, fatal);\
++									\
++		ret;							\
++	})
++
++extern struct array *array_alloc_i(size_t elem_size, size_t prealloc_count);
++extern void array_free_i(struct array *array);
++
++extern int array_truncate_i(struct array *array, size_t idx);
++extern size_t array_size_i(struct array *array);
++
++extern int array_set_i(struct array *array, size_t idx, void *v, bool fatal);
++
++static inline const void *array_get_void_ptr_i(struct array *array, size_t idx)
++{
++	const size_t off = idx * array->elem_size;
++	const char *data;
++
++	data = buffer_data(array->data);
++
++	return &data[off];
++}
++
++static inline int array_append_i(struct array *array, void *v, bool fatal)
++{
++	return array_set_i(array, array_size_i(array), v, fatal);
++}
++
++#endif
+diff --git a/mapfile-vers b/mapfile-vers
+--- a/mapfile-vers
++++ b/mapfile-vers
+@@ -23,10 +23,11 @@
+ JEFFPC_0.10 {
+ 	global:
+ 		# array
+-		array_alloc;
+-		array_free;
+-		array_size;
+-		array_truncate;
++		array_alloc_i;
++		array_free_i;
++		array_set_i;
++		array_size_i;
++		array_truncate_i;
+ 
+ 		# bst
+ 		bst_add;
+diff --git a/tests/test_array.c b/tests/test_array.c
+--- a/tests/test_array.c
++++ b/tests/test_array.c
+@@ -1,5 +1,5 @@
+ /*
+- * Copyright (c) 2017 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
++ * Copyright (c) 2017-2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+  *
+  * Permission is hereby granted, free of charge, to any person obtaining a copy
+  * of this software and associated documentation files (the "Software"), to deal
+@@ -27,9 +27,9 @@
+ 
+ static void test_alloc_free(void)
+ {
+-	int *arr;
++	ARRAY_TYPE(int) *arr;
+ 
+-	arr = array_alloc(sizeof(int), 0);
++	arr = array_alloc(int, 0);
+ 	if (!arr)
+ 		fail("array_alloc returned NULL");
+ 
+@@ -58,13 +58,14 @@ static void test_alloc_free(void)
+ #define CHECK_VAL(arr, idx, expected_val)				\
+ 	do {								\
+ 		size_t exp = (expected_val);				\
++		int got = array_get((arr), (idx));			\
+ 									\
+ 		fprintf(stderr, "checking array idx %zu; expect %zu...",\
+ 			(idx), exp);					\
+ 									\
+-		if (arr[idx] != (expected_val))				\
++		if (got != exp)						\
+ 			fail("value mismatch! expected %zu, got %u",	\
+-			     exp, arr[i]);				\
++			     exp, got);					\
+ 									\
+ 		fprintf(stderr, "ok\n");				\
+ 	} while (0)
+@@ -73,13 +74,13 @@ static void test_alloc_free(void)
+ 
+ static void test_size(void)
+ {
+-	unsigned int *arr;
++	ARRAY_TYPE(int) *arr;
+ 	size_t i, j, k;
+ 
+ 	for (i = 0; i < 3; i++) {
+ 		fprintf(stderr, "prealloc %zu\n", i * 10);
+ 
+-		arr = array_alloc(sizeof(int), i * 10);
++		arr = array_alloc(int, i * 10);
+ 		if (!arr)
+ 			fail("array_alloc_returned NULL");
+ 
+@@ -90,7 +91,7 @@ static void test_size(void)
+ 
+ 			fprintf(stderr, "truncating to %zu\n", j);
+ 
+-			ret = array_truncate(&arr, j);
++			ret = array_truncate(arr, j);
+ 			if (ret)
+ 				fail("truncate failed: %s", xstrerror(ret));
+ 
+@@ -101,7 +102,7 @@ static void test_size(void)
+ 				CHECK_VAL(arr, j - 1, 0);
+ 
+ 				/* set the newly allocated value */
+-				arr[j - 1] = GEN_VAL(j - 1);
++				array_set_fatal(arr, j - 1, GEN_VAL(j - 1));
+ 			}
+ 
+ 			/* check that the previous values are still there */
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/2018-11-17-3-WIP__buffer__remove_byte_slice.patch	Sat Nov 17 12:02:16 2018 -0500
@@ -0,0 +1,51 @@
+# HG changeset patch
+# User Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+# Date 1541776712 18000
+#      Fri Nov 09 10:18:32 2018 -0500
+# Node ID f5d73784e3be072001b5dacf11ef37a6570dade7
+# Parent  7b73a1dd0a54f89713008239cf69188e32ea80b9
+WIP: buffer: remove byte slice
+
+diff --git a/buffer.c b/buffer.c
+--- a/buffer.c
++++ b/buffer.c
+@@ -217,6 +217,17 @@ int buffer_truncate(struct buffer *buffe
+ 	return 0;
+ }
+ 
++int buffer_remove(struct buffer *buffer, size_t off, size_t len)
++{
++	if (!buffer)
++		return -EINVAL;
++
++	if (!len)
++		return 0;
++
++	XXX;
++}
++
+ ssize_t buffer_pread(struct buffer *buffer, void *buf, size_t len, size_t off)
+ {
+ 	ssize_t ret;
+diff --git a/include/jeffpc/buffer.h b/include/jeffpc/buffer.h
+--- a/include/jeffpc/buffer.h
++++ b/include/jeffpc/buffer.h
+@@ -76,6 +76,7 @@ extern void buffer_init_stdio(struct buf
+ extern int buffer_append(struct buffer *buffer, const void *data, size_t size);
+ extern ssize_t buffer_seek(struct buffer *buffer, off_t offset, int whence);
+ extern int buffer_truncate(struct buffer *buffer, size_t size);
++extern int buffer_remove(struct buffer *buffer, size_t off, size_t len);
+ extern ssize_t buffer_pread(struct buffer *buffer, void *data, size_t len,
+ 			    size_t off);
+ extern ssize_t buffer_pwrite(struct buffer *buffer, const void *data, size_t len,
+diff --git a/mapfile-vers b/mapfile-vers
+--- a/mapfile-vers
++++ b/mapfile-vers
+@@ -45,6 +45,7 @@ JEFFPC_0.10 {
+ 		buffer_init_stdio;
+ 		buffer_pread;
+ 		buffer_pwrite;
++		buffer_remove;
+ 		buffer_seek;
+ 		buffer_truncate;
+ 
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/2018-11-17-4-WIP__array__implement_a_remove_element_function.patch	Sat Nov 17 12:02:16 2018 -0500
@@ -0,0 +1,37 @@
+# HG changeset patch
+# User Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+# Date 1541776930 18000
+#      Fri Nov 09 10:22:10 2018 -0500
+# Node ID 1dd108ab152cacaf7676755282844c1673b5f064
+# Parent  f5d73784e3be072001b5dacf11ef37a6570dade7
+WIP: array: implement a remove-element function
+
+Signed-off-by: Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+
+diff --git a/include/jeffpc/array.h b/include/jeffpc/array.h
+--- a/include/jeffpc/array.h
++++ b/include/jeffpc/array.h
+@@ -42,6 +42,8 @@
+ 	array_free_i(&(typed)->array)
+ #define array_truncate(typed, new_elem_count)				\
+ 	array_truncate_i(&(typed)->array, (new_elem_count))
++#define array_remove(typed, idx)					\
++	array_remove_i(&(typed)->array, (idx))
+ #define array_size(typed)						\
+ 	array_size_i(&(typed)->array)
+ #define array_get_ptr(typed, idx)					\
+diff --git a/include/jeffpc/array_private.h b/include/jeffpc/array_private.h
+--- a/include/jeffpc/array_private.h
++++ b/include/jeffpc/array_private.h
+@@ -77,4 +77,11 @@ static inline int array_append_i(struct 
+ 	return array_set_i(array, array_size_i(array), v, fatal);
+ }
+ 
++static inline int array_remove_i(struct array *array, size_t idx)
++{
++	const size_t off = idx * array->elem_size;
++
++	return buffer_remove(array->data, off, array->elem_size);
++}
++
+ #endif
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/2018-11-17-5-exlist__a_non_intrusive_circular_doubly_linked_list.patch	Sat Nov 17 12:02:16 2018 -0500
@@ -0,0 +1,279 @@
+# HG changeset patch
+# User Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+# Date 1542072280 18000
+#      Mon Nov 12 20:24:40 2018 -0500
+# Node ID f086439ec8a832b724b41837cd34c0619b9e4eed
+# Parent  1dd108ab152cacaf7676755282844c1673b5f064
+exlist: a non-intrusive circular doubly-linked list
+
+Signed-off-by: Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+
+diff --git a/CMakeLists.txt b/CMakeLists.txt
+--- a/CMakeLists.txt
++++ b/CMakeLists.txt
+@@ -93,6 +93,7 @@ add_library(jeffpc SHARED
+ 	buffer_stdio.c
+ 	cstr.c
+ 	error.c
++	exlist.c
+ 	fmt_cbor.c
+ 	hexdump.c
+ 	init.c
+@@ -152,6 +153,7 @@ install(FILES	include/jeffpc/atomic.h
+ 		include/jeffpc/buffer.h
+ 		include/jeffpc/cstr.h
+ 		include/jeffpc/error.h
++		include/jeffpc/exlist.h
+ 		include/jeffpc/hexdump.h
+ 		include/jeffpc/int.h
+ 		include/jeffpc/io.h
+diff --git a/exlist.c b/exlist.c
+new file mode 100644
+--- /dev/null
++++ b/exlist.c
+@@ -0,0 +1,109 @@
++/*
++ * Copyright (c) 2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
++ *
++ * Permission is hereby granted, free of charge, to any person obtaining a copy
++ * of this software and associated documentation files (the "Software"), to deal
++ * in the Software without restriction, including without limitation the rights
++ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
++ * copies of the Software, and to permit persons to whom the Software is
++ * furnished to do so, subject to the following conditions:
++ *
++ * The above copyright notice and this permission notice shall be included in
++ * all copies or substantial portions of the Software.
++ *
++ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
++ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
++ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
++ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
++ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
++ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
++ * SOFTWARE.
++ */
++
++#include <jeffpc/exlist.h>
++
++struct exlist_node {
++	struct list_node node;
++	void *data;
++};
++
++void exlist_create(struct exlist *list)
++{
++	list_create(&list->list, sizeof(struct exlist_node),
++		    offsetof(struct exlist_node, node));
++}
++
++int _exlist_insert(struct exlist *list, void *new, bool head)
++{
++	struct exlist_node *node;
++
++	node = malloc(sizeof(struct exlist_node));
++	if (!node)
++		return -ENOMEM;
++
++	node->data = new;
++
++	if (head)
++		list_insert_head(&list->list, node);
++	else
++		list_insert_tail(&list->list, node);
++
++	return 0;
++}
++
++void *_exlist_headtail(struct exlist *list, bool head)
++{
++	struct exlist_node *node;
++
++	node = head ? list_head(&list->list) : list_tail(&list->list);
++
++	return node ? node->data : NULL;
++}
++
++void *_exlist_nextprev(struct exlist *list,
++		       struct exlist_iter_cookie *cookie, bool fwd)
++{
++	struct exlist_node *node;
++
++	if (fwd)
++		node = list_next(&list->list, (void *) cookie->private);
++	else
++		node = list_prev(&list->list, (void *) cookie->private);
++
++	cookie->private = (uintptr_t) node;
++
++	return node ? node->data : NULL;
++}
++
++bool exlist_remove(struct exlist *list, void *item)
++{
++	struct exlist_node *node;
++
++	list_for_each(node, &list->list) {
++		if (node->data != item)
++			continue;
++
++		list_remove(&list->list, node);
++		free(node);
++		return true;
++	}
++
++	return false;
++}
++
++void *_exlist_remove_headtail(struct exlist *list, bool head)
++{
++	struct exlist_node *node;
++	void *item;
++
++	if (head)
++		node = list_remove_head(&list->list);
++	else
++		node = list_remove_tail(&list->list);
++
++	item = node->data;
++
++	free(node);
++
++	return item;
++}
+diff --git a/include/jeffpc/exlist.h b/include/jeffpc/exlist.h
+new file mode 100644
+--- /dev/null
++++ b/include/jeffpc/exlist.h
+@@ -0,0 +1,113 @@
++/*
++ * Copyright (c) 2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
++ *
++ * Permission is hereby granted, free of charge, to any person obtaining a copy
++ * of this software and associated documentation files (the "Software"), to deal
++ * in the Software without restriction, including without limitation the rights
++ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
++ * copies of the Software, and to permit persons to whom the Software is
++ * furnished to do so, subject to the following conditions:
++ *
++ * The above copyright notice and this permission notice shall be included in
++ * all copies or substantial portions of the Software.
++ *
++ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
++ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
++ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
++ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
++ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
++ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
++ * SOFTWARE.
++ */
++
++#ifndef __JEFFPC_EXLIST_H
++#define __JEFFPC_EXLIST_H
++
++/*
++ * An external/non-intrusive circular doubly-linked list.
++ */
++
++#include <jeffpc/list.h>
++
++struct exlist {
++	struct list list;
++};
++
++struct exlist_iter_cookie {
++	uintptr_t private;
++};
++
++/* internal helpers */
++extern int _exlist_insert(struct exlist *list, void *new, bool head);
++extern void *_exlist_headtail(struct exlist *list, bool head);
++extern void *_exlist_nextprev(struct exlist *list,
++			      struct exlist_iter_cookie *cookie, bool fwd);
++extern void *_exlist_remove_headtail(struct exlist *list, bool head);
++
++/* API */
++extern void exlist_create(struct exlist *list);
++extern bool exlist_remove(struct exlist *list, void *item);
++
++static inline void exlist_destroy(struct exlist *list)
++{
++	list_destroy(&list->list);
++}
++
++static inline void exlist_move_tail(struct exlist *dst, struct exlist *src)
++{
++	list_move_tail(&dst->list, &src->list);
++}
++
++static inline bool exlist_is_empty(struct exlist *list)
++{
++	return list_is_empty(&list->list);
++}
++
++static inline void exlist_insert_head(struct exlist *list, void *new)
++{
++	_exlist_insert(list, new, true);
++}
++
++static inline void exlist_insert_tail(struct exlist *list, void *new)
++{
++	_exlist_insert(list, new, false);
++}
++
++static inline void *exlist_head(struct exlist *list)
++{
++	return _exlist_headtail(list, true);
++}
++
++static inline void *exlist_tail(struct exlist *list)
++{
++	return _exlist_headtail(list, false);
++}
++
++static inline void *exlist_next(struct exlist *list,
++				struct exlist_iter_cookie *cookie)
++{
++	return _exlist_nextprev(list, cookie, true);
++}
++
++static inline void *exlist_prev(struct exlist *list,
++				struct exlist_iter_cookie *cookie)
++{
++	return _exlist_nextprev(list, cookie, false);
++}
++
++static inline void *exlist_remove_head(struct exlist *list)
++{
++	return _exlist_remove_headtail(list, true);
++}
++
++static inline void *exlist_remove_tail(struct exlist *list)
++{
++	return _exlist_remove_headtail(list, false);
++}
++
++#define exlist_for_each(node, list) \
++	for (node = exlist_head(list); \
++	     node != NULL; \
++	     node = exlist_next(list, node))
++
++#endif
+diff --git a/mapfile-vers b/mapfile-vers
+--- a/mapfile-vers
++++ b/mapfile-vers
+@@ -82,6 +82,14 @@ JEFFPC_0.10 {
+ 		save_stacktrace;
+ 		xstrerror;
+ 
++		# exlist
++		_exlist_headtail;
++		_exlist_insert;
++		_exlist_nextprev;
++		_exlist_remove_headtail;
++		exlist_create;
++		exlist_remove;
++
+ 		# hexdump
+ 		hexdump;
+ 		hexdumpz;