3
\$\begingroup\$

This is a follow-up from my previous question. In summary, I am trying to implement a BVH module with Cython and need a way to keep track of the volumes during the construction of the hierarchy.

I was going to use a Doubly linked list for that purpose as it allows for efficiently inserting and popping items from either side, but a user pointed that many APIs use a circular version of the list to avoid problems.

I decided to implement such a list, also tried to make it more general so it can be useful for further projects.


cdef struct CDLinkedList:
    ListNode* head
    int length

cdef struct ListNode:
    ListNode** links #[0] = previous, [1] = next or vice versa, doesn't matter.
    void* data

cdef ListNode* list_node_create(void* data) nogil:
    cdef ListNode* n = <ListNode *> malloc(sizeof(ListNode))
    n.links = <ListNode **> malloc(sizeof(ListNode*) * 2)
    n.data = data
    return n

cdef void list_node_free(ListNode* node) nogil:
    free(node.links)
    free(node)

cdef CDLinkedList* list_create() nogil:
    cdef CDLinkedList* lst = <CDLinkedList *> malloc(sizeof(CDLinkedList))
    lst.head = list_node_create(NULL)
    lst.head.links[0] = lst.head
    lst.head.links[1] = lst.head
    lst.length = 0
    return lst

cdef void list_free(CDLinkedList* lst) nogil:
    while lst.length > 0:
        list_pop(lst, 0)
    list_node_free(lst.head)
    free(lst)

cdef void list_insert(CDLinkedList* lst, void* data, int link_side) nogil:
    cdef:
        int next = link_side
        int prev = 1 - link_side
        ListNode* next_node = lst.head.links[next]
        ListNode* new_node = list_node_create(data)
    next_node.links[prev] = new_node
    lst.head.links[next] = new_node
    new_node.links[prev] = lst.head
    new_node.links[next] = next_node
    lst.length += 1

cdef void* list_pop(CDLinkedList* lst, int link_side) nogil:
    if lst.length <= 0:
        return NULL
    cdef:
        int next = link_side
        int prev = 1 - link_side
        ListNode* next_node = lst.head.links[next]
        ListNode* next_next_node = next_node.links[next]
        void* data = next_node.data
    lst.head.links[next] = next_next_node
    next_next_node.links[prev] = lst.head
    list_node_free(next_node)
    lst.length -= 1
    return data

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.