ms.c

   1 /* ms.c - resizable multiset implementation */
   2
   3 /* Copyright (C) 2008 Keith Rarick and Philotic Inc.
   4
   5  * This program is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation, either version 3 of the License, or
   8  * (at your option) any later version.
   9
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17  */
  18
  19 #include <stdint.h>
  20 #include <string.h>
  21 #include <stdlib.h>
  22 #include "dat.h"
  23
  24 void
  25 ms_init(ms a, ms_event_fn oninsert, ms_event_fn onremove)
  26 {
  27     a->used = a->cap = a->last = 0;
  28     a->items = NULL;
  29     a->oninsert = oninsert;
  30     a->onremove = onremove;
  31 }
  32
  33 static void
  34 grow(ms a)
  35 {
  36     void **nitems;
  37     size_t ncap = (a->cap << 1) ? : 1;
  38
  39     nitems = malloc(ncap * sizeof(void *));
  40     if (!nitems) return;
  41
  42     memcpy(nitems, a->items, a->used * sizeof(void *));
  43     free(a->items);
  44     a->items = nitems;
  45     a->cap = ncap;
  46 }
  47
  48 int
  49 ms_append(ms a, void *item)
  50 {
  51     if (a->used >= a->cap) grow(a);
  52     if (a->used >= a->cap) return 0;
  53
  54     a->items[a->used++] = item;
  55     if (a->oninsert) a->oninsert(a, item, a->used - 1);
  56     return 1;
  57 }
  58
  59 static int
  60 ms_delete(ms a, size_t i)
  61 {
  62     void *item;
  63
  64     if (i >= a->used) return 0;
  65     item = a->items[i];
  66     a->items[i] = a->items[--a->used];
  67
  68     /* it has already been removed now */
  69     if (a->onremove) a->onremove(a, item, i);
  70     return 1;
  71 }
  72
  73 void
  74 ms_clear(ms a)
  75 {
  76     while (ms_delete(a, 0));
  77     free(a->items);
  78     ms_init(a, a->oninsert, a->onremove);
  79 }
  80
  81 int
  82 ms_remove(ms a, void *item)
  83 {
  84     size_t i;
  85
  86     for (i = 0; i < a->used; i++) {
  87         if (a->items[i] == item) return ms_delete(a, i);
  88     }
  89     return 0;
  90 }
  91
  92 int
  93 ms_contains(ms a, void *item)
  94 {
  95     size_t i;
  96
  97     for (i = 0; i < a->used; i++) {
  98         if (a->items[i] == item) return 1;
  99     }
 100     return 0;
 101 }
 102
 103 void *
 104 ms_take(ms a)
 105 {
 106     void *item;
 107
 108     if (!a->used) return NULL;
 109
 110     a->last = a->last % a->used;
 111     item = a->items[a->last];
 112     ms_delete(a, a->last);
 113     ++a->last;
 114     return item;
 115 }