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++)