ms.c

   1 #include "dat.h"
   2 #include <stdint.h>
   3 #include <string.h>
   4 #include <stdlib.h>
   5
   6 void
   7 ms_init(Ms *a, ms_event_fn oninsert, ms_event_fn onremove)
   8 {
   9     a->len = a->cap = a->last = 0;
  10     a->items = NULL;
  11     a->oninsert = oninsert;
  12     a->onremove = onremove;
  13 }
  14
  15 static int
  16 grow(Ms *a)
  17 {
  18     void **nitems;
  19     size_t ncap = a->cap << 1;
  20     if (!ncap)
  21         ncap = 1;
  22
  23     nitems = malloc(ncap * sizeof(void *));
  24     if (!nitems)
  25         return 0;
  26
  27     memcpy(nitems, a->items, a->len * sizeof(void *));
  28     free(a->items);
  29     a->items = nitems;
  30     a->cap = ncap;
  31     return 1;
  32 }
  33
  34 int
  35 ms_append(Ms *a, void *item)
  36 {
  37     if (a->len >= a->cap && !grow(a))
  38         return 0;
  39
  40     a->items[a->len++] = item;
  41     if (a->oninsert)
  42         a->oninsert(a, item, a->len - 1);
  43     return 1;
  44 }
  45
  46 static int
  47 ms_delete(Ms *a, size_t i)
  48 {
  49     void *item;
  50
  51     if (i >= a->len)
  52         return 0;
  53     item = a->items[i];
  54     a->items[i] = a->items[--a->len];
  55
  56     /* it has already been removed now */
  57     if (a->onremove)
  58         a->onremove(a, item, i);
  59     return 1;
  60 }
  61
  62 void
  63 ms_clear(Ms *a)
  64 {
  65     while (ms_delete(a, 0));
  66     free(a->items);
  67     ms_init(a, a->oninsert, a->onremove);
  68 }
  69
  70 int
  71 ms_remove(Ms *a, void *item)
  72 {
  73     size_t i;
  74
  75     for (i = 0; i < a->len; i++) {
  76         if (a->items[i] == item)
  77             return ms_delete(a, i);
  78     }
  79     return 0;
  80 }
  81
  82 int
  83 ms_contains(Ms *a, void *item)
  84 {
  85     size_t i;
  86
  87     for (i = 0; i < a->len; i++) {
  88         if (a->items[i] == item)
  89             return 1;
  90     }
  91     return 0;
  92 }
  93
  94 void *
  95 ms_take(Ms *a)
  96 {
  97     void *item;
  98
  99     if (!a->len)
 100         return NULL;
 101
 102     // The result of last behaviour is that ms_take returns the oldest elements
 103     // first, exception is a row of multiple take calls without inserts on ms
 104     // of even number of elements. See the test.
 105     a->last = a->last % a->len;
 106     item = a->items[a->last];
 107     ms_delete(a, a->last);
 108     ++a->last;
 109     return item;
 110 }