/src/netcdf-c/libsrc4/ncindex.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | Copyright (c) 1998-2018 University Corporation for Atmospheric Research/Unidata |
3 | | See LICENSE.txt for license information. |
4 | | */ |
5 | | |
6 | | /** \file \internal |
7 | | Internal netcdf-4 functions. |
8 | | |
9 | | This file contains functions for manipulating ncindex objects. |
10 | | |
11 | | Warning: This code depends critically on the assumption that |
12 | | |void*| == |uintptr_t| |
13 | | |
14 | | */ |
15 | | |
16 | | /* Define this for debug so that table sizes are small */ |
17 | | #undef SMALLTABLE |
18 | | #undef NCNOHASH |
19 | | |
20 | | #include "config.h" |
21 | | #include <stdlib.h> |
22 | | #include <stdio.h> |
23 | | #include <string.h> |
24 | | #ifdef HAVE_STDINT_H |
25 | | #include <stdint.h> |
26 | | #endif |
27 | | #include <assert.h> |
28 | | |
29 | | #include "nc4internal.h" |
30 | | #include "ncindex.h" |
31 | | |
32 | | #ifdef SMALLTABLE |
33 | | /* Keep the table sizes small initially */ |
34 | | #define DFALTTABLESIZE 7 |
35 | | #else |
36 | 0 | #define DFALTTABLESIZE 37 |
37 | | #endif |
38 | | |
39 | | /* Hack to access internal state of a hashmap. Use with care */ |
40 | | /* Convert an entry from ACTIVE to DELETED; |
41 | | Return 0 if not found. |
42 | | */ |
43 | | extern int NC_hashmapdeactivate(NC_hashmap*, uintptr_t data); |
44 | | |
45 | | #ifndef NCNOHASH |
46 | | extern void printhashmap(NC_hashmap*); |
47 | | #endif |
48 | | |
49 | | /* Locate object by name in an NCindex */ |
50 | | NC_OBJ* |
51 | | ncindexlookup(NCindex* ncindex, const char* name) |
52 | 0 | { |
53 | 0 | NC_OBJ* obj = NULL; |
54 | 0 | if(ncindex == NULL || name == NULL) |
55 | 0 | return NULL; |
56 | 0 | { |
57 | 0 | #ifndef NCNOHASH |
58 | 0 | uintptr_t index; |
59 | 0 | assert(ncindex->map != NULL); |
60 | 0 | if(!NC_hashmapget(ncindex->map,(void*)name,strlen(name),&index)) |
61 | 0 | return NULL; /* not present */ |
62 | 0 | obj = (NC_OBJ*)nclistget(ncindex->list,(size_t)index); |
63 | | #else |
64 | | int i; |
65 | | for(i=0;i<nclistlength(ncindex->list);i++) { |
66 | | NC_OBJ* o = (NC_OBJ*)ncindex->list->content[i]; |
67 | | if(strcmp(o->name,name)==0) return o; |
68 | | } |
69 | | #endif |
70 | 0 | } |
71 | 0 | return obj; |
72 | 0 | } |
73 | | |
74 | | /* Get ith object in the vector */ |
75 | | NC_OBJ* |
76 | | ncindexith(NCindex* index, size_t i) |
77 | 0 | { |
78 | 0 | if(index == NULL) return NULL; |
79 | 0 | assert(index->list != NULL); |
80 | 0 | return nclistget(index->list,i); |
81 | 0 | } |
82 | | |
83 | | /* See if x is contained in the index */ |
84 | | /* Return vector position if in index, otherwise return -1. */ |
85 | | int |
86 | | ncindexfind(NCindex* index, NC_OBJ* nco) |
87 | 0 | { |
88 | 0 | int i; |
89 | 0 | NClist* list; |
90 | 0 | if(index == NULL || nco == NULL) return -1; |
91 | 0 | list = index->list; |
92 | 0 | for(i=0;i<nclistlength(list);i++) { |
93 | 0 | NC_OBJ* o = (NC_OBJ*)list->content[i]; |
94 | 0 | if(nco == o) return i; |
95 | 0 | } |
96 | 0 | return -1; |
97 | 0 | } |
98 | | |
99 | | /* Add object to the end of the vector, also insert into the hashmaps */ |
100 | | /* Return 1 if ok, 0 otherwise.*/ |
101 | | int |
102 | | ncindexadd(NCindex* ncindex, NC_OBJ* obj) |
103 | 0 | { |
104 | 0 | if(ncindex == NULL) return 0; |
105 | 0 | #ifndef NCNOHASH |
106 | 0 | { |
107 | 0 | uintptr_t index; /*Note not the global id */ |
108 | 0 | index = (uintptr_t)nclistlength(ncindex->list); |
109 | 0 | NC_hashmapadd(ncindex->map,index,(void*)obj->name,strlen(obj->name)); |
110 | 0 | } |
111 | 0 | #endif |
112 | 0 | if(!nclistpush(ncindex->list,obj)) |
113 | 0 | return 0; |
114 | 0 | return 1; |
115 | 0 | } |
116 | | |
117 | | /* Insert object at ith position of the vector, also insert into the hashmaps; */ |
118 | | /* Return 1 if ok, 0 otherwise.*/ |
119 | | int |
120 | | ncindexset(NCindex* ncindex, size_t i, NC_OBJ* obj) |
121 | 0 | { |
122 | 0 | if(ncindex == NULL) return 0; |
123 | 0 | if(!nclistset(ncindex->list,i,obj)) return 0; |
124 | 0 | #ifndef NCNOHASH |
125 | 0 | { |
126 | 0 | uintptr_t index = (uintptr_t)i; |
127 | 0 | NC_hashmapadd(ncindex->map,index,(void*)obj->name,strlen(obj->name)); |
128 | 0 | } |
129 | 0 | #endif |
130 | 0 | return 1; |
131 | 0 | } |
132 | | |
133 | | /** |
134 | | * Remove ith object from the index; |
135 | | * Return 1 if ok, 0 otherwise.*/ |
136 | | int |
137 | | ncindexidel(NCindex* index, size_t i) |
138 | 0 | { |
139 | 0 | if(index == NULL) return 0; |
140 | 0 | nclistremove(index->list,i); |
141 | 0 | #ifndef NCNOHASH |
142 | | /* Remove from the hash map by deactivating its entry */ |
143 | 0 | if(!NC_hashmapdeactivate(index->map,(uintptr_t)i)) |
144 | 0 | return 0; /* not present */ |
145 | 0 | #endif |
146 | 0 | return 1; |
147 | 0 | } |
148 | | |
149 | | /*Return a duplicate of the index's vector */ |
150 | | /* Return list if ok, NULL otherwise.*/ |
151 | | NC_OBJ** |
152 | | ncindexdup(NCindex* index) |
153 | 0 | { |
154 | 0 | if(index == NULL || nclistlength(index->list) == 0) |
155 | 0 | return NULL; |
156 | 0 | return (NC_OBJ**)nclistclone(index->list,0/*!deep*/); |
157 | 0 | } |
158 | | |
159 | | /* Count the non-null entries in an NCindex */ |
160 | | int |
161 | | ncindexcount(NCindex* index) |
162 | 0 | { |
163 | 0 | int count = 0; |
164 | 0 | int i; |
165 | 0 | for(i=0;i<ncindexsize(index);i++) { |
166 | 0 | if(ncindexith(index,i) != NULL) count++; |
167 | 0 | } |
168 | 0 | return count; |
169 | 0 | } |
170 | | |
171 | | /* |
172 | | Rebuild the list map by rehashing all entries |
173 | | using their current, possibly changed id and name; |
174 | | also recompute their hashkey. |
175 | | */ |
176 | | /* Return 1 if ok, 0 otherwise.*/ |
177 | | int |
178 | | ncindexrebuild(NCindex* index) |
179 | 0 | { |
180 | 0 | #ifndef NCNOHASH |
181 | 0 | size_t i; |
182 | 0 | size_t size = nclistlength(index->list); |
183 | 0 | NC_OBJ** contents = (NC_OBJ**)nclistextract(index->list); |
184 | | /* Reset the index map and list*/ |
185 | 0 | nclistfree(index->list); |
186 | 0 | index->list = nclistnew(); |
187 | 0 | nclistsetalloc(index->list,size); |
188 | 0 | NC_hashmapfree(index->map); |
189 | 0 | index->map = NC_hashmapnew(size); |
190 | | /* Now, reinsert all the attributes except NULLs */ |
191 | 0 | for(i=0;i<size;i++) { |
192 | 0 | NC_OBJ* tmp = contents[i]; |
193 | 0 | if(tmp == NULL) continue; /* ignore */ |
194 | 0 | if(!ncindexadd(index,tmp)) |
195 | 0 | return 0; |
196 | 0 | } |
197 | 0 | #endif |
198 | 0 | if(contents != NULL) free(contents); |
199 | 0 | return 1; |
200 | 0 | } |
201 | | |
202 | | /* Free a list map */ |
203 | | int |
204 | | ncindexfree(NCindex* index) |
205 | 0 | { |
206 | 0 | if(index == NULL) return 1; |
207 | 0 | nclistfree(index->list); |
208 | 0 | NC_hashmapfree(index->map); |
209 | 0 | free(index); |
210 | 0 | return 1; |
211 | 0 | } |
212 | | |
213 | | /* Create a new index */ |
214 | | NCindex* |
215 | | ncindexnew(size_t size0) |
216 | 0 | { |
217 | 0 | NCindex* index = NULL; |
218 | 0 | size_t size = (size0 == 0 ? DFALTTABLESIZE : size0); |
219 | 0 | index = calloc(1,sizeof(NCindex)); |
220 | 0 | if(index == NULL) return NULL; |
221 | 0 | index->list = nclistnew(); |
222 | 0 | if(index->list == NULL) {ncindexfree(index); return NULL;} |
223 | 0 | nclistsetalloc(index->list,size); |
224 | 0 | #ifndef NCNOHASH |
225 | 0 | index->map = NC_hashmapnew(size); |
226 | 0 | if(index->map == NULL) {ncindexfree(index); return NULL;} |
227 | 0 | #endif |
228 | 0 | return index; |
229 | 0 | } |
230 | | |
231 | | #ifndef NCNOHASH |
232 | | /* Debug: handle the data key part */ |
233 | | static const char* |
234 | | keystr(NC_hentry* e) |
235 | 0 | { |
236 | 0 | if(e->keysize < sizeof(uintptr_t)) |
237 | 0 | return (const char*)(&e->key); |
238 | 0 | else |
239 | 0 | return (const char*)(e->key); |
240 | 0 | } |
241 | | #endif |
242 | | |
243 | | int |
244 | | ncindexverify(NCindex* lm, int dump) |
245 | 0 | { |
246 | 0 | size_t i; |
247 | 0 | NClist* l = lm->list; |
248 | 0 | int nerrs = 0; |
249 | 0 | #ifndef NCNOHASH |
250 | 0 | size_t m; |
251 | 0 | #endif |
252 | |
|
253 | 0 | if(lm == NULL) { |
254 | 0 | fprintf(stderr,"index: <empty>\n"); |
255 | 0 | return 1; |
256 | 0 | } |
257 | 0 | if(dump) { |
258 | 0 | fprintf(stderr,"-------------------------\n"); |
259 | 0 | #ifndef NCNOHASH |
260 | 0 | if(lm->map->active == 0) { |
261 | 0 | fprintf(stderr,"hash: <empty>\n"); |
262 | 0 | goto next1; |
263 | 0 | } |
264 | 0 | for(i=0;i < lm->map->alloc; i++) { |
265 | 0 | NC_hentry* e = &lm->map->table[i]; |
266 | 0 | if(e->flags != 1) continue; |
267 | 0 | fprintf(stderr,"hash: %ld: data=%lu key=%s\n",(unsigned long)i,(unsigned long)e->data,keystr(e)); |
268 | 0 | fflush(stderr); |
269 | 0 | } |
270 | 0 | next1: |
271 | 0 | #endif |
272 | 0 | if(nclistlength(l) == 0) { |
273 | 0 | fprintf(stderr,"list: <empty>\n"); |
274 | 0 | goto next2; |
275 | 0 | } |
276 | 0 | for(i=0;i < nclistlength(l); i++) { |
277 | 0 | const char** a = (const char**)nclistget(l,i); |
278 | 0 | fprintf(stderr,"list: %ld: name=%s\n",(unsigned long)i,*a); |
279 | 0 | fflush(stderr); |
280 | 0 | } |
281 | 0 | fprintf(stderr,"-------------------------\n"); |
282 | 0 | fflush(stderr); |
283 | 0 | } |
284 | | |
285 | 0 | next2: |
286 | 0 | #ifndef NCNOHASH |
287 | | /* Need to verify that every entry in map is also in vector and vice-versa */ |
288 | | |
289 | | /* Verify that map entry points to same-named entry in vector */ |
290 | 0 | for(m=0;m < lm->map->alloc; m++) { |
291 | 0 | NC_hentry* e = &lm->map->table[m]; |
292 | 0 | char** object = NULL; |
293 | 0 | char* oname = NULL; |
294 | 0 | uintptr_t udata = (uintptr_t)e->data; |
295 | 0 | if((e->flags & 1) == 0) continue; |
296 | 0 | object = nclistget(l,(size_t)udata); |
297 | 0 | if(object == NULL) { |
298 | 0 | fprintf(stderr,"bad data: %d: %lu\n",(int)m,(unsigned long)udata); |
299 | 0 | nerrs++; |
300 | 0 | } else { |
301 | 0 | oname = *object; |
302 | 0 | if(strcmp(oname,keystr(e)) != 0) { |
303 | 0 | fprintf(stderr,"name mismatch: %d: %lu: hash=%s list=%s\n", |
304 | 0 | (int)m,(unsigned long)udata,keystr(e),oname); |
305 | 0 | nerrs++; |
306 | 0 | } |
307 | 0 | } |
308 | 0 | } |
309 | | /* Walk vector and mark corresponding hash entry*/ |
310 | 0 | if(nclistlength(l) == 0 || lm->map->active == 0) |
311 | 0 | goto done; /* cannot verify */ |
312 | 0 | for(i=0;i < nclistlength(l); i++) { |
313 | 0 | int match; |
314 | 0 | const char** xp = (const char**)nclistget(l,i); |
315 | | /* Walk map looking for *xp */ |
316 | 0 | for(match=0,m=0;m < lm->map->active; m++) { |
317 | 0 | NC_hentry* e = &lm->map->table[m]; |
318 | 0 | if((e->flags & 1) == 0) continue; |
319 | 0 | if(strcmp(keystr(e),*xp)==0) { |
320 | 0 | if((e->flags & 128) == 128) { |
321 | 0 | fprintf(stderr,"%ld: %s already in map at %ld\n",(unsigned long)i,keystr(e),(unsigned long)m); |
322 | 0 | nerrs++; |
323 | 0 | } |
324 | 0 | match = 1; |
325 | 0 | e->flags += 128; |
326 | 0 | } |
327 | 0 | } |
328 | 0 | if(!match) { |
329 | 0 | fprintf(stderr,"mismatch: %d: %s in vector, not in map\n",(int)i,*xp); |
330 | 0 | nerrs++; |
331 | 0 | } |
332 | 0 | } |
333 | | /* Verify that every element in map in in vector */ |
334 | 0 | for(m=0;m < lm->map->active; m++) { |
335 | 0 | NC_hentry* e = &lm->map->table[m]; |
336 | 0 | if((e->flags & 1) == 0) continue; |
337 | 0 | if((e->flags & 128) == 128) continue; |
338 | | /* We have a hash entry not in the vector */ |
339 | 0 | fprintf(stderr,"mismatch: %d: %s->%lu in hash, not in vector\n",(int)m,keystr(e),(unsigned long)e->data); |
340 | 0 | nerrs++; |
341 | 0 | } |
342 | | /* clear the 'touched' flag */ |
343 | 0 | for(m=0;m < lm->map->active; m++) { |
344 | 0 | NC_hentry* e = &lm->map->table[m]; |
345 | 0 | e->flags &= ~128; |
346 | 0 | } |
347 | |
|
348 | 0 | done: |
349 | 0 | #endif /*NCNOHASH*/ |
350 | 0 | fflush(stderr); |
351 | 0 | return (nerrs > 0 ? 0: 1); |
352 | 0 | } |
353 | | |
354 | | static const char* |
355 | | sortname(NC_SORT sort) |
356 | 0 | { |
357 | 0 | switch(sort) { |
358 | 0 | case NCNAT: return "NCNAT"; |
359 | 0 | case NCVAR: return "NCVAR"; |
360 | 0 | case NCDIM: return "NCDIM"; |
361 | 0 | case NCATT: return "NCATT"; |
362 | 0 | case NCTYP: return "NCTYP"; |
363 | 0 | case NCGRP: return "NCGRP"; |
364 | 0 | default: break; |
365 | 0 | } |
366 | 0 | return "unknown"; |
367 | 0 | } |
368 | | |
369 | | void |
370 | | printindexlist(NClist* lm) |
371 | 0 | { |
372 | 0 | int i; |
373 | 0 | if(lm == NULL) { |
374 | 0 | fprintf(stderr,"<empty>\n"); |
375 | 0 | return; |
376 | 0 | } |
377 | 0 | for(i=0;i<nclistlength(lm);i++) { |
378 | 0 | NC_OBJ* o = (NC_OBJ*)nclistget(lm,i); |
379 | 0 | if(o == NULL) |
380 | 0 | fprintf(stderr,"[%ld] <null>\n",(unsigned long)i); |
381 | 0 | else |
382 | 0 | fprintf(stderr,"[%ld] sort=%s name=|%s| id=%lu\n", |
383 | 0 | (unsigned long)i,sortname(o->sort),o->name,(unsigned long)o->id); |
384 | 0 | } |
385 | 0 | } |
386 | | |
387 | | #ifndef NCNOHASH |
388 | | void |
389 | | printindexmap(NCindex* lm) |
390 | 0 | { |
391 | 0 | if(lm == NULL) { |
392 | 0 | fprintf(stderr,"<empty>\n"); |
393 | 0 | return; |
394 | 0 | } |
395 | 0 | printhashmap(lm->map); |
396 | 0 | } |
397 | | #endif |
398 | | |
399 | | void |
400 | | printindex(NCindex* lm) |
401 | 0 | { |
402 | 0 | if(lm == NULL) { |
403 | 0 | fprintf(stderr,"<empty>\n"); |
404 | 0 | return; |
405 | 0 | } |
406 | 0 | printindexlist(lm->list); |
407 | 0 | #ifndef NCNOHASH |
408 | 0 | printindexmap(lm); |
409 | 0 | #endif |
410 | 0 | } |