ucx
UAP Common Extensions
map.h
Go to the documentation of this file.
1 /*
2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3  *
4  * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions are met:
8  *
9  * 1. Redistributions of source code must retain the above copyright
10  * notice, this list of conditions and the following disclaimer.
11  *
12  * 2. Redistributions in binary form must reproduce the above copyright
13  * notice, this list of conditions and the following disclaimer in the
14  * documentation and/or other materials provided with the distribution.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26  * POSSIBILITY OF SUCH DAMAGE.
27  */
28 
41 #ifndef UCX_MAP_H
42 #define UCX_MAP_H
43 
44 #include "ucx.h"
45 #include "string.h"
46 #include "allocator.h"
47 #include <stdio.h>
48 
49 #ifdef __cplusplus
50 extern "C" {
51 #endif
52 
65 #define UCX_MAP_FOREACH(key,value,iter) \
66  for(UcxKey key;ucx_map_iter_next(&iter,&key, (void**)&value);)
67 
69 typedef struct UcxMap UcxMap;
70 
72 typedef struct UcxKey UcxKey;
73 
76 
79 
81 struct UcxMap {
87  size_t size;
89  size_t count;
90 };
91 
93 struct UcxKey {
95  const void *data;
97  size_t len;
99  int hash;
100 };
101 
103 struct UcxMapKey {
105  void *data;
107  size_t len;
109  int hash;
110 };
111 
115  void *data;
116 
119 
121  struct UcxMapKey key;
122 };
123 
127  UcxMap const *map;
128 
131 
138  size_t index;
139 };
140 
146 UcxMap *ucx_map_new(size_t size);
147 
155 
165 void ucx_map_free(UcxMap *map);
166 
187 
197 void ucx_map_clear(UcxMap *map);
198 
199 
214 int ucx_map_copy(UcxMap const *from, UcxMap *to, copy_func fnc, void *data);
215 
230 UcxMap *ucx_map_clone(UcxMap const *map, copy_func fnc, void *data);
231 
248  UcxMap const *map, copy_func fnc, void *data);
249 
267 
276 int ucx_map_put(UcxMap *map, UcxKey key, void *value);
277 
285 void* ucx_map_get(UcxMap const *map, UcxKey key);
286 
294 void* ucx_map_remove(UcxMap *map, UcxKey key);
295 
304 #define ucx_map_sstr_put(map, key, value) \
305  ucx_map_put(map, ucx_key(key.ptr, key.length), (void*)value)
306 
315 #define ucx_map_cstr_put(map, key, value) \
316  ucx_map_put(map, ucx_key(key, strlen(key)), (void*)value)
317 
326 #define ucx_map_int_put(map, key, value) \
327  ucx_map_put(map, ucx_key(&key, sizeof(key)), (void*)value)
328 
336 #define ucx_map_sstr_get(map, key) \
337  ucx_map_get(map, ucx_key(key.ptr, key.length))
338 
346 #define ucx_map_cstr_get(map, key) \
347  ucx_map_get(map, ucx_key(key, strlen(key)))
348 
356 #define ucx_map_int_get(map, key) \
357  ucx_map_get(map, ucx_key(&key, sizeof(int)))
358 
366 #define ucx_map_sstr_remove(map, key) \
367  ucx_map_remove(map, ucx_key(key.ptr, key.length))
368 
376 #define ucx_map_cstr_remove(map, key) \
377  ucx_map_remove(map, ucx_key(key, strlen(key)))
378 
386 #define ucx_map_int_remove(map, key) \
387  ucx_map_remove(map, ucx_key(&key, sizeof(key)))
388 
399 UcxKey ucx_key(const void *data, size_t len);
400 
408 int ucx_hash(const char *data, size_t len);
409 
428 
445 int ucx_map_iter_next(UcxMapIterator *iterator, UcxKey *key, void **value);
446 
459 UcxMap* ucx_map_union(const UcxMap *first, const UcxMap *second,
460  copy_func cpfnc, void* cpdata);
461 
476  const UcxMap *first, const UcxMap *second,
477  copy_func cpfnc, void* cpdata);
478 
491 UcxMap* ucx_map_intersection(const UcxMap *first, const UcxMap *second,
492  copy_func cpfnc, void* cpdata);
493 
508  const UcxMap *first, const UcxMap *second,
509  copy_func cpfnc, void* cpdata);
510 
523 UcxMap* ucx_map_difference(const UcxMap *first, const UcxMap *second,
524  copy_func cpfnc, void* cpdata);
525 
540  const UcxMap *first, const UcxMap *second,
541  copy_func cpfnc, void* cpdata);
542 
543 
544 #ifdef __cplusplus
545 }
546 #endif
547 
548 #endif /* UCX_MAP_H */
549 
void *(* copy_func)(const void *, void *)
Function pointer to a copy function.
Definition: ucx.h:106
size_t index
The current index of the element list array.
Definition: map.h:138
size_t len
The length of the key data.
Definition: map.h:107
UcxMap * ucx_map_difference_a(UcxAllocator *allocator, const UcxMap *first, const UcxMap *second, copy_func cpfnc, void *cpdata)
Returns the difference of two maps.
Definition: map.c:386
Bounded string implementation.
Main UCX Header providing most common definitions.
int ucx_hash(const char *data, size_t len)
Computes a murmur hash-2.
Definition: map.c:260
int hash
The hash value of the key data.
Definition: map.h:109
void ucx_map_free_content(UcxMap *map, ucx_destructor destr)
Frees the contents of a hash map.
Definition: map.c:85
void * ucx_map_get(UcxMap const *map, UcxKey key)
Retrieves a value by using a key.
Definition: map.c:243
UcxMapIterator ucx_map_iterator(UcxMap const *map)
Creates an iterator for a map.
Definition: map.c:302
UcxMap * ucx_map_union(const UcxMap *first, const UcxMap *second, copy_func cpfnc, void *cpdata)
Returns the union of two maps.
Definition: map.c:343
int hash
A cache for the hash value of the key data.
Definition: map.h:99
void ucx_map_clear(UcxMap *map)
Clears a hash map.
Definition: map.c:97
UcxMap * ucx_map_difference(const UcxMap *first, const UcxMap *second, copy_func cpfnc, void *cpdata)
Returns the difference of two maps.
Definition: map.c:380
Structure for an element of a UcxMap.
Definition: map.h:113
Structure to publicly denote a key of a UcxMap.
Definition: map.h:93
size_t count
The count of elements currently stored in this map.
Definition: map.h:89
UcxMapElement * next
A pointer to the next element in the current list.
Definition: map.h:118
UcxMap * ucx_map_union_a(UcxAllocator *allocator, const UcxMap *first, const UcxMap *second, copy_func cpfnc, void *cpdata)
Returns the union of two maps.
Definition: map.c:349
UcxMap const * map
The map to iterate over.
Definition: map.h:127
Structure for an iterator over a UcxMap.
Definition: map.h:125
void * data
The value data.
Definition: map.h:115
int ucx_map_copy(UcxMap const *from, UcxMap *to, copy_func fnc, void *data)
Copies contents from a map to another map using a copy function.
Definition: map.c:106
UCX allocator data structure containing memory management functions.
Definition: allocator.h:88
UcxKey ucx_key(const void *data, size_t len)
Creates a UcxKey based on the given data.
Definition: map.c:251
UcxMap * ucx_map_new(size_t size)
Creates a new hash map with the specified size.
Definition: map.c:34
UcxMapElement * cur
The current map element.
Definition: map.h:130
UcxMap * ucx_map_new_a(UcxAllocator *allocator, size_t size)
Creates a new hash map with the specified size using a UcxAllocator.
Definition: map.c:38
UcxAllocator * allocator
An allocator that is used for the map elements.
Definition: map.h:83
Internal structure for a key of a UcxMap.
Definition: map.h:103
int ucx_map_put(UcxMap *map, UcxKey key, void *value)
Puts a key/value-pair into the map.
Definition: map.c:158
UcxMap * ucx_map_clone_a(UcxAllocator *allocator, UcxMap const *map, copy_func fnc, void *data)
Clones the map and rehashes if necessary.
Definition: map.c:121
size_t size
The size of the map is the length of the element list array.
Definition: map.h:87
int ucx_map_iter_next(UcxMapIterator *iterator, UcxKey *key, void **value)
Proceeds to the next element of the map (if any).
Definition: map.c:310
const void * data
The key data.
Definition: map.h:95
Allocator for custom memory management.
Structure for the UCX map.
Definition: map.h:81
void * ucx_map_remove(UcxMap *map, UcxKey key)
Removes a key/value-pair from the map by using the key.
Definition: map.c:247
size_t len
The length of the key data.
Definition: map.h:97
UcxMap * ucx_map_intersection(const UcxMap *first, const UcxMap *second, copy_func cpfnc, void *cpdata)
Returns the intersection of two maps.
Definition: map.c:357
int ucx_map_rehash(UcxMap *map)
Increases size of the hash map, if necessary.
Definition: map.c:132
void ucx_map_free(UcxMap *map)
Frees a hash map.
Definition: map.c:79
UcxMap * ucx_map_clone(UcxMap const *map, copy_func fnc, void *data)
Clones the map and rehashes if necessary.
Definition: map.c:117
UcxMapElement ** map
The array of map element lists.
Definition: map.h:85
UcxMap * ucx_map_intersection_a(UcxAllocator *allocator, const UcxMap *first, const UcxMap *second, copy_func cpfnc, void *cpdata)
Returns the intersection of two maps.
Definition: map.c:363
void * data
The key data.
Definition: map.h:105
void(* ucx_destructor)(void *)
A function pointer to a destructor function.
Definition: ucx.h:72