deque: New module
authorDan Good <dan@dancancode.com>
Wed, 23 Dec 2015 12:11:44 +0000 (12:11 +0000)
committerDavid Gibson <david@gibson.dropbear.id.au>
Mon, 28 Dec 2015 03:34:15 +0000 (14:34 +1100)
deque - type-preserving resizing circular deque

Signed-off-by: Dan Good <dan@dancancode.com>
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Makefile-ccan
ccan/deque/LICENSE [new symlink]
ccan/deque/_info [new file with mode: 0644]
ccan/deque/deque.c [new file with mode: 0644]
ccan/deque/deque.h [new file with mode: 0644]
ccan/deque/test/run1.c [new file with mode: 0644]
ccan/deque/test/run2.c [new file with mode: 0644]
ccan/deque/test/run3.c [new file with mode: 0644]

index 8eac2d73c70586954aa5bed9c0ac86b42abf1423..8d99bbf4cff713da934de045ca5d3ab96a49a156 100644 (file)
@@ -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 (symlink)
index 0000000..4f8ee74
--- /dev/null
@@ -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 (file)
index 0000000..b1a47bb
--- /dev/null
@@ -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 (file)
index 0000000..cb628d3
--- /dev/null
@@ -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 (file)
index 0000000..1e5b4e8
--- /dev/null
@@ -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 (file)
index 0000000..8d953ea
--- /dev/null
@@ -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 (file)
index 0000000..9250210
--- /dev/null
@@ -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 (file)
index 0000000..91f1444
--- /dev/null
@@ -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());
+}