TwinCAT Dynamic Collections

A TwinCAT library for creating and manipulating dynamic collections of data in TwinCAT. It provides multiple data structures such as ArrayList (a dynamic array), List (a doubly linked list that is optimized for sequential access and mutation), Set, Map, Queue, Stack and more. Examples are in the project.

TwinCAT Dynamic Collections is written in Structured Text and is available under the MIT license. It is easy to use and can be integrated into any TwinCAT project.

Here are some of the features of Dynamic Collections:

• Fast and efficient

  The collections in the library use data structures and algorithms along with optimisations that make them well-suited for PLCs, allowing for fast and efficient access to data.

• Easy to use

  Collections follow a simple and intuitive interface for handling data.

• Extendable

  The library allows you to take advantage of interfaces, OOP principles, functions and internal types to allow you to create/extend/wrap functionally or even implement a data structure in your preferred algorithm. You can even optimise it for your particular use case e.g. choosing the number of buckets in a hash map/set.

Click here for releases/prerelease!

Function Blocks

• 👍 FB_Collection - Abstract class/Function Block that all collections inherit, contains many methods and base implementation for methods and properties for creating a collection. Implements I_Collection.

• 👍 FB_Array - An array that can store multiple datatypes whose size is fixed. Implements I_Array.

• 👍 FB_Array_List - A dynamic array that can grow and shrink as needed. Can store multiple types. Implements I_List.

• 👍 FB_List - A doubly linked list with iterator hint optimisation. Essentially the linked list keeps track of the node it last accessed. Iteration starts from the closest node (head, tail or last accessed) to the access/mutation index. This should result in sequential access times of O(1) and similar times for access/mutation on the same index. Can store multiple types. Implements I_List.

• 👍 FB_Hash_Map - A collection of key-value pair items implemented using a hash table with closed addressing. The hash function uses MurmurHash3. Keys and values can be retrieved as an immutable list (whose base is FB_Array_List) in no particular order. Can store multiple types. Implements I_Hash_Map which inherits I_Map.

• 👍 FB_Hash_Set - A collection that contains no duplicate items implemented using an iterative AVL Tree. The hash function uses MurmurHash3. Keys and values can be retrieved as an immutable list (whose base is FB_ArrayList) in no particular order. Can store multiple types. Implements I_Hash_Set which inherits I_Set.

• 👍 FB_Tree_Map - A collection of key-value pair items implemented using a hash table with closed addressing. Keys and values can be retrieved as an immutable list (whose base is FB_ArrayList) via 4 traversal methods; Inorder, Preorder, Postorder and Level Order. Can store multiple types. Implements I_Tree_Map which inherits I_Map.

• 👍 FB_Tree_Set - A collection that contains no duplicate items implemented using an iterative AVL Tree. Keys and values can be retrieved as an immutable list (whose base is FB_Array_List) via 4 traversal methods; Inorder, Preorder, Postorder and Level Order. Can store multiple types. Implements I_Tree_Set which inherits I_Set.

• 👍 FB_Tree_Multiset - A collection similar to a set except it allows for duplicate items implemented using an iterative AVL Tree. Keys and values can be retrieved as an immutable list (whose base is FB_Array_List) via 4 traversal methods; Inorder, Preorder, Postorder and Level Order. Can store multiple types. Implements I_Tree_Set which inherits I_Set.

• 👍 FB_Queue - A collection whose access/mutation of items is first-in, first-out whose base is FB_List. Can store multiple types. Implements I_Queue.

• 👍 FB_Stack - A collection whose access/mutation of items is last-in, first-out whose base is FB_List. Can store multiple types. Implements I_Stack.

• 👍 FB_Deque - (Pronounced as 'deck') Double-Ended Queue. A collection that supports the insertion and removal of items at the front and back. Its base is FB_List. Can store multiple types. Implements I_Deque.

• 👍 FB_Ordered_Hash_Set - A collection that maintains unique items while preserving their insertion order. Implemented using a hash table with closed addressing. Can store multiple types. Implements I_Hash_Set.

• 👍 FB_Ordered_Hash_Map - A collection that maintains key-value pairs with unique keys while preserving their insertion order. Implemented using a hash table with closed addressing. Can store multiple types. Implements I_Hash_Map.

Interface UML

Simple List Examples

Declarations:

fbArray      : FB_Array(3); // FB_Array(<number of items>)
fbArray_List : FB_Array_List(0); // FB_Array_List(<number of initial items>)
fbList       : FB_List; 

sData   : STRING := 'Cats'; // variable that holds string data
nData   : DINT := 1234567; // variable that holds 32-bit int data
stData  : ST_DATA := (bMammals := TRUE, sDescription := 'Twin cats'); // variable that holds struct data

// variable to store returned data same as, "bVar := TRUE"
sRTNData    : STRING;
nRTNData    : DINT;
stRTNData   : ST_DATA; 

Arr_Count,
Arr_List_Count,
List_Count : T_Capacity; // variables will hold the number of items in the collection

Implementation:

fbArray
    .Set(0, sData)
    .Set(1, nData)
    .Set(2, stData)
    .Reverse()
    .Get(2, sRTNData)
    .Get(1, nRTNData)
    .Get(0, stRTNData);
Arr_Count := fbArray._Count;

fbArray_List
    .Append(sData)
    .Append(nData)
    .Append(stData)
    .Swap(0,2)
    .Get(2, sRTNData)
    .Get(1, nRTNData)
    .Get(0, stRTNData);
Arr_List_Count := fbArray_List._Count;

fbList
    .Prepend(sData)
    .Prepend(nData)
    .Prepend(stData)
    .Get(2, sRTNData)
    .Get(1, nRTNData)
    .Get(0, stRTNData);

List_Count := fbList._Count;

Simple Queue and Stack Examples

FOR i := 0 TO 2 DO
    fbQueue.Enqueue(i);
    END_FOR

fbQueue.Reverse();

WHILE NOT fbQueue._Empty DO
    fbQueue.Get(Values[j]).Dequeue();
    fbStack.Push(Values[j]);
    j := j + 1;
    END_WHILE

WHILE NOT fbStack._Empty DO
    fbStack.Get(Values[k]).Pop();
    k := k + 1;
    END_WHILE

Simple Tree Set Example

Declarations:

fbSet : FB_Tree_Set; 

arnData,
arnItems : ARRAY[0..5] OF DINT := [3,1,2,1,3,2];
ipItems : I_Immutable_List;
Count : T_Capacity;

Implementation:

FOR i := 0 TO 5 DO
    fbSet.Insert(arnItems[i]);
    END_FOR

Count := fbSet._Count; // Value is 3

fbSet._Traversal := T_BST_Traversal.In_Order; // will get the values in ascending order

ipItems := fbSet.Get_Values();
ipItems
    .Get(0, arnItems[0])
    .Get(1, arnItems[1])
    .Get(2, arnItems[2]);

Simple Tree Map Example

Declarations:

fbTree_Map : FB_Tree_Map;
ipKeys     : I_Immutable_List;
ipValues   : I_Immutable_List;

arKeys        : ARRAY[0..6] OF WSTRING := ["qwerty","play","thomas","jerry","perry","sarah"];
arValues      : ARRAY[0..6] OF WSTRING := ["Cats","Dogs","Ravens","Mollies","Anaconda","Cow"]
arUpdate      : ARRAY[0..1] OF WSTRING := ["Python", ""];
arRTNData     : ARRAY[0..6] OF WSTRING; // Array to store values retrieved using a key
arTravData    : ARRAY[0..1] OF ARRAY[0..9] OF STRING; // array containg all keys and values
rmvdVal       : WSTRING;

Implementation:

// Insert data into map
fbTree_Map
       .Insert(arKeys[0], arValues[0])
       .Insert(arKeys[1], arValues[1])
       .Insert(arKeys[2], arValues[2])
       .Insert(arKeys[3], arValues[3])
       .Insert(arKeys[4], arValues[4])
       .Insert(arKeys[5], arValues[5]);

// Retrieve data using keys
fbTree_Map
       .Get(arKeys[0], arRTNData[0])
       .Get(arKeys[1], arRTNData[1])
       .Get(arKeys[2], arRTNData[2])
       .Get(arKeys[3], arRTNData[3])
       .Get(arKeys[4], arRTNData[4])
       .Get(arKeys[5], arRTNData[5]);

// Update a values of keys
fbTree_Map
       .Update(arKeys[1], arUpdate[0])
       .Update(arKeys[2], arUpdate[0]);

// Get and remove
fbTree_Map
       .Get(arKeys[3], rmvdVal)
       .Remove(arKeys[3]);

// Retrieve all keys and values
fbTree_Map._Traversal := T_BST_Traversal.Inorder; // Sets traversal method in which keys/values are to be retrieved.
ipKeys := fbTree_Map.Get_Keys();
ipValues := fbTree_Map.Get_Values();
FOR i := ipKeys._Begin TO ipKeys._End DO 
    ipKeys
        .Get_As_String(i, arTravData[0][i]);
    ipValues
        .Get_As_String(i, arTravData[1][i]); 
    END_FOR

Hash Map and Hash Set Declarations

Declarations:

fbHash_Map : FB_Hash_Map(0); // FB_Hash_Map(<number of initial buckets>)
fbHash_Set : FB_Hash_Set(0); // FB_Hash_Set(<number of initial buckets>)

Developer Notes

Version 1 (v1.x.x.x) is still a work in progress. It is not backward compatible with version 0 (v0.x.x.x). If you were using version 0 a new branch has been created for it and updates will only be for bug fixes.

Click here for the version 0 branch

As always feel free to contribute or report issues.

⚠ Important ⚠

The internally used memory is allocated from the router memory pool and is generated via _NEW and released via _DELETE at runtime. Please make sure you have enough router memory allocated for your use case.

Be careful when storing STRUCTs or FUNCTION BLOCKs that contain STRINGs or WSTRINGs. You may not be able to retrieve them with any search operation method that includes keys to retrieve a value in a map. This is because strings are null-terminated, so any junk characters after the null character are retained. Equality of STRUCTs and FUNCTION BLOCKs are checked using MEMCMP. For FUNCTION BLOCKs I recommend you store them using interfaces or pointers. For STRUCTs, clear any strings inside using MEMSET and set them to your chosen value before you store them. If you have questions I'm happy to answer them.