source/utils/RtLinkedList.hpp

   1 /*
   2  * High-level, real-time safe, templated, C++ doubly-linked list
   3  * Copyright (C) 2013-2022 Filipe Coelho <falktx@falktx.com>
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License as
   7  * published by the Free Software Foundation; either version 2 of
   8  * the License, or any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13  * GNU General Public License for more details.
  14  *
  15  * For a full copy of the GNU General Public License see the doc/GPL.txt file.
  16  */
  17
  18 #ifndef RT_LINKED_LIST_HPP_INCLUDED
  19 #define RT_LINKED_LIST_HPP_INCLUDED
  20
  21 #include "LinkedList.hpp"
  22
  23 extern "C" {
  24 /* full path as IDE Helper */
  25 #include "../modules/rtmempool/rtmempool.h"
  26 }
  27
  28 // -----------------------------------------------------------------------
  29 // Realtime safe linkedlist
  30
  31 template<typename T>
  32 class RtLinkedList : public AbstractLinkedList<T>
  33 {
  34 public:
  35     // -------------------------------------------------------------------
  36     // RtMemPool C++ class
  37
  38     class Pool
  39     {
  40     public:
  41         Pool(const char* const poolName, const std::size_t minPreallocated, const std::size_t maxPreallocated) noexcept
  42             : kDataSize(sizeof(typename AbstractLinkedList<T>::Data)),
  43               kPoolName(carla_strdup_safe(poolName)),
  44               fHandle(nullptr)
  45         {
  46             rtsafe_memory_pool_create(&fHandle, nullptr, kDataSize, minPreallocated, maxPreallocated);
  47             CARLA_SAFE_ASSERT(fHandle != nullptr);
  48         }
  49
  50         ~Pool() noexcept
  51         {
  52             if (fHandle != nullptr)
  53             {
  54                 carla_debug("Destroying %s", kPoolName);
  55                 rtsafe_memory_pool_destroy(fHandle);
  56                 fHandle = nullptr;
  57             }
  58             delete[] kPoolName;
  59         }
  60
  61         void* allocate_atomic() const noexcept
  62         {
  63             return rtsafe_memory_pool_allocate_atomic(fHandle);
  64         }
  65
  66         void* allocate_sleepy() const noexcept
  67         {
  68             return rtsafe_memory_pool_allocate_sleepy(fHandle);
  69         }
  70
  71         void deallocate(void* const dataPtr) const noexcept
  72         {
  73             CARLA_SAFE_ASSERT_RETURN(dataPtr != nullptr,);
  74
  75             rtsafe_memory_pool_deallocate(fHandle, dataPtr);
  76         }
  77
  78         bool operator==(const Pool& pool) const noexcept
  79         {
  80             return (fHandle == pool.fHandle && kDataSize == pool.kDataSize);
  81         }
  82
  83         bool operator!=(const Pool& pool) const noexcept
  84         {
  85             return (fHandle != pool.fHandle || kDataSize != pool.kDataSize);
  86         }
  87
  88     private:
  89         const std::size_t kDataSize;
  90         const char* const kPoolName;
  91
  92         mutable RtMemPool_Handle fHandle;
  93
  94         CARLA_PREVENT_HEAP_ALLOCATION
  95         CARLA_DECLARE_NON_COPYABLE(Pool)
  96     };
  97
  98     // -------------------------------------------------------------------
  99     // Now the actual rt-linkedlist code
 100
 101     RtLinkedList(Pool& memPool) noexcept
 102         : fMemPool(memPool) {}
 103
 104 #ifdef STOAT_TEST_BUILD
 105     // overridden for stoat
 106     bool append(const T& value) noexcept
 107     {
 108         if (typename AbstractLinkedList<T>::Data* const data = _allocate())
 109             return this->_add_internal(data, value, true, &this->fQueue);
 110         return false;
 111     }
 112
 113     void clear() noexcept
 114     {
 115         if (this->fCount == 0)
 116             return;
 117
 118         for (typename AbstractLinkedList<T>::ListHead *entry = this->fQueue.next, *entry2 = entry->next;
 119              entry != &this->fQueue; entry = entry2, entry2 = entry->next)
 120         {
 121             typename AbstractLinkedList<T>::Data* const data = list_entry(entry, typename AbstractLinkedList<T>::Data, siblings);
 122             CARLA_SAFE_ASSERT_CONTINUE(data != nullptr);
 123
 124             this->_deallocate(data);
 125         }
 126
 127         this->_init();
 128     }
 129
 130     T getFirst(T& fallback, const bool removeObj) noexcept
 131     {
 132         CARLA_SAFE_ASSERT_RETURN(this->fCount > 0, fallback);
 133
 134         typename AbstractLinkedList<T>::ListHead* const entry = this->fQueue.next;
 135
 136         typename AbstractLinkedList<T>::Data* const data = list_entry(entry, typename AbstractLinkedList<T>::Data, siblings);
 137         CARLA_SAFE_ASSERT_RETURN(data != nullptr, fallback);
 138
 139         if (! removeObj)
 140             return data->value;
 141
 142         const T value(data->value);
 143
 144         _deleteRT(entry, data);
 145
 146         return value;
 147     }
 148
 149     void _deleteRT(typename AbstractLinkedList<T>::ListHead* const entry, typename AbstractLinkedList<T>::Data* const data) noexcept
 150     {
 151         CARLA_SAFE_ASSERT_RETURN(entry       != nullptr,);
 152         CARLA_SAFE_ASSERT_RETURN(entry->prev != nullptr,);
 153         CARLA_SAFE_ASSERT_RETURN(entry->next != nullptr,);
 154
 155         --this->fCount;
 156
 157         entry->next->prev = entry->prev;
 158         entry->prev->next = entry->next;
 159
 160         entry->next = nullptr;
 161         entry->prev = nullptr;
 162
 163         _deallocate(data);
 164     }
 165 #endif
 166
 167     bool append_sleepy(const T& value) noexcept
 168     {
 169         return _add_sleepy(value, true);
 170     }
 171
 172     bool insert_sleepy(const T& value) noexcept
 173     {
 174         return _add_sleepy(value, false);
 175     }
 176
 177     bool moveTo(AbstractLinkedList<T>& list, const bool inTail) noexcept override
 178     {
 179         CARLA_SAFE_ASSERT_RETURN(((RtLinkedList&)list).fMemPool == fMemPool, false);
 180
 181         return AbstractLinkedList<T>::moveTo(list, inTail);
 182     }
 183
 184 protected:
 185     typename AbstractLinkedList<T>::Data* _allocate() noexcept override
 186     {
 187         return (typename AbstractLinkedList<T>::Data*)fMemPool.allocate_atomic();
 188     }
 189
 190     typename AbstractLinkedList<T>::Data* _allocate_sleepy() noexcept
 191     {
 192         return (typename AbstractLinkedList<T>::Data*)fMemPool.allocate_sleepy();
 193     }
 194
 195     void _deallocate(typename AbstractLinkedList<T>::Data* const dataPtr) noexcept override
 196     {
 197         fMemPool.deallocate(dataPtr);
 198     }
 199
 200 private:
 201     Pool& fMemPool;
 202
 203     bool _add_sleepy(const T& value, const bool inTail) noexcept
 204     {
 205         if (typename AbstractLinkedList<T>::Data* const data = _allocate_sleepy())
 206             return this->_add_internal(data, value, inTail, &this->fQueue);
 207         return false;
 208     }
 209
 210     CARLA_PREVENT_VIRTUAL_HEAP_ALLOCATION
 211     CARLA_DECLARE_NON_COPYABLE(RtLinkedList)
 212 };
 213
 214 // -----------------------------------------------------------------------
 215
 216 #endif // RT_LINKED_LIST_HPP_INCLUDED