code.grnet.gr Git - archipelago/blob - xseg/xtypes/xq.c

   1 /*
   2  * Copyright 2012 GRNET S.A. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or
   5  * without modification, are permitted provided that the following
   6  * conditions are met:
   7  *
   8  *   1. Redistributions of source code must retain the above
   9  *      copyright notice, this list of conditions and the following
  10  *      disclaimer.
  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.
  15  *
  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.
  28  *
  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.
  33  */
  34
  35 #include <xtypes/xq.h>
  36 #include <xtypes/domain.h>
  37
  38 static inline int __snap(xqindex size)
  39 {
  40         if (!size)
  41                 return 0;
  42         return 1 << ((sizeof(size) * 8) - __builtin_clz(size) - 1);
  43 }
  44
  45 void xq_free(struct xq *xq) {
  46         xtypes_free((void *)XPTR(&xq->queue));
  47         memset(xq, 0, sizeof(struct xq));
  48 }
  49
  50 void xq_init_empty(struct xq *xq, xqindex size, void *mem)
  51 {
  52         xq->head = 1;
  53         xq->tail = 0;
  54         XPTRSET(&xq->queue, mem);
  55         xq->size = __snap(size);
  56         xlock_release(&xq->lock);
  57 }
  58
  59 void xq_init_map(struct xq *xq,
  60                  xqindex size,
  61                  xqindex count,
  62                  xqindex (*mapfn)(xqindex),
  63                  void *mem)
  64 {
  65         xqindex t, *qmem = mem;
  66         xq->size = __snap(size);
  67         if (count > xq->size)
  68                 count = xq->size;
  69         xq->head = count + 1;
  70         xq->tail = 0;
  71         XPTRSET(&xq->queue, qmem);
  72         for (t = 0; t < count; t++)
  73                 qmem[t] = mapfn(t);
  74         xlock_release(&xq->lock);
  75 }
  76
  77 void xq_init_seq(struct xq *xq, xqindex size, xqindex count, void *mem)
  78 {
  79         xqindex t, *qmem = mem;
  80         xq->size = __snap(size);
  81         if (count > xq->size)
  82                 count = xq->size;
  83         xq->head = count + 1;
  84         xq->tail = 0;
  85         XPTRSET(&xq->queue, qmem);
  86         for (t = 0; t < count; t++)
  87                 qmem[t] = t;
  88         xlock_release(&xq->lock);
  89 }
  90
  91 xqindex *xq_alloc_empty(struct xq *xq, xqindex size)
  92 {
  93         xqindex *mem = xtypes_malloc(size * sizeof(xqindex));
  94         if (!mem)
  95                 return mem;
  96         xq_init_empty(xq, size, mem);
  97         return mem;
  98 }
  99
 100 xqindex *xq_alloc_map(struct xq *xq,
 101                         xqindex size,
 102                         xqindex count,
 103                         xqindex (*mapfn)(xqindex)       )
 104 {
 105         xqindex *mem = xtypes_malloc(size * sizeof(xqindex));
 106         if (!mem)
 107                 return mem;
 108         xq_init_map(xq, size, count, mapfn, mem);
 109         return mem;
 110 }
 111
 112 xqindex *xq_alloc_seq(struct xq *xq, xqindex size, xqindex count)
 113 {
 114         xqindex *mem = xtypes_malloc(size * sizeof(xqindex));
 115         if (!mem)
 116                 return mem;
 117         xq_init_seq(xq, size, count, mem);
 118         return mem;
 119 }
 120
 121 xqindex xq_size(struct xq *xq)
 122 {
 123         return xq->size;
 124 }
 125
 126 xqindex xq_count(struct xq *xq)
 127 {
 128         return xq->head - xq->tail - 1;
 129 }
 130
 131 xqindex xq_element(struct xq *xq, xqindex index)
 132 {
 133         return XPTR(&xq->queue)[index & (xq->size - 1)];
 134 }
 135
 136 void xq_print(struct xq *xq)
 137 {
 138         xqindex i;
 139
 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);
 144         i = xq->tail + 1;
 145
 146         for (;;) {
 147                 if (i == xq->head)
 148                         break;
 149                 XSEGLOG(        "%lu %lu\n",
 150                         (unsigned long)i,
 151                         (unsigned long)xq_element(xq, i) );
 152                 i += 1;
 153         }
 154 }
 155
 156 xqindex __xq_append_head_idx(struct xq *xq, xqindex nr)
 157 {
 158         xqindex head = xq->head;
 159         xq->head = head + nr;
 160         return head;
 161 }
 162
 163 /*
 164 xqindex xq_append_heads(struct xq *xq,
 165                         xqindex nr,
 166                         xqindex *heads)
 167 {
 168         xqindex i, mask, head;
 169         xqindex serial = xlock_acquire(&xq->lock, nr);
 170
 171         if (!(xq_count(xq) + nr <= xq->size)) {
 172                 serial = Noneidx;
 173                 goto out;
 174         }
 175
 176         mask = xq->size -1;
 177         head = __xq_append_head_idx(xq, nr);
 178         for (i = 0; i < nr; i++)
 179                 XPTR(&xq->queue)[(head + i) & mask] = heads[i];
 180 out:
 181         xlock_release(&xq->lock);
 182         return serial;
 183 }
 184 */
 185
 186 xqindex __xq_append_head(struct xq *xq, xqindex xqi)
 187 {
 188         if (xq_count(xq) >= xq->size) {
 189                 return Noneidx;
 190         }
 191         XPTR(&xq->queue)[__xq_append_head_idx(xq, 1) & (xq->size -1)] = xqi;
 192         return xqi;
 193
 194 }
 195 xqindex xq_append_head(struct xq *xq, xqindex xqi, unsigned long who)
 196 {
 197         xqindex serial;
 198         xlock_acquire(&xq->lock, who);
 199         serial = __xq_append_head(xq, xqi);
 200         xlock_release(&xq->lock);
 201         return serial;
 202 }
 203
 204 xqindex __xq_pop_head_idx(struct xq *xq, xqindex nr)
 205 {
 206         xqindex head = xq->head - nr;
 207         xq->head = head;
 208         return head;
 209 }
 210
 211 /*
 212 xqindex xq_pop_heads(struct xq *xq,
 213                         xqindex nr,
 214                         xqindex *heads)
 215 {
 216         xqindex i, mask, head;
 217         xqindex serial = xlock_acquire(&xq->lock, nr);
 218
 219         if (xq_count(xq) < nr) {
 220                 serial = Noneidx;
 221                 goto out;
 222         }
 223
 224         mask = xq->size -1;
 225         head = __xq_pop_head_idx(xq, nr);
 226         for (i = 0; i < nr; i++)
 227                 heads[i] = XPTR(&xq->queue)[(head - i) & mask];
 228 out:
 229         xlock_release(&xq->lock);
 230         return serial;
 231 }
 232 */
 233
 234 xqindex __xq_pop_head(struct xq *xq)
 235 {
 236         xqindex value = Noneidx;
 237         if (!xq_count(xq))
 238                 return value;
 239         return XPTR(&xq->queue)[__xq_pop_head_idx(xq, 1) & (xq->size -1)];
 240 }
 241
 242 xqindex xq_pop_head(struct xq *xq, unsigned long who)
 243 {
 244         xqindex value = Noneidx;
 245         (void)xlock_acquire(&xq->lock, who);
 246         value = __xq_pop_head(xq);
 247         xlock_release(&xq->lock);
 248         return value;
 249 }
 250
 251 xqindex __xq_peek_head_idx(struct xq *xq, xqindex nr)
 252 {
 253         xqindex head = xq->head - nr;
 254         return head;
 255 }
 256
 257 xqindex __xq_peek_head(struct xq *xq)
 258 {
 259         if (!xq_count(xq))
 260                 return Noneidx;
 261         return XPTR(&xq->queue)[__xq_peek_head_idx(xq, 1) & (xq->size -1)];
 262 }
 263
 264 xqindex xq_peek_head(struct xq *xq, unsigned long who)
 265 {
 266         xqindex value;
 267         (void)xlock_acquire(&xq->lock, who);
 268         value = __xq_peek_head(xq);
 269         xlock_release(&xq->lock);
 270         return value;
 271 }
 272
 273 xqindex __xq_peek_tail_idx(struct xq *xq, xqindex nr)
 274 {
 275         xqindex tail = xq->tail + nr;
 276         return tail;
 277 }
 278
 279 xqindex __xq_peek_tail(struct xq *xq)
 280 {
 281         if (!xq_count(xq))
 282                 return Noneidx;
 283         return XPTR(&xq->queue)[__xq_peek_tail_idx(xq, 1) & (xq->size -1)];
 284 }
 285
 286 xqindex xq_peek_tail(struct xq *xq, unsigned long who)
 287 {
 288         xqindex value;
 289         (void)xlock_acquire(&xq->lock, who);
 290         value = __xq_peek_tail(xq);
 291         xlock_release(&xq->lock);
 292         return value;
 293 }
 294
 295 xqindex __xq_append_tail_idx(struct xq *xq, xqindex nr)
 296 {
 297         xqindex tail = xq->tail - nr;
 298         xq->tail = tail;
 299         return tail + 1;
 300 }
 301
 302 /*
 303 xqindex xq_append_tails(struct xq *xq,
 304                         xqindex nr,
 305                         xqindex *tails)
 306 {
 307         xqindex i, mask, tail;
 308         xqindex serial = xlock_acquire(&xq->lock, nr);
 309
 310         if (!(xq_count(xq) + nr <= xq->size)) {
 311                 serial = Noneidx;
 312                 goto out;
 313         }
 314
 315         mask = xq->size -1;
 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];
 319 out:
 320         xlock_release(&xq->lock);
 321         return serial;
 322 }
 323 */
 324
 325 xqindex __xq_append_tail(struct xq *xq, xqindex xqi)
 326 {
 327         if (!(xq_count(xq) + 1 <= xq->size)) {
 328                 return Noneidx;
 329         }
 330         XPTR(&xq->queue)[__xq_append_tail_idx(xq, 1) & (xq->size -1)] = xqi;
 331         return xqi;
 332 }
 333
 334 xqindex xq_append_tail(struct xq *xq, xqindex xqi, unsigned long who)
 335 {
 336         xqindex serial = Noneidx;
 337         xlock_acquire(&xq->lock, who);
 338         serial =__xq_append_tail(xq, xqi);
 339         xlock_release(&xq->lock);
 340         return serial;
 341 }
 342
 343 xqindex __xq_pop_tail_idx(struct xq *xq, xqindex nr)
 344 {
 345         xqindex tail = xq->tail;
 346         xq->tail = tail + nr;
 347         return tail +1;
 348 }
 349
 350 /*
 351 xqindex xq_pop_tails(struct xq *xq, xqindex nr, xqindex *tails)
 352 {
 353         xqindex i, mask, tail;
 354         xqindex serial = xlock_acquire(&xq->lock, nr);
 355
 356         if (xq_count(xq) < nr) {
 357                 serial = Noneidx;
 358                 goto out;
 359         }
 360
 361         mask = xq->size -1;
 362         tail = __xq_pop_tail_idx(xq, nr);
 363         for (i = 0; i < nr; i++)
 364                 tails[i] = XPTR(&xq->queue)[(tail + i) & mask];
 365 out:
 366         xlock_release(&xq->lock);
 367         return serial;
 368 }
 369 */
 370
 371 xqindex __xq_pop_tail(struct xq *xq)
 372 {
 373         if (!xq_count(xq))
 374                 return Noneidx;
 375         return XPTR(&xq->queue)[__xq_pop_tail_idx(xq, 1) & (xq->size -1)];
 376 }
 377
 378 xqindex xq_pop_tail(struct xq *xq, unsigned long who)
 379 {
 380         xqindex value;
 381         (void)xlock_acquire(&xq->lock, who);
 382         value = __xq_pop_tail(xq);
 383         xlock_release(&xq->lock);
 384         return value;
 385 }
 386
 387 int xq_head_to_tail(struct xq *headq, struct xq *tailq, xqindex nr, unsigned long who)
 388 {
 389         xqindex head, tail, hmask, tmask, *hq, *tq, i, ret = -1;
 390
 391         if (headq >= tailq) {
 392                 xlock_acquire(&headq->lock, who);
 393                 xlock_acquire(&tailq->lock, who);
 394         } else {
 395                 xlock_acquire(&tailq->lock, who);
 396                 xlock_acquire(&headq->lock, who);
 397         }
 398
 399         if (xq_count(headq) < nr || xq_count(tailq) + nr > tailq->size)
 400                 goto out;
 401
 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);
 408
 409         for (i = 0; i < nr; i++)
 410                 tq[(tail + i) & tmask] = hq[(head + i) & hmask];
 411
 412         ret = 0;
 413 out:
 414         xlock_release(&headq->lock);
 415         xlock_release(&tailq->lock);
 416         return ret;
 417 }
 418
 419 int __xq_check(struct xq *xq, xqindex idx)
 420 {
 421         xqindex i, val;
 422         for (i = xq->tail + 1; i != xq->head ; i++) {
 423                 val = XPTR(&xq->queue)[i & (xq->size -1)];
 424                 if (val == idx)
 425                         return 1;
 426         }
 427         return 0;
 428 }
 429
 430 int xq_check(struct xq *xq, xqindex idx, unsigned long who)
 431 {
 432         int r;
 433         xlock_acquire(&xq->lock, who);
 434         r = __xq_check(xq, idx);
 435         xlock_release(&xq->lock);
 436         return r;
 437 }
 438
 439 xqindex __xq_resize(struct xq *xq, struct xq *newxq)
 440 {
 441         xqindex i, mask, mask_new, head, tail, val;
 442         xqindex nr = xq_count(xq);
 443
 444         if (nr > newxq->size) {
 445                 return Noneidx;
 446         }
 447
 448         mask = xq->size -1;
 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;
 455         }
 456
 457         return nr;
 458 }
 459
 460 xqindex xq_resize(struct xq *xq, struct xq *newxq, unsigned long who)
 461 {
 462         xqindex r = Noneidx;
 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);
 468         return r;
 469 }
 470
 471 #ifdef __KERNEL__
 472 #include <linux/module.h>
 473 #include <xtypes/xq_exports.h>
 474 #endif
 475