enum locktype {
  sharelock,            //read-only
  updatelock,           //upgradable shared lock
  updateexlock,         //updatelock waiting to upgrade to exclusivelock
  exclusivelock         //exclusive
};

class LockManager {
public:
  struct LockRegistration;
  struct Lock;
  typedef Lock *LockId;
  
  LockId RequestLock(LockEntity e, locktype lt);
  int ChangeLock(LockId li, locktype lt);
  void ReleaseLock(LockId li);
private:
  struct LockRegistration : IDblLinkList::IDblLink {
    LockEntity e;
    IDblLinkList<Lock> lock;         //active lock(s)
    IDblLinkList<Lock> q_Lock;       //queued lock(s)
  };
  struct Lock : IDblLinkList::IDblLink {
    LockId            li;
    LockType          lt;
    LockRegistration *lr;
    FEventSemaphore   *granted;
    LockEntity        e;
  };
  IDblLinkList<LockRegistration> a_lockreg[37];
  FMutex a_lockregmtx[37];
  static int iscompatible(DblLinkList<Lock>& l, locktype lt);
};


LockManager::LockId LockManager::RequestLock(LockEntity e, locktype lt)
{
        //build lock
        Lock *lock = new lock;
        lock->li = (LockId)lock;
        lock->lt = lt;
        lock->lr = 0;
        lock->granted = 0;
        lock->e = e;
        
        unsigned e_hash = hash(lock->e);
        
        a_lockregmtx[e_hash%37].Request();
        LockRegistration *lr = a_lockreg[e_hash%37].head();
        while(lr && lr->e != e)
                lr = lr->next;
        if(!lr) {
                //new entity
                lr = new LockRegistration;
                lr->e = e;
                lr->lock.append(lock);
                lock->lr = lr;
                a_lockreg.append(lr);
                a_lockregmtx[e_hash%37].Release();
                return lock->li;
        } 
        
        //lock on an entity exists
        if(!lr->q_lock.empty ||
           !iscompatible(lr->lock,lock->lt))
        {   
                //queue lock
                lr->q_lock.append(lock);
                FEventSemaphore g;
                lock->granted = &g;
                a_lockregmtx[e_hash%37].Release();
                g.Wait();
        } else {
                //grant lock
                lr->lock.append(lock);
                a_lockregmtx[e_hash%37].Release();
        }
        return lock->li;
}

void LockManager::ReleaseLock(LockId li) {
        Lock *lock=(Lock*)li;
        LockRegistration = li->lr;

        unsigned e_hash = hash(lock->e);
        a_lockregmtx[e_hash%37].Request();

        //remove from lr->lock chain
        lr->lock.remove(lock);
        
        if(lr->lock.empty() && lr->q_lock.empty()) {
                //remove lockreg
                a_lockreg.remove(lr);
                a_lockregmtx[e_hash%37].Release();
                return;
        }
        
        if(lr->lock.card()==1) {
                Lock *lock=lr->lock.head();
                if(lock->lt==updateexlock) {
                        //upgrade updateex to exclusive
                        lock->lt=exclusivelock;
                        lock->granted->Signal();
                        a_lockregmtx[e_hash%37].Release();
                        return;
                }        
        }
        
        while(!lr->q_lock.empty() &&
              iscompatible(lr->lock,lr->q_lock.head()->lt))
        {      
                Lock *lock=lr->q_lock.head();
                lr->q_lock.remove(lock);
                lr->lock.append(lock);
                lock->granted.Signal();
        }        
        a_lockregmtx[e_hash%37].Relase();
        return;
}

void LockManager::ChangeLock(LockId li, locktype lt) {
        Lock *lock=(Lock*)li;
        LockRegistration = li->lr;
        if(lock->lt==lt) return;
        //if(lock->lt==sharedlock) return -1;
        
        unsigned e_hash = hash(lock->e);
        a_lockregmtx[e_hash%37].Request();
        if(lock->lt==exclusivelock) {
                //Downgrading exclusive->shared/update
                //change lock type
                lock->lt = lt;
                //grant shared locks
                while(!lr->q_lock.empty() &&
                      iscompatible(lr->lock,lr->q_lock.head()->lt))
                {
                        Lock *lock=lr->q_lock.head();
                        lr->q_lock.remove(lock);
                        lr->lock.append(lock);
                        lock->granted.Signal();
                }        
                a_lockregmtx[e_hash%37].Release();
        } else {
                //Upgrading update->exclusive
                if(lr->lock.card()==1) {
                        //one and only lock
                        lock->lt = exclusivelock;
                        a_lockregmtx[e_hash%37].Release();
                } else {
                        //if(!canshare(lr->lock)) deadlock!;
                        lock->lt = updateexlock;
                        FEventSemaphore g;
                        lock->granted=&g;
                        a_lockregmtx[e_hash%37].Release();
                        g.Wait();
                }
        }
}

#define _ 0
static int lockcompatibility[4][4] = {
        { 1,1,_,0 }, //shared   * {shared,update,exclusive}
        { 1,0,_,0 }, //update   * {shared,update,exclusive}
        { 0,0,_,0 }, //updateex * {shared,update,exclusive}
        { 0,0,_,0 }  //exclusive* {shared,update,exclusive}
};
#undef _

int LockManager::iscompatible(DblLinkList<Lock>& l, locktype lt) {
        for(Lock *lock=l.head(); lock; lock=lock->next) {
                if(!lockcompatibility[lock->lt][lt])
                        return 0;
        }
        return 1;
}

LockSet:
  RequestLock(LockEntity e, locktype lt);
  ChangeLock(LockEntity e, locktype lt);
  ReleaseLock(LockEntity e);