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_clone(Queue *t, Queue *s)
  21 {
  22   t->alloc = t->elements = sat_malloc2(s->count + 8, sizeof(Id));
  23   if (s->count)
  24     memcpy(t->alloc, s->elements, s->count * sizeof(Id));
  25   t->count = s->count;
  26   t->left = 8;
  27 }
  28
  29 void
  30 queue_init(Queue *q)
  31 {
  32   q->alloc = q->elements = 0;
  33   q->count = q->left = 0;
  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 && q->alloc != q->elements)
  58     {
  59       memmove(q->alloc, q->elements, q->count * sizeof(Id));
  60       q->left += q->elements - q->alloc;
  61       q->elements = q->alloc;
  62     }
  63   else if (q->alloc)
  64     {
  65       q->elements = q->alloc = sat_realloc2(q->alloc, q->count + 8, sizeof(Id));
  66       q->left += 8;
  67     }
  68   else
  69     {
  70       q->alloc = sat_malloc2(q->count + 8, sizeof(Id));
  71       if (q->count)
  72         memcpy(q->alloc, q->elements, q->count * sizeof(Id));
  73       q->elements = q->alloc;
  74       q->left += 8;
  75     }
  76 }
  77
  78 void
  79 queue_insert(Queue *q, int pos, Id id)
  80 {
  81   queue_push(q, id);    /* make room */
  82   if (pos < q->count - 1)
  83     {
  84       memmove(q->elements + pos + 1, q->elements + pos, (q->count - 1 - pos) * sizeof(Id));
  85       q->elements[pos] = id;
  86     }
  87 }
  88
  89 void
  90 queue_delete(Queue *q, int pos)
  91 {
  92   if (pos >= q->count)
  93     return;
  94   if (pos < q->count - 1)
  95     memmove(q->elements + pos, q->elements + pos + 1, (q->count - 1 - pos) * sizeof(Id));
  96   q->left++;
  97   q->count--;
  98 }
  99
 100 void
 101 queue_insert2(Queue *q, int pos, Id id1, Id id2)
 102 {
 103   queue_push(q, id1);   /* make room */
 104   queue_push(q, id2);   /* make room */
 105   if (pos < q->count - 2)
 106     {
 107       memmove(q->elements + pos + 2, q->elements + pos, (q->count - 2 - pos) * sizeof(Id));
 108       q->elements[pos] = id1;
 109       q->elements[pos] = id2;
 110     }
 111 }
 112
 113 void
 114 queue_delete2(Queue *q, int pos)
 115 {
 116   if (pos >= q->count)
 117     return;
 118   if (pos == q->count - 1)
 119     {
 120       q->left++;
 121       q->count--;
 122       return;
 123     }
 124   if (pos < q->count - 2)
 125     memmove(q->elements + pos, q->elements + pos + 2, (q->count - 2 - pos) * sizeof(Id));
 126   q->left += 2;
 127   q->count -= 2;
 128 }