hash.h

Go to the documentation of this file.

// See the end of this file for license information.

#ifndef TORSION_HASH_H
#define TORSION_HASH_H

#include "asm.h"
#include "list.h"
#include "array.h"
#include "types.h"
#include "screen.h"

template <class Key>
struct hash { };

inline unsigned
hash_string(const char* str) {
  unsigned long hash_value = 0;
  for ( ; *str; ++str)
    hash_value = 5 * hash_value + *str;
                                                                                
  return unsigned(hash_value);
}

inline unsigned
hash_data(const char* data, Size length) {
  unsigned long hash_value = 0;
  for (unsigned i = 0; i < length; ++i, ++data)
    hash_value = 5 * hash_value + *data;
                                                                                
  return unsigned(hash_value);
}

template<>
struct hash<char*> {
  unsigned
  operator()(const char* str) const {
    return hash_string(str);
  }
};

template<>
struct hash<const char*> {
  unsigned
  operator()(const char* str) const {
    return hash_string(str);
  }
};

template<>
struct hash<void*> {
  unsigned
  operator()(const void* data) const {
    return hash_data((char*)&data, sizeof(void*));
  }
};

template <class Key>
struct compare { };

template<>
struct compare<char*> {
  int
  operator()(const char* str1, const char* str2, Size size) const {
    return strncmp(str1, str2, size);
  }
};

template<>
struct compare<const char*> {
  int
  operator()(const char* str1, const char* str2, Size size) const {
    return strncmp(str1, str2, size);
  }
};

template<>
struct compare<void*> {
  int
  operator()(void* ptr1, void* ptr2, Size size) const {
    if (ptr1 > ptr2)
      return 1;
    if (ptr1 < ptr2)
      return -1;
    return 0;
  }
};

template <class Key, class Value>
class Hash_node : public List_node {
public:
  Key key;
  Value value;
};


// forward declaration of death
template <class Key, class Value, class Hash_func = hash<Key>,
          class Compare_func = compare<Key> >
class Hash_table;

template <class Key, class Value>
class Hash_iterator {
public:
  Hash_table<Key, Value>* hash_table; 
  unsigned bucket_index;    

  List_iterator< Hash_node<Key, Value> > position;

  Hash_iterator&
  operator++();       // prefix ++

  Hash_iterator&
  operator--();       // prefix --

  Hash_iterator&
  operator++(int);      // postfix ++

  Hash_iterator&
  operator--(int);      // postfix --

  Hash_node<Key, Value>&
  operator*() const;

  Hash_node<Key, Value>*
  operator->() const;

  bool
  operator==(const Hash_iterator& iterator) const;

  bool
  operator!=(const Hash_iterator& iterator) const;
};

template <class Key, class Value>
inline Hash_iterator<Key, Value>&
Hash_iterator<Key, Value>::operator++() {
  // iterate to the next element in the current bucket
  ++position;

  // if we've reached the end of the current bucket, move to the start of the
  // next non-empty bucket
  while (position == hash_table->buckets[bucket_index].end()) {
    ++bucket_index;
    position = hash_table->buckets[bucket_index].begin();
    
    // at the very last bucket, stop looking for non-empty buckets
    if (bucket_index == hash_table->buckets.size() - 1)
      break;
  }

  return *this;
}

template <class Key, class Value>
inline Hash_iterator<Key, Value>&
Hash_iterator<Key, Value>::operator--() {
  // iterate to the previous element in the current bucket
  --position;

  // if we're at the start of the current bucket, move to end of the previous
  // non-empty bucket
  while (position == hash_table->buckets[bucket_index].begin()) {
    --bucket_index;
    position = --(hash_table->buckets[bucket_index].end());
    
    // at the very first bucket, stop looking for non-empty buckets
    if (bucket_index == 0)
      break;
  }

  return *this;
}

template <class Key, class Value>
inline Hash_iterator<Key, Value>&
Hash_iterator<Key, Value>::operator++(int) {
  return ++this;
}

template <class Key, class Value>
inline Hash_iterator<Key, Value>&
Hash_iterator<Key, Value>::operator--(int) {
  return --this;
}

template <class Key, class Value>
inline Hash_node<Key, Value>&
Hash_iterator<Key, Value>::operator*() const {
  return *(Hash_node<Key, Value>*)position.node;
}

template <class Key, class Value>
inline Hash_node<Key, Value>*
Hash_iterator<Key, Value>::operator->() const {
  return (Hash_node<Key, Value>*)position.node;
}

template <class Key, class Value>
inline bool
Hash_iterator<Key, Value>::operator==(const Hash_iterator& iterator) const {
  return (position == position.position);
}

template <class Key, class Value>
inline bool
Hash_iterator<Key, Value>::operator!=(const Hash_iterator& iterator) const {
  return (position != iterator.position);
}

template <class Key, class Value, class Hash_func, class Compare_func >
class Hash_table {
protected:
  Hash_func hash_func;      
  Compare_func compare_func;    
  static const Size MAX_KEY_SIZE = 1024;
  bool physical_memory;     
  bool alloc_nodes;     
  bool physical;

  inline unsigned
  get_bucket_index(Key key) {
    return hash_func(key) % buckets.get_capacity();
  }

  List_iterator< Hash_node<Key, Value> >
  find(unsigned bucket_index, Key key);

public:
  Array< List< Hash_node<Key, Value> > > buckets;
  typedef Hash_iterator<Key, Value> Iterator;

  Hash_table(bool physical = false, Size init_buckets = 0,
             bool alloc_nodes = false) {
    init(physical, init_buckets);
  }

  void
  init(bool physical = false, Size init_buckets = 0,
       bool alloc_nodes = false) {
    this->physical = physical;
    this->alloc_nodes = alloc_nodes;
    buckets.init(physical, init_buckets);
    buckets.grow(true);

    for (unsigned i = 0; i < buckets.get_capacity(); ++i)
      buckets[i].clear();
  }

  inline void
  clear() {
    for (unsigned i = 0; i < buckets.get_capacity(); ++i)
      buckets[i].clear();
    
    buckets.clear();
  }

  void
  free_and_clear();

  bool
  has_key(Key key);

  Value*
  get(Key key);

  void
  insert(Hash_node<Key, Value>& node);

  bool
  remove(Key key);

  // TODO
  bool
  grow() { return false; }

  Iterator
  begin();

  Iterator
  end();

  void
  print();

  void
  unit_test();
};

template <class Key, class Value, class Hash_func, class Compare_func>
List_iterator< Hash_node<Key, Value> >
Hash_table<Key, Value, Hash_func, Compare_func>::find(unsigned bucket_index, Key key) {
  // search for the key within the contents of the bucket
  for (List_iterator< Hash_node<Key, Value> > position = buckets[bucket_index].begin();
       position != buckets[bucket_index].end(); ++position) {
    // if the key is found, return its position in the bucket contents
    if (compare_func(position->key, key, MAX_KEY_SIZE) == 0)
      return position;
  }
  
  return buckets[bucket_index].end();
}

template <class Key, class Value, class Hash_func, class Compare_func>
void
Hash_table<Key, Value, Hash_func, Compare_func>::free_and_clear() {
  // free the hash nodes within each bucket's list
  for (unsigned i = 0; i < buckets.size(); ++i)
    buckets[i].free_and_clear();

  // clear all the buckets out of this hash table
  buckets.clear();
}

template <class Key, class Value, class Hash_func, class Compare_func>
bool
Hash_table<Key, Value, Hash_func, Compare_func>::has_key(Key key) {
  // if the key exists in the corresponding bucket, return true
  unsigned bucket_index = get_bucket_index(key);
  List_iterator< Hash_node<Key, Value> > position = find(bucket_index, key);

  if (position == buckets[bucket_index].end())
    return false;

  return true;
}

template <class Key, class Value, class Hash_func, class Compare_func>
Value*
Hash_table<Key, Value, Hash_func, Compare_func>::get(Key key) {
  // if the key exists in the corresponding bucket, return true
  unsigned bucket_index = get_bucket_index(key);
  List_iterator< Hash_node<Key, Value> > position = find(bucket_index, key);

  if (position == buckets[bucket_index].end())
    return NULL;

  return &position->value;
}


template <class Key, class Value, class Hash_func, class Compare_func>
void
Hash_table<Key, Value, Hash_func, Compare_func>::insert(Hash_node<Key, Value>& node) {
  // if the key exists in the corresponding bucket, replace it with the new
  // value. otherwise, insert the key/value pair into the hash table
  unsigned bucket_index = get_bucket_index(node.key);
  List_iterator< Hash_node<Key, Value> > position = find(bucket_index, node.key);

  if (position == buckets[bucket_index].end()) {
    buckets[bucket_index].insert_back(&node);
  } else {
    buckets[bucket_index].remove(position);
    buckets[bucket_index].insert_back(&node);
  }
}

template <class Key, class Value, class Hash_func, class Compare_func>
bool
Hash_table<Key, Value, Hash_func, Compare_func>::remove(Key key) {
  // find the given key and them remove its node. if the key could not be
  // found, return false
  unsigned bucket_index = get_bucket_index(key);
  List_iterator< Hash_node<Key, Value> > position = find(bucket_index, key);

  if (position == buckets[bucket_index].end())
    return false;

  buckets[bucket_index].remove(position);
  return true;
}

template <class Key, class Value, class Hash_func, class Compare_func>
inline Hash_iterator<Key, Value>
Hash_table<Key, Value, Hash_func, Compare_func>::begin() {
  // return an iterator for the first element in the first bucket
  Iterator iterator;
  iterator.hash_table = this;
  iterator.bucket_index = 0;
  iterator.position = buckets[0].begin();

  // if the first bucket is empty, start the iterator off at the first actual
  // element
  if (buckets[0].size() == 0)
    ++iterator;
  return iterator;
}

template <class Key, class Value, class Hash_func, class Compare_func>
inline Hash_iterator<Key, Value>
Hash_table<Key, Value, Hash_func, Compare_func>::end() {
  // return an iterator for the end of the hash table, after the last
  // element in the last bucket
  Iterator iterator;
  iterator.hash_table = this;
  iterator.bucket_index = buckets.size() - 1;
  iterator.position = buckets[buckets.size() - 1].end();
  return iterator;
}

template <class Key, class Value, class Hash_func, class Compare_func>
void
Hash_table<Key, Value, Hash_func, Compare_func>::print() {
  screen.print("hash table ", false);
  screen.print(this, false);
  screen.print(": ");
  
  unsigned count = 0;
  for (Hash_iterator<Key, Value> pos = begin(); pos != end(); ++pos) {
    screen.print("  node ", false);
    screen.print(&*pos, false);
    screen.print(" index ", false);
    screen.print(pos.bucket_index, false);
    screen.print(": ", false);
    screen.print(pos->key, false);
    screen.print(" -> ", false);
    screen.print(pos->value);
    for (unsigned i=0; i<999999; i++){}
    count++;
  }

  screen.print(count, false);
  screen.print(" elements");

  screen.print(buckets.size(), false);
  screen.print(" buckets");
}

template <class Key, class Value, class Hash_func, class Compare_func>
void
Hash_table<Key, Value, Hash_func, Compare_func>::unit_test() {
  const unsigned NODE_COUNT = 1;
  Hash_node<Key, Value> nodes[NODE_COUNT];

  // insert a ton of nodes into the hash table
  screen.print("inserting test nodes into hash table");
  for (unsigned i = 0; i < NODE_COUNT; ++i) {
    nodes[i].key = (Key)i;
    nodes[i].value = (Key)(i+1);
    insert(nodes[i]);
  }
  
  screen.print("checking values of all test nodes");
  for (unsigned i = 0; i < NODE_COUNT; ++i) {
    Value* value = get(nodes[i].key);
    if (*value != nodes[i].value) {
      screen.print("error: expected test value not found");
      while (1) { }
    }
  }

  screen.print("removing all test nodes");
  for (unsigned i = 0; i < NODE_COUNT; ++i) {
    if (!remove(nodes[i].key)) {
      screen.print("error: node removal failed");
      while (1) { }
    }
  }

  screen.print("unit test complete");
}

#endif    

/* Torsion Operating System, Copyright (C) 2000-2004 Dan Helfman
 *
 * 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 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 (in the COPYING file).
 * 
 * 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.,
 * 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

---

Torsion Operating System, Copyright (C) 2000-2004 Dan Helfman