list.h

Go to the documentation of this file.

// Copyright 2021-2025 The Aerospace Corporation.
// This file is a part of SatCat5, licensed under CERN-OHL-W v2 or later.
 
#pragma once
 
namespace satcat5 {
    namespace util {
        class ListCore {
        public:
            template <class T> static inline
            void add(T*& list, T* item) {
                satcat5::util::ListCore::push_front(list, item);
            }
 
            template <class T> static inline
            void add_list(T*& list1, T*& list2) {
                while (T* item = satcat5::util::ListCore::pop_front(list2)) {
                    satcat5::util::ListCore::add(list1, item);
                }
            }
 
            template <class T> static inline
            void add_safe(T*& list, T* item) {
                if (!satcat5::util::ListCore::contains(list, item))
                    satcat5::util::ListCore::add(list, item);
            }
 
            template <class T> static inline
            bool contains(const T* list, const T* item) {
                const T* ptr = list;
                while (ptr) {
                    if (ptr == item) return true;
                    ptr = ptr->m_next;
                }
                return false;
            }
 
            template <class T> static inline
            T** find_ptr(T** list, const T* item) {
                T** ptr = list;
                while (1) {
                    if (*ptr == item) return ptr;   // Found a match?
                    if (*ptr == 0) return 0;        // End of list?
                    ptr = &((*ptr)->m_next);
                }
            }
 
            template <class T> static inline
            T* get_index(T* list, unsigned idx) {
                T* ptr = list;
                while (ptr && idx--) {
                    ptr = ptr->m_next;
                }
                return ptr;
            }
 
            template <class T> static inline
            bool has_loop(const T* list) {
                if (!list) return false;    // Empty list has no loops.
                const T* slow = list;
                const T* fast = list->m_next;
                while (fast && fast->m_next) {
                    if (slow == fast || slow == fast->m_next) return true;
                    slow = slow->m_next;
                    fast = fast->m_next->m_next;
                }
                return false;               // Reached end with no loops.
            }
 
            template <class T> static inline
            void insert_after(T* where, T* item) {
                if (where && item) {
                    item->m_next = where->m_next;
                    where->m_next = item;
                }
            }
 
            template <class T> static inline
            unsigned len(const T* list) {
                unsigned count = 0;
                const T* ptr = list;
                while (ptr) {
                    ++count;
                    ptr = ptr->m_next;
                }
                return count;
            }
 
            template <class T> static inline
            T* next(const T* item) {
                return item->m_next;
            }
 
            template <class T> static inline
            T* pop_front(T*& list) {
                if (!list) return 0;
                T* item = list;
                list = item->m_next;
                item->m_next = 0;
                return item;
            }
 
            template <class T> static inline
            void push_front(T*& list, T* item) {
                item->m_next = list;
                list = item;
            }
 
            template <class T> static inline
            void push_back(T*& list, T* item) {
                T** ptr = satcat5::util::ListCore::find_ptr<T>(&list, 0);
                *ptr = item;
                item->m_next = 0;
            }
 
            template <class T> static inline
            void remove(T*& list, T* item) {
                T** ptr = satcat5::util::ListCore::find_ptr<T>(&list, item);
                if (ptr) *ptr = item->m_next;
                item->m_next = 0;
            }
 
            template <class T> static inline
            void reset(T*& list, T* item) {
                list = item;
                if (item) item->m_next = 0;
            }
 
            template <class T> static inline
            bool pre_test_reset(T*& list, T* item) {
                bool adj = (list != item) || (item && list->m_next);
                if (adj) reset(list, item);
                return adj;
            }
        };
 
        template <class T> class List final {
        public:
            constexpr List()
                : m_head(0) {}      
            constexpr explicit List(T* item)
                : m_head(item) {}   
            ~List() {}              
 
            T* head() const {return m_head;}
 
            inline void add(T* item)
                {satcat5::util::ListCore::add(m_head, item);}
 
            inline void add_list(satcat5::util::List<T>& other)
                {satcat5::util::ListCore::add_list(m_head, other.m_head);}
 
            inline void add_safe(T* item)
                {satcat5::util::ListCore::add_safe(m_head, item);}
 
            inline bool contains(const T* item) const
                {return satcat5::util::ListCore::contains(m_head, item);}
 
            inline T* get_index(unsigned idx)
                {return satcat5::util::ListCore::get_index(m_head, idx);}
 
            inline bool has_loop() const
                {return satcat5::util::ListCore::has_loop(m_head);}
 
            inline void insert_after(T* where, T* item)
                {satcat5::util::ListCore::insert_after(where, item);}
 
            inline bool is_empty() const
                {return m_head == 0;}
 
            inline unsigned len() const
                {return satcat5::util::ListCore::len(m_head);}
 
            inline T* next(const T* item) const
                {return satcat5::util::ListCore::next(item);}
 
            inline T* pop_front()
                {return satcat5::util::ListCore::pop_front(m_head);}
 
            inline void push_front(T* item)
                {satcat5::util::ListCore::push_front(m_head, item);}
 
            inline void push_back(T* item)
                {satcat5::util::ListCore::push_back(m_head, item);}
 
            inline void remove(T* item)
                {satcat5::util::ListCore::remove(m_head, item);}
 
            inline void reset(T* item = 0)
                {return satcat5::util::ListCore::reset(m_head, item);}
 
        protected:
            T* m_head;  
        };
    }
};