Debian Codegraph @

src/fcml_coll.c

raw
1 /*
2 * FCML - Free Code Manipulation Library.
3 * Copyright (C) 2010-2020 Slawomir Wojtasiak
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
9 *
10 * This library 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 GNU
13 * Lesser General Public License for more details.
14 *
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
18 */
19
20 #include <string.h>
21 #include "fcml_env_int.h"
22 #include "fcml_coll.h"
23 #include "fcml_ceh.h"
24
25 /***********************/
26 /* Bidirectional list. */
27 /***********************/
28
29 fcml_st_coll_list* fcml_fn_coll_list_alloc() {
30 FCML_ENV_ALLOC_CLEAR(list, fcml_st_coll_list);
31 return list;
32 }
33
34 fcml_st_coll_list_element* fcml_fn_coll_list_add_front(fcml_st_coll_list *list,
35 const fcml_ptr item) {
36 FCML_ENV_ALLOC_CLEAR(element, fcml_st_coll_list_element);
37 if (element) {
38 element->next = list->head;
39 if (list->head) {
40 list->head->prev = element;
41 }
42 element->prev = NULL;
43 element->item = item;
44 list->head = element;
45 if (!list->tail) {
46 list->tail = element;
47 }
48 list->size++;
49 }
50 return element;
51 }
52
53 fcml_st_coll_list_element* fcml_fn_coll_list_add_back(fcml_st_coll_list *list,
54 const fcml_ptr item) {
55 FCML_ENV_ALLOC_CLEAR(element, fcml_st_coll_list_element);
56 if (element) {
57 element->next = NULL;
58 element->prev = list->tail;
59 element->item = item;
60 if (list->tail) {
61 list->tail->next = element;
62 }
63 list->tail = element;
64 if (!list->head) {
65 list->head = element;
66 }
67 list->size++;
68 }
69 return element;
70 }
71
72 fcml_st_coll_list_element* fcml_fn_coll_list_insert(fcml_st_coll_list *list,
73 fcml_st_coll_list_element *prev_element, const fcml_ptr item) {
74 fcml_st_coll_list_element *element;
75 if (prev_element) {
76 element = FCML_ENV_ALLOC_ST(fcml_st_coll_list_element);
77 if (element) {
78 element->item = item;
79 element->prev = prev_element;
80 element->next = prev_element->next;
81 prev_element->next = element;
82 list->size++;
83 }
84 } else {
85 element = fcml_fn_coll_list_add_front(list, item);
86 }
87 return element;
88 }
89
90 void fcml_fn_coll_list_free(fcml_st_coll_list *list,
91 fcml_fp_coll_list_action item_handler,
92 const fcml_ptr item_handler_args) {
93 fcml_st_coll_list_element *current = list->head;
94 while (current) {
95 if (item_handler) {
96 (item_handler)(current->item, item_handler_args);
97 }
98 fcml_st_coll_list_element *tmp = current;
99 current = current->next;
100 fcml_fn_env_memory_free(tmp);
101 }
102 fcml_fn_env_memory_free(list);
103 }
104
105 /*************/
106 /* Hash map. */
107 /*************/
108
109 /* Internal data types dedicated for given implementation of the map.*/
110
111 static fcml_uint32_t key_hash_string(fcml_ptr key);
112 static fcml_bool key_equals_string(fcml_ptr key1, fcml_ptr key2);
113 static fcml_uint32_t key_hash_uint32(fcml_ptr key);
114 static fcml_bool key_equals_uint32(fcml_ptr key1, fcml_ptr key2);
115
116 static fcml_coll_map map_alloc_factor(
117 const fcml_st_coll_map_descriptor *descriptor, fcml_uint32_t capacity,
118 float load_factor, fcml_int *error);
119
120 struct fcml_ist_coll_map_entry {
121 struct fcml_ist_coll_map_entry *next;
122 fcml_uint32_t hash;
123 fcml_ptr key;
124 fcml_ptr value;
125 };
126
127 struct fcml_ist_coll_map {
128 fcml_st_coll_map_descriptor descriptor;
129 float load_factor;
130 fcml_uint32_t boundary;
131 fcml_uint32_t capacity;
132 fcml_uint32_t size;
133 fcml_uint32_t hash_mask;
134 struct fcml_ist_coll_map_entry **map_entries;
135 };
136
137 fcml_st_coll_map_descriptor fcml_coll_map_descriptor_string = {
138 key_hash_string, key_equals_string,
139 NULL, NULL };
140
141 fcml_st_coll_map_descriptor fcml_coll_map_descriptor_uint32 = {
142 key_hash_uint32, key_equals_uint32,
143 NULL, NULL };
144
145 static fcml_uint32_t get_hash(fcml_st_coll_map_descriptor *descriptor,
146 fcml_ptr key) {
147 fcml_uint32_t hash = descriptor->hash_function(key);
148 hash ^= (hash >> 20) ^ (hash >> 12);
149 hash ^= (hash >> 7) ^ (hash >> 4);
150 return hash;
151 }
152
153 fcml_coll_map fcml_fn_coll_map_alloc(
154 const fcml_st_coll_map_descriptor *descriptor, fcml_uint32_t capacity,
155 fcml_int *error) {
156 return map_alloc_factor(descriptor, capacity,
157 FCML_COLL_MAP_DEFAULT_FACTOR, error);
158 }
159
160 static fcml_coll_map map_alloc_factor(
161 const fcml_st_coll_map_descriptor *descriptor, fcml_uint32_t capacity,
162 float load_factor, fcml_int *error) {
163
164 *error = FCML_COLL_ERROR_NO_ERROR;
165
166 if (capacity > (1 << 31)) {
167 *error = FCML_COLL_ERROR_BAD_ARGS;
168 return NULL;
169 }
170
171 fcml_uint32_t real_capacity = 2;
172 while (real_capacity < capacity) {
173 real_capacity <<= 1;
174 }
175
176 FCML_ENV_ALLOC_CLEAR(map, struct fcml_ist_coll_map);
177 if (map == NULL) {
178 *error = FCML_COLL_ERROR_OUT_OF_MEMORY;
179 return NULL;
180 }
181
182 map->descriptor = *descriptor;
183
184 /* Calculate and cache boundary to gain some performance
185 * from further calculations.
186 */
187 map->load_factor = load_factor;
188 map->boundary = (fcml_uint32_t) (real_capacity * load_factor);
189 map->capacity = real_capacity;
190 map->hash_mask = real_capacity - 1;
191 map->size = 0;
192
193 /* Allocate space for entries.*/
194 map->map_entries =
195 (struct fcml_ist_coll_map_entry**) fcml_fn_env_memory_alloc_clear(
196 sizeof(struct fcml_ist_coll_map_entry*) * real_capacity);
197
198 if (!map->map_entries) {
199 fcml_fn_env_memory_free(map);
200 *error = FCML_COLL_ERROR_OUT_OF_MEMORY;
201 return NULL;
202 }
203
204 return map;
205 }
206
207 fcml_uint32_t fcml_fn_coll_map_size(const fcml_coll_map map_int) {
208 struct fcml_ist_coll_map *map = (struct fcml_ist_coll_map*) map_int;
209 return map->size;
210 }
211
212 static fcml_bool map_expand(struct fcml_ist_coll_map *map,
213 fcml_ceh_error *error) {
214
215 *error = FCML_COLL_ERROR_NO_ERROR;
216
217 if (map->capacity > FCML_INT32_MAX) {
218 /* Map reached its maximum capacity.*/
219 *error = FCML_COLL_ERROR_MAP_FULL;
220 return FCML_FALSE;
221 }
222
223 fcml_uint32_t new_capacity = map->capacity << 1;
224
225 /* Allocate new map entries.*/
226 struct fcml_ist_coll_map_entry **new_map_entries =
227 (struct fcml_ist_coll_map_entry**) fcml_fn_env_memory_alloc(
228 new_capacity * sizeof(struct fcml_ist_coll_map_entry*));
229
230 if (!new_map_entries) {
231 *error = FCML_COLL_ERROR_OUT_OF_MEMORY;
232 return FCML_FALSE;
233 }
234
235 fcml_fn_env_memory_clear(new_map_entries,
236 new_capacity * sizeof(struct fcml_ist_coll_map_entry*));
237
238 fcml_uint32_t new_hash_mask = (new_capacity - 1);
239 fcml_uint32_t i;
240 for (i = 0; i < map->capacity; i++) {
241 struct fcml_ist_coll_map_entry *entry = map->map_entries[i];
242 if (entry) {
243 while (entry) {
244 struct fcml_ist_coll_map_entry *next_entry = entry->next;
245 fcml_uint32_t new_index = new_hash_mask & entry->hash;
246 entry->next = new_map_entries[new_index];
247 new_map_entries[new_index] = entry;
248 entry = next_entry;
249 }
250 }
251 }
252
253 fcml_fn_env_memory_free(map->map_entries);
254
255 map->map_entries = new_map_entries;
256 map->capacity = new_capacity;
257 map->boundary = (fcml_uint32_t) (new_capacity * map->load_factor);
258 map->hash_mask = new_hash_mask;
259
260 return FCML_TRUE;
261 }
262
263 void fcml_fn_coll_map_put(fcml_coll_map map_int, const fcml_ptr key,
264 const fcml_ptr value, fcml_int *error) {
265
266 *error = FCML_COLL_ERROR_NO_ERROR;
267
268 struct fcml_ist_coll_map *map = (struct fcml_ist_coll_map*) map_int;
269
270 fcml_st_coll_map_descriptor *descriptor = &(map->descriptor);
271 fcml_uint32_t hash = get_hash(descriptor, key);
272 fcml_uint32_t index = map->hash_mask & hash;
273
274 struct fcml_ist_coll_map_entry *entry = map->map_entries[index];
275 struct fcml_ist_coll_map_entry *current_entry = entry;
276
277 /* Checking for entry with the same key. */
278 while (current_entry) {
279 if (current_entry->hash == hash
280 && (key == current_entry->key
281 || descriptor->equals_function(key, current_entry->key))) {
282 /* We found element with same key, so replace key and value. */
283 if (descriptor->entry_free_function) {
284 descriptor->entry_free_function(current_entry->key,
285 current_entry->value, map->descriptor.entry_free_args);
286 }
287 current_entry->key = key;
288 current_entry->value = value;
289 return;
290 }
291 current_entry = current_entry->next;
292 }
293
294 /* Check if map should be already extended. */
295 if (entry && map->size > map->boundary) {
296 /* Currently we ignore errors, because it really doesn't matter if
297 * there is no space in the map or on the heap.
298 */
299 fcml_ceh_error error;
300 if (map_expand(map, &error)) {
301 index = map->hash_mask & hash;
302 }
303 }
304
305 struct fcml_ist_coll_map_entry *newEntry =
306 (struct fcml_ist_coll_map_entry*) fcml_fn_env_memory_alloc(
307 sizeof(struct fcml_ist_coll_map_entry));
308
309 if (!newEntry) {
310 *error = FCML_COLL_ERROR_OUT_OF_MEMORY;
311 return;
312 }
313
314 newEntry->key = key;
315 newEntry->value = value;
316 newEntry->hash = hash;
317 newEntry->next = map->map_entries[index];
318 map->map_entries[index] = newEntry;
319 map->size++;
320
321 }
322
323 void fcml_fn_coll_map_remove(fcml_coll_map map_int, const fcml_ptr key) {
324
325 struct fcml_ist_coll_map *map = (struct fcml_ist_coll_map*) map_int;
326 fcml_uint32_t hash = get_hash(&(map->descriptor), key);
327 int index = map->hash_mask & hash;
328 struct fcml_ist_coll_map_entry *entry = map->map_entries[index];
329 struct fcml_ist_coll_map_entry *previous_entry = NULL;
330
331 while (entry) {
332 if (entry->hash == hash && (key == entry->key
333 || map->descriptor.equals_function(key, entry->key))) {
334 /* We found entry, so remove it. */
335 if (map->descriptor.entry_free_function) {
336 map->descriptor.entry_free_function(entry->key, entry->value,
337 map->descriptor.entry_free_args);
338 }
339 if (previous_entry) {
340 previous_entry->next = entry->next;
341 } else {
342 map->map_entries[index] = NULL;
343 }
344 fcml_fn_env_memory_free(entry);
345 map->size--;
346 return;
347 }
348 previous_entry = entry;
349 entry = entry->next;
350 }
351 return;
352 }
353
354 void fcml_fn_coll_map_remove_if(fcml_coll_map map_int,
355 fcml_fnp_coll_map_entry_handler_if item_handler,
356 fcml_ptr item_handler_args) {
357
358 struct fcml_ist_coll_map *map = (struct fcml_ist_coll_map*) map_int;
359 fcml_uint32_t i;
360
361 for (i = 0; i < map->capacity; i++) {
362 struct fcml_ist_coll_map_entry **entry = &( map->map_entries[i] );
363 struct fcml_ist_coll_map_entry **next_entry;
364 while (*entry) {
365 next_entry = &((*entry )->next);
366 if (item_handler((*entry )->key, (*entry)->value,
367 item_handler_args)) {
368 if (map->descriptor.entry_free_function) {
369 map->descriptor.entry_free_function((*entry)->key,
370 (*entry )->value, map->descriptor.entry_free_args);
371 }
372 struct fcml_ist_coll_map_entry *current = *entry;
373 *entry = *next_entry;
374 fcml_fn_env_memory_free( current );
375 map->size--;
376 } else {
377 entry = next_entry;
378 }
379 }
380 }
381 }
382
383 void fcml_fn_coll_map_clear(fcml_coll_map map_int) {
384 struct fcml_ist_coll_map *map = (struct fcml_ist_coll_map*) map_int;
385 fcml_uint32_t i;
386 for (i = 0; i < map->capacity; i++) {
387 struct fcml_ist_coll_map_entry *entry = map->map_entries[i];
388 struct fcml_ist_coll_map_entry *next_entry;
389 while (entry) {
390 next_entry = entry->next;
391 if (map->descriptor.entry_free_function) {
392 map->descriptor.entry_free_function(entry->key, entry->value,
393 map->descriptor.entry_free_args);
394 }
395 fcml_fn_env_memory_free(entry);
396 entry = next_entry;
397 }
398 map->map_entries[i] = NULL;
399 }
400 map->size = 0;
401 }
402
403 fcml_ptr fcml_fn_coll_map_get(fcml_coll_map map_int, const fcml_ptr key) {
404 struct fcml_ist_coll_map *map = (struct fcml_ist_coll_map*) map_int;
405 fcml_uint32_t hash = get_hash(&(map->descriptor), key);
406 fcml_uint32_t index = map->hash_mask & hash;
407 struct fcml_ist_coll_map_entry *entry = map->map_entries[index];
408 /* Checking for entry with the same key.*/
409 while (entry) {
410 if (entry->hash == hash
411 && (key == entry->key
412 || map->descriptor.equals_function(key, entry->key))) {
413 return entry->value;
414 }
415 entry = entry->next;
416 }
417 return NULL;
418 }
419
420 void fcml_fn_coll_map_free(fcml_coll_map map_int) {
421 if (map_int) {
422 fcml_fn_coll_map_clear(map_int);
423 struct fcml_ist_coll_map *map = (struct fcml_ist_coll_map*) map_int;
424 if (map->map_entries) {
425 fcml_fn_env_memory_free(map->map_entries);
426 }
427 fcml_fn_env_memory_free(map);
428 }
429 }
430
431 /* Build-in Hash & Equals implementations. */
432
433 static fcml_uint32_t key_hash_string(fcml_ptr key) {
434 fcml_uint32_t hash = 0;
435 fcml_string str_key = (fcml_string) key;
436 int i;
437 for (i = 0; str_key[i] != '\0'; i++) {
438 hash = (hash << 6) | (hash >> 26);
439 hash += (fcml_uint32_t) str_key[i];
440 }
441 return hash;
442 }
443
444 static fcml_bool key_equals_string(fcml_ptr key1, fcml_ptr key2) {
445 return fcml_fn_env_str_strcmp((fcml_string) key1, (fcml_string) key2);
446 }
447
448 static fcml_uint32_t key_hash_uint32(fcml_ptr key) {
449 return *((fcml_uint32_t*) key);
450 }
451
452 static fcml_bool key_equals_uint32(fcml_ptr key1, fcml_ptr key2) {
453 return *((fcml_uint32_t*) key1) == *((fcml_uint32_t*) key2);
454 }