Class Map.

Inherits PatriciaTree

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).

Map::Map()

Creates a new empty Map.

Reimplements PatriciaTree::PatriciaTree().

void Map::clear()

Removes everything in the map.

Reimplements PatriciaTree::clear().

bool Map::contains( uint i )

Returns true if this map has an object at index i, and false if not.

uint Map::count() const

Returns the number of objects in the Map.

Reimplements PatriciaTree::count().

T * Map::find( uint i )

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.

void Map::insert( uint i, T * r )

Inserts r into the Map at index i. This may cause memory allocation as the map builds intermediate tree nodes.

static uint Map::k( uint i )

Returns i with the most significant byte first (AKA network byte order), useful for PatriciaTree.

static uint Map::l()

Returns the number of bits in a uint.

void Map::remove( uint i )

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.