/*
 * Copyright 2006, Haiku.
 * Distributed under the terms of the MIT License.
 *
 * Authors:
 *		IngoWeinhold <bonefish@cs.tu-berlin.de>
 */

#include "RWLocker.h"

#include <String.h>

// info about a read lock owner
struct RWLocker::ReadLockInfo {
	thread_id	reader;
	int32		count;
};


// constructor
RWLocker::RWLocker()
	: fLock(),
	  fMutex(),
	  fQueue(),
	  fReaderCount(0),
	  fWriterCount(0),
	  fReadLockInfos(8),
	  fWriter(B_ERROR),
	  fWriterWriterCount(0),
	  fWriterReaderCount(0)
{
	_Init(NULL);
}

// constructor
RWLocker::RWLocker(const char* name)
	: fLock(name),
	  fMutex(),
	  fQueue(),
	  fReaderCount(0),
	  fWriterCount(0),
	  fReadLockInfos(8),
	  fWriter(B_ERROR),
	  fWriterWriterCount(0),
	  fWriterReaderCount(0)
{
	_Init(name);
}

// destructor
RWLocker::~RWLocker()
{
	fLock.Lock();
	delete_sem(fMutex.semaphore);
	delete_sem(fQueue.semaphore);
	for (int32 i = 0; ReadLockInfo* info = _ReadLockInfoAt(i); i++)
		delete info;
}

// ReadLock
bool
RWLocker::ReadLock()
{
	status_t error = _ReadLock(B_INFINITE_TIMEOUT);
	return (error == B_OK);
}

// ReadLockWithTimeout
status_t
RWLocker::ReadLockWithTimeout(bigtime_t timeout)
{
	bigtime_t absoluteTimeout = system_time() + timeout;
	// take care of overflow
	if (timeout > 0 && absoluteTimeout < 0)
		absoluteTimeout = B_INFINITE_TIMEOUT;
	return _ReadLock(absoluteTimeout);
}

// ReadUnlock
void
RWLocker::ReadUnlock()
{
	if (fLock.Lock()) {
		thread_id thread = find_thread(NULL);
		if (thread == fWriter) {
			// We (also) have a write lock.
			if (fWriterReaderCount > 0)
				fWriterReaderCount--;
			// else: error: unmatched ReadUnlock()
		} else {
			int32 index = _IndexOf(thread);
			if (ReadLockInfo* info = _ReadLockInfoAt(index)) {
				fReaderCount--;
				if (--info->count == 0) {
					// The outer read lock bracket for the thread has been
					// reached. Dispose the info.
					_DeleteReadLockInfo(index);
				}
				if (fReaderCount == 0) {
					// The last reader needs to unlock the mutex.
					_ReleaseBenaphore(fMutex);
				}
			}	// else: error: caller has no read lock
		}
		fLock.Unlock();
	}	// else: we are probably going to be destroyed
}

// IsReadLocked
//
// Returns whether or not the calling thread owns a read lock or even a
// write lock.
bool
RWLocker::IsReadLocked() const
{
	bool result = false;
	if (fLock.Lock()) {
		thread_id thread = find_thread(NULL);
		result = (thread == fWriter || _IndexOf(thread) >= 0);
		fLock.Unlock();
	}
	return result;
}

// WriteLock
bool
RWLocker::WriteLock()
{
	status_t error = _WriteLock(B_INFINITE_TIMEOUT);
	return (error == B_OK);
}

// WriteLockWithTimeout
status_t
RWLocker::WriteLockWithTimeout(bigtime_t timeout)
{
	bigtime_t absoluteTimeout = system_time() + timeout;
	// take care of overflow
	if (timeout > 0 && absoluteTimeout < 0)
		absoluteTimeout = B_INFINITE_TIMEOUT;
	return _WriteLock(absoluteTimeout);
}

// WriteUnlock
void
RWLocker::WriteUnlock()
{
	if (fLock.Lock()) {
		thread_id thread = find_thread(NULL);
		if (thread == fWriter) {
			fWriterCount--;
			if (--fWriterWriterCount == 0) {
				// The outer write lock bracket for the thread has been
				// reached.
				fWriter = B_ERROR;
				if (fWriterReaderCount > 0) {
					// We still own read locks.
					_NewReadLockInfo(thread, fWriterReaderCount);
					// A reader that expects to be the first reader may wait
					// at the mutex semaphore. We need to wake it up.
					if (fReaderCount > 0)
						_ReleaseBenaphore(fMutex);
					fReaderCount += fWriterReaderCount;
					fWriterReaderCount = 0;
				} else {
					// We don't own any read locks. So we have to release the
					// mutex benaphore.
					_ReleaseBenaphore(fMutex);
				}
			}
		}	// else: error: unmatched WriteUnlock()
		fLock.Unlock();
	}	// else: We're probably going to die.
}

// IsWriteLocked
//
// Returns whether or not the calling thread owns a write lock.
bool
RWLocker::IsWriteLocked() const
{
	return (fWriter == find_thread(NULL));
}

// _Init
void
RWLocker::_Init(const char* name)
{
	// init the mutex benaphore
	BString mutexName(name);
	mutexName += "_RWLocker_mutex";
	fMutex.semaphore = create_sem(0, mutexName.String());
	fMutex.counter = 0;
	// init the queueing benaphore
	BString queueName(name);
	queueName += "_RWLocker_queue";
	fQueue.semaphore = create_sem(0, queueName.String());
	fQueue.counter = 0;
}

// _ReadLock
//
// /timeout/ -- absolute timeout
status_t
RWLocker::_ReadLock(bigtime_t timeout)
{
	status_t error = B_OK;
	thread_id thread = find_thread(NULL);
	bool locked = false;
	if (fLock.Lock()) {
		// Check, if we already own a read (or write) lock. In this case we
		// can skip the usual locking procedure.
		if (thread == fWriter) {
			// We already own a write lock.
			fWriterReaderCount++;
			locked = true;
		} else if (ReadLockInfo* info = _ReadLockInfoAt(_IndexOf(thread))) {
			// We already own a read lock.
			info->count++;
			fReaderCount++;
			locked = true;
		}
		fLock.Unlock();
	} else	// failed to lock the data
		error = B_ERROR;
	// Usual locking, i.e. we do not already own a read or write lock.
	if (error == B_OK && !locked) {
		error = _AcquireBenaphore(fQueue, timeout);
		if (error == B_OK) {
			if (fLock.Lock()) {
				bool firstReader = false;
				if (++fReaderCount == 1) {
					// We are the first reader.
					_NewReadLockInfo(thread);
					firstReader = true;
				} else
					_NewReadLockInfo(thread);
				fLock.Unlock();
				// The first reader needs to lock the mutex.
				if (firstReader) {
					error = _AcquireBenaphore(fMutex, timeout);
					switch (error) {
						case B_OK:
							// fine
							break;
						case B_TIMED_OUT: {
							// clean up
							if (fLock.Lock()) {
								_DeleteReadLockInfo(_IndexOf(thread));
								fReaderCount--;
								fLock.Unlock();
							}
							break;
						}
						default:
							// Probably we are going to be destroyed.
							break;
					}
				}
				// Let the next candidate enter the game.
				_ReleaseBenaphore(fQueue);
			} else {
				// We couldn't lock the data, which can only happen, if
				// we're going to be destroyed.
				error = B_ERROR;
			}
		}
	}
	return error;
}

// _WriteLock
//
// /timeout/ -- absolute timeout
status_t
RWLocker::_WriteLock(bigtime_t timeout)
{
	status_t error = B_ERROR;
	if (fLock.Lock()) {
		bool infiniteTimeout = (timeout == B_INFINITE_TIMEOUT);
		bool locked = false;
		int32 readerCount = 0;
		thread_id thread = find_thread(NULL);
		int32 index = _IndexOf(thread);
		if (ReadLockInfo* info = _ReadLockInfoAt(index)) {
			// We already own a read lock.
			if (fWriterCount > 0) {
				// There are writers before us.
				if (infiniteTimeout) {
					// Timeout is infinite and there are writers before us.
					// Unregister the read locks and lock as usual.
					readerCount = info->count;
					fWriterCount++;
					fReaderCount -= readerCount;
					_DeleteReadLockInfo(index);
					error = B_OK;
				} else {
					// The timeout is finite and there are readers before us:
					// let the write lock request fail.
					error = B_WOULD_BLOCK;
				}
			} else if (info->count == fReaderCount) {
				// No writers before us.
				// We are the only read lock owners. Just move the read lock
				// info data to the special writer fields and then we are done.
				// Note: At this point we may overtake readers that already
				// have acquired the queueing benaphore, but have not yet
				// locked the data. But that doesn't harm.
				fWriter = thread;
				fWriterCount++;
				fWriterWriterCount = 1;
				fWriterReaderCount = info->count;
				fReaderCount -= fWriterReaderCount;
				_DeleteReadLockInfo(index);
				locked = true;
				error = B_OK;
			} else {
				// No writers before us, but other readers.
				// Note, we're quite restrictive here. If there are only
				// readers before us, we could reinstall our readers, if
				// our request times out. Unfortunately it is not easy
				// to ensure, that no writer overtakes us between unlocking
				// the data and acquiring the queuing benaphore.
				if (infiniteTimeout) {
					// Unregister the readers and lock as usual.
					readerCount = info->count;
					fWriterCount++;
					fReaderCount -= readerCount;
					_DeleteReadLockInfo(index);
					error = B_OK;
				} else
					error = B_WOULD_BLOCK;
			}
		} else {
			// We don't own a read lock.
			if (fWriter == thread) {
				// ... but a write lock.
				fWriterCount++;
				fWriterWriterCount++;
				locked = true;
				error = B_OK;
			} else {
				// We own neither read nor write locks.
				// Lock as usual.
				fWriterCount++;
				error = B_OK;
			}
		}
		fLock.Unlock();
		// Usual locking...
		// First step: acquire the queueing benaphore.
		if (!locked && error == B_OK) {
			error = _AcquireBenaphore(fQueue, timeout);
			switch (error) {
				case B_OK:
					break;
				case B_TIMED_OUT: {
					// clean up
					if (fLock.Lock()) {
						fWriterCount--;
						fLock.Unlock();
					}	// else: failed to lock the data: we're probably going
						// to die.
					break;
				}
				default:
					// Probably we're going to die.
					break;
			}
		}
		// Second step: acquire the mutex benaphore.
		if (!locked && error == B_OK) {
			error = _AcquireBenaphore(fMutex, timeout);
			switch (error) {
				case B_OK: {
					// Yeah, we made it. Set the special writer fields.
					fWriter = thread;
					fWriterWriterCount = 1;
					fWriterReaderCount = readerCount;
					break;
				}
				case B_TIMED_OUT: {
					// clean up
					if (fLock.Lock()) {
						fWriterCount--;
						fLock.Unlock();
					}	// else: failed to lock the data: we're probably going
						// to die.
					break;
				}
				default:
					// Probably we're going to die.
					break;
			}
			// Whatever happened, we have to release the queueing benaphore.
			_ReleaseBenaphore(fQueue);
		}
	} else	// failed to lock the data
		error = B_ERROR;
	return error;
}

// _AddReadLockInfo
int32
RWLocker::_AddReadLockInfo(ReadLockInfo* info)
{
	int32 index = fReadLockInfos.CountItems();
	fReadLockInfos.AddItem(info, index);
	return index;
}

// _NewReadLockInfo
//
// Create a new read lock info for the supplied thread and add it to the
// list. Returns the index of the info.
int32
RWLocker::_NewReadLockInfo(thread_id thread, int32 count)
{
	ReadLockInfo* info = new ReadLockInfo;
	info->reader = thread;
	info->count = count;
	return _AddReadLockInfo(info);
}

// _DeleteReadLockInfo
void
RWLocker::_DeleteReadLockInfo(int32 index)
{
	if (ReadLockInfo* info = (ReadLockInfo*)fReadLockInfos.RemoveItem(index))
		delete info;
}

// _ReadLockInfoAt
RWLocker::ReadLockInfo*
RWLocker::_ReadLockInfoAt(int32 index) const
{
	return (ReadLockInfo*)fReadLockInfos.ItemAt(index);
}

// _IndexOf
int32
RWLocker::_IndexOf(thread_id thread) const
{
	int32 count = fReadLockInfos.CountItems();
	for (int32 i = 0; i < count; i++) {
		if (_ReadLockInfoAt(i)->reader == thread)
			return i;
	}
	return -1;
}

// _AcquireBenaphore
status_t
RWLocker::_AcquireBenaphore(Benaphore& benaphore, bigtime_t timeout)
{
	status_t error = B_OK;
	if (atomic_add(&benaphore.counter, 1) > 0) {
		error = acquire_sem_etc(benaphore.semaphore, 1, B_ABSOLUTE_TIMEOUT,
								timeout);
	}
	return error;
}

// _ReleaseBenaphore
void
RWLocker::_ReleaseBenaphore(Benaphore& benaphore)
{
	if (atomic_add(&benaphore.counter, -1) > 1)
		release_sem(benaphore.semaphore);
}