b760b8bd |
1 | /* |
2 | * tdq.c: implement a 'to-do queue', a simple de-duplicating to-do |
3 | * list mechanism. |
4 | */ |
5 | |
6 | #include <assert.h> |
7 | |
8 | #include "puzzles.h" |
9 | |
10 | /* |
11 | * Implementation: a tdq consists of a circular buffer of size n |
12 | * storing the integers currently in the queue, plus an array of n |
13 | * booleans indicating whether each integer is already there. |
14 | * |
15 | * Using a circular buffer of size n to store between 0 and n items |
16 | * inclusive has an obvious failure mode: if the input and output |
17 | * pointers are the same, how do you know whether that means the |
18 | * buffer is full or empty? |
19 | * |
20 | * In this application we have a simple way to tell: in the former |
21 | * case, the flags array is all 1s, and in the latter case it's all |
22 | * 0s. So we could spot that case and check, say, flags[0]. |
23 | * |
24 | * However, it's even easier to simply determine whether the queue is |
25 | * non-empty by testing flags[buffer[op]] - that way we don't even |
26 | * _have_ to compare ip against op. |
27 | */ |
28 | |
29 | struct tdq { |
30 | int n; |
31 | int *queue; |
32 | int ip, op; /* in pointer, out pointer */ |
33 | char *flags; |
34 | }; |
35 | |
36 | tdq *tdq_new(int n) |
37 | { |
38 | int i; |
39 | tdq *tdq = snew(struct tdq); |
40 | tdq->queue = snewn(n, int); |
41 | tdq->flags = snewn(n, char); |
42 | for (i = 0; i < n; i++) { |
43 | tdq->queue[i] = 0; |
44 | tdq->flags[i] = 0; |
45 | } |
46 | tdq->n = n; |
47 | tdq->ip = tdq->op = 0; |
48 | return tdq; |
49 | } |
50 | |
51 | void tdq_free(tdq *tdq) |
52 | { |
53 | sfree(tdq->queue); |
54 | sfree(tdq->flags); |
55 | sfree(tdq); |
56 | } |
57 | |
58 | void tdq_add(tdq *tdq, int k) |
59 | { |
60 | assert((unsigned)k < (unsigned)tdq->n); |
61 | if (!tdq->flags[k]) { |
62 | tdq->queue[tdq->ip] = k; |
63 | tdq->flags[k] = 1; |
64 | if (++tdq->ip == tdq->n) |
65 | tdq->ip = 0; |
66 | } |
67 | } |
68 | |
69 | int tdq_remove(tdq *tdq) |
70 | { |
71 | int ret = tdq->queue[tdq->op]; |
72 | |
73 | if (!tdq->flags[ret]) |
74 | return -1; |
75 | |
76 | tdq->flags[ret] = 0; |
77 | if (++tdq->op == tdq->n) |
78 | tdq->op = 0; |
79 | |
80 | return ret; |
81 | } |
82 | |
83 | void tdq_fill(tdq *tdq) |
84 | { |
85 | int i; |
86 | for (i = 0; i < tdq->n; i++) |
87 | tdq_add(tdq, i); |
88 | } |