#linked-list #kernel #environment #circular #hairy

nightly clist

A hairy circular linked list for no_std environments

1 unstable release

0.1.1 Apr 27, 2022

#34 in #circular

Apache-2.0

25KB
607 lines

Introduction

This library is part of RIOT-rs.

This is a try to use linked lists to keep track kernel objects (like, threads, locks, ...).


lib.rs:

This crate contains a circularly and singly linked list implementation.

Its operations are:

operation runtime description
clist::lpush() O(1) insert as head (leftmost node)
clist::lpeek() O(1) get the head without removing it
clist::lpop() O(1) remove and return head (leftmost node)
clist::rpush() O(1) append as tail (rightmost node)
clist::rpeek() O(1) get the tail without removing it
clist::rpop() O(n) remove and return tail (rightmost node)
clist::lpoprpush() O(1) move first element to the end of the list
clist::contains( O(n) check if list contains element
clist::find() O(n) find and return node
clist::find_before() O(n) find node return node pointing to node
clist::remove() O(n) remove and return node
clist::sort() O(NlogN) sort list (stable)
clist::count() O(n) count the number of elements in a list

clist can be used as a traditional list, a queue (FIFO) and a stack (LIFO) using fast O(1) operations.

Dependencies

~37KB