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