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 void
  20 queue_init(Queue *q)
  21 {
  22   q->alloc = q->elements = 0;
  23   q->count = q->left = 0;
  24 }
  25
  26 void
  27 queue_init_clone(Queue *t, Queue *s)
  28 {
  29   t->alloc = t->elements = sat_malloc2(s->count + 8, sizeof(Id));
  30   if (s->count)
  31     memcpy(t->alloc, s->elements, s->count * sizeof(Id));
  32   t->count = s->count;
  33   t->left = 8;
  34 }
  35
  36 void
  37 queue_init_buffer(Queue *q, Id *buf, int size)
  38 {
  39   q->alloc = 0;
  40   q->elements = buf;
  41   q->count = 0;
  42   q->left = size;
  43 }
  44
  45 void
  46 queue_free(Queue *q)
  47 {
  48   if (q->alloc)
  49     sat_free(q->alloc);
  50   q->alloc = q->elements = 0;
  51   q->count = q->left = 0;
  52 }
  53
  54 void
  55 queue_alloc_one(Queue *q)
  56 {
  57   if (!q->alloc)
  58     {
  59       /* queue was created with queue_init_buf */
  60       q->alloc = sat_malloc2(q->count + 8, sizeof(Id));
  61       if (q->count)
  62         memcpy(q->alloc, q->elements, q->count * sizeof(Id));
  63       q->elements = q->alloc;
  64       q->left = 8;
  65     }
  66   else if (q->alloc != q->elements)
  67     {
  68       int l = q->elements - q->alloc;
  69       if (q->count)
  70         memmove(q->alloc, q->elements, q->count * sizeof(Id));
  71       q->elements -= l;
  72       q->left += l;
  73     }
  74   else
  75     {
  76       q->elements = q->alloc = sat_realloc2(q->alloc, q->count + 8, sizeof(Id));
  77       q->left = 8;
  78     }
  79 }
  80
  81 /* make room for an element in front of queue */
  82 void
  83 queue_alloc_one_head(Queue *q)
  84 {
  85   int l;
  86   if (!q->alloc || !q->left)
  87     queue_alloc_one(q);
  88   l = q->left > 8 ? 8 : q->left;
  89   if (q->count);
  90     memmove(q->elements + l, q->elements, q->count * sizeof(Id));
  91   q->elements += l;
  92   q->left -= l;
  93 }
  94
  95 void
  96 queue_insert(Queue *q, int pos, Id id)
  97 {
  98   queue_push(q, id);    /* make room */
  99   if (pos < q->count - 1)
 100     {
 101       memmove(q->elements + pos + 1, q->elements + pos, (q->count - 1 - pos) * sizeof(Id));
 102       q->elements[pos] = id;
 103     }
 104 }
 105
 106 void
 107 queue_delete(Queue *q, int pos)
 108 {
 109   if (pos >= q->count)
 110     return;
 111   if (pos < q->count - 1)
 112     memmove(q->elements + pos, q->elements + pos + 1, (q->count - 1 - pos) * sizeof(Id));
 113   q->left++;
 114   q->count--;
 115 }
 116
 117 void
 118 queue_insert2(Queue *q, int pos, Id id1, Id id2)
 119 {
 120   queue_push(q, id1);   /* make room */
 121   queue_push(q, id2);   /* make room */
 122   if (pos < q->count - 2)
 123     {
 124       memmove(q->elements + pos + 2, q->elements + pos, (q->count - 2 - pos) * sizeof(Id));
 125       q->elements[pos] = id1;
 126       q->elements[pos + 1] = id2;
 127     }
 128 }
 129
 130 void
 131 queue_delete2(Queue *q, int pos)
 132 {
 133   if (pos >= q->count)
 134     return;
 135   if (pos == q->count - 1)
 136     {
 137       q->left++;
 138       q->count--;
 139       return;
 140     }
 141   if (pos < q->count - 2)
 142     memmove(q->elements + pos, q->elements + pos + 2, (q->count - 2 - pos) * sizeof(Id));
 143   q->left += 2;
 144   q->count -= 2;
 145 }