1 /* src/toolbox/set.c - Set implementation.
4 CACAOVM - Verein zu Foerderung der freien virtuellen Machine CACAO
6 This file is part of CACAO.
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.
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.
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
23 This file implements a set of pointers.
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.
28 The representation of the set is an contingous unordered array of the
37 #include "toolbox/set.h"
39 #include "mm/memory.h"
41 #include "vm/global.h"
44 /* struct set ******************************************************************
48 *******************************************************************************/
51 void **elements; /* An array of elements */
52 unsigned capacity; /* Size of elements */
53 unsigned size; /* Current number of elements */
56 /* set_new ********************************************************************
58 Creates an instance of a set on the dump area.
61 capacity: Maximal number of elements of elements the set can hold.
63 *******************************************************************************/
65 set *set_new(unsigned capacity) {
66 set *s = DumpMemory_allocate(sizeof(set));
68 s->elements = DumpMemory_allocate(sizeof(void*) * capacity);
69 MZERO(s->elements, void *, capacity);
70 s->capacity = capacity;
76 /* set_insert ******************************************************************
78 Inserts element e into set s
80 The current implementation takes O(size).
82 *******************************************************************************/
84 void set_insert(set *s, void *element) {
87 for (i = 0; i < s->size; ++i) {
88 if (s->elements[i] == element) {
93 assert(i < s->capacity);
96 s->elements[i] = element;
99 /* set_remove ******************************************************************
101 Removes element e into set s
103 The current implementation takes O(size).
105 *******************************************************************************/
107 void set_remove(set *s, void *element) {
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.
114 if (i == (s->size - 1)) { /* The last one */
115 s->elements[i] = NULL;
117 s->elements[i] = s->elements[s->size - 1];
118 s->elements[s->size - 1] = NULL;
125 /* set_size ********************************************************************
127 Returns the number of elements in the set s.
128 The complexity of the operation is O(1).
130 *******************************************************************************/
132 unsigned set_size(const set *s) {
136 /* set_empty *******************************************************************
138 Returns true, iif the set s is empty.
139 The complexity of the operation is O(1).
141 *******************************************************************************/
143 bool set_empty(const set *s) {
147 /* set_contains ****************************************************************
149 Returns true, iif the set s contains element element.
151 The current implementation takes O(size).
153 *******************************************************************************/
155 bool set_contains(const set *s, void *element) {
157 for (i = 0; i < s->size; ++i) {
158 if (s->elements[i] == element) {
165 /* set_pop *********************************************************************
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).
171 *******************************************************************************/
173 void *set_pop(set *s) {
177 ret = s->elements[s->size - 1];
178 s->elements[s->size - 1] = NULL;
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 * ---------------------------------------------------------------------
192 * indent-tabs-mode: t
196 * vim:noexpandtab:sw=4:ts=4: