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

   1 #include <xq/xq.h>
   2
   3 #ifdef RELATIVE_POINTERS
   4 #define PTR(p, f) ((typeof((p)->f))((unsigned long)(p) + (unsigned long)(p)->f))
   5 #define PTRSET(p, f, v) ((p)->f = (void *)((unsigned long)(v) - (unsigned long)(p)))
   6 #else
   7 #define PTR(p, f) (p)->f
   8 #define PTRSET(p, f, v) ((p)->f = (v))
   9 #endif
  10
  11 static inline int __snap(xqindex size)
  12 {
  13         if (!size)
  14                 return 0;
  15         return 1 << ((sizeof(size) * 8) - __builtin_clz(size) - 1);
  16 }
  17
  18 void xq_free(struct xq *xq) {
  19         xq_mfree((void *)PTR(xq, queue));
  20         memset(xq, 0, sizeof(struct xq));
  21 }
  22
  23 void xq_init_empty(struct xq *xq, xqindex size, void *mem)
  24 {
  25         xq->head = 1;
  26         xq->tail = 0;
  27         PTRSET(xq, queue, mem);
  28         xq->size = __snap(size);
  29         xq_release(&xq->lock);
  30 }
  31
  32 void xq_init_map(struct xq *xq,
  33                  xqindex size,
  34                  xqindex count,
  35                  xqindex (*mapfn)(xqindex),
  36                  void *mem)
  37 {
  38         xqindex t, *qmem = mem;
  39         xq->head = count + 1;
  40         xq->tail = 0;
  41         PTRSET(xq, queue, qmem);
  42         xq->size = __snap(size);
  43         for (t = 0; t < count; t++)
  44                 qmem[t] = mapfn(t);
  45         xq_release(&xq->lock);
  46 }
  47
  48 void xq_init_seq(struct xq *xq, xqindex size, xqindex count, void *mem)
  49 {
  50         xqindex t, *qmem = mem;
  51         xq->head = count + 1;
  52         xq->tail = 0;
  53         PTRSET(xq, queue, qmem);
  54         xq->size = __snap(size);
  55         for (t = 0; t < count; t++)
  56                 qmem[t] = t;
  57         xq_release(&xq->lock);
  58 }
  59
  60 xqindex *xq_alloc_empty(struct xq *xq, xqindex size)
  61 {
  62         xqindex *mem = xq_malloc(size * sizeof(xqindex));
  63         if (!mem)
  64                 return mem;
  65         xq_init_empty(xq, size, mem);
  66         return mem;
  67 }
  68
  69 xqindex *xq_alloc_map(struct xq *xq,
  70                         xqindex size,
  71                         xqindex count,
  72                         xqindex (*mapfn)(xqindex)       )
  73 {
  74         xqindex *mem = xq_malloc(size * sizeof(xqindex));
  75         if (!mem)
  76                 return mem;
  77         xq_init_map(xq, size, count, mapfn, mem);
  78         return mem;
  79 }
  80
  81 xqindex *xq_alloc_seq(struct xq *xq, xqindex size, xqindex count)
  82 {
  83         xqindex *mem = xq_malloc(size * sizeof(xqindex));
  84         if (!mem)
  85                 return mem;
  86         xq_init_seq(xq, size, count, mem);
  87         return mem;
  88 }
  89
  90 xqindex xq_size(struct xq *xq)
  91 {
  92         return xq->size;
  93 }
  94
  95 xqindex xq_count(struct xq *xq)
  96 {
  97         return xq->head - xq->tail - 1;
  98 }
  99
 100 xqindex xq_element(struct xq *xq, xqindex index)
 101 {
 102         return PTR(xq, queue)[index & (xq->size - 1)];
 103 }
 104
 105 void xq_print(struct xq *xq)
 106 {
 107         xqindex i;
 108
 109         LOGMSG("xq head: %lu, tail: %lu, size: %lu\n",
 110                 (unsigned long)xq->head,
 111                 (unsigned long)xq->tail,
 112                 (unsigned long)xq->size);
 113         i = xq->tail + 1;
 114
 115         for (;;) {
 116                 if (i == xq->head)
 117                         break;
 118                 LOGMSG( "%lu %lu\n",
 119                         (unsigned long)i,
 120                         (unsigned long)xq_element(xq, i) );
 121                 i += 1;
 122         }
 123 }
 124
 125 xqindex __xq_append_head(struct xq *xq, xqindex nr)
 126 {
 127         xqindex head = xq->head;
 128         xq->head = head + nr;
 129         return head;
 130 }
 131
 132 xqindex xq_append_heads(struct xq *xq,
 133                         xqindex nr,
 134                         xqindex *heads)
 135 {
 136         xqindex i, mask, head;
 137         xqindex serial = xq_acquire(&xq->lock, nr);
 138
 139         if (!(xq_count(xq) + nr <= xq->size)) {
 140                 serial = None;
 141                 goto out;
 142         }
 143
 144         mask = xq->size -1;
 145         head = __xq_append_head(xq, nr);
 146         for (i = 0; i < nr; i++)
 147                 PTR(xq, queue)[(head + i) & mask] = heads[i];
 148 out:
 149         xq_release(&xq->lock);
 150         return serial;
 151 }
 152
 153 xqindex xq_append_head(struct xq *xq, xqindex xqi)
 154 {
 155         xqindex serial = xq_acquire(&xq->lock, 1);
 156
 157         if (xq_count(xq) >= xq->size) {
 158                 serial = None;
 159                 goto out;
 160         }
 161         PTR(xq, queue)[__xq_append_head(xq, 1) & (xq->size -1)] = xqi;
 162 out:
 163         xq_release(&xq->lock);
 164         return serial;
 165 }
 166
 167 xqindex __xq_pop_head(struct xq *xq, xqindex nr)
 168 {
 169         xqindex head = xq->head;
 170         xq->head = head - nr;
 171         return head - nr;
 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 = xq_acquire(&xq->lock, nr);
 180
 181         if (xq_count(xq) < nr) {
 182                 serial = None;
 183                 goto out;
 184         }
 185
 186         mask = xq->size -1;
 187         head = __xq_pop_head(xq, nr);
 188         for (i = 0; i < nr; i++)
 189                 heads[i] = PTR(xq, queue)[(head - i) & mask];
 190 out:
 191         xq_release(&xq->lock);
 192         return serial;
 193 }
 194
 195 xqindex xq_pop_head(struct xq *xq)
 196 {
 197         xqindex value = None;
 198         (void)xq_acquire(&xq->lock, 1);
 199         if (!xq_count(xq))
 200                 goto out;
 201         value = PTR(xq, queue)[__xq_pop_head(xq, 1) & (xq->size -1)];
 202 out:
 203         xq_release(&xq->lock);
 204         return value;
 205 }
 206
 207 xqindex __xq_append_tail(struct xq *xq, xqindex nr)
 208 {
 209         xqindex tail = xq->tail;
 210         xq->tail = tail - nr;
 211         return tail;
 212 }
 213
 214 xqindex xq_append_tails(struct xq *xq,
 215                         xqindex nr,
 216                         xqindex *tails)
 217 {
 218         xqindex i, mask, tail;
 219         xqindex serial = xq_acquire(&xq->lock, nr);
 220
 221         if (!(xq_count(xq) + nr <= xq->size)) {
 222                 serial = None;
 223                 goto out;
 224         }
 225
 226         mask = xq->size -1;
 227         tail = __xq_append_tail(xq, nr);
 228         for (i = 0; i < nr; i++)
 229                 PTR(xq, queue)[(tail - i) & mask] = tails[i];
 230 out:
 231         xq_release(&xq->lock);
 232         return serial;
 233 }
 234
 235 xqindex xq_append_tail(struct xq *xq, xqindex xqi)
 236 {
 237         xqindex serial = xq_acquire(&xq->lock, 1);
 238
 239         if (!(xq_count(xq) + 1 <= xq->size)) {
 240                 serial = None;
 241                 goto out;
 242         }
 243         PTR(xq, queue)[__xq_append_tail(xq, 1) & (xq->size -1)] = xqi;
 244 out:
 245         xq_release(&xq->lock);
 246         return serial;
 247 }
 248
 249 xqindex __xq_pop_tail(struct xq *xq, xqindex nr)
 250 {
 251         xqindex tail = xq->tail;
 252         xq->tail = tail + nr;
 253         return tail + 1;
 254 }
 255
 256 xqindex xq_pop_tails(struct xq *xq, xqindex nr, xqindex *tails)
 257 {
 258         xqindex i, mask, tail;
 259         xqindex serial = xq_acquire(&xq->lock, nr);
 260
 261         if (xq_count(xq) < nr) {
 262                 serial = None;
 263                 goto out;
 264         }
 265
 266         mask = xq->size -1;
 267         tail = __xq_pop_tail(xq, nr);
 268         for (i = 0; i < nr; i++)
 269                 tails[i] = PTR(xq, queue)[(tail + i) & mask];
 270 out:
 271         xq_release(&xq->lock);
 272         return serial;
 273 }
 274
 275 xqindex xq_pop_tail(struct xq *xq)
 276 {
 277         xqindex value = None;
 278         (void)xq_acquire(&xq->lock, 1);
 279         if (!xq_count(xq))
 280                 goto out;
 281         value = PTR(xq, queue)[__xq_pop_tail(xq, 1) & (xq->size -1)];
 282 out:
 283         xq_release(&xq->lock);
 284         return value;
 285 }
 286
 287 int xq_head_to_tail(struct xq *headq, struct xq *tailq, xqindex nr)
 288 {
 289         xqindex head, tail, hmask, tmask, *hq, *tq, i, ret = -1;
 290
 291         if (headq >= tailq) {
 292                 xq_acquire(&headq->lock, nr);
 293                 xq_acquire(&tailq->lock, nr);
 294         } else {
 295                 xq_acquire(&tailq->lock, nr);
 296                 xq_acquire(&headq->lock, nr);
 297         }
 298
 299         if (xq_count(headq) < nr || xq_count(tailq) + nr > tailq->size)
 300                 goto out;
 301
 302         hmask = headq->size -1;
 303         tmask = tailq->size -1;
 304         head = __xq_pop_head(headq, nr);
 305         tail = __xq_append_tail(tailq, nr);
 306         hq = PTR(headq, queue);
 307         tq = PTR(tailq, queue);
 308
 309         for (i = 0; i < nr; i++)
 310                 tq[(tail - i) & tmask] = hq[(head - i) & hmask];
 311
 312         ret = 0;
 313 out:
 314         xq_release(&headq->lock);
 315         xq_release(&tailq->lock);
 316         return ret;
 317 }
 318
 319 #undef PTR
 320 #undef PTRDEF
 321
 322 #ifdef __KERNEL__
 323 #include <linux/module.h>
 324 #include <xq/xq_exports.h>
 325 #endif
 326