[toc]

preface

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

link

  • My Gitee
  • Non-generic linked list complete C language source code

reference

  • The above link
  • FreeRTOS kernel source code
  • A wildfire

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
  • Self-understanding concept
    • 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

  • 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)

Record of the draft

Two-way linked list

  • Bidirectional linked list understanding diagram

  • Principle: Linked lists include root nodes and common nodes

    • The root nodeThe main management of linked lists, generally including
      • On a
      • The next
      • How many equal messages exist

** * Common nodes ** mainly used to hook socks (i.e. to carry information)Copy the code

Node and node structure code

  • The common node
    • Storing node information
    • To attach things (hooks), such as socks, etc

/* * The linked list node */
struct LIST_ITEM_LSS_T
{   
    struct LIST_ITEM_LSS_T * pxNext; / / the next
    struct LIST_ITEM_LSS_T  * pxPrevious; / / a
    
    /* Node attributes, (add or subtract according to personal needs) */
    uint32_t xItemValue; // Token value, generally used for sorting
    void * pvOwner; // Hook, that is, the information carried
    void * pvContainer; // To which list you belong
};
typedef struct LIST_ITEM_LSS_T listItem_t;
Copy the code
  • Root node (linked list point)
    • Store linked list information
    • There is aMini node, used for connection and positioning (equivalent to position calibration point), do not mount how things, and simple for the best
      • The token value of the mini node is the largest in the bidirectional linked list, because the largest is both tail and head.

/* Mini node structure */
struct LIST_MINI_ITEM_LSS_T
{
    /* point to, (delete the following content according to single and double linked list) */
    struct node *pxPrevious; // Last node
    struct node *pxNext; // Next node
     /* Node attributes, (add or subtract according to personal needs) */
    uint32_t xItemValue; // The token value is the maximum value in the bidirectional list
};
typedef struct LIST_MINI_ITEM_LSS_T ListMiniItem_t;

/* List structure, i.e. root node */
struct LIST_LSS_T
{
    /* Node attributes, (add or subtract according to personal needs) \*/
    uint32_t uxNumberOfItems; // Number of nodes, count the number of nodes attached to this list
    struct LIST_ITEM_LSS_T * pxIndex; // Index, linked list index, points to a node in the list
    struct LIST_MINI_ITEM_LSS_T xListEnd; // List root node
};
typedef struct LIST_LSS_T List_t;
Copy the code

Linked list operation function code

List initialization function

  1. The linked list index points to the tail node of the list (the tail node is also the head node)
  2. The listEnd nodeThe token value is assigned to the maximum value (The root node contains the tail node)
  3. Initialize the last and next nodes of the tail node, respectively, pointing to the ** tail node
  4. The total number of initialized nodes is 0.
 /** * @brief list initialization * @param * @retval * @author LZM */
void listInit(list_t * const list)
{
    /* Index to last: tail is head */
    list->pxIndex = (listItem_t *) &(list->xListEnd);
    
    /* Maximum list value */
    list->xListEnd.xItemValue = lssLIST_MAX_VALUE;
    
    list->xListEnd.pxNext = ( listItem_t * ) &( list->xListEnd );
    list->xListEnd.pxPrevious = ( listItem_t * ) &( list->xListEnd );
    
    list->uxNumberOfItems = (lssLIST_BASE_TYPE)0U;
}
Copy the code

Node initialization function

  1. The initialization node carries empty information
 /** * @brief Node initialization * @param * @retval * @author LZM */
void listItemInit(listItem_t * const item)
{
    item->pvContainer = NULL;
}
Copy the code

The node inserts the function at the end of the list

Note: The node to be inserted is hereinafter referred to as node A

  1. Get the index (index is the cursor, which is the node to which the list is currently pointing)
  2. The next node of node A points to the index node,
  3. The first of node A points to the first of the index node
  4. The next node before the index node points to node A
  5. The preceding index node points to node A
  6. Set the linked list to which node A belongs
  7. List nodes count to +1
/** * @brief inserts the end of the list (* bidirectional lists have no absolute head or tail, so cursors are used as references *) * @param * @retval * @author LZM */
void listInsertEnd( list_t * const pxList, listItem_t * const pxNewListItem )
{
    listItem_t * const pxIndex = pxList->pxIndex;

    pxNewListItem->pxNext = pxIndex;
    pxNewListItem->pxPrevious = pxIndex->pxPrevious;

    pxIndex->pxPrevious->pxNext = pxNewListItem;
    pxIndex->pxPrevious = pxNewListItem;

    /* Remember which list the item is in. */
    pxNewListItem->pvContainer = ( void * ) pxList;

    ( pxList->uxNumberOfItems )++;
}
Copy the code

Nodes are inserted into the linked list function in order

Note: The node to be inserted is hereinafter referred to as node A

  1. Gets the new node token value

1. If the token value is the maximum value in the linked list (i.eEnd nodeIs equal to the token value of), then take the previous node of the tail node as the reference node 2. If the token valueDon’tIs the maximum value in the linked list, the search starts from the last node until it is foundThe current nodetheNext nodeThe token value of isGreater than node A(that is, find red box node B in the linked list)3. Insert node 1.A node(A nodeIs the node that needs to be insertedThe nextPoint to theThe index node. 2.A nodetheBefore aPoint to theThe node BtheBefore a 3. The preceding one of node BtheThe nextPoint to theA node 4. The node BtheBefore aPoint to theA node5. SetA node6. The value of the linked list node is +1

/** * @brief insert * @param * @retval * @author LZM */ with token value value
void listInsert( list_t * const pxList, listItem_t * const pxNewListItem )
{
    listItem_t *pxIterator;
    const lssLIST_BASE_TYPE xValueOfInsertion = pxNewListItem->xItemValue; // Get the new node token value
    
    /* Find */ in order
    if( xValueOfInsertion == lssLIST_MAX_VALUE )
    {
          pxIterator = pxList->xListEnd.pxPrevious;
    }
    else
    {
          for( pxIterator = ( listItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext ) /*lint ! e826 ! e740 The mini list structure is used as the list end to save RAM. This is checked and valid. */
          {
                /* There is nothing to do here, just iterating to the wanted insertion position. */
          }
    }

    pxNewListItem->pxNext = pxIterator->pxNext;
    pxNewListItem->pxNext->pxPrevious = pxNewListItem;
    pxNewListItem->pxPrevious = pxIterator;
    pxIterator->pxNext = pxNewListItem;

    /* Remember which list the item is in. This allows fast removal of the item later. */
    pxNewListItem->pvContainer = ( void * ) pxList;

    ( pxList->uxNumberOfItems )++;
}
Copy the code

Remove functions from the linked list

Note: The deleted node is hereafter referred to as node A

  1. Access list
  2. The preceding node of node A points to the preceding node of node A
  3. The next node before node A points to the next node of node A
  4. Check whether the linked list index points toA node
    1. Yes: The index is updated to the previous node pointing to node A
    2. No: skip
  5. Clear the linked list of node A
  6. The value of the linked list node is -1
  7. Returns the number of linked list nodes
/** * @brief Deletes a node from the list * @param * @retval * @author LZM */
uint32_t listRemove( listItem_t * const pxItemToRemove )
{
/* The list item knows which list it is in. Obtain the list from the list item. */
    list_t * const pxList = ( list_t * ) pxItemToRemove->pvContainer;

    pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
    pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;

    /* Make sure the index is left pointing to a valid item. */
    if( pxList->pxIndex == pxItemToRemove )
    {
          pxList->pxIndex = pxItemToRemove->pxPrevious;
    }

    pxItemToRemove->pvContainer = NULL;
    
    ( pxList->uxNumberOfItems )--;

    return pxList->uxNumberOfItems;
}

Copy the code

Source collection

  • contains
    • Nodes and linked list structures
    • Node initialization function
    • List initialization function
    • Node insertion function
    • Delete node function
    • Pair hook with sock function
    • Get node information function
    • Gets the token value function
    • Gets the node-valued function for the first node
    • Gets the entry node function of the linked list
    • Gets the next node function
    • Gets the function of the last node of the list
    • Check whether the linked list is an empty function
    • Gets the current total number of nodes function of the linked list
    • Gets the next node function to which the linked list index points
  • Jump to non – general linked list complete C language source code