deque: New module
[ccan] / ccan / deque / deque.c
1 #include <assert.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include "deque.h"
5
6 int deq_resize_(struct deq *q, unsigned n)
7 {
8         char *t;
9
10         assert(q && n > 0 && n >= q->len);
11
12         if (!(t = malloc(q->esz * n)))
13                 return -1;
14
15         if (q->len) {
16                 unsigned part1 = q->head + q->len <= q->cap ? q->len : q->cap - q->head;
17                 unsigned part2 = q->len - part1;
18                 memcpy(t, q->v + q->head * q->esz, q->esz * part1);
19                 if (part2)
20                         memcpy(t + q->esz * part1, q->v, q->esz * part2);
21         }
22         if (q->cap)
23                 free(q->v);
24
25         q->v    = t;
26         q->head = 0;
27         q->tail = q->len;
28         q->cap  = n;
29
30         return 0;
31 }
32
33 int deq_op_(struct deq *q, enum deq_op op, unsigned *i)
34 {
35         assert(q && i);
36         assert(op == DEQ_PUSH || op == DEQ_POP ||  op == DEQ_SHIFT || op == DEQ_UNSHIFT);
37
38         switch (op) {
39         case DEQ_PUSH:
40         case DEQ_UNSHIFT:
41                 if (q->len == q->cap && deq_resize_(q, q->cap == 0 ? q->min : q->cap * 2) == -1)
42                         return -1;
43                 break;
44         case DEQ_POP:
45         case DEQ_SHIFT:
46                 if (q->cap > q->min) {
47                         if (q->shrink == DEQ_SHRINK_IF_EMPTY && q->len == 1 && deq_resize_(q, q->min) == -1)
48                                 return -1;
49                         if (q->shrink == DEQ_SHRINK_AT_20PCT && (q->len - 1) * 5 <= q->cap && deq_resize_(q, q->cap / 2) == -1)
50                                 return -1;
51                 }
52                 if (q->len == 0)
53                         return 0;
54         }
55
56         switch (op) {
57         case DEQ_PUSH:
58                 *i = q->tail++;
59                 q->tail  %= q->cap;
60                 q->len++;
61                 break;
62         case DEQ_SHIFT:
63                 *i = q->head++;
64                 q->head %= q->cap;
65                 q->len--;
66                 break;
67         case DEQ_POP:
68                 q->tail = (q->tail == 0 ? q->cap : q->tail) - 1;
69                 *i = q->tail;
70                 q->len--;
71                 break;
72         case DEQ_UNSHIFT:
73                 q->head = (q->head == 0 ? q->cap : q->head) - 1;
74                 *i = q->head;
75                 q->len++;
76                 break;
77         }
78
79         return 1;
80 }
81
82 void deq_reset_(struct deq *q)
83 {
84         assert(q);
85
86         if (q->v)
87                 free(q->v);
88
89         q->v = 0;
90         q->head = q->tail = q->len = q->cap = 0;
91 }