[ccan] deque: New module
Dan Good
dan at dancancode.com
Wed Dec 23 23:11:44 AEDT 2015
deque - type-preserving resizing circular deque
Signed-off-by: Dan Good <dan at 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 at 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
More information about the ccan
mailing list