Integer Maps

Integer Maps map unsigned 32-bit integer keys to arbitrary pointers. They were added in 1.8.3p7. They're used in a number of places; for example, in queue entry process id related code (src/cque.c), and in looking up the structure representing a connected socket via its descriptor number (src/bsd.c).

API

To use integer maps, you have to #include "intmap.h". The type of an integer map is a intmap *. The type is opaque; you cannot directly access elements of the structure.

Basic functions

intmap * im_new(void)

Return a new, empty intmap structure.

bool im_insert(intmap *, uint32_t, void *)

Insert a new key,value pair into the map. Returns true on success, false on failure (Usually because of a duplicate key).

void * im_find(intmap *, uint32_t)

Return the pointer associated with the given key, or NULL if the key isn't present.

bool im_exists(intmap *, uint32_t)

Returns true if a key is present in the map.

int64_t im_count(intmap *)

Returns the number of keys stored in the map.

bool im_delete(intmap *, uint32_t)

Removes a mapping from the map. Returns true on success, false on failure (If the key didn't exist.) Deletion of memory allocated in the data pointer is left up to the user.

Less common functions

void im_destroy(intmap *)

Delete an entire intmap. The intmap passed to this function becomes unusable. Memory allocated in the data pointers must be freed by the user.

void im_dump_graph(intmap *, const char *)

Dump a representation of the map to the given filename. The dump is in the dot language, which can be rendered by tools in the graphviz package, specifically dot(1). Useful for debugging the internal tree structure.

Implementation

Integer maps use a slight modification of radix trees (AKA patricia trees), a self-balancing binary tree where branching is based on the status of particular bits in the key.