---

hashtable.h

Go to the documentation of this file.

/***************************************************************************
    hashtable.h  -  Definition of template class HashTable.
                             -------------------
    begin                : June 21 2002
    copyright            : (C) 2003 by Vojtìch Toman
    email                : vtoman@lit.cz
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   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; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/

#ifndef HASHTABLE_H
# define HASHTABLE_H


#include <cstring>      //for strcmp()

#include "defs.h"
#include "collection.h"
#include "debug.h"
#include "xmldefs.h"
#include "xmlchar.h"





static inline unsigned long hashXmlString(const XmlChar *s)
{
  unsigned long h = 0; 

  for ( ; *s; ++s)
    h = 5 * h + *s;
  
  return h;
}



template<unsigned long size_> struct HashTableHash
{
  //unsigned long operator()(XmlChar *s) const { return hashXmlString_(s) % size_; }

  unsigned long operator()(const XmlChar *s) const { return hashXmlString(s) % size_; }

  unsigned long operator()(char x) const { return x % size_; }

  unsigned long operator()(unsigned char x) const { return x % size_; }

  //unsigned long operator()(short x) const { return x % size_; }

  //unsigned long operator()(unsigned short x) const { return x % size_; }

  unsigned long operator()(int x) const { return x % size_; }

  unsigned long operator()(unsigned int x) const { return x % size_; }

  unsigned long operator()(long x) const { return x % size_; }

  unsigned long operator()(unsigned long x) const { return x % size_; }
};





struct HashTableComparator
{
  bool compare(XmlChar x, XmlChar y) { return x == y; }

  bool compare(unsigned char x, unsigned char y) { return x == y; }
  //bool compare(short x, short y) { return x == y; }
  //bool compare(unsigned short x, unsigned short y) { return x == y; }

  bool compare(int x, int y) { return x == y; }

  bool compare(unsigned int x, unsigned int y) { return x == y; }

  bool compare(long x, long y) { return x == y; }

  bool compare(unsigned long x, unsigned long y) { return x == y; }

  bool compare(XmlChar *x, XmlChar *y) { return !xmlchar_strcmp(x, y); }
};



template<class Key_, class T_> struct HashTableItem
{
  Key_ key_;

  T_ *data_;
};



template<class Key_, class T_, template<class T_>
 class HashTableBucketContainer_> class HashTableBucket
#ifndef DOXYGEN_SHOULD_SKIP_THIS
   : public HashTableBucketContainer_< HashTableItem<Key_, T_> >
#endif //DOXYGEN_SHOULD_SKIP_THIS
{
public:
  HashTableComparator comparator_;

  virtual void insertItem(HashTableItem<Key_, T_> *item)
  {
    prepend(item);
  }


  virtual T_ *find(Key_ key)
  {
    HashTableItem<Key_, T_> *pom;

    for (pom = first(); pom; pom = next())
      {
        if (comparator_.compare(pom->key_, key))
          return pom->data_;
      }
    
    return 0;
  }



  virtual bool removeItem(Key_ key)
  {
    HashTableItem<Key_, T_> *pom;

    pom = first();

    while (pom)
      {
        if (comparator_.compare(pom->key_, key))
          {
            if (autoDelete_)
              //if neccessary, delete the contents of found item
              DELETE(pom->data_);
            
            //delete the item
            return remove();
          }

        pom = next();
      }
    
    return false;
  }
};



template<class Key_, class T_, template<class T_> class HashTableBucketContainer_, unsigned long size_> class HashTable : public Collection<T_>
{
public:

  HashTable(void) : Collection<T_>()
  {
    NEW(table_, (HashTableBucket<Key_, T_, HashTableBucketContainer_> *[size_]));

    for (unsigned long i = 0; i < size_; i++)
      table_[i] = 0;
  }

  virtual ~HashTable(void)
  {
    clear();
    DELETE_ARRAY(table_);
  }


  virtual T_ *find(Key_ key)
  {
    unsigned long pos = hash_(key);

    if (!table_[pos])
      return 0;
    else
      return table_[pos]->find(key);
  }


  virtual void insert(Key_ key, T_ *item)
  {
    unsigned long pos = hash_(key);

    if (!table_[pos])
      {
        NEW(table_[pos], (HashTableBucket<Key_, T_, HashTableBucketContainer_>));
      }

    if (!contains(key))
      {
        HashTableItem<Key_, T_> *tableItem;

        NEW(tableItem, (HashTableItem<Key_, T_>));
        
        tableItem->key_ = key;
        tableItem->data_ = item;
        table_[pos]->insertItem(tableItem);
        cnt_++;
      }
  }


  virtual bool remove(Key_ key)
  {
    unsigned long pos = hash_(key);

    if (!table_[pos])
      return false;
    else
      {
        if (table_[pos]->removeItem(key))
          {
            cnt_--;
            return true;
          }
        else
          return false;
      }
  }


  virtual bool contains(Key_ key)
  {
    unsigned long pos = hash_(key);

    if (!table_[pos])
      return false;
    else
      return (table_[pos]->find(key) != 0);
  }


  virtual void clear(void)
  {
    for (unsigned long i = 0; i < size_; i++)
      {
        if (autoDelete_)
          {
            if (table_[i])
              {
                //HashTableItem<Key_, T_> *pom;

                //for (pom = table_[i]->first(); pom; pom = table_[i]->next())
                //  DELETE(pom->data_);
              }
          }

        if (table_[i])
          {
            DELETE(table_[i]);
            //      table_[i] = 0;
          }
      }
  }

  
  virtual void setAutoDelete(bool ad)
  {
    for (unsigned long i = 0; i < size_; i++)
      {
        if (table_[i])
          table_[i]->setAutoDelete(ad);
      }

    autoDelete_ = ad;
  }

protected:
  HashTableBucket<Key_, T_, HashTableBucketContainer_> **table_;

  HashTableHash<size_> hash_;
};

#endif //HASHTABLE_H

---