Complex Data Structures image/svg+xml Complex Data Structures Zidarics Zoltánzamek@vili.pmmf.hu 2018 Complex data structures EmbeddedProgramming 5.documentation 7.parallel programming Problem storing data generated by asynchronous events temporary storage of data received or to be sent from communication channels data communication between processes / threads Store data read from I / O devices Store data to send to I / O devices Requirements storing multiple data of the same type data type not relevant (pointer) the size of the container can change dynamically fifo type storage (queue) lifo type storage (stack) random access Solution OOP environment (Java, C ++) Collection framework BSD Queue (sys/queue.h) single chained list list queue circular queue List types single linked list data data data data next next next next head double linked list data next head prev prev next prev next data data circular list data next head prev prev next prev next data data virtual virtual queue (FIFO First In First Out) data6 data5 data4 data3 data2 data1 data7 data0 enqueue dequeue stack (LIFO Last In First Out) data5 data4 data3 data2 data1 data0 push data7 data6 pop List Operations initialize insert an item delete item iterating list resetting the internal data structure top of list (queue / enqueue, stack / push) to the end of the list in front of an item after an item from the top of the list (stack / pop) from the end of the list (queue / deque) a specified item (by its pointer) select an item from the list first item last item specified item previous / next item operations to be performed cyclically on all elements list status information empty? number of element? sys/queue.h SLIST: single linked list demo TAILQ: queue, the internal represantation is a double linked list LIST: double linked list STAIL_QUEUE: queue, the internal representation is a single linked list SIMPLEQ: queue, the internal represantation is a single linked list CIRCLEQ: queue, the internal represantation is a circular double linked list the entire framework is implemented with macros, so it is platform independent STAILQ definitions data next head prev prev next prev next data data STAILQ_HEAD(name,type) Initialize list STAILQ_INSERT_HEAD(head,elm,field) insert an elm in front of the first item in the list starting with head STAILQ_INSERT_TAIL(head,elm,field) insert elm at the end of the list STAILQ_REMOVE_HEAD(head,field) removes the first element from the list STAILQ_REMOVE(head,elm,type,field) removes elm from the list  STAILQ_FOREACH(var,head,field) iterates all items in the list starting with head. The elements are placed in var. var: each element is placed in the variable field: the name of the list manager member in the item declaration elm: item to be removed type: the data structure type of elm field: the name of the list manager member in the item declaration head: address of the head of the list head: address of the head of the list field: the name of the list manager member in the item declaration head: address of the head of the list elm: item to be inserted field: the name of the list manager member in the item declaration head: address of the head of the list elm: item to be inserted field: the name of the list manager member in the item declaration name: the name of the head variable in the list STAILQ_EMPTY(head) 1 if the list starting with head is empty, 0 if not STAILQ_FIRST(head) returns the first item in the list beginning with head STAILQ_NEXT(elm,field) returns the element after the elm existing element STAILQ_INSERT_AFTER(head,listelm, elm,field) insert elm after slistelm head: address of the head of the list elm: item to be inserted field: the name of the list manager member in the item declaration listelm: an existing item in the list after which the new item should be inserted STAILQ_CONCAT(head1,head2) add head2 to head1 list head1: the first list head2: the second list SLIST definitions data data data data next next next next head SLIST_HEAD(head) List definition head: the variable name of the list SLIST_INITIALIZER(head) initial assignment to the list (NULL) head: the variable name of the list SLIST_ENTRY(type) element structure declaration is the declaration required to manage the list type: the name of the element structure SLIST_INIT(head) type: the name of the element structure SLIST_INSERT_HEAD(head,elm,field) insert an elm in front of the first item in the list starting with head SLIST_INSERT_AFTER(slistelm,elm,field) insert elm after slistelm SLIST_REMOVE_HEAD(head,field) removes the first element from the list SLIST_REMOVE(head,elm,type,field) removes elm from the list   SLIST_FOREACH(var,head,field) iterates all items in the list starting with head. The elements are placed in var. var: each element is placed in the variable field: the name of the list manager member in the item declaration elm: item to be removed type: the data structure type of elm field: the name of the list manager member in the item declaration head: address of the head of the list head: address of the head of the list field: the name of the list manager member in the item declaration slistelm: an existing item in the list after which the new item should be inserted elm: the item to be inserted field: az elem deklarációban a listakezelő tag neve head: address of the head of the list elm: the item to be inserted field: the name of the list manager member in the item declaration head: the head of list SLIST operations SLIST_EMPTY(head) 1 if the list starting with head is empty, 0 if not SLIST_FIRST(head) returns the first item in the list beginning with head SLIST_NEXT(elm,field) returns the element after the elm existing element SLIST element methods type: the name of the list item structure STAILQ_HEAD_INITIALIZER(head) initial assignment to the list (NULL) head: the variable name of the list STAILQ_ENTRY(type) element structure declaration is the declaration required to manage the list type: the name of the element structure STAILQ operations STAILQ element methods SIMPLEQ definitions SIMPLEQ_HEAD(name,type) Initialize list name: name of the head of the list type: the name of the list item structure SIMPLEQ_HEAD_INITIALIZER(head) initial assignment to the list (NULL) head: address of the head of the list SIMPLEQ_ENTRY(type) element structure declaration is the declaration required to manage the list type: the name of the element structure elm: the item field: the name of the list manager member in the item declaration SIMPLEQ_INIT(head) Initialize list SIMPLEQ_INSERT_HEAD(head,elm,field) insert a head in front of the first item in the list starting with head SIMPLEQ_INSERT_TAIL(head,elm,field) insert elm at the end of the list SIMPLEQ_REMOVE_HEAD(head,field) delete the first item in the list starting with head from the list SIMPLEQ_REMOVE(head,elm,type,field) delete the elm element from the list beginning with head SIMPLEQ_FOREACH(var,head,field) iterates all items in the list starting with head. The elements are placed in var. var: each element is placed in the variable field: the name of the list manager member in the element declaration elm: item to be deleted type: the type of data structure field: the name of the list manager member in the element declaration head: address of the head of the list head: address of the head of the list field: the name of the list manager member in the element declaration head: address of the head of the list elm: item to be inserted field: the name of the list manager member in the element declaration head: address of the head of the list elm: item to be inserted field: the name of the list manager member in the element declaration head: address of the head of the list SIMPLEQ_INSERT_AFTER(head, listelm, elm,field) insert elm after listelm head: address of the head of the list elm: item to be inserted field: the name of the list manager member in the element declaration listelm: the address of the list element after which the new item is to be inserted SIMPLEQ operations SIMPLEQ_EMPTY(head) 1 if the list starting with head is empty, 0 if not SIMPLEQ_FIRST(head) returns the first item in the list beginning with head SIMPLEQ_NEXT(elm,field) returns the element after the elm existing element SIMPLEQ element methods TAILQ definitions TAILQ_HEAD(name,type) Initialize list name: the name of the head variable in the list type: the name of the list item structure TAILQ_HEAD_INITIALIZER(head) initial assignment to the list (NULL) head: address of the head of the list TAILQ_ENTRY(type) element structure declaration is the declaration required to manage the list type: the name of the element structure TAILQ_HEAD(name,type,qual) Initialize list name: the name of the head variable in the list type: the name of the list item structure qual: modifier e.g. static TAILQ_INIT(head) Initialize list TAILQ_INSERT_HEAD(head,elm,field) insert elm in front of the first item in the list starting with head TAILQ_INSERT_TAIL(head,elm,field) insert elm at the end of the list TAILQ_REMOVE(head,elm,type,field) removes the first element from the list TAILQ_FOREACH(var,head,field) iterates all items in the list starting with head. The elements are placed in var. var: each element is placed in the variable field: the name of the list manager member in the element declaration elm: item to be deleted type: the type of data structure field: the name of the list manager member in the element declaration head: address of the head of the list head: address of the head of the list elm: item to be inserted field: the name of the list manager member in the element declaration head: address of the head of the list elm: item to be inserted field: the name of the list manager member in the element declaration head: address of the head of the list TAILQ_INSERT_AFTER(head, listelm, elm,field) insert elm after the existing listelm head: address of the head of the list elm: item to be inserted field: the name of the list manager member in the element declaration listelm: the element after which the new item is to be inserted TAILQ operations TAILQ_INSERT_BEFORE(listelm, elm,field) insert elm in front of the existing listelm elm: item to be inserted field: the name of the list manager member in the element declaration listelm: the listel before which the new item is to be inserted TAILQ_FOREACH_REVERSE(var,head,headname,field) iterates all items in the list beginning with head in reverse order. The elements are placed in var. var: each element is placed in the variable field: the name of the list manager member in the element declaration headname: the variable name of the head element TAILQ_CONCAT(head1,head2,field) Add head2 items to the head1 list head1: the first list field: the name of the list manager member in the element declaration head2: the second list TAILQ_EMPTY(head) 1 if the list starting with head is empty, 0 if not TAILQ_FIRST(head) returns the first item in the list beginning with head TAILQ_NEXT(elm,field) returns the element after the elm existing element TAILQ elem methods TAILQ_LAST(head,headname) returns the last item headname: the name of the head variable TAILQ_PREV(elm,headname,field) returns the element before the existing elm elm: the element before which we are looking for the element headname: the name of the head variable field: the name of the list manager member in the element declaration CIRCLEQ_INIT(head) Initialize list CIRCLEQ_INSERT_HEAD(head,elm,field) insert a head in front of the first item in the list starting with head CIRCLEQ_INSERT_TAIL(head,elm,field) insert elm at the end of the list CIRCLEQ_REMOVE(head,elm,field) removes first element from the list CIRCLEQ_FOREACH(var,head,field) head kezdetű lista minden elemének bejárása. Az elemek var-ba kerülnek. var: az egyes elemek kerülnek a változóba field: az elem deklarációban a listakezelő tag neve elm: item to be removed field: the name of the list manager member in the element declaration head: address of the head of the list head: address of the head of the list elm: item to be inserted field: the name of the list manager member in the element declaration head: address of the head of the list elm: item to be inserted field: the name of the list manager member in the element declaration head: address of the head of the list CIRCLEQ_INSERT_AFTER(head, listelm, elm,field) insert elm after existing listelm head: address of the head of the list elm: item to be inserted field: the name of the list manager member in the element declaration listelm: the existing element after which the new item is to be inserted CIRCLEQ operations CIRCLEQ_INSERT_BEFORE(listelm, elm,field) insert elm before existing listelm elm: item to be inserted field: the name of the list manager member in the element declaration listelm: the existing element before which the new item is to be inserted CIRCLEQ_FOREACH_REVERSE(var,head,headname,field) iterates all items in the list beginning with head in reverse order. The elements are placed in var. var: each element is placed in the variable field: az elem deklarációban a listakezelő tag neve headname: the variable name of the head element CIRCLEQ definitions CIRCLEQ_HEAD(name,type) Initialize list name: the name of the head variable in the list type: the name of the list item structure initial assignment to the list (NULL) head: the variable name of the list CIRCLEQ_ENTRY(type) element structure declaration is the declaration required to manage the list type: the name of the element structure CIRCLEQ_HEAD_INITIALIZER(head) CIRCLEQ_EMPTY(head) 0 if the list starting with head is empty, 1 if not CIRCLEQ_FIRST(head) returns the first item in the list beginning with head CIRCLEQ_NEXT(elm,field) returns the element after the elm existing element CIRCLEQ element methods CIRCLEQ_LAST(head,headname) returns the last item headname: the name of the head variable CIRCLEQ_PREV(elm,field) returns the element before the elm elm: the element before which we are looking for the element field: the name of the list manager member in the element declaration CIRCLEQ_LOOP_NEXT(head,elm,field) returns the previous item in circular mode elm: the element before which we are looking for the element field: the name of the list manager member in the element declaration head: address of the head of the list Queue implementation STAILQ (single chaining is enough) MALLOC(entry, sizeof(node_t));...STAILQ_INSERT_TAIL(&node_list, entry, link); typedef struct node { char *label; int order; STAILQ_ENTRY(node) link;} node_t; node declaration list declaration and initialization static STAILQ_HEAD(head, node) node_list= STAILQ_HEAD_INITIALIZER(node_list); enqueue operation entry = STAILQ_FIRST(&node_list);STAILQ_REMOVE(&node_list, entry, node, link); dequeue operation Queue demo Stack implementation TAILQ (double linked list) MALLOC(entry, sizeof(node_t));...TAILQ_INSERT_TAIL(&node_list, entry, link); typedef struct node { char *label; int order; STAILQ_ENTRY(node) link;} node_t; node declaration list declaration and initialization static TAILQ_HEAD(head, node) node_list= TAILQ_HEAD_INITIALIZER(node_list); push operation entry = TAILQ_LAST(&node_list, head);TAILQ_REMOVE(&node_list, entry, node, link); pop operation Stack demo Task Packets in the following formats are received from the SPI port typedef struct package { uint8_t channel; int16_t value;} package_t; Create tests for the module Create a module that stores incoming packets in a queue The module should hide all internal methods belonging to the queue Public functions: spi_init(), spi_add_package(), spi_is_package(), spi_get_package(), spi_free_package() Document the module For the finished module, make a project on gitlab called spi_queue Memory fragmentation for short-term storage of large amounts of data UART, SPI, I2C, TCP stack data from ports is stored only during processing AD converter measurements if you allocate memory and memory for each data packet separatelyreleased after processing (malloc / free) memory is fragmented malloc / free is time consuming       defragment required (garbage collector) GC is time consuming task scheduling must be stopped for the duration of the GC embedded operating systems may not be supported 0x0000 0x1000 0x2000 0x3000 0x4000 0x5000 A A B C C Start with all memory available for allocation Allocated three blocks A, B, and C, of size 0x1000. Freed block B. Notice that the memory that B used cannot be included for an allocation larger than B's size. Object pool reserving a defined amount of data storage at compile timewhen starting the application when a data packet arrives, malloc instead of get operation after processing free instead of put operation pool pool get pool put advantages there is no fragmentation as we only allocate the memory required for the pool once no malloc / free to get and put simple pointer operation disadvantages pool size must be specified at compile time or possibly uploaded from config in case of underdefining size, thread starvation or data loss memory wasting when oversizing size implementation simple queue get operation: dequeue put operation: enqueue creating a pool is time consuming     Unused packets pool U3 U4 U5 U6 U7 U8 U9   A2 A1 A0 Active packets pool Producer task 1. GET an unused packet 2. fill it with data 3. PUT to active pool   Consumer task 1. GET an active packet 2. process data 3. PUT to unused pool POOL implementation base address base+4 base+12 phy_link price base+8 modem_state_phy_done reserved flags Union A union is a user-defined type similar to structs in C except for one key difference Structures allocate enough space to store all their members, whereas unions can only hold one member value at a time. union Car{ char name[20]; int price;};int main(){ union Car car1, car2, *car3; return 0;} base address base+4 base+20 name price union Car { char name[20]; int price;};int main() { union Car car; car.price=1000; printf("Price of car is %d\n", car.price); printf("Name of car is: %s\n", car.name); car.name="Toyota Yaris"; printf("Name of car is: %s\n", car.name); printf("Price of car is %d\n", car.price); return 0;} typedef struct sleep_modem_config { struct { void *phy_link; union { struct { uint32_t modem_state_phy_done; uint32_t reserved; }; uint32_t flags; }; } wifi;} sleep_modem_config_t; Demo
1
  1. Main
  2. Problem
  3. Requirements
  4. Solution
  5. List types
  6. List operations
  7. sys/queue.h
  8. SLIST definitions
  9. SLIST operations
  10. SLIST element methods
  11. STAILQ definitions
  12. STAILQ operations
  13. STAILQ element methods
  14. SIMPLEQ definitions
  15. SIMPLEQ operations
  16. SIMPLEQ element methods
  17. TAILQ definitions
  18. TAILQ operations
  19. TAILQ element methods
  20. CIRCLEQ definitions
  21. CIRCLEQ operations
  22. CIRCLEQ element methods
  23. Queue implementation
  24. Stack implementation
  25. Task
  26. Memória fragmentation
  27. Object pool I.
  28. Object pool II.
  29. Object Pool implementation
  30. Union1
  31. Union2
  32. Union3
  33. next