choc_DirtyList.h

//
//    ██████ ██   ██  ██████   ██████
//   ██      ██   ██ ██    ██ ██            ** Classy Header-Only Classes **
//   ██      ███████ ██    ██ ██
//   ██      ██   ██ ██    ██ ██           https://github.com/Tracktion/choc
//    ██████ ██   ██  ██████   ██████
//
//   CHOC is (C)2022 Tracktion Corporation, and is offered under the terms of the ISC license:
//
//   Permission to use, copy, modify, and/or distribute this software for any purpose with or
//   without fee is hereby granted, provided that the above copyright notice and this permission
//   notice appear in all copies. THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
//   WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
//   AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
//   CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
//   WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
//   CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

#ifndef CHOC_DIRTY_LIST_HEADER_INCLUDED
#define CHOC_DIRTY_LIST_HEADER_INCLUDED

#include "choc_SingleReaderMultipleWriterFIFO.h"

namespace choc::fifo
{

//==============================================================================
/**
    A lock-free list of objects where multiple threads may mark an object as dirty,
    while a single thread polls the list and service the dirty ones.

    The main use-case for this class is where a set of objects need to be asynchronously
    serviced by a single thread or timer after they get flagged by a realtime thread.

    The class is designed so that the markAsDirty() and popNextDirtyObject() functions
    will execute in very short, constant time even when the total number of objects is
    very large, and no heap allocations or other system calls are involved. And if only
    one thread ever calls markAsDirty(), it's safe for realtime use.
    To make this possible, the compromises are that it needs to be initialised with a
    complete list of the objects needed, so that it can assign handles to them, and its
    memory requirements include allocating a small amount of storage per object.
*/
template <typename ObjectType>
struct DirtyList
{
    DirtyList() = default;
    ~DirtyList() = default;

    DirtyList (DirtyList&&) = delete;
    DirtyList (const DirtyList&) = delete;

    using Handle = uint32_t;

    /// Prepares the list by giving it the complete set of objects that it will manage.
    /// The return value is the set of handles assigned to each of the objects. The handles
    /// are later needed by the caller in order to call markAsDirty().
    ///
    /// Note that this method is not thread-safe, and must be performed before any other
    /// operations begin. It can be called multiple times to re-initialise the same list
    /// for other objects, as long as thread-safety is observed.
    template <typename Array>
    std::vector<Handle> initialise (const Array& objects);

    /// Clears the queue of pending items and resets the 'dirty' state of all objects.
    void resetAll();

    /// Marks an object as dirty.
    ///
    /// This may be called from any thread, and is lock-free.
    /// If the object is already marked as dirty, this function does nothing. If not, then
    /// the object is marked as dirty and added to the queue of objects which will later
    /// be returned by calls to popNextDirtyObject().
    void markAsDirty (Handle objectHandle);

    /// Returns a pointer to the next dirty object (and in doing so marks that object
    /// as now being 'clean').
    /// If no objects are dirty, this returns nullptr.
    /// This method is lock-free, but is designed to be called by only a single reader
    /// thread.
    ObjectType* popNextDirtyObject();

    /// Returns true if any objects are currently queued for attention.
    bool areAnyObjectsDirty() const;

private:
    //==============================================================================
    std::unique_ptr<std::atomic_flag[]> flags; // avoiding a vector here as atomics aren't copyable
    std::vector<ObjectType*> allObjects;
    choc::fifo::SingleReaderMultipleWriterFIFO<Handle> fifo;
};



//==============================================================================
//        _        _           _  _
//     __| |  ___ | |_   __ _ (_)| | ___
//    / _` | / _ \| __| / _` || || |/ __|
//   | (_| ||  __/| |_ | (_| || || |\__ \ _  _  _
//    \__,_| \___| \__| \__,_||_||_||___/(_)(_)(_)
//
//   Code beyond this point is implementation detail...
//
//==============================================================================

template <typename ObjectType>
template <typename Array>
std::vector<typename DirtyList<ObjectType>::Handle> DirtyList<ObjectType>::initialise (const Array& objects)
{
    std::vector<Handle> handles;
    auto numObjects = static_cast<size_t> (objects.size());
    handles.reserve (numObjects);
    flags.reset (new std::atomic_flag[numObjects]);
    allObjects.resize (numObjects);
    fifo.reset (numObjects);
    size_t i = 0;

    for (auto& o : objects)
    {
        CHOC_ASSERT (o != nullptr);
        flags[i].clear();
        allObjects[i] = o;
        handles.push_back (static_cast<Handle> (i));
        ++i;
    }

    return handles;
}

template <typename ObjectType>
void DirtyList<ObjectType>::resetAll()
{
    for (auto& o : allObjects)
        o.isDirty = false;

    fifo.reset();
}

template <typename ObjectType>
void DirtyList<ObjectType>::markAsDirty (Handle objectHandle)
{
    CHOC_ASSERT (objectHandle < allObjects.size());

    if (! flags[objectHandle].test_and_set())
        fifo.push (objectHandle);
}

template <typename ObjectType>
ObjectType* DirtyList<ObjectType>::popNextDirtyObject()
{
    Handle item;

    if (! fifo.pop (item))
        return nullptr;

    flags[item].clear();
    return allObjects[item];
}

template <typename ObjectType>
bool DirtyList<ObjectType>::areAnyObjectsDirty() const
{
    return fifo.getUsedSlots() != 0;
}


} // choc::fifo

#endif