hash_table.cpp

Go to the documentation of this file.

#ifndef HASH_TABLE_IMPLEMENTATION
#define HASH_TABLE_IMPLEMENTATION

/*****************************************************************************\
*                                                                             *
*  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 "amorph.cpp"
#include "hash_table.h"

#include <basis/byte_array.h>
#include <basis/array.cpp>
#include <basis/function.h>
#include <basis/log_base.h>
#include <mathematics/math_ops.h>

#include <math.h>


// this is a very special micro-managed class.  it holds two pointers which
// it neither creates nor destroys.  thus all interaction with it must be
// careful about removing these objects at the appropriate time.  we don't
// want automatic memory management since we want a cheap copy on the items
// in the buckets.

template <class key_type, class contents>
class hash_wrapper
{
public:
  key_type *_id;
  contents *_data;

  hash_wrapper(key_type *id = NIL, contents *data = NIL)
      : _id(id), _data(data) {}
};


template <class key_type, class contents>
class bucket : public array<hash_wrapper<key_type, contents> >
{
public:
  bucket() : array<hash_wrapper<key_type, contents> >(0, NIL,
      byte_array::SIMPLE_COPY | byte_array::EXPONE
      | byte_array::FLUSH_INVISIBLE) {}

  int find(const key_type &to_find) {
    for (int i = 0; i < this->length(); i++) {
      key_type *curr_key = this->get(i)._id;
//hmmm: if curr key is not set, is that a logic error?  it seems like we
//      are seeing the potential for this.
      if (curr_key && (to_find == *curr_key))
        return i;
    }
    return common::NOT_FOUND;
  }
};


template <class key_type, class contents>
class internal_hash_array : public amorph<bucket<key_type, contents> >
{
public:
  internal_hash_array(u_int max_bits)
      : amorph<bucket<key_type, contents> >(math_ops::pow_2(max_bits)) {}
};


#define static_class_name() "hash_table"

template <class key_type, class contents>
hash_table<key_type, contents>::hash_table(const hashing_algorithm &hasher,
    int max_table_bits)
: _max_bits((max_table_bits > 0)? max_table_bits : 1),
  _hasher(hasher.clone()),
  _table(new internal_hash_array<key_type, contents>(max_table_bits)),
  _last_iter(0)
{}

template <class key_type, class contents>
hash_table<key_type, contents>::~hash_table()
{
  FUNCDEF("destructor");
#ifdef EXTREME_CHECKING
  if (!verify()) deadly_error(class_name(), func, "state did not verify.");
#endif
  reset();
  WHACK(_table);
  WHACK(_hasher);
}

// the specialized copy operation.
template <class key_type, class contents>
void copy_hash_table(hash_table<key_type, contents> &target,
    const hash_table<key_type, contents> &source)
{
  #define class_name() "hash_table"
  FUNCDEF("copy_hash_table");
#ifdef EXTREME_CHECKING
  if (!source.verify())
    deadly_error(class_name(), func, "source state did not verify.");
#endif
  target.reset();
  for (int i = 0; i < source.table_access().elements(); i++) {
    bucket<key_type, contents> *buck = source.table_access().borrow(i);
    if (!buck) continue;
    for (int j = 0; j < buck->length(); j++) {
      target.add(*((*buck)[j]._id), new contents(*((*buck)[j]._data)));
    }
  }
#ifdef EXTREME_CHECKING
  if (!target.verify())
    deadly_error(class_name(), func, "target state did not verify.");
#endif
  #undef class_name
}

template <class key_type, class contents>
void hash_table<key_type, contents>::reset()
{
  FUNCDEF("reset");
#ifdef EXTREME_CHECKING
  if (!verify()) deadly_error(class_name(), func, "state did not verify.");
#endif
  // iterate over the list whacking the content items in the buckets.
  for (int i = 0; i < _table->elements(); i++) {
    bucket<key_type, contents> *buck = _table->acquire(i);
    if (!buck) continue;
    for (int j = 0; j < buck->length(); j++) {
      WHACK((*buck)[j]._data);  // eliminate the stored data.
      WHACK((*buck)[j]._id);  // eliminate the stored key.
      buck->zap(j, j);  // remove the element.
      j--;  // skip back before whack happened.
    }
    WHACK(buck);
  }
#ifdef EXTREME_CHECKING
  if (!verify())
    deadly_error(class_name(), func, "state did not verify afterwards.");
#endif
}

template <class key_type, class contents>
bool hash_table<key_type, contents>::verify() const
{
  for (int i = 0; i < _table->elements(); i++) {
    const bucket<key_type, contents> *buck = _table->borrow(i);
    if (!buck) continue;  // that's acceptable.
    for (int j = 0; j < buck->length(); j++) {
      const hash_wrapper<key_type, contents> &wrap = (*buck)[j];
      if (!wrap._data) {
//        program_wide_logger().log(isprintf("hash table: no data segment at position %d.", j));
        return false;
      }
      if (!wrap._id) {
//        program_wide_logger().log(isprintf("hash table: no identifier at position %d.", j));
        return false;
      }
    }
  }
  return true;
}

template <class key_type, class contents>
internal_hash_array<key_type, contents> &hash_table<key_type, contents>
    ::table_access() const
{ return *_table; }

template <class key_type, class contents>
void hash_table<key_type, contents>::rehash(int max_bits)
{
  FUNCDEF("rehash");
#ifdef EXTREME_CHECKING
  if (!verify()) deadly_error(class_name(), func, "state did not verify.");
#endif
  typedef bucket<key_type, contents> buckie;
  hash_table<key_type, contents> new_hash(*_hasher, max_bits);
    // this is the new table that will be used.

  // scoot through the existing table so we can move items into the new one.
  for (int i = 0; i < _table->elements(); i++) {
    buckie *b = _table->borrow(i);  // look at the current element.
    if (!b) continue;  // nothing here, keep going.
    for (int j = b->length() - 1; j >= 0; j--) {
      key_type *k = b->use(j)._id;
      contents *c = b->use(j)._data;
      new_hash.add(k, c);
    }
    b->reset();
      // clean out any items in the buckets here now that they've moved.
  }

  // now flip the contents of the new guy into "this".
  _table->reset();  // toss previous stuff.
  _table->adjust(new_hash._table->elements());
  for (int q = 0; q < new_hash._table->elements(); q++)
    _table->put(q, new_hash._table->acquire(q));
  // reset other data members.
  _max_bits = new_hash._max_bits;
  _last_iter = 0;
#ifdef EXTREME_CHECKING
  if (!verify())
    deadly_error(class_name(), func, "state did not verify afterwards.");
#endif
}

template <class key_type, class contents>
outcome hash_table<key_type, contents>::add(const key_type &key,
    contents *to_store)
{ return add(new key_type(key), to_store); }

template <class key_type, class contents>
outcome hash_table<key_type, contents>::add(key_type *key,
    contents *to_store, bool check_dupes)
{
  FUNCDEF("add");
#ifdef EXTREME_CHECKING
  if (!verify()) deadly_error(class_name(), func, "state did not verify.");
#endif
  // get a hash value.
  u_int hashed = _hasher->hash((const void *)key, sizeof(key_type));
  // make the value appropriate for our table.
  hashed = hashed % _table->elements();
  // see if the key already exists there.
  bucket<key_type, contents> *buck = _table->borrow(hashed);
  if (!buck) {
    // this slot doesn't exist yet.
    buck = new bucket<key_type, contents>;
    _table->put(hashed, buck);
  }
  if (!check_dupes) {
    // we aren't even going to check for its existence.
    *buck += hash_wrapper<key_type, contents>(key, to_store);
    return IS_NEW;
  }
  int indy = buck->find(*key);
  if (negative(indy)) {
    // that value was not seen yet, so we're adding a new entry.
    *buck += hash_wrapper<key_type, contents>(key, to_store);
#ifdef EXTREME_CHECKING
    if (!verify())
      deadly_error(class_name(), func, "state did not verify afterwards.");
#endif
    return IS_NEW;
  }
  // that key already existed, so we'll re-use its slot with the new data.
  WHACK((*buck)[indy]._data);
  WHACK(key);  // toss since we're not using.
  (*buck)[indy]._data = to_store;
#ifdef EXTREME_CHECKING
  if (!verify())
    deadly_error(class_name(), func, "state did not verify afterwards.");
#endif
  return EXISTING;
}

template <class key_type, class contents>
outcome hash_table<key_type, contents>::fast_dangerous_add
    (const key_type &key, contents *to_store)
{ return add(new key_type(key), to_store, false); }

template <class key_type, class contents>
bool hash_table<key_type, contents>::find(const key_type &key,
    contents * &item_found) const
{
  FUNCDEF("find");
#ifdef EXTREME_CHECKING
  if (!verify()) deadly_error(class_name(), func, "state did not verify.");
#endif
  item_found = NIL;
  // get a hash value.
  u_int hashed = _hasher->hash((const void *)&key, sizeof(key));
  // make the value appropriate for our table.
  hashed = hashed % _table->elements();
  // see if the key exists in the bucket.
  bucket<key_type, contents> *buck = _table->borrow(hashed);
  if (!buck) return false;
  int indy = buck->find(key);
  if (negative(indy)) return false;  // not there.
  // was there, so retrieve the data.
  item_found = (*buck)[indy]._data;
  return true;
}

template <class key_type, class contents>
contents *hash_table<key_type, contents>::acquire(const key_type &key)
{
  FUNCDEF("acquire");
#ifdef EXTREME_CHECKING
  if (!verify()) deadly_error(class_name(), func, "state did not verify.");
#endif
  // get a hash value.
  u_int hashed = _hasher->hash((const void *)&key, sizeof(key));
  // make the value appropriate for our table.
  hashed = hashed % _table->elements();
  // see if the key exists in the bucket.
  bucket<key_type, contents> *buck = _table->borrow(hashed);
  if (!buck) return NIL;
  int indy = buck->find(key);
  if (negative(indy)) return NIL;  // nope, not there.
  contents *to_return = (*buck)[indy]._data;
  WHACK((*buck)[indy]._id);  // clean the id.
  buck->zap(indy, indy);  // toss the storage blob for the item.
#ifdef EXTREME_CHECKING
  if (!verify())
    deadly_error(class_name(), func, "state did not verify afterwards.");
#endif
  return to_return;
}

template <class key_type, class contents>
bool hash_table<key_type, contents>::zap(const key_type &key)
{
  FUNCDEF("zap");
#ifdef EXTREME_CHECKING
  if (!verify()) deadly_error(class_name(), func, "state did not verify.");
#endif
  // get a hash value.
  u_int hashed = _hasher->hash((const void *)&key, sizeof(key));
  // make the value appropriate for our table.
  hashed = hashed % _table->elements();
  // see if the key exists in the bucket.
  bucket<key_type, contents> *buck = _table->borrow(hashed);
  if (!buck) return false;
  int indy = buck->find(key);
  if (negative(indy)) {
    // nope, not there.
    return false;
  }
  WHACK((*buck)[indy]._data);  // delete the data held.
  WHACK((*buck)[indy]._id);  // delete the data held.
  buck->zap(indy, indy);  // toss the storage blob for the item.
  if (!buck->length()) {
    // clean up this bucket now.
    buck = _table->acquire(hashed);
    WHACK(buck);
  }
#ifdef EXTREME_CHECKING
  if (!verify())
    deadly_error(class_name(), func, "state did not verify afterwards.");
#endif
  return true;
}

template <class key_type, class contents>
void hash_table<key_type, contents>::apply(apply_function *to_apply,
    void *data_link)
{
  FUNCDEF("apply");
#ifdef EXTREME_CHECKING
  if (!verify()) deadly_error(class_name(), func, "state did not verify.");
#endif
  typedef bucket<key_type, contents> buckie;
  int bucks_seen = 0;
  int posn = _last_iter;  // start at the same place we left.
  while (bucks_seen++ < _table->elements()) {
    if ( (posn < 0) || (posn >= _table->elements()) )
      posn = 0;
    buckie *b = _table->borrow(posn);
    _last_iter = posn++;
      // record where the iteration last touched and increment next position.
      // we must do this before we check if the bucket exists or we'll rotate
      // on this same place forever.
    if (!b) continue;  // nothing here, keep going.
    for (int j = 0; j < b->length(); j++) {
      contents *c = b->use(j)._data;
      if (!c) {
#ifdef EXTREME_CHECKING
        deadly_error("hash_table", "apply", "logic error--missing pointer");
#endif
        continue;
      }
      if (!to_apply(*b->use(j)._id, *c, data_link)) return;
    }
  }
}

template <class key_type, class contents>
int hash_table<key_type, contents>::elements() const
{
  FUNCDEF("elements");
#ifdef EXTREME_CHECKING
  if (!verify()) deadly_error(class_name(), func, "state did not verify.");
#endif
  typedef bucket<key_type, contents> buckie;
  int to_return = 0;
  for (int i = 0; i < _table->elements(); i++) {
    bucket<key_type, contents> *buck = _table->borrow(i);
    if (!buck) continue;  // nothing to count.
    to_return += buck->length();
  }
  return to_return;
}

#undef static_class_name

#endif // outer guard.

---