src/parsec/disk-image/parsec/parsec-benchmark/pkgs/libs/tbblib/src/src/tbb/reader_writer_lock.cpp - public/gem5-resources - Git at Google

 /*
     Copyright 2005-2010 Intel Corporation.  All Rights Reserved.

     This file is part of Threading Building Blocks.

     Threading Building Blocks is free software; you can redistribute it
     and/or modify it under the terms of the GNU General Public License
     version 2 as published by the Free Software Foundation.

     Threading Building Blocks 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 General Public License for more details.

     You should have received a copy of the GNU General Public License
     along with Threading Building Blocks; if not, write to the Free Software
     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

     As a special exception, you may use this file as part of a free software
     library without restriction.  Specifically, if other files instantiate
     templates or use macros or inline functions from this file, or you compile
     this file and link it with other files to produce an executable, this
     file does not by itself cause the resulting executable to be covered by
     the GNU General Public License.  This exception does not however
     invalidate any other reasons why the executable file might be covered by
     the GNU General Public License.
 */

 #include "tbb/reader_writer_lock.h"
 #include "tbb/tbb_machine.h"
 #include "tbb/tbb_exception.h"
 #include "itt_notify.h"

 namespace tbb {
 namespace interface5 {

 const unsigned WFLAG1 = 0x1;  // writer interested or active
 const unsigned WFLAG2 = 0x2;  // writers interested, no entering readers
 const unsigned RFLAG = 0x4;   // reader interested but not active
 const unsigned RC_INCR = 0x8; // to adjust reader count


 // Perform an atomic bitwise-OR on the operand with the addend, and return
 // the previous value of the operand.
 inline unsigned fetch_and_or(atomic<unsigned>& operand, unsigned addend) {
     tbb::internal::atomic_backoff backoff;
     for (;;) {
         unsigned old = operand;
         unsigned result = operand.compare_and_swap(old|addend, old);
         if (result==old) return old;
         backoff.pause();
     }
 }

 // Perform an atomic bitwise-AND on the operand with the addend, and return
 // the previous value of the operand.
 inline unsigned fetch_and_and(atomic<unsigned>& operand, unsigned addend) {
     tbb::internal::atomic_backoff backoff;
     for (;;) {
         unsigned old = operand;
         unsigned result = operand.compare_and_swap(old&addend, old);
         if (result==old) return old;
         backoff.pause();
     }
 }

 //! Spin WHILE the value at the location is greater than or equal to a given value
 /** T and U should be comparable types. */
 template<typename T, typename U>
 void spin_wait_while_geq( const volatile T& location, U value ) {
     tbb::internal::atomic_backoff backoff;
     while( location>=value ) backoff.pause();
 }

 //! Spin UNTIL (location & value) is true.
 /** T and U should be comparable types. */
 template<typename T, typename U>
 void spin_wait_until_and( const volatile T& location, U value ) {
     tbb::internal::atomic_backoff backoff;
     while( !(location & value) ) backoff.pause();
 }


 void reader_writer_lock::internal_construct() {
     reader_head = NULL;
     writer_head = NULL;
     writer_tail = NULL;
     rdr_count_and_flags = 0;
     my_current_writer = tbb_thread::id();
 #if TBB_USE_THREADING_TOOLS
     ITT_SYNC_CREATE(this, _T("tbb::reader_writer_lock"), _T(""));
 #endif /* TBB_USE_THREADING_TOOLS */
 }

 void reader_writer_lock::internal_destroy() {
     __TBB_ASSERT(rdr_count_and_flags==0, "reader_writer_lock destroyed with pending readers/writers.");
     __TBB_ASSERT(reader_head==NULL, "reader_writer_lock destroyed with pending readers.");
     __TBB_ASSERT(writer_tail==NULL, "reader_writer_lock destroyed with pending writers.");
     __TBB_ASSERT(writer_head==NULL, "reader_writer_lock destroyed with pending/active writers.");
 }

 // Acquires the reader_writer_lock for write.    If the lock is currently held in write
 // mode by another context, the writer will block by spinning on a local variable.
 // Throws exception improper_lock if the context tries to acquire a
 // reader_writer_lock that it already has write ownership of.
 void reader_writer_lock::lock() {
     if (is_current_writer()) { // recursive lock attempt
         // we don't support recursive writer locks; throw exception
         tbb::internal::throw_exception(tbb::internal::eid_improper_lock);
     }
     else {
         scoped_lock *a_writer_lock = new scoped_lock();
         (void) start_write(a_writer_lock);
     }
 }

 // Tries to acquire the reader_writer_lock for write.    This function does not block.
 // Return Value: True or false, depending on whether the lock is acquired or not.
 // If the lock is already held by this acquiring context, try_lock() returns false.
 bool reader_writer_lock::try_lock() {
     if (is_current_writer()) { // recursive lock attempt
         return false;
     }
     else {
         scoped_lock *a_writer_lock = new scoped_lock();
         a_writer_lock->status = waiting_nonblocking;
         return start_write(a_writer_lock);
     }
 }

 bool reader_writer_lock::start_write(scoped_lock *I) {
     tbb_thread::id id = this_tbb_thread::get_id();
     scoped_lock *pred = NULL;
     if (I->status == waiting_nonblocking) {
         if ((pred = writer_tail.compare_and_swap(I, NULL)) != NULL) {
             delete I;
             return false;
         }
     }
     else {
         ITT_NOTIFY(sync_prepare, this);
         pred = writer_tail.fetch_and_store(I);
     }
     if (pred)
         pred->next = I;
     else {
         set_next_writer(I);
         if (I->status == waiting_nonblocking) {
             if (I->next) { // potentially more writers
                 set_next_writer(I->next);
             }
             else { // no more writers
                 writer_head.fetch_and_store(NULL);
                 if (I != writer_tail.compare_and_swap(NULL, I)) { // an incoming writer is in the process of being added
                     spin_wait_while_eq(I->next, (scoped_lock *)NULL);  // wait for new writer to be added
                     __TBB_ASSERT(I->next, "There should be a node following the last writer.");
                     set_next_writer(I->next);
                 }
             }
             delete I;
             return false;
         }
     }
     spin_wait_while_eq(I->status, waiting);
     ITT_NOTIFY(sync_acquired, this);
     my_current_writer = id;
     return true;
 }

 void reader_writer_lock::set_next_writer(scoped_lock *W) {
     writer_head = W;
     if (W->status == waiting_nonblocking) {
         if (rdr_count_and_flags.compare_and_swap(WFLAG1+WFLAG2, 0) == 0) {
             W->status = active;
         }
     }
     else {
         if (fetch_and_or(rdr_count_and_flags, WFLAG1) & RFLAG) { // reader present
             spin_wait_until_and(rdr_count_and_flags, WFLAG2); // block until readers set WFLAG2
         }
         else { // no reader in timing window
             __TBB_AtomicOR(&rdr_count_and_flags, WFLAG2);
         }
         spin_wait_while_geq(rdr_count_and_flags, RC_INCR); // block until readers finish
         W->status = active;
    }
 }

 // Acquires the reader_writer_lock for read.    If the lock is currently held by a writer,
 // this reader will block and wait until the writers are done.
 // Throws exception improper_lock when the context tries to acquire a reader_writer_lock
 // that it already has write ownership of.
 void reader_writer_lock::lock_read() {
     if (is_current_writer()) { // recursive lock attempt
         // we don't support writer->reader downgrade; throw exception
         tbb::internal::throw_exception(tbb::internal::eid_improper_lock);
     }
     else {
         scoped_lock_read a_reader_lock;
         start_read(&a_reader_lock);
     }
 }

 // Tries to acquire the reader_writer_lock for read.    This function does not block.
 // Return Value: True or false, depending on whether the lock is acquired or not.
 bool reader_writer_lock::try_lock_read() {
     if (is_current_writer()) { // recursive lock attempt
         return false;
     }
     else {
         if (rdr_count_and_flags.fetch_and_add(RC_INCR) & (WFLAG1+WFLAG2)) { // writers present
             rdr_count_and_flags -= RC_INCR;
             return false;
         }
         else { // no writers
             ITT_NOTIFY(sync_acquired, this);
             return true;
         }
     }
 }

 void reader_writer_lock::start_read(scoped_lock_read *I) {
     ITT_NOTIFY(sync_prepare, this);
     I->next = reader_head.fetch_and_store(I);
     if (!I->next) { // first arriving reader in my group; set RFLAG, test writer flags
         // unblock and/or update statuses of non-blocking readers
         if (!(fetch_and_or(rdr_count_and_flags, RFLAG) & (WFLAG1+WFLAG2))) { // no writers
             unblock_readers();
         }
     }
     __TBB_ASSERT(I->status == waiting || I->status == active, "Lock requests should be waiting or active before blocking.");
     spin_wait_while_eq(I->status, waiting); // block
     if (I->next) {
         __TBB_ASSERT(I->next->status == waiting, NULL);
         rdr_count_and_flags += RC_INCR;
         I->next->status = active; // wake successor
     }
     ITT_NOTIFY(sync_acquired, this);
 }

 void reader_writer_lock::unblock_readers() {
     // clear rdr interest flag, increment rdr count
     __TBB_ASSERT(rdr_count_and_flags&RFLAG, NULL);
     rdr_count_and_flags += RC_INCR-RFLAG;
     __TBB_ASSERT(rdr_count_and_flags >= RC_INCR, NULL);
     // indicate clear of window
     if (rdr_count_and_flags & WFLAG1 && !(rdr_count_and_flags & WFLAG2)) {
         __TBB_AtomicOR(&rdr_count_and_flags, WFLAG2);
     }
     // unblock waiting readers
     scoped_lock_read *head = reader_head.fetch_and_store(NULL);
     __TBB_ASSERT(head, NULL);
     __TBB_ASSERT(head->status == waiting, NULL);
     head->status = active;
 }

 // Releases the reader_writer_lock
 void reader_writer_lock::unlock() {
     if( my_current_writer!=tbb_thread::id() ) {
         // A writer owns the lock
         __TBB_ASSERT(is_current_writer(), "caller of reader_writer_lock::unlock() does not own the lock.");
         __TBB_ASSERT(writer_head, NULL);
         __TBB_ASSERT(writer_head->status==active, NULL);
         scoped_lock *a_writer_lock = writer_head;
         end_write(a_writer_lock);
         __TBB_ASSERT(a_writer_lock != writer_head, "Internal error: About to turn writer_head into dangling reference.");
         delete a_writer_lock;
     } else {
         end_read();
     }
 }

 void reader_writer_lock::end_write(scoped_lock *I) {
     __TBB_ASSERT(I==writer_head, "Internal error: can't unlock a thread that is not holding the lock.");
     my_current_writer = tbb_thread::id();
     ITT_NOTIFY(sync_releasing, this);
     if (I->next) { // potentially more writers
         writer_head = I->next;
         writer_head->status = active;
     }
     else { // No more writers; clear writer flag, test reader interest flag
         __TBB_ASSERT(writer_head, NULL);
         if (fetch_and_and(rdr_count_and_flags, ~(WFLAG1+WFLAG2)) & RFLAG) {
             unblock_readers();
         }
         writer_head.fetch_and_store(NULL);
         if (I != writer_tail.compare_and_swap(NULL, I)) { // an incoming writer is in the process of being added
             spin_wait_while_eq(I->next, (scoped_lock *)NULL);  // wait for new writer to be added
             __TBB_ASSERT(I->next, "There should be a node following the last writer.");
             set_next_writer(I->next);
         }
     }
 }

 void reader_writer_lock::end_read() {
     ITT_NOTIFY(sync_releasing, this);
     __TBB_ASSERT(rdr_count_and_flags >= RC_INCR, "unlock() called but no readers hold the lock.");
     rdr_count_and_flags -= RC_INCR;
 }

 inline bool reader_writer_lock::is_current_writer() {
     return my_current_writer==this_tbb_thread::get_id();
 }

 // Construct with a blocking attempt to acquire a write lock on the passed reader_writer_lock
 void reader_writer_lock::scoped_lock::internal_construct (reader_writer_lock& lock) {
     mutex = &lock;
     next = NULL;
     status = waiting;
     if (mutex->is_current_writer()) { // recursive lock attempt
         // we don't support recursive writer locks; throw exception
         tbb::internal::throw_exception(tbb::internal::eid_improper_lock);
     }
     else { // this thread holds no locks
         (void) mutex->start_write(this);
     }
 }

 inline reader_writer_lock::scoped_lock::scoped_lock() : mutex(NULL), next(NULL) {
     status = waiting;
 }

 // Construct with a blocking attempt to acquire a write lock on the passed reader_writer_lock
 void reader_writer_lock::scoped_lock_read::internal_construct (reader_writer_lock& lock) {
     mutex = &lock;
     next = NULL;
     status = waiting;
     if (mutex->is_current_writer()) { // recursive lock attempt
         // we don't support writer->reader downgrade; throw exception
         tbb::internal::throw_exception(tbb::internal::eid_improper_lock);
     }
     else { // this thread holds no locks
         mutex->start_read(this);
     }
 }

 inline reader_writer_lock::scoped_lock_read::scoped_lock_read() : mutex(NULL), next(NULL) {
     status = waiting;
 }

 void reader_writer_lock::scoped_lock::internal_destroy() {
     if (mutex) {
         __TBB_ASSERT(mutex->is_current_writer(), "~scoped_lock() destroyed by thread different than thread that holds lock.");
         mutex->end_write(this);
     }
     status = invalid;
 }

 void reader_writer_lock::scoped_lock_read::internal_destroy() {
     if (mutex)
         mutex->end_read();
     status = invalid;
 }

 } // namespace interface5
 } // namespace tbb
	/*
	Copyright 2005-2010 Intel Corporation. All Rights Reserved.

	This file is part of Threading Building Blocks.

	Threading Building Blocks is free software; you can redistribute it
	and/or modify it under the terms of the GNU General Public License
	version 2 as published by the Free Software Foundation.

	Threading Building Blocks 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 General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with Threading Building Blocks; if not, write to the Free Software
	Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA

	As a special exception, you may use this file as part of a free software
	library without restriction. Specifically, if other files instantiate
	templates or use macros or inline functions from this file, or you compile
	this file and link it with other files to produce an executable, this
	file does not by itself cause the resulting executable to be covered by
	the GNU General Public License. This exception does not however
	invalidate any other reasons why the executable file might be covered by
	the GNU General Public License.
	*/

	#include "tbb/reader_writer_lock.h"
	#include "tbb/tbb_machine.h"
	#include "tbb/tbb_exception.h"
	#include "itt_notify.h"

	namespace tbb {
	namespace interface5 {

	const unsigned WFLAG1 = 0x1; // writer interested or active
	const unsigned WFLAG2 = 0x2; // writers interested, no entering readers
	const unsigned RFLAG = 0x4; // reader interested but not active
	const unsigned RC_INCR = 0x8; // to adjust reader count


	// Perform an atomic bitwise-OR on the operand with the addend, and return
	// the previous value of the operand.
	inline unsigned fetch_and_or(atomic<unsigned>& operand, unsigned addend) {
	tbb::internal::atomic_backoff backoff;
	for (;;) {
	unsigned old = operand;
	unsigned result = operand.compare_and_swap(old\|addend, old);
	if (result==old) return old;
	backoff.pause();
	}
	}

	// Perform an atomic bitwise-AND on the operand with the addend, and return
	// the previous value of the operand.
	inline unsigned fetch_and_and(atomic<unsigned>& operand, unsigned addend) {
	tbb::internal::atomic_backoff backoff;
	for (;;) {
	unsigned old = operand;
	unsigned result = operand.compare_and_swap(old&addend, old);
	if (result==old) return old;
	backoff.pause();
	}
	}

	//! Spin WHILE the value at the location is greater than or equal to a given value
	/** T and U should be comparable types. */
	template<typename T, typename U>
	void spin_wait_while_geq( const volatile T& location, U value ) {
	tbb::internal::atomic_backoff backoff;
	while( location>=value ) backoff.pause();
	}

	//! Spin UNTIL (location & value) is true.
	/** T and U should be comparable types. */
	template<typename T, typename U>
	void spin_wait_until_and( const volatile T& location, U value ) {
	tbb::internal::atomic_backoff backoff;
	while( !(location & value) ) backoff.pause();
	}


	void reader_writer_lock::internal_construct() {
	reader_head = NULL;
	writer_head = NULL;
	writer_tail = NULL;
	rdr_count_and_flags = 0;
	my_current_writer = tbb_thread::id();
	#if TBB_USE_THREADING_TOOLS
	ITT_SYNC_CREATE(this, _T("tbb::reader_writer_lock"), _T(""));
	#endif /* TBB_USE_THREADING_TOOLS */
	}

	void reader_writer_lock::internal_destroy() {
	__TBB_ASSERT(rdr_count_and_flags==0, "reader_writer_lock destroyed with pending readers/writers.");
	__TBB_ASSERT(reader_head==NULL, "reader_writer_lock destroyed with pending readers.");
	__TBB_ASSERT(writer_tail==NULL, "reader_writer_lock destroyed with pending writers.");
	__TBB_ASSERT(writer_head==NULL, "reader_writer_lock destroyed with pending/active writers.");
	}

	// Acquires the reader_writer_lock for write. If the lock is currently held in write
	// mode by another context, the writer will block by spinning on a local variable.
	// Throws exception improper_lock if the context tries to acquire a
	// reader_writer_lock that it already has write ownership of.
	void reader_writer_lock::lock() {
	if (is_current_writer()) { // recursive lock attempt
	// we don't support recursive writer locks; throw exception
	tbb::internal::throw_exception(tbb::internal::eid_improper_lock);
	}
	else {
	scoped_lock *a_writer_lock = new scoped_lock();
	(void) start_write(a_writer_lock);
	}
	}

	// Tries to acquire the reader_writer_lock for write. This function does not block.
	// Return Value: True or false, depending on whether the lock is acquired or not.
	// If the lock is already held by this acquiring context, try_lock() returns false.
	bool reader_writer_lock::try_lock() {
	if (is_current_writer()) { // recursive lock attempt
	return false;
	}
	else {
	scoped_lock *a_writer_lock = new scoped_lock();
	a_writer_lock->status = waiting_nonblocking;
	return start_write(a_writer_lock);
	}
	}

	bool reader_writer_lock::start_write(scoped_lock *I) {
	tbb_thread::id id = this_tbb_thread::get_id();
	scoped_lock *pred = NULL;
	if (I->status == waiting_nonblocking) {
	if ((pred = writer_tail.compare_and_swap(I, NULL)) != NULL) {
	delete I;
	return false;
	}
	}
	else {
	ITT_NOTIFY(sync_prepare, this);
	pred = writer_tail.fetch_and_store(I);
	}
	if (pred)
	pred->next = I;
	else {
	set_next_writer(I);
	if (I->status == waiting_nonblocking) {
	if (I->next) { // potentially more writers
	set_next_writer(I->next);
	}
	else { // no more writers
	writer_head.fetch_and_store(NULL);
	if (I != writer_tail.compare_and_swap(NULL, I)) { // an incoming writer is in the process of being added
	spin_wait_while_eq(I->next, (scoped_lock *)NULL); // wait for new writer to be added
	__TBB_ASSERT(I->next, "There should be a node following the last writer.");
	set_next_writer(I->next);
	}
	}
	delete I;
	return false;
	}
	}
	spin_wait_while_eq(I->status, waiting);
	ITT_NOTIFY(sync_acquired, this);
	my_current_writer = id;
	return true;
	}

	void reader_writer_lock::set_next_writer(scoped_lock *W) {
	writer_head = W;
	if (W->status == waiting_nonblocking) {
	if (rdr_count_and_flags.compare_and_swap(WFLAG1+WFLAG2, 0) == 0) {
	W->status = active;
	}
	}
	else {
	if (fetch_and_or(rdr_count_and_flags, WFLAG1) & RFLAG) { // reader present
	spin_wait_until_and(rdr_count_and_flags, WFLAG2); // block until readers set WFLAG2
	}
	else { // no reader in timing window
	__TBB_AtomicOR(&rdr_count_and_flags, WFLAG2);
	}
	spin_wait_while_geq(rdr_count_and_flags, RC_INCR); // block until readers finish
	W->status = active;
	}
	}

	// Acquires the reader_writer_lock for read. If the lock is currently held by a writer,
	// this reader will block and wait until the writers are done.
	// Throws exception improper_lock when the context tries to acquire a reader_writer_lock
	// that it already has write ownership of.
	void reader_writer_lock::lock_read() {
	if (is_current_writer()) { // recursive lock attempt
	// we don't support writer->reader downgrade; throw exception
	tbb::internal::throw_exception(tbb::internal::eid_improper_lock);
	}
	else {
	scoped_lock_read a_reader_lock;
	start_read(&a_reader_lock);
	}
	}

	// Tries to acquire the reader_writer_lock for read. This function does not block.
	// Return Value: True or false, depending on whether the lock is acquired or not.
	bool reader_writer_lock::try_lock_read() {
	if (is_current_writer()) { // recursive lock attempt
	return false;
	}
	else {
	if (rdr_count_and_flags.fetch_and_add(RC_INCR) & (WFLAG1+WFLAG2)) { // writers present
	rdr_count_and_flags -= RC_INCR;
	return false;
	}
	else { // no writers
	ITT_NOTIFY(sync_acquired, this);
	return true;
	}
	}
	}

	void reader_writer_lock::start_read(scoped_lock_read *I) {
	ITT_NOTIFY(sync_prepare, this);
	I->next = reader_head.fetch_and_store(I);
	if (!I->next) { // first arriving reader in my group; set RFLAG, test writer flags
	// unblock and/or update statuses of non-blocking readers
	if (!(fetch_and_or(rdr_count_and_flags, RFLAG) & (WFLAG1+WFLAG2))) { // no writers
	unblock_readers();
	}
	}
	__TBB_ASSERT(I->status == waiting \|\| I->status == active, "Lock requests should be waiting or active before blocking.");
	spin_wait_while_eq(I->status, waiting); // block
	if (I->next) {
	__TBB_ASSERT(I->next->status == waiting, NULL);
	rdr_count_and_flags += RC_INCR;
	I->next->status = active; // wake successor
	}
	ITT_NOTIFY(sync_acquired, this);
	}

	void reader_writer_lock::unblock_readers() {
	// clear rdr interest flag, increment rdr count
	__TBB_ASSERT(rdr_count_and_flags&RFLAG, NULL);
	rdr_count_and_flags += RC_INCR-RFLAG;
	__TBB_ASSERT(rdr_count_and_flags >= RC_INCR, NULL);
	// indicate clear of window
	if (rdr_count_and_flags & WFLAG1 && !(rdr_count_and_flags & WFLAG2)) {
	__TBB_AtomicOR(&rdr_count_and_flags, WFLAG2);
	}
	// unblock waiting readers
	scoped_lock_read *head = reader_head.fetch_and_store(NULL);
	__TBB_ASSERT(head, NULL);
	__TBB_ASSERT(head->status == waiting, NULL);
	head->status = active;
	}

	// Releases the reader_writer_lock
	void reader_writer_lock::unlock() {
	if( my_current_writer!=tbb_thread::id() ) {
	// A writer owns the lock
	__TBB_ASSERT(is_current_writer(), "caller of reader_writer_lock::unlock() does not own the lock.");
	__TBB_ASSERT(writer_head, NULL);
	__TBB_ASSERT(writer_head->status==active, NULL);
	scoped_lock *a_writer_lock = writer_head;
	end_write(a_writer_lock);
	__TBB_ASSERT(a_writer_lock != writer_head, "Internal error: About to turn writer_head into dangling reference.");
	delete a_writer_lock;
	} else {
	end_read();
	}
	}

	void reader_writer_lock::end_write(scoped_lock *I) {
	__TBB_ASSERT(I==writer_head, "Internal error: can't unlock a thread that is not holding the lock.");
	my_current_writer = tbb_thread::id();
	ITT_NOTIFY(sync_releasing, this);
	if (I->next) { // potentially more writers
	writer_head = I->next;
	writer_head->status = active;
	}
	else { // No more writers; clear writer flag, test reader interest flag
	__TBB_ASSERT(writer_head, NULL);
	if (fetch_and_and(rdr_count_and_flags, ~(WFLAG1+WFLAG2)) & RFLAG) {
	unblock_readers();
	}
	writer_head.fetch_and_store(NULL);
	if (I != writer_tail.compare_and_swap(NULL, I)) { // an incoming writer is in the process of being added
	spin_wait_while_eq(I->next, (scoped_lock *)NULL); // wait for new writer to be added
	__TBB_ASSERT(I->next, "There should be a node following the last writer.");
	set_next_writer(I->next);
	}
	}
	}

	void reader_writer_lock::end_read() {
	ITT_NOTIFY(sync_releasing, this);
	__TBB_ASSERT(rdr_count_and_flags >= RC_INCR, "unlock() called but no readers hold the lock.");
	rdr_count_and_flags -= RC_INCR;
	}

	inline bool reader_writer_lock::is_current_writer() {
	return my_current_writer==this_tbb_thread::get_id();
	}

	// Construct with a blocking attempt to acquire a write lock on the passed reader_writer_lock
	void reader_writer_lock::scoped_lock::internal_construct (reader_writer_lock& lock) {
	mutex = &lock;
	next = NULL;
	status = waiting;
	if (mutex->is_current_writer()) { // recursive lock attempt
	// we don't support recursive writer locks; throw exception
	tbb::internal::throw_exception(tbb::internal::eid_improper_lock);
	}
	else { // this thread holds no locks
	(void) mutex->start_write(this);
	}
	}

	inline reader_writer_lock::scoped_lock::scoped_lock() : mutex(NULL), next(NULL) {
	status = waiting;
	}

	// Construct with a blocking attempt to acquire a write lock on the passed reader_writer_lock
	void reader_writer_lock::scoped_lock_read::internal_construct (reader_writer_lock& lock) {
	mutex = &lock;
	next = NULL;
	status = waiting;
	if (mutex->is_current_writer()) { // recursive lock attempt
	// we don't support writer->reader downgrade; throw exception
	tbb::internal::throw_exception(tbb::internal::eid_improper_lock);
	}
	else { // this thread holds no locks
	mutex->start_read(this);
	}
	}

	inline reader_writer_lock::scoped_lock_read::scoped_lock_read() : mutex(NULL), next(NULL) {
	status = waiting;
	}

	void reader_writer_lock::scoped_lock::internal_destroy() {
	if (mutex) {
	__TBB_ASSERT(mutex->is_current_writer(), "~scoped_lock() destroyed by thread different than thread that holds lock.");
	mutex->end_write(this);
	}
	status = invalid;
	}

	void reader_writer_lock::scoped_lock_read::internal_destroy() {
	if (mutex)
	mutex->end_read();
	status = invalid;
	}

	} // namespace interface5
	} // namespace tbb