cfengine  3.15.4
About: CFEngine is a configuration management system for configuring and maintaining Unix-like computers (using an own high level policy language). Community version.
  Fossies Dox: cfengine-3.15.4.tar.gz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

map.c
Go to the documentation of this file.
1 /*
2  Copyright 2020 Northern.tech AS
3 
4  This file is part of CFEngine 3 - written and maintained by Northern.tech AS.
5 
6  This program is free software; you can redistribute it and/or modify it
7  under the terms of the GNU General Public License as published by the
8  Free Software Foundation; version 3.
9 
10  This program 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
13  GNU General Public License for more details.
14 
15  You should have received a copy of the GNU General Public License
16  along with this program; if not, write to the Free Software
17  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
18 
19  To the extent this program is licensed as part of the Enterprise
20  versions of CFEngine, the applicable Commercial Open Source License
21  (COSL) may apply to this file if you as a licensee so wish it. See
22  included file COSL.txt.
23 */
24 
25 #include <platform.h>
26 #include <map.h>
27 #include <alloc.h>
28 #include <array_map_priv.h>
29 #include <hash_map_priv.h>
30 #include <string_lib.h>
31 
32 /*
33  * This associative array implementation uses array with linear search up to
34  * TINY_LIMIT elements, and then converts into full-fledged hash table with open
35  * addressing.
36  *
37  * There is a lot of small hash tables, both iterating and deleting them as a
38  * hashtable takes a lot of time, especially given associative hash tables are
39  * created and destroyed for each scope entered and left.
40  */
41 
42 /* FIXME: make configurable */
43 #define DEFAULT_HASHMAP_INIT_SIZE 128
44 
45 struct Map_
46 {
48 
49  union
50  {
53  };
54 };
55 
56 static unsigned IdentityHashFn(const void *ptr, ARG_UNUSED unsigned int seed)
57 {
58  return (unsigned)(uintptr_t)ptr;
59 }
60 
61 static bool IdentityEqualFn(const void *p1, const void *p2)
62 {
63  return p1 == p2;
64 }
65 
66 static void NopDestroyFn(ARG_UNUSED void *p1)
67 {
68 }
69 
70 /*
71  * hash_fn is used as a flag "this map uses ArrayMap still". We could have a
72  * separate boolean flag for that, but given we have to store hash_fn somewhere
73  * anyway, let's reuse it this way. Saves us 4-8 bytes for each map.
74  */
75 static bool IsArrayMap(const Map *map)
76 {
77  assert(map != NULL);
78  return map->hash_fn != NULL;
79 }
80 
81 Map *MapNew(MapHashFn hash_fn,
82  MapKeyEqualFn equal_fn,
83  MapDestroyDataFn destroy_key_fn,
84  MapDestroyDataFn destroy_value_fn)
85 {
86  if (hash_fn == NULL)
87  {
88  hash_fn = &IdentityHashFn;
89  }
90 
91  if (equal_fn == NULL)
92  {
93  equal_fn = &IdentityEqualFn;
94  }
95 
96  if (destroy_key_fn == NULL)
97  {
98  destroy_key_fn = &NopDestroyFn;
99  }
100 
101  if (destroy_value_fn == NULL)
102  {
103  destroy_value_fn = &NopDestroyFn;
104  }
105 
106  Map *map = xcalloc(1, sizeof(Map));
107  map->arraymap = ArrayMapNew(equal_fn, destroy_key_fn, destroy_value_fn);
108  map->hash_fn = hash_fn;
109  return map;
110 }
111 
112 size_t MapSize(const Map *map)
113 {
114  assert(map != NULL);
115 
116  if (IsArrayMap(map))
117  {
118  return map->arraymap->size;
119  }
120  else
121  {
122  MapIterator i = MapIteratorInit((Map*)map);
123  size_t size = 0;
124 
125  while (MapIteratorNext(&i))
126  {
127  size++;
128  }
129 
130  return size;
131  }
132 }
133 
134 static void ConvertToHashMap(Map *map)
135 {
136  assert(map != NULL);
137 
138  HashMap *hashmap = HashMapNew(map->hash_fn,
139  map->arraymap->equal_fn,
140  map->arraymap->destroy_key_fn,
143 
144  /* We have to use internals of ArrayMap here, as we don't want to
145  destroy the values in ArrayMapDestroy */
146 
147  for (int i = 0; i < map->arraymap->size; ++i)
148  {
149  HashMapInsert(hashmap,
150  map->arraymap->values[i].key,
151  map->arraymap->values[i].value);
152  }
153 
154  free(map->arraymap->values);
155  free(map->arraymap);
156 
157  map->hashmap = hashmap;
158  map->hash_fn = NULL;
159 }
160 
161 bool MapInsert(Map *map, void *key, void *value)
162 {
163  assert(map != NULL);
164  /* MapGet() is not capable of handling NULL values. */
165  assert(key != NULL);
166  assert(value != NULL);
167 
168  if (IsArrayMap(map))
169  {
170  int ret = ArrayMapInsert(map->arraymap, key, value);
171  if (ret != 0)
172  {
173  /* Return true if value was replaced, false if key-value was
174  * inserted as new. */
175  return (ret == 1);
176  }
177 
178  /* Does not fit in ArrayMap, must convert to HashMap. */
179  ConvertToHashMap(map);
180  }
181 
182  return HashMapInsert(map->hashmap, key, value);
183 }
184 
185 /*
186  * The best we can get out of C type system. Caller should make sure that if
187  * argument is const, it does not modify the result.
188  */
189 static MapKeyValue *MapGetRaw(const Map *map, const void *key)
190 {
191  assert(map != NULL);
192 
193  if (IsArrayMap(map))
194  {
195  return ArrayMapGet((ArrayMap *)map->arraymap, key);
196  }
197  else
198  {
199  return HashMapGet((HashMap *)map->hashmap, key);
200  }
201 }
202 
203 bool MapHasKey(const Map *map, const void *key)
204 {
205  assert(map != NULL);
206  assert(key != NULL);
207  return MapGetRaw(map, key) != NULL;
208 }
209 
210 /* NULL return means not found, or value was NULL! TODO fix, it should only
211  * mean one thing. I added the assert() to make sure we never store NULL
212  * values. */
213 void *MapGet(Map *map, const void *key)
214 {
215  assert(map != NULL);
216  MapKeyValue *kv = MapGetRaw(map, key);
217  if (kv != NULL)
218  {
219  assert(kv->value != NULL);
220  return kv->value;
221  }
222 
223  return NULL;
224 }
225 
226 bool MapRemove(Map *map, const void *key)
227 {
228  assert(map != NULL);
229 
230  if (IsArrayMap(map))
231  {
232  return ArrayMapRemove(map->arraymap, key);
233  }
234  else
235  {
236  return HashMapRemove(map->hashmap, key);
237  }
238 }
239 
240 void MapClear(Map *map)
241 {
242  assert(map != NULL);
243 
244  if (IsArrayMap(map))
245  {
246  ArrayMapClear(map->arraymap);
247  }
248  else
249  {
250  HashMapClear(map->hashmap);
251  }
252 }
253 
254 void MapSoftDestroy(Map *map)
255 {
256  if (map)
257  {
258  if (IsArrayMap(map))
259  {
261  }
262  else
263  {
265  }
266  free(map);
267  }
268 }
269 
270 void MapDestroy(Map *map)
271 {
272  if (map)
273  {
274  if (IsArrayMap(map))
275  {
277  }
278  else
279  {
280  HashMapDestroy(map->hashmap);
281  }
282  free(map);
283  }
284 }
285 
286 bool MapContainsSameKeys(const Map *map1, const Map *map2)
287 {
288  assert(map1 != NULL);
289  assert(map2 != NULL);
290 
291  MapIterator i = MapIteratorInit((Map *)map1);
292  MapKeyValue *item;
293  size_t count = 0;
294  while ((item = MapIteratorNext(&i)))
295  {
296  count++;
297  if (!MapHasKey(map2, item->key))
298  {
299  return false;
300  }
301  }
302  return (count == MapSize(map2));
303 }
304 
305 void MapPrintStats(const Map *map, FILE *f)
306 {
307  assert(map != NULL);
308 
309  fprintf(f, "================ Map statistics ================\n");
310 
311  if (IsArrayMap(map))
312  {
313  fprintf(f, "Map is too small, fits in a small array.\n");
314  }
315  else
316  {
317  HashMapPrintStats(map->hashmap, f);
318  }
319 
320  fprintf(f, "================================================\n");
321 }
322 
323 /******************************************************************************/
324 
326 {
327  assert(map != NULL);
328 
329  MapIterator i;
330  if (IsArrayMap(map))
331  {
332  i.is_array = true;
334  }
335  else
336  {
337  i.is_array = false;
339  }
340  return i;
341 }
342 
344 {
345  if (i->is_array)
346  {
348  }
349  else
350  {
351  return HashMapIteratorNext(&i->hashmap_iter);
352  }
353 }
354 
355 TYPED_MAP_DEFINE(String, char *, char *,
358  &free,
void * xcalloc(size_t nmemb, size_t size)
Definition: alloc-mini.c:51
void ArrayMapSoftDestroy(ArrayMap *map)
Definition: array_map.c:111
ArrayMapIterator ArrayMapIteratorInit(ArrayMap *map)
Definition: array_map.c:138
void ArrayMapDestroy(ArrayMap *map)
Definition: array_map.c:126
int ArrayMapInsert(ArrayMap *map, void *key, void *value)
Definition: array_map.c:44
bool ArrayMapRemove(ArrayMap *map, const void *key)
Definition: array_map.c:70
MapKeyValue * ArrayMapGet(const ArrayMap *map, const void *key)
Definition: array_map.c:89
MapKeyValue * ArrayMapIteratorNext(ArrayMapIterator *i)
Definition: array_map.c:143
ArrayMap * ArrayMapNew(MapKeyEqualFn equal_fn, MapDestroyDataFn destroy_key_fn, MapDestroyDataFn destroy_value_fn)
Definition: array_map.c:32
void ArrayMapClear(ArrayMap *map)
Definition: array_map.c:101
#define ARG_UNUSED
Definition: cf-net.c:47
void free(void *)
#define NULL
Definition: getopt1.c:56
HashMapIterator HashMapIteratorInit(HashMap *map)
Definition: hash_map.c:308
void HashMapSoftDestroy(HashMap *map)
Definition: hash_map.c:231
void HashMapClear(HashMap *map)
Definition: hash_map.c:218
MapKeyValue * HashMapGet(const HashMap *map, const void *key)
Definition: hash_map.c:175
MapKeyValue * HashMapIteratorNext(HashMapIterator *i)
Definition: hash_map.c:313
bool HashMapRemove(HashMap *map, const void *key)
Definition: hash_map.c:142
void HashMapDestroy(HashMap *map)
Definition: hash_map.c:249
bool HashMapInsert(HashMap *map, void *key, void *value)
Definition: hash_map.c:109
HashMap * HashMapNew(MapHashFn hash_fn, MapKeyEqualFn equal_fn, MapDestroyDataFn destroy_key_fn, MapDestroyDataFn destroy_value_fn, size_t init_size)
Definition: hash_map.c:35
void HashMapPrintStats(const HashMap *hmap, FILE *f)
Definition: hash_map.c:259
MapIterator MapIteratorInit(Map *map)
Definition: map.c:325
static void ConvertToHashMap(Map *map)
Definition: map.c:134
bool MapRemove(Map *map, const void *key)
Definition: map.c:226
void MapPrintStats(const Map *map, FILE *f)
Definition: map.c:305
static MapKeyValue * MapGetRaw(const Map *map, const void *key)
Definition: map.c:189
bool MapContainsSameKeys(const Map *map1, const Map *map2)
Definition: map.c:286
Map * MapNew(MapHashFn hash_fn, MapKeyEqualFn equal_fn, MapDestroyDataFn destroy_key_fn, MapDestroyDataFn destroy_value_fn)
Definition: map.c:81
void MapSoftDestroy(Map *map)
Definition: map.c:254
size_t MapSize(const Map *map)
Definition: map.c:112
static bool IsArrayMap(const Map *map)
Definition: map.c:75
static void NopDestroyFn(void *p1)
Definition: map.c:66
#define DEFAULT_HASHMAP_INIT_SIZE
Definition: map.c:43
static unsigned IdentityHashFn(const void *ptr, unsigned int seed)
Definition: map.c:56
static bool IdentityEqualFn(const void *p1, const void *p2)
Definition: map.c:61
bool MapInsert(Map *map, void *key, void *value)
Definition: map.c:161
void * MapGet(Map *map, const void *key)
Definition: map.c:213
MapKeyValue * MapIteratorNext(MapIterator *i)
Definition: map.c:343
void MapClear(Map *map)
Definition: map.c:240
bool MapHasKey(const Map *map, const void *key)
Definition: map.c:203
void MapDestroy(Map *map)
Definition: map.c:270
#define TYPED_MAP_DEFINE(Prefix, KeyType, ValueType, hash_fn, equal_fn, destroy_key_fn, destroy_value_fn)
Definition: map.h:134
void(* MapDestroyDataFn)(void *key)
Definition: map_common.h:41
bool(* MapKeyEqualFn)(const void *key1, const void *key2)
Definition: map_common.h:40
unsigned int(* MapHashFn)(const void *p, unsigned int seed)
Definition: map_common.h:39
bool StringEqual_untyped(const void *a, const void *b)
Definition: string_lib.c:306
unsigned int StringHash_untyped(const void *str, unsigned int seed)
Definition: string_lib.c:114
MapDestroyDataFn destroy_value_fn
MapKeyValue * values
short size
MapKeyEqualFn equal_fn
MapDestroyDataFn destroy_key_fn
ArrayMapIterator arraymap_iter
Definition: map.h:83
bool is_array
Definition: map.h:80
HashMapIterator hashmap_iter
Definition: map.h:84
void * key
Definition: map_common.h:35
void * value
Definition: map_common.h:36
Definition: map.c:46
HashMap * hashmap
Definition: map.c:52
ArrayMap * arraymap
Definition: map.c:51
MapHashFn hash_fn
Definition: map.c:47