#if !defined( _IOADATALOCK_H )
#define _IOADATALOCK_H

// Asynchronous data access: how to control access to data structures shared between a high priority
// writing process and one or more reading processes.

// (1) If there is one single copy of the data, the one way to ensure coherent access to the data is to use
//     some sort of mutually-exclusive locking mechanism (mutex or critical section object) which allows only
//     one process at-a-time to access the data. The problem with this approach is that if a low priority
//     process has gained control of the lock, any attempt by a higher priority process to accesss the data
//     will be blocked until the lock is released (priority inversion). This can seriously compromise the
//     operation of any real-time writing process. If there are other synchronisation constraints between
//     processes, there is also the possibility of deadlock. Another solution is for a reader to check some form
//     of flag or checksum to see if it was interrupted by the writing process, and if so, the reader restarts the
//     process until it has obtained an intact copy of the data. This approach will not work if there are no
//     sufficiently long gaps between writer accesses to the data. Also, if the reader is interrupted too often,
//     it will waste a lot of CPU time.

// (2) A double-buffered approach improves things by allowing simultaneous reading and writing of data. But it still
//     does not guarantee coherent access to data structures for the reading process as long as the writing process
//     takes priority (i.e. where the writing process has the ability to pre-empt or interrupt the reading process).

// (3) It has been known for some time that at least 3 buffers are required to support simultaneous, non-blocking
//     access to shared data (more generally, n + 2 buffers are required to support 1 writer and n readers).
//     See Peterson G., Concurrent reading while writing, ACM Transations on Programming Languages and Systems, 5, 1,
//     January 1983, pages 46-55.

// (4) Simpson points out a possible flaw in the three-slot solution: a race condition between reader and writer.
//     See Simpson H.R., Four-slot fully asynchronous communication mechanism, IEE Proceedings, Volume 137, Pt. E,
//     No. 1, January 1990, pages 17-30.

// (5) Chen & Burns have shown that it is possible to implement the three-slot approach without the race condition.
//     See Chen J. & Burns A., A three-slot asynchronous reader/writer mechanism for multiprocessor real-time systems,
//     Technical report YCS-186, University of York, January 1997, for a correct three-slot solution (1 writer/1 reader)
//     and Chen J. & Burns A., A fully asynchronous reader/writer mechanism for multiprocessor real-time systems,
//     Technical report YCS-288, University of York, May 1997 for the multi-slot solution (1 writer/n readers).
//     In both cases the race condition is avoided by making use of specialised atomic read-write operations.

// The multi-slot solution allows the high-priority writing process to save up-to-date copies of a data structure while
// any number of lower priority processes are reading separate but less recent copies of the same data structure. The
// writer writes each copy once only. Each reader can retain access to its copy of the data for as long as it requires
// coherent access to the data structure.

// The requirements for implementing the multi-slot solution are:

// (1) Shared memory: in Windows, all memory belonging to a given process or executable is accesible from all threads
//     belonging to that same process. Sharing memory between separate processes is possible via the file mapping
//     mechanism, but is not implemented here.

// (2) Cache coherency: what Chen & Burns refer to as the "sequential consistency principle" for processor-to-memory
//     communication, i.e. all threads/processes are provided with a consistent view of shared memory such that no
//     thread could have access to an out-of-date value stored in memory once that memory location has been updated.
//     This situation could arise if cached memory values get out of sync. All Intel processors (including the Core i7)
//     are equipped with specialised logic to maintain cache coherency. It is also necessary for all variables and
//     pointers associated with shared memory to be declared "volatile". This will prevent the compiler/optimiser
//     caching any shared memory values in registers, i.e. all variable and pointer accesses are forced to refer back
//     to the associated memory location at all times.

// (3) Atomic read-write operations: provides the necessary mechanism to synchronise access to the critical shared
//     memory locations, avoiding the race condition that could cause the scheme to fail. Windows provides the function
//     InterlockedCompareExchange( ) for this purpose. The function returns the value stored at a given memory location
//     and only replaces the old value with a new value if the old value is equal to another specified value. By calling
//     this function it is possible for asynchronous reader and writer threads to cooperate in the process of updating
//     the memory location which would otherwise have resulted in the troublesome race condition.

class IoADataLock
{
public:
    IoADataLock( int ReaderCount = 1 )
    {
        const int MaxReaderCount = sizeof( m_ReadBufferIndex ) / sizeof( m_ReadBufferIndex[ 0 ] );

        if ( ReaderCount <              1 ) ReaderCount =              1;
        if ( ReaderCount > MaxReaderCount ) ReaderCount = MaxReaderCount;

        m_ReaderCount = ReaderCount;

        for ( int ReaderIndex = 0; ReaderIndex < ReaderCount; ReaderIndex++ )
        {
            m_ReadBufferIndex[ ReaderIndex ] = 0;
        }

        m_WriteBufferIndex  = 0;
        m_LatestBufferIndex = 0;
    }

    int ReaderCount( ) const { return m_ReaderCount; }
    int BufferCount( ) const { return m_ReaderCount + 2; }

    int ReadBufferIndex( int ReaderIndex = 0 )
    {
        if ( ReaderIndex < 0 || ReaderIndex >= m_ReaderCount ) return -1;  // bad reader index

        m_ReadBufferIndex[ ReaderIndex ] = 0;  // mark reader's buffer as available

        // Update reader's buffer index (use of interlocked function call prevents possible race condition)
#ifdef WindowsXP  // pre Windows Vista
        ::InterlockedCompareExchange( (PVOID *) &m_ReadBufferIndex[ ReaderIndex ], (PVOID) m_LatestBufferIndex, 0 );
#else
        ::InterlockedCompareExchange( &m_ReadBufferIndex[ ReaderIndex ], m_LatestBufferIndex, 0 );
#endif

        return (int) m_ReadBufferIndex[ ReaderIndex ] - 1;  // return zero-based buffer index
    }

private:
    // Functions to support operation of IoAWriteLock class
    friend class IoAWriteLock;

    void AcquireWriteLock( )
    {
        if ( ! WriteLockIsAcquired( ) )  // do not lock the write buffer more than once
        {
            unsigned __int32 BufferMask = 0x00000000;  // 1 bit per buffer

            // Flag read buffers
            for ( int ReaderIndex = 0; ReaderIndex < ReaderCount( ); ReaderIndex++ )
            {
                __int32 ReadBufferIndex = m_ReadBufferIndex[ ReaderIndex ];

                if ( ReadBufferIndex ) BufferMask |= 0x00000001 << ( ReadBufferIndex - 1 );
            }

            // Flag write buffer
            __int32 WriteBufferIndex = m_LatestBufferIndex;

            if ( WriteBufferIndex ) BufferMask |= 0x00000001 << ( WriteBufferIndex - 1 );

            // Search for available (unflagged) buffer (there must be at least 1)
            for ( int BufferIndex = 0; BufferIndex < BufferCount( ); BufferIndex++, BufferMask >>= 1 )
            {
                if ( BufferMask & 0x00000001 ) continue;  // buffer is flagged, keep looking

                m_WriteBufferIndex = (__int32) BufferIndex + 1; break;  // buffer is available for writing
            }
        }
    }

    void ReleaseWriteLock( )
    {
        if ( WriteLockIsAcquired( ) )
        {
            __int32 BufferIndex = m_WriteBufferIndex;

            m_LatestBufferIndex = BufferIndex;  // make write buffer available for reading

            // Make sure all readers get to know about it (use of interlocked function call prevents possible race condition)
            for ( int ReaderIndex = 0; ReaderIndex < ReaderCount( ); ReaderIndex++ )
            {
#ifdef WindowsXP  // pre Windows Vista
                ::InterlockedCompareExchange( (PVOID *) &m_ReadBufferIndex[ ReaderIndex ], (PVOID) BufferIndex, 0 );
#else
                ::InterlockedCompareExchange( &m_ReadBufferIndex[ ReaderIndex ], BufferIndex, 0 );
#endif
            }

            m_WriteBufferIndex = 0;
        }
    }

    int WriteLockIsAcquired( ) const { return m_WriteBufferIndex != 0; }

    int WriteBufferIndex( ) const { return m_WriteBufferIndex - 1; }  // return zero-based buffer index

    // Data members
    int m_ReaderCount;  // number of simultaneous readers supported

    volatile unsigned __int32 m_WriteBufferIndex;       // current write buffer (= 0, if none)
    volatile unsigned __int32 m_LatestBufferIndex;      // most up-to-date copy of data (= 0, if none)
    volatile unsigned __int32 m_ReadBufferIndex[ 30 ];  // maximum of 30 simultaneous read buffers
};

// Access to the single write lock is handled through a separate class IoAWriteLock. The IoAWriteLock object
// must be declared inside the scope containing the code which updates the data associated with the lock.
// The lock is then automatically released when the IoAWriteLock object goes out of scope.

class IoAWriteLock
{
public:
    IoAWriteLock( IoADataLock& DataLock ) : m_DataLock( DataLock ) { m_DataLock.AcquireWriteLock( ); }

    ~IoAWriteLock( ) { m_DataLock.ReleaseWriteLock( ); }

    int IsAcquired( ) const { return m_DataLock.WriteLockIsAcquired( ); }

    int BufferIndex( ) const { return m_DataLock.WriteBufferIndex( ); }

private:
    IoADataLock& m_DataLock;
};

#endif