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