1 /*
2 * (C) Copyright 2005- ECMWF.
3 *
4 * This software is licensed under the terms of the Apache Licence Version 2.0
5 * which can be obtained at http://www.apache.org/licenses/LICENSE-2.0.
6 *
7 * In applying this licence, ECMWF does not waive the privileges and immunities granted to it by
8 * virtue of its status as an intergovernmental organisation nor does it submit to any jurisdiction.
9 */
10
11 #include "grib_api_internal.h"
12
13 /* Note: all non-alpha are mapped to 0 */
14 static const int mapping[] = {
15 0, /* 00 */
16 0, /* 01 */
17 0, /* 02 */
18 0, /* 03 */
19 0, /* 04 */
20 0, /* 05 */
21 0, /* 06 */
22 0, /* 07 */
23 0, /* 08 */
24 0, /* 09 */
25 0, /* 0a */
26 0, /* 0b */
27 0, /* 0c */
28 0, /* 0d */
29 0, /* 0e */
30 0, /* 0f */
31 0, /* 10 */
32 0, /* 11 */
33 0, /* 12 */
34 0, /* 13 */
35 0, /* 14 */
36 0, /* 15 */
37 0, /* 16 */
38 0, /* 17 */
39 0, /* 18 */
40 0, /* 19 */
41 0, /* 1a */
42 0, /* 1b */
43 0, /* 1c */
44 0, /* 1d */
45 0, /* 1e */
46 0, /* 1f */
47 0, /* 20 */
48 0, /* 21 */
49 0, /* 22 */
50 38, /* # */
51 0, /* 24 */
52 0, /* 25 */
53 0, /* 26 */
54 0, /* 27 */
55 0, /* 28 */
56 0, /* 29 */
57 0, /* 2a */
58 0, /* 2b */
59 0, /* 2c */
60 0, /* 2d */
61 0, /* 2e */
62 0, /* 2f */
63 1, /* 0 */
64 2, /* 1 */
65 3, /* 2 */
66 4, /* 3 */
67 5, /* 4 */
68 6, /* 5 */
69 7, /* 6 */
70 8, /* 7 */
71 9, /* 8 */
72 10, /* 9 */
73 0, /* 3a */
74 0, /* 3b */
75 0, /* 3c */
76 0, /* 3d */
77 0, /* 3e */
78 0, /* 3f */
79 0, /* 40 */
80 11, /* A */
81 12, /* B */
82 13, /* C */
83 14, /* D */
84 15, /* E */
85 16, /* F */
86 17, /* G */
87 18, /* H */
88 19, /* I */
89 20, /* J */
90 21, /* K */
91 22, /* L */
92 23, /* M */
93 24, /* N */
94 25, /* O */
95 26, /* P */
96 27, /* Q */
97 28, /* R */
98 29, /* S */
99 30, /* T */
100 31, /* U */
101 32, /* V */
102 33, /* W */
103 34, /* X */
104 35, /* Y */
105 36, /* Z */
106 0, /* 5b */
107 0, /* 5c */
108 0, /* 5d */
109 0, /* 5e */
110 37, /* _ */
111 0, /* 60 */
112 11, /* a */
113 12, /* b */
114 13, /* c */
115 14, /* d */
116 15, /* e */
117 16, /* f */
118 17, /* g */
119 18, /* h */
120 19, /* i */
121 20, /* j */
122 21, /* k */
123 22, /* l */
124 23, /* m */
125 24, /* n */
126 25, /* o */
127 26, /* p */
128 27, /* q */
129 28, /* r */
130 29, /* s */
131 30, /* t */
132 31, /* u */
133 32, /* v */
134 33, /* w */
135 34, /* x */
136 35, /* y */
137 36, /* z */
138 0, /* 7b */
139 0, /* 7c */
140 0, /* 7d */
141 0, /* 7e */
142 0, /* 7f */
143 0, /* 80 */
144 0, /* 81 */
145 0, /* 82 */
146 0, /* 83 */
147 0, /* 84 */
148 0, /* 85 */
149 0, /* 86 */
150 0, /* 87 */
151 0, /* 88 */
152 0, /* 89 */
153 0, /* 8a */
154 0, /* 8b */
155 0, /* 8c */
156 0, /* 8d */
157 0, /* 8e */
158 0, /* 8f */
159 0, /* 90 */
160 0, /* 91 */
161 0, /* 92 */
162 0, /* 93 */
163 0, /* 94 */
164 0, /* 95 */
165 0, /* 96 */
166 0, /* 97 */
167 0, /* 98 */
168 0, /* 99 */
169 0, /* 9a */
170 0, /* 9b */
171 0, /* 9c */
172 0, /* 9d */
173 0, /* 9e */
174 0, /* 9f */
175 0, /* a0 */
176 0, /* a1 */
177 0, /* a2 */
178 0, /* a3 */
179 0, /* a4 */
180 0, /* a5 */
181 0, /* a6 */
182 0, /* a7 */
183 0, /* a8 */
184 0, /* a9 */
185 0, /* aa */
186 0, /* ab */
187 0, /* ac */
188 0, /* ad */
189 0, /* ae */
190 0, /* af */
191 0, /* b0 */
192 0, /* b1 */
193 0, /* b2 */
194 0, /* b3 */
195 0, /* b4 */
196 0, /* b5 */
197 0, /* b6 */
198 0, /* b7 */
199 0, /* b8 */
200 0, /* b9 */
201 0, /* ba */
202 0, /* bb */
203 0, /* bc */
204 0, /* bd */
205 0, /* be */
206 0, /* bf */
207 0, /* c0 */
208 0, /* c1 */
209 0, /* c2 */
210 0, /* c3 */
211 0, /* c4 */
212 0, /* c5 */
213 0, /* c6 */
214 0, /* c7 */
215 0, /* c8 */
216 0, /* c9 */
217 0, /* ca */
218 0, /* cb */
219 0, /* cc */
220 0, /* cd */
221 0, /* ce */
222 0, /* cf */
223 0, /* d0 */
224 0, /* d1 */
225 0, /* d2 */
226 0, /* d3 */
227 0, /* d4 */
228 0, /* d5 */
229 0, /* d6 */
230 0, /* d7 */
231 0, /* d8 */
232 0, /* d9 */
233 0, /* da */
234 0, /* db */
235 0, /* dc */
236 0, /* dd */
237 0, /* de */
238 0, /* df */
239 0, /* e0 */
240 0, /* e1 */
241 0, /* e2 */
242 0, /* e3 */
243 0, /* e4 */
244 0, /* e5 */
245 0, /* e6 */
246 0, /* e7 */
247 0, /* e8 */
248 0, /* e9 */
249 0, /* ea */
250 0, /* eb */
251 0, /* ec */
252 0, /* ed */
253 0, /* ee */
254 0, /* ef */
255 0, /* f0 */
256 0, /* f1 */
257 0, /* f2 */
258 0, /* f3 */
259 0, /* f4 */
260 0, /* f5 */
261 0, /* f6 */
262 0, /* f7 */
263 0, /* f8 */
264 0, /* f9 */
265 0, /* fa */
266 0, /* fb */
267 0, /* fc */
268 0, /* fd */
269 0, /* fe */
270 0, /* ff */
271 };
272
273 /* ECC-388 */
274 #ifdef DEBUG
275 static const size_t NUM_MAPPINGS = sizeof(mapping) / sizeof(mapping[0]);
276
277 #define DebugCheckBounds(index, value) \
278 do { \
279 if (!((index) >= 0 && (index) < NUM_MAPPINGS)) { \
280 printf("ERROR: string='%s' index=%ld @ %s +%d \n", value, (long)index, __FILE__, __LINE__); \
281 abort(); \
282 } \
283 } while (0)
284 #else
285 #define DebugCheckBounds(index, value)
286 #endif
287
288
289 #define SIZE 39
290
291 #if GRIB_PTHREADS
292 static pthread_once_t once = PTHREAD_ONCE_INIT;
293 static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
294
init()295 static void init()
296 {
297 pthread_mutexattr_t attr;
298 pthread_mutexattr_init(&attr);
299 pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE);
300 pthread_mutex_init(&mutex, &attr);
301 pthread_mutexattr_destroy(&attr);
302 }
303 #elif GRIB_OMP_THREADS
304 static int once = 0;
305 static omp_nest_lock_t mutex;
306
init()307 static void init()
308 {
309 GRIB_OMP_CRITICAL(lock_grib_trie_with_rank_c)
310 {
311 if (once == 0) {
312 omp_init_nest_lock(&mutex);
313 once = 1;
314 }
315 }
316 }
317 #endif
318
319 /*
320 struct grib_trie_with_rank_list {
321 grib_trie_with_rank_list* next;
322 int rank;
323 void* data;
324 };
325 */
326
327 struct grib_trie_with_rank
328 {
329 grib_trie_with_rank* next[SIZE];
330 grib_context* context;
331 int first;
332 int last;
333 grib_oarray* objs;
334 };
335
grib_trie_with_rank_new(grib_context * c)336 grib_trie_with_rank* grib_trie_with_rank_new(grib_context* c)
337 {
338 #ifdef RECYCLE_TRIE
339 grib_trie_with_rank* t = grib_context_malloc_clear_persistent(c, sizeof(grib_trie_with_rank));
340 #else
341 grib_trie_with_rank* t = (grib_trie_with_rank*)grib_context_malloc_clear(c, sizeof(grib_trie_with_rank));
342 #endif
343 t->context = c;
344 t->first = SIZE;
345 t->last = -1;
346 return t;
347 }
348
349 /*
350 static void grib_trie_with_rank_delete_container_list(grib_context* c,grib_trie_with_rank_list *list) {
351 grib_trie_with_rank_list* next=list;
352 grib_trie_with_rank_list* p;
353 while (next) {
354 p=next;
355 next=next->next;
356 grib_context_free( c, p );
357 }
358 }
359 */
360
_grib_trie_with_rank_delete_container(grib_trie_with_rank * t)361 static void _grib_trie_with_rank_delete_container(grib_trie_with_rank* t)
362 {
363 int i;
364 DebugAssert(t);
365 for (i = t->first; i <= t->last; i++)
366 if (t->next[i]) {
367 grib_trie_with_rank_delete_container(t->next[i]);
368 }
369 grib_oarray_delete(t->context, t->objs);
370 /* grib_trie_with_rank_delete_container_list(t->context,t->list); */
371 #ifdef RECYCLE_TRIE
372 grib_context_free_persistent(t->context, t);
373 #else
374 grib_context_free(t->context, t);
375 #endif
376 }
grib_trie_with_rank_delete_container(grib_trie_with_rank * t)377 void grib_trie_with_rank_delete_container(grib_trie_with_rank* t)
378 {
379 GRIB_MUTEX_INIT_ONCE(&once, &init);
380 GRIB_MUTEX_LOCK(&mutex);
381 _grib_trie_with_rank_delete_container(t);
382 GRIB_MUTEX_UNLOCK(&mutex);
383 }
384
385 /*
386 static void grib_trie_with_rank_delete_list(grib_context* c,grib_trie_with_rank_list *list) {
387 grib_trie_with_rank_list* next=list;
388 grib_trie_with_rank_list* p;
389 while (next) {
390 grib_context_free( c, next->data );
391 p=next;
392 next=next->next;
393 grib_context_free( c, p );
394 }
395 }
396 */
397
grib_trie_with_rank_delete(grib_trie_with_rank * t)398 void grib_trie_with_rank_delete(grib_trie_with_rank* t)
399 {
400 GRIB_MUTEX_INIT_ONCE(&once, &init);
401 GRIB_MUTEX_LOCK(&mutex);
402 if (t) {
403 int i;
404 for (i = t->first; i <= t->last; i++)
405 if (t->next[i]) {
406 if (t->objs) {
407 grib_oarray_delete_content(t->context, t->objs);
408 grib_oarray_delete(t->context, t->objs);
409 }
410 /* grib_trie_with_rank_delete_list(t->context, t->next[i]->list ); */
411 grib_trie_with_rank_delete(t->next[i]);
412 }
413 #ifdef RECYCLE_TRIE
414 grib_context_free_persistent(t->context, t);
415 #else
416 grib_context_free(t->context, t);
417 #endif
418 }
419 GRIB_MUTEX_UNLOCK(&mutex);
420 }
421
grib_trie_with_rank_clear(grib_trie_with_rank * t)422 void grib_trie_with_rank_clear(grib_trie_with_rank* t)
423 {
424 if (t) {
425 int i;
426 if (t->objs) {
427 grib_oarray_delete_content(t->context, t->objs);
428 grib_oarray_delete(t->context, t->objs);
429 }
430
431 for (i = t->first; i <= t->last; i++)
432 if (t->next[i])
433 grib_trie_with_rank_clear(t->next[i]);
434 }
435 }
436
437 /*
438 static void grib_trie_with_rank_insert_in_list(grib_trie_with_rank* t,void* data) {
439 if (t->list==NULL) {
440 t->list=grib_context_malloc_clear(t->context,sizeof(grib_trie_with_rank_list));
441 t->list->data=data;
442 t->list->rank=1;
443 t->last_list=t->list;
444 } else {
445 t->last_list->next=grib_context_malloc_clear(t->context,sizeof(grib_trie_with_rank_list));
446 t->last_list=t->last_list->next;
447 t->last_list->data=data;
448 t->last_list->rank++;
449 }
450 }
451 */
452
grib_trie_with_rank_insert(grib_trie_with_rank * t,const char * key,void * data)453 int grib_trie_with_rank_insert(grib_trie_with_rank* t, const char* key, void* data)
454 {
455 grib_trie_with_rank* last = t;
456 const char* k = key;
457 DebugAssert(t);
458 if (!t) return -1;
459
460 GRIB_MUTEX_INIT_ONCE(&once, &init);
461 GRIB_MUTEX_LOCK(&mutex);
462
463 while (*k && t) {
464 last = t;
465 DebugCheckBounds((int)*k, key);
466 t = t->next[mapping[(int)*k]];
467 if (t)
468 k++;
469 }
470
471 if (*k != 0) {
472 t = last;
473 while (*k) {
474 int j = 0;
475 DebugCheckBounds((int)*k, key);
476 j = mapping[(int)*k++];
477 if (j < t->first)
478 t->first = j;
479 if (j > t->last)
480 t->last = j;
481 t = t->next[j] = grib_trie_with_rank_new(t->context);
482 }
483 }
484 if (t->objs == NULL)
485 t->objs = grib_oarray_new(t->context, 100, 1000);
486 grib_oarray_push(t->context, t->objs, data);
487 /* grib_trie_with_rank_insert_in_list(t,data); */
488 GRIB_MUTEX_UNLOCK(&mutex);
489 return t->objs->n; /* grib_oarray_used_size(t->objs) */
490 }
491
492 /*
493 static void *grib_trie_with_rank_get_from_list(grib_trie_with_rank_list* list,int rank) {
494 grib_trie_with_rank_list* next=list;
495 int r=1;
496
497 while(next) {
498 if (r==rank) return next->data;
499 next=next->next;
500 r++;
501 }
502 return NULL;
503 }
504 */
505
grib_trie_with_rank_get(grib_trie_with_rank * t,const char * key,int rank)506 void* grib_trie_with_rank_get(grib_trie_with_rank* t, const char* key, int rank)
507 {
508 const char* k = key;
509 void* data;
510 GRIB_MUTEX_INIT_ONCE(&once, &init);
511
512 if (rank < 0)
513 return NULL;
514
515 GRIB_MUTEX_LOCK(&mutex);
516
517 while (*k && t) {
518 DebugCheckBounds((int)*k, key);
519 t = t->next[mapping[(int)*k++]];
520 }
521
522 if (*k == 0 && t != NULL) {
523 data = grib_oarray_get(t->objs, rank - 1);
524 GRIB_MUTEX_UNLOCK(&mutex);
525 return data;
526 }
527 GRIB_MUTEX_UNLOCK(&mutex);
528 return NULL;
529 }
530