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