src/queue.c

   1 /*
   2  * queue.c
   3  *
   4  */
   5
   6 #include <stdlib.h>
   7 #include <string.h>
   8
   9 #include "queue.h"
  10
  11 void
  12 clonequeue(Queue *t, Queue *s)
  13 {
  14   t->alloc = t->elements = malloc((s->count + 8) * sizeof(Id));
  15   if (s->count)
  16     memcpy(t->alloc, s->elements, s->count * sizeof(Id));
  17   t->count = s->count;
  18   t->left = 8;
  19 }
  20
  21 void
  22 queueinit(Queue *q)
  23 {
  24   q->alloc = q->elements = 0;
  25   q->count = q->left = 0;
  26 }
  27
  28 void
  29 queueinit_buffer(Queue *q, Id *buf, int size)
  30 {
  31   q->alloc = 0;
  32   q->elements = buf;
  33   q->count = 0;
  34   q->left = size;
  35 }
  36
  37 void
  38 queuefree(Queue *q)
  39 {
  40   if (q->alloc)
  41     free(q->alloc);
  42   q->alloc = q->elements = 0;
  43   q->count = q->left = 0;
  44 }
  45
  46 Id
  47 queueshift(Queue *q)
  48 {
  49   if (!q->count)
  50     return 0;
  51   q->count--;
  52   return *q->elements++;
  53 }
  54
  55 void
  56 queuepush(Queue *q, Id id)
  57 {
  58   if (!q->left)
  59     {
  60       if (q->alloc && q->alloc != q->elements)
  61         {
  62           memmove(q->alloc, q->elements, q->count * sizeof(Id));
  63           q->left += q->elements - q->alloc;
  64           q->elements = q->alloc;
  65         }
  66       else if (q->alloc)
  67         {
  68           q->elements = q->alloc = realloc(q->alloc, (q->count + 8) * sizeof(Id));
  69           q->left += 8;
  70         }
  71       else
  72         {
  73           q->alloc = malloc((q->count + 8) * sizeof(Id));
  74           if (q->count)
  75             memcpy(q->alloc, q->elements, q->count * sizeof(Id));
  76           q->elements = q->alloc;
  77           q->left += 8;
  78         }
  79     }
  80   q->elements[q->count++] = id;
  81   q->left--;
  82 }
  83
  84 void
  85 queuepushunique(Queue *q, Id id)
  86 {
  87   int i;
  88   for (i = q->count; i > 0; )
  89     if (q->elements[--i] == id)
  90       return;
  91   queuepush(q, id);
  92 }
  93
  94