• Alice Ryhl's avatar
    rust: list: add List · db841866
    Alice Ryhl authored
    Add the actual linked list itself.
    
    The linked list uses the following design: The List type itself just has
    a single pointer to the first element of the list. And the actual list
    items then form a cycle. So the last item is `first->prev`.
    
    This is slightly different from the usual kernel linked list. Matching
    that exactly would amount to giving List two pointers, and having it be
    part of the cycle of items. This alternate design has the advantage that
    the cycle is never completely empty, which can reduce the number of
    branches in some cases. However, it also has the disadvantage that List
    must be pinned, which this design is trying to avoid.
    
    Having the list items form a cycle rather than having null pointers at
    the beginning/end is convenient for several reasons. For one, it lets us
    store only one pointer in List, and it simplifies the implementation of
    several functions.
    
    Unfortunately, the `remove` function that removes an arbitrary element
    from the list has to be unsafe. This is needed because there is no way
    to handle the case where you pass an element from the wrong list. For
    example, if it is the first element of some other list, then that other
    list's `first` pointer would not be updated. Similarly, it could be a
    data race if you try to remove it from two different lists in parallel.
    (There's no problem with passing `remove` an item that's not in any
    list. Additionally, other removal methods such as `pop_front` need not
    be unsafe, as they can't be used to remove items from another list.)
    
    A future patch in this series will introduce support for cursors that
    can be used to remove arbitrary items without unsafe code.
    Reviewed-by: default avatarBenno Lossin <benno.lossin@proton.me>
    Signed-off-by: default avatarAlice Ryhl <aliceryhl@google.com>
    Link: https://lore.kernel.org/r/20240814-linked-list-v5-6-f5f5e8075da0@google.com
    [ Fixed a few typos. - Miguel ]
    Signed-off-by: default avatarMiguel Ojeda <ojeda@kernel.org>
    db841866
arc.rs 19.7 KB