Latest news

Static Stack – A lightweight framework for embedded systems

No comments

This post is part of the Memory Control Structures series. Also, read the other posts in the series:

Hello my dear reader. Let’s keep talking about small efficient static data structures for use in embedded systems. Today we will present another structure derived from our circular Buffer, the Static Stack, in free translation of the English Static stack. As many should know the stack is one of the earliest data structures studied in the academic world, having the most diverse ways to implement list-based and dynamic memory allocation. The purpose of this paper is to add to these approaches an additional form of circular buffering, easy to manipulate.

What is Static Stack?

Static Stack is a variant that uses static allocation to reserve the memory that will be used to store data, ie it is not necessary to use functions to reserve memory during execution. All memory used by the structure will be reserved at compile time. The static stack, as well as the entire stack, has a LIFO-type data-insertion and deletion policy, which postulates: “The last data to enter the top of the stack will always be the first to be taken out.”

Basically, inverse to our Circular Queue (and Buffer), as the slots are filled they stack so that the most recently filled slot in relation to the others will be the first to be available for withdrawal. This operation is exactly the same as our processor uses to save variables and context during the operation of an operating system, through known push and pop instructions. The explanation regarding the operation of the battery can be illustrated in the figure below:

Figure 1: Stack operation

Use Case: Where do I apply a stack in general?

Although the processor already has a stack implementation in hardware, its use is restricted to the saving of variables and registers, as well as data used by the compiler that manages the function call system and context switching, so this stack has its very restricted use. With the use of a stack we can illustrate the case of the window manager for an application that uses a display (the popular TFT), let’s see the figure below:

Figure 2: Use of stack in display

Look, we have three overlapping windows. Now comes the question, which one makes sense to process first? Probably the user will be with his attention turned to the last opened window, being necessary to process it first, but we can not discard the others, being necessary, at the closing of the most recent, that we return the processing to the most recent window previous to this one , until all windows are processed, or closed. Notice that this performance policy has exactly the same form of stack operation.

Therefore, stacks are excellent for use in applications that need to save previous states temporarily, can also be used for allocation of fixed memory blocks, being an efficient and light alternative to the use of the traditional mechanism of dynamic memory allocation. Unusual uses of the stack are also located in automatons as state machines, the use of the stack allows previous states to be stored and at convenient times are unpinned or checked, in case an action depends on the previous state (s).

You spoke of a pile. And the static stack?

Static Stack as already mentioned is a version that does not need dynamic allocation, all its parameters are set at compile time, which requires the user to know how much memory (or slots) he needs to reserve. There are several ways to implement a static stack. The implementation presented here makes use of our known circular buffer to also gain protection against memory leak, implicit from circular buffers. Let’s look at the interface of our static stack below:

/**
 * @brief simple static stack demo for embedded systems
 */

#ifndef STATIC_STACK_H_
#define STATIC_STACK_H_

#include <stdbool.h>


/* static stack control structure */
typedef struct {
	unsigned char *data_buffer;
	int put_index;
	int get_index;
	int slot_size;
	int noof_elem;
	int slots_used;
}sstack_t;



/**
 * @brief insert data on top of queue
 */
int sstack_push(sstack_t *s, void *data, int size);

/**
 * @brief gets data on top of queue
 */
int sstack_pop(sstack_t *s, void *data, int *size);

/**
 * @brief check if stack is full
 */
bool sstack_full(sstack_t *s);

/**
 * @brief check if stack is empty
 */
bool sstack_empty(sstack_t *s);

/**
 * @brief flush the stack
 */
int sstack_flush(sstack_t *s);

/* declare a fully initialized stack control structure */
#define SSTACK_DECLARE(name, slot_len, elements) 		\
		unsigned char sstack_buffer_##name[(slot_len + sizeof(int)) * elements];	\
		sstack_t name = {				\
			.data_buffer = &sstack_buffer_##name[0],\
			.put_index = 0,				\
			.get_index = elements - 1,		\
			.slot_size = slot_len + sizeof(int),	\
			.noof_elem = elements,			\
			.slots_used = 0				\
		}

#endif /* STATIC_STACK_H_ */

The interface has the same form as those described in previous articles, we describe the control structure of our stack, and we provide data insertion and removal functions, where the entire policy is managed automatically, the check functions to be used when the stack is full and empty synchronization operations and during development, we also have the classic macro for declaration of the stack fully initialized and ready for use. Let’s look at the implementation now:

/**
 * @brief simple static stack demo for embedded systems
 */

#include <string.h>
#include "static_stack.h"

int sstack_push(sstack_t *s, void *data, int size){
	int ret = 0;
	unsigned char *ptr;

	if(s == NULL || data == NULL || size == 0) {
		/* check your parameters */
		ret = -1;
	} else {
		int mem_pos = s->put_index * s->slot_size;
		ptr = (unsigned char *)s->data_buffer;

		if(s->slots_used >= s->noof_elem|| size > s->slot_size) {
			/* stack full or not enough room for data*/
			ret = -1;
		} else {

			/* insert the size of byte stream */
			memcpy(&ptr[mem_pos], &size, sizeof(size));

			/* insert the byte stream on stack memory*/
			memcpy(&ptr[mem_pos + sizeof(size)], data, size);

			/* update memory indexes, a stack has
			 * policy based on LIFO data insertion and
			 * remotion, so both indexes walk, and always
			 * put_index is ahead of get_index by 1 slot
			 */
			s->put_index = (s->put_index + 1) % s->noof_elem;
			s->get_index = (s->put_index == 0 ?(s->noof_elem + 
                                                   ((s->put_index - 1) % s->noof_elem))
						    :(s->put_index - 1) % s->noof_elem);
			++s->slots_used;
		}
	}

	return(ret);
}

int sstack_pop(sstack_t *s, void *data, int *size){
	int ret = 0;
	unsigned char *ptr;

	if(s == NULL || data == NULL || size == NULL) {
		/* check your parameters */
		ret = -1;
	} else {
		int mem_pos = s->get_index * s->slot_size;
		ptr = (unsigned char *)s->data_buffer;

		if(s->noof_elem == 0) {
			/* stack empty...*/
			ret = -1;
		} else {

			/* gets the size of byte stream */
			memcpy(size,&ptr[mem_pos], sizeof(int));

			/* remove the byte stream from stack memory*/
			memcpy(data,&ptr[mem_pos + sizeof(int)], *size);

			/* update memory indexes, a stack has
			 * policy based on LIFO data insertion and
			 * remotion, so both indexes walk, and always
			 * put_index is ahead of get_index by 1 slot
			 */
			s->put_index = (s->put_index == 0 ?(s->noof_elem +
                                                            ((s->put_index - 1) % s->noof_elem))
							    :(s->put_index - 1) % s->noof_elem);

			s->get_index = (s->put_index == 0 ?(s->noof_elem + 
                                                           ((s->put_index - 1) % s->noof_elem))
							   :(s->put_index - 1) % s->noof_elem);
			--s->slots_used;
		}
	}

	return(ret);
}

bool sstack_full(sstack_t *s){
	bool ret = true;
	if(s == NULL) {
		/* check your parameters */
		ret = false;
	} else {
		ret = (s->slots_used >= s->noof_elem? true : false);
	}
	return(ret);
}

bool sstack_empty(sstack_t *s){
	bool ret = true;
	if(s == NULL) {
		/* check your parameters */
		ret = false;
	} else {
		ret = (s->slots_used == 0? true : false);
	}
	return(ret);
}

int sstack_flush(sstack_t *s){
	int ret = 0;
	if(s == NULL) {
		/* check your parameters */
		ret = -1;
	} else {
		s->slots_used = 0;
		s->get_index = s->noof_elem - 1;
		s->put_index = 0;
	}
	return(ret);
}

The LIFO policy is managed by lines 35, 56, and 72 through 76. Note that the update of the indexes is a bit more complicated than in systems that use FIFO policy, data entry and exit indexes go the same way, but they are together. The data output index always points to the first data available at the top of the stack, while the input data (put_index) points to the first free slot (since there is space), so the update of the first depends on the second. In the removal, unlike the FIFO method, that we simply increment the indexes, we need to make them “walk” in the opposite direction of the insertion, then we introduce to you reader the circular decrement operation, which has a special case that needs to be treated, or (put_index) has a value of zero, which generates the extra code for increment and decrement that appear in these lines.

Conclusion

In addition to structures with FIFO policy, we also have structures with LIFO policy, in today’s article we present one of the most popular, the stack or stack, we also provide the reader with a different approach to its implementation, based on something we already know of articles providing a lightweight, efficient and memory leak protected module. In the link, with the repository for GitHub, there is an example application that uses all the functions and demonstrates the basic use of our Static Stack. I hope this structure is useful. Good projects!

Links

Access here the repository in Github containing the implementation and example application.

FelipeStatic Stack – A lightweight framework for embedded systems

Leave a Reply