2 * Copyright 2012 GRNET S.A. All rights reserved.
4 * Redistribution and use in source and binary forms, with or
5 * without modification, are permitted provided that the following
8 * 1. Redistributions of source code must retain the above
9 * copyright notice, this list of conditions and the following
11 * 2. Redistributions in binary form must reproduce the above
12 * copyright notice, this list of conditions and the following
13 * disclaimer in the documentation and/or other materials
14 * provided with the distribution.
16 * THIS SOFTWARE IS PROVIDED BY GRNET S.A. ``AS IS'' AND ANY EXPRESS
17 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
19 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL GRNET S.A OR
20 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
23 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
24 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
26 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 * POSSIBILITY OF SUCH DAMAGE.
29 * The views and conclusions contained in the software and
30 * documentation are those of the authors and should not be
31 * interpreted as representing official policies, either expressed
32 * or implied, of GRNET S.A.
35 #include <xtypes/xq.h>
36 #include <xtypes/domain.h>
38 static inline int __snap(xqindex size)
42 return 1 << ((sizeof(size) * 8) - __builtin_clz(size) - 1);
45 void xq_free(struct xq *xq) {
46 xtypes_free((void *)XPTR(&xq->queue));
47 memset(xq, 0, sizeof(struct xq));
50 void xq_init_empty(struct xq *xq, xqindex size, void *mem)
54 XPTRSET(&xq->queue, mem);
55 xq->size = __snap(size);
56 xlock_release(&xq->lock);
59 void xq_init_map(struct xq *xq,
62 xqindex (*mapfn)(xqindex),
65 xqindex t, *qmem = mem;
66 xq->size = __snap(size);
71 XPTRSET(&xq->queue, qmem);
72 for (t = 0; t < count; t++)
74 xlock_release(&xq->lock);
77 void xq_init_seq(struct xq *xq, xqindex size, xqindex count, void *mem)
79 xqindex t, *qmem = mem;
80 xq->size = __snap(size);
85 XPTRSET(&xq->queue, qmem);
86 for (t = 0; t < count; t++)
88 xlock_release(&xq->lock);
91 xqindex *xq_alloc_empty(struct xq *xq, xqindex size)
93 xqindex *mem = xtypes_malloc(size * sizeof(xqindex));
96 xq_init_empty(xq, size, mem);
100 xqindex *xq_alloc_map(struct xq *xq,
103 xqindex (*mapfn)(xqindex) )
105 xqindex *mem = xtypes_malloc(size * sizeof(xqindex));
108 xq_init_map(xq, size, count, mapfn, mem);
112 xqindex *xq_alloc_seq(struct xq *xq, xqindex size, xqindex count)
114 xqindex *mem = xtypes_malloc(size * sizeof(xqindex));
117 xq_init_seq(xq, size, count, mem);
121 xqindex xq_size(struct xq *xq)
126 xqindex xq_count(struct xq *xq)
128 return xq->head - xq->tail - 1;
131 xqindex xq_element(struct xq *xq, xqindex index)
133 return XPTR(&xq->queue)[index & (xq->size - 1)];
136 void xq_print(struct xq *xq)
140 XSEGLOG("xq head: %lu, tail: %lu, size: %lu\n",
141 (unsigned long)xq->head,
142 (unsigned long)xq->tail,
143 (unsigned long)xq->size);
149 XSEGLOG( "%lu %lu\n",
151 (unsigned long)xq_element(xq, i) );
156 xqindex __xq_append_head_idx(struct xq *xq, xqindex nr)
158 xqindex head = xq->head;
159 xq->head = head + nr;
164 xqindex xq_append_heads(struct xq *xq,
168 xqindex i, mask, head;
169 xqindex serial = xlock_acquire(&xq->lock, nr);
171 if (!(xq_count(xq) + nr <= xq->size)) {
177 head = __xq_append_head_idx(xq, nr);
178 for (i = 0; i < nr; i++)
179 XPTR(&xq->queue)[(head + i) & mask] = heads[i];
181 xlock_release(&xq->lock);
186 xqindex __xq_append_head(struct xq *xq, xqindex xqi)
188 if (xq_count(xq) >= xq->size) {
191 XPTR(&xq->queue)[__xq_append_head_idx(xq, 1) & (xq->size -1)] = xqi;
195 xqindex xq_append_head(struct xq *xq, xqindex xqi, unsigned long who)
198 xlock_acquire(&xq->lock, who);
199 serial = __xq_append_head(xq, xqi);
200 xlock_release(&xq->lock);
204 xqindex __xq_pop_head_idx(struct xq *xq, xqindex nr)
206 xqindex head = xq->head - nr;
212 xqindex xq_pop_heads(struct xq *xq,
216 xqindex i, mask, head;
217 xqindex serial = xlock_acquire(&xq->lock, nr);
219 if (xq_count(xq) < nr) {
225 head = __xq_pop_head_idx(xq, nr);
226 for (i = 0; i < nr; i++)
227 heads[i] = XPTR(&xq->queue)[(head - i) & mask];
229 xlock_release(&xq->lock);
234 xqindex __xq_pop_head(struct xq *xq)
236 xqindex value = Noneidx;
239 return XPTR(&xq->queue)[__xq_pop_head_idx(xq, 1) & (xq->size -1)];
242 xqindex xq_pop_head(struct xq *xq, unsigned long who)
244 xqindex value = Noneidx;
245 (void)xlock_acquire(&xq->lock, who);
246 value = __xq_pop_head(xq);
247 xlock_release(&xq->lock);
251 xqindex __xq_peek_head_idx(struct xq *xq, xqindex nr)
253 xqindex head = xq->head - nr;
257 xqindex __xq_peek_head(struct xq *xq)
261 return XPTR(&xq->queue)[__xq_peek_head_idx(xq, 1) & (xq->size -1)];
264 xqindex xq_peek_head(struct xq *xq, unsigned long who)
267 (void)xlock_acquire(&xq->lock, who);
268 value = __xq_peek_head(xq);
269 xlock_release(&xq->lock);
273 xqindex __xq_peek_tail_idx(struct xq *xq, xqindex nr)
275 xqindex tail = xq->tail + nr;
279 xqindex __xq_peek_tail(struct xq *xq)
283 return XPTR(&xq->queue)[__xq_peek_tail_idx(xq, 1) & (xq->size -1)];
286 xqindex xq_peek_tail(struct xq *xq, unsigned long who)
289 (void)xlock_acquire(&xq->lock, who);
290 value = __xq_peek_tail(xq);
291 xlock_release(&xq->lock);
295 xqindex __xq_append_tail_idx(struct xq *xq, xqindex nr)
297 xqindex tail = xq->tail - nr;
303 xqindex xq_append_tails(struct xq *xq,
307 xqindex i, mask, tail;
308 xqindex serial = xlock_acquire(&xq->lock, nr);
310 if (!(xq_count(xq) + nr <= xq->size)) {
316 tail = __xq_append_tail_idx(xq, nr) + nr -1;
317 for (i = 0; i < nr; i++)
318 XPTR(&xq->queue)[(tail - i) & mask] = tails[i];
320 xlock_release(&xq->lock);
325 xqindex __xq_append_tail(struct xq *xq, xqindex xqi)
327 if (!(xq_count(xq) + 1 <= xq->size)) {
330 XPTR(&xq->queue)[__xq_append_tail_idx(xq, 1) & (xq->size -1)] = xqi;
334 xqindex xq_append_tail(struct xq *xq, xqindex xqi, unsigned long who)
336 xqindex serial = Noneidx;
337 xlock_acquire(&xq->lock, who);
338 serial =__xq_append_tail(xq, xqi);
339 xlock_release(&xq->lock);
343 xqindex __xq_pop_tail_idx(struct xq *xq, xqindex nr)
345 xqindex tail = xq->tail;
346 xq->tail = tail + nr;
351 xqindex xq_pop_tails(struct xq *xq, xqindex nr, xqindex *tails)
353 xqindex i, mask, tail;
354 xqindex serial = xlock_acquire(&xq->lock, nr);
356 if (xq_count(xq) < nr) {
362 tail = __xq_pop_tail_idx(xq, nr);
363 for (i = 0; i < nr; i++)
364 tails[i] = XPTR(&xq->queue)[(tail + i) & mask];
366 xlock_release(&xq->lock);
371 xqindex __xq_pop_tail(struct xq *xq)
375 return XPTR(&xq->queue)[__xq_pop_tail_idx(xq, 1) & (xq->size -1)];
378 xqindex xq_pop_tail(struct xq *xq, unsigned long who)
381 (void)xlock_acquire(&xq->lock, who);
382 value = __xq_pop_tail(xq);
383 xlock_release(&xq->lock);
387 int xq_head_to_tail(struct xq *headq, struct xq *tailq, xqindex nr, unsigned long who)
389 xqindex head, tail, hmask, tmask, *hq, *tq, i, ret = -1;
391 if (headq >= tailq) {
392 xlock_acquire(&headq->lock, who);
393 xlock_acquire(&tailq->lock, who);
395 xlock_acquire(&tailq->lock, who);
396 xlock_acquire(&headq->lock, who);
399 if (xq_count(headq) < nr || xq_count(tailq) + nr > tailq->size)
402 hmask = headq->size -1;
403 tmask = tailq->size -1;
404 head = __xq_pop_head_idx(headq, nr);
405 tail = __xq_append_tail_idx(tailq, nr);
406 hq = XPTR(&headq->queue);
407 tq = XPTR(&tailq->queue);
409 for (i = 0; i < nr; i++)
410 tq[(tail + i) & tmask] = hq[(head + i) & hmask];
414 xlock_release(&headq->lock);
415 xlock_release(&tailq->lock);
419 int __xq_check(struct xq *xq, xqindex idx)
422 for (i = xq->tail + 1; i != xq->head ; i++) {
423 val = XPTR(&xq->queue)[i & (xq->size -1)];
430 int xq_check(struct xq *xq, xqindex idx, unsigned long who)
433 xlock_acquire(&xq->lock, who);
434 r = __xq_check(xq, idx);
435 xlock_release(&xq->lock);
439 xqindex __xq_resize(struct xq *xq, struct xq *newxq)
441 xqindex i, mask, mask_new, head, tail, val;
442 xqindex nr = xq_count(xq);
444 if (nr > newxq->size) {
449 mask_new = newxq->size -1;
450 head = __xq_peek_head_idx(xq, nr);
451 tail = __xq_append_tail_idx(newxq, nr) + nr -1;
452 for (i = 0; i < nr; i++) {
453 val = XPTR(&xq->queue)[(head + i) & mask];
454 XPTR(&newxq->queue)[(tail - i) & mask_new] = val;
460 xqindex xq_resize(struct xq *xq, struct xq *newxq, unsigned long who)
463 xlock_acquire(&xq->lock, who);
464 xlock_acquire(&newxq->lock, who);
465 r = __xq_resize(xq, newxq);
466 xlock_release(&newxq->lock);
467 xlock_release(&xq->lock);
472 #include <linux/module.h>
473 #include <xtypes/xq_exports.h>