Map === Tucker Evans v0.6, 2020-07-06 A basic map implemented in an AVL tree. NOTE: Keys are passed as void pointers and their data is not copied (this should be handled by the user), they should not be freed without clearing the map. NOTE: There is currently no way to distinquish between a failed retrieval (pop, index, back, etc.) and returning a NULL value. Keep this in mind if you plan on storing NULL values in the vector, there are plans to fix this in the future. Types ---- The following types are defined in the header file: [[map]] +map+ ~~~~~ This structure holds all internal information regarding a map. All functions (except constructors) expect a pointer to this struct as their first parameter. [[cmp_func]] +cmp_func+ ~~~~~~~~~~~ This is a pointer to a function that to compare keys from pointers. This typedef is provided to cast comparison functions as a map expects the comparison function to take void* as its parameters. Functions --------- [[map_new]] +map_new(cmp_func cmp)+ ~~~~~~~~~~~~~~~~~~~~~~~ Constructs an empty map. +cmp+ should be a function that takes two pointers (+lhs+, +rhs+)to your value type and returns (int) a negative value if +lhs+ is less than +rhs+, zero if +lhs+ is equal to +rhs+, and positive value if +lhs+ is greater than +rhs+. Examples ^^^^^^^^ [source,c] ---- #include "map.h" #include map *dict = map_new((cmp_func) strcmp); ---- [[map_size]] +map_size(map *self)+ ~~~~~~~~~~~~~~~~~~~~~ Returns the number of key, value pairs stored in map +self+. Examples ^^^^^^^^ [source,c] ---- #include "map.h" #include map *dict = map_new((cmp_func) strcmp); assert(map_size(dict) == 0); map_insert(dict, "ONE", NULL); assert(map_size(dict) == 1); ---- [[map_insert]] +int map_insert(map *self, void *key, void *value)+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Inserts a new item +value+ for +key+ into +self+ This returns an int indicating a successful insertion; providing a NULL +self+ or a key that is already in +self+ will return -1 otherwise 0 is returned. Examples ^^^^^^^^ [source,c] ---- #include "map.h" #include #include map *dict = map_new((cmp_func) strcmp); if (map_insert(dict, "ONE", NULL) < 0) printf("Failed to insert {\"ONE\": NULL}\n"); else assert(map_size(dict) == 1); ---- [[map_remove]] +void* map_remove(map *self, void *key)+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Removes (and returns) the element at position +key+. The key and value are not freed. Examples ^^^^^^^^ [source,c] ---- #include "map.h" #include map *dict = map_new((cmp_func) strcmp); map_insert(dict, "ONE", strdup("VALUE")); map_insert(dict, "TWO", strdup("VALUE")); map_insert(dict, "THREE", strdup("VALUE")); map_insert(dict, "FOUR", strdup("VALUE")); map_insert(dict, "FIVE", strdup("VALUE")); map_insert(dict, "SIX", strdup("VALUE")); char* tmp = map_remove(dict, "FOUR"); assert(strcmp(tmp, "FOUR") == 0); free(tmp); ---- [[map_swap]] +void map_swap(map *self, void *i, void *j)+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Swaps values at keys +i+ and +j+, does nothing if +i+ or +j+ are invalid keys. Examples ^^^^^^^^ [source,c] ---- #include "map.h" #include char *str1 = "ONE"; char *str2 = "TWO"; map *dict = map_new((cmp_func) strcmp); map_insert(dict, str1, strdup(str2)); map_insert(dict, str2, strdup(str3)); map_swap(dict, str1, str2); assert(strcmp(str1, map_index(dict, str1)) == 0); assert(strcmp(str2, map_index(dict, str2)) == 0); ---- [[map_set_val]] +void* map_set_val(map *self, void *key, void *val)+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ This replaces the value stored at +key+ (or equivalent) with +val+, the value that is overwritten is return so the user can free it. Examples ^^^^^^^^ [source,c] ---- #include "map.h" #include map *dict = map_new((cmp_func) strcmp); map_insert(dict, strdup("ONE"), strdup("VALUE")); free(map_set_val(dict, "ONE", "NEW_VALUE")); ---- [[map_check_key_ptr]] +int map_check_key_ptr(map *self, void *key)+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ This is used to check the key pointer for equivalent keys. It is provided to ease memory management, in combination with <>. Examples ^^^^^^^^ [source,c] ---- #include "map.h" #include char *eq_key2 map *dict = map_new((cmp_func) strcmp); map_insert(dict, strdup("ONE"), NULL); eq_key2 = strdup("ONE"); /*Want to free key1 for some reason*/ if (!map_check_key_ptr(dict, eq_key2)) { free(map_set_key(dict, eq_key2)); } ---- [[map_set_key]] +void* map_set_key(map *self, void *key)+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ This replaces an equivalent key with the one passed in, the key that is overwritten is return so the user can free it. Examples ^^^^^^^^ [source,c] ---- #include "map.h" #include map *dict = map_new((cmp_func) strcmp); map_insert(dict, strdup("ONE"), NULL); eq_key2 = strdup("ONE"); /*Want to free key1 for some reason*/ if (!map_check_key_ptr(dict, eq_key2)) { free(map_set_key(dict, eq_key2)); } ---- [[map_index]] +void* map_index(map *self, void *key)+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Returns the value associated with +key+ (or equivalent). Examples ^^^^^^^^ [source,c] ---- #include "map.h" #include map *dict = map_new((cmp_func) strcmp, sizeof(char*)); map_insert(dict, strdup("ONE"), "VALUE"); assert(strcmp(map_index(dict, "ONE"), "VALUE") == 0); ---- [[map_clear]] +void map_clear(map *self)+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~ Free all elements within dict +self+, and sets dict to empty (size 0). NOTE: Does not free all internal memory of +self+ or +self+ itself, if this is desired <> should be called immediatly after this. Examples ^^^^^^^^ [source,c] ---- #include "map.h" #include char *str1 = "ONE"; char *str2 = "TWO"; map *dict = map_new(); map_insert(dict, str_dup(str1), NULL); map_insert(dict, str_dup(str2), NULL); map_clear(dict); assert(map_size(dict) == 0); map_free(dict); ---- [[map_free]] +void map_free(map *self)+ ~~~~~~~~~~~~~~~~~~~~~~~~~~ Frees all internal memory and +self+. NOTE: All item pointers are still valid after a call to <>, <> should be called before if they are no longer needed to avoid memory leaks. Examples ^^^^^^^^ [source,c] ---- #include "map.h" map *dict = map_new(); map_free(dict); ----