Line data Source code
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.hpp"
33 : #include <assert.h> // for assert
34 : #include <stddef.h> // for NULL
35 : #include "mm/dumpmemory.hpp" // for DumpMemory
36 : #include "mm/memory.hpp" // for MZERO
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 0 : set *set_new(unsigned capacity) {
60 0 : set *s = (set*) DumpMemory::allocate(sizeof(set));
61 :
62 0 : s->elements = (void**) DumpMemory::allocate(sizeof(void*) * capacity);
63 0 : MZERO(s->elements, void *, capacity);
64 0 : s->capacity = capacity;
65 0 : s->size = 0;
66 :
67 0 : 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 0 : void set_insert(set *s, void *element) {
79 : unsigned i;
80 :
81 0 : for (i = 0; i < s->size; ++i) {
82 0 : if (s->elements[i] == element) {
83 0 : return;
84 : }
85 : }
86 :
87 0 : assert(i < s->capacity);
88 :
89 0 : s->size += 1;
90 0 : 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 0 : void set_remove(set *s, void *element) {
102 : unsigned i;
103 0 : for (i = 0; i < s->size; ++i) {
104 0 : if (s->elements[i] == element) {
105 : /* Do not creaet a "hole".
106 : * Overwrite this element with the last element.
107 : */
108 0 : if (i == (s->size - 1)) { /* The last one */
109 0 : s->elements[i] = NULL;
110 : } else {
111 0 : s->elements[i] = s->elements[s->size - 1];
112 0 : s->elements[s->size - 1] = NULL;
113 : }
114 0 : s->size -= 1;
115 : }
116 : }
117 0 : }
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 0 : unsigned set_size(const set *s) {
127 0 : 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 0 : bool set_empty(const set *s) {
138 0 : 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 0 : bool set_contains(const set *s, void *element) {
150 : unsigned i;
151 0 : for (i = 0; i < s->size; ++i) {
152 0 : if (s->elements[i] == element) {
153 0 : return true;
154 : }
155 : }
156 0 : 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 0 : void *set_pop(set *s) {
168 0 : void *ret = NULL;
169 :
170 0 : if (s->size > 0) {
171 0 : ret = s->elements[s->size - 1];
172 0 : s->elements[s->size - 1] = NULL;
173 0 : s->size -= 1;
174 : }
175 :
176 0 : 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 : */
|
