Skip to content
  • Jim Huang's avatar
    284f69d2
    Rewrite with circular doubly-linked list · 284f69d2
    Jim Huang authored
    In original CMU assignment, a singly-linked list was used. However,
    toward to Linux kernel development, we would like to stick to its linked
    list implementation. That is, we take the circular doubly-linked list to
    re-implement the queue oriented operations. In addition, we introduce
    some LeetCode exercises based on Linux-like lists.
    
    Now, queue is replaced with linux kernel linked list. Also, implementation
    of l_new, l_free, l_insert_head, l_insert_tail, l_remove_head and l_size
    are added.
    
    Implementation of l_sort and l_reverse are added.
    
    Add command "mid" which would return the middle element in list.
    Relative test also be added in this commit
    
    Add command "swap" which would swap every two adjacent nodes in list.
    Relative test also be added in this commit.
    Reference:
        https://leetcode.com/problems/swap-nodes-in-pairs/
    
    Replace "get_mid" with "remove_mid", which is LeetCode problem.
    Relative test bench also be updated in this commit.
    Reference:
        https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    
    
    
    Add command remove_tail.
    
    Suppress the null pointer errors
    
    Newer versions of cppcheck find the potential NULL pointer
    bug in list_entry. The function is difficult to refactor without
    extensive work, so suppress the potential NULL pointer error
    which cannot occur for now.
    
    remove_tail and remove_head was re-desinged. We extract "free" from
    remove_.* because "free" is not stable (lead not constant time).
    Relative testbench also update in this commit.
    
    Add function "is_circular" which check if the queue is doubly circular.
    
    Suppress simulation of list removal on Arm64
    
    We suffered from some unknown issues that simulation of list removal can
    not pass on Arm64 based platforms such as ThunderX2/Linux and Apple M1
    (macOS).
    
    At the moment, we just skip the simulations for Arm64.
    
    We support new command: dedup.
    Relative test bench also be updated.
    
    Co-authored-by: default avatareecheng87 <yucheng871011@gmail.com>
    284f69d2
    Rewrite with circular doubly-linked list
    Jim Huang authored
    In original CMU assignment, a singly-linked list was used. However,
    toward to Linux kernel development, we would like to stick to its linked
    list implementation. That is, we take the circular doubly-linked list to
    re-implement the queue oriented operations. In addition, we introduce
    some LeetCode exercises based on Linux-like lists.
    
    Now, queue is replaced with linux kernel linked list. Also, implementation
    of l_new, l_free, l_insert_head, l_insert_tail, l_remove_head and l_size
    are added.
    
    Implementation of l_sort and l_reverse are added.
    
    Add command "mid" which would return the middle element in list.
    Relative test also be added in this commit
    
    Add command "swap" which would swap every two adjacent nodes in list.
    Relative test also be added in this commit.
    Reference:
        https://leetcode.com/problems/swap-nodes-in-pairs/
    
    Replace "get_mid" with "remove_mid", which is LeetCode problem.
    Relative test bench also be updated in this commit.
    Reference:
        https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    
    
    
    Add command remove_tail.
    
    Suppress the null pointer errors
    
    Newer versions of cppcheck find the potential NULL pointer
    bug in list_entry. The function is difficult to refactor without
    extensive work, so suppress the potential NULL pointer error
    which cannot occur for now.
    
    remove_tail and remove_head was re-desinged. We extract "free" from
    remove_.* because "free" is not stable (lead not constant time).
    Relative testbench also update in this commit.
    
    Add function "is_circular" which check if the queue is doubly circular.
    
    Suppress simulation of list removal on Arm64
    
    We suffered from some unknown issues that simulation of list removal can
    not pass on Arm64 based platforms such as ThunderX2/Linux and Apple M1
    (macOS).
    
    At the moment, we just skip the simulations for Arm64.
    
    We support new command: dedup.
    Relative test bench also be updated.
    
    Co-authored-by: default avatareecheng87 <yucheng871011@gmail.com>
Loading