Stacks, queues and lists¶
Warning
In embedded systems with limited amounts of RAM you should typically avoid dynamic memory allocation. I.e. avoid the malloc() function. As an alternative to dynamic allocation, static allocation (i.e. compile time allocation) is possible. E.g by putting your data structures in an statically allocated array. Still for completeness several of the examples in this chapter uses dynamic memory allocation. High end microcontrollers, and especially microcontrollers running a operating system to manage memory could safely use this approach.
Memory allocation¶
Memory allocation is the process of reserving some part of the memory for a particluar purpose. We distinguish between static and dynamic allocation, where the former is compile time allocation, while the latter is run time allocation. Finally there is also automatic allocation, which is the allocation of memory for the variables when you enter a new functions, or more generally when you enter a new scope.
Static memory allocation¶
Variables with static allocation include global variables, file scope variables, and variables inside functions that are declared with the static modifier. The memory for these variables is reserved as long as your program is running, and it may not be resized.
Dynamic memory allocation¶
In the C standard we have four functions for dynamic memory allocation:
malloc()calloc()realloc()free()
C++ offers the new, and delete operators as a alternative to the C functions, but the C functions are also supported in C++.
The actual implementation of the memory allocation functions vary depending on the arcitecture, and operating system in use. On the AVR microcontroller a rather simple function is used: https://www.nongnu.org/avr-libc/user-manual/malloc.html
The following code illustrates how to dynamically allocate memory for 10 unsigned 32 bit integers. I.e. it allocates 320 bit, or 40 bytes.
uint32_t *ptr = (uint32_t *) malloc(10 * sizeof(uint32_t));
if (NULL == ptr) {
/* Handle could not allocate memory. */
} else {
/* Do something useful with the memory. */
free(ptr); /* Free the memory (on a MCU this will often cause memory fragmentation) */
ptr = NULL;
}
Custom memory allocation function¶
On microcontrollers with small amounts of RAM, dynamic memory allocation could be dangerous. As an alternative one may declare a static array, and write a special function to declare parts of the array for specific purposes. A lock on the function provides additional safety, it may be used to prevent allocation of more memory after the microcontroller has finished it’s initialization procedure.
#include <Arduino.h>
/*
* Literature: https://barrgroup.com/embedded-systems/how-to/malloc-free-dynamic-memory-allocation
*/
#define STATIC_BUFFER_SIZE 200
static uint8_t static_buffer[STATIC_BUFFER_SIZE];
static bool static_buffer_enabled = true;
size_t static_buffer_free = 0;
void *salloc(size_t size){
if(static_buffer_enabled){
if((static_buffer_free + size) > STATIC_BUFFER_SIZE){
return NULL;
}
void *next_block = &static_buffer[static_buffer_free];
static_buffer_free += size;
return next_block;
}
else {
return NULL;
}
}
void disable_salloc(){
static_buffer_enabled = false;
}
void setup() {
Serial.begin(9600);
}
void loop() {
uint32_t *testvar = (uint32_t*)salloc(sizeof(uint32_t));
uint32_t *testvar2 = (uint32_t*)salloc(sizeof(uint32_t));
*testvar = 324;
*testvar2 = 324324;
Serial.print("Test: ");
Serial.print(*testvar);
Serial.print("Test2: ");
Serial.print(*testvar2);
for(;;){
asm("NOP");
}
}
Linked List Data Structure¶
A linked list is a data structure where each element links to the next element using a pointer.
Manual assignment of elements in linked list¶
The following example shows a static implementation of a linked list, where the links are made by explicitly assigning addresses to the next pointers. This is not how you would do it in practice, it only serves to demonstrate the simplest possible list you could make.
#include <Arduino.h>
typedef struct node {
uint32_t value1;
uint16_t value2;
struct node *next;
} node_t;
void print_linked_list(node_t *head){
node_t *temp = head;
Serial.print("\t");
while (temp != NULL){
Serial.print("[(");
Serial.print(temp->value1);
Serial.print("), (");
Serial.print(temp->value2);
Serial.print(")]");
temp = temp->next;
Serial.print(" -> ");
}
}
void setup() {
Serial.begin(9600);
Serial.println("Linked list example.");
}
void loop() {
node_t node1, node2, node3;
node_t *head;
node1.value1 = 23;
node1.value2 = 34;
node2.value1 = 3;
node2.value2 = 4;
node3.value1 = 223;
node3.value2 = 14;
head = &node1;
node1.next = &node3;
node3.next = &node2;
node2.next = NULL;
print_linked_list(head);
for(;;){
asm("NOP");
}
}
Linked list demo with various useful functions¶
#include <Arduino.h>
typedef struct node {
uint32_t value1;
uint16_t value2;
struct node *next;
} node_t;
void print_linked_list(node_t *head){
node_t *temp = head;
Serial.print("\t");
while (temp != NULL){
Serial.print("[");
Serial.print(temp->value1);
Serial.print(", ");
Serial.print(temp->value2);
Serial.print("]");
temp = temp->next;
Serial.print(" -> ");
}
Serial.print("NULL");
}
/*
* Be cautious with the use of malloc on embedded systems with small
* amounts of RAM.
*/
node_t *create_new_node(uint32_t value1, uint16_t value2){
node_t *node = (node_t *) malloc(sizeof(node_t));
node->value1 = value1;
node->value2 = value2;
node->next = NULL;
return node;
}
node_t *insert_node_at_head(node_t **head, node_t *new_node){
new_node->next = *head;
*head = new_node;
return new_node;
}
void insert_node_after_node(node_t *node_to_insert_after, node_t *new_node){
new_node->next = node_to_insert_after->next;
node_to_insert_after->next = new_node;
}
node_t *find_node_by_value1(node_t *head, uint32_t value1){
node_t *temp = head;
while(temp != NULL){
if(temp->value1 == value1){
return temp;
}
temp = temp->next;
}
return NULL;
}
void setup() {
Serial.begin(9600);
Serial.println("Linked list example.");
}
void loop() {
node_t *head = NULL;
node_t *temp;
for(uint8_t i = 0; i < 30; i++){
temp = create_new_node(i*i, i);
insert_node_at_head(&head, temp);
}
node_t *goal = find_node_by_value1(head, 81);
insert_node_after_node(goal, create_new_node(8154,93));
print_linked_list(head);
Serial.println("Søker etter 484...");
node_t *resultat = find_node_by_value1(head, 484);
Serial.print("Fann: ");
Serial.print(resultat->value1);
Serial.print(" - ");
Serial.print(resultat->value2);
for(;;){
asm("NOP");
}
}
Stacks¶
A stack is a data structure which follows the last in first out (LIFO) strategy, i.e the last added element to the stack must be the first to leave. Two fundamental operations push, and pop are supported by the stack. The push operation adds a new element on to the stack, while the pop operation removes a element, returning the element to the user. In addidion a third operation peek is often supported, in order to look at the top element in the stack without removing it.
Stacks are used by many different algorithms. Typical examples include balancing of symbols, infix to postfix/prefix conversion, and undo commands of editors.
Example with statically allocated memory¶
/**
* Stack implementation with static memory allocation.
*
* In this implementation the pop, and peek operations returns zero
* if the stack is empty. This is not a good solution if the elements you
* push to the stack sometimes have a value of zero.
*/
#include <Arduino.h>
typedef uint32_t stack_element_t;
struct stack {
stack_element_t *data;
int16_t top;
int16_t size;
};
const uint8_t stack_size = 50;
stack_element_t stack_elements[stack_size];
struct stack mystack = {.data = stack_elements, .top = -1, .size = stack_size};
stack_element_t pop(){
stack_element_t data;
if(mystack.top == -1){
data = 0;
} else{
data = mystack.data[mystack.top--];
}
return data;
}
stack_element_t peek(){
if(mystack.top >= 0){
return mystack.data[mystack.top];
}
else {
return 0;
}
}
void push(stack_element_t element){
if(mystack.top < mystack.size){
mystack.data[++mystack.top] = element;
}
}
void setup() {
Serial.begin(9600);
Serial.println("Simple stack example with static memory allocation.");
}
void loop() {
Serial.println("Pushing some values.");
push(54);
push(44);
push(94);
push(44);
push(14);
push(55);
push(8154);
push(9300);
Serial.println("Taking a peek:");
Serial.println(peek());
Serial.println("Popping them back:");
for(uint8_t i = 0; i < 10; i++){
Serial.println(pop());
}
/* Stop here */
for(;;){
asm("NOP");
}
}
Dynamic memory allocation stack example¶
#include <Arduino.h>
typedef uint32_t stack_element_t;
typedef struct {
stack_element_t *data;
int16_t top;
int16_t size;
} stack_t;
stack_t *init_stack(uint16_t size){
stack_t *stack_pointer = (stack_t*)malloc(sizeof(stack_t));
if(stack_pointer != NULL){
stack_element_t *temp = (stack_element_t*)malloc(sizeof(stack_element_t) * size);
if(temp != NULL){
stack_pointer->data = temp;
stack_pointer->top = -1;
stack_pointer->size = size;
return stack_pointer;
}
}
free(stack_pointer);
return NULL;
}
bool pop(stack_t *stack_pointer, stack_element_t *data){
/* Check for stack underflow, i.e. if stack is empty. */
if(stack_pointer->top == -1){
*data = 0;
return false;
}
else {
*data = stack_pointer->data[stack_pointer->top--];
return true;
}
}
bool peek(stack_t *stack_pointer, stack_element_t *data){
/* Check for stack underflow, i.e. if stack is empty. */
if(stack_pointer->top == -1){
*data = 0;
return false;
}
else {
*data = stack_pointer->data[stack_pointer->top];
return true;
}
}
bool push(stack_t *stack_pointer, stack_element_t data){
if(stack_pointer->top == (stack_pointer->size - 1)){
/*
* If the stack is full, double the size of the stack.
*/
stack_element_t *temp = (stack_element_t*)malloc(sizeof(stack_element_t) * stack_pointer->size * 2);
if(temp == NULL){
return false;
}
for(int16_t i = 0; i < stack_pointer->size; i++){
temp[i] = stack_pointer->data[i];
}
free(stack_pointer->data);
stack_pointer->data = temp;
stack_pointer->size *= 2;
}
stack_pointer->data[++stack_pointer->top] = data;
return true;
}
void setup() {
Serial.begin(9600);
Serial.println("Dynamic stack example.");
}
void loop() {
stack_t *stack1 = init_stack(5); // Init stack with room for 5 elements.
stack_element_t temp;
push(stack1, 3);
push(stack1, 5);
push(stack1, 329);
push(stack1, 39);
push(stack1, 2339);
push(stack1, 815);
push(stack1, 493);
push(stack1, 0);
push(stack1, 0);
Serial.print("Peek: ");
if(peek(stack1, &temp)){
Serial.println(temp);
}
else {
Serial.println("<empty>");
}
Serial.println();
Serial.println("Pop all elements from stack:");
for(uint8_t i = 0; i < stack1->size; i++){
if(pop(stack1, &temp)){
Serial.print("Data: ");
Serial.println(temp);
}
}
for(;;){
asm("NOP");
}
}
Queues¶
A queue is a data structure which follows the first in first out (FIFO) strategy. The fundamental operations are enqueue, and dequeue.
Queues are used for enqueuing of operations, or events. E.g. if several events happen before the controller is able to process them, they should be processed in the same order that they occured.
One example is the receive and transmit buffers used by the Serial library for
UART communication in the Arduino. E.g. for reception, a RX complete interrupt is used to place the
next received byte in the queue, while Serial.read() retrives the oldest byte from the queue.
Static queue Arduino example¶
The following example uses a statically allocated array for the queue. The array will be filled at the tail, and data will be removed at the head. This eventually uses up all the allocated memory, as the free memory at the front of the queue is unavailable. There are many ways to address this problem, but for simplicity this first example ignores the problem.
/**
* Simple FIFO queue with static memory allocation.
*
* This example is intended to demonstrate a problem, and thus it should
* not be used in any application.
*
* The problem is that the memory that is free after you dequeue is not made available
* for adding new elements. One possible solution is to use a circular queue.
*/
#include <Arduino.h>
typedef int32_t queue_data_t;
const uint8_t queue_size = 50;
struct queue {
queue_data_t *data;
uint8_t head;
uint8_t tail;
uint8_t size;
};
queue_data_t queue_data[queue_size];
struct queue myqueue = {.data = queue_data, .head = 0, .tail = 0, .size = queue_size};
bool is_empty();
void enqueue(queue_data_t data);
queue_data_t dequeue();
void print_queue();
bool is_empty(){
if(myqueue.head == myqueue.tail){
return true;
}
else {
return false;
}
}
void enqueue(queue_data_t data){
if(myqueue.tail < myqueue.size){
myqueue.data[myqueue.tail++] = data;
}
}
queue_data_t dequeue(){
if(!is_empty()){
return myqueue.data[myqueue.head++];
}
return 0;
}
void setup() {
Serial.begin(9600);
Serial.println("Simple queue with static memory allocation.");
}
void loop() {
enqueue(234);
enqueue(24);
enqueue(134);
enqueue(243);
enqueue(874);
enqueue(527);
Serial.println("Dequeueing: ");
for(uint8_t i = 0; i < 10; i++){
Serial.println(dequeue());
}
enqueue(1234);
enqueue(4321);
enqueue(904);
enqueue(2123);
enqueue(8724);
enqueue(1527);
enqueue(527);
enqueue(27);
enqueue(7);
Serial.println("Dequeueing: ");
for(uint8_t i = 0; i < 10; i++){
Serial.println(dequeue());
}
for(;;){
asm("NOP");
}
}
Dynamic queue Arduino example¶
When enqueueing a new element the following example will allocate the memory dynamically. It is not the recommended approach for systems with limited memory, you should at least add a limit for the maximum memory allocation.
#include <Arduino.h>
typedef struct {
uint32_t number;
uint32_t another_number;
char string[5];
} queue_data_t;
typedef struct queue_node {
queue_data_t *data;
struct queue_node *next;
} queue_node_t;
typedef struct {
queue_node_t *head;
queue_node_t *tail;
} queue_t;
queue_t *init_queue();
bool is_empty();
bool enqueue(queue_t q, queue_data_t data);
void dequeue(queue_t q, queue_data_t *data);
void print_queue();
queue_t *init_queue(){
queue_t *new_queue = (queue_t*)malloc(sizeof(queue_t));
if(new_queue != NULL){
new_queue->head = NULL;
new_queue->tail = NULL;
}
return new_queue;
}
bool is_empty(queue_t *q){
return (q->head == NULL);
}
/**
* @brief Enqueue a new node.
*
* @param q The queue struct
* @param data The data structure to enqueue
* @return true Memory allocation was succesfull
* @return false Memory allocation failed
*/
bool enqueue(queue_t *q, queue_data_t data){
queue_node_t *new_node = (queue_node_t*)malloc(sizeof(queue_node_t));
queue_data_t *new_data = (queue_data_t*)malloc(sizeof(queue_data_t));
if(new_data != NULL){
*new_data = data;
}
if(new_node != NULL){
new_node->data = new_data;
new_node->next = NULL;
if(is_empty(q)){
q->head = new_node;
q->tail = new_node;
}
else{
q->tail->next = new_node;
q->tail = new_node;
}
return true;
}
return false;
}
/**
* @brief Dequeue a node, and free the memory
*
* @param q The queue struct
* @param return_data Pointer to the struct where the dequeued data should be placed
* @return true Successfully dequeued a node
* @return false Queue is allready empty
*/
bool dequeue(queue_t *q, queue_data_t *return_data){
if(is_empty(q)){
return false;
}
queue_node_t *head = q->head;
queue_data_t *data = q->head->data;
*return_data = *data;
q->head = q->head->next;
free(head);
free(data);
return true;
}
void print_queue(queue_t *q){
queue_data_t data;
Serial.println("--");
while(!is_empty(q)){
dequeue(q, &data);
Serial.print("[ ");
Serial.print(data.number);
Serial.print(", ");
Serial.print(data.another_number);
Serial.print(", ");
Serial.print(data.string);
Serial.print("] -> ");
}
Serial.println("--");
}
void setup() {
Serial.begin(9600);
}
void loop() {
queue_t *testqueue = init_queue();
queue_data_t testdata = {34, 53, "Test"};
enqueue(testqueue, testdata);
enqueue(testqueue, {334,4, '\0'});
//char text[] = "asdf";
//enqueue(testqueue, {7823, 324, text});
//enqueue(testqueue, {321,324, "jkds"});
print_queue(testqueue);
for(;;){
asm("NOP");
}
}