Linked lists - Bi-directional universal linked lists

[toc]

preface

20201014
While reading the source code of the RTOS LiteOS kernel, it is found that the kernel uses a generic linked list, while the FreeRTOS kernel uses a non-generic linked list, so it is necessary to take notes on the implementation of the linked list.
The following contents are personal notes, involving some non-professional vocabulary, please understand, thank you.

concept

Normal expression
- List:
  - Linked lists are a basic data structure in C.
  - Think of it as a circular clotheshorse.
- Nodes:
  - The nodes form a linked list
Non-generic linked list self-understanding concept: nodes carry information
- Chain list: round clothes-hangers
- Nodes: hooks
  - Including the previous one
  - The next
  - Hooks and other required information
- Socks: Hang on tohookThe things
  - Contains the hook
  - Socks carry information
General linked list self – understanding concept: information carrying nodes
- Chain list: round clothes-hangers
- A section of the round frame of a clothes-hanger
  - Contains only the previous one
  - The next
- Socks: Placed on a section of the round frame of the clothes rack, making the node a member pointer variable of the socks
  - Socks carry information
  - Contains nodes in the information
The difference between generic and non-generic linked lists
- A generic list of nodes has very little content, usually just the previous and the next.
- The generic list node is placed into the information structure and is offset to find the structure (i.e. the sock tip).
- Non-generic lists carry Pointers to information structures in nodes.
- Other people understand, readers need not ignore this little point
  - The general linked list is to put the socks on the circular circle of the drying rack, and the contact part between the socks and the circular circle is the node of the socks reception. (Information carrying node)
  - Non-generic linked lists are. (Node carrying information)
  - Universal linked listChain line –Run through the socks (Socks are information)
  - Non-generic linked lists of chain-lines connected to hooks, which hook socks

Record of the draft

Two-way linked list

Bidirectional linked list understanding diagram

Nodes, linked lists, and information access **

node
- The members are only one and the next

/* *Structure of a node in a doubly linked list. */
typedef struct LSS_LIST
{
    struct LSS_LIST *pstPrev;            /**< Current node's pointer to the previous node*/
    struct LSS_LIST *pstNext;            /**< Current node's pointer to the next node*/
} LSS_LIST;
typedef struct LSS_LIST listItem_t;
Copy the code

The list
- Multiple nodes form a linked list

Access to information
- The core and most important part of manipulating a generic linked list is to get an information handle by offsetting it(Socks head)
  - The length in figure C below is the offset length of the node and the information handle. You only need to know the address of ** node, information type (structure type) and member name (that is, the name of the member of the current node in the structure) ** to get the information handle

/* * @param item Current node's pointer. * @param type Structure name of type. * @param member Member name of the doubly  linked list in the structure. */
#define LSS_LIST_ENTRY(item, type, member)    \
                    ((type *)((char *)(item) - (unsigned long)(&((type *)0)->member)))
Copy the code

Operation code and description

The following are just some extension examples of generic linked lists, more of which can be implemented in quadrant +.

1. Initialize the linked list

The last one was pointing to itself
The next one points to me

/** * @brief list initialization * @param pstList: pointer to the list (node) to be initialized * @retval None * @author LZM */
void listInit(listItem_t *pstList)
{
    pstList->pstNext = pstList;
    pstList->pstPrev = pstList;
}
Copy the code

2. Obtain the first node

Points to the next node of the current node
The first one is the next one

/** * @brief Obtain the first node * @param pstObject: pointer to the current node * @retval None * @author LZM */
#define listGetFirst(pstObject) ((pstObject)->pstNext)
Copy the code

3. Insert a node (head)

Insert after the current node
- Handle the external pointing of nodes to be inserted first
- Then process the in-node pointing that needs to be inserted

* @param pstList: linked list (also the current node) * @param pstNode: node (the node to be inserted) * @retval None * @author LZM */
void listAdd(LSS_LIST *pstList, LSS_LIST *pstNode)
{
    pstNode->pstNext = pstList->pstNext;
    pstNode->pstPrev = pstList;
    pstList->pstNext->pstPrev = pstNode;
    pstList->pstNext = pstNode;
}
Copy the code

4. Insert a node (tail)

Insert the end of the list (That is, insert before the current node)

/** * @brief insert the end of the list * @param pstList: linked list (also the current node) * @param pstNode: node (node to be inserted) * @retval None * @author LZM */
void listTailInsert(LSS_LIST *pstList, LSS_LIST *pstNode)
{
    listAdd(pstList->pstPrev, pstNode); // Use the previous node of the current node as a reference
}
Copy the code

5. Delete a node

Deleting the current Node
- First deal with the in-node pointing to be deleted
- Then process the external pointing of the node to be deleted

/** * @brief Delete the current node * @param pstNode: node (node to be deleted) * @retval None * @author LZM */
void listDelete(LSS_LIST *pstNode)
{
    pstNode->pstNext->pstPrev = pstNode->pstPrev;
    pstNode->pstPrev->pstNext = pstNode->pstNext;
    pstNode->pstNext = (LSS_LIST *)NULL;
    pstNode->pstPrev = (LSS_LIST *)NULL;
}
Copy the code

6. Determine if a linked list is empty

Determine whether the linked list node points to the initialization value.

/** * @brief Delete the current node * @param pstNode: node (node to be deleted) * @retval TRUE: the list is empty * @retval FALSE: the list is not empty * @author LZM */
bool listEmpty(LSS_LIST *pstNode)
{
    return (bool)(pstNode->pstNext == pstNode);
}
Copy the code

7. The offset * of the information handle is obtained

The information structure type and the name of the member in the information structure can be used to obtain the offset of the name to the information handle.

/** * @brief Indicates the offset of the information handle. * @param type: indicates the type of the information structure. * @param member: indicates the name of the member
#define getOffsetOfMenber(type, member)    ((uint32_t)&(((type *)0)->member))
Copy the code

8. Obtain the information handle * of the node

That is to get the address of the information structure where the node is located

* @param type: indicates the type of the information structure. * @param member: indicates the name of the member. * @retval Returns the information handle of the node
#define getItemDataHandle(item, type, member) \
    ((type *)((char *)item - getOffsetOfMenber(type, member))) \
Copy the code

Walk through the linked list

/** * @brief Deletes nodes and reinitializes them * @param pstList: linked list nodes that need to be reinitialized * @retval * @author LZM */
#defineLIST_FOR_EACH(item, list) \ for ((item) = (list)->pstNext; \ (item) ! = (list); \ (item) = (item)->pstNext)
Copy the code

10. Iterate through the list and get the information handle (macro) *

This macro is not a complete statement, just a for statement, do a list traversal.

/** * @brief traverse the entire list and get the information handle (macro) * @param Handle: hold the information handle of the target node * @param item: the list to traverse (node) * @param type: Information type (structure name) * @param member: the list's name in type * @retval is also the for statement * @author LZM */
#defineLIST_FOR_EACH_HANDEL(handle, list, type, member) \ for (handle = getItemDataHandle((list)->pstNext, type, member); \ &handle->member ! = (list); \ handle = getItemDataHandle(handle->member.pstNext, type, member))
Copy the code

11. Delete the node and initialize it again

Delete this node from the linked list first
Initialize the node again

void osListDel(LSS_LIST *pstPrevNode, LSS_LIST *pstNextNode)
{
    pstNextNode->pstPrev = pstPrevNode;
    pstPrevNode->pstNext = pstNextNode;
}
/** * @brief Deletes nodes and reinitializes them * @param pstList: linked list nodes that need to be reinitialized * @retval * @author LZM */
void listDelInit(LSS_LIST *pstList)
{
    osListDel(pstList->pstPrev, pstList->pstNext);
    listInit(pstList);
}
Copy the code

reference

link
- My Gitee
- Non-generic linked list complete C language source code
LiteOS kernel source code

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Linked lists – Bi-directional universal linked lists

preface

concept

Record of the draft

Two-way linked list

Nodes, linked lists, and information access **

Operation code and description

1. Initialize the linked list

2. Obtain the first node

3. Insert a node (head)

4. Insert a node (tail)

5. Delete a node

6. Determine if a linked list is empty

7. The offset * of the information handle is obtained

8. Obtain the information handle * of the node

Walk through the linked list

10. Iterate through the list and get the information handle (macro) *

11. Delete the node and initialize it again

reference

Linked lists – Bi-directional universal linked lists

preface

concept

Record of the draft

Two-way linked list

Nodes, linked lists, and information access **

Operation code and description

1. Initialize the linked list

2. Obtain the first node

3. Insert a node (head)

4. Insert a node (tail)

5. Delete a node

6. Determine if a linked list is empty

7. The offset * of the information handle is obtained

8. Obtain the information handle * of the node

Walk through the linked list

10. Iterate through the list and get the information handle (macro) *

11. Delete the node and initialize it again

reference

Related Posts

How to upload files with Serverless

Client encapsulation based on socket. IO

LeetCode 599. Minimum index sum for two lists