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 <string.h>
  20 #include <stdlib.h>
  21
  22 #include "ms.h"
  23 #include "util.h"
  24
  25 void
  26 ms_init(ms a, ms_event_fn oninsert, ms_event_fn onremove)
  27 {
  28     a->used = a->cap = a->last = 0;
  29     a->items = NULL;
  30     a->oninsert = oninsert;
  31     a->onremove = onremove;
  32 }
  33
  34 static void
  35 grow(ms a)
  36 {
  37     void **nitems;
  38     size_t ncap = (a->cap << 1) ? : 1;
  39
  40     nitems = malloc(ncap * sizeof(void *));
  41     if (!nitems) return;
  42
  43     memcpy(nitems, a->items, a->used * sizeof(void *));
  44     free(a->items);
  45     a->items = nitems;
  46     a->cap = ncap;
  47 }
  48
  49 int
  50 ms_append(ms a, void *item)
  51 {
  52     if (a->used >= a->cap) grow(a);
  53     if (a->used >= a->cap) return 0;
  54
  55     a->items[a->used++] = item;
  56     if (a->oninsert) a->oninsert(a, item, a->used - 1);
  57     return 1;
  58 }
  59
  60 static int
  61 ms_delete(ms a, size_t i)
  62 {
  63     void *item;
  64
  65     if (i >= a->used) return 0;
  66     item = a->items[i];
  67     a->items[i] = a->items[--a->used];
  68
  69     /* it has already been removed now */
  70     if (a->onremove) a->onremove(a, item, i);
  71     return 1;
  72 }
  73
  74 void
  75 ms_clear(ms a)
  76 {
  77     while (ms_delete(a, 0));
  78     free(a->items);
  79     ms_init(a, a->oninsert, a->onremove);
  80 }
  81
  82 int
  83 ms_remove(ms a, void *item)
  84 {
  85     size_t i;
  86
  87     for (i = 0; i < a->used; i++) {
  88         if (a->items[i] == item) return ms_delete(a, i);
  89     }
  90     return 0;
  91 }
  92
  93 int
  94 ms_contains(ms a, void *item)
  95 {
  96     size_t i;
  97
  98     for (i = 0; i < a->used; i++) {
  99         if (a->items[i] == item) return 1;
 100     }
 101     return 0;
 102 }
 103
 104 void *
 105 ms_take(ms a)
 106 {
 107     void *item;
 108
 109     if (!a->used) return NULL;
 110
 111     a->last = a->last % a->used;
 112     item = a->items[a->last];
 113     ms_delete(a, a->last);
 114     ++a->last;
 115     return item;
 116 }