diff options
| author | Josh Rahm <joshuarahm@gmail.com> | 2020-12-06 02:00:43 -0700 |
|---|---|---|
| committer | Josh Rahm <joshuarahm@gmail.com> | 2020-12-06 02:00:43 -0700 |
| commit | 1710871aa1958c2cac38e4b372964ef22032ed4a (patch) | |
| tree | 259bcbae2f5d1c93877c74ed53ff9d2169f1ee15 /include/shared/map.h | |
| parent | d29ea8d7fb8cc6f7c3dda1cbca6266908acd4291 (diff) | |
| download | stm32l4-1710871aa1958c2cac38e4b372964ef22032ed4a.tar.gz stm32l4-1710871aa1958c2cac38e4b372964ef22032ed4a.tar.bz2 stm32l4-1710871aa1958c2cac38e4b372964ef22032ed4a.zip | |
Added header files implementing a basic AVL tree and Map based off it.
These headers take inspiration from the linked list and array list
headers as a way to provide primitive templates in C. This time
they implement an AVL tree and Map template (which uses the AVL tree).
Included are relatively robust tests, though they could be improved.
Diffstat (limited to 'include/shared/map.h')
| -rw-r--r-- | include/shared/map.h | 90 |
1 files changed, 90 insertions, 0 deletions
diff --git a/include/shared/map.h b/include/shared/map.h new file mode 100644 index 0000000..c9ee6b9 --- /dev/null +++ b/include/shared/map.h @@ -0,0 +1,90 @@ +#ifndef _SHARED_MAP_H_ +#define _SHARED_MAP_H_ + +#include "shared/avl_tree.h" +#include "shared/stdmacro.h" + +#define MAP_PASTE_KV(K, V) CONCAT(CONCAT(K, ___), V) +#define map_entry_t(K, V) CONCAT(map_entry_t__, MAP_PASTE_KV(K, V)) +#define map_t(K, V) CONCAT(map_t__, MAP_PASTE_KV(K, V)) + +#define map_new(K, V) CONCAT(map_new__, MAP_PASTE_KV(K, V)) +#define map_free(K, V) CONCAT(map_free__, MAP_PASTE_KV(K, V)) +#define map_put(K, V) CONCAT(map_put__, MAP_PASTE_KV(K, V)) +#define map_get(K, V) CONCAT(map_get__, MAP_PASTE_KV(K, V)) +#define map_erase(K, V) CONCAT(map_erase__, MAP_PASTE_KV(K, V)) +#define _map_compare_(K, V) CONCAT(_map_compare__, MAP_PASTE_KV(K, V)) +#define _map_dtor_(K, V) CONCAT(_map_dtor__, MAP_PASTE_KV(K, V)) + +#define MAP_DECL(K, V) \ + typedef struct { \ + K key; \ + V value; \ + } map_entry_t(K, V); \ + AVL_TREE_DECL(map_entry_t(K, V)); \ + typedef struct { \ + avl_tree_t(map_entry_t(K, V)) * tree; \ + } map_t(K, V); \ + map_t(K, V) * map_new(K, V)(); \ + void map_free(K, V)(map_t(K, V) * map); \ + V* map_get(K, V)(map_t(K, V) * map, K key); \ + V* map_put(K, V)(map_t(K, V) * map, K key, V value); \ + bool map_erase(K, V)(map_t(K, V) * map, K key, V * out); + +#define MAP_IMPL(K, V, CMP, DTOR) \ + static inline int _map_compare_(K, V)( \ + map_entry_t(K, V) e1, map_entry_t(K, V) e2) \ + { \ + return CMP(e1.key, e2.key); \ + } \ + static inline void _map_dtor_(K, V)(map_entry_t(K, V) e1) \ + { \ + DTOR(e1.value); \ + } \ + AVL_TREE_IMPL(map_entry_t(K, V), _map_compare_(K, V), _map_dtor_(K, V)) \ + map_t(K, V) * map_new(K, V)() \ + { \ + map_t(K, V)* ret = ALLOC(sizeof(map_t(K, V))); \ + ret->tree = avl_tree_new(map_entry_t(K, V))(); \ + return ret; \ + } \ + void map_free(K, V)(map_t(K, V) * map) { \ + avl_tree_free(map_entry_t(K, V))(map->tree); \ + FREE(map); \ + }\ + V* map_get(K, V)(map_t(K, V) * map, K key) \ + { \ + map_entry_t(K, V) key_; \ + key_.key = key; \ + map_entry_t(K, V)* entry = \ + avl_tree_find(map_entry_t(K, V))(map->tree, key_); \ + \ + if (!entry) { \ + return NULL; \ + } \ + \ + return &entry->value; \ + } \ + V* map_put(K, V)(map_t(K, V) * map, K key, V val) \ + { \ + map_entry_t(K, V) entry; \ + entry.key = key; \ + entry.value = val; \ + map_entry_t(K, V)* ref = \ + avl_tree_insert(map_entry_t(K, V))(map->tree, entry); \ + return &ref->value; \ + } \ + bool map_erase(K, V)(map_t(K, V) * map, K key, V * out) \ + { \ + map_entry_t(K, V) key_; \ + key_.key = key; \ + \ + map_entry_t(K, V) entry_out; \ + bool ret = avl_tree_erase(map_entry_t(K, V))(map->tree, key_, &entry_out); \ + if (ret) { \ + *out = entry_out.value; \ + } \ + return ret; \ + } + +#endif /* _SHARED_MAP_H_ */ |