How Are Data Structures Useful In Embedded Systems?

C programes  |     |  

How are data structures useful in embedded systems

Blog Contents

Data Structures in Embedded Systems

This is a very common question my student is asking when we are data structure class for them. When a student joins embedded system training in our institute the data structure is not required an embedded system.
So we thought to write details description of where the data structure is used in the embedded world, so it will help another student across the world who can’t join embedded system training in Bangalore, India.
In the embedded system we are processing a large amount of data from Sensors/devices like ADC, accelerometer/gyro meter, data logger. Normally these data come to the microcontroller using UART, IIC, SPI, or Internal reading of registers like in case of internal ADC register. You can read our post which is talking about many types of sensors in an embedded system.

Most of the time data is updated in the microsecond or millisecond. It means a lot of data, so defiantly we have to save these data in the data structure. First, we will see what mechanism available in C language to save data, and then we will go through the real-time examples which type of data is saved into which type of data structure practically.

Different Data Structure in C

Data structures are arrays, structure, union, files, queues, stack, Linked lists, binary trees etc.

Arrays

To store a single data we use variables. To store a large number of data of the same data type we use arrays. The array is a collection of the same data type variable. In array, memory is allocated continuously.

Arrays can be a single dimension or multi-dimensions.
The size of the array is declared while declaring the array data type. It means we can’t change the size of the array run time. Here are the examples of Array
ex: int arr[5]; if starting address of arr is 0x7890, here we consider integer is 4 bytes long, then the array will be saved following ways.

Address of arr[0] is 0x7890
Address of arr[1] is 0x7894
Address of arr[2] is 0x7898
Address of arr[3] is 0x789c
Address of arr[4] is 0x78a0

Practical Example:

int AdcValue[100]: Read ADC value and save it into an array. Data will be read and save into an array.
float Temperature [50]: Here we are saving the temperature of the wheel and saving it into an array. We will take an average of all 50 elements and then find the average.
char UserName[40][20]: Here save 40 user name into an array, each size is 20 bytes long maximum.

Structure:

The structure is a group of different or same data type elements. In structure, we can have a float, int, char, etc data types grouped together. The memory allocated to structure elements is continuous, the first element occupies the memory address equal to the structure address, and next it stores the second element in memory.

Example:

struct Sen
{
char ch;
float receiveddata;
short count;
} senvar;

Here the sizeof structure senvar is 12 bytes, but if we calculate individual variable sizes than it becomes 1+4+2= 7 bytes. This is because the 32 bit systems stores the data in 32 bit aligned. First, if it stores character then if it stores float 4-byte size, then it would not store the data next to the character since if it stores then 4 bytes not stored in one 4 byte sequence. 3 bytes stored in one row and 1 byte in another row.

Example:
structure start address 0xffff5560
char ch stored at 0xffff5560
flaot receiveddata stored at 0xffff5564
short count stroed at 0xffff5568

So to save the memory while declaring the data in a structure we keep the elements aligned to 4 bytes size all integers, floats at one place then characters and short integers another place.
using structure packing instruction to the compiler we pack the data nest to each other for GCC compiler with code blocks you can use #pragma pack(1) to pack the structure.

Structure with bitfields:

To store the data in bit or bitfield of a memory we use structure fields.
In microcontroller we use registers, to access the bitfields of the register we can use structure/union bitfields.

Example:
struct reg{
unsigned int bit1:1;
unsigned int bit2:1;
unsigned int bitfield1:4;
unsigned int bitfield2:7;
unsigned int bitfield3:9;
unsigned int bitfield4:5;
unsigned int bitfield4:5;
} controlreg1;
here the bit1 is the bit name, 1 is the size of the bit
here the bitfield1 is the bitfield name, 4 is the size of the bitfield, etc.

Union:

The union also can be used to store the variables of different data types. Here all the data stored in the same memory location, the size of the union is equal to the biggest variable data it is holding.
we can also use the union to access both the register and bitfields.
Example: for example, we can define the structure in a union to access both register and
bitfields.
union {
unsigned int reg32;
struct {
unsigned int b1:6;
unsigned int b2:4;
unsigned int b3:6;
unsigned int b4:8;
unsigned int b5:8;
};
}reg2;

Practical Example:

typedef struct
wpan_endpoint_table_entry_t
{
/// Endpoint ID, 0 to 254 255 (0xFF) is used as an end-of-//table marker.
uint8_t endpoint;
/// This endpoint’s profile ID. See WPAN_PROFILE_* macros //for
some known profile ids
uint16_t profile_id;
/// Function to receive all frames for invalid clusters, or //clusters
with a \c handler.
wpan_ep_handler_fn handler;
/// Structure used to track transactions and conversations on
//ZDO/ZDP and
struct wpan_ep_state_t FAR *ep_state;
/// This endpoint’s device ID.
uint16_t device_id;
//Lower 4 bits are used, upper 4 are reserved and should 0
uint8_t device_version;
const wpan_cluster_table_entry_t *cluster_table;
} wpan_endpoint_table_entry_t;

Stack:

The stack is a first in Last out FILO concept. It is like we put the books one above the other than picking it from the top one after the other. we will be storing the data to stack by push() operation and data retrieving are done by pop() function.

Example program to create a stack structure:

The stack is normally used in the embedded system to saved the return of function and local variables.

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 2
struct Stack
{
int data;
struct Stack *next;
}*top;
typedef struct Stack stack;
int count =0;
int main()
{
push(20);
push(10);
disp();
pop();
pop();
pop();
free(top);
return 0;
}

void push(int d)
{
stack *newdata;
if(++count > MAXSIZE)
{
printf(“\n stack is full”);
return 0;
}
newdata= (stack *)malloc(sizeof(stack));
newdata->data = d;
newdata->next=top;
top=newdata;
}
void pop()
{
if(–count == -1)
{
printf(“\n stack is empty”);
return 0;
}
printf(“\ndata popped is = %d”, top->data);
top=top->next;
}

disp()
{
stack *ptr;
for(ptr=top; ptr; ptr=ptr->next)
printf(“\n%d “, ptr->data);
}

Queue Structure:

Queue structure is the FIFO concept first in first out data type. It is similar to the queue of a people standing to collect the ticket in front of a counter. Here the first person standing in front of the queue takes the ticket first, and the next person takes the ticket next.it goes on. In Queue data structure also the first data stored will be read back first and the last data stored will be read last.

Here Is The Practical Example Of A Queue

1. Declare A Queue

/* Declare a variable of type xQueueHandle. This is used to store the queue * that is accessed by all three tasks. */
static xQueueHandle gCellMesgQueue;
/* The queue is created to hold a maximum of 3 structures of type TaskMesg. */
gCellMesgQueue = xQueueCreate( 16, sizeof( TaskMesg ) );

2. Update queue when we received a message

And This is how we put message into queue
if(gCellTaskStarted)
{
cellTaskMesg.id = id;
cellTaskMesg.data = data;
xStatus = xQueueSendToBackFromISR( gCellMesgQueue, &cellTaskMesg,
&xHigherPriorityTaskWoken );
Once we received message into ISR we can update queue. This activity is asynchronous and whenever message received then we update into queue.

3. Continuously check the available message into a queue and take action

for( ;; )
{
if( uxQueueMessagesWaiting( gCellMesgQueue ) == 16 )
{
}
xStatus = xQueueReceive( gCellMesgQueue, &recvCellTaskMesg, 10
/*portMAX_DELAY*/ );
if( xStatus == pdPASS )
{
/* Data was successfully received from the queue, print out the received
* value and the source of the value. Based on received message id take
* action*/
switch( recvCellTaskMesg.id)
{
case E_CELL_TASK_MESG_ID_CELL_RX_BUF_RDY:
//vPrintStringAndNumber( “From Sender 1 = “, recvCellTaskMesg.id );
// for testing we can print message id and check.
CellTaskProcessRxBuf();
break;
case MESG_ID_CELL_STATE_TMR_EVT:

CellStateTimeout();
break;
case MESG_ID_CELL_MDM_RESET:
CellCommand_CmdReset(1);
……….
………
Like this based on message id we can take different action.

Linked Lists:

Arrays use the fixed memory and it allocates memory during compile time.
Linked lists are the data structures, the memory for these is allocated during run time means while the program is running.
Here how much data we want that much memory only we are going to allocate.
No memory is wasted. Extra memory is not allocated.
There are two types of linked lists, one is a singly linked list and another is a doubly-linked list.

Singly Linked List:

The singly-linked list means data is stored in the structural element and one pointer is pointing to the next data structure. Like this, the data structure nodes will be added and the size of the list increases.

Data Structures in embedded system, Singly Linked List:

Doubley Linked List:

Data is stored in data structure and it is having two pointers. One pointer pointing to the next element and the other pointer pointing to the previous element. We traverse the list in both directions one is starting to end called forward direction and the other is an end to start called reverse direction.

Doubley linkted list, data structure

Here is a practical example of link-list in embedded system

if (Alarm_list->Counter > 1) {
for(i = 0;i < Alarm_list->Counter-1;i++) {
for(j = 1;j < Alarm_list->Counter;j++) {
if (Alarm_list->plog[j].uStamp > Alarm_list ->blog[i].uStamp) {
u32SortTick = Alarm_list ->blog[i].uStamp;
u32SortCode = Alarm_list ->blog[i].u16EvtCode;
Alarm_list ->plog[i].uStamp = Alarm_list ->blog[j].uStamp;
Alarm_list ->plog[i].u16EvtCode = Alarm_list ->blog[j].u16EvtCode;
Alarm_list ->plog[j].uStamp = u32SortTick;
Alarm_list ->plog[j].u16EvtCode = u32SortCode;
}
}
}

Here Alarm_list is the list, as and when we get some alarm we make new node and update the information into the list, on the other side of code we are continuously monitoring the list, and if an alarm is generated for any of the thread then we process at a centralized location.

Binary Trees:

The data structure is arranged like a tree. The first node is called the root and the next it will connect to elements one is left and the other is right. A node above it is called the parent node and below the above node is called child nodes. The nodes at the end of the tree are called leaves of the tree.

Normally binary tree is used to sorting the data, more frequently is used where continuously data is coming and going, and always we need to present into sorting. Here we have shown many data structures, which are frequently used embedded systems. In this document, we are shown particle and real-time example code which I had written during my professional career. You can consider the following points while choosing data types in your projects.

Array:

When similar data type needs to save multiple numbers, like ADC value, temperature data, per minute motor revolution count, etc.

Structure

When we need multiple data type need to save and maintain. For example, if we read voltage, current, power factor time, etc. Another example is Task status, last action status, the command sent, the last response received, etc.

Structure Bit filed

In embedded bit filed is widely used, like consider we are updating Bit filed data bitwise also the possibility of data update on full integer. Like
Typedef volatile
struct
_ARM_I2C_STAT
US {
uint32_t busy : 1; ///< Busy flag
uint32_t mode : 1; ///< Mode: 0=Slave, 1=Master
uint32_t direction : 1; ///< Direction: 0=Transmitter,
1=Receiver
uint32_t general_call : 1; ///< General Call indication
(cleared on start of next Slave operation)
uint32_t arbitration_lost : 1; ///< Master lost arbitration
(cleared on start of next Master operation)
uint32_t bus_error : 1; ///< Bus error detected (cleared
on start of next Master/Slave operation)
uint32_t reserved : 26;
} ARM_I2C_STATUS;

Nested Union and Structure

Consider we have to read data from EEPROM byte by byte serially and saved them such a way that while using we want to use in a group of 4,4 bytes. In this case, we can make data structure which is nested with union and structure, as shown below
structure meter_Data{
unsigned int Voltage[2];
unsinged int Current[2];
char Hour;
char Min;
char Sec;
char Day;
};
union read_memory{
unsinged char readbytes[20];
structure meter_Data myMeter;
};
Now union read_memory can be used to read data one by one and while using we can use them as a group of 4 bytes which is an integer or as one byte which is character.

Binary Tree

The binary tree is used when the number of data is entering and leaving, Tree and we need to present always data into sorted order.

Here is a Professional Training Institute which is famous for practical embedded training, we focus on Data structure in practical ways. Our training methods are one on one which leads us to focus on each and every student and give them a complete practical training on C and Data structure. So if you are looking for embedded systems training in Bangalore then come and meet us once to explore in detail. We provide job oriented embedded system training and help our students until their job.