From 4eb5f52c94d6c32f1b8347ee599906d60239e0d4 Mon Sep 17 00:00:00 2001 From: Dan Good Date: Wed, 23 Dec 2015 12:11:44 +0000 Subject: [PATCH] deque: New module deque - type-preserving resizing circular deque Signed-off-by: Dan Good Signed-off-by: David Gibson --- 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 8eac2d73..8d99bbf4 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 00000000..4f8ee740 --- /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 00000000..b1a47bbb --- /dev/null +++ b/ccan/deque/_info @@ -0,0 +1,140 @@ +#include "config.h" +#include +#include + +/** + * 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 + * #include + * #include + * #include + * #include + * + * 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 + */ +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 00000000..cb628d37 --- /dev/null +++ b/ccan/deque/deque.c @@ -0,0 +1,91 @@ +#include +#include +#include +#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 00000000..1e5b4e8e --- /dev/null +++ b/ccan/deque/deque.h @@ -0,0 +1,252 @@ +#ifndef _DEQUE_H +#define _DEQUE_H + +#include + +/** + * 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 00000000..8d953ea4 --- /dev/null +++ b/ccan/deque/test/run1.c @@ -0,0 +1,140 @@ +#include +/* Include the C files directly. */ +#include +#include + +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 00000000..92502104 --- /dev/null +++ b/ccan/deque/test/run2.c @@ -0,0 +1,59 @@ +#include +#include +#include +/* Include the C files directly. */ + +size_t malloc_sz; +#define malloc(x) malloc(malloc_sz = x) +#include + +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 00000000..91f1444e --- /dev/null +++ b/ccan/deque/test/run3.c @@ -0,0 +1,37 @@ +#include +#include +#include +/* Include the C files directly. */ +#include +#include + +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.39.2