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