* deque: New module @ 2015-12-23 12:11 Dan Good 2015-12-28 3:43 ` David Gibson 0 siblings, 1 reply; 5+ messages in thread From: Dan Good @ 2015-12-23 12:11 UTC (permalink / raw) To: ccan 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 ^ permalink raw reply related [flat|nested] 5+ messages in thread
* Re: deque: New module 2015-12-23 12:11 deque: New module Dan Good @ 2015-12-28 3:43 ` David Gibson 2015-12-28 3:44 ` David Gibson 2015-12-29 6:00 ` Dan Good 0 siblings, 2 replies; 5+ messages in thread From: David Gibson @ 2015-12-28 3:43 UTC (permalink / raw) To: Dan Good; +Cc: ccan [-- 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 ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: deque: New module 2015-12-28 3:43 ` David Gibson @ 2015-12-28 3:44 ` David Gibson 2015-12-29 6:00 ` Dan Good 1 sibling, 0 replies; 5+ messages in thread From: David Gibson @ 2015-12-28 3:44 UTC (permalink / raw) To: Dan Good; +Cc: ccan [-- 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 ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: deque: New module 2015-12-28 3:43 ` David Gibson 2015-12-28 3:44 ` David Gibson @ 2015-12-29 6:00 ` Dan Good 2015-12-31 12:38 ` David Gibson 1 sibling, 1 reply; 5+ messages in thread From: Dan Good @ 2015-12-29 6:00 UTC (permalink / raw) To: David Gibson; +Cc: ccan [-- 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 ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: deque: New module 2015-12-29 6:00 ` Dan Good @ 2015-12-31 12:38 ` David Gibson 0 siblings, 0 replies; 5+ messages in thread From: David Gibson @ 2015-12-31 12:38 UTC (permalink / raw) To: Dan Good; +Cc: ccan [-- 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 ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2015-12-31 12:38 UTC | newest] Thread overview: 5+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2015-12-23 12:11 deque: New module Dan Good 2015-12-28 3:43 ` David Gibson 2015-12-28 3:44 ` David Gibson 2015-12-29 6:00 ` Dan Good 2015-12-31 12:38 ` David Gibson
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox