2 * Copyright (c) 2007, Novell Inc.
4 * This program is licensed under the BSD license, read LICENSE.BSD
5 * for further information
20 queue_extra_space(int size)
34 q->alloc = q->elements = 0;
35 q->count = q->left = 0;
39 queue_init_clone(Queue *target, const Queue *source)
42 if (!source->elements)
44 target->alloc = target->elements = 0;
45 target->count = target->left = 0;
48 extra_space = queue_extra_space(source->count);
49 target->alloc = target->elements = solv_malloc2(source->count + extra_space, sizeof(Id));
51 memcpy(target->alloc, source->elements, source->count * sizeof(Id));
52 target->count = source->count;
53 target->left = extra_space;
57 queue_init_buffer(Queue *q, Id *buf, int size)
70 q->alloc = q->elements = 0;
71 q->count = q->left = 0;
74 /* make room for one element at the tail of the queue */
76 queue_alloc_one(Queue *q)
78 if (q->alloc && q->alloc != q->elements)
80 /* there's room at the front. just move data */
81 int l = q->elements - q->alloc;
83 memmove(q->alloc, q->elements, q->count * sizeof(Id));
89 int extra_space = queue_extra_space(q->count);
92 q->alloc = solv_malloc2(q->count + extra_space, sizeof(Id));
94 memcpy(q->alloc, q->elements, q->count * sizeof(Id));
97 q->alloc = solv_realloc2(q->alloc, q->count + extra_space, sizeof(Id));
98 q->elements = q->alloc;
99 q->left = extra_space;
103 /* make room for an element in front of queue */
105 queue_alloc_one_head(Queue *q)
108 if (!q->alloc || !q->left)
109 queue_alloc_one(q); /* easy way to make room */
110 extra_space = queue_extra_space(q->count);
111 l = q->left > extra_space ? extra_space : q->left;
113 memmove(q->elements + l, q->elements, q->count * sizeof(Id));
119 queue_insert(Queue *q, int pos, Id id)
121 queue_push(q, id); /* make room */
122 if (pos < q->count - 1)
124 memmove(q->elements + pos + 1, q->elements + pos, (q->count - 1 - pos) * sizeof(Id));
125 q->elements[pos] = id;
130 queue_delete(Queue *q, int pos)
134 if (pos < q->count - 1)
135 memmove(q->elements + pos, q->elements + pos + 1, (q->count - 1 - pos) * sizeof(Id));
141 queue_insert2(Queue *q, int pos, Id id1, Id id2)
143 queue_push(q, id1); /* make room */
144 queue_push(q, id2); /* make room */
145 if (pos < q->count - 2)
147 memmove(q->elements + pos + 2, q->elements + pos, (q->count - 2 - pos) * sizeof(Id));
148 q->elements[pos] = id1;
149 q->elements[pos + 1] = id2;
154 queue_delete2(Queue *q, int pos)
158 if (pos == q->count - 1)
164 if (pos < q->count - 2)
165 memmove(q->elements + pos, q->elements + pos + 2, (q->count - 2 - pos) * sizeof(Id));
171 queue_insertn(Queue *q, int pos, int n, const Id *elements)
178 queue_prealloc(q, n);
180 memmove(q->elements + pos + n, q->elements + pos, (q->count - pos) * sizeof(Id));
182 memcpy(q->elements + pos, elements, n * sizeof(Id));
184 memset(q->elements + pos, 0, n * sizeof(Id));
190 queue_deleten(Queue *q, int pos, int n)
192 if (n <= 0 || pos >= q->count)
194 if (pos + n >= q->count)
197 memmove(q->elements + pos, q->elements + pos + n, (q->count - n - pos) * sizeof(Id));
202 /* pre-allocate room for n more elements */
204 queue_prealloc(Queue *q, int n)
206 int off, extra_space;
207 if (n <= 0 || q->left >= n)
211 off = q->elements - q->alloc;
212 extra_space = queue_extra_space(q->count + n);
213 q->alloc = solv_realloc2(q->alloc, off + q->count + n + extra_space, sizeof(Id));
214 q->elements = q->alloc + off;
215 q->left = n + extra_space;