The Map template maps from uint to a pointer.
It is intended to be used for cached database rows: The user supplies the row's unique key and the Map supplies a pointer to the cached object.
The implementation is optimized for scattered clusters of values: If 1234 is in the map, other integers nearby are assumed to be there, too. When this is true, the memory overhead is small and speed high. When not, speed remains high.
The actual implementation is a number of arrays. The key is chopped into n-bit chunks and each chunk is used to index into a table. The most significant few bits index into the root table.
n is an implementation constant, not adjustable per Map. At the moment it's 6 (and the root table is mostly empty).
Creates a new empty Map.
Removes everything in the map.
Returns true if this map has an object at index i, and false if not.
Returns the number of objects in the Map.
Returns a pointer to the object at index i, or a null pointer if there is no such object. This function does not allocate any memory.
Inserts r into the Map at index i. This may cause memory allocation as the map builds intermediate tree nodes.
Returns i with the most significant byte first (AKA network byte order), useful for PatriciaTree.
Returns the number of bits in a uint.
Removes the object at index i from the Map. This may cause memory allocation, as it's a thin wrapper around insert( i, 0 ).
This web page based on source code belonging to The Archiveopteryx Developers. All rights reserved.