DLHashTable2.hpp

/*
   Copyright (C) 2003-2006, 2008 MySQL AB
    All rights reserved. Use is subject to license terms.

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

   This program 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 this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301  USA
*/

#ifndef DL_HASHTABLE2_HPP
#define DL_HASHTABLE2_HPP

#include <ndb_global.h>
#include "ArrayPool.hpp"

template <class T, class U>
class DLHashTable2 {
public:
  DLHashTable2(ArrayPool<U> & thePool);
  ~DLHashTable2();
  
  bool setSize(Uint32 noOfElements);

  bool seize(Ptr<T> &);

  void add(Ptr<T> &);
  
  bool find(Ptr<T> &, const T & key) const;

  void getPtr(Ptr<T> &, Uint32 i) const;

  void getPtr(Ptr<T> &) const;

  T * getPtr(Uint32 i) const;

  void remove(Ptr<T> &, const T & key);

  void remove(Uint32 i);

  void remove(Ptr<T> &);

  void removeAll();
  
  void release(Ptr<T> &, const T & key);

  void release(Uint32 i);

  void release(Ptr<T> &);
  
  class Iterator {
  public:
    Ptr<T> curr;
    Uint32 bucket;
    inline bool isNull() const { return curr.isNull();}
    inline void setNull() { curr.setNull(); }
  };

  void getPtr(Iterator & iter) const ;

  bool first(Iterator & iter) const;
  
  bool next(Iterator & iter) const;

  bool next(Uint32 bucket, Iterator & iter) const;

  inline bool isEmpty() const { Iterator iter; return ! first(iter); }
  
private:
  Uint32 mask;
  Uint32 * hashValues;
  ArrayPool<U> & thePool;
};

template<class T, class U>
inline
DLHashTable2<T, U>::DLHashTable2(ArrayPool<U> & _pool)
  : thePool(_pool)
{
  mask = 0;
  hashValues = 0;
}

template<class T, class U>
inline
DLHashTable2<T, U>::~DLHashTable2(){
  if(hashValues != 0)
    delete [] hashValues;
}

template<class T, class U>
inline
bool
DLHashTable2<T, U>::setSize(Uint32 size){
  Uint32 i = 1;
  while(i < size) i *= 2;

  if(mask == (i - 1)){
    return true;
  }

  if(mask != 0){
    return false;
  }
  
  mask = (i - 1);
  hashValues = new Uint32[i];
  for(Uint32 j = 0; j<i; j++)
    hashValues[j] = RNIL;
  
  return true;
}

template<class T, class U>
inline
void
DLHashTable2<T, U>::add(Ptr<T> & obj){
  const Uint32 hv = obj.p->hashValue() & mask;
  const Uint32 i  = hashValues[hv];
  
  if(i == RNIL){
    hashValues[hv] = obj.i;
    obj.p->nextHash = RNIL;
    obj.p->prevHash = RNIL;
  } else {
    
    T * tmp = (T*)thePool.getPtr(i);    // cast
    tmp->prevHash = obj.i;
    obj.p->nextHash = i;
    obj.p->prevHash = RNIL;
    
    hashValues[hv] = obj.i;
  }
}

template<class T, class U>
inline
bool
DLHashTable2<T, U>::first(Iterator & iter) const {
  Uint32 i = 0;
  while(i <= mask && hashValues[i] == RNIL) i++;
  if(i <= mask){
    iter.bucket = i;
    iter.curr.i = hashValues[i];
    iter.curr.p = (T*)thePool.getPtr(iter.curr.i);      // cast
    return true;
  } else {
    iter.curr.i = RNIL;
  }
  return false;
}

template<class T, class U>
inline
bool
DLHashTable2<T, U>::next(Iterator & iter) const {
  if(iter.curr.p->nextHash == RNIL){
    Uint32 i = iter.bucket + 1;
    while(i <= mask && hashValues[i] == RNIL) i++;
    if(i <= mask){
      iter.bucket = i;
      iter.curr.i = hashValues[i];
      iter.curr.p = (T*)thePool.getPtr(iter.curr.i);    // cast
      return true;
    } else {
      iter.curr.i = RNIL;
      return false;
    }
  }
  
  iter.curr.i = iter.curr.p->nextHash;
  iter.curr.p = (T*)thePool.getPtr(iter.curr.i);        // cast
  return true;
}

template<class T, class U>
inline
void
DLHashTable2<T, U>::remove(Ptr<T> & ptr, const T & key){
  const Uint32 hv = key.hashValue() & mask;  
  
  Uint32 i;
  T * p;
  Ptr<T> prev;
  prev.i = RNIL;

  i = hashValues[hv];
  while(i != RNIL){
    p = (T*)thePool.getPtr(i);  // cast
    if(key.equal(* p)){
      const Uint32 next = p->nextHash;
      if(prev.i == RNIL){
        hashValues[hv] = next;
      } else {
        prev.p->nextHash = next;
      }
      
      if(next != RNIL){
        T * nextP = (T*)thePool.getPtr(next);   // cast
        nextP->prevHash = prev.i;
      }

      ptr.i = i;
      ptr.p = p;
      return;
    }
    prev.p = p;
    prev.i = i;
    i = p->nextHash;
  }
  ptr.i = RNIL;
}

template<class T, class U>
inline
void
DLHashTable2<T, U>::release(Ptr<T> & ptr, const T & key){
  const Uint32 hv = key.hashValue() & mask;  
  
  Uint32 i;
  T * p;
  Ptr<T> prev;
  prev.i = RNIL;

  i = hashValues[hv];
  while(i != RNIL){
    p = (T*)thePool.getPtr(i);  // cast
    if(key.equal(* p)){
      const Uint32 next = p->nextHash;
      if(prev.i == RNIL){
        hashValues[hv] = next;
      } else {
        prev.p->nextHash = next;
      }
      
      if(next != RNIL){
        T * nextP = (T*)thePool.getPtr(next);   // cast
        nextP->prevHash = prev.i;
      }

      p->~T();  // dtor
      thePool.release(i);
      ptr.i = i;
      ptr.p = p;        // invalid
      return;
    }
    prev.p = p;
    prev.i = i;
    i = p->nextHash;
  }
  ptr.i = RNIL;
}

template<class T, class U>
inline
void
DLHashTable2<T, U>::remove(Uint32 i){
  Ptr<T> tmp;
  tmp.i = i;
  tmp.p = (T*)thePool.getPtr(i);        // cast
  remove(tmp);
}

template<class T, class U>
inline
void
DLHashTable2<T, U>::release(Uint32 i){
  Ptr<T> tmp;
  tmp.i = i;
  tmp.p = (T*)thePool.getPtr(i);        // cast
  release(tmp);
}

template<class T, class U>
inline
void 
DLHashTable2<T, U>::remove(Ptr<T> & ptr){
  const Uint32 next = ptr.p->nextHash;
  const Uint32 prev = ptr.p->prevHash;

  if(prev != RNIL){
    T * prevP = (T*)thePool.getPtr(prev);       // cast
    prevP->nextHash = next;
  } else {
    const Uint32 hv = ptr.p->hashValue() & mask;  
    if (hashValues[hv] == ptr.i)
    {
      hashValues[hv] = next;
    }
    else
    {
      // Will add assert in 5.1
    }
  }
  
  if(next != RNIL){
    T * nextP = (T*)thePool.getPtr(next);       // cast
    nextP->prevHash = prev;
  }
}

template<class T, class U>
inline
void 
DLHashTable2<T, U>::release(Ptr<T> & ptr){
  const Uint32 next = ptr.p->nextHash;
  const Uint32 prev = ptr.p->prevHash;

  if(prev != RNIL){
    T * prevP = (T*)thePool.getPtr(prev);       // cast
    prevP->nextHash = next;
  } else {
    const Uint32 hv = ptr.p->hashValue() & mask;  
    if (hashValues[hv] == ptr.i)
    {
      hashValues[hv] = next;
    }
    else
    {
      // Will add assert in 5.1
    }
  }
  
  if(next != RNIL){
    T * nextP = (T*)thePool.getPtr(next);       // cast
    nextP->prevHash = prev;
  }
  
  thePool.release(ptr.i);
}

template<class T, class U>
inline
void 
DLHashTable2<T, U>::removeAll(){
  for(Uint32 i = 0; i<=mask; i++)
    hashValues[i] = RNIL;
}

template<class T, class U>
inline
bool
DLHashTable2<T, U>::next(Uint32 bucket, Iterator & iter) const {
  while (bucket <= mask && hashValues[bucket] == RNIL) 
    bucket++; 
  
  if (bucket > mask) {
    iter.bucket = bucket;
    iter.curr.i = RNIL;
    return false;
  }
  
  iter.bucket = bucket;
  iter.curr.i = hashValues[bucket];
  iter.curr.p = (T*)thePool.getPtr(iter.curr.i);        // cast
  return true;
}

template<class T, class U>
inline
bool
DLHashTable2<T, U>::seize(Ptr<T> & ptr){
  Ptr<U> ptr2;
  thePool.seize(ptr2);
  ptr.i = ptr2.i;
  ptr.p = (T*)ptr2.p;   // cast
  if (ptr.p != NULL){
    ptr.p->nextHash = RNIL;
    ptr.p->prevHash = RNIL;
    new (ptr.p) T;      // ctor
  }
  return !ptr.isNull();
}

template<class T, class U>
inline
void
DLHashTable2<T, U>::getPtr(Ptr<T> & ptr, Uint32 i) const {
  ptr.i = i;
  ptr.p = (T*)thePool.getPtr(i);        // cast
}

template<class T, class U>
inline
void
DLHashTable2<T, U>::getPtr(Ptr<T> & ptr) const {
  Ptr<U> ptr2;
  thePool.getPtr(ptr2);
  ptr.i = ptr2.i;
  ptr.p = (T*)ptr2.p;   // cast
}

template<class T, class U>
inline
T * 
DLHashTable2<T, U>::getPtr(Uint32 i) const {
  return (T*)thePool.getPtr(i); // cast
}

template<class T, class U>
inline
bool
DLHashTable2<T, U>::find(Ptr<T> & ptr, const T & key) const {
  const Uint32 hv = key.hashValue() & mask;  
  
  Uint32 i;
  T * p;

  i = hashValues[hv];
  while(i != RNIL){
    p = (T*)thePool.getPtr(i);  // cast
    if(key.equal(* p)){
      ptr.i = i;
      ptr.p = p;
      return true;
    }
    i = p->nextHash;
  }
  ptr.i = RNIL;
  ptr.p = NULL;
  return false;
}
#endif