1 /*============================================================================
2 * Map helper structure
3 *============================================================================*/
4
5 /*
6 This file is part of Code_Saturne, a general-purpose CFD tool.
7
8 Copyright (C) 1998-2021 EDF S.A.
9
10 This program is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free Software
12 Foundation; either version 2 of the License, or (at your option) any later
13 version.
14
15 This program is distributed in the hope that it will be useful, but WITHOUT
16 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
17 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
18 details.
19
20 You should have received a copy of the GNU General Public License along with
21 this program; if not, write to the Free Software Foundation, Inc., 51 Franklin
22 Street, Fifth Floor, Boston, MA 02110-1301, USA.
23 */
24
25 /*----------------------------------------------------------------------------*/
26
27 #include "cs_defs.h"
28
29 /*----------------------------------------------------------------------------
30 * Standard C library headers
31 *----------------------------------------------------------------------------*/
32
33 #include <stdio.h>
34 #include <stdlib.h>
35 #include <string.h>
36 #include <assert.h>
37
38 /*----------------------------------------------------------------------------
39 * Local headers
40 *----------------------------------------------------------------------------*/
41
42 #include "bft_mem.h"
43 #include "bft_error.h"
44 #include "bft_printf.h"
45
46 #include "cs_base.h"
47
48 /*----------------------------------------------------------------------------
49 * Header for the current file
50 *----------------------------------------------------------------------------*/
51
52 #include "cs_map.h"
53
54 /*----------------------------------------------------------------------------*/
55
56 BEGIN_C_DECLS
57
58 /*! \cond DOXYGEN_SHOULD_SKIP_THIS */
59
60 /*=============================================================================
61 * Local Macro Definitions
62 *============================================================================*/
63
64 /* Align to 64-bit size for better performance */
65
66 #define CS_ALIGN_SIZE(s) (((s-1)/8+1)*8)
67
68 /*=============================================================================
69 * Local Structure Definitions
70 *============================================================================*/
71
72 /* Basic Map structure */
73 /*---------------------*/
74
75 struct _cs_map_name_to_id_t {
76
77 size_t size; /* Number of entries */
78 size_t max_size; /* Maximum number of entries */
79
80 size_t max_keys_size; /* Maximum size for keys buffer */
81 size_t keys_size; /* Size of keys buffer */
82 char *keys; /* Key buffer */
83
84 char **key; /* Pointer to keys */
85 int *id; /* Matching id */
86 int *reverse_id; /* Reverse id mapping */
87 };
88
89 /*============================================================================
90 * Global variables
91 *============================================================================*/
92
93 /*============================================================================
94 * Private function definitions
95 *============================================================================*/
96
97 /*----------------------------------------------------------------------------
98 * Insert new key.
99 *
100 * parameters:
101 * m <-> pointer to map structure
102 * key <-- character string (key)
103 * id <-- id associated with key
104 * index <-- index of key in map
105 *----------------------------------------------------------------------------*/
106
107 static void
_name_to_id_insert_key(cs_map_name_to_id_t * m,const char * key,int id,size_t index)108 _name_to_id_insert_key(cs_map_name_to_id_t *m,
109 const char *key,
110 int id,
111 size_t index)
112 {
113 size_t i;
114 size_t key_size = CS_ALIGN_SIZE(strlen(key) + 1);
115
116 /* Resize map arrays if necessary */
117
118 if (m->size >= m->max_size) {
119
120 size_t prev_size = m->max_size;
121
122 m->max_size*= 2;
123 BFT_REALLOC(m->key, m->max_size, char *);
124 BFT_REALLOC(m->id, m->max_size, int);
125 BFT_REALLOC(m->reverse_id, m->max_size, int);
126
127 for (i = prev_size; i < m->max_size; i++) {
128 m->key[i] = NULL;
129 m->id[i] = -1;
130 m->reverse_id[i] = -1;
131 }
132 }
133
134 if (m->keys_size + key_size >= m->max_keys_size) {
135
136 size_t min_size = m->keys_size + key_size;
137 size_t prev_size = m->max_keys_size;
138 char *old_addr = m->keys;
139 ptrdiff_t addr_shift = 0;
140
141 m->max_keys_size*= 2;
142 if (m->max_keys_size < min_size)
143 m->max_keys_size = min_size;
144
145 BFT_REALLOC(m->keys, m->max_keys_size, char);
146 addr_shift = m->keys - old_addr;
147
148 for (i = 0; i < m->size; i++) {
149 m->key[i] += addr_shift;
150 }
151
152 for (i = prev_size; i < m->max_keys_size; i++)
153 m->keys[i] = '\0';
154 }
155
156 /* Shift previous data */
157
158 for (i = m->size; i > index; i--) {
159 m->key[i] = m->key[i-1];
160 m->id[i] = m->id[i-1];
161 m->reverse_id[m->id[i]] = i;
162 }
163
164 /* Insert data */
165
166 strcpy(m->keys + m->keys_size, key);
167
168 m->key[index] = m->keys + m->keys_size;
169 m->id[index] = id;
170 m->reverse_id[m->size] = index;
171
172 m->keys_size += key_size;
173
174 m->size += 1;
175 }
176
177 /*! (DOXYGEN_SHOULD_SKIP_THIS) \endcond */
178
179 /*============================================================================
180 * Public function definitions for Fortran API
181 *============================================================================*/
182
183 /*============================================================================
184 * Public function definitions
185 *============================================================================*/
186
187 /*----------------------------------------------------------------------------
188 * Create empty name to id map.
189 *
190 * returns:
191 * pointer to newly initialized map structure.
192 *----------------------------------------------------------------------------*/
193
194 cs_map_name_to_id_t *
cs_map_name_to_id_create(void)195 cs_map_name_to_id_create(void)
196 {
197 cs_map_name_to_id_t *m = NULL;
198
199 BFT_MALLOC(m, 1, cs_map_name_to_id_t);
200
201 m->size = 0;
202 m->max_size = 8;
203
204 m->max_keys_size = 128;
205 m->keys_size = 0;
206
207 BFT_MALLOC(m->keys, m->max_keys_size, char);
208
209 BFT_MALLOC(m->key, m->max_size, char *);
210 BFT_MALLOC(m->id, m->max_size, int);
211 BFT_MALLOC(m->reverse_id, m->max_size, int);
212
213 return m;
214 }
215
216 /*----------------------------------------------------------------------------
217 * Destroy name to id map structure.
218 *
219 * parameters:
220 * m <-> pointer to map structure.
221 *----------------------------------------------------------------------------*/
222
223 void
cs_map_name_to_id_destroy(cs_map_name_to_id_t ** m)224 cs_map_name_to_id_destroy(cs_map_name_to_id_t **m)
225 {
226 if (m != NULL) {
227
228 if (*m != NULL) {
229
230 cs_map_name_to_id_t *_m = *m;
231
232 BFT_FREE(_m->reverse_id);
233 BFT_FREE(_m->id);
234 BFT_FREE(_m->key);
235
236 BFT_FREE(_m->keys);
237
238 BFT_FREE(*m);
239
240 }
241 }
242 }
243
244 /*----------------------------------------------------------------------------
245 * Find id matching a key, inserting key if not already present.
246 *
247 * parameters:
248 * m <-> pointer to map structure
249 * key <-- character string (key)
250 *
251 * returns:
252 * id matching key (already present or newly inserted)
253 *----------------------------------------------------------------------------*/
254
255 int
cs_map_name_to_id(cs_map_name_to_id_t * m,const char * key)256 cs_map_name_to_id(cs_map_name_to_id_t *m,
257 const char *key)
258 {
259 int start_id, end_id, mid_id;
260 int cmp_ret = 1;
261
262 /* Use binary search to find entry */
263
264 start_id = 0;
265 end_id = m->size - 1;
266 mid_id = start_id + ((end_id -start_id) / 2);
267
268 while (start_id <= end_id) {
269 cmp_ret = strcmp(m->key[mid_id], key);
270 if (cmp_ret < 0)
271 start_id = mid_id + 1;
272 else if (cmp_ret > 0)
273 end_id = mid_id - 1;
274 else
275 break;
276 mid_id = start_id + ((end_id -start_id) / 2);
277 }
278
279 /* If not found, insert key */
280
281 if (cmp_ret != 0)
282 _name_to_id_insert_key(m, key, m->size, mid_id);
283
284 return m->id[mid_id];
285 }
286
287 /*----------------------------------------------------------------------------
288 * Return id matching a key, or -1 if not present.
289 *
290 *
291 * parameters:
292 * m <-- pointer to map structure
293 * key <-- character string (key)
294 *
295 * returns:
296 * id matching key, or -1.
297 *----------------------------------------------------------------------------*/
298
299 int
cs_map_name_to_id_try(const cs_map_name_to_id_t * m,const char * key)300 cs_map_name_to_id_try(const cs_map_name_to_id_t *m,
301 const char *key)
302 {
303 int start_id, end_id, mid_id;
304 int cmp_ret = 1;
305
306 int retval = -1;
307
308 /* Use binary search to find entry */
309
310 if (m != NULL) {
311
312 start_id = 0;
313 end_id = m->size - 1;
314 mid_id = start_id + ((end_id -start_id) / 2);
315
316 while (start_id <= end_id) {
317 cmp_ret = strcmp(m->key[mid_id], key);
318 if (cmp_ret < 0)
319 start_id = mid_id + 1;
320 else if (cmp_ret > 0)
321 end_id = mid_id - 1;
322 else
323 break;
324 mid_id = start_id + ((end_id -start_id) / 2);
325 }
326
327 if (cmp_ret == 0)
328 retval = m->id[mid_id];
329
330 }
331
332 return retval;
333 }
334
335
336 /*----------------------------------------------------------------------------
337 * Return a key name in a map matching a given id.
338 *
339 * parameters:
340 * m <-- pointer to map structure.
341 * id <-- key id
342 *
343 * returns:
344 * pointer to key.
345 *----------------------------------------------------------------------------*/
346
347 const char *
cs_map_name_to_id_reverse(const cs_map_name_to_id_t * m,size_t id)348 cs_map_name_to_id_reverse(const cs_map_name_to_id_t *m,
349 size_t id)
350 {
351 const char *retval = NULL;
352
353 if (m == NULL)
354 return retval;
355
356 if (id < m->size)
357 retval = (const char *)(m->key[m->reverse_id[id]]);
358
359 return retval;
360 }
361 /*----------------------------------------------------------------------------
362 * Return the size of a map.
363 *
364 * parameters:
365 * m <-- pointer to map structure.
366 *
367 * returns:
368 * number of entries in map.
369 *----------------------------------------------------------------------------*/
370
371 size_t
cs_map_name_to_id_size(const cs_map_name_to_id_t * m)372 cs_map_name_to_id_size(const cs_map_name_to_id_t *m)
373 {
374 size_t retval = 0;
375
376 if (m != NULL)
377 retval = m->size;
378
379 return retval;
380 }
381
382 /*----------------------------------------------------------------------------
383 * Return key in a map for a given index position.
384 *
385 * parameters:
386 * m <-- pointer to map structure.
387 * index <-- key index
388 *
389 * returns:
390 * pointer to key.
391 *----------------------------------------------------------------------------*/
392
393 const char *
cs_map_name_to_id_key(const cs_map_name_to_id_t * m,size_t index)394 cs_map_name_to_id_key(const cs_map_name_to_id_t *m,
395 size_t index)
396 {
397 const char *retval = NULL;
398
399 if (m == NULL)
400 return retval;
401
402 if (index < m->size)
403 retval = (const char *)(m->key[index]);
404
405 return retval;
406 }
407
408 /*----------------------------------------------------------------------------*/
409
410 END_C_DECLS
411