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);
74 return address;
75}
76
85 HASHMAP(entry_t)* upper_limit = hashmap->entries + hashmap->capacity;
86 while ((address->key != hashmap->nothing) & (address->key != key)) address++;
88 address = hashmap->entries;
89 while ((address->key != hashmap->nothing) & (address->key != key)) address++;
90 if (address == upper_limit) return NULL;
91 }
92 assert(address->key == key || address->key == hashmap->nothing);
93 return address;
94}
95
97
98HASHMAP(t)* HASHMAP(new)(size_t capacity, K nothing) {
100 (capacity + 1) * sizeof(HASHMAP(entry_t))
101 );
102 if (!entries) exit(1);
103 HASHMAP(t)* ret = (HASHMAP(t)*) malloc(sizeof(HASHMAP(t)));
104 if (!ret) exit(1);
105 // The entry at the end is used as a boundary. It will never again be written to.
106 for (size_t i = 0; i < capacity + 1; i++) {
107 entries[i].key = nothing;
108 }
109 ret->entries = entries;
110 ret->capacity = capacity;
111 ret->num_entries = 0;
112 // A second nothing may be required if removal is to be supported and we want to make removal
113 // a constant-time operation.
114 ret->nothing = nothing;
115 return ret;
116}
117
119 free(hashmap->entries);
120 free(hashmap);
121}
122
123void HASHMAP(put)(HASHMAP(t)* hashmap, K key, V value) {
124 assert(key != hashmap->nothing);
125 assert(key >= 0);
127 write_to->key = key;
128 write_to->value = value;
129}
130
132 assert(key != hashmap->nothing);
134 return read_from->value; // Crash the program if the key cannot be found
135}
ret capacity
Definition hashmap.h:110
ret entries
Definition hashmap.h:109
return ret
Definition hashmap.h:115
void HASHMAP free(HASHMAP(t) *hashmap)
Free all memory used by the given hashmap.
Definition hashmap.h:118
void HASHMAP put(HASHMAP(t) *hashmap, K key, V value)
Associate a value with the given key.
Definition hashmap.h:123
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:131
#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:111
#define HASHMAP(token)
Definition hashmap.h:25
return address
Definition hashmap.h:74
#define V
Definition hashmap.h:19