FrontISTR 5.2.0
Large-scale structural analysis program with finit element method
Loading...
Searching...
No Matches
hecmw_map_int.c
Go to the documentation of this file.
1/*****************************************************************************
2 * Copyright (c) 2019 FrontISTR Commons
3 * This software is released under the MIT License, see LICENSE.txt
4 *****************************************************************************/
5
6#include <stdio.h>
7#include <stdlib.h>
8#include <string.h>
9#include <errno.h>
10#include "hecmw_util.h"
11#include "hecmw_malloc.h"
12#include "hecmw_config.h"
13#include "hecmw_bit_array.h"
14#include "hecmw_map_int.h"
15
17
18int HECMW_map_int_init(struct hecmw_map_int *map, void (*free_fnc)(void *)) {
19 HECMW_assert(map);
20
21 map->n_val = 0;
22 map->max_val = 0;
23
24 map->vals = NULL;
25 map->pairs = NULL;
26
27 map->checked = 1;
28 map->sorted = 1;
29
30 map->mark = NULL;
31
32 map->in_iter = 0;
33 map->iter = 0;
34
35 map->free_fnc = free_fnc;
36
37 return HECMW_SUCCESS;
38}
39
41 HECMW_assert(map);
42
43 if (map->max_val == 0) {
44 HECMW_assert(map->n_val == 0);
45 return;
46 }
47
48 if (map->free_fnc != NULL) {
49 size_t i;
50
51 for (i = 0; i < map->n_val; i++) map->free_fnc(map->vals[i].val);
52 }
53
54 HECMW_free(map->vals);
55 HECMW_free(map->pairs);
56
57 if (map->mark != NULL) {
59 HECMW_free(map->mark);
60 }
61
62 return;
63}
64
65size_t HECMW_map_int_nval(const struct hecmw_map_int *map) {
66 HECMW_assert(map);
67
68 return map->n_val;
69}
70
71static int map_resize(struct hecmw_map_int *map, size_t new_max_val) {
72 HECMW_assert(map);
73 HECMW_assert(map->n_val <= new_max_val);
74
75 if (map->max_val == new_max_val) return HECMW_SUCCESS;
76
77 if (map->mark) {
79 HECMW_free(map->mark);
80 map->mark = NULL;
81 }
82
83 if (new_max_val == 0) {
84 HECMW_assert(map->vals != NULL && map->pairs != NULL);
85
86 free(map->vals);
87 map->vals = NULL;
88 free(map->pairs);
89 map->pairs = NULL;
90 } else {
91 struct hecmw_map_int_value *new_vals;
92 struct hecmw_map_int_pair *new_pairs;
93
94 new_vals = (struct hecmw_map_int_value *)HECMW_realloc(
95 map->vals, sizeof(struct hecmw_map_int_value) * new_max_val);
96 if (new_vals == NULL) return HECMW_ERROR;
97 map->vals = new_vals;
98
99 new_pairs = (struct hecmw_map_int_pair *)HECMW_realloc(
100 map->pairs, sizeof(struct hecmw_map_int_pair) * new_max_val);
101 if (new_pairs == NULL) return HECMW_ERROR;
102 map->pairs = new_pairs;
103 }
104
105 map->max_val = new_max_val;
106 return HECMW_SUCCESS;
107}
108
109static int map_grow(struct hecmw_map_int *map) {
110 size_t new_max_val;
111
112 HECMW_assert(map);
113
114 if (map->max_val == 0)
115 new_max_val = MAP_MAX_VAL_INIT;
116 else
117 new_max_val = map->max_val * MAP_MAX_VAL_GROW;
118
119 return map_resize(map, new_max_val);
120}
121
122int HECMW_map_int_add(struct hecmw_map_int *map, int key, void *value) {
123 HECMW_assert(map);
124
125 if (map->n_val == map->max_val)
126 if (map_grow(map) != HECMW_SUCCESS) return HECMW_ERROR;
127
128 map->vals[map->n_val].key = key;
129 map->vals[map->n_val].val = value;
130
131 map->pairs[map->n_val].key = key;
132 map->pairs[map->n_val].local = map->n_val;
133
134 if (map->n_val > 0 && map->sorted) {
135 int key_prev = map->vals[map->n_val - 1].key;
136
137 if (key_prev > key) map->sorted = map->checked = 0;
138
139 if (map->checked && key_prev == key) map->checked = 0;
140 }
141
142 map->n_val++;
143
144 return HECMW_SUCCESS;
145}
146
147static int pair_cmp(const void *v1, const void *v2) {
148 const struct hecmw_map_int_pair *p1, *p2;
149
150 p1 = (const struct hecmw_map_int_pair *)v1;
151 p2 = (const struct hecmw_map_int_pair *)v2;
152
153 if (p1->key < p2->key) return -1;
154 if (p1->key > p2->key) return 1;
155 return 0;
156}
157
159 size_t i, n_dup = 0, n = 1;
160
161 HECMW_assert(map);
162
163 if (map->checked) return 0;
164
165 if (!map->sorted) {
166 qsort(map->pairs, map->n_val, sizeof(struct hecmw_map_int_pair), pair_cmp);
167 map->sorted = 1;
168 }
169
172
173 for (i = 1; i < map->n_val; i++) {
174 if (map->pairs[i - n].key == map->pairs[i].key) {
175 n_dup++;
176 if (map->pairs[i - n].local < map->pairs[i].local) {
177 HECMW_bit_array_unset(map->mark, map->pairs[i - n].local);
178 n = 1;
179 } else {
180 HECMW_bit_array_unset(map->mark, map->pairs[i].local);
181 n++;
182 }
183 } else {
184 n = 1;
185 }
186 }
187
189
190 map->checked = 1;
191
192 map_resize(map, map->n_val); /* reduce memory usage */
193
194 return n_dup;
195}
196
197static int map_search(const struct hecmw_map_int *map, int key, size_t *index) {
198 size_t left, right, center;
199 int ckey;
200
201 HECMW_assert(map && index);
202
203 /* binary search */
204
205 left = 0;
206 right = map->n_val - 1;
207
208 while (left <= right) {
209 center = (left + right) / 2;
210 ckey = map->pairs[center].key;
211
212 if (ckey < key)
213 left = center + 1;
214 else if (ckey > key)
215 right = center - 1;
216 else { /* ckey == key */
217 *index = map->pairs[center].local;
218 return HECMW_SUCCESS;
219 }
220 }
221
222 /* not found */
223 *index = left;
224 return HECMW_ERROR;
225}
226
227int HECMW_map_int_key2local(const struct hecmw_map_int *map, int key,
228 size_t *local) {
229 size_t index;
230
231 HECMW_assert(map);
232 HECMW_assert(map->checked);
233
234 if (map_search(map, key, local) != HECMW_SUCCESS) return HECMW_ERROR;
235
236 HECMW_assert(0 <= *local && *local < map->n_val);
237 HECMW_assert(map->vals[*local].key == key);
238
239 return HECMW_SUCCESS;
240}
241
242void *HECMW_map_int_get(const struct hecmw_map_int *map, int key) {
243 size_t local;
244
245 HECMW_assert(map);
246 HECMW_assert(map->checked);
247
248 if (HECMW_map_int_key2local(map, key, &local) != HECMW_SUCCESS) return NULL;
249
250 return map->vals[local].val;
251}
252
254 HECMW_assert(map);
255 HECMW_assert(map->checked);
256
257 map->in_iter = 1;
258 map->iter = 0;
259 return;
260}
261
262int HECMW_map_int_iter_next(struct hecmw_map_int *map, int *key, void **value) {
263 HECMW_assert(map && key);
264 HECMW_assert(map->in_iter);
265 HECMW_assert(map->iter <= map->n_val);
266
267 if (map->iter == map->n_val) {
268 map->in_iter = 0;
269 map->iter = 0;
270 return 0;
271 }
272
273 *key = map->vals[map->iter].key;
274 if (value != NULL) *value = map->vals[map->iter].val;
275
276 map->iter++;
277
278 return 1;
279}
280
282 HECMW_assert(map);
283
284 if (map->mark != NULL) {
286 HECMW_free(map->mark);
287 }
288 map->mark =
289 (struct hecmw_bit_array *)HECMW_malloc(sizeof(struct hecmw_bit_array));
290 if (map->mark == NULL) {
291 return HECMW_ERROR;
292 }
293
294 if (HECMW_bit_array_init(map->mark, map->n_val) != HECMW_SUCCESS)
295 return HECMW_ERROR;
296
297 return HECMW_SUCCESS;
298}
299
300int HECMW_map_int_mark(struct hecmw_map_int *map, int key) {
301 size_t local;
302
303 HECMW_assert(map);
304 HECMW_assert(map->mark);
305
306 if (HECMW_map_int_key2local(map, key, &local) != HECMW_SUCCESS)
307 return HECMW_ERROR;
308
309 HECMW_bit_array_set(map->mark, local);
310
311 return HECMW_SUCCESS;
312}
313
315 void **value) {
316 HECMW_assert(map);
317 HECMW_assert(0 <= map->iter && map->iter <= map->n_val);
318 HECMW_assert(map->mark);
319
320 while (map->iter < map->n_val && HECMW_bit_array_get(map->mark, map->iter))
321 map->iter++;
322
323 return HECMW_map_int_iter_next(map, key, value);
324}
325
326static void rebuild_pairs(struct hecmw_map_int *map) {
327 size_t i;
328 int sorted = 1;
329
330 HECMW_assert(map);
331
332 for (i = 0; i < map->n_val; i++) {
333 map->pairs[i].key = map->vals[i].key;
334 map->pairs[i].local = i;
335 if (i > 0 && map->vals[i].key < map->vals[i - 1].key) sorted = 0;
336 }
337
338 if (!sorted) {
339 qsort(map->pairs, map->n_val, sizeof(struct hecmw_map_int_pair), pair_cmp);
340 }
341}
342
344 size_t i, n_del = 0;
345
346 HECMW_assert(map);
347 HECMW_assert(map->mark);
348
349 for (i = 0; i < map->n_val; i++) {
350 if (HECMW_bit_array_get(map->mark, i)) { /* marked */
351 if (n_del > 0) map->vals[i - n_del] = map->vals[i];
352 } else { /* not marked */
353 if (map->free_fnc != NULL) map->free_fnc(map->vals[i].val);
354 n_del++;
355 }
356 }
357
358 if (n_del > 0) {
359 map->n_val -= n_del;
360 rebuild_pairs(map);
361 }
362
364 HECMW_free(map->mark);
365 map->mark = NULL;
366
367 return n_del;
368}
int HECMW_bit_array_init(struct hecmw_bit_array *ba, size_t len)
int HECMW_bit_array_get(struct hecmw_bit_array *ba, size_t index)
void HECMW_bit_array_set(struct hecmw_bit_array *ba, size_t index)
void HECMW_bit_array_unset(struct hecmw_bit_array *ba, size_t index)
void HECMW_bit_array_set_all(struct hecmw_bit_array *ba)
void HECMW_bit_array_finalize(struct hecmw_bit_array *ba)
#define HECMW_ERROR
Definition: hecmw_config.h:66
#define HECMW_SUCCESS
Definition: hecmw_config.h:64
#define NULL
#define HECMW_realloc(ptr, size)
Definition: hecmw_malloc.h:22
#define HECMW_free(ptr)
Definition: hecmw_malloc.h:24
#define HECMW_malloc(size)
Definition: hecmw_malloc.h:20
size_t HECMW_map_int_nval(const struct hecmw_map_int *map)
Definition: hecmw_map_int.c:65
int HECMW_map_int_add(struct hecmw_map_int *map, int key, void *value)
int HECMW_map_int_iter_next(struct hecmw_map_int *map, int *key, void **value)
int HECMW_map_int_mark_init(struct hecmw_map_int *map)
int HECMW_map_int_mark(struct hecmw_map_int *map, int key)
int HECMW_map_int_iter_next_unmarked(struct hecmw_map_int *map, int *key, void **value)
@ MAP_MAX_VAL_INIT
Definition: hecmw_map_int.c:16
@ MAP_MAX_VAL_GROW
Definition: hecmw_map_int.c:16
int HECMW_map_int_del_unmarked(struct hecmw_map_int *map)
size_t HECMW_map_int_check_dup(struct hecmw_map_int *map)
void HECMW_map_int_iter_init(struct hecmw_map_int *map)
void HECMW_map_int_finalize(struct hecmw_map_int *map)
Definition: hecmw_map_int.c:40
int HECMW_map_int_key2local(const struct hecmw_map_int *map, int key, size_t *local)
void * HECMW_map_int_get(const struct hecmw_map_int *map, int key)
int HECMW_map_int_init(struct hecmw_map_int *map, void(*free_fnc)(void *))
Definition: hecmw_map_int.c:18
#define HECMW_assert(cond)
Definition: hecmw_util.h:40
struct hecmw_map_int_value * vals
Definition: hecmw_map_int.h:25
struct hecmw_bit_array * mark
Definition: hecmw_map_int.h:31
struct hecmw_map_int_pair * pairs
Definition: hecmw_map_int.h:26
void(* free_fnc)(void *)
Definition: hecmw_map_int.h:36