linked_list.h

Go to the documentation of this file.

// Copyright Microsoft and CHERIoT Contributors.
// SPDX-License-Identifier: MIT
 
/**
 * @file
 * A (circular) doubly linked list, abstracted over cons cell
 * representations.
 *
 * See `tests/list-test.cc` for additional information on how to use it.
 */
 
#pragma once
 
#include <concepts>
#include <ds/pointer.h>
 
namespace ds::linked_list
{
 
    namespace cell
    {
        /**
         * The primitive, required, abstract interface to our cons cells.
         *
         * All methods are "namespaced" with `cell_` to support the case where
         * the encoded forms are also representing other state (for example,
         * bit-packed flags in pointer address bits).
         */
        template<typename T>
        concept HasCellOperations = requires(T &t) {
            /** Proxies for list linkages */
            { t.cell_next() } -> ds::pointer::proxy::Proxies<T>;
            { t.cell_prev() } -> ds::pointer::proxy::Proxies<T>;
        };
 
        /**
         * Reset a cell to a singleton ring.  Not all cons cells are required to
         * be able to do this, though if you're sticking to rings and not
         * (ab)using the machinery here in interesting ways, this should be easy
         * to specify.
         *
         * This is a method, and not a constructor, to handle cases where the
         * cell is also packing other state into its representation.
         */
        template<typename T>
        concept HasReset = requires(T &t) {
            { t.cell_reset() } -> std::same_as<void>;
        };
 
        template<typename T>
        concept HasCellOperationsReset = HasCellOperations<T> && HasReset<T>;
 
        /**
         * Additional, optional overrides available within implementation of
         * cons cells.  It may be useful to static_assert() these in
         * implementations to make sure we are not falling back to the defaults
         * in terms of the above primops.
         *
         * @{
         */
        template<typename T>
        concept HasIsSingleton = requires(T &t) {
            { t.cell_is_singleton() } -> std::same_as<bool>;
        };
 
        template<typename T>
        concept HasIsSingletonCheck = requires(T &t) {
            { t.cell_is_singleton_check() } -> std::same_as<bool>;
        };
 
        template<typename T>
        concept HasIsDoubleton = requires(T &t) {
            { t.cell_is_doubleton() } -> std::same_as<bool>;
        };
 
        /** @} */
 
    } // namespace cell
 
    /**
     * Self-loops indicate either the sentinels of an empty list or,
     * less often, singletons without their sentinels; it's up to
     * the caller to know which is being tested for, here.
     *
     * The default implementation decodes and compares one link;
     * implementations may have more efficient mechanisms.
     *
     * @{
     */
    template<cell::HasCellOperations T>
        requires(!cell::HasIsSingleton<T>)
    __always_inline bool is_singleton(T *e)
    {
        return e == e->cell_prev();
    }
 
    template<cell::HasCellOperations T>
        requires(cell::HasIsSingleton<T>)
    __always_inline bool is_singleton(T *e)
    {
        return e->cell_is_singleton();
    }
    /** @} */
 
    /**
     * Like is_singleton(), but checks both edges.  Useful only for
     * testing invariants.
     *
     * The default implementation decodes and compares both links.
     */
    template<cell::HasCellOperations T>
        requires(!cell::HasIsSingletonCheck<T>)
    __always_inline bool is_singleton_check(T *e)
    {
        return (e == e->cell_next()) && (e == e->cell_prev());
    }
 
    template<cell::HasCellOperations T>
        requires(cell::HasIsSingletonCheck<T>)
    __always_inline bool is_singleton_check(T *e)
    {
        return e->is_singleton_check();
    }
    /** @} */
 
    /**
     * Doubletons are either singleton collections (with both the sentinel
     * and the single element satisfying this test) or, less often, a pair
     * of elements without a sentinel.  The caller is expected to know
     * what's meant by this test.
     *
     * The default implementation decodes and compares both links.
     * @{
     */
    template<cell::HasCellOperations T>
        requires(!cell::HasIsDoubleton<T>)
    __always_inline bool is_doubleton(T *e)
    {
        return e->cell_prev() == e->cell_next();
    }
 
    template<cell::HasCellOperations T>
        requires(cell::HasIsDoubleton<T>)
    __always_inline bool is_doubleton(T *e)
    {
        return e->cell_is_doubleton();
    }
    /** @} */
 
    /**
     * Verify linkage invariants.  Again, useful only for testing.
     *
     * The default implementation decodes all four relevant links.
     */
    template<cell::HasCellOperations T>
    __always_inline bool is_well_formed(T *e)
    {
        return (e == e->cell_prev()->cell_next()) &&
               (e == e->cell_next()->cell_prev());
    }
 
    /**
     * Insert a ring of `elem`-ents (typically, a singleton ring) before the
     * `curr`-ent element (or sentinel) in the ring.  In general, you will
     * probably want to make sure that at most one of `elem` or `curr`
     * points to a ring with a sentinel node.
     *
     * If `curr` is the sentinel, this is appending to the list, in the
     * sense that the element(s) occupy (or span) the next-most and
     * prev-least position from the sentinel.
     *
     * By symmetry, if `elem` is, instead, the sentinel, then `curr` is
     * prepended to the list in the same sense.
     */
    template<cell::HasCellOperations Cell>
    __always_inline void insert_before(Cell *curr, Cell *elem)
    {
        curr->cell_prev()->cell_next() = elem->cell_next();
        elem->cell_next()->cell_prev() = curr->cell_prev();
        curr->cell_prev()              = elem;
        elem->cell_next()              = curr;
    }
 
    /**
     * Emplacement before.  This fuses initialization and insertion, so that
     *
     *    emplace_before(c, e);
     *
     * is semantically equivalent to
     *
     *    e->cell_reset(); insert_before(c, e);
     *
     * but spelled in a way that the compiler can understand a bit better, with
     * less effort spent in provenance and/or alias analysis.
     */
    template<cell::HasCellOperations Cell, typename P>
        requires std::same_as<P, Cell *> || ds::pointer::proxy::Proxies<P, Cell>
    __always_inline void emplace_before(P curr, Cell *elem)
    {
        auto prev         = curr->cell_prev();
        elem->cell_next() = curr;
        elem->cell_prev() = prev;
        prev->cell_next() = elem;
        prev              = elem;
    }
 
    /**
     * Emplacement after.  This fuses initialization and insertion, so that
     *
     *    emplace_after(c, e);
     *
     * is semantically equivalent to
     *
     *    e->cell_reset(); insert_before(e, c);
     *
     * but spelled in a way that the compiler can understand a bit better, with
     * less effort spent in provenance and/or alias analysis.
     */
    template<cell::HasCellOperations Cell, typename P>
        requires std::same_as<P, Cell *> || ds::pointer::proxy::Proxies<P, Cell>
    __always_inline void emplace_after(P curr, Cell *elem)
    {
        auto next         = curr->cell_next();
        elem->cell_prev() = curr;
        elem->cell_next() = next;
        next->cell_prev() = elem;
        next              = elem;
    }
 
    /**
     * Remove from the list without turning the removed span into a
     * well-formed ring.  This is useful only if that invariant will be
     * restored later (prior to insertion, at the very least).
     *
     * The removed element or span instead retains links into the ring
     * whence it was removed, but is no longer well-formed, since that ring
     * no longer references the removed element or span.
     *
     * This can be used to remove...
     *
     *   - a single element (`el == er`)
     *
     *   - the sentinel (`el == er`), leaving the rest of the ring, if any,
     *     as a sentinel-free ring
     *
     *   - a span of elements from `el` to `er` via the `next` links; the
     *     removed span is damaged and must be corrected, while the residual
     *     ring remains well-formed.
     *
     * In all cases, `el`'s previous element is returned as a handle to the
     * residual ring.
     */
    template<cell::HasCellOperations Cell>
    __always_inline Cell *unsafe_remove(Cell *el, Cell *er)
    {
        auto p         = el->cell_prev();
        auto n         = er->cell_next();
        n->cell_prev() = p;
        p->cell_next() = n;
        return p;
    }
 
    template<cell::HasCellOperations Cell>
    __always_inline Cell *unsafe_remove(Cell *e)
    {
        return unsafe_remove(e, e);
    }
 
    /**
     * Remove a particular element `rem` from the ring, already knowing its
     * adjacent, previous link `prev`.  `prev` remains connected to the ring
     * but `rem` will no longer be well-formed.  Returns a proxy to prev's
     * next field.
     */
    template<cell::HasCellOperations Cell>
    __always_inline auto unsafe_remove_link(Cell *prev, Cell *rem)
    {
        auto next         = rem->cell_next();
        auto prevnext     = prev->cell_next();
        prevnext          = next;
        next->cell_prev() = prev;
        return prevnext;
    }
 
    /**
     * Remove from the ring, cleaving the ring into two well-formed rings.
     *
     * This can be used to remove...
     *
     *   - a single element (`el == er`)
     *
     *   - the sentinel (`el == er`), leaving the rest of the ring, if any,
     *     as a sentinel-free collection
     *
     *   - a span of elements from `el` to `er` via `next` links; the
     *     removed span is made into a ring and the residual ring is left
     *     well-formed.
     *
     * In all cases, `el`'s previous element is returned as a handle to the
     * residual ring.  (The caller must already have a reference to the span
     * being removed).  This is especially useful when `remove`-ing elements
     * during a `search`, below: overwriting the callback's Cell pointer
     * (passed by *reference*) will continue the iteration, calling back at
     * the removed node's successor.
     *
     * Removing a singleton from its ring from itself causes no change, as
     * any would-be residual ring is empty.  This corner case requires some
     * care on occasion.
     */
    template<cell::HasCellOperations Cell>
    __always_inline Cell *remove(Cell *el, Cell *er)
    {
        Cell *p         = unsafe_remove(el, er);
        el->cell_prev() = er;
        er->cell_next() = el;
        return p;
    }
 
    template<cell::HasCellOperations Cell>
    __always_inline Cell *remove(Cell *e)
    {
        return remove(e, e);
    }
 
    /**
     * Search through a span of a ring, inclusively from `from` through
     * exclusively to `to`, applying `f` to each cons cell in turn.  If `f`
     * returns `true`, the search stops early and returns `true`; otherwise,
     * search returns `false`.  To (side-effectfully) visit every node in the
     * span, have `f` always return false.
     */
    template<cell::HasCellOperations Cell, typename F>
    __always_inline bool search(Cell *from, Cell *to, F f)
    {
        Cell *elem;
        for (elem = from; elem != to; elem = elem->cell_next())
        {
            if (f(elem))
            {
                return true;
            }
        }
        return false;
    }
 
    /**
     * Search through all elements of a ring *except* `elem`.  If `elem` is the
     * sentinel of a ring, then this is, as one expects, a `search` over all
     * non-sentinel members of the ring.
     */
    template<cell::HasCellOperations Cell, typename F>
    __always_inline bool search(Cell *elem, F f)
    {
        return search(static_cast<Cell *>(elem->cell_next()), elem, f);
    }
 
    /**
     * Convenience wrapper for a sentinel cons cell, encapsulating some common
     * patterns.
     */
    template<cell::HasCellOperationsReset CellTemplateArg>
    struct Sentinel
    {
        using Cell = CellTemplateArg;
 
        /**
         * The sentinel node itself.  Viewing the ring as a list, this
         * effectively serves as pointers to the head (next) and to the tail
         * (prev) of the list.  Unlike more traditional nullptr-terminated
         * lists, though, here, the sentinel participates in the ring.
         *
         * This is marked `cheri_no_subobject_bounds` because some of our cons
         * cell implementations use pointer proxies that rely on the bounds
         * provided by `this` (which, in turn, is likely to be
         * `cheri_no_subobject_bounds`)
         */
        Cell sentinel __attribute__((__cheri_no_subobject_bounds__)) = {};
 
        __always_inline void reset()
        {
            sentinel.cell_reset();
        }
 
        __always_inline bool is_empty()
        {
            return linked_list::is_singleton(&sentinel);
        }
 
        __always_inline void append(Cell *elem)
        {
            linked_list::insert_before(&sentinel, elem);
        }
 
        __always_inline void append_emplace(Cell *elem)
        {
            linked_list::emplace_before(&sentinel, elem);
        }
 
        __always_inline void prepend(Cell *elem)
        {
            linked_list::insert_before(elem, &sentinel);
        }
 
        __always_inline Cell *first()
        {
            return sentinel.cell_next();
        }
 
        __always_inline Cell *last()
        {
            return sentinel.cell_prev();
        }
 
        __always_inline Cell *unsafe_take_first()
        {
            Cell *f = sentinel.cell_next();
            linked_list::unsafe_remove_link(&sentinel, f);
            return f;
        }
 
        __always_inline Cell *take_all()
        {
            auto p = linked_list::unsafe_remove(&sentinel);
            sentinel.cell_reset();
            return p;
        }
 
        template<typename F>
        __always_inline bool search(F f)
        {
            return linked_list::search(&sentinel, f);
        }
    };
 
    namespace cell
    {
 
        /** Cons cell using two pointers */
        class Pointer
        {
            Pointer *prev, *next;
 
            public:
            Pointer()
            {
                this->cell_reset();
            }
 
            __always_inline void cell_reset()
            {
                prev = next = this;
            }
 
            __always_inline auto cell_next()
            {
                return ds::pointer::proxy::Pointer(next);
            }
 
            __always_inline auto cell_prev()
            {
                return ds::pointer::proxy::Pointer(prev);
            }
        };
        static_assert(HasCellOperationsReset<Pointer>);
 
        /**
         * Encode a linked list cons cell as a pair of addresses (but present an
         * interface in terms of pointers).  CHERI bounds on the returned
         * pointers are inherited from the pointer to `this` cons cell.
         */
        class __cheri_no_subobject_bounds PtrAddr
        {
            ptraddr_t prev, next;
 
            public:
            PtrAddr()
            {
                this->cell_reset();
            }
            /* Primops */
 
            __always_inline void cell_reset()
            {
                prev = next = CHERI::Capability{this}.address();
            }
 
            __always_inline auto cell_next()
            {
                return ds::pointer::proxy::PtrAddr(this, next);
            }
 
            __always_inline auto cell_prev()
            {
                return ds::pointer::proxy::PtrAddr(this, prev);
            }
 
            /*
             * Specialized implementations that may be slightly fewer
             * instructions than the generic approaches in terms of the primops.
             */
 
            __always_inline bool cell_is_singleton()
            {
                return prev == CHERI::Capability{this}.address();
            }
 
            __always_inline bool cell_is_doubleton()
            {
                return prev == next;
            }
        };
        static_assert(HasCellOperationsReset<PtrAddr>);
        static_assert(HasIsSingleton<PtrAddr>);
        static_assert(HasIsDoubleton<PtrAddr>);
 
        /**
         * Encode a linked list cons cell as a pair of addresses (but present an
         * interface in terms of pointers).  CHERI bounds on the returned
         * pointers are inherited from the pointer to `this` cons cell.
         */
        template<ptrdiff_t Offset>
        class OffsetPtrAddr
        {
            ptraddr_t prev, next;
 
            public:
            OffsetPtrAddr()
            {
                this->cell_reset();
            }
 
            /* Primops */
 
            __always_inline void cell_reset()
            {
                prev = next = CHERI::Capability{this}.address() - Offset;
            }
 
            __always_inline auto cell_next()
            {
                return ds::pointer::proxy::OffsetPtrAddr<Offset, OffsetPtrAddr>(
                  this, next);
            }
 
            __always_inline auto cell_prev()
            {
                return ds::pointer::proxy::OffsetPtrAddr<Offset, OffsetPtrAddr>(
                  this, prev);
            }
 
            /*
             * Specialized implementations that may be slightly fewer
             * instructions than the generic approaches in terms of the primops.
             */
 
            __always_inline bool cell_is_singleton()
            {
                return prev == CHERI::Capability{this}.address() - Offset;
            }
 
            __always_inline bool cell_is_doubleton()
            {
                return prev == next;
            }
        };
        static_assert(HasCellOperationsReset<OffsetPtrAddr<0>>);
        static_assert(HasIsSingleton<OffsetPtrAddr<0>>);
        static_assert(HasIsDoubleton<OffsetPtrAddr<0>>);
 
    } // namespace cell
 
} // namespace ds::linked_list