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 static inline int
  20 queue_extra_space(int size)
  21 {
  22   if (size < 32)
  23     return 8;
  24   if (size < 64)
  25     return 16;
  26   if (size < 128)
  27     return 32;
  28   return 64;
  29 }
  30
  31 void
  32 queue_init(Queue *q)
  33 {
  34   q->alloc = q->elements = 0;
  35   q->count = q->left = 0;
  36 }
  37
  38 void
  39 queue_init_clone(Queue *t, Queue *s)
  40 {
  41   int extra_space;
  42   if (!s->elements)
  43     {
  44       t->alloc = t->elements = 0;
  45       t->count = t->left = 0;
  46       return;
  47     }
  48   extra_space = queue_extra_space(s->count);
  49   t->alloc = t->elements = solv_malloc2(s->count + extra_space, sizeof(Id));
  50   if (s->count)
  51     memcpy(t->alloc, s->elements, s->count * sizeof(Id));
  52   t->count = s->count;
  53   t->left = extra_space;
  54 }
  55
  56 void
  57 queue_init_buffer(Queue *q, Id *buf, int size)
  58 {
  59   q->alloc = 0;
  60   q->elements = buf;
  61   q->count = 0;
  62   q->left = size;
  63 }
  64
  65 void
  66 queue_free(Queue *q)
  67 {
  68   if (q->alloc)
  69     solv_free(q->alloc);
  70   q->alloc = q->elements = 0;
  71   q->count = q->left = 0;
  72 }
  73
  74 /* make room for one element at the tail of the queue */
  75 void
  76 queue_alloc_one(Queue *q)
  77 {
  78   if (q->alloc && q->alloc != q->elements)
  79     {
  80       /* there's room at the front. just move data */
  81       int l = q->elements - q->alloc;
  82       if (q->count)
  83         memmove(q->alloc, q->elements, q->count * sizeof(Id));
  84       q->elements -= l;
  85       q->left += l;
  86     }
  87   else
  88     {
  89       int extra_space = queue_extra_space(q->count);
  90       if (!q->alloc)
  91         {
  92           q->alloc = solv_malloc2(q->count + extra_space, sizeof(Id));
  93           if (q->count)
  94             memcpy(q->alloc, q->elements, q->count * sizeof(Id));
  95         }
  96       else
  97         q->alloc = solv_realloc2(q->alloc, q->count + extra_space, sizeof(Id));
  98       q->elements = q->alloc;
  99       q->left = extra_space;
 100     }
 101 }
 102
 103 /* make room for an element in front of queue */
 104 void
 105 queue_alloc_one_head(Queue *q)
 106 {
 107   int l, extra_space;
 108   if (!q->alloc || !q->left)
 109     queue_alloc_one(q);         /* easy way to make room */
 110   extra_space = queue_extra_space(q->count);
 111   l = q->left > extra_space ? extra_space : q->left;
 112   if (q->count)
 113     memmove(q->elements + l, q->elements, q->count * sizeof(Id));
 114   q->elements += l;
 115   q->left -= l;
 116 }
 117
 118 void
 119 queue_insert(Queue *q, int pos, Id id)
 120 {
 121   queue_push(q, id);    /* make room */
 122   if (pos < q->count - 1)
 123     {
 124       memmove(q->elements + pos + 1, q->elements + pos, (q->count - 1 - pos) * sizeof(Id));
 125       q->elements[pos] = id;
 126     }
 127 }
 128
 129 void
 130 queue_delete(Queue *q, int pos)
 131 {
 132   if (pos >= q->count)
 133     return;
 134   if (pos < q->count - 1)
 135     memmove(q->elements + pos, q->elements + pos + 1, (q->count - 1 - pos) * sizeof(Id));
 136   q->left++;
 137   q->count--;
 138 }
 139
 140 void
 141 queue_insert2(Queue *q, int pos, Id id1, Id id2)
 142 {
 143   queue_push(q, id1);   /* make room */
 144   queue_push(q, id2);   /* make room */
 145   if (pos < q->count - 2)
 146     {
 147       memmove(q->elements + pos + 2, q->elements + pos, (q->count - 2 - pos) * sizeof(Id));
 148       q->elements[pos] = id1;
 149       q->elements[pos + 1] = id2;
 150     }
 151 }
 152
 153 void
 154 queue_delete2(Queue *q, int pos)
 155 {
 156   if (pos >= q->count)
 157     return;
 158   if (pos == q->count - 1)
 159     {
 160       q->left++;
 161       q->count--;
 162       return;
 163     }
 164   if (pos < q->count - 2)
 165     memmove(q->elements + pos, q->elements + pos + 2, (q->count - 2 - pos) * sizeof(Id));
 166   q->left += 2;
 167   q->count -= 2;
 168 }
 169
 170 void
 171 queue_insertn(Queue *q, int pos, int n, Id *elements)
 172 {
 173   if (n <= 0)
 174     return;
 175   if (pos > q->count)
 176     pos = q->count;
 177   if (q->left < n)
 178     queue_prealloc(q, n);
 179   if (pos < q->count)
 180     memmove(q->elements + pos + n, q->elements + pos, (q->count - pos) * sizeof(Id));
 181   if (elements)
 182     memcpy(q->elements + pos, elements, n * sizeof(Id));
 183   else
 184     memset(q->elements + pos, 0, n * sizeof(Id));
 185   q->left -= n;
 186   q->count += n;
 187 }
 188
 189 void
 190 queue_deleten(Queue *q, int pos, int n)
 191 {
 192   if (n <= 0 || pos >= q->count)
 193     return;
 194   if (pos + n >= q->count)
 195     n = q->count - pos;
 196   else
 197     memmove(q->elements + pos, q->elements + pos + n, (q->count - n - pos) * sizeof(Id));
 198   q->left += n;
 199   q->count -= n;
 200 }
 201
 202 /* pre-allocate room for n more elements */
 203 void
 204 queue_prealloc(Queue *q, int n)
 205 {
 206   int off, extra_space;
 207   if (n <= 0 || q->left >= n)
 208     return;
 209   if (!q->alloc)
 210     queue_alloc_one(q);
 211   off = q->elements - q->alloc;
 212   extra_space = queue_extra_space(q->count + n);
 213   q->alloc = solv_realloc2(q->alloc, off + q->count + n + extra_space, sizeof(Id));
 214   q->elements = q->alloc + off;
 215   q->left = n + extra_space;
 216 }
 217