Analysis of diilist.cpp in OpenGuass source code

Article directory

• Analysis of dllist.cpp
• • introduction
  • code
  • • Basic operations
    • Advanced operations
    • function definition
  • Summarize
  • Summarize

Analysis of dllist.cpp

Introduction

This file is a typical C++ file, and dllist is the abbreviation of doubly linked list, that is, a doubly linked list. Doubly linked list is a commonly used data structure. Each element (node) contains a pointer to the previous node and the next node, so the linked list can be traversed in both directions. This article continues the analysis of dllist.h in the previous article. It is recommended to read the two blogs in parallel.

Code

code address

Basic operations

Dllist* DLNewList(void)
{<!-- -->
    Dllist* l = NULL;

    l = (Dllist*)palloc(sizeof(Dllist));

    l->dll_head = NULL;
    l->dll_tail = NULL;
    l->dll_len = 0;

    return l;
}

void DLInitList(Dllist* list)
{<!-- -->
    list->dll_head = NULL;
    list->dll_tail = NULL;
    list->dll_len = 0;
}

/*
 * free up a list and all the nodes in it --- but *not* whatever the nodes
 * might point to!
 */
void DLFreeList(Dllist* list)
{<!-- -->
    Dlelem*curr = NULL;

    while ((curr = DLRemHead(list)) != NULL)
        pfree(curr);

    pfree(list);
}

Dlelem* DLNewElem(void* val)
{<!-- -->
    Dlelem* e = NULL;

    e = (Dlelem*)palloc(sizeof(Dlelem));

    e->dle_next = NULL;
    e->dle_prev = NULL;
    e->dle_val = val;
    e->dle_list = NULL;
    return e;
}

void DLInitElem(Dlelem* e, void* val)
{<!-- -->
    e->dle_next = NULL;
    e->dle_prev = NULL;
    e->dle_val = val;
    e->dle_list = NULL;
}

void DLFreeElem(Dlelem* e)
{<!-- -->
    pfree(e);
}

This code is a doubly linked list (DLL) implementation written in C language. Below is an explanation of each provided function:

1. DLNewList:

   • This function creates a new doubly linked list and initializes its properties.
   • It uses palloc (the memory allocation function provided in the environment) to allocate memory for a Dllist structure.
   • Set the dll_head and dll_tail pointers to NULL, and set dll_len to 0.
   • Finally, it returns a pointer to the newly created list.

2. DLInitList:

   • This function initializes an existing doubly linked list.
   • Set the dll_head and dll_tail pointers to NULL, and set dll_len to 0.
   • If you have allocated memory for the Dllist structure and want to reset it, you can use this function.

3. DLFreeList:

   • This function releases the doubly linked list and all nodes in it.
   • It traverses the list by repeatedly using DLRemHead to remove the head node and release each node.
   • After all nodes have been removed and freed, it frees the memory of the Dllist structure itself.
   • Be careful when using this function as it does not free the memory pointed to by the element’s dle_val. If necessary, you should handle the release of values separately.

4. DLNewElem：

   • This function creates a new doubly linked list element (node) and initializes its properties.
   • It uses palloc to allocate memory for a Dlelem structure.
   • Sets the dle_next, dle_prev, and dle_list pointers to NULL and the supplied value valis assigned to dle_val.
   • Finally, it returns a pointer to the newly created element.

5. DLInitElem:

   • This function initializes an existing doubly linked list element (node).
   • Sets the dle_next, dle_prev, and dle_list pointers to NULL and the supplied value valis assigned to dle_val.
   • Use this function if you have allocated memory for a Dlelem structure and want to reset it.

6. DLFreeElem：

   • This function frees the memory associated with a doubly linked list element (node) by calling pfree on the element itself.

This code provides the basis for using a doubly linked list, allowing you to create, initialize and release the list and the elements in it to achieve management of the DLL

Advanced operations

void DLRemove(Dlelem* e)
{<!-- -->
    Dllist* l = e->dle_list;

    if (e->dle_prev)
        e->dle_prev->dle_next = e->dle_next;
    else {<!-- -->
        /* must be the head element */
        Assert(e == l->dll_head);
        l->dll_head = e->dle_next;
    }
    if (e->dle_next)
        e->dle_next->dle_prev = e->dle_prev;
    else {<!-- -->
        /* must be the tail element */
        Assert(e == l->dll_tail);
        l->dll_tail = e->dle_prev;
    }
    if (l != NULL) {<!-- -->
        l->dll_len--;
    }

    e->dle_next = NULL;
    e->dle_prev = NULL;
    e->dle_list = NULL;
}

void DLAddHead(Dllist* l, Dlelem* e)
{<!-- -->
    e->dle_list = l;

    if (l->dll_head)
        l->dll_head->dle_prev = e;
    e->dle_next = l->dll_head;
    e->dle_prev = NULL;
    l->dll_head = e;

    if (l->dll_tail == NULL) /* if this is first element added */
        l->dll_tail = e;
    l->dll_len + + ;
}

void DLAddTail(Dllist* l, Dlelem* e)
{<!-- -->
    e->dle_list = l;

    if (l->dll_tail)
        l->dll_tail->dle_next = e;
    e->dle_prev = l->dll_tail;
    e->dle_next = NULL;
    l->dll_tail = e;

    if (l->dll_head == NULL) /* if this is first element added */
        l->dll_head = e;
    l->dll_len + + ;
}

Dlelem* DLRemHead(Dllist* l)
{<!-- -->
    /* remove and return the head */
    Dlelem* result = l->dll_head;

    if (result == NULL)
        return result;

    if (result->dle_next)
        result->dle_next->dle_prev = NULL;

    l->dll_head = result->dle_next;

    if (result == l->dll_tail) /* if the head is also the tail */
        l->dll_tail = NULL;

    l->dll_len--;
    result->dle_next = NULL;
    result->dle_list = NULL;

    return result;
}

Dlelem* DLRemTail(Dllist* l)
{<!-- -->
    /* remove and return the tail */
    Dlelem* result = l->dll_tail;

    if (result == NULL)
        return result;

    if (result->dle_prev)
        result->dle_prev->dle_next = NULL;

    l->dll_tail = result->dle_prev;

    if (result == l->dll_head) /* if the tail is also the head */
        l->dll_head = NULL;

    l->dll_len--;
    result->dle_prev = NULL;
    result->dle_list = NULL;

    return result;
}
/* Same as DLRemove followed by DLAddHead, but faster */
void DLMoveToFront(Dlelem* e)
{<!-- -->
    Dllist* l = e->dle_list;

    if (l->dll_head == e)
        return; /* Fast path if already at front */

    Assert(e->dle_prev != NULL); /* since it's not the head */
    e->dle_prev->dle_next = e->dle_next;

    if (e->dle_next)
        e->dle_next->dle_prev = e->dle_prev;
    else {<!-- -->
        /* must be the tail element */
        Assert(e == l->dll_tail);
        l->dll_tail = e->dle_prev;
    }

    l->dll_head->dle_prev = e;
    e->dle_next = l->dll_head;
    e->dle_prev = NULL;
    l->dll_head = e;
    /* We need not check dll_tail, since there must have been > 1 entry */
}

/*
 * double-linked list length
 */
uint64 DLListLength(Dllist* list)
{<!-- -->
    Dlelem* cur = list->dll_head;
    uint64 length = 0;

    while (cur != NULL) {<!-- -->
        length + + ;
        cur = cur->dle_next;
    }
    Assert(length == list->dll_len);
    return length;
}

Note: The Assert function is usually used for assertion testing (Assertion Testing) in programming. An assertion is a condition in a program that is used to check the correctness of the program. If the asserted condition is true, the program continues execution; if the condition is false, the program throws an exception or aborts execution, often used to find and diagnose errors in code.

This code contains some functions for operating doubly linked lists. Let’s explain what each function does one by one:

1. DLRemove:

   • This function is used to remove a given element (node) e from a doubly linked list.
   • It first obtains the linked list l to which element e belongs.
   • If the element e has a previous node dle_prev, point the previous node’s dle_next to the next element e Node dle_next, thereby removing e from the linked list.
   • If the element e has no previous node, that is, e is the head node, then the head pointer of the linked list l will be dll_head Points to the next node of element e.
   • Similarly, if element e has a next node dle_next, point the next node’s dle_prev to element e the previous node.
   • If the element e has no next node, that is, e is the tail node, then the tail pointer of the linked list l will be dll_tail Points to the previous node of element e.
   • Finally, if the linked list l is not NULL, reduce the length of the linked list dll_len by one, and set the relevant pointer of the element e to NULL.

   

2. DLAddHead:

   • This function is used to add an element e to the head of a doubly linked list.
   • It points the dle_list pointer of element e to the linked list l.
   • If the head node of the linked list l exists (not empty), point the previous node of the head node to the element e to ensure that the element e becomes New head node.
   • Then, point the dle_next of element e to the original head node, set dle_prev to NULL, and set the head pointer of the linked list dll_head is updated to the element e.
   • If the tail node of the linked list l is empty, it means that this is the first added element, and the tail pointer dll_tail of the linked list also points to the element e .
   • Finally, add one to the length of the linked list dll_len.

3. DLAddTail：

   • This function is used to add an element e to the end of a doubly linked list.
   • It points the dle_list pointer of element e to the linked list l.
   • If the tail node of the linked list l exists (not empty), point the next node of the tail node to the element e to ensure that the element e becomes New tail node.
   • Then, point the dle_prev of element e to the original tail node, set dle_next to NULL, and set the tail pointer of the linked list dll_tail is updated to the element e.
   • If the head node of the linked list l is empty, it means that this is the first added element, and the head pointer dll_head of the linked list also points to the element e .
   • Finally, add one to the length of the linked list dll_len.

4. DLRemHead:

   • This function removes and returns the head node from the head of a doubly linked list.
   • If the head pointer of the linked list dll_head is empty, it means that the linked list is empty and NULL is returned.
   • Otherwise, save the head node to result, and then update the head pointer of the linked list to the next node of the head node.
   • If the removed node is also the tail node, set the tail pointer dll_tail of the linked list to NULL.
   • Finally, update the length of the linked list dll_len by one, and set the relevant pointer to NULL.

5. DLRemTail：

   • This function removes and returns the tail node from the tail of a doubly linked list.
   • If the tail pointer dll_tail of the linked list is empty, it means that the linked list is empty and NULL is returned.
   • Otherwise, save the tail node to result, and then update the tail pointer of the linked list to the node before the tail node.
   • If the removed node is also the head node, set the head pointer dll_head of the linked list to NULL.
   • Finally, update the length of the linked list dll_len by one, and set the relevant pointer to NULL.

6. DLMoveToFront function:

• The purpose of this function is to move the specified element e to the head of the linked list l to speed up access. If the element e is already at the head of the linked list, the function will return directly without performing any operation.
• If element e is not at the head of the linked list, it first asserts (Assert) e->dle_prev != NULL to ensure that e is not the head of the linked list.
• Then, it removes the element e from the linked list and points the dle_next of the previous node of e to that of e The next node, thereby disconnecting e from the linked list.
• If e has a next node dle_next, point the node’s dle_prev to the previous node of e; otherwise , if e is the tail node of the linked list, update the tail pointer dll_tail of the linked list l to the previous one of e node.
• Next, point the dle_prev of the head node of the linked list l to e, and point the dle_next< of e to /code> points to the head node of the linked list, sets the dle_prev of e to NULL, and finally updates the linked list head pointer dll_head is e.
• Since it has already been checked whether e is the head node or tail node of the linked list, there is no need to check dll_tail again

DllistWithLock::DllistWithLock() {<!-- -->
    DLInitList( & amp;m_list); // init list
    SpinLockInit( & amp;m_lock); // init lock
}

DllistWithLock::~DllistWithLock() {<!-- -->
    SpinLockFree( & amp;m_lock); // free lock
}

bool DllistWithLock::RemoveConfirm(Dlelem* e) {<!-- -->
    bool found = false; // found flag
    START_CRIT_SECTION(); // start critical section, avoid interrupt
    SpinLockAcquire( & amp;(m_lock)); // get lock
    if (e->dle_list == & amp;m_list) {<!-- --> // if e is in list
        found = true;
        DLRemove(e); // remove e from list
    }
    SpinLockRelease( & amp;(m_lock)); // release lock
    END_CRIT_SECTION(); // end critical section
    return found; // return found flag
}

void DllistWithLock::AddHead(Dlelem* e) {<!-- -->
    START_CRIT_SECTION(); // start critical section
    SpinLockAcquire( & amp;(m_lock)); // get lock
    if (e->dle_list == NULL) {<!-- --> // if e is not in list
        DLAddHead( & amp;m_list, e); // add e to list
    }
    SpinLockRelease( & amp;(m_lock)); // release lock
    END_CRIT_SECTION(); // end critical section
}

void DllistWithLock::AddTail(Dlelem* e) {<!-- -->
    START_CRIT_SECTION(); // start critical section
    SpinLockAcquire( & amp;(m_lock)); // get lock
    if (e->dle_list == NULL) {<!-- --> // if e is not in list
        DLAddTail( & amp;m_list, e); // add e to list
    }
    SpinLockRelease( & amp;(m_lock)); // release lock
    END_CRIT_SECTION(); // end critical section
}

Dlelem* DllistWithLock::RemoveHead() {<!-- -->
    Dlelem* head = NULL; // head pointer
    START_CRIT_SECTION(); // start critical section
    SpinLockAcquire( & amp;(m_lock)); // get lock
    head = DLRemHead( & amp;m_list); // remove head from list
    SpinLockRelease( & amp;(m_lock)); // release lock
    END_CRIT_SECTION(); // end critical section
    return head; // return head pointer
}

Dlelem* DllistWithLock::RemoveTail() {<!-- -->
    Dlelem* head = NULL; // head pointer
    START_CRIT_SECTION(); // start critical section
    SpinLockAcquire( & amp;(m_lock)); // get lock
    head = DLRemTail( & amp;m_list); // remove tail from list
    SpinLockRelease( & amp;(m_lock)); // release lock
    END_CRIT_SECTION(); // end critical section
    return head; // return head pointer
}

bool DllistWithLock::IsEmpty() {<!-- -->
    START_CRIT_SECTION(); // start critical section
    SpinLockAcquire( & amp;(m_lock)); // get lock
    bool ret = DLIsNIL( & amp;m_list); // judge whether list is empty
    SpinLockRelease( & amp;(m_lock)); // release lock
    END_CRIT_SECTION(); // end critical section
    return ret; // return result
}

Dlelem* DllistWithLock::GetHead() {<!-- -->
    Dlelem* head = NULL; // head pointer
    head = m_list.dll_head; // get head pointer
    return head; // return head pointer
}

void DllistWithLock::GetLock() {<!-- -->
    START_CRIT_SECTION(); // start critical section
    SpinLockAcquire( & amp;(m_lock)); // get lock
}

Dlelem* DllistWithLock::RemoveHeadNoLock() {<!-- -->
    Dlelem* head = DLRemHead( & amp;m_list); // remove head from list
    return head; // return head pointer
}

void DllistWithLock::ReleaseLock() {<!-- -->
    SpinLockRelease( & amp;(m_lock)); // release lock
    END_CRIT_SECTION(); // end critical section
}