template< class Key, class Item > class RED::Map

Binary tree for template scalars. Similar to the std::map class. More...

#include <REDSTL.h>

Inherits: Object.

Public functions:

Map ( )
Map ( const Map< Key, Item > & iSource )
virtual ~Map ( )
virtual void *As ( const RED::CID & iCID )
virtual const void *As ( const RED::CID & iCID ) const
template< class T_As > const T_As *As ( ) const
template< class T_As > T_As *As ( )
voidbegin ( ) const
voidclear ( )
Item &current ( )
const Item &current ( ) const
Key &current_key ( )
const Key &current_key ( ) const
boolempty ( ) const
boolend ( ) const
voiderase ( const Key & iKey )
voiderase_current ( )
const Item *find ( const Key & iKey ) const
Item *find ( const Key & iKey )
RED_RCinsert ( const Key & iKey, const Item & iValue )
RED_RCinsert ( bool & oInsert, const Key & iKey, const Item & iValue )
boolmapcheck ( ) const
void *mt_begin ( ) const
Item &mt_current ( void * iParsingAddress )
const Item &mt_current ( void * iParsingAddress ) const
Key &mt_current_key ( void * iParsingAddress )
const Key &mt_current_key ( void * iParsingAddress ) const
boolmt_end ( void * iParsingAddress ) const
voidmt_erase_current ( void *& oParsingAddress )
const Item *mt_find ( void *& oParsingAddress, const Key & iKey ) const
Item *mt_find ( void *& oParsingAddress, const Key & iKey )
boolmt_next ( void *& ioParsingAddress ) const
boolnext ( ) const
RED_RCoperator= ( const Map< Key, Item > & iSource )
voidrestore_parsing ( ) const
voidsave_parsing ( ) const
RED::uint64size ( ) const

Public static functions:

static RED::CIDGetClassID ( )

Protected functions:

RED_RCAllocate ( )
voidrotate_left ( Cell * iCell )
voidrotate_right ( Cell * iCell )

Protected variables:

RED::Vector< RED::Vector< Cell > >_chunk
Cell *_current
Cell *_root
Cell *_saved_current
RED::uint64_size

Protected enumerations:

enumMapColor { RED =  1, BLACK =  0 }

Detailed description:

Binary tree for template scalars. Similar to the std::map class.

The Map implements a binary search tree. The algorithm used is based on the red-black tree balance method to ensure that the entire tree remains properly balanced all the times.

Red-black tree rules are:

1) A tree node is either RED or BLACK. 2) The root node is BLACK. 3) All leaves are BLACK (we assume that every item with data in our tree is a node and has NULL leaves that are considered black). 4) Both children of a RED node are BLACK. 5) All paths from any given node to its leaf nodes contain the same number of black nodes.

The 'Key' and the 'Item' may be scalars and / or classes.

The Map class is not thread-safe for all operations that may change it's contents. It has two parsing APIs: one which is not thread safe and one which is thread safe and prefixed by 'mt_' in the method names used.

Functions documentation

public RED::Map::Map()

Map default construction method.

public RED::Map::Map(const Map< Key, Item > &iSource)

Map copy construction method.

The memory capacity of this is set to the actual size of 'iSource'.

Parameters:

iSource:Item source defining our contents.
public virtual RED::Map::~Map()

Map destruction method.

public virtual void * RED::Map::As(const RED::CID &iCID)

Converts the object to an instance of the given type.

Parameters:

iCID:Requested class.

Returns:

An object pointer of the given class on success, NULL otherwise.

Reimplements: RED::Object::As.

public virtual const void * RED::Map::As(const RED::CID &iCID) const

Converts the object to an instance of the given type.

Parameters:

iCID:Requested class.

Returns:

An object pointer of the given class on success, NULL otherwise.

Reimplements: RED::Object::As.

template< class T_As > public const T_As * RED::Map::As() const

Template version of the as const method.

Simply set T to be the class you want to retrieve an interface to.

Returns:

A pointer to a const instance of class T on success, NULL otherwise.

Reimplements: RED::Object::As.

template< class T_As > public T_As * RED::Map::As()

Template version of the as method.

Simply set T to be the class you want to retrieve an interface to.

Returns:

A pointer to an instance of class T on success, NULL otherwise.

Reimplements: RED::Object::As.

public void RED::Map::begin() const

Initializes the map parsing.

This is not a thread safe operation refer to 'mt_begin' for a thread safe map parsing.

public void RED::Map::clear()

Erases the contents of the map.

All Objects in the map are destroyed. All map storage memory is released.

public Item & RED::Map::current()

Gets the current element value.

This is not a thread safe operation refer to 'mt_current' for a thread safe map parsing.

The current element value is valid if:

  • We are parsing the map contents.
  • OR after a call to Map::find.

Returns:

the element value.
public const Item & RED::Map::current() const
public Key & RED::Map::current_key()

Gets the current element key.

This is not a thread safe operation refer to 'mt_current_key' for a thread safe map parsing.

The current element key is valid if:

  • We are parsing the map contents.
  • OR after a call to Map::find.

Returns:

the element key.
public const Key & RED::Map::current_key() const
public bool RED::Map::empty() const

Returns:

true if the map is empty, false if the map is not empty.
public bool RED::Map::end() const

Checks whether we have reached the last map element.

This is not a thread safe operation refer to 'mt_end' for a thread safe map parsing.

Returns:

true if the map parsing is finished.
public void RED::Map::erase(const Key &iKey)

Erases an element by its key.

Parameters:

iKey:Key used to look for the element.

Erases the current element in the map parsing.

The current element in the map parsing, or that was found is being erased by the call. The 'cursor' is set to the next element in the map after the deletion.

public const Item * RED::Map::find(const Key &iKey) const
public Item * RED::Map::find(const Key &iKey)

Looks for an element value by its key.

This is not a thread safe operation refer to 'mt_find' for a thread safe map parsing.

The current element is set to the result of the research. No call to this method should be issued during a map parsing. Note that after a find, Map::erase_current can be issued.

Parameters:

iKey:Searched element key.

Returns:

The address of the searched element. NULL when not found.
public RED_RC RED::Map::insert(const Key &iKey,
const Item &iValue
)

Inserts an element in the map.

Multiple insertions of values with the same key do not produce any changes to the map.

Parameters:

iKey:Insertion key.
iValue:Insertion object value.

Returns:

RED_OK when the insertion succeeded,
RED_ALLOC_FAILURE if an internal allocation did fail.
public RED_RC RED::Map::insert(bool &oInsert,
const Key &iKey,
const Item &iValue
)

Inserts an element in the map.

Multiple insertions of values with the same key do not produce any changes to the map.

Parameters:

oInsert:Set to true when the element has been successfully inserted in the map, false if 'iKey' existed already in the map.
iKey:Insertion key.
iValue:Insertion object value.

Returns:

RED_OK when the insertion succeeded,
RED_ALLOC_FAILURE if an internal allocation did fail.
public bool RED::Map::mapcheck() const

Map debugging tool. Checks the map integrity.

Checks the cell linking for all the map elements. Verifies the red-black tree rules.

Returns:

false if the map is not correct.
public void * RED::Map::mt_begin() const

Initializes the map parsing.

Thread safe method.

Returns:

A parsing address to reuse for all 'mt_' map parsing operations. This parsing address can be seen as an iterator.
public Item & RED::Map::mt_current(void *iParsingAddress)

Gets the current element value.

Thread safe method.
The current element value is valid if:

  • We are parsing the map contents.
  • OR after a call to Map::find.

Parameters:

iParsingAddress:The current parsing address.

Returns:

the element value.
public const Item & RED::Map::mt_current(void *iParsingAddress) const
public Key & RED::Map::mt_current_key(void *iParsingAddress)

Gets the current element key.

Thread safe method.
The current element key is valid if:

  • We are parsing the map contents.
  • OR after a call to Map::find.

Parameters:

iParsingAddress:The current parsing address.

Returns:

the element key.
public const Key & RED::Map::mt_current_key(void *iParsingAddress) const
public bool RED::Map::mt_end(void *iParsingAddress) const

Checks whether we have reached the last map element.

Thread safe method.

Parameters:

iParsingAddress:The current parsing address.

Returns:

true if the map parsing is finished.
public void RED::Map::mt_erase_current(void *&oParsingAddress)
public const Item * RED::Map::mt_find(void *&oParsingAddress,
const Key &iKey
)const
public Item * RED::Map::mt_find(void *&oParsingAddress,
const Key &iKey
)

Looks for an element value by its key.

Thread safe method.
The current element is set to the result of the research thanks to the parsing address. No call to this method should be issued during a map parsing.

Parameters:

oParsingAddress:The parsing address to reuse or access the current element using the 'mt_' parsing API. This parsing address can be seen as an iterator.
iKey:Searched element key.

Returns:

The address of the searched element. NULL when not found.
public bool RED::Map::mt_next(void *&ioParsingAddress) const

Moves to the next map element.

Thread safe method.

Parameters:

ioParsingAddress:The current parsing address.

Returns:

true if we have a valid element after that call, false if we have finished the map parsing.
public bool RED::Map::next() const

Moves to the next map element.

This is not a thread safe operation refer to 'mt_next' for a thread safe map parsing.

Returns:

true if we have a valid element after that call, false if we have finished the map parsing.
public RED_RC RED::Map::operator=(const Map< Key, Item > &iSource)

Assignment operator.

The memory capacity of this is set to the actual size of 'iSource'.

Parameters:

iSource:Source overwriting our current contents.

Returns:

RED_OK when the assignment succeeded,
RED_ALLOC_FAILURE if an internal allocation did fail.
public void RED::Map::restore_parsing() const

Restores the parsing position.

This is not a thread safe operation.

Restores a previously saved parsing position. Note that the contents of the map must not have changed between Map::save_parsing and Map::restore_parsing.

public void RED::Map::save_parsing() const

Saves the parsing position.

This is not a thread safe operation.

Saves the current parsing position. It can be restored with a call to Map::restore_parsing.

Returns:

The number of Objects in the map.

Adds memory storage to the map.

The memory size of the chunk that is created is based on its number, using a 50% memory growth per chunk.

Returns:

RED_OK when the allocation succeeded,
RED_ALLOC_FAILURE otherwise.
protected void RED::Map::rotate_left(Cell *iCell)

Left tree rotation.

Parameters:

iCell:Rotated cell.
protected void RED::Map::rotate_right(Cell *iCell)

Right tree rotation.

Parameters:

iCell:Rotated cell.

Variables documentation

Chunks of (key,item) pairs defining the map. pairs addresses never change along the life cycle of the map, hence each array of cells is resized once for all at its creation time.

protected Cell * RED::Map::_current

Current cell being navigated for the map parsing.

protected Cell * RED::Map::_root

Root cell in the tree.

protected Cell * RED::Map::_saved_current

Current cell being navigated for the map parsing.

Current number of items in the map.

Enumerations documentation

protected enum RED::Map::MapColor

RED or BLACK to match the red-black tree rules.

Enumerator:

RED
BLACK