00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #include <stdlib.h>
00014 #include <string.h>
00015
00016 #include "queue.h"
00017 #include "util.h"
00018
00019 #define EXTRA_SPACE 8
00020 #define EXTRA_SPACE_HEAD 8
00021
00022 void
00023 queue_init(Queue *q)
00024 {
00025 q->alloc = q->elements = 0;
00026 q->count = q->left = 0;
00027 }
00028
00029 void
00030 queue_init_clone(Queue *t, Queue *s)
00031 {
00032 if (!s->elements)
00033 {
00034 t->alloc = t->elements = 0;
00035 t->count = t->left = 0;
00036 return;
00037 }
00038 t->alloc = t->elements = sat_malloc2(s->count + EXTRA_SPACE, sizeof(Id));
00039 if (s->count)
00040 memcpy(t->alloc, s->elements, s->count * sizeof(Id));
00041 t->count = s->count;
00042 t->left = EXTRA_SPACE;
00043 }
00044
00045 void
00046 queue_init_buffer(Queue *q, Id *buf, int size)
00047 {
00048 q->alloc = 0;
00049 q->elements = buf;
00050 q->count = 0;
00051 q->left = size;
00052 }
00053
00054 void
00055 queue_free(Queue *q)
00056 {
00057 if (q->alloc)
00058 sat_free(q->alloc);
00059 q->alloc = q->elements = 0;
00060 q->count = q->left = 0;
00061 }
00062
00063 void
00064 queue_alloc_one(Queue *q)
00065 {
00066 if (!q->alloc)
00067 {
00068 q->alloc = sat_malloc2(q->count + EXTRA_SPACE, sizeof(Id));
00069 if (q->count)
00070 memcpy(q->alloc, q->elements, q->count * sizeof(Id));
00071 q->elements = q->alloc;
00072 q->left = EXTRA_SPACE;
00073 }
00074 else if (q->alloc != q->elements)
00075 {
00076 int l = q->elements - q->alloc;
00077 if (q->count)
00078 memmove(q->alloc, q->elements, q->count * sizeof(Id));
00079 q->elements -= l;
00080 q->left += l;
00081 }
00082 else
00083 {
00084 q->elements = q->alloc = sat_realloc2(q->alloc, q->count + EXTRA_SPACE, sizeof(Id));
00085 q->left = EXTRA_SPACE;
00086 }
00087 }
00088
00089
00090 void
00091 queue_alloc_one_head(Queue *q)
00092 {
00093 int l;
00094 if (!q->alloc || !q->left)
00095 queue_alloc_one(q);
00096 l = q->left > EXTRA_SPACE_HEAD ? EXTRA_SPACE_HEAD : q->left;
00097 if (q->count);
00098 memmove(q->elements + l, q->elements, q->count * sizeof(Id));
00099 q->elements += l;
00100 q->left -= l;
00101 }
00102
00103 void
00104 queue_insert(Queue *q, int pos, Id id)
00105 {
00106 queue_push(q, id);
00107 if (pos < q->count - 1)
00108 {
00109 memmove(q->elements + pos + 1, q->elements + pos, (q->count - 1 - pos) * sizeof(Id));
00110 q->elements[pos] = id;
00111 }
00112 }
00113
00114 void
00115 queue_delete(Queue *q, int pos)
00116 {
00117 if (pos >= q->count)
00118 return;
00119 if (pos < q->count - 1)
00120 memmove(q->elements + pos, q->elements + pos + 1, (q->count - 1 - pos) * sizeof(Id));
00121 q->left++;
00122 q->count--;
00123 }
00124
00125 void
00126 queue_insert2(Queue *q, int pos, Id id1, Id id2)
00127 {
00128 queue_push(q, id1);
00129 queue_push(q, id2);
00130 if (pos < q->count - 2)
00131 {
00132 memmove(q->elements + pos + 2, q->elements + pos, (q->count - 2 - pos) * sizeof(Id));
00133 q->elements[pos] = id1;
00134 q->elements[pos + 1] = id2;
00135 }
00136 }
00137
00138 void
00139 queue_delete2(Queue *q, int pos)
00140 {
00141 if (pos >= q->count)
00142 return;
00143 if (pos == q->count - 1)
00144 {
00145 q->left++;
00146 q->count--;
00147 return;
00148 }
00149 if (pos < q->count - 2)
00150 memmove(q->elements + pos, q->elements + pos + 2, (q->count - 2 - pos) * sizeof(Id));
00151 q->left += 2;
00152 q->count -= 2;
00153 }
00154
00155 void
00156 queue_insertn(Queue *q, int pos, int n)
00157 {
00158 if (n <= 0)
00159 return;
00160 if (pos > q->count)
00161 pos = q->count;
00162 if (q->left < n)
00163 {
00164 int off;
00165 if (!q->alloc)
00166 queue_alloc_one(q);
00167 off = q->elements - q->alloc;
00168 q->alloc = sat_realloc2(q->alloc, off + q->count + n + EXTRA_SPACE, sizeof(Id));
00169 q->elements = q->alloc + off;
00170 q->left = n + EXTRA_SPACE;
00171 }
00172 if (pos < q->count)
00173 memmove(q->elements + pos + n, q->elements + pos, (q->count - pos) * sizeof(Id));
00174 memset(q->elements + pos, 0, n * sizeof(Id));
00175 q->left -= n;
00176 q->count += n;
00177 }
00178
00179 void
00180 queue_deleten(Queue *q, int pos, int n)
00181 {
00182 if (n <= 0 || pos >= q->count)
00183 return;
00184 if (pos + n >= q->count)
00185 n = q->count - pos;
00186 else
00187 memmove(q->elements + pos, q->elements + pos + n, (q->count - n - pos) * sizeof(Id));
00188 q->left += n;
00189 q->count -= n;
00190 }