ReadWriteLock.h

Go to the documentation of this file.

/*  ReadWriteLock.h - N readers, N writers problem with preference
    for readers

    Copyright (C) 2001-2004 Mark Weaver
    Written by Mark Weaver <mark@npsl.co.uk>

    Part of the Open-Win32 library.
    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Library General Public
    License as published by the Free Software Foundation; either
    version 2 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Library General Public License for more details.

    You should have received a copy of the GNU Library General Public
    License along with this library; if not, write to the
    Free Software Foundation, Inc., 59 Temple Place - Suite 330,
    Boston, MA  02111-1307, USA.
*/

#ifndef OW32_ReadWriteLock_h
#define OW32_ReadWriteLock_h

#include <OW32/SyncObjects.h>
#include <cstddef>
#include <assert.h>

namespace OW32
{

class OW32_LIB_EXPORT CReadWriteLock
{
public:
    CReadWriteLock() :
        m_activeReaders(0), 
        m_writerID(0), 
        m_writerRecursionCount(0),
        m_pendingReaders(0), 
        m_pendingWriters(0),
        m_freeToRead(TRUE)
    {
    }

    CSyncObject& GetWriteLock()
    {
        return m_writeLock;
    }

    CSyncObject& GetReadLock()
    {
        return m_readLock;
    }

private:
    BOOL readLock(DWORD timeout)
    {
        DWORD dwStart = GetTickCount();
        DWORD pendIncrement = 1;
        DWORD myID = ::GetCurrentThreadId();
        for (;;)
        {
            bool needReset = false;

            { // Lock scope
                CSingleLock lock(m_stateLock);

                // Too many pending or active? (caps too early, but not really relevant...)
                if (m_pendingReaders == 0xffffffff || m_activeReaders == 0xffffffff)
                {
                    ::SetLastError(ERROR_BUSY);
                    return FALSE;
                }

                // Am I a writer? If so, just recurse the write lock.
                // (Note that there is no upgrade so you can't be a reader already:
                // upgrade would require a container of thread IDs).
                if (m_writerRecursionCount > 0 && m_writerID == myID)
                {
                    ++m_writerRecursionCount;
                    return TRUE;
                }

                m_pendingReaders += pendIncrement;
                pendIncrement = 0;
                // Not write locked, and no waiting writers
                if (m_writerRecursionCount == 0 && m_pendingWriters == 0)
                {
                    //OWTRACE(_T("%lu: got read lock\n"), ::GetCurrentThreadId());
                    ++m_activeReaders;

                    // Seems odd, but we can only reset this event when no-one is
                    // waiting on it (otherwise the lost signal would be a disaster)
                    // or we know that we will generate the signal
                    // When there are no pending readers then no-one is waiting below
                    // We also optimise by only resetting if anyone actually waited
                    // on the event
                    if (--m_pendingReaders == 0 && needReset)
                    {
                        m_freeToRead.Reset();
                    }
                    return TRUE;
                }
            }

            // wait for `write complete' signal
            DWORD timeoutRemaining = INFINITE;
            if (timeout != INFINITE)
            {   
                timeoutRemaining = GetTickCount() - dwStart;
                if (timeoutRemaining > timeout)
                    timeoutRemaining = 0;
#if 0
                printf("sleep for %lu\n", timeoutRemaining);
#endif
            }
            if (!m_freeToRead.Lock(timeoutRemaining))
                break;
            needReset = true;
        }
        // Timed out, remove us from pending readers
        if (pendIncrement == 0)
        {
            CSingleLock lock(m_stateLock);

            // Reset the event as above.  We waited on it, so no need for
            // the conditional check.
            if (--m_pendingReaders == 0)
            {
                m_freeToRead.Reset();
            }
        }
        ::SetLastError(ERROR_TIMEOUT);
        return FALSE;
    }

    void readUnlock()
    {
        CSingleLock lock(m_stateLock);

        // Am I really a writer?
        if (m_writerRecursionCount > 0)
        {
            writeUnlockLocked();
            return;
        }

        // Can't have any writers, must have a reader
        assert(m_writerRecursionCount == 0);
        assert(m_activeReaders > 0);
        // Ditch one reader
        --m_activeReaders;
        if (m_activeReaders == 0 && m_pendingWriters > 0) 
        {
            // Release one waiting writer
            m_freeToWrite.Set();
        }
        //OWTRACE(_T("%lu: readUnlock\n"), ::GetCurrentThreadId());
    }

    class OW32_LIB_EXPORT CReadLock : public CSyncObject
    {
    private:
        CReadLock(const CReadLock&);
        CReadLock& operator=(const CReadLock&);

    public:
        CReadLock()
        {
        }

        virtual BOOL Lock(DWORD timeout)
        {
            CReadWriteLock& parent = *(CReadWriteLock *)((const char *)this-offsetof(CReadWriteLock, m_readLock));
            return parent.readLock(timeout);
        }

        virtual void Unlock()
        {
            CReadWriteLock& parent = *(CReadWriteLock *)((const char *)this-offsetof(CReadWriteLock, m_readLock));
            parent.readUnlock();
        }
    };
    friend CReadLock;

    BOOL writeLock(DWORD timeout)
    {
        DWORD dwStart = GetTickCount();
        DWORD pendIncrement = 1;
        DWORD myID = GetCurrentThreadId();
        for (;;)
        {
            { // Lock scope
                CSingleLock lock(m_stateLock);

                // Too many pending (caps too early, maybe, but not really relevant...)
                if (m_pendingWriters == 0xffffffff)
                {
                    ::SetLastError(ERROR_BUSY);
                    return FALSE;
                }

                m_pendingWriters += pendIncrement;
                pendIncrement = 0;

                // No readers?
                if (m_activeReaders == 0)
                {
                    // No active writers or me again
                    if (m_writerRecursionCount == 0 || m_writerID == myID)
                    {
                        // Grab the lock
                        --m_pendingWriters;
                        m_writerID = myID;
                        ++m_writerRecursionCount;

                        // Since we now have the lock, reset the 'freeToRead' event
                        // if there are pending readers.  Might be unnecessary, but
                        // it might be that it got set last time around and couldn't
                        // be unset by the repeated arrival of new readers.  Here
                        // we know if anyone pends we will set the event, so it's ok
                        // to clear it here.
                        if (m_pendingReaders > 0)
                            m_freeToRead.Reset();
                        return TRUE;
                    }
                    // Otherwise, have an active writer
                }
            }

            // Wait for `write complete' signal
            DWORD timeoutRemaining = INFINITE;
            if (timeout != INFINITE)
            {   
                timeoutRemaining = GetTickCount() - dwStart;
                if (timeoutRemaining > timeout)
                    timeoutRemaining = 0;
            }
            // Wait until OK to write (=> no active readers or writers)
            if (!m_freeToWrite.Lock(timeoutRemaining))
                break;
        }
        // Timeout
        //OWTRACE(_T("%lu: writeLock timeout\n"), ::GetCurrentThreadId());
        if (pendIncrement == 0) 
        {
            CSingleLock lock(m_stateLock);
            if (--m_pendingWriters == 0 && m_pendingReaders > 0)
            {
                // Release a possibly blocked pending reader
                m_freeToRead.Set();
            }
        }
        ::SetLastError(ERROR_TIMEOUT);
        return FALSE;
    }

    void writeUnlock()
    {
        CSingleLock lock(m_stateLock);
        
        writeUnlockLocked();
        //OWTRACE(_T("%lu: writeUnlock\n"), ::GetCurrentThreadId());
    }

    void writeUnlockLocked()
    {
        // Check state
        assert(m_writerID == GetCurrentThreadId());
        assert(m_writerRecursionCount > 0);
        assert(m_activeReaders == 0);

        // Recurse out
        if (--m_writerRecursionCount == 0)
        {
            // Signal write completion with writer preference
            if (m_pendingWriters != 0)
            {
                //OWTRACE(_T("%lu: writeUnlock, release writer\n"), ::GetCurrentThreadId());
                m_freeToWrite.Set();
            }
            else if (m_pendingReaders != 0)
            {
                //OWTRACE(_T("%lu: writeUnlock, release reader\n"), ::GetCurrentThreadId());
                m_freeToRead.Set();
            }
        }
    }

    class OW32_LIB_EXPORT CWriteLock : public CSyncObject
    {
    private:
        CWriteLock(const CWriteLock&);
        CWriteLock& operator=(const CWriteLock&);

    public:
        CWriteLock()
        {
        }

        virtual BOOL Lock(DWORD timeout)
        {
            CReadWriteLock& parent = *(CReadWriteLock *)((const char *)this-offsetof(CReadWriteLock, m_writeLock));
            return parent.writeLock(timeout);
        }

        virtual void Unlock()
        {
            CReadWriteLock& parent = *(CReadWriteLock *)((const char *)this-offsetof(CReadWriteLock, m_writeLock));
            parent.writeUnlock();
        }
    };
    friend CWriteLock;

    CReadWriteLock(const CReadWriteLock&);
    CReadWriteLock& operator=(const CReadWriteLock&);

    CCriticalSection    m_stateLock;
    DWORD               m_pendingReaders;
    DWORD               m_activeReaders;
    DWORD               m_pendingWriters;
    DWORD               m_writerID;
    DWORD               m_writerRecursionCount;
    CEvent              m_freeToWrite;
    CEvent              m_freeToRead;

    CReadLock           m_readLock;
    CWriteLock          m_writeLock;
};

#ifdef _MSC_VER
#pragma warning(default: 4251)
#endif

} // namespace OW32

#endif // OW32_ReadWriteLock_h

---