Hello everyone, I am a ruffian balance, is a serious technical ruffian. Ruffian balance to you today is embedded stack principle and its pure C implementation.
Today we share this article or before 2016 ruffian Balance wrote technical documents, took some time to rearrange the format. Stack this structure are commonly used in embedded, such as the function call and return is a typical application stack, although most of the time the stack are CPU in the automatic management system, we only need to distribution in the link to the file size and stack location, but to understand a little bit about the stack will be more conducive to us to understand the principle of the embedded code execution mechanism, And help us debug further.
1. What is stack?
HEAP and STACK are two different concepts, which are essentially a kind of data structure. A stack is a data structure arranged by data items. Data items can only be inserted or deleted at one end (top of the stack), which complies with the last-in/first-out principle. The stack (OS) is typically allocated and released automatically by the compiler, using a level 1 cache. A heap is also a data structure that is allocated like a linked list and can operate on items anywhere. The heap (OS) is typically allocated and released manually by the programmer using a level 2 cache. In the embedded world, stack generally means just stack.
2. Function and significance
In MCU, the stack structure is commonly used by the CPU and OS. There are two ways to use it in the BARE CPU: first, STACK is used to temporarily store the address of an instruction, function parameters and local variables defined in the function when the function is called. Second, when the hard interrupt comes, the current execution of the field data (the address of the next instruction, all kinds of cache data) is temporarily saved, after the interruption, for recovery. When used in OS, the use of hard stack is the same as CPU bare machine; However, the OS generally allocates an extra soft stack for each task. During task scheduling, soft interrupts can be used to interrupt the currently executing task, and the stack can be used to save their respective tasks for recovery.
3. Soft versus hard
Hardware stack: is the address of the index pointer through register SP, which is automatically filled by the hardware after calling the function call instructions such as BL. Software stack: A stack created by the compiler to handle some parameter passing. It is automatically generated and processed by the compiler and can be edited with the appropriate compilation options. To put it simply, the hardware stack is primarily used as an address stack, while the software stack is primarily allocated as a data stack. Or to see if the pointer to the top of the stack has a special association with the CPU, the associated (such as SP) “hard”, and the unassociated “soft”.
4. Pure C implementation of stack
Basic abstract data types (ADTs) are necessary to write C programs. These ADTs include linked lists, stacks, queues, and trees. This section focuses on several implementations of stack and their advantages and disadvantages. A stack (stack) is characterized by last-in first-out (LIFO), which can be implemented In three options: static array, dynamically allocated array, and dynamically allocated chain structure.
Static arrays: Features that require structures of a fixed length that must be determined at compile time. Its advantages are simple structure, easy to implement and not easy to make mistakes. The disadvantage is not flexible enough and fixed length is not easy to control, suitable for the occasion of knowing a clear length. Dynamic arrays: Features that the length can be determined at run time and the length of the original array can be changed. The advantage is flexibility, but the disadvantage is that this increases the complexity of the program. Chain structure: features no length line, when the need to apply for allocation of memory space, can achieve maximum flexibility. The disadvantage is that the linked fields of a chained structure consume a certain amount of memory, and accessing a particular element in a chained structure is not as efficient as accessing an array.
Start with a stack interface header file, which contains the prototype functions for each scenario, put together to make the program modular and easy to modify. Then the specific implementation methods of each scheme are introduced respectively. Stack interface stack.h file code:
1./* 2.** Stack module interface stack.h 3.*/
4.#include<stdlib.h>
5.
6.#define STACK_TYPE int /* The data type of the value stored in the stack */
7.
8.10.** Creates a stack that specifies how many elements the stack can hold. ** Note: This function only works with dynamically allocated arrays. 12. * /
13.void create_stack(size_t size);
14.
15.17.** Destroy a stack, freeing the memory to which it belongs. ** Note: This function only works with dynamically allocated arrays and chained stacks. 19. * /
20.void destroy_stack(void);
21.
22.** Pushes a new value onto the stack. The argument is the value being pushed. 25. * /
26.void push(STACK_TYPE value);
27.
28./* 29.** Function prototype: pop 30.** Pops a value at the top of the stack and discards it. 31. * /
32.void pop(void);
33.
34.** Returns the value of the element at the top of the stack, but does not change the stack structure. 37. * /
38.STACK_TYPE top(void);
39.
40.** Returns TRUE if the stack is empty, FALSE otherwise. 43. * /
44.int is_empty(void);
45.
46.** Returns TRUE if the stack is full, FALSE otherwise. 49. * /
50.int is_full(void);
Copy the code4.1 Static Array
In a static array stack, STACK_SIZE represents the maximum number of elements that can be stored on the stack, and top_element is used as an array subscript to represent the elements in the stack. When top_element == -1, the stack is empty. When top_element == stack_size-1, the stack is full. Push top_element increments by 1, top_element == 0 represents the first stack element; When pop, top_element decreases by 1. A_stack. c source code is as follows:
1./* 2.** 3.** static array implementation stack program a_stack.c, array length determined by #define 4
5.
6.#include"stack.h"
7.#include<assert.h>
8.#include<stdio.h>
9.
10.#define STACK_SIZE 100 /* Stack maximum number of elements */
11.
12./* 13.** Stores the array in the stack and a pointer to the element at the top of the stack
15.static STACK_TYPE stack[STACK_SIZE];
16.static int top_element = - 1;
17.
18./* push */
19.void push(STACK_TYPE value)
20.{
21.assert(! is_full());/* Check whether the stack is full before pushing onto the stack */
22. top_element += 1;
23. stack[top_element] = value;
24.}
25.
26./* pop */
27.void pop(void)
28.{
29.assert(! is_empty());/* Check if the stack is empty before popping it */
30. top_element -= 1;
31.}
32.
33./* top */
34.STACK_TYPE top(void)
35.{
36.assert(! is_empty());37. return stack[top_element];
38.}
39.
40./* is_empty */
41.int is_empty(void)
42.{
43. return top_element == - 1;
44.}
45.
46./* is_full */
47.int is_full(void)
48.{
49. return top_element == STACK_SIZE - 1;
50.}
Copy the code4.2 Dynamic Array
The header file is still stack.h, not much changed, adding the stack_size variable instead of stack_size to hold the stack length, and replacing the array with a pointer that defaults to 0 under global variables. The create_stack function first checks that the stack has been created, and then allocates the required amount of memory and checks that the allocation was successful. The destroy_stack function first checks to see if the stack exists and, after releasing memory, resets the length and pointer variables to zero. An assertion is added to the is_Empty and is_full functions to prevent any stack function from being called before the stack has been created. D_stack. c source code is as follows:
1.3.** The length of the stack is given when the function that creates the stack is called, and this function must be used before any other function that operates on the stack is called. 4. * /
5.#include"stack.h"
6.#include<stdio.h>
7.#include<malloc.h>
8.#include<assert.h>
9.
10.** The array used to store stack elements and the pointer to the element at the top of the stack 12.*/
13.static STACK_TYPE *stack;
14.static int stack_size;
15.static int top_element = - 1;
16.
17./* create_stack */
18.void create_stack(size_t size)
19.{
20. assert(stack_size == 0);
21. stack_size = size;
22. stack = (STACK_TYPE *)malloc(stack_size * sizeof(STACK_TYPE));
23. if(stack= =NULL)
24. perror("Malloc allocation failed");
25.}
26.
27./* destroy */
28.void destroy_stack(void)
29.{
30. assert(stack_size > 0);
31. stack_size = 0;
32. free(stack);
33. stack = NULL;
34.}
35.
36./* push */
37.void push(STACK_TYPE value)
38.{
39.assert(! is_full());40. top_element += 1;
41. stack[top_element] = value;
42.}
43.
44./* pop */
45.void pop(void)
46.{
47.assert(! is_empty());48. top_element -= 1;
49.}
50.
51./* top */
52.STACK_TYPE top(void)
53.{
54.assert(! is_empty());55. return stack[top_element];
56.}
57.
58./* is_empty */
59.int is_empty(void)
60.{
61. assert(stack_size > 0);
62. return top_element == - 1;
63.}
64.
65./* is_full */
66.int is_full(void)
67.{
68. assert(stack_size > 0);
69. return top_element == stack_size - 1;
70.}
Copy the code4.3 Chain structure
Because only the element at the top of the stack can be accessed, a single linked list works well for a chained stack with no length restrictions. Pushing an element onto the stack is done by adding an element to the head of the list. Popping an element is done by deleting the first element in the list header. Since there is no length limit, you don’t need the create_STACK function. Instead, you need destroy_stack to free up memory to avoid a memory leak. L_stack.c source code is as follows:
1./* 2.** Single list implementation stack, no length limit 3.*/
4.#include"stack.h"
5.#include<stdio.h>
6.#include<malloc.h>
7.#include<assert.h>
8.
9.#define FALSE 0
10.
11./* 12.** Defines a structure to store stack elements. 13. * /
14.typedef struct STACK_NODE15. {
16. STACK_TYPE value;
17. struct STACK_NODE *next;
18.} StackNode;
19.
20./* A pointer to the first node in the stack */
21.static StackNode *stack;
22.
23./* create_stack */
24.void create_stack(size_t size)
25.{}
26.
27./* destroy_stack */
28.void destroy_stack(void)
29.{
30. while(! is_empty())31. pop(); /* Eject elements one by one, freeing node memory one by one */
32.}
33.
34./* push */
35.void push(STACK_TYPE value)
36.{
37. StackNode *new_node;
38. new_node = (StackNode *)malloc(sizeof(StackNode));
39. if(new_node == NULL)
40. perror("malloc fail");
41. new_node->value = value;
42. new_node->next = stack; /* Insert a new element into the head of the list */
43. stack = new_node; /* stack redirects to the list head */
44.}
45.
46./* pop */
47.void pop(void)
48.{
49. StackNode *first_node;
50.
51.assert(! is_empty());52. first_node = stack;
53. stack = first_node->next;
54. free(first_node);
55.}
56.
57./* top */
58.STACK_TYPE top(void)
59.{
60.assert(! is_empty());61. return stack->value;
62.}
63.
64./* is_empty */
65.int is_empty(void)
66.{
67. return stack= =NULL;
68.}
69.
70./* is_full */
71.int is_full(void)
72.{
73. return FALSE;
74.}
Copy the codeAt this point, the embedded stack principle and its pure C realization riffraff balance will be introduced over, where is the applause ~~~
Welcome to subscribe to
The article will be published on my blog park homepage, CSDN homepage and wechat public account platform at the same time.
Wechat search “ruffian balance embedded” or scan the following two-dimensional code, you can see the first time on the phone oh.
