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

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