doc/RedBlackTree/FS/EPTF CLL Red Black Tree, Function Description.adoc - titan/titan.Libraries.CLL - Git at Google

 ---
 Author: Gábor Tatárka
 Version: 12/155 16-CNL 113 512, Rev. B
 Date: 2011-12-06

 ---
 = EPTF CLL Red Black Tree, Function Description
 :author: Gábor Tatárka
 :revnumber: 12/155 16-CNL 113 512, Rev. B
 :revdate: 2011-12-06
 :toc:


 == How to Read This Document

 This is the Function Description for the Red Black Tree of the Ericsson Performance Test Framework (TitanSim), Core Load Library (CLL). TitanSim CLL is developed for the TTCN-3 <<_1, ‎[1]>> Toolset with TITAN ‎<<_2, [2]>>.

 == Scope

 This document is to specify the content and functionality of the Red Black Tree feature of the TitanSim CLL.

 == Recommended Way of Reading

 The readers are supposed to get familiar with the concept and functionalities of TitanSim CLL <<_3, ‎[3]>>. They should get familiar with the list of acronyms and the glossary in the Terminology section.

 = General Description

 This document specifies the Red Black Tree feature of the TitanSim CLL.

 The EPTF Red Black Tree feature is a self-balancing binary search tree, for details see <<_6, [6]>>. It can be used to store indexes into an associated array, similar to the EPTF Free Busy Queue <<_5, ‎[5]>>.

 Each node in the EPTF Red Black Tree is a linked list. This makes it possible to store more than one item with the same key, in the order of the insertion. Each item in the tree (or the lists) has a unique ID/index, which is allocated incrementally with each item-insertion into the tree. Removed items are reused in subsequent insert operations.

 Inserting new item in the Red Black Tree is slightly slower, but searching for a specific item is faster than with the Free Busy Queue with a large number of items. Furthermore, the Red Black Tree can be used to sort items or to iterate through items in order.

 See overview of the Red Black Tree in the figure below:

 image:images/Red_black_tree.png[alt]

 Figure above shows an example overview of the internal data representation of a Red Black Tree and its associated array (item keys and leaf/null nodes are not shown). The links between tree nodes, chain items and the free items are all stored in the items themselves. Any change in the chaining (e.g. tree rotation) does not modify the index of the items.

 Items removed are stored in a stack (free stack or free chain), and are reused in reverse order of their removal when inserting items (if there are no available pre-allocated items).

 In the example above, there are 6 nodes in the tree, meaning that 6 individual keys were used when inserting items. The node at item 9 has a chain length of three, i.e. three items with this key were inserted: 9, 10 and 11 in this order.

 NOTE: The head and tail of this chain refers to each other in order to speed up insertion at the end of the chain). Sorting the items would result in index list 1, 3, 2, 7, 6, 9, 10 and 11. The next item inserted (assuming there are no pre-allocated items) would be item 0 (and the free head would then point to item 4).

 = Functional Interface

 Currently there are three kinds of trees in the Red Black Tree feature, distinguished by the key type of the items. These are:

 * integer tree
 * float tree
 * charstring tree

 There are separate functions for each tree type if the function has the key as parameter or if it returns the key. These functions refer to the key type with their name (e.g. `f_EPTF_RBT_insertIntItem`)

 Other functions that do not depend on the key type are unified (e.g. `f_EPTF_RBT_removeItem`).

 The component `EPTF_RBT_CT` must be extended and initialized (<<init, Initialization>>) to use the Red Black Tree feature. The external functions in this feature do not have a runs-on clause, but they must be handled as if they would run on `EPTF_RBT_CT`.

 All functions have the prefix `f_EPTF_RBT_`.

 Apart from this description a cross-linked reference guide for the TitanSim CLL Functions can be reached for on-line reading ‎<<_4, [4]>>.

 [[init]]
 == Initialization

 The function `f_EPTF_RBT_init_CT(pl_selfName)` must be called before using the Red Black Tree feature.

 == Creating a Tree

 The following functions can be used to create a new Red Black Tree:

 [source]
 ----
 f_EPTF_RBT_createIntTree(pl_name) return EPTF_RBT_TreeId

 f_EPTF_RBT_createFloatTree(pl_name) return EPTF_RBT_TreeId

 f_EPTF_RBT_createCharstringTree(pl_name) return EPTF_RBT_TreeId
 ----

 == Deleting a Tree

 The function `f_EPTF_RBT_deleteTree(pl_tree)` can be used to delete a tree and free all its resources.

 == Inserting an Item

 The following functions can be used to insert (create) a new item in a tree:

 [source]
 ----
 f_EPTF_RBT_insertIntItem(pl_tree, pl_key) return EPTF_RBT_ItemIdx

 f_EPTF_RBT_insertFloatItem(pl_tree, pl_key) return EPTF_RBT_ItemIdx

 f_EPTF_RBT_insertCharstringItem(pl_tree, pl_key) return EPTF_RBT_ItemIdx
 ----

 == Removing an Item

 The function `f_EPTF_RBT_removeItem(pl_tree, pl_item)` can be used to remove an item from a tree. Removed items will be reused in subsequent insertions.

 == Getting the Smallest Item

 The function `f_EPTF_RBT_getItemWithSmallestKey(pl_tree)` returns the index of the item with the smallest key in the tree, or `_−1_` if the tree is empty. The index of the smallest item is cached, and its cache is updated at both insertion and removal in a way that searching for the smallest item is never needed.

 == Getting the Key of an Item

 The following functions return the key of an item in a tree:

 [source]
 ----
 f_EPTF_RBT_getKeyOfIntItem(pl_tree, pl_item) return integer

 f_EPTF_RBT_getKeyOfFloatItem(pl_tree, pl_item) return float

 f_EPTF_RBT_getKeyOfCharstringItem(pl_tree, pl_item) return charstring
 ----

 == Finding an Item by Key

 The following functions return the index of the first item with a given key or `_−1_` if no item is found:

 [source]
 ----
 f_EPTF_RBT_findFirstItemByIntKey(pl_tree, pl_key) return EPTF_RBT_ItemIdx

 f_EPTF_RBT_findFirstItemByFloatKey(pl_tree, pl_key) return EPTF_RBT_ItemIdx

 f_EPTF_RBT_findFirstItemByCharstringKey(pl_tree, pl_key) return EPTF_RBT_ItemIdx
 ----

 Use `f_EPTF_RBT_getNextInChain` to get further items with the same keys (if any), see <<other_getter_functions, Other Getter Functions>>.

 [[other_getter_functions]]
 == Other Getter Functions

 In addition to the functions in previous sections, the following getter functions are defined:

 * `f_EPTF_RBT_getRoot(pl_tree)`: returns the root node or `_−1_` if tree is empty
 * `f_EPTF_RBT_getLeft(pl_tree, pl_item)`: returns the left child of a node or −1 if none (no child or item is not node)
 * `f_EPTF_RBT_getRight(pl_tree, pl_item`): returns the right child of a node or −1 if none (no child or item is not node)
 * `f_EPTF_RBT_getParent(pl_tree, pl_item)`: returns the parent of a node or −1 if none (item is root or not a node)
 * `f_EPTF_RBT_getNextInChain(pl_tree, pl_item)`: returns the next item with the same key as the key of `pl_item` or `_−1_` if none
 * `f_EPTF_RBT_getPrevInChain(pl_tree, pl_item)`: returns the previous item with the same key as the key of `pl_item` or `_−1_` if none

 == Iterating Through Items

 The function `f_EPTF_RBT_iterateIncremental(pl_tree, pl_item)` can be used to iterate through the items of the tree, including items with the same key (in insertion order).

 == Sorting Items

 The following function returns the item order (including items with same key) in its out parameter `pl_itemsSorted`:

 `f_EPTF_RBT_sortIncremental(pl_tree, pl_itemsSorted)`

 == Summary Table of All Public Functions for EPTF Red Black Tree

 See summary of Red Black Tree functions in the table below:

 [cols=",",options="header",]
 |====================================================================
 |Function name |Description
 |`f_EPTF_RBT_init_CT` |Init the Red Black Tree feature
 |`f_EPTF_RBT_createIntTree` |Create an integer tree
 |`f_EPTF_RBT_createFloatTree` |Create a float tree
 |`f_EPTF_RBT_createCharstringTree` |Create a charstring tree
 |`f_EPTF_RBT_deleteTree` |Delete a tree
 |`f_EPTF_RBT_insertIntItem` |Insert an item with integer key
 |`f_EPTF_RBT_insertFloatItem` |Insert an item with float key
 |`f_EPTF_RBT_insertCharstringItem` |Insert an item with charstring key
 |`f_EPTF_RBT_removeItem` |Remove an item
 |`f_EPTF_RBT_getItemWithSmallestKey` |Get item with the smallest key
 |`f_EPTF_RBT_getKeyOfIntItem` |Get integer key of an item
 |`f_EPTF_RBT_getKeyOfFloatItem` |Get float key of an item
 |`f_EPTF_RBT_getKeyOfCharstringItem` |Get charstring key of an item
 |`f_EPTF_RBT_findFirstItemByIntKey` |Find item by integer key
 |`f_EPTF_RBT_findFirstItemByFloatKey` |Find item by float key
 |`f_EPTF_RBT_findFirstItemByCharstringKey` |Find item by charstring key
 |`f_EPTF_RBT_getRoot` |Get root node
 |`f_EPTF_RBT_getLeft` |Get left child node
 |`f_EPTF_RBT_getRight` |Get right child node
 |`f_EPTF_RBT_getNextInChain` |Get next item with same key
 |`f_EPTF_RBT_getPrevInChain` |Get previous item with same key
 |`f_EPTF_RBT_iterateIncremental` |Iterate through the items
 |`f_EPTF_RBT_sortIncremental` |Sort the items
 |====================================================================

 = Obsolete Functional Interface

 Currently, the following *obsolete* functionality is also included.

 NOTE: These functions will be removed in a later release of the Core Load Library.

 Apart from this description a cross-linked reference guide for the TitanSim CLL Functions can be reached for on-line reading ‎<<_4, [4]>>.

 == Naming Conventions

 All integer Red Black Tree functions have the prefix `f_EPTF_RBTreeI`.

 All float Red Black Tree functions have the prefix `f_EPTF_RBTreeF`.

 == Public Functions

 === Initialization

 Before using the EPTF Red Black Tree functions the

 `f_EPTF_RBTreeI_initIntegerTree(rb_Tree)` or

 `f_EPTF_RBTreeF_initFloatTree(rb_Tree)`

 function should be called. This initializes the Red Black Tree passed as the parameter.

 === Creating a New Node

 The function `f_EPTF_RBTreeI_createNewIntegerNode(rb_Tree, key, data)` or `f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, key, data)` can be used to create a new node in the tree.

 === Removing a Node

 The following functions can be used to remove a node from the tree:

 [source]
 ----
 f_EPTF_RBTreeI_removeIntegerNodeWithSameKey(rb_Tree, pl_nodeToDeleteIndex)

 f_EPTF_RBTreeI_removeIntegerNode(rb_Tree, pl_z, pl_destroyNode)

 f_EPTF_RBTreeF_removeFloatNodeWithSameKey(rb_Tree, pl_nodeToDeleteIndex)

 f_EPTF_RBTreeF_removeFloatNode(rb_Tree, pl_z, pl_destroyNode)
 ----

 === Getting Elements From the Tree

 The following functions can be used to get elements from the tree:

 [source]
 ----
 f_EPTF_RBTreeI_getIntegerElementNodeByKey(rb_Tree, key, nodeFound, indexFound)

 f_EPTF_RBTreeI_searchSmallestIntegerNode(tree, nodeFound, indexFound)

 f_EPTF_RBTreeI_getSmallestNodeFromCache(rb_Tree, nodeFound)

 f_EPTF_RBTreeI_getBusyEventHeadIndex(rb_Tree, idx)

 f_EPTF_RBTreeF_getFloatElementNodeByKey(rb_Tree, key, nodeFound, indexFound)

 f_EPTF_RBTreeF_searchSmallestFloatNode(tree, nodeFound, indexFound)

 f_EPTF_RBTreeF_getSmallestNodeFromCache(rb_Tree, nodeFound)

 f_EPTF_RBTreeF_getBusyEventHeadIndex(rb_Tree, idx)

 f_EPTF_RBTreeF_getNextSmallestFloatElementIndex(pl_tree, pl_curSmallestIndex, pl_indexFound)
 ----

 == Summary Table of Obsolete Functions for EPTF Red Black Tree

 See summary of obsolete Red Black Tree functions in the table below:

 [cols=",",options="header",]
 |==========================================================================
 |Function name |Description
 |`f_EPTF_RBTreeI_initIntegerTree` |initialize an integer red black tree
 |`f_EPTF_RBTreeF_initFloatTree` |initialize a float red black tree
 |`f_EPTF_RBTreeI_createNewIntegerNode` |create a new integer node
 |`f_EPTF_RBTreeF_createNewFloatNode` |create a new float node
 |`f_EPTF_RBTreeI_removeIntegerNodeWithSameKey` |remove a node
 |`f_EPTF_RBTreeI_removeIntegerNode` |remove a node
 |`f_EPTF_RBTreeF_removeFloatNodeWithSameKey` |remove a node
 |`f_EPTF_RBTreeF_removeFloatNode` |remove a node
 |`f_EPTF_RBTreeI_getIntegerElementNodeByKey` |get an element by key
 |`f_EPTF_RBTreeI_searchSmallestIntegerNode` |get smallest element
 |`f_EPTF_RBTreeI_getSmallestNodeFromCache` |get smallest element
 |`f_EPTF_RBTreeI_getBusyEventHeadIndex` |get smallest element
 |`f_EPTF_RBTreeF_getFloatElementNodeByKey` |get an element by key
 |`f_EPTF_RBTreeF_searchSmallestFloatNode` |get smallest element
 |`f_EPTF_RBTreeF_getSmallestNodeFromCache` |get smallest element
 |`f_EPTF_RBTreeF_getBusyEventHeadIndex` |get smallest element
 |`f_EPTF_RBTreeF_getNextSmallestFloatElementIndex` |get next smallest element
 |==========================================================================

 = Terminology

 *TitanSim Core (Load) Library(CLL):* +
 It is that part of the TitanSim software that is totally project independent. (I.e., which is not protocol-, or application-dependent). The TitanSim CLL is to be supplied and supported by the TCC organization. Any TitanSim CLL development is to be funded centrally by Ericsson

 *Free Busy Queue:* +
 The aim of the EPTF Free Busy Queue feature is to provide dynamic memory allocation and list element sorting for the TTCN-3 language in an efficient way.

 *Item:* +
 An item in the red black tree. Can be a node, a chain item or a free item. It is uniquely identified by its index. An EPTF red black tree can contain multiple items with the same key.

 *Node Item:* +
 A node of the red black tree. If there are more than one items in the tree with the same key, subsequently added items are stored in a linked list, with the node item being the head of the list.

 *Chain Item:* +
 An item that is stored in a linked list and is not the head of the list (i.e. the node itself). Its key equals the key of the node item it is chained after.

 *Free Item:* +
 An item that was previously removed from the tree, it will be reused in a subsequent insert operation.

 *Key:* +
 The key is a non-unique identifier of an item in the tree. Each item in the tree is added with a specific key and the first item added with a given key can be searched for. Items in a tree can be sorted by their keys (and addition order in case of multiple items with the same key).

 = Abbreviations

 CLL:: Core Load Library

 EPTF:: Ericsson Load Test Framework, formerly TITAN Load Test Framework

 TitanSim:: Ericsson Load Test Framework, formerly TITAN Load Test Framework

 TTCN-3:: Testing and Test Control Notation version 3 <<_1, ‎[1]>>

 = References

 [[_1]]
 [1] ETSI ES 201 873-1 v3.2.1 (2007-02) +
 The Testing and Test Control Notation version 3. Part 1: Core Language

 [[_2]]
 [2] User Guide for the TITAN TTCN-3 Test Executor

 [[_3]]
 [3] TitanSim CLL for TTCN-3 toolset with TITAN, Function Specification

 [[_4]]
 [4] TitanSim CLL for TTCN-3 toolset with TITAN, +
 http://ttcn.ericsson.se/products/libraries.shtml[Reference Guide]

 [[_5]]
 [5] EPTF Free Busy Queue, Function Description

 [[_6]]
 [6] Red-black tree, wikipedia +
 http://en.wikipedia.org/wiki/Red-black_tree
	---
	Author: Gábor Tatárka
	Version: 12/155 16-CNL 113 512, Rev. B
	Date: 2011-12-06

	---
	= EPTF CLL Red Black Tree, Function Description
	:author: Gábor Tatárka
	:revnumber: 12/155 16-CNL 113 512, Rev. B
	:revdate: 2011-12-06
	:toc:


	== How to Read This Document

	This is the Function Description for the Red Black Tree of the Ericsson Performance Test Framework (TitanSim), Core Load Library (CLL). TitanSim CLL is developed for the TTCN-3 <<_1, ‎[1]>> Toolset with TITAN ‎<<_2, [2]>>.

	== Scope

	This document is to specify the content and functionality of the Red Black Tree feature of the TitanSim CLL.

	== Recommended Way of Reading

	The readers are supposed to get familiar with the concept and functionalities of TitanSim CLL <<_3, ‎[3]>>. They should get familiar with the list of acronyms and the glossary in the Terminology section.

	= General Description

	This document specifies the Red Black Tree feature of the TitanSim CLL.

	The EPTF Red Black Tree feature is a self-balancing binary search tree, for details see <<_6, [6]>>. It can be used to store indexes into an associated array, similar to the EPTF Free Busy Queue <<_5, ‎[5]>>.

	Each node in the EPTF Red Black Tree is a linked list. This makes it possible to store more than one item with the same key, in the order of the insertion. Each item in the tree (or the lists) has a unique ID/index, which is allocated incrementally with each item-insertion into the tree. Removed items are reused in subsequent insert operations.

	Inserting new item in the Red Black Tree is slightly slower, but searching for a specific item is faster than with the Free Busy Queue with a large number of items. Furthermore, the Red Black Tree can be used to sort items or to iterate through items in order.

	See overview of the Red Black Tree in the figure below:

	image:images/Red_black_tree.png[alt]

	Figure above shows an example overview of the internal data representation of a Red Black Tree and its associated array (item keys and leaf/null nodes are not shown). The links between tree nodes, chain items and the free items are all stored in the items themselves. Any change in the chaining (e.g. tree rotation) does not modify the index of the items.

	Items removed are stored in a stack (free stack or free chain), and are reused in reverse order of their removal when inserting items (if there are no available pre-allocated items).

	In the example above, there are 6 nodes in the tree, meaning that 6 individual keys were used when inserting items. The node at item 9 has a chain length of three, i.e. three items with this key were inserted: 9, 10 and 11 in this order.

	NOTE: The head and tail of this chain refers to each other in order to speed up insertion at the end of the chain). Sorting the items would result in index list 1, 3, 2, 7, 6, 9, 10 and 11. The next item inserted (assuming there are no pre-allocated items) would be item 0 (and the free head would then point to item 4).

	= Functional Interface

	Currently there are three kinds of trees in the Red Black Tree feature, distinguished by the key type of the items. These are:

	* integer tree
	* float tree
	* charstring tree

	There are separate functions for each tree type if the function has the key as parameter or if it returns the key. These functions refer to the key type with their name (e.g. `f_EPTF_RBT_insertIntItem`)

	Other functions that do not depend on the key type are unified (e.g. `f_EPTF_RBT_removeItem`).

	The component `EPTF_RBT_CT` must be extended and initialized (<<init, Initialization>>) to use the Red Black Tree feature. The external functions in this feature do not have a runs-on clause, but they must be handled as if they would run on `EPTF_RBT_CT`.

	All functions have the prefix `f_EPTF_RBT_`.

	Apart from this description a cross-linked reference guide for the TitanSim CLL Functions can be reached for on-line reading ‎<<_4, [4]>>.

	[[init]]
	== Initialization

	The function `f_EPTF_RBT_init_CT(pl_selfName)` must be called before using the Red Black Tree feature.

	== Creating a Tree

	The following functions can be used to create a new Red Black Tree:

	[source]
	----
	f_EPTF_RBT_createIntTree(pl_name) return EPTF_RBT_TreeId

	f_EPTF_RBT_createFloatTree(pl_name) return EPTF_RBT_TreeId

	f_EPTF_RBT_createCharstringTree(pl_name) return EPTF_RBT_TreeId
	----

	== Deleting a Tree

	The function `f_EPTF_RBT_deleteTree(pl_tree)` can be used to delete a tree and free all its resources.

	== Inserting an Item

	The following functions can be used to insert (create) a new item in a tree:

	[source]
	----
	f_EPTF_RBT_insertIntItem(pl_tree, pl_key) return EPTF_RBT_ItemIdx

	f_EPTF_RBT_insertFloatItem(pl_tree, pl_key) return EPTF_RBT_ItemIdx

	f_EPTF_RBT_insertCharstringItem(pl_tree, pl_key) return EPTF_RBT_ItemIdx
	----

	== Removing an Item

	The function `f_EPTF_RBT_removeItem(pl_tree, pl_item)` can be used to remove an item from a tree. Removed items will be reused in subsequent insertions.

	== Getting the Smallest Item

	The function `f_EPTF_RBT_getItemWithSmallestKey(pl_tree)` returns the index of the item with the smallest key in the tree, or `_−1_` if the tree is empty. The index of the smallest item is cached, and its cache is updated at both insertion and removal in a way that searching for the smallest item is never needed.

	== Getting the Key of an Item

	The following functions return the key of an item in a tree:

	[source]
	----
	f_EPTF_RBT_getKeyOfIntItem(pl_tree, pl_item) return integer

	f_EPTF_RBT_getKeyOfFloatItem(pl_tree, pl_item) return float

	f_EPTF_RBT_getKeyOfCharstringItem(pl_tree, pl_item) return charstring
	----

	== Finding an Item by Key

	The following functions return the index of the first item with a given key or `_−1_` if no item is found:

	[source]
	----
	f_EPTF_RBT_findFirstItemByIntKey(pl_tree, pl_key) return EPTF_RBT_ItemIdx

	f_EPTF_RBT_findFirstItemByFloatKey(pl_tree, pl_key) return EPTF_RBT_ItemIdx

	f_EPTF_RBT_findFirstItemByCharstringKey(pl_tree, pl_key) return EPTF_RBT_ItemIdx
	----

	Use `f_EPTF_RBT_getNextInChain` to get further items with the same keys (if any), see <<other_getter_functions, Other Getter Functions>>.

	[[other_getter_functions]]
	== Other Getter Functions

	In addition to the functions in previous sections, the following getter functions are defined:

	* `f_EPTF_RBT_getRoot(pl_tree)`: returns the root node or `_−1_` if tree is empty
	* `f_EPTF_RBT_getLeft(pl_tree, pl_item)`: returns the left child of a node or −1 if none (no child or item is not node)
	* `f_EPTF_RBT_getRight(pl_tree, pl_item`): returns the right child of a node or −1 if none (no child or item is not node)
	* `f_EPTF_RBT_getParent(pl_tree, pl_item)`: returns the parent of a node or −1 if none (item is root or not a node)
	* `f_EPTF_RBT_getNextInChain(pl_tree, pl_item)`: returns the next item with the same key as the key of `pl_item` or `_−1_` if none
	* `f_EPTF_RBT_getPrevInChain(pl_tree, pl_item)`: returns the previous item with the same key as the key of `pl_item` or `_−1_` if none

	== Iterating Through Items

	The function `f_EPTF_RBT_iterateIncremental(pl_tree, pl_item)` can be used to iterate through the items of the tree, including items with the same key (in insertion order).

	== Sorting Items

	The following function returns the item order (including items with same key) in its out parameter `pl_itemsSorted`:

	`f_EPTF_RBT_sortIncremental(pl_tree, pl_itemsSorted)`

	== Summary Table of All Public Functions for EPTF Red Black Tree

	See summary of Red Black Tree functions in the table below:

	[cols=",",options="header",]
	\|====================================================================
	\|Function name \|Description
	\|`f_EPTF_RBT_init_CT` \|Init the Red Black Tree feature
	\|`f_EPTF_RBT_createIntTree` \|Create an integer tree
	\|`f_EPTF_RBT_createFloatTree` \|Create a float tree
	\|`f_EPTF_RBT_createCharstringTree` \|Create a charstring tree
	\|`f_EPTF_RBT_deleteTree` \|Delete a tree
	\|`f_EPTF_RBT_insertIntItem` \|Insert an item with integer key
	\|`f_EPTF_RBT_insertFloatItem` \|Insert an item with float key
	\|`f_EPTF_RBT_insertCharstringItem` \|Insert an item with charstring key
	\|`f_EPTF_RBT_removeItem` \|Remove an item
	\|`f_EPTF_RBT_getItemWithSmallestKey` \|Get item with the smallest key
	\|`f_EPTF_RBT_getKeyOfIntItem` \|Get integer key of an item
	\|`f_EPTF_RBT_getKeyOfFloatItem` \|Get float key of an item
	\|`f_EPTF_RBT_getKeyOfCharstringItem` \|Get charstring key of an item
	\|`f_EPTF_RBT_findFirstItemByIntKey` \|Find item by integer key
	\|`f_EPTF_RBT_findFirstItemByFloatKey` \|Find item by float key
	\|`f_EPTF_RBT_findFirstItemByCharstringKey` \|Find item by charstring key
	\|`f_EPTF_RBT_getRoot` \|Get root node
	\|`f_EPTF_RBT_getLeft` \|Get left child node
	\|`f_EPTF_RBT_getRight` \|Get right child node
	\|`f_EPTF_RBT_getNextInChain` \|Get next item with same key
	\|`f_EPTF_RBT_getPrevInChain` \|Get previous item with same key
	\|`f_EPTF_RBT_iterateIncremental` \|Iterate through the items
	\|`f_EPTF_RBT_sortIncremental` \|Sort the items
	\|====================================================================

	= Obsolete Functional Interface

	Currently, the following obsolete functionality is also included.

	NOTE: These functions will be removed in a later release of the Core Load Library.

	Apart from this description a cross-linked reference guide for the TitanSim CLL Functions can be reached for on-line reading ‎<<_4, [4]>>.

	== Naming Conventions

	All integer Red Black Tree functions have the prefix `f_EPTF_RBTreeI`.

	All float Red Black Tree functions have the prefix `f_EPTF_RBTreeF`.

	== Public Functions

	=== Initialization

	Before using the EPTF Red Black Tree functions the

	`f_EPTF_RBTreeI_initIntegerTree(rb_Tree)` or

	`f_EPTF_RBTreeF_initFloatTree(rb_Tree)`

	function should be called. This initializes the Red Black Tree passed as the parameter.

	=== Creating a New Node

	The function `f_EPTF_RBTreeI_createNewIntegerNode(rb_Tree, key, data)` or `f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, key, data)` can be used to create a new node in the tree.

	=== Removing a Node

	The following functions can be used to remove a node from the tree:

	[source]
	----
	f_EPTF_RBTreeI_removeIntegerNodeWithSameKey(rb_Tree, pl_nodeToDeleteIndex)

	f_EPTF_RBTreeI_removeIntegerNode(rb_Tree, pl_z, pl_destroyNode)

	f_EPTF_RBTreeF_removeFloatNodeWithSameKey(rb_Tree, pl_nodeToDeleteIndex)

	f_EPTF_RBTreeF_removeFloatNode(rb_Tree, pl_z, pl_destroyNode)
	----

	=== Getting Elements From the Tree

	The following functions can be used to get elements from the tree:

	[source]
	----
	f_EPTF_RBTreeI_getIntegerElementNodeByKey(rb_Tree, key, nodeFound, indexFound)

	f_EPTF_RBTreeI_searchSmallestIntegerNode(tree, nodeFound, indexFound)

	f_EPTF_RBTreeI_getSmallestNodeFromCache(rb_Tree, nodeFound)

	f_EPTF_RBTreeI_getBusyEventHeadIndex(rb_Tree, idx)

	f_EPTF_RBTreeF_getFloatElementNodeByKey(rb_Tree, key, nodeFound, indexFound)

	f_EPTF_RBTreeF_searchSmallestFloatNode(tree, nodeFound, indexFound)

	f_EPTF_RBTreeF_getSmallestNodeFromCache(rb_Tree, nodeFound)

	f_EPTF_RBTreeF_getBusyEventHeadIndex(rb_Tree, idx)

	f_EPTF_RBTreeF_getNextSmallestFloatElementIndex(pl_tree, pl_curSmallestIndex, pl_indexFound)
	----

	== Summary Table of Obsolete Functions for EPTF Red Black Tree

	See summary of obsolete Red Black Tree functions in the table below:

	[cols=",",options="header",]
	\|==========================================================================
	\|Function name \|Description
	\|`f_EPTF_RBTreeI_initIntegerTree` \|initialize an integer red black tree
	\|`f_EPTF_RBTreeF_initFloatTree` \|initialize a float red black tree
	\|`f_EPTF_RBTreeI_createNewIntegerNode` \|create a new integer node
	\|`f_EPTF_RBTreeF_createNewFloatNode` \|create a new float node
	\|`f_EPTF_RBTreeI_removeIntegerNodeWithSameKey` \|remove a node
	\|`f_EPTF_RBTreeI_removeIntegerNode` \|remove a node
	\|`f_EPTF_RBTreeF_removeFloatNodeWithSameKey` \|remove a node
	\|`f_EPTF_RBTreeF_removeFloatNode` \|remove a node
	\|`f_EPTF_RBTreeI_getIntegerElementNodeByKey` \|get an element by key
	\|`f_EPTF_RBTreeI_searchSmallestIntegerNode` \|get smallest element
	\|`f_EPTF_RBTreeI_getSmallestNodeFromCache` \|get smallest element
	\|`f_EPTF_RBTreeI_getBusyEventHeadIndex` \|get smallest element
	\|`f_EPTF_RBTreeF_getFloatElementNodeByKey` \|get an element by key
	\|`f_EPTF_RBTreeF_searchSmallestFloatNode` \|get smallest element
	\|`f_EPTF_RBTreeF_getSmallestNodeFromCache` \|get smallest element
	\|`f_EPTF_RBTreeF_getBusyEventHeadIndex` \|get smallest element
	\|`f_EPTF_RBTreeF_getNextSmallestFloatElementIndex` \|get next smallest element
	\|==========================================================================

	= Terminology

	TitanSim Core (Load) Library(CLL): +
	It is that part of the TitanSim software that is totally project independent. (I.e., which is not protocol-, or application-dependent). The TitanSim CLL is to be supplied and supported by the TCC organization. Any TitanSim CLL development is to be funded centrally by Ericsson

	Free Busy Queue: +
	The aim of the EPTF Free Busy Queue feature is to provide dynamic memory allocation and list element sorting for the TTCN-3 language in an efficient way.

	Item: +
	An item in the red black tree. Can be a node, a chain item or a free item. It is uniquely identified by its index. An EPTF red black tree can contain multiple items with the same key.

	Node Item: +
	A node of the red black tree. If there are more than one items in the tree with the same key, subsequently added items are stored in a linked list, with the node item being the head of the list.

	Chain Item: +
	An item that is stored in a linked list and is not the head of the list (i.e. the node itself). Its key equals the key of the node item it is chained after.

	Free Item: +
	An item that was previously removed from the tree, it will be reused in a subsequent insert operation.

	Key: +
	The key is a non-unique identifier of an item in the tree. Each item in the tree is added with a specific key and the first item added with a given key can be searched for. Items in a tree can be sorted by their keys (and addition order in case of multiple items with the same key).

	= Abbreviations

	CLL:: Core Load Library

	EPTF:: Ericsson Load Test Framework, formerly TITAN Load Test Framework

	TitanSim:: Ericsson Load Test Framework, formerly TITAN Load Test Framework

	TTCN-3:: Testing and Test Control Notation version 3 <<_1, ‎[1]>>

	= References

	[[_1]]
	[1] ETSI ES 201 873-1 v3.2.1 (2007-02) +
	The Testing and Test Control Notation version 3. Part 1: Core Language

	[[_2]]
	[2] User Guide for the TITAN TTCN-3 Test Executor

	[[_3]]
	[3] TitanSim CLL for TTCN-3 toolset with TITAN, Function Specification

	[[_4]]
	[4] TitanSim CLL for TTCN-3 toolset with TITAN, +
	http://ttcn.ericsson.se/products/libraries.shtml[Reference Guide]

	[[_5]]
	[5] EPTF Free Busy Queue, Function Description

	[[_6]]
	[6] Red-black tree, wikipedia +
	http://en.wikipedia.org/wiki/Red-black_tree