tdq.c

   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 }