doc/NQueue/FS/EPTF CLL NQueue, Function Description.adoc

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

---
= EPTF CLL NQueue, Function Description
:author: Gábor Tatárka
:revnumber: 31/155 16-CNL 113 512, Rev. A
:revdate: 2011-06-07
:toc:

== How to Read This Document

This is the Function Description for the `NQueue` 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 `NQueue` 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 `NQueue` feature of the TitanSim CLL.

The EPTF `NQueue` feature makes it possible to

* Manage linked lists ("chains") over 'record of' datastructures easily using index-arithmetics
** Provide efficient iterators over the elements linked into the same list
* Book-keep the state of elements of a 'record of' type efficiently
** Provide efficient methods for moving elements back and forth between an arbitrary number of chains with computational complexity of O(1) (that is, constant), regardless of the length of the queue
** Reorder items within the same chain
** Maintain up-to-date additional statistics about the number of elements in each chain, respectively
* Implement stacks
** Stack-like data structures can be implemented with a chain by adding elements at the chain head (or tail) and also removing them from the head (or tail) of the chain.

The `NQueue` feature can be thought of as a general version of the Free Busy Queue <<_4, [4]>> feature and can, in a similar way, be used for dynamic memory allocation for the TTCN-3 language in an efficient way. Furthermore, it can be used to group the items in a 'record of' data structure by their state (chain ID) and iterating through these items.

An example of `NQueue` and an associated user defined data list can be seen on figure below:

[[NQueue_assoc_data_list]]
image::images/NQueue_assoc_data_list.png[alt]

== `NQueues` for Resource Allocation

The `NQueue` feature can be used as a replacement of the Free Busy Queue feature for resource allocation. This section describes one of the possible ways to do this, i.e. items are reused in a FIFO (round-robin) order. It is also possible to do a stack-like implementation with LIFO reuse order.

Typically, an `NQueue` has an associated data array (record of a user defined type), with the same length as the queue. Two chains in the queue have to be created: one representing the free state and the other the busy state of items in the queue. This also represents the allocation state of elements in the corresponding data array with the same index. Allocating or freeing a new element is usually a matter of moving a slot from one chain to the other.

It is up to the user of the `NQueue` to resize the data record-of in case the length of the queue increases (it never decreases). This can happen if the free chain has no more elements, so a new item has to be created in the queue.

Allocating a new element can be done by one of the following:

* If the length of the free chain is nonzero, the head of the free chain will be the index of the allocated element. In this case, the item at this index has to be moved to the tail of the chain representing busy elements. In this case, an element of the associated data which was earlier freed is now reused.
* If the length of the free chain is zero, a new item has to be created in the queue. This can be done in the busy chain as a single step, so the item does not have to be moved from free to busy chain. The index of the new item is in this case larger than the valid index range of the associated data list, so a new element will be created there as well.

Freeing an element is done by simply moving the queue item with the same index to the tail of the free chain. This item will then be reused by one of the subsequent element allocations.

Figure <<NQueue_assoc_data_list, NQueue and associated data lsit>>  can be used as an example, with chain 0 representing free items and chain 1 representing busy/allocated items. In this case, the next allocated item will be item 0. Freeing one of the busy items will result in it being chained after item 5, and becoming the new tail of chain 0.

== `NQueues` for Data Sorting

`NQueues` can be also used for storing the ordering of user elements of user data arrays. If the order of the user data elements are stored as a linked list, reordering of complex data structures can be performed via integer index arithmetic only, that is, without moving the (possibly complex) user data itself.

= Functional Interface

Apart from this description a cross-linked reference guide for the TitanSim CLL Functions can be reached for on-line reading.

The component that wishes to use the `NQueue` feature has to extend the component type `EPTF_NQueue_CT` defined in module `EPTF_CLL_NQueue_Definitions`.

The API of the NQueue feature is implemented in external functions. Because of this, the functions declared in module `EPTF_CLL_NQueue_Functions` do not have a 'runs on' clause. However, all these functions have to be handled as if they were defined as `runs on EPTF_NQueue_CT`. Calling these functions from other functions that do not have a 'runs on' attribute or that run on a component type not extending `EPTF_NQueue_CT` is not recommended.

== Naming Conventions

All functions have the prefix `f_EPTF_NQueue_`.

== Public Functions

=== Initialization

Before using the EPTF `NQueue` feature, the following function has to be called:

`f_EPTF_NQueue_init_CT(pl_selfName)`

=== Creating an Empty Queue

The following function creates a new, empty queue:

* `f_EPTF_NQueue_createQueue(pl_name)`
+
This function returns a queue ID of type `EPTF_NQueue_QueueId` which can later be used to reference the queue. An (optional) charstring name can be specified for the queue, which will be logged in error messages.

=== Deleting a Queue

The function `f_EPTF_NQueue_deleteQueue(pl_queue)` can be used to delete a queue and all the resources it uses. This is useful if a queue is used locally in a function. The IDs of deleted queues are stored in a stack and are reused on subsequent queue creations.

All queues are automatically deleted at component cleanup.

=== Creating a Chain

The following function creates a new chain within an existing queue:

* `f_EPTF_NQueue_createChain(pl_queue)`
+
This function returns the ID of chain that is of type `EPTF_NQueue_ChainId` which can later be used to reference the chain within the queue.

=== Creating Items

The following functions can be used to create a single item in a queue at either the head or tail of a chain, of after/before another item:

[source]
----
f_EPTF_NQueue_createItemAtChainHead(pl_queue, pl_chain)

f_EPTF_NQueue_createItemAtChainTail(pl_queue, pl_chain)

f_EPTF_NQueue_createItemAfter(pl_queue, pl_afterIdx)

f_EPTF_NQueue_createItemBefore(pl_queue, pl_beforeIdx)
----

These functions return the index of the created item (of type `EPTF_NQueue_ItemIdx`).

The following functions can be used to create more than one items at the same time:

[source,subs="quotes"]
----
f_EPTF_NQueue_createItem*s*AtChainHead(pl_queue, pl_chain, pl_count)

f_EPTF_NQueue_createItem*s*AtChainTail(pl_queue, pl_chain, pl_count)
----

These functions do not have a return value. The created items can be retrieved from the head or tail of the respective chain. These functions are identical to calling their single item creating counterpart in a for loop `pl_count` times (i.e. `createItemsAtChainHead` chains the new items in a reverse order).

=== Moving an Item to Head or Tail of Chain

The following functions can be used to move an item to the head or tail of the same or another chain:

[source]
----
f_EPTF_NQueue_moveToHead(pl_queue, pl_toChain, pl_item)

f_EPTF_NQueue_moveToTail(pl_queue, pl_toChain, pl_item)
----

The parameter `pl_toChain` is the target chain, and can be the same chain in which the item is before the move.

=== Moving an Item After or Before Another Item

The following functions can be used to move an item after or before another item:

[source]
----
f_EPTF_NQueue_moveAfter(pl_queue, pl_afterIdx, pl_item)

f_EPTF_NQueue_moveBefore(pl_queue, pl_beforeIdx, pl_item)
----

The parameter `pl_afterIdx` and `pl_beforeIdx` is the item index after or before which to move the item at `pl_item` respectively. The target chain of the item is the chain of the item after or before which it is moved to.

=== Getting the Chain of an Item

The following function returns the ID of the chain in which the item is linked:

`f_EPTF_NQueue_getChainOfItem(pl_queue, pl_item)`

=== Getting the Length of a Queue

The following function returns the length of (i.e. number of elements in) a queue:

`f_EPTF_NQueue_getLengthOfQueue(pl_queue)`

=== Getting the Length of a Chain

The following function returns the length of a chain:

`f_EPTF_NQueue_getLengthOfChain(pl_queue, pl_chain)`

=== Getting the Head Item of a Chain

The following function returns the index of the head (first) item in a chain or `_-1_` if the chain is empty:

`f_EPTF_NQueue_getHeadOfChain(pl_queue, pl_chain)`

=== Getting the Tail Item of a Chain

The following function returns the index of the tail (last) item in a chain or `_-1_` if the chain is empty:

`f_EPTF_NQueue_getTailOfChain(pl_queue, pl_chain)`

=== Iterating Through a Chain

The function `f_EPTF_NQueue_getNextItemIdx(pl_queue, pl_item)` can be used to iterate forward, `f_EPTF_NQueue_getPrevItemIdx(pl_queue, pl_item)` can be used to iterate backward through the busy chain from a given index. These functions modify the inout parameter `pl_item` in case there is a next or previous item, and return `_true_`. If there is no more items in the chain, they return `_false_`.

=== Logging Functions

Following functions can be used to log information about the queue for debugging:

`f_EPTF_NQueue_logQueue(pl_queue)`

`f_EPTF_NQueue_logChain(pl_queue, pl_chain)`

`f_EPTF_NQueue_logChainFields(pl_queue, pl_chain)`

=== Dumping a Queue to a PNG Image

The function `f_EPTF_NQueue_dumpToPng(pl_queue, pl_name)` can be used to save a queue as a digraph file and generate a PNG image using the tool 'dot' (which has to be installed to use this function, see <<_5, [5]>>). This is for testing purposes, the number of items in the queue should not be too large due to the limitations of 'dot'.

== Summary Table of All Public Functions for EPTF `NQueue`

See summary of `NQueue` functions in the table below:

[cols=",",options="header",]
|===================================================================
|Function name |Description
|`f_EPTF_NQueue_init_CT` |Initializes the `NQueue` feature
|`f_EPTF_NQueue_createQueue` |Creates a new queue
|`f_EPTF_NQueue_deleteQueue` |Deletes a queue
|`f_EPTF_NQueue_createChain` |Creates a chain in a queue
|`f_EPTF_NQueue_createItemAtChainHead` |Creates one item at chain head
|`f_EPTF_NQueue_createItemAtChainTail` |Creates one item at chain tail
|`f_EPTF_NQueue_createItemAfter` |Creates one item after another
|`f_EPTF_NQueue_createItemBefore` |Creates one item before another
|`f_EPTF_NQueue_createItemsAtChainHead` |Creates items at chain head
|`f_EPTF_NQueue_createItemsAtChainTail` |Creates items at chain tail
|`f_EPTF_NQueue_moveToHead` |Moves an item to chain head
|`f_EPTF_NQueue_moveToTail` |Moves an item to chain tail
|`f_EPTF_NQueue_moveAfter` |Moves an item after another
|`f_EPTF_NQueue_moveBefore` |Moves an item before another
|`f_EPTF_NQueue_getChainOfItem` |Returns the chain of the item
|`f_EPTF_NQueue_getLengthOfQueue` |Returns the length of the queue
|`f_EPTF_NQueue_getLengthOfChain` |Returns the length of a chain
|`f_EPTF_NQueue_getHeadOfChain` |Returns the head of a chain
|`f_EPTF_NQueue_getTailOfChain` |Returns the tail of a chain
|`f_EPTF_NQueue_getNextItemIdx` |Forward iterator
|`f_EPTF_NQueue_getPrevItemIdx` |Backward iterator
|`f_EPTF_NQueue_logQueue` |Logs the queue
|`f_EPTF_NQueue_logChain` |Logs a chain with items
|`f_EPTF_NQueue_logChainFields` |Logs the chain without items
|`f_EPTF_NQueue_dumpToPng` |Dumps the queue to PNG
|===================================================================

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

*NQueue:* +
It is a data type consisting of an arbitrary number of chains and an arbitrary number of items. Items in the queue are identified by their index, which has a continuous range and is thus useful for creating associated data structures by indexing a list of data with the item index.

*Chain:* +
It is a group of items in the queue. Each item belongs to a chain and can be moved to another chain. A chain is represented as a doubly linked list and can be iterated forward (head to tail) or backward (tail to head). A chain can, for example, be thought of as the state of its items (e.g. free/busy).

= Abbreviations

API:: Application Programming Interface

CLL:: Core Load Library

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

FIFO:: First In First Out

LIFO:: Last In First Out

PNG:: Portable Network Graphics

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] EPTF CLL Free Busy Queue, Function Description

[[_5]]
[5] www.graphviz.org +
open source graph visualization software