satsolver 0.16.3
|
00001 /* 00002 * Copyright (c) 2007, Novell Inc. 00003 * 00004 * This program is licensed under the BSD license, read LICENSE.BSD 00005 * for further information 00006 */ 00007 00008 /* 00009 * queue.c 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 /* make room for an element in front of queue */ 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); /* make room */ 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); /* make room */ 00129 queue_push(q, id2); /* make room */ 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 }