hash_table.h

Go to the documentation of this file.

#ifndef HASH_TABLE_CLASS
#define HASH_TABLE_CLASS

/*****************************************************************************\
*                                                                             *
*  Name   : hash_table                                                        *
*  Author : Chris Koeritz                                                     *
*                                                                             *
*******************************************************************************
* Copyright (c) 2001-$now By Author.  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.  This is online at:      *
*     http://www.fsf.org/copyleft/gpl.html                                    *
* Please send any updates to: fred@gruntose.com                               *
\*****************************************************************************/

#include "data_structure_dll.h"

#include <basis/object_base.h>

// forward.
template <class key, class contents> class internal_hash_array;


class DATA_STRUCTURE_CLASS_STYLE hashing_algorithm : public virtual object_base
{
public:
  virtual ~hashing_algorithm() {}  

  IMPLEMENT_CLASS_NAME("hashing_algorithm");

  virtual u_int hash(const void *key_data, int key_length) const = 0;

  virtual hashing_algorithm *clone() const = 0;
};



template <class key_type, class contents>
  // the key_type must support valid copy constructor, assignment operator and
  // equality operators.  the contents need not support any special operations;
  // it is always considered as just a pointer.
class hash_table
{
public:
  hash_table(const hashing_algorithm &hasher, int max_table_bits);

  ~hash_table();

  static const char *class_name() { return "hash_table"; }

  int max_bits() const { return _max_bits; }

  void rehash(int max_bits);

  enum outcomes {
    IS_NEW = common::IS_NEW,
    EXISTING = common::EXISTING
  };

  int elements() const;

  outcome add(const key_type &key, contents *to_store);

  outcome fast_dangerous_add(const key_type &key, contents *to_store);

  bool find(const key_type &key, contents * &item_found) const;

  inline contents *find(const key_type &key) const
          { contents *c = NIL; return find(key, c)? c : NIL; }

  contents *acquire(const key_type &key);

  bool zap(const key_type &key);

  void reset();

  typedef bool apply_function(const key_type &key, contents &current,
          void *data_link);

  void apply(apply_function *to_apply, void *data_link);

  outcome add(key_type *key, contents *to_store, bool check_dupes = true);

  bool verify() const;

private:
  int _max_bits;  
  hashing_algorithm *_hasher;  
  internal_hash_array<key_type, contents> *_table;  
  int _last_iter;

  hash_table(const hash_table &to_copy);
  hash_table &operator =(const hash_table &to_copy);

public:
  internal_hash_array<key_type, contents> &table_access() const;
};



template <class key_type, class contents>
void copy_hash_table(hash_table<key_type, contents> &target,
    const hash_table<key_type, contents> &source);

#endif

---