path: root/collections/map/map.adoc

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 <string.h>

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 <string.h>

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 <string.h>
#include <stdio.h>

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 <string.h>

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 <string.h>

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 <string.h>

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
<<map_set_key,+map_set_key()+>>.

Examples
^^^^^^^^
[source,c]
----
#include "map.h"
#include <string.h>

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 <string.h>

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 <string.h>

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 <<map_free,+map_free()+>> should be called immediatly after this.

Examples
^^^^^^^^
[source,c]
----
#include "map.h"
#include <string.h>

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
<<map_free,+map_free()+>>, <<map_clear,+map_clear()+>> 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);
----