2
* tdq.c: implement a 'to-do queue', a simple de-duplicating to-do
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.
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?
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].
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.
32
int ip, op; /* in pointer, out pointer */
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++) {
47
tdq->ip = tdq->op = 0;
51
void tdq_free(tdq *tdq)
58
void tdq_add(tdq *tdq, int k)
60
assert((unsigned)k < (unsigned)tdq->n);
62
tdq->queue[tdq->ip] = k;
64
if (++tdq->ip == tdq->n)
69
int tdq_remove(tdq *tdq)
71
int ret = tdq->queue[tdq->op];
77
if (++tdq->op == tdq->n)
83
void tdq_fill(tdq *tdq)
86
for (i = 0; i < tdq->n; i++)
added
removed
tdq.c
