reactor-c
C Runtime for Lingua Franca
Loading...
Searching...
No Matches
hashmap.h
Go to the documentation of this file.
15#ifndef K
16#define K void*
17#endif
18#ifndef V
19#define V void*
20#endif
21#ifndef HASH_OF
22#define HASH_OF(key) (size_t) key
23#endif
24#ifndef HASHMAP
25#define HASHMAP(token) hashmap##_##token
26#endif
27
28#include <stddef.h>
29#include <assert.h>
30#include <stdbool.h>
31
33
34typedef struct HASHMAP(entry_t) {
35 K key;
36 V value;
37} HASHMAP(entry_t);
38
39typedef struct HASHMAP(t) {
40 HASHMAP(entry_t) * entries;
41 size_t capacity;
42 size_t num_entries;
43 K nothing;
44} HASHMAP(t);
45
47
54HASHMAP(t) * HASHMAP(new)(size_t capacity, K nothing);
55
57void HASHMAP(free)(HASHMAP(t) * hashmap);
58
60void HASHMAP(put)(HASHMAP(t) * hashmap, K key, V value);
61
66V HASHMAP(get)(HASHMAP(t) * hashmap, K key);
67
69
70static HASHMAP(entry_t) * HASHMAP(get_ideal_address)(HASHMAP(t) * hashmap, K key) {
71 HASHMAP(entry_t)* address = hashmap->entries + (HASH_OF(key) % hashmap->capacity);
72 assert(address >= hashmap->entries);
73 assert(address < hashmap->entries + hashmap->capacity);
74 return address;
75}
76
83static HASHMAP(entry_t) * HASHMAP(get_actual_address)(HASHMAP(t) * hashmap, K key) {
84 HASHMAP(entry_t)* address = HASHMAP(get_ideal_address)(hashmap, key);
85 HASHMAP(entry_t)* upper_limit = hashmap->entries + hashmap->capacity;
86 while ((address->key != hashmap->nothing) & (address->key != key))
87 address++;
88 if (address == upper_limit) {
89 address = hashmap->entries;
90 while ((address->key != hashmap->nothing) & (address->key != key))
91 address++;
92 if (address == upper_limit)
93 return NULL;
94 }
95 assert(address->key == key || address->key == hashmap->nothing);
96 return address;
97}
98
100
101HASHMAP(t) * HASHMAP(new)(size_t capacity, K nothing) {
102 HASHMAP(entry_t)* entries = (HASHMAP(entry_t)*)malloc((capacity + 1) * sizeof(HASHMAP(entry_t)));
104 exit(1);
105 HASHMAP(t)* ret = (HASHMAP(t)*)malloc(sizeof(HASHMAP(t)));
106 if (!ret)
107 exit(1);
108 // The entry at the end is used as a boundary. It will never again be written to.
109 for (size_t i = 0; i < capacity + 1; i++) {
110 entries[i].key = nothing;
111 }
112 ret->entries = entries;
113 ret->capacity = capacity;
114 ret->num_entries = 0;
115 // A second nothing may be required if removal is to be supported and we want to make removal
116 // a constant-time operation.
117 ret->nothing = nothing;
118 return ret;
119}
120
121void HASHMAP(free)(HASHMAP(t) * hashmap) {
122 free(hashmap->entries);
123 free(hashmap);
124}
125
126void HASHMAP(put)(HASHMAP(t) * hashmap, K key, V value) {
127 assert(key != hashmap->nothing);
128 HASHMAP(entry_t)* write_to = HASHMAP(get_actual_address)(hashmap, key);
129 write_to->key = key;
130 write_to->value = value;
131}
132
133V HASHMAP(get)(HASHMAP(t) * hashmap, K key) {
134 assert(key != hashmap->nothing);
135 HASHMAP(entry_t)* read_from = HASHMAP(get_actual_address)(hashmap, key);
136 return read_from->value; // Crash the program if the key cannot be found
137}
ret capacity
Definition hashmap.h:113
ret entries
Definition hashmap.h:112
return ret
Definition hashmap.h:118
void HASHMAP free(HASHMAP(t) *hashmap)
Free all memory used by the given hashmap.
Definition hashmap.h:121
void HASHMAP put(HASHMAP(t) *hashmap, K key, V value)
Associate a value with the given key.
Definition hashmap.h:126
V HASHMAP get(HASHMAP(t) *hashmap, K key)
Get the value associated with the given key. Precondition: The key must be present in the map.
Definition hashmap.h:133
#define HASH_OF(key)
Definition hashmap.h:22
#define K
Defines a generic, non-resizing hashmap data type.
Definition hashmap.h:16
assert(address >=hashmap->entries)
static K key
Definition hashmap.h:70
K nothing
Definition hashmap.h:54
ret num_entries
Definition hashmap.h:114
#define HASHMAP(token)
Definition hashmap.h:25
return address
Definition hashmap.h:74
#define V
Definition hashmap.h:19