/*
 *  ZThreads, a platform-independant, multithreading and 
 *  synchroniation library
 *
 *  Copyright (C) 2001, 2002 Eric Crahen, See LGPL.TXT for details
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2.1 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
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser 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
 *
 *  SUNY @ Buffalo, hereby disclaims all copyright interest in the
 *  ZThreads library written by Eric Crahen
 */

#include "MutexImpl.h"

#include <assert.h>
#include <errno.h>
#include <algorithm>

using namespace ZThread;

/**
 * Create a new MutexImpl
 *
 * @exception Initialization_Exception thrown if resources could not be
 * properly allocated
 */
MutexImpl::MutexImpl(size_t increment) 
  throw(Synchronization_Exception) : _owner(0), _increment(increment), _count(0) {
 
}

/**
 * Destroy this MutexImpl and release its resources
 */
MutexImpl::~MutexImpl() 
 throw() {

#ifndef NDEBUG

  // It is an error to destroy a mutex that has not been released
  if(_owner != 0) { 

    ZTDEBUG("** You are destroying a mutex which was never released. **\n");
    assert(0); // Destroyed mutex while in use

  }

  if(_waiters.size() > 0) { 

    ZTDEBUG("** You are destroying a mutex which is blocking %d threads. **\n", _waiters.size());
    assert(0); // Destroyed mutex while in use

  }

#endif

}


/**
 * Acquire a lock on the mutex. If this operation succeeds the calling
 * thread holds an exclusive lock on this mutex, otherwise it is blocked 
 * until the lock can be acquired.
 *
 * If the lock cannot be acquired on the first try, an Monitor object is
 * used to block the thread and a reference to it is placed into a waiter
 * list. A Monitor objects are later unblocked one at a time as thier waits
 * are interrupted or as they are assigned ownership of the mutex by a 
 * release()ing thread.
 *
 * @exception Deadlock_Exception thrown when the caller attempts to acquire() more
 * than once, If the checking flag is set.
 * @exception Interrupted_Exception thrown when the callers state is INTERRUPTED
 * @exception Unexpected_Exception thrown when the callers state is KILLED
 * @exception InvalidOp_Exception thrown when the callers state is not RUNNING
 */
void MutexImpl::acquire() 
  throw(Synchronization_Exception) {

  bool isWaiting = false;
  bool isDeadlock = false;

  // Get the monitor for the current thread, and acquire() it. 
  // Placing focus of the synchronization on the monitor.
  MONITOR& m = getMonitor();
  m.acquire();

  // Check the state bits, if none are set then attempt to acquire this Mutex
  unsigned int state = check(m);

  if(!state) {
    
    // Serialize access to the Mutex, to safely update the state.
    _lock.acquire();
  
    // Deadlock will occur if the current thread is the owner 
    // and there is no entry count.
    if(_owner == &m && _count == 0) 
      isDeadlock = true;
    
    // If there is an entry count and the current thread is 
    // the owner, increment the count and continue.
    else if(_owner == &m) 
      _count += _increment;

    else {

      // Acquire the lock if it is free and there are no waiting threads
      if(_owner == 0 && _waiters.empty()) {
        _owner = &m;
        _count = _increment;
      }

      // Otherwise, wait() for the lock by placing the waiter in the list
      else {
        
        _waiters.push_back(&m);
        isWaiting = true;
        
      }
      
    }
    
    // Release the Mutex lock
    _lock.release();
      
    if(isWaiting) {

      // If the Mutex could not immediately acquired, wait until the monitor 
      // is notify()d. 

      // Wait for a signal
      m.wait();

      // The SIGNAL flag will be set (and cleared here) if wait() was terminated 
      // by a release(). The state can be checked to avoid searching the list
      // of waiters if it is not neccessary
      state = check(m);
      
      m.release();

      // Here there is a lack of atomicity on the Mutex and the monitor. 
      // Rely on the sticky nature of the monitor to stay in a consistent state

      // Serialize access to the Mutex, update the state. The focus is really still
      // on the monitors.
      _lock.acquire();

      // If awoke due to release(), take ownership. 
      if(state & State::SIGNAL) {
        
        // Update the Mutex
        _owner = &m;
        _count = _increment;
        state = 0;

        // The thread should not in the waiter list if it was SIGNALed.
        assert(std::find(_waiters.begin(), _waiters.end(), &m) == _waiters.end());

      } else {

        // Remove self from the waiter list.
        WaiterList::iterator i;
        i = std::find(_waiters.begin(), _waiters.end(), &m);
        assert(i != _waiters.end());
        _waiters.erase(i);

      }

      // Release the Mutex lock
      _lock.release();

    } else 
      m.release(); // Release monitor when no wait is needed
    
  } else 
    m.release(); // Release monitor when state does not check out initially


  // Check for deadlock when the _increment is 0
  if(isDeadlock)
    throw Deadlock_Exception();

  // Check the state and throw an exception if needed.
  if(state & State::KILLED)
    throw Unexpected_Exception();

  if(state & State::INTERRUPTED)
    throw Interrupted_Exception();

  if(state)
    throw InvalidOp_Exception();

}

/**
 * Acquire a lock on the mutex. If this operation succeeds the calling
 * thread holds an exclusive lock on this mutex. If the lock cannot be
 * obtained before the timeout expires, the caller returns false.
 *
 * @param timeout milliseconds
 * @return bool true if the lock was acquired.
 *
 * @exception Deadlock_Exception thrown when the caller attempts to acquire() more
 * than once, If the checking flag is set.
 * @exception Interrupted_Exception thrown when the callers state is INTERRUPTED
 * @exception Unexpected_Exception thrown when the callers state is KILLED
 * @exception InvalidOp_Exception thrown when the callers state is not RUNNING
 */
bool MutexImpl::tryAcquire(unsigned long timeout) 
  throw (Synchronization_Exception) {
  
  bool isWaiting = false;
  bool isDeadlock = false;
  bool wasOnTime = false;

  // Get the monitor for the current thread, and acquire() it. 
  // Placing focus of the synchronization on the monitor.
  MONITOR& m = getMonitor();
  m.acquire();

  // Check the state bits, if none are set then attempt to acquire this Mutex
  unsigned int state = check(m);
  if(!state) {
    
    // Serialize access to the Mutex, to safely update the state.
    _lock.acquire();
  
    // Deadlock will occur if the current thread is the owner 
    // and there is no entry count.
    if(_owner == &m && _count == 0) 
      isDeadlock = true;
    
    // If there is an entry count and the current thread is 
    // the owner, increment the count and continue.
    else if(_owner == &m) {

      _count += _increment;
      wasOnTime = true;

    } else {

      // Acquire the lock if it is free and there are no waiting threads
      if(_owner == 0 && _waiters.empty()) {

        _owner = &m;
        _count = _increment;
        wasOnTime = true;

      }

      // Otherwise, wait() for the lock by placing the waiter in the list
      // if there is a valid timeout
      else if(timeout > 0) {
        
        _waiters.push_back(&m);
        isWaiting = true;
        
      }
      
    }

    // Release the Mutex lock
    _lock.release();
  
    // If the lock was not acquired, wait until the monitor is notify()d.
    if(isWaiting) {

      // Wait with a timeout
      wasOnTime = m.wait(timeout);

      // The SIGNAL flag will be set (and cleared here) if wait() was terminated 
      // by a release(). The state can be checked to avoid searching the list
      // of waiters if it is not neccessary
      state = check(m);

      // It is also possible that wait will awaken with no flags set simply due
      // to the timeout. The monitor will still be in the waiter list, and could
      // possibly be sent a phantom signal by a late release()

      m.release(); 

      // Here there is a lack of atomicity on the Mutex and the monitor. 
      // Rely on the sticky nature of the monitor to stay in a consistent state

      // Serialize access to the Mutex, update the state. The focus is really still
      // on the monitors.
      _lock.acquire();
     
      // If awoke due to notify(), take ownership.
      if(state & State::SIGNAL) {

        _owner = &m;
        _count = _increment;
        state = 0;
        wasOnTime = true;

        // The thread should not in the waiter list if it was SIGNALed.
        assert(std::find(_waiters.begin(), _waiters.end(), &m) == _waiters.end());

      } else {

        // Remove self from the waiter list.
        WaiterList::iterator i;
        i = std::find(_waiters.begin(), _waiters.end(), &m);
        if(i != _waiters.end())
          _waiters.erase(i);
        
        else if(!state) {
          
          // Presumably, this should happen only if the thread timesout during
          // a wait and is signalled before it can remove itself from the waiter
          // list.

          assert(wasOnTime);

          // If the thread was signaled sometime between when it woke up
          // from a timeout & before it was able to attempt to remove itself
          // from the waiter list, then absorb the phantom signal

          state = State::SIGNAL;

        }

      }

      // Release the Mutex lock
      _lock.release();

    } else 
      m.release(); // Release monitor when no wait is needed
    
  } else 
    m.release(); // Release monitor when state does not check out initially


  // Check for deadlock when the _increment is 0
  if(isDeadlock)
    throw Deadlock_Exception();

  // Check the state and absorb phantom signal
  if(state & State::SIGNAL) {
    
    m.acquire();   
    
    // Only clear the monitor if the state is SIGNAL'd. If another flag
    // was set, then leave it and just continue.
    state = (check(m) & ~State::SIGNAL);

    // This won't block because we know there is a phantom signal
    if(!state) {
      
      m.wait(); 
      state = 0;

    }

    m.acquire();
        
  }

  // Check the state and throw an exception if needed.
  if(state & State::KILLED)
    throw Unexpected_Exception();

  if(state & State::INTERRUPTED)
    throw Interrupted_Exception();

  if(state)
    throw InvalidOp_Exception();

  return wasOnTime;

}

/**
 * Release a lock on the mutex. If this operation succeeds the calling
 * thread no longer holds an exclusive lock on this mutex. If there are 
 * waiting threads, one will be selected, assigned ownership and specifically 
 * awakened.
 *
 * @exception InvalidOp_Exception - thrown if an attempt is made to 
 * release a mutex not owned by the calling thread.
 */
void MutexImpl::release() 
  throw (Synchronization_Exception) {

  MONITOR* m = 0;
  bool isOwner = false;

  // Serialize access to the Mutex
  _lock.acquire();

  // The caller should own this Mutex
  if(isOwner = (_owner == &getMonitor())) {

    // Update the count
    _count -= _increment;
    if(_count == 0) {

      // To avoid notifying same monitor more than once (stolen signal)  
      // a signaled monitor is removed from the waiter list.
      
      for(WaiterList::iterator i = _waiters.begin(); i != _waiters.end(); ++i) {

        // Find a monitor that is still in the waiter list and has not 
        // been awaken.

        m = *i;

        // Acquire the monitor, preventing any interference from an 
        // interrupt() that might result in an extra notfy() being sent 
        // to that monitor (phantom signal)
        m->acquire();

        // If a monitor is selected, hold its lock and notify() it after
        // releasing the lock on this Mutex. If successful then mark the 
        // monitor with the SIGNAL flag.
        if(wake(*m)) {

          _waiters.erase(i);
          break;

        }

        // A thread may have been awakened by an interrupt() or kill() and
        // simply be waiting to acquire the lock for this Mutex and has not 
        // yet been able to remove itself from the waiter list. In those
        // cases, there will be either an INTERRUPTED or KILLED flag set 
        // that can be check so those threads can be skipped (mis-signaled)

        m->release();
        m = 0;

      }
      
      // Remove the previous owner
      _owner = 0;

    }

  }

  _lock.release();
  
  // notify() the selected monitor
  if(m) {

    m->notify();
    m->release();

  }

  // If the calling thread was not the owner, throw an exception
  if(!isOwner)
    throw InvalidOp_Exception();

}





