deque: New module

deque: New module

[Dan Good]

deque - type-preserving resizing circular deque

Signed-off-by: Dan Good <dan@dancancode.com>
---
 Makefile-ccan          |   1 +
 ccan/deque/LICENSE     |   1 +
 ccan/deque/_info       | 140 +++++++++++++++++++++++++++
 ccan/deque/deque.c     |  91 ++++++++++++++++++
 ccan/deque/deque.h     | 252 +++++++++++++++++++++++++++++++++++++++++++++++++
 ccan/deque/test/run1.c | 140 +++++++++++++++++++++++++++
 ccan/deque/test/run2.c |  59 ++++++++++++
 ccan/deque/test/run3.c |  37 ++++++++
 8 files changed, 721 insertions(+)
 create mode 120000 ccan/deque/LICENSE
 create mode 100644 ccan/deque/_info
 create mode 100644 ccan/deque/deque.c
 create mode 100644 ccan/deque/deque.h
 create mode 100644 ccan/deque/test/run1.c
 create mode 100644 ccan/deque/test/run2.c
 create mode 100644 ccan/deque/test/run3.c

diff --git a/Makefile-ccan b/Makefile-ccan
index 8eac2d7..8d99bbf 100644
--- a/Makefile-ccan
+++ b/Makefile-ccan
@@ -57,6 +57,7 @@ MODS_WITH_SRC := aga \
 	crypto/shachain \
 	daemonize \
 	daemon_with_notify \
+	deque \
 	dgraph \
 	eratosthenes \
 	err \
diff --git a/ccan/deque/LICENSE b/ccan/deque/LICENSE
new file mode 120000
index 0000000..4f8ee74
--- /dev/null
+++ b/ccan/deque/LICENSE
@@ -0,0 +1 @@
+../../licenses/APACHE-2
\ No newline at end of file
diff --git a/ccan/deque/_info b/ccan/deque/_info
new file mode 100644
index 0000000..b1a47bb
--- /dev/null
+++ b/ccan/deque/_info
@@ -0,0 +1,140 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * deque - type-preserving resizing circular deque
+ *
+ * This is a deque (double-ended queue, pronounced deck) implementation using
+ * a resizing circular buffer.  At steady state, deque operations can proceed
+ * perpetually without mallocing.  The initial capacity must be specified and
+ * is a lower bound when shrinking.  Buffer capacity is doubled at enqueue
+ * to a full deque.  Shrink behavior choices are never shrink, shrink to
+ * minimum when the queue is empty, or shrink by half when the queue is at 20%
+ * of capacity.  Operation names are in the Perl/Ruby style.
+ *
+ * Example:
+ *	// Evaluates arithmetic expressions using Dijkstra's two-stack algorithm.
+ *	// Original: http://algs4.cs.princeton.edu/13stacks/EvaluateDeluxe.java.html
+ *	#define _XOPEN_SOURCE 700
+ *	#include <stdio.h>
+ *	#include <stdlib.h>
+ *	#include <ctype.h>
+ *	#include <err.h>
+ *	#include <ccan/deque/deque.h>
+ *
+ *	static double eval(char op, double a, double b)
+ *	{
+ *		switch (op) {
+ *		case '+': return a + b;
+ *		case '-': return a - b;
+ *		case '/': return a / b;
+ *		case '*': return a * b;
+ *		}
+ *		errx(1, "bad op: %c", op);
+ *	}
+ *
+ *	char opchr[] = { '(', ')', '+', '-', '*', '/' };
+ *	int  opprc[] = {  0 ,  0 ,  1 ,  1 ,  2 ,  2  };
+ *
+ *	static int precedence(char op)
+ *	{
+ *		int i;
+ *		for (i = 0; i < sizeof(opchr); i++)
+ *			if (opchr[i] == op)
+ *				return opprc[i];
+ *		return -1;
+ *	}
+ *
+ *	#define ok(x) ({ int n = (x); if (n == -1) err(1, "%s", #x); n; })
+ *
+ *	int main(int argc, char *argv[])
+ *	{
+ *		DEQ_WRAP(char) *ops;
+ *		DEQ_WRAP(double) *vals;
+ *		char *ln = NULL, *p, op;
+ *		size_t lnsz = 0;
+ *		double a, b;
+ *		int n;
+ *
+ *		ok(deq_new(ops,  8, DEQ_NO_SHRINK));
+ *		ok(deq_new(vals, 8, DEQ_NO_SHRINK));
+ *
+ *		while (getline(&ln, &lnsz, stdin) > 0) {
+ *
+ *			for (p = ln; *p; p++) {
+ *				if (isspace(*p))
+ *					continue;
+ *
+ *				if (precedence(*p) == -1) {
+ *					if (sscanf(p, "%lf%n", &a, &n) != 1)
+ *						errx(1, "parse fail: %s", p);
+ *					ok(deq_push(vals, a));
+ *					p += n - 1;
+ *					continue;
+ *				}
+ *
+ *				while (1) {
+ *					if (*p == '(' || deq_last(ops, &op) == 0 || (precedence(*p) > precedence(op))) {
+ *						ok(deq_push(ops, *p));
+ *						break;
+ *					}
+ *
+ *					ok(deq_pop(ops, &op));
+ *
+ *					if (op == '(') {
+ *						assert(*p == ')');
+ *						break;
+ *					}
+ *					else {
+ *						if (deq_len(vals) < 2)
+ *							errx(1, "out of values");
+ *						ok(deq_pop(vals, &b));
+ *						ok(deq_pop(vals, &a));
+ *						ok(deq_push(vals, eval(op, a, b)));
+ *					}
+ *				}
+ *			}
+ *
+ *			while (ok(deq_pop(ops, &op)) == 1) {
+ *				if (deq_len(vals) < 2)
+ *					errx(1, "out of values");
+ *				ok(deq_pop(vals, &b));
+ *				ok(deq_pop(vals, &a));
+ *				ok(deq_push(vals, eval(op, a, b)));
+ *			}
+ *
+ *			if ((n = deq_len(vals)) != 1)
+ *				errx(1, "wrong number of values: %d", n);
+ *
+ *			ok(deq_pop(vals, &a));
+ *			printf("%.lf\n", a);
+ *		}
+ *
+ *		if (ferror(stdin))
+ *			err(1, "getline");
+ *
+ *		deq_free(ops);
+ *		deq_free(vals);
+ *		free(ln);
+ *		exit(0);
+ *	}
+ *
+ * License: APACHE-2
+ * Author: Dan Good <dan@dancancode.com>
+ */
+int main(int argc, char *argv[])
+{
+	/* Expect exactly one argument */
+	if (argc != 2)
+		return 1;
+
+	if (strcmp(argv[1], "depends") == 0)
+		return 0;
+	if (strcmp(argv[1], "testdepends") == 0) {
+		printf("ccan/failtest\n");
+		return 0;
+	}
+
+	return 1;
+}
diff --git a/ccan/deque/deque.c b/ccan/deque/deque.c
new file mode 100644
index 0000000..c984092
--- /dev/null
+++ b/ccan/deque/deque.c
@@ -0,0 +1,91 @@
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+#include "deque.h"
+
+int deq_resize_(struct deq *q, unsigned n)
+{
+	char *t;
+
+	assert(q && n > 0 && n >= q->len);
+
+	if (!(t = malloc(q->esz * n)))
+		return -1;
+
+	if (q->len) {
+		unsigned part1 = q->head + q->len <= q->cap ? q->len : q->cap - q->head;
+		unsigned part2 = q->len - part1;
+		memcpy(t, q->v + q->head * q->esz, q->esz * part1);
+		if (part2)
+			memcpy(t + q->esz * part1, q->v, q->esz * part2);
+	}
+	if (q->cap)
+		free(q->v);
+
+	q->v    = t;
+	q->head = 0;
+	q->tail = q->len;
+	q->cap  = n;
+
+	return 0;
+}
+
+int deq_op_(struct deq *q, enum deq_op op, unsigned *i)
+{
+	assert(q && i);
+	assert(op == DEQ_PUSH || op == DEQ_POP ||  op == DEQ_SHIFT || op == DEQ_UNSHIFT);
+
+	switch (op) {
+	case DEQ_PUSH:
+	case DEQ_UNSHIFT:
+		if (q->len == q->cap && deq_resize_(q, q->cap == 0 ? q->min : q->cap * 2) == -1)
+			return -1;
+		break;
+	case DEQ_POP:
+	case DEQ_SHIFT:
+		if (q->cap > q->min) {
+			if (q->shrink == DEQ_SHRINK_IF_EMPTY && q->len == 1 && deq_resize_(q, q->min) == -1)
+				return -1;
+			if (q->shrink == DEQ_SHRINK_AT_20PCT && (q->len - 1) * 5 <= q->cap && deq_resize_(q, q->cap / 2) == -1)
+				return -1;
+		}
+		if (q->len == 0)
+			return 0;
+	}
+
+	switch (op) {
+	case DEQ_PUSH:
+		*i = q->tail++;
+		q->tail  %= q->cap;
+		q->len++;
+		break;
+	case DEQ_SHIFT:
+		*i = q->head++;
+		q->head %= q->cap;
+		q->len--;
+		break;
+	case DEQ_POP:
+		q->tail = (q->tail == 0 ? q->cap : q->tail) - 1;
+		*i = q->tail;
+		q->len--;
+		break;
+	case DEQ_UNSHIFT:
+		q->head = (q->head == 0 ? q->cap : q->head) - 1;
+		*i = q->head;
+		q->len++;
+		break;
+	}
+	
+	return 1;
+}
+
+void deq_reset_(struct deq *q)
+{
+	assert(q);
+
+	if (q->v)
+		free(q->v);
+
+	q->v = 0;
+	q->head = q->tail = q->len = q->cap = 0;
+}
diff --git a/ccan/deque/deque.h b/ccan/deque/deque.h
new file mode 100644
index 0000000..1e5b4e8
--- /dev/null
+++ b/ccan/deque/deque.h
@@ -0,0 +1,252 @@
+#ifndef _DEQUE_H
+#define _DEQUE_H
+
+#include <assert.h>
+
+/**
+ * struct deq - deque metadata
+ * @v: char pointer to malloced memory
+ * @head: index of first item in deque
+ * @tail: index after last item in deque
+ * @len: length of deque
+ * @cap: total capacity of deque
+ * @min: initial capacity of deque
+ * @esz: element size
+ * @shrink: flag specifying shrink behavior
+ *
+ * len is distance between head and tail. cap changes with resizing.
+ * shrink must be one of DEQ_NO_SHRINK, DEQ_SHRINK_IF_EMPTY, or DEQ_SHRINK_AT_20PCT.
+ * When shrinking, min is the smallest size.
+ */
+
+enum deq_flag { DEQ_NO_SHRINK, DEQ_SHRINK_IF_EMPTY, DEQ_SHRINK_AT_20PCT };
+
+struct deq {
+	char *v;
+	unsigned head, tail, len, cap, min, esz, shrink;
+};
+
+/**
+ * DEQ_WRAP - declare a wrapper type for struct deq and base type
+ * @basetype: the base type to wrap
+ *
+ * Example:
+ *	// init inline, defer malloc to first push/unshift
+ *	struct point { int x, y; } a;
+ *	DEQ_WRAP(struct point) pointq = DEQ_INIT(sizeof(struct point), 64, DEQ_NO_SHRINK);
+ *
+ *	// or init and malloc by function call
+ *	struct vector3 { double x, y, z; };
+ *	typedef DEQ_WRAP(struct vector3) vector3q_t;
+ *	vector3q_t v;
+ *
+ *	if (deq_init(&v, 16, DEQ_SHRINK_IF_EMPTY) == -1)
+ *		err(1, "deq_init");
+ *
+ *	a.x = 1; a.y = 1;
+ *	// first malloc for pointq
+ *	if (deq_push(&pointq, a) == -1)
+ *		err(1, "deq_push");
+ */
+#define DEQ_WRAP(basetype)	\
+	union {			\
+		struct deq deq;	\
+		basetype *v;	\
+	}
+
+#define DEQ_INIT_DEQ(esz, min, shrink) \
+	(struct deq) { 0, 0, 0, 0, 0, (min), (esz), (shrink) }
+
+#define DEQ_INIT(esz, min, shrink) { .deq = DEQ_INIT_DEQ(esz, min, shrink) }
+
+/**
+ * deq_init - initialize struct deq and malloc
+ * @w: pointer to wrapper
+ * @min: initial capacity of deque
+ * @shrink: flag specifying shrink behavior
+ *
+ * Returns: 0 on success, -1 on error
+ */
+int deq_resize_(struct deq *q, unsigned n);
+#define deq_init(w, min, shrink) ({				\
+	(w)->deq = DEQ_INIT_DEQ(sizeof(*(w)->v), min, shrink);	\
+	deq_resize_(&(w)->deq, (min));				\
+})
+
+/**
+ * deq_new - malloc wrapper and run deq_init
+ * @w: pointer to wrapper
+ * @min: initial capacity of deque
+ * @shrink: flag specifying shrink behavior
+ *
+ * Example:
+ *	vector3q_t *z;
+ *
+ *	if (deq_new(z, 16, DEQ_SHRINK_AT_20PCT) == -1)
+ *		err(1, "deq_new");
+ *	//later
+ *	deq_free(z);
+ *
+ * Returns: pointer on success, NULL on error
+ */
+#define deq_new(w, min, shrink) ({			\
+	w = malloc(sizeof(*w));				\
+	if (w && deq_init(w, min, shrink) == -1) {	\
+		free(w);				\
+		w = 0;					\
+	}						\
+	w ? 0 : -1;					\
+})
+
+enum deq_op { DEQ_PUSH, DEQ_POP, DEQ_SHIFT, DEQ_UNSHIFT };
+int deq_op_(struct deq *q, enum deq_op op, unsigned *i);
+
+/**
+ * deq_push - add element to end of deque
+ * @w: pointer to wrapper
+ * @e: element to add
+ *
+ * Returns: 1 on success, -1 on error
+ */
+#define deq_push(w, e) ({					\
+	unsigned __i;						\
+	int __ret = deq_op_(&(w)->deq, DEQ_PUSH, &__i);		\
+	if (__ret == 1)						\
+		(w)->v[__i] = (e);				\
+	__ret;							\
+})
+
+/**
+ * deq_unshift - add element to beginning of deque
+ * @w: pointer to wrapper
+ * @e: element to add
+ *
+ * Returns: 1 on success, -1 on error
+ */
+#define deq_unshift(w, e) ({					\
+	unsigned __i;						\
+	int __ret = deq_op_(&(w)->deq, DEQ_UNSHIFT, &__i);	\
+	if (__ret == 1)						\
+		(w)->v[__i] = (e);				\
+	__ret;							\
+})
+
+/**
+ * deq_pop - dequeue element from end of deque
+ * @w: pointer to wrapper
+ * @e: pointer to receive dequeued element
+ *
+ * Returns: 1 on success, 0 if deque is empty, -1 on error
+ *
+ * Example:
+ *	DEQ_WRAP(int) w = DEQ_INIT(sizeof(int), 8, DEQ_NO_SHRINK);
+ *	int ret, i;
+ *	// ... after enqueuing some ints
+ *	while ((ret = deq_pop(&w, &i)) == 1)
+ *		printf("%d\n", i);
+ *	if (ret == -1)
+ *		err(1, "deq_pop");
+ */
+#define deq_pop(w, e) ({					\
+	unsigned __i;						\
+	int __ret = deq_op_(&(w)->deq, DEQ_POP, &__i);		\
+	if (__ret == 1)						\
+		*(e) = (w)->v[__i];				\
+	__ret;							\
+})
+
+/**
+ * deq_shift - dequeue element from beginning of deque
+ * @w: pointer to wrapper
+ * @e: pointer to receive dequeued element
+ *
+ * Returns: 1 on success, 0 if deque is empty, -1 on error
+ */
+#define deq_shift(w, e) ({					\
+	unsigned __i;						\
+	int __ret = deq_op_(&(w)->deq, DEQ_SHIFT, &__i);	\
+	if (__ret == 1)						\
+		*(e) = (w)->v[__i];				\
+	__ret;							\
+})
+
+/**
+ * deq_first - get element from beginning of deque, deque is unchanged
+ * @w: pointer to wrapper
+ * @e: pointer to receive element
+ *
+ * Returns: 1 on success, 0 if deque is empty
+ */
+#define deq_first(w, e) ({			\
+	int __ret = 0;				\
+	assert(w);				\
+	assert(e);				\
+	if ((w)->deq.len > 0) {			\
+		*(e) = (w)->v[(w)->deq.head];	\
+		__ret = 1;			\
+	}					\
+	__ret;					\
+})
+
+/**
+ * deq_last - get element from end of deque, deque is unchanged
+ * @w: pointer to wrapper
+ * @e: pointer to receive element
+ *
+ * Returns: 1 on success, 0 if deque is empty
+ */
+#define deq_last(w, e) ({				\
+	int __ret = 0;					\
+	assert(w);					\
+	assert(e);					\
+	if ((w)->deq.len > 0) {				\
+		unsigned __i = (w)->deq.tail == 0 ?	\
+			(w)->deq.cap : (w)->deq.tail;	\
+		*(e) = (w)->v[__i - 1];			\
+		__ret = 1;				\
+	}						\
+	__ret;						\
+})
+
+/**
+ * deq_reset - set struct deq indexes and counters to zero, and free malloced buffer
+ * @w: pointer to wrapper
+ *
+ * Returns: void
+ */
+void deq_reset_(struct deq *q);
+#define deq_reset(w) do {	\
+	assert(w);		\
+	deq_reset_(&(w)->deq);	\
+	(w)->v = 0;		\
+} while (0)
+
+/**
+ * deq_free - run deq_reset and free malloced wrapper
+ * @w: pointer to wrapper
+ *
+ * Returns: void
+ */
+#define deq_free(w) do {	\
+	deq_reset(w);		\
+	free(w);		\
+	w = 0;			\
+} while (0)
+
+/**
+ * deq_len - return deque length
+ * @w: pointer to wrapper
+ *
+ * Returns: int
+ */
+#define deq_len(w) ({ assert(w); (w)->deq.len; })
+
+/**
+ * deq_cap - return deque capacity
+ * @w: pointer to wrapper
+ *
+ * Returns: int
+ */
+#define deq_cap(w) ({ assert(w); (w)->deq.cap; })
+
+#endif
diff --git a/ccan/deque/test/run1.c b/ccan/deque/test/run1.c
new file mode 100644
index 0000000..8d953ea
--- /dev/null
+++ b/ccan/deque/test/run1.c
@@ -0,0 +1,140 @@
+#include <ccan/deque/deque.h>
+/* Include the C files directly. */
+#include <ccan/deque/deque.c>
+#include <ccan/tap/tap.h>
+
+int main(void)
+{
+	char t, *save;
+
+	plan_tests(64);
+
+	DEQ_WRAP(char) *a;
+	ok1(deq_new(a, 4, DEQ_SHRINK_AT_20PCT) == 0);
+	ok1(a->v && a->deq.head == 0 && a->deq.tail == 0 && a->deq.len == 0 && a->deq.cap == 4 &&
+	    a->deq.min == 4 && a->deq.esz == 1 && a->deq.shrink == DEQ_SHRINK_AT_20PCT);
+	save = a->v;
+	memset(a->v, 0, a->deq.cap);
+	ok1(deq_len(a) == 0 && deq_cap(a) == 4);
+
+	ok1(deq_push(a, 'a') == 1);
+	ok1(a->v == save && a->deq.head == 0 && a->deq.tail == 1 && a->deq.len == 1 && a->deq.cap == 4);
+	ok1(a->v[0] == 'a');
+	ok1(t = '~' && deq_first(a, &t) == 1 && t == 'a');
+	ok1(t = '~' && deq_last(a, &t)  == 1 && t == 'a');
+	ok1(deq_len(a) == 1 && deq_cap(a) == 4);
+
+	ok1(t = '~' && deq_pop(a, &t) == 1 && t == 'a');
+	ok1(a->v == save && a->deq.head == 0 && a->deq.tail == 0 && a->deq.len == 0 && a->deq.cap == 4);
+
+	ok1(deq_unshift(a, 'a') == 1);
+	ok1(a->v == save && a->deq.head == 3 && a->deq.tail == 0 && a->deq.len == 1 && a->deq.cap == 4);
+	ok1(a->v[3] == 'a');
+	ok1(t = '~' && deq_first(a, &t) == 1 && t == 'a');
+	ok1(t = '~' && deq_last(a, &t)  == 1 && t == 'a');
+
+	ok1(t = '~' && deq_shift(a, &t) == 1 && t == 'a');
+	ok1(a->v == save && a->deq.head == 0 && a->deq.tail == 0 && a->deq.len == 0 && a->deq.cap == 4);
+
+	memset(a->v, 0, a->deq.cap);
+	deq_push(a, 'a');
+	deq_push(a, 'b');
+	deq_push(a, 'c');
+	deq_push(a, 'd');
+	ok1(a->v == save && a->deq.head == 0 && a->deq.tail == 0 && a->deq.len == 4 && a->deq.cap == 4);
+	ok1(strncmp("abcd", a->v + a->deq.head, a->deq.len) == 0);
+	ok1(t = '~' && deq_first(a, &t) == 1 && t == 'a');
+	ok1(t = '~' && deq_last(a, &t)  == 1 && t == 'd');
+
+	deq_push(a, 'e');
+	ok1(a->v != save);
+	save = a->v;
+	ok1(a->v == save && a->deq.head == 0 && a->deq.tail == 5 && a->deq.len == 5 && a->deq.cap == 8);
+	ok1(strncmp("abcde", a->v + a->deq.head, a->deq.len) == 0);
+	ok1(t = '~' && deq_first(a, &t) == 1 && t == 'a');
+	ok1(t = '~' && deq_last(a, &t)  == 1 && t == 'e');
+	ok1(deq_len(a) == 5 && deq_cap(a) == 8);
+
+
+	deq_push(a, 'f');
+	deq_push(a, 'g');
+	deq_push(a, 'h');
+	ok1(a->v == save && a->deq.head == 0 && a->deq.tail == 0 && a->deq.len == 8 && a->deq.cap == 8);
+	ok1(strncmp("abcdefgh", a->v + a->deq.head, a->deq.len) == 0);
+
+	ok1(t = '~' && deq_shift(a, &t) == 1 && t == 'a');
+	ok1(t = '~' && deq_shift(a, &t) == 1 && t == 'b');
+	ok1(t = '~' && deq_shift(a, &t) == 1 && t == 'c');
+	ok1(t = '~' && deq_shift(a, &t) == 1 && t == 'd');
+	ok1(a->v == save && a->deq.head == 4 && a->deq.tail == 0 && a->deq.len == 4 && a->deq.cap == 8);
+	ok1(strncmp("efgh", a->v + a->deq.head, a->deq.len) == 0);
+	ok1(t = '~' && deq_first(a, &t) == 1 && t == 'e');
+	ok1(t = '~' && deq_last(a, &t)  == 1 && t == 'h');
+
+	deq_push(a, 'i');
+	deq_push(a, 'j');
+	deq_push(a, 'k');
+	deq_push(a, 'l');
+	ok1(a->v == save && a->deq.head == 4 && a->deq.tail == 4 && a->deq.len == 8 && a->deq.cap == 8);
+	ok1(strncmp("ijklefgh", a->v, a->deq.len) == 0);
+
+	deq_push(a, 'm');
+	ok1(a->v != save);
+	save = a->v;
+	ok1(a->v == save && a->deq.head == 0 && a->deq.tail == 9 && a->deq.len == 9 && a->deq.cap == 16);
+	ok1(strncmp("efghijklm", a->v + a->deq.head, a->deq.len) == 0);
+
+	int i;
+	for (i = 9, t = '!'; i <= 128; i++, t = (t == '~' ? '!' : t + 1))
+		deq_push(a, t);
+
+	save = a->v;
+	ok1(a->v == save && a->deq.head == 0 && a->deq.tail == 129 && a->deq.len == 129 && a->deq.cap == 256);
+	int j;
+	for(j = 0; i > 52; i--, j++)
+		deq_shift(a, &t);
+	ok1(a->v == save && a->deq.head == j && a->deq.tail == 129 && a->deq.len == 52 && a->deq.cap == 256);
+	deq_shift(a, &t);
+	ok1(a->v != save);
+	save = a->v;
+	ok1(a->v == save && a->deq.head == 1 && a->deq.tail == 52 && a->deq.len == 51 && a->deq.cap == 128);
+	ok1(strncmp("fghijklmnopqrstuvwxyz{|}~!\"#$%&'()*+,-./0123456789:", a->v + a->deq.head, a->deq.len) == 0);
+
+	a->deq.shrink = DEQ_SHRINK_IF_EMPTY;
+	for(i = a->deq.len; i > 1; i--)
+		deq_shift(a, &t);
+	ok1(a->v == save && a->deq.head == 51 && a->deq.tail == 52 && a->deq.len == 1 && a->deq.cap == 128);
+	deq_shift(a, &t);
+	ok1(a->v != save);
+	save = a->v;
+	ok1(a->v == save && a->deq.head == 1 && a->deq.tail == 1 && a->deq.len == 0 && a->deq.cap == a->deq.min);
+
+	deq_reset(a);
+	ok1(!a->v);
+	ok1(deq_unshift(a, 'a') == 1);
+	save = a->v;
+	memset(a->v, 0, a->deq.cap - 1);
+	ok1(t = '~' && deq_pop(a, &t) == 1 && t == 'a');
+	ok1(a->v == save && a->deq.head == 3 && a->deq.tail == 3 && a->deq.len == 0 && a->deq.cap == 4);
+
+	deq_reset(a);
+	deq_push(a, 'A');
+	save = a->v;
+	deq_unshift(a, 'B');
+	deq_push(a, 'C');
+	deq_unshift(a, 'D');
+	ok1(strncmp("ACDB", a->v, 4) == 0);
+	ok1(a->v == save && a->deq.head == 2 && a->deq.tail == 2 && a->deq.len == 4 && a->deq.cap == 4);
+	ok1(t = '~' && deq_pop(a, &t) == 1 && t == 'C');
+	ok1(t = '~' && deq_shift(a, &t) == 1 && t == 'D');
+	ok1(t = '~' && deq_shift(a, &t) == 1 && t == 'B');
+	ok1(t = '~' && deq_pop(a, &t) == 1 && t == 'A');
+
+	ok1(deq_pop(a, &t) == 0);
+	ok1(deq_shift(a, &t) == 0);
+
+	deq_free(a);
+	ok1(!a);
+
+	return exit_status();
+}
diff --git a/ccan/deque/test/run2.c b/ccan/deque/test/run2.c
new file mode 100644
index 0000000..9250210
--- /dev/null
+++ b/ccan/deque/test/run2.c
@@ -0,0 +1,59 @@
+#include <stdlib.h>
+#include <ccan/tap/tap.h>
+#include <ccan/deque/deque.h>
+/* Include the C files directly. */
+
+size_t malloc_sz;
+#define malloc(x) malloc(malloc_sz = x)
+#include <ccan/deque/deque.c>
+
+int main(void)
+{
+	struct quad { int w, x, y, z; } p, q, r, s, *save;
+	assert(sizeof(struct quad) == sizeof(int) * 4);
+
+	plan_tests(19);
+
+	typedef DEQ_WRAP(struct quad) qd_t;
+	qd_t a_, *a = &a_;
+
+	ok1(deq_init(a, 4, DEQ_SHRINK_AT_20PCT) == 0);
+	ok1(malloc_sz == sizeof(struct quad) * 4);
+
+	ok1(a->v && a->deq.head == 0 && a->deq.tail == 0 && a->deq.len == 0 && a->deq.cap == 4 &&
+	    a->deq.min == 4 && a->deq.esz == sizeof(struct quad) && a->deq.shrink == DEQ_SHRINK_AT_20PCT);
+	save = a->v;
+	memset(a->v, 0xFF, a->deq.cap * sizeof(struct quad));
+
+	int chk[12] = { 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3 };
+	p = (struct quad) { 1, 1, 1, 1 };
+	ok1(deq_push(a, p) == 1);
+	ok1(a->v == save && a->deq.head == 0 && a->deq.tail == 1 && a->deq.len == 1 && a->deq.cap == 4);
+	ok1(memcmp(a->v, chk, sizeof(int) * 4) == 0 && memcmp(a->v, chk, sizeof(chk)) != 0);
+	q = (struct quad) { 2, 2, 2, 2 };
+	ok1(deq_push(a, q) == 1);
+	ok1(a->v == save && a->deq.head == 0 && a->deq.tail == 2 && a->deq.len == 2 && a->deq.cap == 4);
+	ok1(memcmp(a->v, chk, sizeof(int) * 8) == 0 && memcmp(a->v, chk, sizeof(chk)) != 0);
+	r = (struct quad) { 3, 3, 3, 3 };
+	ok1(deq_push(a, r) == 1);
+	ok1(a->v == save && a->deq.head == 0 && a->deq.tail == 3 && a->deq.len == 3 && a->deq.cap == 4);
+	ok1(memcmp(a->v, chk, sizeof(int) * 12) == 0);
+
+	ok1(deq_shift(a, &s) == 1 && s.w == 1 && s.x == 1 && s.y == 1 && s.z == 1);
+	ok1(deq_shift(a, &s) == 1 && s.w == 2 && s.x == 2 && s.y == 2 && s.z == 2);
+	ok1(deq_shift(a, &s) == 1 && s.w == 3 && s.x == 3 && s.y == 3 && s.z == 3);
+	ok1(a->v == save && a->deq.head == 3 && a->deq.tail == 3 && a->deq.len == 0 && a->deq.cap == 4);
+	deq_push(a, p);
+	deq_push(a, q);
+	deq_push(a, r);
+	deq_push(a, p);
+	ok1(a->v == save && a->deq.head == 3 && a->deq.tail == 3 && a->deq.len == 4 && a->deq.cap == 4);
+
+	deq_push(a, q);
+	ok1(a->v != save && a->deq.head == 0 && a->deq.tail == 5 && a->deq.len == 5 && a->deq.cap == 8);
+	ok1(malloc_sz == sizeof(struct quad) * 8);
+
+	deq_reset(a);
+
+	return exit_status();
+}
diff --git a/ccan/deque/test/run3.c b/ccan/deque/test/run3.c
new file mode 100644
index 0000000..91f1444
--- /dev/null
+++ b/ccan/deque/test/run3.c
@@ -0,0 +1,37 @@
+#include <ccan/failtest/failtest_override.h>
+#include <ccan/failtest/failtest.h>
+#include <ccan/deque/deque.h>
+/* Include the C files directly. */
+#include <ccan/deque/deque.c>
+#include <ccan/tap/tap.h>
+
+int main(int argc, char *argv[])
+{
+	failtest_init(argc, argv);
+	plan_tests(18);
+
+	DEQ_WRAP(char) *a;
+	ok1(deq_new(a, 2, DEQ_SHRINK_IF_EMPTY) == 0); // two mallocs
+	ok1(a && deq_push(a, 'a') == 1);
+	ok1(a && deq_push(a, 'b') == 1);
+	ok1(a && deq_push(a, 'c') == 1); // malloc to grow
+
+	char t;
+	ok1(a && deq_pop(a, &t) == 1);
+	ok1(a && deq_pop(a, &t) == 1);
+	ok1(a && deq_pop(a, &t) == 1);   // malloc to shrink
+
+	if (a) deq_free(a);
+
+	DEQ_WRAP(char) *b;
+	ok1(deq_new(b, 5, DEQ_SHRINK_AT_20PCT) == 0); // two mallocs
+	int i;
+	for (i = 0; b && i < 6; i++)
+		ok1(deq_push(b, i + 'A') == 1); // last iteration mallocs to grow
+	for (; b && i > 2; i--)
+		ok1(deq_pop(b, &t) == 1);       // last iteration mallocs to shrink
+
+	if (b) deq_free(b);
+
+	failtest_exit(exit_status());
+}
-- 
2.4.3

_______________________________________________
ccan mailing list
ccan@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/ccan

Re: deque: New module

[David Gibson]

[-- Attachment #1.1: Type: text/plain, Size: 26164 bytes --]

On Wed, Dec 23, 2015 at 12:11:44PM +0000, Dan Good wrote:
> deque - type-preserving resizing circular deque

Concept looks good.  There are some fairly minor nits in the
implementation that I've noted below.  However, none are serious
enough to hold up merging, so I've applied this.  I did modify
trivially to remove some trailing whitespace.

It would be nice to address some of the comments in follow up
commits, particularly some of the portability issues.

> Signed-off-by: Dan Good <dan@dancancode.com>
> ---
>  Makefile-ccan          |   1 +
>  ccan/deque/LICENSE     |   1 +
>  ccan/deque/_info       | 140 +++++++++++++++++++++++++++
>  ccan/deque/deque.c     |  91 ++++++++++++++++++
>  ccan/deque/deque.h     | 252 +++++++++++++++++++++++++++++++++++++++++++++++++
>  ccan/deque/test/run1.c | 140 +++++++++++++++++++++++++++
>  ccan/deque/test/run2.c |  59 ++++++++++++
>  ccan/deque/test/run3.c |  37 ++++++++
>  8 files changed, 721 insertions(+)
>  create mode 120000 ccan/deque/LICENSE
>  create mode 100644 ccan/deque/_info
>  create mode 100644 ccan/deque/deque.c
>  create mode 100644 ccan/deque/deque.h
>  create mode 100644 ccan/deque/test/run1.c
>  create mode 100644 ccan/deque/test/run2.c
>  create mode 100644 ccan/deque/test/run3.c
> 
> diff --git a/Makefile-ccan b/Makefile-ccan
> index 8eac2d7..8d99bbf 100644
> --- a/Makefile-ccan
> +++ b/Makefile-ccan
> @@ -57,6 +57,7 @@ MODS_WITH_SRC := aga \
>  	crypto/shachain \
>  	daemonize \
>  	daemon_with_notify \
> +	deque \
>  	dgraph \
>  	eratosthenes \
>  	err \
> diff --git a/ccan/deque/LICENSE b/ccan/deque/LICENSE
> new file mode 120000
> index 0000000..4f8ee74
> --- /dev/null
> +++ b/ccan/deque/LICENSE
> @@ -0,0 +1 @@
> +../../licenses/APACHE-2
> \ No newline at end of file
> diff --git a/ccan/deque/_info b/ccan/deque/_info
> new file mode 100644
> index 0000000..b1a47bb
> --- /dev/null
> +++ b/ccan/deque/_info
> @@ -0,0 +1,140 @@
> +#include "config.h"
> +#include <stdio.h>
> +#include <string.h>
> +
> +/**
> + * deque - type-preserving resizing circular deque
> + *
> + * This is a deque (double-ended queue, pronounced deck) implementation using
> + * a resizing circular buffer.  At steady state, deque operations can proceed
> + * perpetually without mallocing.  The initial capacity must be specified and
> + * is a lower bound when shrinking.  Buffer capacity is doubled at enqueue
> + * to a full deque.  Shrink behavior choices are never shrink, shrink to
> + * minimum when the queue is empty, or shrink by half when the queue is at 20%
> + * of capacity.  Operation names are in the Perl/Ruby style.
> + *
> + * Example:
> + *	// Evaluates arithmetic expressions using Dijkstra's two-stack algorithm.
> + *	// Original: http://algs4.cs.princeton.edu/13stacks/EvaluateDeluxe.java.html
> + *	#define _XOPEN_SOURCE 700

This define suggests non-portability.

> + *	#include <stdio.h>
> + *	#include <stdlib.h>
> + *	#include <ctype.h>
> + *	#include <err.h>
> + *	#include <ccan/deque/deque.h>
> + *
> + *	static double eval(char op, double a, double b)
> + *	{
> + *		switch (op) {
> + *		case '+': return a + b;
> + *		case '-': return a - b;
> + *		case '/': return a / b;
> + *		case '*': return a * b;
> + *		}
> + *		errx(1, "bad op: %c", op);
> + *	}
> + *
> + *	char opchr[] = { '(', ')', '+', '-', '*', '/' };
> + *	int  opprc[] = {  0 ,  0 ,  1 ,  1 ,  2 ,  2  };
> + *
> + *	static int precedence(char op)
> + *	{
> + *		int i;
> + *		for (i = 0; i < sizeof(opchr); i++)
> + *			if (opchr[i] == op)
> + *				return opprc[i];
> + *		return -1;
> + *	}
> + *
> + *	#define ok(x) ({ int n = (x); if (n == -1) err(1, "%s", #x); n; })
> + *
> + *	int main(int argc, char *argv[])
> + *	{
> + *		DEQ_WRAP(char) *ops;
> + *		DEQ_WRAP(double) *vals;
> + *		char *ln = NULL, *p, op;
> + *		size_t lnsz = 0;
> + *		double a, b;
> + *		int n;
> + *
> + *		ok(deq_new(ops,  8, DEQ_NO_SHRINK));
> + *		ok(deq_new(vals, 8, DEQ_NO_SHRINK));
> + *
> + *		while (getline(&ln, &lnsz, stdin) > 0) {
> + *
> + *			for (p = ln; *p; p++) {
> + *				if (isspace(*p))
> + *					continue;
> + *
> + *				if (precedence(*p) == -1) {
> + *					if (sscanf(p, "%lf%n", &a, &n) != 1)
> + *						errx(1, "parse fail: %s", p);
> + *					ok(deq_push(vals, a));
> + *					p += n - 1;
> + *					continue;
> + *				}
> + *
> + *				while (1) {
> + *					if (*p == '(' || deq_last(ops, &op) == 0 || (precedence(*p) > precedence(op))) {
> + *						ok(deq_push(ops, *p));
> + *						break;
> + *					}
> + *
> + *					ok(deq_pop(ops, &op));
> + *
> + *					if (op == '(') {
> + *						assert(*p == ')');
> + *						break;
> + *					}
> + *					else {
> + *						if (deq_len(vals) < 2)
> + *							errx(1, "out of values");
> + *						ok(deq_pop(vals, &b));
> + *						ok(deq_pop(vals, &a));
> + *						ok(deq_push(vals, eval(op, a, b)));
> + *					}
> + *				}
> + *			}
> + *
> + *			while (ok(deq_pop(ops, &op)) == 1) {
> + *				if (deq_len(vals) < 2)
> + *					errx(1, "out of values");
> + *				ok(deq_pop(vals, &b));
> + *				ok(deq_pop(vals, &a));
> + *				ok(deq_push(vals, eval(op, a, b)));
> + *			}
> + *
> + *			if ((n = deq_len(vals)) != 1)
> + *				errx(1, "wrong number of values: %d", n);
> + *
> + *			ok(deq_pop(vals, &a));
> + *			printf("%.lf\n", a);
> + *		}
> + *
> + *		if (ferror(stdin))
> + *			err(1, "getline");
> + *
> + *		deq_free(ops);
> + *		deq_free(vals);
> + *		free(ln);
> + *		exit(0);
> + *	}
> + *
> + * License: APACHE-2
> + * Author: Dan Good <dan@dancancode.com>
> + */
> +int main(int argc, char *argv[])
> +{
> +	/* Expect exactly one argument */
> +	if (argc != 2)
> +		return 1;
> +
> +	if (strcmp(argv[1], "depends") == 0)
> +		return 0;
> +	if (strcmp(argv[1], "testdepends") == 0) {
> +		printf("ccan/failtest\n");
> +		return 0;
> +	}
> +
> +	return 1;
> +}
> diff --git a/ccan/deque/deque.c b/ccan/deque/deque.c
> new file mode 100644
> index 0000000..c984092
> --- /dev/null
> +++ b/ccan/deque/deque.c
> @@ -0,0 +1,91 @@

It's usual to put a one-line reference to the license at the beginning
of the .c and .h files.  In fact I thought ccanlint already added that
for you.

Also, it's important to *always* include "config.h" before anything else.

> +#include <assert.h>
> +#include <stdlib.h>
> +#include <string.h>
> +#include "deque.h"
> +
> +int deq_resize_(struct deq *q, unsigned n)
> +{
> +	char *t;
> +
> +	assert(q && n > 0 && n >= q->len);
> +
> +	if (!(t = malloc(q->esz * n)))
> +		return -1;
> +
> +	if (q->len) {
> +		unsigned part1 = q->head + q->len <= q->cap ? q->len : q->cap - q->head;
> +		unsigned part2 = q->len - part1;
> +		memcpy(t, q->v + q->head * q->esz, q->esz * part1);
> +		if (part2)
> +			memcpy(t + q->esz * part1, q->v, q->esz * part2);
> +	}
> +	if (q->cap)
> +		free(q->v);
> +
> +	q->v    = t;
> +	q->head = 0;
> +	q->tail = q->len;
> +	q->cap  = n;
> +
> +	return 0;
> +}
> +
> +int deq_op_(struct deq *q, enum deq_op op, unsigned *i)
> +{
> +	assert(q && i);
> +	assert(op == DEQ_PUSH || op == DEQ_POP ||  op == DEQ_SHIFT || op == DEQ_UNSHIFT);

Is there really any reason to multiplex all the operations into a
single function - there's not much shared code, particularly if you
used some grow/shrink helpers.

> +	switch (op) {
> +	case DEQ_PUSH:
> +	case DEQ_UNSHIFT:
> +		if (q->len == q->cap && deq_resize_(q, q->cap == 0 ? q->min : q->cap * 2) == -1)
> +			return -1;
> +		break;
> +	case DEQ_POP:
> +	case DEQ_SHIFT:
> +		if (q->cap > q->min) {
> +			if (q->shrink == DEQ_SHRINK_IF_EMPTY && q->len == 1 && deq_resize_(q, q->min) == -1)
> +				return -1;
> +			if (q->shrink == DEQ_SHRINK_AT_20PCT && (q->len - 1) * 5 <= q->cap && deq_resize_(q, q->cap / 2) == -1)
> +				return -1;
> +		}
> +		if (q->len == 0)
> +			return 0;
> +	}
> +
> +	switch (op) {
> +	case DEQ_PUSH:
> +		*i = q->tail++;
> +		q->tail  %= q->cap;
> +		q->len++;
> +		break;
> +	case DEQ_SHIFT:
> +		*i = q->head++;
> +		q->head %= q->cap;
> +		q->len--;
> +		break;
> +	case DEQ_POP:
> +		q->tail = (q->tail == 0 ? q->cap : q->tail) - 1;
> +		*i = q->tail;
> +		q->len--;
> +		break;
> +	case DEQ_UNSHIFT:
> +		q->head = (q->head == 0 ? q->cap : q->head) - 1;
> +		*i = q->head;
> +		q->len++;
> +		break;
> +	}
> +	
> +	return 1;
> +}
> +
> +void deq_reset_(struct deq *q)
> +{
> +	assert(q);
> +
> +	if (q->v)
> +		free(q->v);
> +
> +	q->v = 0;
> +	q->head = q->tail = q->len = q->cap = 0;
> +}
> diff --git a/ccan/deque/deque.h b/ccan/deque/deque.h
> new file mode 100644
> index 0000000..1e5b4e8
> --- /dev/null
> +++ b/ccan/deque/deque.h
> @@ -0,0 +1,252 @@
> +#ifndef _DEQUE_H
> +#define _DEQUE_H
> +
> +#include <assert.h>
> +
> +/**
> + * struct deq - deque metadata
> + * @v: char pointer to malloced memory
> + * @head: index of first item in deque
> + * @tail: index after last item in deque
> + * @len: length of deque
> + * @cap: total capacity of deque
> + * @min: initial capacity of deque
> + * @esz: element size
> + * @shrink: flag specifying shrink behavior
> + *
> + * len is distance between head and tail. cap changes with resizing.
> + * shrink must be one of DEQ_NO_SHRINK, DEQ_SHRINK_IF_EMPTY, or DEQ_SHRINK_AT_20PCT.
> + * When shrinking, min is the smallest size.
> + */
> +
> +enum deq_flag { DEQ_NO_SHRINK, DEQ_SHRINK_IF_EMPTY, DEQ_SHRINK_AT_20PCT };
> +
> +struct deq {
> +	char *v;
> +	unsigned head, tail, len, cap, min, esz, shrink;
> +};
> +
> +/**
> + * DEQ_WRAP - declare a wrapper type for struct deq and base type
> + * @basetype: the base type to wrap
> + *
> + * Example:
> + *	// init inline, defer malloc to first push/unshift
> + *	struct point { int x, y; } a;
> + *	DEQ_WRAP(struct point) pointq = DEQ_INIT(sizeof(struct point), 64, DEQ_NO_SHRINK);
> + *
> + *	// or init and malloc by function call
> + *	struct vector3 { double x, y, z; };
> + *	typedef DEQ_WRAP(struct vector3) vector3q_t;
> + *	vector3q_t v;
> + *
> + *	if (deq_init(&v, 16, DEQ_SHRINK_IF_EMPTY) == -1)
> + *		err(1, "deq_init");
> + *
> + *	a.x = 1; a.y = 1;
> + *	// first malloc for pointq
> + *	if (deq_push(&pointq, a) == -1)
> + *		err(1, "deq_push");
> + */
> +#define DEQ_WRAP(basetype)	\
> +	union {			\
> +		struct deq deq;	\
> +		basetype *v;	\
> +	}

It might be nice to use the existing tcon module to handle the
wrapping here

> +
> +#define DEQ_INIT_DEQ(esz, min, shrink) \
> +	(struct deq) { 0, 0, 0, 0, 0, (min), (esz), (shrink) }

I think compound literals may be a gcc extension.

> +
> +#define DEQ_INIT(esz, min, shrink) { .deq = DEQ_INIT_DEQ(esz, min, shrink) }
> +
> +/**
> + * deq_init - initialize struct deq and malloc
> + * @w: pointer to wrapper
> + * @min: initial capacity of deque
> + * @shrink: flag specifying shrink behavior
> + *
> + * Returns: 0 on success, -1 on error
> + */
> +int deq_resize_(struct deq *q, unsigned n);
> +#define deq_init(w, min, shrink) ({				\
> +	(w)->deq = DEQ_INIT_DEQ(sizeof(*(w)->v), min, shrink);	\
> +	deq_resize_(&(w)->deq, (min));				\
> +})

And I'm pretty sure statement expressions are a gcc extension.

> +
> +/**
> + * deq_new - malloc wrapper and run deq_init
> + * @w: pointer to wrapper
> + * @min: initial capacity of deque
> + * @shrink: flag specifying shrink behavior
> + *
> + * Example:
> + *	vector3q_t *z;
> + *
> + *	if (deq_new(z, 16, DEQ_SHRINK_AT_20PCT) == -1)
> + *		err(1, "deq_new");
> + *	//later
> + *	deq_free(z);
> + *
> + * Returns: pointer on success, NULL on error
> + */
> +#define deq_new(w, min, shrink) ({			\
> +	w = malloc(sizeof(*w));				\
> +	if (w && deq_init(w, min, shrink) == -1) {	\
> +		free(w);				\
> +		w = 0;					\
> +	}						\
> +	w ? 0 : -1;					\
> +})
> +
> +enum deq_op { DEQ_PUSH, DEQ_POP, DEQ_SHIFT, DEQ_UNSHIFT };
> +int deq_op_(struct deq *q, enum deq_op op, unsigned *i);
> +
> +/**
> + * deq_push - add element to end of deque
> + * @w: pointer to wrapper
> + * @e: element to add
> + *
> + * Returns: 1 on success, -1 on error
> + */
> +#define deq_push(w, e) ({					\
> +	unsigned __i;						\
> +	int __ret = deq_op_(&(w)->deq, DEQ_PUSH, &__i);		\
> +	if (__ret == 1)						\
> +		(w)->v[__i] = (e);				\
> +	__ret;							\
> +})
> +
> +/**
> + * deq_unshift - add element to beginning of deque
> + * @w: pointer to wrapper
> + * @e: element to add
> + *
> + * Returns: 1 on success, -1 on error
> + */
> +#define deq_unshift(w, e) ({					\
> +	unsigned __i;						\
> +	int __ret = deq_op_(&(w)->deq, DEQ_UNSHIFT, &__i);	\
> +	if (__ret == 1)						\
> +		(w)->v[__i] = (e);				\
> +	__ret;							\
> +})
> +
> +/**
> + * deq_pop - dequeue element from end of deque
> + * @w: pointer to wrapper
> + * @e: pointer to receive dequeued element
> + *
> + * Returns: 1 on success, 0 if deque is empty, -1 on error
> + *
> + * Example:
> + *	DEQ_WRAP(int) w = DEQ_INIT(sizeof(int), 8, DEQ_NO_SHRINK);
> + *	int ret, i;
> + *	// ... after enqueuing some ints
> + *	while ((ret = deq_pop(&w, &i)) == 1)
> + *		printf("%d\n", i);
> + *	if (ret == -1)
> + *		err(1, "deq_pop");
> + */
> +#define deq_pop(w, e) ({					\
> +	unsigned __i;						\
> +	int __ret = deq_op_(&(w)->deq, DEQ_POP, &__i);		\
> +	if (__ret == 1)						\
> +		*(e) = (w)->v[__i];				\
> +	__ret;							\
> +})
> +
> +/**
> + * deq_shift - dequeue element from beginning of deque
> + * @w: pointer to wrapper
> + * @e: pointer to receive dequeued element
> + *
> + * Returns: 1 on success, 0 if deque is empty, -1 on error
> + */
> +#define deq_shift(w, e) ({					\
> +	unsigned __i;						\
> +	int __ret = deq_op_(&(w)->deq, DEQ_SHIFT, &__i);	\
> +	if (__ret == 1)						\
> +		*(e) = (w)->v[__i];				\
> +	__ret;							\
> +})
> +
> +/**
> + * deq_first - get element from beginning of deque, deque is unchanged
> + * @w: pointer to wrapper
> + * @e: pointer to receive element
> + *
> + * Returns: 1 on success, 0 if deque is empty
> + */
> +#define deq_first(w, e) ({			\
> +	int __ret = 0;				\
> +	assert(w);				\
> +	assert(e);				\
> +	if ((w)->deq.len > 0) {			\
> +		*(e) = (w)->v[(w)->deq.head];	\
> +		__ret = 1;			\
> +	}					\
> +	__ret;					\
> +})
> +
> +/**
> + * deq_last - get element from end of deque, deque is unchanged
> + * @w: pointer to wrapper
> + * @e: pointer to receive element
> + *
> + * Returns: 1 on success, 0 if deque is empty
> + */
> +#define deq_last(w, e) ({				\
> +	int __ret = 0;					\
> +	assert(w);					\
> +	assert(e);					\
> +	if ((w)->deq.len > 0) {				\
> +		unsigned __i = (w)->deq.tail == 0 ?	\
> +			(w)->deq.cap : (w)->deq.tail;	\
> +		*(e) = (w)->v[__i - 1];			\
> +		__ret = 1;				\
> +	}						\
> +	__ret;						\
> +})
> +
> +/**
> + * deq_reset - set struct deq indexes and counters to zero, and free malloced buffer
> + * @w: pointer to wrapper
> + *
> + * Returns: void
> + */
> +void deq_reset_(struct deq *q);
> +#define deq_reset(w) do {	\
> +	assert(w);		\
> +	deq_reset_(&(w)->deq);	\
> +	(w)->v = 0;		\
> +} while (0)
> +
> +/**
> + * deq_free - run deq_reset and free malloced wrapper
> + * @w: pointer to wrapper
> + *
> + * Returns: void
> + */
> +#define deq_free(w) do {	\
> +	deq_reset(w);		\
> +	free(w);		\
> +	w = 0;			\
> +} while (0)
> +
> +/**
> + * deq_len - return deque length
> + * @w: pointer to wrapper
> + *
> + * Returns: int
> + */
> +#define deq_len(w) ({ assert(w); (w)->deq.len; })
> +
> +/**
> + * deq_cap - return deque capacity
> + * @w: pointer to wrapper
> + *
> + * Returns: int
> + */
> +#define deq_cap(w) ({ assert(w); (w)->deq.cap; })
> +
> +#endif
> diff --git a/ccan/deque/test/run1.c b/ccan/deque/test/run1.c
> new file mode 100644
> index 0000000..8d953ea
> --- /dev/null
> +++ b/ccan/deque/test/run1.c

AFAICT you're not accessing any of the module internals in this test,
so you might be better off making this api1.c, in which case you don't
need to #include deque.c.

That distinction is pretty non-obvious I'll grant you - many existing
modules use run.c when they could be using api.c

> @@ -0,0 +1,140 @@
> +#include <ccan/deque/deque.h>
> +/* Include the C files directly. */
> +#include <ccan/deque/deque.c>
> +#include <ccan/tap/tap.h>
> +
> +int main(void)
> +{
> +	char t, *save;
> +
> +	plan_tests(64);
> +
> +	DEQ_WRAP(char) *a;

Mixing declarations and statements (plan_tests()) isn't supported by
all compilers / C versions.

> +	ok1(deq_new(a, 4, DEQ_SHRINK_AT_20PCT) == 0);
> +	ok1(a->v && a->deq.head == 0 && a->deq.tail == 0 && a->deq.len == 0 && a->deq.cap == 4 &&
> +	    a->deq.min == 4 && a->deq.esz == 1 && a->deq.shrink == DEQ_SHRINK_AT_20PCT);
> +	save = a->v;
> +	memset(a->v, 0, a->deq.cap);
> +	ok1(deq_len(a) == 0 && deq_cap(a) == 4);
> +
> +	ok1(deq_push(a, 'a') == 1);
> +	ok1(a->v == save && a->deq.head == 0 && a->deq.tail == 1 && a->deq.len == 1 && a->deq.cap == 4);
> +	ok1(a->v[0] == 'a');
> +	ok1(t = '~' && deq_first(a, &t) == 1 && t == 'a');
> +	ok1(t = '~' && deq_last(a, &t)  == 1 && t == 'a');
> +	ok1(deq_len(a) == 1 && deq_cap(a) == 4);
> +
> +	ok1(t = '~' && deq_pop(a, &t) == 1 && t == 'a');
> +	ok1(a->v == save && a->deq.head == 0 && a->deq.tail == 0 && a->deq.len == 0 && a->deq.cap == 4);
> +
> +	ok1(deq_unshift(a, 'a') == 1);
> +	ok1(a->v == save && a->deq.head == 3 && a->deq.tail == 0 && a->deq.len == 1 && a->deq.cap == 4);
> +	ok1(a->v[3] == 'a');
> +	ok1(t = '~' && deq_first(a, &t) == 1 && t == 'a');
> +	ok1(t = '~' && deq_last(a, &t)  == 1 && t == 'a');
> +
> +	ok1(t = '~' && deq_shift(a, &t) == 1 && t == 'a');
> +	ok1(a->v == save && a->deq.head == 0 && a->deq.tail == 0 && a->deq.len == 0 && a->deq.cap == 4);
> +
> +	memset(a->v, 0, a->deq.cap);
> +	deq_push(a, 'a');
> +	deq_push(a, 'b');
> +	deq_push(a, 'c');
> +	deq_push(a, 'd');
> +	ok1(a->v == save && a->deq.head == 0 && a->deq.tail == 0 && a->deq.len == 4 && a->deq.cap == 4);
> +	ok1(strncmp("abcd", a->v + a->deq.head, a->deq.len) == 0);
> +	ok1(t = '~' && deq_first(a, &t) == 1 && t == 'a');
> +	ok1(t = '~' && deq_last(a, &t)  == 1 && t == 'd');
> +
> +	deq_push(a, 'e');
> +	ok1(a->v != save);
> +	save = a->v;
> +	ok1(a->v == save && a->deq.head == 0 && a->deq.tail == 5 && a->deq.len == 5 && a->deq.cap == 8);
> +	ok1(strncmp("abcde", a->v + a->deq.head, a->deq.len) == 0);
> +	ok1(t = '~' && deq_first(a, &t) == 1 && t == 'a');
> +	ok1(t = '~' && deq_last(a, &t)  == 1 && t == 'e');
> +	ok1(deq_len(a) == 5 && deq_cap(a) == 8);
> +
> +
> +	deq_push(a, 'f');
> +	deq_push(a, 'g');
> +	deq_push(a, 'h');
> +	ok1(a->v == save && a->deq.head == 0 && a->deq.tail == 0 && a->deq.len == 8 && a->deq.cap == 8);
> +	ok1(strncmp("abcdefgh", a->v + a->deq.head, a->deq.len) == 0);
> +
> +	ok1(t = '~' && deq_shift(a, &t) == 1 && t == 'a');
> +	ok1(t = '~' && deq_shift(a, &t) == 1 && t == 'b');
> +	ok1(t = '~' && deq_shift(a, &t) == 1 && t == 'c');
> +	ok1(t = '~' && deq_shift(a, &t) == 1 && t == 'd');
> +	ok1(a->v == save && a->deq.head == 4 && a->deq.tail == 0 && a->deq.len == 4 && a->deq.cap == 8);
> +	ok1(strncmp("efgh", a->v + a->deq.head, a->deq.len) == 0);
> +	ok1(t = '~' && deq_first(a, &t) == 1 && t == 'e');
> +	ok1(t = '~' && deq_last(a, &t)  == 1 && t == 'h');
> +
> +	deq_push(a, 'i');
> +	deq_push(a, 'j');
> +	deq_push(a, 'k');
> +	deq_push(a, 'l');
> +	ok1(a->v == save && a->deq.head == 4 && a->deq.tail == 4 && a->deq.len == 8 && a->deq.cap == 8);
> +	ok1(strncmp("ijklefgh", a->v, a->deq.len) == 0);
> +
> +	deq_push(a, 'm');
> +	ok1(a->v != save);
> +	save = a->v;
> +	ok1(a->v == save && a->deq.head == 0 && a->deq.tail == 9 && a->deq.len == 9 && a->deq.cap == 16);
> +	ok1(strncmp("efghijklm", a->v + a->deq.head, a->deq.len) == 0);
> +
> +	int i;
> +	for (i = 9, t = '!'; i <= 128; i++, t = (t == '~' ? '!' : t + 1))
> +		deq_push(a, t);
> +
> +	save = a->v;
> +	ok1(a->v == save && a->deq.head == 0 && a->deq.tail == 129 && a->deq.len == 129 && a->deq.cap == 256);
> +	int j;
> +	for(j = 0; i > 52; i--, j++)
> +		deq_shift(a, &t);
> +	ok1(a->v == save && a->deq.head == j && a->deq.tail == 129 && a->deq.len == 52 && a->deq.cap == 256);
> +	deq_shift(a, &t);
> +	ok1(a->v != save);
> +	save = a->v;
> +	ok1(a->v == save && a->deq.head == 1 && a->deq.tail == 52 && a->deq.len == 51 && a->deq.cap == 128);
> +	ok1(strncmp("fghijklmnopqrstuvwxyz{|}~!\"#$%&'()*+,-./0123456789:", a->v + a->deq.head, a->deq.len) == 0);
> +
> +	a->deq.shrink = DEQ_SHRINK_IF_EMPTY;
> +	for(i = a->deq.len; i > 1; i--)
> +		deq_shift(a, &t);
> +	ok1(a->v == save && a->deq.head == 51 && a->deq.tail == 52 && a->deq.len == 1 && a->deq.cap == 128);
> +	deq_shift(a, &t);
> +	ok1(a->v != save);
> +	save = a->v;
> +	ok1(a->v == save && a->deq.head == 1 && a->deq.tail == 1 && a->deq.len == 0 && a->deq.cap == a->deq.min);
> +
> +	deq_reset(a);
> +	ok1(!a->v);
> +	ok1(deq_unshift(a, 'a') == 1);
> +	save = a->v;
> +	memset(a->v, 0, a->deq.cap - 1);
> +	ok1(t = '~' && deq_pop(a, &t) == 1 && t == 'a');
> +	ok1(a->v == save && a->deq.head == 3 && a->deq.tail == 3 && a->deq.len == 0 && a->deq.cap == 4);
> +
> +	deq_reset(a);
> +	deq_push(a, 'A');
> +	save = a->v;
> +	deq_unshift(a, 'B');
> +	deq_push(a, 'C');
> +	deq_unshift(a, 'D');
> +	ok1(strncmp("ACDB", a->v, 4) == 0);
> +	ok1(a->v == save && a->deq.head == 2 && a->deq.tail == 2 && a->deq.len == 4 && a->deq.cap == 4);
> +	ok1(t = '~' && deq_pop(a, &t) == 1 && t == 'C');
> +	ok1(t = '~' && deq_shift(a, &t) == 1 && t == 'D');
> +	ok1(t = '~' && deq_shift(a, &t) == 1 && t == 'B');
> +	ok1(t = '~' && deq_pop(a, &t) == 1 && t == 'A');
> +
> +	ok1(deq_pop(a, &t) == 0);
> +	ok1(deq_shift(a, &t) == 0);
> +
> +	deq_free(a);
> +	ok1(!a);
> +
> +	return exit_status();
> +}
> diff --git a/ccan/deque/test/run2.c b/ccan/deque/test/run2.c
> new file mode 100644
> index 0000000..9250210
> --- /dev/null
> +++ b/ccan/deque/test/run2.c
> @@ -0,0 +1,59 @@
> +#include <stdlib.h>
> +#include <ccan/tap/tap.h>
> +#include <ccan/deque/deque.h>
> +/* Include the C files directly. */
> +
> +size_t malloc_sz;
> +#define malloc(x) malloc(malloc_sz = x)
> +#include <ccan/deque/deque.c>
> +
> +int main(void)
> +{
> +	struct quad { int w, x, y, z; } p, q, r, s, *save;
> +	assert(sizeof(struct quad) == sizeof(int) * 4);
> +
> +	plan_tests(19);
> +
> +	typedef DEQ_WRAP(struct quad) qd_t;
> +	qd_t a_, *a = &a_;
> +
> +	ok1(deq_init(a, 4, DEQ_SHRINK_AT_20PCT) == 0);
> +	ok1(malloc_sz == sizeof(struct quad) * 4);
> +
> +	ok1(a->v && a->deq.head == 0 && a->deq.tail == 0 && a->deq.len == 0 && a->deq.cap == 4 &&
> +	    a->deq.min == 4 && a->deq.esz == sizeof(struct quad) && a->deq.shrink == DEQ_SHRINK_AT_20PCT);
> +	save = a->v;
> +	memset(a->v, 0xFF, a->deq.cap * sizeof(struct quad));
> +
> +	int chk[12] = { 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3 };
> +	p = (struct quad) { 1, 1, 1, 1 };
> +	ok1(deq_push(a, p) == 1);
> +	ok1(a->v == save && a->deq.head == 0 && a->deq.tail == 1 && a->deq.len == 1 && a->deq.cap == 4);
> +	ok1(memcmp(a->v, chk, sizeof(int) * 4) == 0 && memcmp(a->v, chk, sizeof(chk)) != 0);
> +	q = (struct quad) { 2, 2, 2, 2 };
> +	ok1(deq_push(a, q) == 1);
> +	ok1(a->v == save && a->deq.head == 0 && a->deq.tail == 2 && a->deq.len == 2 && a->deq.cap == 4);
> +	ok1(memcmp(a->v, chk, sizeof(int) * 8) == 0 && memcmp(a->v, chk, sizeof(chk)) != 0);
> +	r = (struct quad) { 3, 3, 3, 3 };
> +	ok1(deq_push(a, r) == 1);
> +	ok1(a->v == save && a->deq.head == 0 && a->deq.tail == 3 && a->deq.len == 3 && a->deq.cap == 4);
> +	ok1(memcmp(a->v, chk, sizeof(int) * 12) == 0);
> +
> +	ok1(deq_shift(a, &s) == 1 && s.w == 1 && s.x == 1 && s.y == 1 && s.z == 1);
> +	ok1(deq_shift(a, &s) == 1 && s.w == 2 && s.x == 2 && s.y == 2 && s.z == 2);
> +	ok1(deq_shift(a, &s) == 1 && s.w == 3 && s.x == 3 && s.y == 3 && s.z == 3);
> +	ok1(a->v == save && a->deq.head == 3 && a->deq.tail == 3 && a->deq.len == 0 && a->deq.cap == 4);
> +	deq_push(a, p);
> +	deq_push(a, q);
> +	deq_push(a, r);
> +	deq_push(a, p);
> +	ok1(a->v == save && a->deq.head == 3 && a->deq.tail == 3 && a->deq.len == 4 && a->deq.cap == 4);
> +
> +	deq_push(a, q);
> +	ok1(a->v != save && a->deq.head == 0 && a->deq.tail == 5 && a->deq.len == 5 && a->deq.cap == 8);
> +	ok1(malloc_sz == sizeof(struct quad) * 8);
> +
> +	deq_reset(a);
> +
> +	return exit_status();
> +}
> diff --git a/ccan/deque/test/run3.c b/ccan/deque/test/run3.c
> new file mode 100644
> index 0000000..91f1444
> --- /dev/null
> +++ b/ccan/deque/test/run3.c
> @@ -0,0 +1,37 @@
> +#include <ccan/failtest/failtest_override.h>
> +#include <ccan/failtest/failtest.h>
> +#include <ccan/deque/deque.h>
> +/* Include the C files directly. */
> +#include <ccan/deque/deque.c>
> +#include <ccan/tap/tap.h>
> +
> +int main(int argc, char *argv[])
> +{
> +	failtest_init(argc, argv);
> +	plan_tests(18);
> +
> +	DEQ_WRAP(char) *a;
> +	ok1(deq_new(a, 2, DEQ_SHRINK_IF_EMPTY) == 0); // two mallocs
> +	ok1(a && deq_push(a, 'a') == 1);
> +	ok1(a && deq_push(a, 'b') == 1);
> +	ok1(a && deq_push(a, 'c') == 1); // malloc to grow
> +
> +	char t;
> +	ok1(a && deq_pop(a, &t) == 1);
> +	ok1(a && deq_pop(a, &t) == 1);
> +	ok1(a && deq_pop(a, &t) == 1);   // malloc to shrink
> +
> +	if (a) deq_free(a);
> +
> +	DEQ_WRAP(char) *b;
> +	ok1(deq_new(b, 5, DEQ_SHRINK_AT_20PCT) == 0); // two mallocs
> +	int i;
> +	for (i = 0; b && i < 6; i++)
> +		ok1(deq_push(b, i + 'A') == 1); // last iteration mallocs to grow
> +	for (; b && i > 2; i--)
> +		ok1(deq_pop(b, &t) == 1);       // last iteration mallocs to shrink
> +
> +	if (b) deq_free(b);
> +
> +	failtest_exit(exit_status());
> +}

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

[-- Attachment #2: Type: text/plain, Size: 127 bytes --]

_______________________________________________
ccan mailing list
ccan@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/ccan

Re: deque: New module

[David Gibson]

[-- Attachment #1.1: Type: text/plain, Size: 836 bytes --]

On Mon, Dec 28, 2015 at 02:43:37PM +1100, David Gibson wrote:
> On Wed, Dec 23, 2015 at 12:11:44PM +0000, Dan Good wrote:
> > deque - type-preserving resizing circular deque
> 
> Concept looks good.  There are some fairly minor nits in the
> implementation that I've noted below.  However, none are serious
> enough to hold up merging, so I've applied this.  I did modify
> trivially to remove some trailing whitespace.
> 
> It would be nice to address some of the comments in follow up
> commits, particularly some of the portability issues.

Forgot to say:

I've also added this module to your key so you have push access.

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

[-- Attachment #2: Type: text/plain, Size: 127 bytes --]

_______________________________________________
ccan mailing list
ccan@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/ccan

Re: deque: New module

[Dan Good]

[-- Attachment #1.1: Type: text/plain, Size: 2216 bytes --]

Thank you for the feedback.  I have a practical question - what is the
workflow for making changes to this module, now that it's been merged?  Do
I clone, then branch, edit, commit, push, merge, and finally mail a patch
to the list?  I'm still learning git.  I've been on the rcs/cvs/svn
bandwagon for a long time.

I'd like some clarification on the need for portability.  Once I read your
comments, I came up with an ad-hoc list of platforms I felt I could
reasonably support: major Linux distros, FreeBSD, OS X, and OmniOS.  I
tried the module on each successfully, though ccanlint needed changes to
build on everything but Linux, and the failtest based test went rogue on
two of the platforms.

Compound literals are a feature of C99 (nice article:
http://www.drdobbs.com/the-new-c-compound-literals/184401404).
Intermingled declarations and code are also from C99.  Half of the
platforms above use gcc and half use clang.  Both gcc and clang support
statement expressions.  The _XOPEN_SOURCE define in _info is there for
getline(3) on Linux which is used solely in the demo code in _info.

Is there a set of platforms CCAN targets for support?  Is there some way I
should document that the code is C99?  Would the lines below be the right
way to handle the statement expression dependance?

#if !HAVE_STATEMENT_EXPR
#error Sorry, deque requires statement expressions
#endif

Thanks.  -Dan

On Sun, Dec 27, 2015 at 10:45 PM David Gibson <david@gibson.dropbear.id.au>
wrote:

> On Wed, Dec 23, 2015 at 12:11:44PM +0000, Dan Good wrote:
> > deque - type-preserving resizing circular deque
>
> Concept looks good.  There are some fairly minor nits in the
> implementation that I've noted below.  However, none are serious
> enough to hold up merging, so I've applied this.  I did modify
> trivially to remove some trailing whitespace.
>
> It would be nice to address some of the comments in follow up
> commits, particularly some of the portability issues.
>
 [...]

> --
> David Gibson                    | I'll have my music baroque, and my code
> david AT gibson.dropbear.id.au  | minimalist, thank you.  NOT _the_
> _other_
>                                 | _way_ _around_!
> http://www.ozlabs.org/~dgibson
>

[-- Attachment #1.2: Type: text/html, Size: 3047 bytes --]

[-- Attachment #2: Type: text/plain, Size: 127 bytes --]

_______________________________________________
ccan mailing list
ccan@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/ccan

Re: deque: New module

[David Gibson]

[-- Attachment #1.1: Type: text/plain, Size: 5480 bytes --]

On Tue, Dec 29, 2015 at 06:00:50AM +0000, Dan Good wrote:
> Thank you for the feedback.  I have a practical question - what is the
> workflow for making changes to this module, now that it's been merged?  Do
> I clone, then branch, edit, commit, push, merge, and finally mail a patch
> to the list?

That's one option.  You can certainly continue to send patches to the
mailing list for your own module as you could for any other module, or
patches adding a new module.  That's a good idea if you want some
review on the patches, are looking for a second opinion or whatever.

However, having been added to gitolite you're now also able to push
commits directly to the master ccan repo - as long as they only touch
files within "your" modules.  To do this you need to add
'ccan@ozlabs.org:ccan' as a remote to your git repository.

If you do push commits directly, please do remain disciplined in
making logically consistent commits with good commit messages (and
Signed-off-by lines).  The usual workflow for many contributors to
many projects, including ccan, is to work in your own git tree for a
while, but before pushing to the master, "polish" the commits.  git
rebase -i is very useful for this and allows you to adjust the history
so you have a logical series of changes, with good commit messages.
The idea is to have a "logical" history that would be suitable to send
out as patches for review, even if you don't actually do so.

> I'm still learning git.  I've been on the rcs/cvs/svn
> bandwagon for a long time.

Yes, distributed version control and the different workflows it
allows can take a while to get used to.

In particular people only used to traditional vcs sometimes react in
horror to "changing history" which git allows very easily and is very
common in many free software projects.

In practice, when it comes to the master tree of a significant
project, the cleaned up "logical history" is generally more useful
than incorporating all the details of experiments and since-corrected
mistakes that usually happen during real development.

> I'd like some clarification on the need for portability.  Once I read your
> comments, I came up with an ad-hoc list of platforms I felt I could
> reasonably support: major Linux distros, FreeBSD, OS X, and OmniOS.  I
> tried the module on each successfully, though ccanlint needed changes to
> build on everything but Linux, and the failtest based test went rogue on
> two of the platforms.

Right.  So generally it's better to think in terms of specific
required features, rather than supported platforms.  Many of those
already have #defines tested by the ccan configurator, and others can
be added if necessary.

I think the point here is not so much that we really expect use of
common-but-not-standard features to break things in practice, but more
that it's good to have reliance on these features documented in the
code, to make life easier for anyone who does try to use this on some
obscure compiler in the future.

And yes, I'm quite sure there are many existing portability bugs in
ccanlint and other parts of the existing infrastructure which would
mask portability problems in your module.  But that's not a great
reason to increase the amount of non-portable code.

> Compound literals are a feature of C99 (nice article:
> http://www.drdobbs.com/the-new-c-compound-literals/184401404).

Ah, yes, I'd forgotten that.  I think we are generally assuming at
least C99 availability in ccan, so that one's probably ok.

> Intermingled declarations and code are also from C99.  Half of the
> platforms above use gcc and half use clang.  Both gcc and clang support
> statement expressions.  The _XOPEN_SOURCE define in _info is there for
> getline(3) on Linux which is used solely in the demo code in _info.
> 
> Is there a set of platforms CCAN targets for support?  Is there some way I
> should document that the code is C99?  Would the lines below be the right
> way to handle the statement expression dependance?
> 
> #if !HAVE_STATEMENT_EXPR
> #error Sorry, deque requires statement expressions
> #endif

That's certainly the simplest way of handling this - see the 'minmax'
module for an existing example which requires certain features (in
particular note the Ccanlint: directive in ccan/minmax/_info).

Better still would be having some fallback to avoid statement
expressions, but that is often messy and occaisonally impossible.
Using #error for now and adding a fallback in future if you can (or
letting someone who needs it do so) is entirely reasonable.
> 
> Thanks.  -Dan
> 
> On Sun, Dec 27, 2015 at 10:45 PM David Gibson <david@gibson.dropbear.id.au>
> wrote:
> 
> > On Wed, Dec 23, 2015 at 12:11:44PM +0000, Dan Good wrote:
> > > deque - type-preserving resizing circular deque
> >
> > Concept looks good.  There are some fairly minor nits in the
> > implementation that I've noted below.  However, none are serious
> > enough to hold up merging, so I've applied this.  I did modify
> > trivially to remove some trailing whitespace.
> >
> > It would be nice to address some of the comments in follow up
> > commits, particularly some of the portability issues.
> >
>  [...]
> 
> >

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

[-- Attachment #2: Type: text/plain, Size: 127 bytes --]

_______________________________________________
ccan mailing list
ccan@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/ccan