source/utils/LinkedList.hpp

   1 /*
   2  * High-level, 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 LINKED_LIST_HPP_INCLUDED
  19 #define LINKED_LIST_HPP_INCLUDED
  20
  21 #include "CarlaUtils.hpp"
  22
  23 // -----------------------------------------------------------------------
  24 // Define list_entry and list_entry_const
  25
  26 #ifndef offsetof
  27 # define offsetof(TYPE, MEMBER) ((std::size_t) &((TYPE*)nullptr)->MEMBER)
  28 #endif
  29
  30 #if (defined(__GNUC__) || defined(__clang__)) && ! defined(__STRICT_ANSI__)
  31 # define list_entry(ptr, type, member) ({                     \
  32     typeof( ((type*)nullptr)->member ) *__mptr = (ptr);       \
  33     (type*)( (char*)__mptr - offsetof(type, member) );})
  34 # define list_entry_const(ptr, type, member) ({               \
  35     const typeof( ((type*)nullptr)->member ) *__mptr = (ptr); \
  36     (const type*)( (const char*)__mptr - offsetof(type, member) );})
  37 #else
  38 # define list_entry(ptr, type, member)       \
  39     ((type*)((char*)(ptr)-offsetof(type, member)))
  40 # define list_entry_const(ptr, type, member) \
  41     ((const type*)((const char*)(ptr)-offsetof(type, member)))
  42 #endif
  43
  44 // -----------------------------------------------------------------------
  45 // Abstract Linked List class
  46 // _allocate() and _deallocate are virtual calls provided by subclasses
  47
  48 // NOTE: this class is meant for non-polymorphic data types only!
  49
  50 template<typename T>
  51 class AbstractLinkedList
  52 {
  53 protected:
  54     struct ListHead {
  55         ListHead* next;
  56         ListHead* prev;
  57     };
  58
  59     struct Data {
  60         T value;
  61         ListHead siblings;
  62     };
  63
  64     AbstractLinkedList() noexcept
  65         : kDataSize(sizeof(Data)),
  66 #ifdef CARLA_PROPER_CPP11_SUPPORT
  67           fQueue({&fQueue, &fQueue}),
  68 #endif
  69           fCount(0)
  70     {
  71 #ifndef CARLA_PROPER_CPP11_SUPPORT
  72         fQueue.next = &fQueue;
  73         fQueue.prev = &fQueue;
  74 #endif
  75     }
  76
  77 public:
  78     virtual ~AbstractLinkedList() noexcept
  79     {
  80         CARLA_SAFE_ASSERT(fCount == 0);
  81     }
  82
  83     class Itenerator {
  84     public:
  85         Itenerator(const ListHead& queue) noexcept
  86             : fEntry(queue.next),
  87               fEntry2(fEntry->next),
  88               kQueue(queue)
  89         {
  90             CARLA_SAFE_ASSERT(fEntry != nullptr);
  91             CARLA_SAFE_ASSERT(fEntry2 != nullptr);
  92         }
  93
  94         bool valid() const noexcept
  95         {
  96             return (fEntry != nullptr && fEntry != &kQueue);
  97         }
  98
  99         void next() noexcept
 100         {
 101             fEntry  = fEntry2;
 102             fEntry2 = (fEntry != nullptr) ? fEntry->next : nullptr;
 103         }
 104
 105         T& getValue(T& fallback) const noexcept
 106         {
 107             Data* const data(list_entry(fEntry, Data, siblings));
 108             CARLA_SAFE_ASSERT_RETURN(data != nullptr, fallback);
 109
 110             return data->value;
 111         }
 112
 113         const T& getValue(const T& fallback) const noexcept
 114         {
 115             const Data* const data(list_entry_const(fEntry, Data, siblings));
 116             CARLA_SAFE_ASSERT_RETURN(data != nullptr, fallback);
 117
 118             return data->value;
 119         }
 120
 121         void setValue(const T& value) noexcept
 122         {
 123             Data* const data(list_entry(fEntry, Data, siblings));
 124             CARLA_SAFE_ASSERT_RETURN(data != nullptr,);
 125
 126             data->value = value;
 127         }
 128
 129     private:
 130         ListHead* fEntry;
 131         ListHead* fEntry2;
 132         const ListHead& kQueue;
 133
 134         friend class AbstractLinkedList;
 135     };
 136
 137     class AutoItenerator {
 138     public:
 139         AutoItenerator(const ListHead* entry) noexcept
 140             : fEntry(entry),
 141               fEntry2(entry != nullptr ? entry->next : nullptr)
 142         {
 143             CARLA_SAFE_ASSERT(fEntry != nullptr);
 144             CARLA_SAFE_ASSERT(fEntry2 != nullptr);
 145         }
 146
 147         bool operator!=(AutoItenerator& it) const noexcept
 148         {
 149             CARLA_SAFE_ASSERT_RETURN(fEntry != nullptr, false);
 150             CARLA_SAFE_ASSERT_RETURN(it.fEntry != nullptr, false);
 151
 152             return fEntry != it.fEntry;
 153         }
 154
 155         AutoItenerator& operator++() noexcept
 156         {
 157             fEntry  = fEntry2;
 158             fEntry2 = (fEntry != nullptr) ? fEntry->next : nullptr;
 159             return *this;
 160         }
 161
 162 #if 0
 163         T& operator*() noexcept
 164         {
 165             static T& fallback(_getFallback());
 166
 167             Data* const data(list_entry(fEntry, Data, siblings));
 168             CARLA_SAFE_ASSERT_RETURN(data != nullptr, fallback);
 169
 170             return data->value;
 171         }
 172 #endif
 173
 174         const T& operator*() const noexcept
 175         {
 176             static const T& fallback(_getFallback());
 177
 178             const Data* const data(list_entry_const(fEntry, Data, siblings));
 179             CARLA_SAFE_ASSERT_RETURN(data != nullptr, fallback);
 180
 181             return data->value;
 182         }
 183
 184     private:
 185         const ListHead* fEntry;
 186         const ListHead* fEntry2;
 187
 188         static T& _getFallback()
 189         {
 190             static T data;
 191             carla_zeroStruct(data);
 192             return data;
 193         }
 194     };
 195
 196     Itenerator begin2() const noexcept
 197     {
 198         return Itenerator(fQueue);
 199     }
 200
 201     AutoItenerator begin() const noexcept
 202     {
 203         return AutoItenerator(fQueue.next);
 204     }
 205
 206     AutoItenerator end() const noexcept
 207     {
 208         return AutoItenerator(&fQueue);
 209     }
 210
 211     void clear() noexcept
 212     {
 213         if (fCount == 0)
 214             return;
 215
 216         for (ListHead *entry = fQueue.next, *entry2 = entry->next; entry != &fQueue; entry = entry2, entry2 = entry->next)
 217         {
 218             Data* const data(list_entry(entry, Data, siblings));
 219             CARLA_SAFE_ASSERT_CONTINUE(data != nullptr);
 220
 221             _deallocate(data);
 222         }
 223
 224         _init();
 225     }
 226
 227     inline std::size_t count() const noexcept
 228     {
 229         return fCount;
 230     }
 231
 232     inline bool isEmpty() const noexcept
 233     {
 234         return fCount == 0;
 235     }
 236
 237     inline bool isNotEmpty() const noexcept
 238     {
 239         return fCount != 0;
 240     }
 241
 242     bool append(const T& value) noexcept
 243     {
 244         return _add(value, true, &fQueue);
 245     }
 246
 247     bool appendAt(const T& value, const Itenerator& it) noexcept
 248     {
 249         return _add(value, true, it.fEntry->next);
 250     }
 251
 252     bool insert(const T& value) noexcept
 253     {
 254         return _add(value, false, &fQueue);
 255     }
 256
 257     bool insertAt(const T& value, const Itenerator& it) noexcept
 258     {
 259         return _add(value, false, it.fEntry->prev);
 260     }
 261
 262     // NOTE: do not use this function unless strictly needed. it can be very expensive if the list is big
 263     const T& getAt(const std::size_t index, const T& fallback) const noexcept
 264     {
 265         CARLA_SAFE_ASSERT_UINT2_RETURN(fCount > 0 && index < fCount, index, fCount, fallback);
 266
 267         std::size_t i = 0;
 268         ListHead* entry = fQueue.next;
 269
 270         for (; i++ != index; entry = entry->next) {}
 271
 272         return _get(entry, fallback);
 273     }
 274
 275     T getFirst(T& fallback, const bool removeObj) noexcept
 276     {
 277         CARLA_SAFE_ASSERT_RETURN(fCount > 0, fallback);
 278
 279         return _get(fQueue.next, fallback, removeObj);
 280     }
 281
 282     T& getFirst(T& fallback) const noexcept
 283     {
 284         CARLA_SAFE_ASSERT_RETURN(fCount > 0, fallback);
 285
 286         return _get(fQueue.next, fallback);
 287     }
 288
 289     const T& getFirst(const T& fallback) const noexcept
 290     {
 291         CARLA_SAFE_ASSERT_RETURN(fCount > 0, fallback);
 292
 293         return _get(fQueue.next, fallback);
 294     }
 295
 296     T getLast(T& fallback, const bool removeObj) noexcept
 297     {
 298         CARLA_SAFE_ASSERT_RETURN(fCount > 0, fallback);
 299
 300         return _get(fQueue.prev, fallback, removeObj);
 301     }
 302
 303     T& getLast(T& fallback) const noexcept
 304     {
 305         CARLA_SAFE_ASSERT_RETURN(fCount > 0, fallback);
 306
 307         return _get(fQueue.prev, fallback);
 308     }
 309
 310     const T& getLast(const T& fallback) const noexcept
 311     {
 312         CARLA_SAFE_ASSERT_RETURN(fCount > 0, fallback);
 313
 314         return _get(fQueue.prev, fallback);
 315     }
 316
 317     void remove(Itenerator& it) noexcept
 318     {
 319         CARLA_SAFE_ASSERT_RETURN(it.fEntry != nullptr,);
 320
 321         Data* const data(list_entry(it.fEntry, Data, siblings));
 322         CARLA_SAFE_ASSERT_RETURN(data != nullptr,);
 323
 324         _delete(it.fEntry, data);
 325     }
 326
 327     bool removeOne(const T& value) noexcept
 328     {
 329         for (ListHead *entry = fQueue.next, *entry2 = entry->next; entry != &fQueue; entry = entry2, entry2 = entry->next)
 330         {
 331             Data* const data = list_entry(entry, Data, siblings);
 332             CARLA_SAFE_ASSERT_CONTINUE(data != nullptr);
 333
 334             if (data->value != value)
 335                 continue;
 336
 337             _delete(entry, data);
 338
 339             return true;
 340         }
 341
 342         return false;
 343     }
 344
 345     void removeAll(const T& value) noexcept
 346     {
 347         for (ListHead *entry = fQueue.next, *entry2 = entry->next; entry != &fQueue; entry = entry2, entry2 = entry->next)
 348         {
 349             Data* const data = list_entry(entry, Data, siblings);
 350             CARLA_SAFE_ASSERT_CONTINUE(data != nullptr);
 351
 352             if (data->value != value)
 353                 continue;
 354
 355             _delete(entry, data);
 356         }
 357     }
 358
 359     // move data to a new list, and clear ourselves
 360     virtual bool moveTo(AbstractLinkedList<T>& list, const bool inTail = true) noexcept
 361     {
 362         CARLA_SAFE_ASSERT_RETURN(fCount > 0, false);
 363
 364         if (inTail)
 365             __list_splice_tail(&fQueue, &list.fQueue);
 366         else
 367             __list_splice(&fQueue, &list.fQueue);
 368
 369         //! @a list gets our items
 370         list.fCount += fCount;
 371
 372         //! and we get nothing
 373         _init();
 374
 375         return true;
 376     }
 377
 378 protected:
 379     const std::size_t kDataSize;
 380
 381     ListHead    fQueue;
 382     std::size_t fCount;
 383
 384     virtual Data* _allocate() noexcept = 0;
 385     virtual void  _deallocate(Data* const dataPtr) noexcept = 0;
 386
 387 private:
 388     void _init() noexcept
 389     {
 390         fCount = 0;
 391         fQueue.next = &fQueue;
 392         fQueue.prev = &fQueue;
 393     }
 394
 395     bool _add(const T& value, const bool inTail, ListHead* const queue) noexcept
 396     {
 397         if (Data* const data = _allocate())
 398             return _add_internal(data, value, inTail, queue);
 399         return false;
 400     }
 401
 402     bool _add_internal(Data* const data, const T& value, const bool inTail, ListHead* const queue) noexcept
 403     {
 404         CARLA_SAFE_ASSERT_RETURN(data        != nullptr, false);
 405         CARLA_SAFE_ASSERT_RETURN(queue       != nullptr, false);
 406         CARLA_SAFE_ASSERT_RETURN(queue->prev != nullptr, false);
 407         CARLA_SAFE_ASSERT_RETURN(queue->next != nullptr, false);
 408
 409         data->value = value;
 410
 411         ListHead* const siblings(&data->siblings);
 412
 413         if (inTail)
 414         {
 415             siblings->prev = queue->prev;
 416             siblings->next = queue;
 417
 418             queue->prev->next = siblings;
 419             queue->prev       = siblings;
 420         }
 421         else
 422         {
 423             siblings->prev = queue;
 424             siblings->next = queue->next;
 425
 426             queue->next->prev = siblings;
 427             queue->next       = siblings;
 428         }
 429
 430         ++fCount;
 431         return true;
 432     }
 433
 434     void _delete(ListHead* const entry, Data* const data) noexcept
 435     {
 436         CARLA_SAFE_ASSERT_RETURN(entry       != nullptr,);
 437         CARLA_SAFE_ASSERT_RETURN(entry->prev != nullptr,);
 438         CARLA_SAFE_ASSERT_RETURN(entry->next != nullptr,);
 439
 440         --fCount;
 441
 442         entry->next->prev = entry->prev;
 443         entry->prev->next = entry->next;
 444
 445         entry->next = nullptr;
 446         entry->prev = nullptr;
 447
 448         _deallocate(data);
 449     }
 450
 451     T _get(ListHead* const entry, T& fallback, const bool removeObj) noexcept
 452     {
 453         Data* const data(list_entry(entry, Data, siblings));
 454         CARLA_SAFE_ASSERT_RETURN(data != nullptr, fallback);
 455
 456         if (! removeObj)
 457             return data->value;
 458
 459         const T value(data->value);
 460
 461         _delete(entry, data);
 462
 463         return value;
 464     }
 465
 466     T& _get(ListHead* const entry, T& fallback) const noexcept
 467     {
 468         Data* const data(list_entry(entry, Data, siblings));
 469         CARLA_SAFE_ASSERT_RETURN(data != nullptr, fallback);
 470
 471         return data->value;
 472     }
 473
 474     const T& _get(const ListHead* const entry, const T& fallback) const noexcept
 475     {
 476         const Data* const data(list_entry_const(entry, Data, siblings));
 477         CARLA_SAFE_ASSERT_RETURN(data != nullptr, fallback);
 478
 479         return data->value;
 480     }
 481
 482     static void __list_splice(ListHead* const list, ListHead* const head) noexcept
 483     {
 484         ListHead* const first = list->next;
 485         ListHead* const last = list->prev;
 486         ListHead* const at = head->next;
 487
 488         first->prev = head;
 489         head->next  = first;
 490
 491         last->next = at;
 492         at->prev   = last;
 493     }
 494
 495     static void __list_splice_tail(ListHead* const list, ListHead* const head) noexcept
 496     {
 497         ListHead* const first = list->next;
 498         ListHead* const last = list->prev;
 499         ListHead* const at = head->prev;
 500
 501         first->prev = at;
 502         at->next    = first;
 503
 504         last->next = head;
 505         head->prev = last;
 506     }
 507
 508     template<typename> friend class RtLinkedList;
 509
 510     CARLA_PREVENT_VIRTUAL_HEAP_ALLOCATION
 511     CARLA_DECLARE_NON_COPYABLE(AbstractLinkedList)
 512 };
 513
 514 // -----------------------------------------------------------------------
 515 // LinkedList
 516
 517 template<typename T>
 518 class LinkedList : public AbstractLinkedList<T>
 519 {
 520 public:
 521     LinkedList() noexcept {}
 522
 523 protected:
 524     typename AbstractLinkedList<T>::Data* _allocate() noexcept override
 525     {
 526         return (typename AbstractLinkedList<T>::Data*)std::malloc(this->kDataSize);
 527     }
 528
 529     void _deallocate(typename AbstractLinkedList<T>::Data* const dataPtr) noexcept override
 530     {
 531         std::free(dataPtr);
 532     }
 533
 534     CARLA_PREVENT_VIRTUAL_HEAP_ALLOCATION
 535     CARLA_DECLARE_NON_COPYABLE(LinkedList)
 536 };
 537
 538 // -----------------------------------------------------------------------
 539
 540 #endif // LINKED_LIST_HPP_INCLUDED