Module map
Maps Implemented as Binary Trees.
Maps use the same basic structure as lists, since most of the requirements are similar:
comparison functions (which are like strcmp) and key allocation. The nodes have the same
structure, so structs with LIST_HEADER can be also put into maps, provided the next
field is the key.
Keys are always pointers, but like with string lists, char* pointers are a special case.
If the keys aren’t strings, then the comparison function is simply the less-than operator. This will work fine if simple equality defines a match, as with pointers and integers.
See test-map.c. words.c generates a map of word counts and then sorts the result, giving the ten most common words.
Macros
| FOR_MAP | for-statement for iterating over a map. |
| FOR_MAP_KEYVALUE | for-statement for iterating over typed key/value pairs |
Making New Maps
| map_new_node (strkey) | make a new struct map. |
| map_new_str_ptr () | make a new map with string keys and pointer values. |
| map_new_str_ref () | make a new map with string keys and refcounted values |
| map_new_str_str () | make a new map with string keys and string values. |
| map_new_ptr_ptr () | make a new map with pointer keys and pointer values. |
| map_new_ptr_ref () | make a new map with pointer keys and refcounted values. |
| map_new_ptr_str () | make a new map with pointer keys and string values. |
Insertion, removal and retrieval
| map_clear (m) | clear all entries out of a Map. |
| map_object (obj) | is this object a Map? |
| map_value_data (m, item) | get the data associated with this tree node. |
| map_first (m) | get the root map node. |
| map_put_struct (m, data) | insert a map struct. |
| map_put_structs (param) | insert a number of map structs, ending in NULL. |
| map_put (m, key, data) | insert pointer data using a pointer key. |
| map_put_keyvalues (m, mkv) | insert an array of key/value pairs. |
| map_get (m, key) | get the value associated with a key. |
| map_geti (m, key) | get an integer value from a map. |
| map_puti (m, key, cast) | put an integer value into a map. |
| map_contains (m, key) | does the map contain this key? |
| map_remove (m, key) | remove the key and value from the map. |
| map_delete (m, key) | remove key/value, freeing any allocated memory. |
Iterating over maps
| map_visit (data, node, fun, order) | in-order traversal of a map. |
| map_to_array (m) | Get the key/value pairs of a map as an array. |
| MapKeyValue | convenient struct for initializing maps. |
| MapIter | map iterator type. |
| map_iter_new (m, pkey, pvalue) | create a new map iterator positioned on the mininum node. |
| map_iter_next (iter) | advance the map iterator to the next node. |
Macros
- FOR_MAP
-
for-statement for iterating over a map.
- var MapIter the loop variable
- the m map
- FOR_MAP_KEYVALUE
-
for-statement for iterating over typed key/value pairs
- key K the key variable
- value V the value variable
- the m map
Making New Maps
- map_new_node (strkey)
-
make a new struct map.
Like lists, such maps own the objects.
Parameters:
- strkey bool whether the key is a string or not
Returns:
-
Map *
- map_new_str_ptr ()
- make a new map with string keys and pointer values. Such keys are treated as in string lists; they are allocated and owned by the map; the values are always pointers.
- map_new_str_ref ()
- make a new map with string keys and refcounted values
- map_new_str_str ()
- make a new map with string keys and string values.
- map_new_ptr_ptr ()
- make a new map with pointer keys and pointer values. It’s possible to use integers up to uintptr_t size as well.
- map_new_ptr_ref ()
- make a new map with pointer keys and refcounted values.
- map_new_ptr_str ()
- make a new map with pointer keys and string values.
Insertion, removal and retrieval
- map_clear (m)
-
clear all entries out of a Map.
Parameters:
- m Map *
- map_object (obj)
-
is this object a Map?
Parameters:
- obj void *
Returns:
-
bool
- map_value_data (m, item)
-
get the data associated with this tree node.
if it’s a container, then we return the node’s data,
otherwise the node itself is the data
Parameters:
- m Map *
- item PEntry
Returns:
-
void *
- map_first (m)
-
get the root map node.
You will need this for map_visit.
Parameters:
- m Map *
Returns:
-
PEntry
- map_put_struct (m, data)
-
insert a map struct.
That is, it is ‘derived’ from the MAP_HEADER type.
Parameters:
- m Map *
- data void *
Returns:
-
PEntry
- map_put_structs (param)
-
insert a number of map structs, ending in NULL.
Parameters:
- param Map* … the struct pointers
- map_put (m, key, data)
-
insert pointer data using a pointer key.
String and pointer/integer keys are handled differently.
Parameters:
- m Map *
- key void *
- data void *
Returns:
-
PEntry
- map_put_keyvalues (m, mkv)
-
insert an array of key/value pairs.
Use map_put_structs for struct maps.
Parameters:
- m Map *
- mkv MapKeyValue *
- map_get (m, key)
-
get the value associated with a key.
Parameters:
- m Map *
- key void *
Returns:
-
void *
the value, or NULL if not found, or the value was NULL.
- map_geti (m, key)
-
get an integer value from a map.
Parameters:
- m Map*
- key cast to void*
Returns:
-
int
- map_puti (m, key, cast)
-
put an integer value into a map.
Parameters:
- m Map*
- key cast to void*
- cast value to void*
- map_contains (m, key)
-
does the map contain this key?
Parameters:
- m Map *
- key void *
Returns:
-
bool
trueif the key is found, even if the value was NULL. - map_remove (m, key)
-
remove the key and value from the map.
Parameters:
- m Map *
- key void *
Returns:
-
PEntry
- map_delete (m, key)
-
remove key/value, freeing any allocated memory.
Parameters:
- m Map *
- key void *
Returns:
-
bool
true if the key was found.
Iterating over maps
- map_visit (data, node, fun, order)
-
in-order traversal of a map.
Parameters:
- data void * arbitrary data for callback
- node PEntry where to start (use map_first for all)
- fun MapCallback callback which will receive data and current node
- order int -1 for pre-order, 0 for in-order, +1 for post-order
- map_to_array (m)
-
Get the key/value pairs of a map as an array.
Parameters:
- m Map *
Returns:
- MapKeyValue
-
convenient struct for initializing maps.
Fields:
- key void*
- value void*
- MapIter
-
map iterator type.
Fields:
- key void*
- value void*
- map_iter_new (m, pkey, pvalue)
-
create a new map iterator positioned on the mininum node.
Parameters:
- m Map *
- pkey void *
- pvalue void *
Returns:
- map_iter_next (iter)
-
advance the map iterator to the next node.
Parameters:
- iter MapIter
Returns: