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
  33 #include "config.h"
  34
  35 #include <assert.h>
  36
  37 #include "toolbox/set.h"
  38
  39 #include "mm/memory.hpp"
  40
  41 #include "vm/global.h"
  42
  43
  44 /* struct set ******************************************************************
  45
  46    Represents the set.
  47
  48 *******************************************************************************/
  49
  50 struct set {
  51         void **elements;   /* An array of elements */
  52         unsigned capacity; /* Size of elements */
  53         unsigned size;     /* Current number of elements */
  54 };
  55
  56 /* set_new ********************************************************************
  57
  58    Creates an instance of a set on the dump area.
  59
  60    IN:
  61        capacity: Maximal number of elements of elements the set can hold.
  62
  63 *******************************************************************************/
  64
  65 set *set_new(unsigned capacity) {
  66         set *s = DumpMemory_allocate(sizeof(set));
  67
  68         s->elements = DumpMemory_allocate(sizeof(void*) * capacity);
  69         MZERO(s->elements, void *, capacity);
  70         s->capacity = capacity;
  71         s->size = 0;
  72
  73         return s;
  74 }
  75
  76 /* set_insert ******************************************************************
  77
  78    Inserts element e into set s
  79
  80    The current implementation takes O(size).
  81
  82 *******************************************************************************/
  83
  84 void set_insert(set *s, void *element) {
  85         unsigned i;
  86
  87         for (i = 0; i < s->size; ++i) {
  88                 if (s->elements[i] == element) {
  89                         return;
  90                 }
  91         }
  92
  93         assert(i < s->capacity);
  94
  95         s->size += 1;
  96         s->elements[i] = element;
  97 }
  98
  99 /* set_remove ******************************************************************
 100
 101    Removes element e into set s
 102
 103    The current implementation takes O(size).
 104
 105 *******************************************************************************/
 106
 107 void set_remove(set *s, void *element) {
 108         unsigned i;
 109         for (i = 0; i < s->size; ++i) {
 110                 if (s->elements[i] == element) {
 111                         /* Do not creaet a "hole".
 112                          * Overwrite this element with the last element.
 113                          */
 114                         if (i == (s->size - 1)) { /* The last one */
 115                                 s->elements[i] = NULL;
 116                         } else {
 117                                 s->elements[i] = s->elements[s->size - 1];
 118                                 s->elements[s->size - 1] = NULL;
 119                         }
 120                         s->size -= 1;
 121                 }
 122         }
 123 }
 124
 125 /* set_size ********************************************************************
 126
 127    Returns the number of elements in the set s.
 128    The complexity of the operation is O(1).
 129
 130 *******************************************************************************/
 131
 132 unsigned set_size(const set *s) {
 133         return s->size;
 134 }
 135
 136 /* set_empty *******************************************************************
 137
 138    Returns true, iif the set s is empty.
 139    The complexity of the operation is O(1).
 140
 141 *******************************************************************************/
 142
 143 bool set_empty(const set *s) {
 144         return s->size == 0;
 145 }
 146
 147 /* set_contains ****************************************************************
 148
 149    Returns true, iif the set s contains element element.
 150
 151    The current implementation takes O(size).
 152
 153 *******************************************************************************/
 154
 155 bool set_contains(const set *s, void *element) {
 156         unsigned i;
 157         for (i = 0; i < s->size; ++i) {
 158                 if (s->elements[i] == element) {
 159                         return true;
 160                 }
 161         }
 162         return false;
 163 }
 164
 165 /* set_pop *********************************************************************
 166
 167    Pics and removes some element from the set s and returns it.
 168    Returns NULL if the set s is empty.
 169    The complexity of the operation is O(1).
 170
 171 *******************************************************************************/
 172
 173 void *set_pop(set *s) {
 174         void *ret = NULL;
 175
 176         if (s->size > 0) {
 177                 ret = s->elements[s->size - 1];
 178                 s->elements[s->size - 1] = NULL;
 179                 s->size -= 1;
 180         }
 181
 182         return ret;
 183 }
 184
 185 /*
 186  * These are local overrides for various environment variables in Emacs.
 187  * Please do not remove this and leave it at the end of the file, where
 188  * Emacs will automagically detect them.
 189  * ---------------------------------------------------------------------
 190  * Local variables:
 191  * mode: c
 192  * indent-tabs-mode: t
 193  * c-basic-offset: 4
 194  * tab-width: 4
 195  * End:
 196  * vim:noexpandtab:sw=4:ts=4:
 197  */