Advanced topics in C, Part 9 -4.9. Linked Lists & State Machines and Multithreading
The first part, chapter contents 4.9.1. Introduction of linked list 4.9.2. Realization of single linked list 4.9.3. Single linked list algorithm insertion node 4.9.4. Single linked list algorithm insertion node continue 4.9.5. Inserting new nodes from the head of a linked list 4.9.6. Traversal of nodes by a single linked list algorithm 4.9.7. Single-linked list algorithm for deleting nodes 4.9.8. Single-linked list algorithm for reversing 4.9.9. Introduction and basic implementation of double linked list 4.9.10. Insert node of double linked list algorithm 4.9.11. Double linked list algorithm traversal node 4.9.12. Double linked list algorithm delete node 4.9.13. Linux kernel linked list 4.9.14. What is the state machine 4.9.16.C language to achieve a simple state machine 4.9.17. Introduction to Multithreading
The second part introduces 4.9.1. Introduction of linked lists. This section introduces the concept of linked lists from the defects of arrays, aiming to make people naturally recognize the significance and use of linked lists. 4.9.2 implementation of Single Linked List This section introduces the idea and programming implementation of single linked list, focusing on the encapsulation and implementation of linked list nodes. This section describes the first algorithm for singly linked list operations, node insertion. This paper mainly introduces two different algorithms of head insertion and tail insertion. This section continues the programming practice of inserting nodes into the tail of a linked list. It takes you to write code to insert nodes from the tail. 4.9.5. Insert new nodes from the head of the linked list This section is the programming practice of insert the head of the linked list. It takes you to write code to insert nodes from the head. This section is the second algorithm of single linked list: the principle and programming implementation of traversal linked list. This section implements the third algorithm of the single linked list: delete the specified node. This section introduces the last single linked list algorithm: list inversion, which is the most difficult algorithm to deal with. 4.9.9 introduction and Basic Implementation of double linked List This section analyzes the defects of single linked list and introduces double linked list at the same time, and realizes the nodes of double linked list programmatically. This section explains the first algorithm of a double-linked list: insert node. It is also divided into head insertion and tail insertion. This section explains the second algorithm of doubly linked lists: traversal nodes. This section introduces the algorithm of deleting nodes of double-linked lists and carries out programming practice. 4.9.13. Linux Kernel linked List This section introduces kernel linked list by analyzing some defects of the linked list we talked about, and introduces the design ideas and main characteristics of kernel linked list. 4.9.14. Introduction to the basic algorithm and Use of kernel linked List This section introduces the implementation of the basic algorithm of kernel linked list and the use of kernel linked list. Kernel linked list is widely used in kernel code, especially in various drivers. 4.9.15 what is a State machine This section introduces the definition and classification of state machines theoretically, and then analyzes the main uses of state machines, the application direction of state machines and the problems to be solved, in order to make people understand why there is a state machine. 4.9.16. Realizing a Simple State machine with C Language This lesson uses C language to realize a simple state machine. The purpose of this lesson is to further understand the realization of the state machine, understand what the state machine realizes and solve by combining with the theory in the last lesson. 4.9.17. Introduction to Multithreading This lesson briefly introduces the concept of multithreading and multithreading programming, which is the beginning of using multithreading in later application programming.
(1) There are two defects in arrays. One is that all elements in arrays must be of the same type. The second is that the number of elements in the array must be specified in advance and cannot be changed once specified. (2) How to solve the two defects of array: the first defect of array depends on the structure to solve. Structs allow elements to be of different types, thus solving the first drawback of arrays. So structs were invented because arrays don’t solve certain problems. (3) How to solve the second defect of array? We want the array size to scale in real time. For example, I initially set the number of elements to be 10, and then when the program runs, it feels inadequate and dynamically expands to 20. Ordinary arrays obviously don’t work, so we can encapsulate arrays to do this; We can also solve this problem with a new data structure called linked lists. Summary: You can almost think of a linked list as an array in which the number of elements can grow or shrink in real time.
4.9.1.2 Why do universities Have New Campuses? (1) When the school was first built (similar to the variable definition and initialization), there were no buildings due to wasteland nearby, so the size of the school campus was determined by itself; But after school established by slowly also had other building (similar to the variable assignment, the memory of the adjacent area and distribution of the other variables are connected to the address of the variable), then you feel not enough campus along with the development of want to extend, only to find that neighbor already full, around campus are all others’ building, At this time, there are two ways to expand the school: the first is demolition, the second is relocation, and the third is external expansion. (2) Demolition is almost impossible because the cost is too high. (3) Relocation can go through. One way to solve the problem of expanding array size is to move the whole array. The procedure is: first create a large array in another blank memory, then copy the values of the elements in the original array to the head of the new array, and then free the memory space of the original array, and replace the new array with the original array. Mutable arrays are not supported in C, but are supported in higher level languages such as C++, Java, etc. (4) The idea of external extension is the most common, basically can be said to be the most reasonable. One of its ideas is to divide the whole into parts and expand the new base externally on the original premise of not moving. External extensions in the case of schools are new campuses; External extensions are linked lists at the point of programming to solve array problems.
4.9.1.3 What is a linked list? (1) As the name implies, a linked list is a list connected by a chain. The table here refers to nodes one by one (a node is a campus), nodes have some memory can be used to store data (so called table, table is data table); The chain here refers to the method of linking various tables. In C language, the method used to connect two tables (in fact, two blocks of memory) is pointer. (2) The linked list is composed of several nodes (the structure of each node of the linked list is completely similar), and the nodes are composed of valid data and Pointers. The active data area is used to store information to complete tasks, and the pointer area is used to point to the next node of the list to form the list.
(1) Keep in mind that lists are used to solve the problem that arrays cannot be dynamically expanded, so lists are used as arrays. Let’s be blunt: anything a list can do can be done with an array, and anything an array can do can be done with a list. But flexibility is different. (2) Simply put: Linked lists are used to store data. Linked lists are used to store data. The advantage of linked lists is that they are more flexible than arrays. Arrays have the advantage of being simple (crude) to use.
4.9.2 Implementation of singly linked List 4.9.2.1 Structure of nodes of singly linked List (1) A linked list is composed of nodes, which contain valid data and Pointers. (2) The defined struct node is only a structure, without variable generation itself, and does not occupy memory. The structure definition is equivalent to defining a template for the linked list node, but there is not a node yet. You can use this template to copy a node when you actually create the list.
4.9.2.2 Application and Use of heap Memory (1) Memory requirements of linked list are flexible, neither stack nor data segment can be used. Only heap memory is available. (2) Use heap memory to create a linked list node: 1. Apply heap memory, the size of a node (check whether the application result is correct); 2. Clean up the applied heap memory; 3. Treat the applied heap memory as a new node; 4. Fill the valid data and pointer fields for your new node.
(1) The header pointer is not a node, but an ordinary pointer, which is only 4 bytes long. The head pointer is of type struct Node *, so it can point to a node in the list. (2) A typical implementation of a linked list is that the head pointer points to the first node of the list, then the pointer in the first node points to the next node, and so on until the last node. So you have a chain.
Objective: Build a linked list and store some data (such as numbers 1, 2, and 3) in the list
4.9.3.1 Continue the previous section, access the data of each node in the linked list (1) can only use the header pointer, not the pointer of each node. Because in practice, when we save the linked list, we do not save the Pointers of each node, only through the head pointer to access the list node. (2) The pNext pointer inside the previous node can help us find the next node. Insert a new node from the head of the linked list. Insert a new node from the tail of the linked list. (1) Insert a simple point at the tail, because the previously established linked list does not need to move. Just move the last one.
4.9.4.1 Detailed explanation of the head insertion function of the linked list 4.9.4.2 What is the head node (1) Question: Insert_tail: insert_tail: insert_tail: insert_tail: insert_tail: insert_tail: insert We had to create a new node for create_node to initialize the header pointer after defining it. But this solution makes the program look a bit illogical, because it looks like the first node is created and added a little differently than the ones that follow. (2) There is another use for linked lists, which is to use the first node to which the head pointer points as the head node. A header node has the following characteristics: first, it follows a header pointer. Second, the data portion of the head node is empty (sometimes not empty, but the number of nodes in the entire list), and the pointer portion points to the next node, the first node. (3) In this way, the head node is really different from the other nodes. We also add nodes differently when creating a linked list. The head node is created and associated with the head pointer when the head pointer is created. The actual nodes that store the data are done by adding functions to the nodes, such as insert_tail. (4) Lists with or without header nodes are different. The algorithm functions of inserting, deleting, traversing and resolving the linked list are different. So if a linked list is designed with a head node then all subsequent algorithms should do that; If there is no head node at design time, then all subsequent algorithms should behave as if there is no head node. Both lists are used in real programming, so when you look at code written by someone else, be sure to look for a head node.
4.9.5. Insert a new node from the head of the linked list (1) Note the arrow symbol during writing code and the pointer pointing during speaking. These are two different things. They get mixed up. The arrow symbol is actually a pointer to the structure, so the essence of the arrow symbol is to access the members of the structure. To be clear, the arrows in the program have nothing to do with the links in the list; The nodes in the linked list are connected by a pointer, which is shown as an assignment statement (connected by =) in programming. In essence, the first address of the next node is assigned to the pNext element in the previous node as a value. (2) Lists can be inserted from the head or from the tail. You can also insert it at both ends. There is little difference between header inserts and tail inserts for linked lists. There is no difference for the linked list itself, but sometimes there is a difference for the business logic.
(1) Traversal is to take out each node in a single linked list one by one, which is called traversal. (2) The main points of traversal: first, it can not be omitted; second, it can not be repeated and the pursuit of efficiency. (1) To analyze how to traverse a data structure, the key is to analyze the characteristics of the data structure itself. Then according to its own characteristics to develop its traversal calculation method. (2) The characteristic of a single linked list is that it is composed of many nodes. The head pointer + head node is the start of the whole linked list. The characteristic of the last node is that its internal pNext pointer value is NULL. The pNext pointer inside each node is attached from start to end. There is only one path from start to end. These characteristics of single – linked list determine its traversal calculation method. (3) Traversal method: start from the head pointer + the head node, follow the linked list to access each node in turn, take out the data of this node, and then proceed to the next node until the last node, and return.
Void bianli(struct node*pH);
(1) It has been emphasized for a long time that what are linked lists used for? (2) Sometimes the data in the linked list node is not needed, so it needs to be deleted. 4.9.7.2 Two steps of Node Deletion (1) Step 1: Find the node to be deleted; Step 2: Delete the node. 4.9.7.3 How to Find the Node to be Deleted (1) Search for the node through the history. Start from the head pointer + head node, take out each node in turn along the linked list, compare according to certain methods, and find the node we want to delete. 4.9.7.4 How to Delete a Node (1) When the node to be deleted is not the tail node: First, the pNext pointer of the previous node of the node to be deleted points to the first address of the next node of the node to be deleted (so that the node is removed from the linked list), and then the removed node is free to remove the interface. (2) When the node to be deleted is the tail node: First, the pNext pointer of the previous node of the tail node to be deleted points to null (in this case, the node before the original tail node becomes the new tail node), and then the removed node is free to be removed.
(1) None of the code we wrote in the previous classes ended up freeing heap memory. When the program is finished, the heap that is not free is freed. (2) Sometimes our program runs for a long time, and malloc memory will be occupied until you free it or the whole program terminates if there is no free.
(1) The reverse order of a linked list is also called the reverse order, which means to reverse the order of all valid nodes in the linked list.
(1) When we perform an operation on a data structure, we need a set of algorithms. That’s the relationship between data structures and algorithms. (2) I conclude that the algorithm has two levels. The first level is mathematical and logical algorithms; The second level is to implement algorithms in a programming language. (3) Logically, there are many ways to reverse a linked list. Each of these approaches achieves the desired end result, but the efficiency is not the same. They differ in scalability, fault tolerance, etc. (4) Idea: First traverse the original linked list, and then take the head pointer and head node in the original linked list as the head pointer and head node of the new linked list. Take out the effective nodes in the original linked list one by one and insert them into the new linked list by using the method of head insertion. (5) List reverse = traversal + head insert
4.9.8.3 Programming actual combat
(1) Single linked list is an extension of array, which solves the problem that the size of array is rigid and not easy to expand. Heap memory is used to store data, and data is dispersed among nodes. Each node can be disconnected in memory, and one-way links between nodes are made by Pointers. The nodes in the linked list are not connected to each other in memory, which facilitates the utilization of fragmented memory. (2) There is only one pointer one-way link between each node of a singly linked list, which has some limitations. The limitation is mainly reflected in the single-linked list can only be moved in one direction by the pointer (once the pointer has moved a node, it cannot come back again, and if you want to operate the node again, you have to traverse it again from the ab initio pointer), so some operations of the single-linked list are more troublesome (the algorithm is limited). Recall all the previous operations (insert, delete nodes, traverse, fetch the number of nodes from the single list…), because the one-way mobility of the single list caused a lot of trouble. Conclusion: The one-way mobility of a single linked list results in that the current node can only move backward but not forward when we operate a single linked list. Therefore, it is not free and is not conducive to solving more complex algorithms.
(1) Single linked list node = valid data + pointer (pointer points to the next node) (2) Bidirectional linked list node = valid data +2 Pointers (one points to the next node, the other points to the previous node)
4.9.9.3 Double linked list encapsulation and programming implementation
Insert node 4.9.10.1, tail insert 4.9.10.2, head insert for double-linked list algorithm
(1) A doubly linked list is a parent set of singly linked lists. A doubly linked list becomes a singly linked list if the pPrev pointer is completely ignored. This determines that forward traversal (backward traversal) of a double-linked list is exactly the same as a single-linked list. (2) Because there are many pPrev Pointers in the double-linked list, the double-linked list can also be traversed forward (from the last node of the list to the first node). But forward traversal doesn’t make much sense, mainly because there are very few cases where the current tail node needs forward traversal. (3) Summary: Double linked list is a costly extension to single linked list, but this extension makes little sense in some times and more sense in other times. Therefore, in practical use, appropriate linked list should be selected according to business requirements.
4.9.12. Double-linked list algorithm for node deletion
4.9.13. Linux kernel linked list 4.9.13.1. Limitations of the above linked list data area (1) Before defining the data area directly int data; We think what we need to store in our linked list is a number of type int. In reality, however, the nodes in a link in real programming are not as simple as this, but diverse. (2) In general, the linked list of actual projects, the data stored in the node is actually a structure, which contains several members, and these members together constitute our node data area.
4.9.13.2 General solution idea: Data area is encapsulated as a structure (1) Because linked lists actually solve a variety of problems, so the structure of the internal data area is also diverse. As a result, the overall composition of linked lists varies from program to program. The problem is that we cannot access all linked lists through a generic, universal operand function. This means that we design a linked list will have to write a list of the operations function (node to create, insert, delete, traverse,…), (2) actually deeper analysis found that different list though these methods can’t general need to write separately, but in fact within the thought and method is the same, the only local areas have different function. (in fact, the list is the same operation, which involves the operation of the data area have different) (3) in view of the above 2 points: our idea is, can you have a way to put all the chain operation method in the common parts extracted in the table with a standard method, and then has make detailed list of the different parts the implementer to handle.
(1) The kernel linked list itself has realized a pure linked list (pure linked list means that there is no data area, only forward and backward Pointers) encapsulation, as well as various operation functions of pure linked list (node creation, insertion, deletion, traversal…). The pure list itself has no use, its use is to give us concrete lists to call from the core.
(1) The implementation of the core pure linked list in the kernel is included/Linux /list.h. (2) List. h is a complete package of pure linked list, including node definition and various linked list operation methods.
4.9.14.1, Node creation, deletion, traversal, etc. 4.9.14.2, Practice of using kernel linked List (1) Question: Kernel linked list only has pure linked list, no data area, how to use it? (2) The use method of design is to embed the kernel linked list as a member of the structure of the whole data structure in the future.
4.9.15. What is a State machine 4.9.15.1, Finite State Machine (1) Often said state machine is a finite state machine FSM. FSM refers to a machine that has a finite number of states (usually the value of a state variable). The machine can receive signals and information input from the external simultaneously. After receiving the signal input from the external, the machine will consider its current state and the information input from the user, and then make an action: jump to another state. (2) Consider the key points of state machine: current state, external input, next state 4.9.15.2, two state machines: Moore and Mealy. (1)Moore state machine features: the output is only related to the current state (independent of the input signal). It’s relatively simple, considering the next state of the state machine only needs to consider its current state. (2) The characteristic of Mealy state machine is that the output is not only related to the current state, but also related to the input signal. When the state machine needs to jump to the next state after receiving an input signal, the state machine considers two conditions (current state and input value) before deciding which state to jump to. 4.9.15.3 Main uses of state machine: circuit design, FPGA programming and software design (1) The idea of state machine is widely used in circuit design (2)FPGA programming and (3) software design (framework type design, such as GUI system of operating system and message mechanism)
(1) We usually write programs that are executed in sequence. This program has a characteristic: the general execution process of the program is established, and the execution of the program can be traced in a certain direction. (2) Occasionally, however, we will encounter a program where the external input does not necessarily follow the established process, and the program needs to be fully able to receive and respond to these external input signals, and to make logical output.
4.9.16.1. Title: Unlocking state Machine. If the user input the correct password continuously, the lock will be unlocked. If the password input process is wrong, the lock will be returned to the initial state and re-included in the password. That is, the user only needs to input the correct password continuously to unlock the lock (there is no need to cancel or delete the input error)
Introduction to Multithreading 4.9.17.1. Parallel Execution mechanism in operating System (1) Parallelism means that multiple tasks are executed simultaneously. Parallelism is divided into microcosmic parallelism and macrocosmic parallelism. (2) Macroscopically, parallelism means that multiple tasks are performed simultaneously in a long period of time (relative to people); Parallelism at the micro level is really executing in parallel. (3) The operating system requires macro parallelism. There are two cases of macroparallelism: the first is microcosmic serial, and the second is microcosmic parallelism. (4) Theoretically speaking, a single-core CPU itself has only one core, and can only execute one instruction at the same time. This KIND of CPU can only realize macroscopically parallel, and must be serial in microscopically. Microparallelism requires multi-core cpus. Multiple cores in a multi-core CPU can execute multiple instructions at the same time on the micro level, so the parallelism on the micro level can be achieved and the parallelism on the macro level can be improved.
(1) Process and thread are two different software technologies in the operating system, which aim to achieve macro parallelism (a popular point is to make multiple programs run on a machine at the same time, so as to achieve the effect of macro parallel execution). (2) Processes and threads have different principles to achieve parallel effects. And the difference depends on the operating system. For example, on Windows there is a large difference between processes and threads, while on Linux there is little difference between processes and threads (threads are lightweight processes in Linux). (3) Whether multi-process or multi-thread, the ultimate goal is to achieve parallel execution.
4.9.17.3, the advantages of multi-threading (1) in the past few years more processes, in recent years, multi-threading began to be used more. (2) The optimization of multi-core CPU is taken into account in the design of modern operating systems, which ensures that when multi-threaded programs are running, the operating system will prioritize multiple threads to run separately in multiple cores. So multi-core CPUS provide a perfect environment for multithreaded programs to run. So there are great benefits to using multithreaded programs on multi-core cpus.
4.9.17.4, Thread synchronization and Locking (1) Multithreaded programs should pay attention to synchronization between threads when running.
4.9.17.5. Details: 3. Linux Application Programming and Network Programming