src/toolbox/set.c

   1 /* src/toolbox/set.c - Set implementation.
   2
   3    Copyright (C) 2008
   4    CACAOVM - Verein zu Foerderung der freien virtuellen Machine CACAO
   5
   6    This file is part of CACAO.
   7
   8    This program is free software; you can redistribute it and/or
   9    modify it under the terms of the GNU General Public License as
  10    published by the Free Software Foundation; either version 2, or (at
  11    your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful, but
  14    WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16    General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  21    02110-1301, USA.
  22
  23    This file implements a set of pointers.
  24
  25    The current implementation is naive and should be improved in the future,
  26    so that the O(size) operations take O(log(size)) instead.
  27
  28    The representation of the set is an contingous unordered array of the
  29    elements (pointers).
  30 */
  31
  32 #include "toolbox/set.h"
  33
  34 #include <assert.h>
  35
  36 #include "mm/memory.h"
  37
  38 /* struct set ******************************************************************
  39
  40    Represents the set.
  41
  42 *******************************************************************************/
  43
  44 struct set {
  45         void **elements;   /* An array of elements */
  46         unsigned capacity; /* Size of elements */
  47         unsigned size;     /* Current number of elements */
  48 };
  49
  50 /* set_new ********************************************************************
  51
  52    Creates an instance of a set on the dump area.
  53
  54    IN:
  55        capacity: Maximal number of elements of elements the set can hold.
  56
  57 *******************************************************************************/
  58
  59 set *set_new(unsigned capacity) {
  60         set *s = DNEW(set);
  61
  62         s->elements = DMNEW(void *, capacity);
  63         MZERO(s->elements, void *, capacity);
  64         s->capacity = capacity;
  65         s->size = 0;
  66
  67         return s;
  68 }
  69
  70 /* set_insert ******************************************************************
  71
  72    Inserts element e into set s
  73
  74    The current implementation takes O(size).
  75
  76 *******************************************************************************/
  77
  78 void set_insert(set *s, void *element) {
  79         unsigned i;
  80
  81         for (i = 0; i < s->size; ++i) {
  82                 if (s->elements[i] == element) {
  83                         return;
  84                 }
  85         }
  86
  87         assert(i < s->capacity);
  88
  89         s->size += 1;
  90         s->elements[i] = element;
  91 }
  92
  93 /* set_remove ******************************************************************
  94
  95    Removes element e into set s
  96
  97    The current implementation takes O(size).
  98
  99 *******************************************************************************/
 100
 101 void set_remove(set *s, void *element) {
 102         unsigned i;
 103         for (i = 0; i < s->size; ++i) {
 104                 if (s->elements[i] == element) {
 105                         /* Do not creaet a "hole".
 106                          * Overwrite this element with the last element.
 107                          */
 108                         if (i == (s->size - 1)) { /* The last one */
 109                                 s->elements[i] = NULL;
 110                         } else {
 111                                 s->elements[i] = s->elements[s->size - 1];
 112                                 s->elements[s->size - 1] = NULL;
 113                         }
 114                         s->size -= 1;
 115                 }
 116         }
 117 }
 118
 119 /* set_size ********************************************************************
 120
 121    Returns the number of elements in the set s.
 122    The complexity of the operation is O(1).
 123
 124 *******************************************************************************/
 125
 126 unsigned set_size(const set *s) {
 127         return s->size;
 128 }
 129
 130 /* set_empty *******************************************************************
 131
 132    Returns true, iif the set s is empty.
 133    The complexity of the operation is O(1).
 134
 135 *******************************************************************************/
 136
 137 bool set_empty(const set *s) {
 138         return s->size == 0;
 139 }
 140
 141 /* set_contains ****************************************************************
 142
 143    Returns true, iif the set s contains element element.
 144
 145    The current implementation takes O(size).
 146
 147 *******************************************************************************/
 148
 149 bool set_contains(const set *s, void *element) {
 150         unsigned i;
 151         for (i = 0; i < s->size; ++i) {
 152                 if (s->elements[i] == element) {
 153                         return true;
 154                 }
 155         }
 156         return false;
 157 }
 158
 159 /* set_pop *********************************************************************
 160
 161    Pics and removes some element from the set s and returns it.
 162    Returns NULL if the set s is empty.
 163    The complexity of the operation is O(1).
 164
 165 *******************************************************************************/
 166
 167 void *set_pop(set *s) {
 168         void *ret = NULL;
 169
 170         if (s->size > 0) {
 171                 ret = s->elements[s->size - 1];
 172                 s->elements[s->size - 1] = NULL;
 173                 s->size -= 1;
 174         }
 175
 176         return ret;
 177 }
 178
 179 /*
 180  * These are local overrides for various environment variables in Emacs.
 181  * Please do not remove this and leave it at the end of the file, where
 182  * Emacs will automagically detect them.
 183  * ---------------------------------------------------------------------
 184  * Local variables:
 185  * mode: c
 186  * indent-tabs-mode: t
 187  * c-basic-offset: 4
 188  * tab-width: 4
 189  * End:
 190  * vim:noexpandtab:sw=4:ts=4:
 191  */