class Concurrent::ReentrantReadWriteLock

def acquire_read_lock
  if (held = @HeldCount.value) > 0
    # If we already have a lock, there's no need to wait
    if held & READ_LOCK_MASK == 0
      # But we do need to update the counter, if we were holding a write
      #   lock but not a read lock
      @Counter.update { |c| c + 1 }
    end
    @HeldCount.value = held + 1
    return true
  end
  while true
    c = @Counter.value
    raise ResourceLimitError.new('Too many reader threads') if max_readers?(c)
    # If a writer is waiting OR running when we first queue up, we need to wait
    if waiting_or_running_writer?(c)
      # Before going to sleep, check again with the ReadQueue mutex held
      @ReadQueue.synchronize do
        @ReadQueue.ns_wait if waiting_or_running_writer?
      end
      # Note: the above 'synchronize' block could have used #wait_until,
      #   but that waits repeatedly in a loop, checking the wait condition
      #   each time it wakes up (to protect against spurious wakeups)
      # But we are already in a loop, which is only broken when we successfully
      #   acquire the lock! So we don't care about spurious wakeups, and would
      #   rather not pay the extra overhead of using #wait_until
      # After a reader has waited once, they are allowed to "barge" ahead of waiting writers
      # But if a writer is *running*, the reader still needs to wait (naturally)
      while true
        c = @Counter.value
        if running_writer?(c)
          @ReadQueue.synchronize do
            @ReadQueue.ns_wait if running_writer?
          end
        elsif @Counter.compare_and_set(c, c+1)
          @HeldCount.value = held + 1
          return true
        end
      end
    elsif @Counter.compare_and_set(c, c+1)
      @HeldCount.value = held + 1
      return true
    end
  end
end

def acquire_write_lock
  if (held = @HeldCount.value) >= WRITE_LOCK_HELD
    # if we already have a write (exclusive) lock, there's no need to wait
    @HeldCount.value = held + WRITE_LOCK_HELD
    return true
  end
  while true
    c = @Counter.value
    raise ResourceLimitError.new('Too many writer threads') if max_writers?(c)
    # To go ahead and take the lock without waiting, there must be no writer
    #   running right now, AND no writers who came before us still waiting to
    #   acquire the lock
    # Additionally, if any read locks have been taken, we must hold all of them
    if held > 0 && @Counter.compare_and_set(1, c+RUNNING_WRITER)
      # If we are the only one reader and successfully swap the RUNNING_WRITER bit on, then we can go ahead
      @HeldCount.value = held + WRITE_LOCK_HELD
      return true
    elsif @Counter.compare_and_set(c, c+WAITING_WRITER)
      while true
        # Now we have successfully incremented, so no more readers will be able to increment
        #   (they will wait instead)
        # However, readers OR writers could decrement right here
        @WriteQueue.synchronize do
          # So we have to do another check inside the synchronized section
          # If a writer OR another reader is running, then go to sleep
          c = @Counter.value
          @WriteQueue.ns_wait if running_writer?(c) || running_readers(c) != held
        end
        # Note: if you are thinking of replacing the above 'synchronize' block
        # with #wait_until, read the comment in #acquire_read_lock first!
        # We just came out of a wait
        # If we successfully turn the RUNNING_WRITER bit on with an atomic swap,
        #   then we are OK to stop waiting and go ahead
        # Otherwise go back and wait again
        c = @Counter.value
        if !running_writer?(c) &&
           running_readers(c) == held &&
           @Counter.compare_and_set(c, c+RUNNING_WRITER-WAITING_WRITER)
          @HeldCount.value = held + WRITE_LOCK_HELD
          return true
        end
      end
    end
  end
end

def initialize
  super()
  @Counter    = AtomicFixnum.new(0)       # single integer which represents lock state
  @ReadQueue  = Synchronization::Lock.new # used to queue waiting readers
  @WriteQueue = Synchronization::Lock.new # used to queue waiting writers
  @HeldCount  = LockLocalVar.new(0) # indicates # of R & W locks held by this thread
end

def max_readers?(c = @Counter.value)
  (c & MAX_READERS) == MAX_READERS
end

def max_writers?(c = @Counter.value)
  (c & MAX_WRITERS) == MAX_WRITERS
end

def release_read_lock
  held = @HeldCount.value = @HeldCount.value - 1
  rlocks_held = held & READ_LOCK_MASK
  if rlocks_held == 0
    c = @Counter.update { |counter| counter - 1 }
    # If one or more writers were waiting, and we were the last reader, wake a writer up
    if waiting_or_running_writer?(c) && running_readers(c) == 0
      @WriteQueue.signal
    end
  elsif rlocks_held == READ_LOCK_MASK
    raise IllegalOperationError, "Cannot release a read lock which is not held"
  end
  true
end

def release_write_lock
  held = @HeldCount.value = @HeldCount.value - WRITE_LOCK_HELD
  wlocks_held = held & WRITE_LOCK_MASK
  if wlocks_held == 0
    c = @Counter.update { |counter| counter - RUNNING_WRITER }
    @ReadQueue.broadcast
    @WriteQueue.signal if waiting_writers(c) > 0
  elsif wlocks_held == WRITE_LOCK_MASK
    raise IllegalOperationError, "Cannot release a write lock which is not held"
  end
  true
end

def running_readers(c = @Counter.value)
  c & MAX_READERS
end

def running_readers?(c = @Counter.value)
  (c & MAX_READERS) > 0
end

def running_writer?(c = @Counter.value)
  c >= RUNNING_WRITER
end

def try_read_lock
  if (held = @HeldCount.value) > 0
    if held & READ_LOCK_MASK == 0
      # If we hold a write lock, but not a read lock...
      @Counter.update { |c| c + 1 }
    end
    @HeldCount.value = held + 1
    return true
  else
    c = @Counter.value
    if !waiting_or_running_writer?(c) && @Counter.compare_and_set(c, c+1)
      @HeldCount.value = held + 1
      return true
    end
  end
  false
end

def try_write_lock
  if (held = @HeldCount.value) >= WRITE_LOCK_HELD
    @HeldCount.value = held + WRITE_LOCK_HELD
    return true
  else
    c = @Counter.value
    if !waiting_or_running_writer?(c) &&
       running_readers(c) == held &&
       @Counter.compare_and_set(c, c+RUNNING_WRITER)
       @HeldCount.value = held + WRITE_LOCK_HELD
      return true
    end
  end
  false
end

def waiting_or_running_writer?(c = @Counter.value)
  c >= WAITING_WRITER
end

def waiting_writers(c = @Counter.value)
  (c & MAX_WRITERS) >> READER_BITS
end

def with_read_lock
  raise ArgumentError.new('no block given') unless block_given?
  acquire_read_lock
  begin
    yield
  ensure
    release_read_lock
  end
end

def with_write_lock
  raise ArgumentError.new('no block given') unless block_given?
  acquire_write_lock
  begin
    yield
  ensure
    release_write_lock
  end
end