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