src/queue.c

   1 /*
   2  * Copyright (c) 2007, Novell Inc.
   3  *
   4  * This program is licensed under the BSD license, read LICENSE.BSD
   5  * for further information
   6  */
   7
   8 /*
   9  * queue.c
  10  *
  11  */
  12
  13 #include <stdlib.h>
  14 #include <string.h>
  15
  16 #include "queue.h"
  17 #include "util.h"
  18
  19 #define EXTRA_SPACE 8
  20 #define EXTRA_SPACE_HEAD 8
  21
  22 void
  23 queue_init(Queue *q)
  24 {
  25   q->alloc = q->elements = 0;
  26   q->count = q->left = 0;
  27 }
  28
  29 void
  30 queue_init_clone(Queue *t, Queue *s)
  31 {
  32   if (!s->elements)
  33     {
  34       t->alloc = t->elements = 0;
  35       t->count = t->left = 0;
  36       return;
  37     }
  38   t->alloc = t->elements = sat_malloc2(s->count + EXTRA_SPACE, sizeof(Id));
  39   if (s->count)
  40     memcpy(t->alloc, s->elements, s->count * sizeof(Id));
  41   t->count = s->count;
  42   t->left = EXTRA_SPACE;
  43 }
  44
  45 void
  46 queue_init_buffer(Queue *q, Id *buf, int size)
  47 {
  48   q->alloc = 0;
  49   q->elements = buf;
  50   q->count = 0;
  51   q->left = size;
  52 }
  53
  54 void
  55 queue_free(Queue *q)
  56 {
  57   if (q->alloc)
  58     sat_free(q->alloc);
  59   q->alloc = q->elements = 0;
  60   q->count = q->left = 0;
  61 }
  62
  63 void
  64 queue_alloc_one(Queue *q)
  65 {
  66   if (!q->alloc)
  67     {
  68       q->alloc = sat_malloc2(q->count + EXTRA_SPACE, sizeof(Id));
  69       if (q->count)
  70         memcpy(q->alloc, q->elements, q->count * sizeof(Id));
  71       q->elements = q->alloc;
  72       q->left = EXTRA_SPACE;
  73     }
  74   else if (q->alloc != q->elements)
  75     {
  76       int l = q->elements - q->alloc;
  77       if (q->count)
  78         memmove(q->alloc, q->elements, q->count * sizeof(Id));
  79       q->elements -= l;
  80       q->left += l;
  81     }
  82   else
  83     {
  84       q->elements = q->alloc = sat_realloc2(q->alloc, q->count + EXTRA_SPACE, sizeof(Id));
  85       q->left = EXTRA_SPACE;
  86     }
  87 }
  88
  89 /* make room for an element in front of queue */
  90 void
  91 queue_alloc_one_head(Queue *q)
  92 {
  93   int l;
  94   if (!q->alloc || !q->left)
  95     queue_alloc_one(q);
  96   l = q->left > EXTRA_SPACE_HEAD ? EXTRA_SPACE_HEAD : q->left;
  97   if (q->count)
  98     memmove(q->elements + l, q->elements, q->count * sizeof(Id));
  99   q->elements += l;
 100   q->left -= l;
 101 }
 102
 103 void
 104 queue_insert(Queue *q, int pos, Id id)
 105 {
 106   queue_push(q, id);    /* make room */
 107   if (pos < q->count - 1)
 108     {
 109       memmove(q->elements + pos + 1, q->elements + pos, (q->count - 1 - pos) * sizeof(Id));
 110       q->elements[pos] = id;
 111     }
 112 }
 113
 114 void
 115 queue_delete(Queue *q, int pos)
 116 {
 117   if (pos >= q->count)
 118     return;
 119   if (pos < q->count - 1)
 120     memmove(q->elements + pos, q->elements + pos + 1, (q->count - 1 - pos) * sizeof(Id));
 121   q->left++;
 122   q->count--;
 123 }
 124
 125 void
 126 queue_insert2(Queue *q, int pos, Id id1, Id id2)
 127 {
 128   queue_push(q, id1);   /* make room */
 129   queue_push(q, id2);   /* make room */
 130   if (pos < q->count - 2)
 131     {
 132       memmove(q->elements + pos + 2, q->elements + pos, (q->count - 2 - pos) * sizeof(Id));
 133       q->elements[pos] = id1;
 134       q->elements[pos + 1] = id2;
 135     }
 136 }
 137
 138 void
 139 queue_delete2(Queue *q, int pos)
 140 {
 141   if (pos >= q->count)
 142     return;
 143   if (pos == q->count - 1)
 144     {
 145       q->left++;
 146       q->count--;
 147       return;
 148     }
 149   if (pos < q->count - 2)
 150     memmove(q->elements + pos, q->elements + pos + 2, (q->count - 2 - pos) * sizeof(Id));
 151   q->left += 2;
 152   q->count -= 2;
 153 }
 154
 155 void
 156 queue_insertn(Queue *q, int pos, int n)
 157 {
 158   if (n <= 0)
 159     return;
 160   if (pos > q->count)
 161     pos = q->count;
 162   if (q->left < n)
 163     {
 164       int off;
 165       if (!q->alloc)
 166         queue_alloc_one(q);
 167       off = q->elements - q->alloc;
 168       q->alloc = sat_realloc2(q->alloc, off + q->count + n + EXTRA_SPACE, sizeof(Id));
 169       q->elements = q->alloc + off;
 170       q->left = n + EXTRA_SPACE;
 171     }
 172   if (pos < q->count)
 173     memmove(q->elements + pos + n, q->elements + pos, (q->count - pos) * sizeof(Id));
 174   memset(q->elements + pos, 0, n * sizeof(Id));
 175   q->left -= n;
 176   q->count += n;
 177 }
 178
 179 void
 180 queue_deleten(Queue *q, int pos, int n)
 181 {
 182   if (n <= 0 || pos >= q->count)
 183     return;
 184   if (pos + n >= q->count)
 185     n = q->count - pos;
 186   else
 187     memmove(q->elements + pos, q->elements + pos + n, (q->count - n - pos) * sizeof(Id));
 188   q->left += n;
 189   q->count -= n;
 190 }