hash_list.h

Go to the documentation of this file.

#ifndef hash_list_h_included
#define hash_list_h_included


//
// Copyright 2002, Lowell Boggs Jr.
//
// This file or directory, containing source code for a computer program,
// is Copyrighted by Lowell Boggs, Jr.  987 Regency Drive, Lewisville
// TX (USA), 75067.  You may use, copy, modify, and distribute this
// source file without charge or obligation so long as you agree to
// the following:
//
//  1.  You must indemnify Lowell Boggs against any and all financial
//      obligations caused by its use, misuse, function, or malfunction.
//      Further, you acknowledge that there is no warranty of any kind,
//      whatsoever.
//
//  2.  You agree not to attempt to patent any portion of this original
//      work -- though you may attempt to patent your own extensions to
//      it if you so choose.
//
//  3.  You keep this copyright notice with the file and all copies
//      of the file and do not change it anyway except language translation.
//
// You are responsible for enforcing your own compliance with these
// conditions and may not use this source file if you cannot agree to the
// above terms and conditions.




#include <list>
#include <vector>
#include <utility>
#include <cxxtls/hashers.h>

namespace cxxtls
{



template<class Key, class Value, class Hash=Hasher<Key> >
class hash_list
//
{
  Value empty_value_;  


public:

  typedef hash_list<Key,Value,Hash>   self;

  typedef typename std::pair<Key,Value> mapped_type;

  struct value_type
    //
  {
    value_type *bucket_next_;  

    mapped_type data_;         

    value_type(value_type* bn, Key const &k, Value const &v)
    : bucket_next_(bn),
      data_(k,v)
    {
    }

  };

  typedef std::list<value_type>    List;    
  typedef std::vector<value_type*> Vector;  

  typedef typename List::iterator        iterator;        
  typedef typename List::const_iterator  const_iterator;  

private:

  size_t size_;                      
  size_t average_chain_length_;      
  List   list_;                      
  Vector ht_;                        
  Hash hash;                         

public:

  hash_list(int chain_length=10)
  :  size_(0),
     average_chain_length_(chain_length),
     ht_(10)

  {
     typename Vector::iterator first = ht_.begin();
     typename Vector::iterator last = ht_.end();

     while(first != last)
     {
        *first = 0;
        ++first;
     }

  }

  ~hash_list()
  {
  }

  size_t size() const { return size_; }  

  iterator begin() { return list_.begin(); } 
  iterator end()   { return list_.end();   } 

  const_iterator begin() const { return list_.begin(); } 
  const_iterator end()   const { return list_.end();   } 

  iterator insert(mapped_type const &data)
  //
  {
       list_.push_back( value_type(0, data.first, data.second) );

       iterator last = end();

       --last;


       value_type *p = & (*last);

       int hash_code = hash(data.first);

       hash_code %= ht_.size();

       last->bucket_next_ = ht_[hash_code];

       ht_[hash_code] = p;

       ++size_;

       if(size_ / ht_.size() > average_chain_length_)
       {
         resize();
       }

       return last;
  }

  void erase(iterator location)
   
    






  {
    value_type *p = &(*location);

    int bucket =  hash(p->data_.first) % ht_.size();

    if(ht_[bucket] == p)
    {
       // erasing first item in the bucket

       ht_[bucket] = p->bucket_next_;

    }
    else
    {
       // unlink the guy from inside the bucket's chain somewhere

       value_type *scan = ht_[bucket];

       while(scan->bucket_next_)
       {
         if(scan->bucket_next_ == p)
         {
           scan->bucket_next_ = p->bucket_next_;
           break;
         }

         scan = scan->bucket_next_;

       }

    }

    list_.erase(location);

    --size_;

  }

  iterator find(Key const &key)
    
    

    
  {
    int hash_code = hash(key);

    hash_code %= ht_.size();

    value_type* scan = ht_[hash_code];

    while(scan)
    {
       if(scan->data_.first == key)
       {

          // this code assumes that the value_type object is
          // encased in a list_node which looks like this
          //
          //   list_node* next_;
          //   list_node* prev_;
          //   value_type v_;
          //
          // And that you can thus subtract 2 * sizeof list_node*
          // from the address of the value type to get the address
          // of the node type.
          //
          // It further assumes that an iterator is just a pointer
          // to a list_node.
          //
          // There will have to be #if's for this logic on
          // each platform.

          iterator rv;

          char *p = (char*)scan;

          p -= 2 * sizeof(void*);

          char **x = (char **)&rv;

          x[0] = p;

          return rv;
       }

       scan = scan->bucket_next_;
    }

    return end();

  }

  const_iterator find( Key const &index ) const
  {
     self * me = (self*)(this);  // unconstify

     return me->find(index);

  }


  Value const &operator[] (Key const &index) const
    
    //
  {
    const_iterator rv = find(index);

    if(rv == end())
      return empty_value_;

    return rv->data_.second;
  }

  struct index_helper
    //
  {
     typedef hash_list<Key, Value, Hash> HL;      
     Key const&                            key_;  
     HL*                                   list_; 

     index_helper(Key const& k, HL *l)
     : key_(k),
       list_(l)
     {
     }

     operator Value const &()
        //
     {
        iterator ptr = list_->find(key_);
        
        if(ptr == list_->end())
          return list_->empty_value_;

        return ptr->data_.second;
        
     }


     Value const &operator=( Value const &r )
        //
     {

        iterator ptr = list_->find(key_);
        
        if(ptr != list_->end())
        {
           list_->erase(ptr);
        }
        
        list_->insert( mapped_type(key_,r) );
        
        return r;
        

     }


  };

  friend class index_helper;


  index_helper operator [] (Key const &index)
  {
    // see the index_helper struct above for an explaination of
    // how this works

    return index_helper(index,this);
  }



private:

  void resize()
  {

    int new_size = size_ / average_chain_length_;

    if(new_size < 10)
      new_size = 10;

    Vector new_table( new_size );

    while(new_table.size() != (unsigned)(new_size))
    {
      new_table.push_back(0);
    }

    ht_.swap(new_table);

    // now the hash table is larger but empty and the
    // bucket_next_ links in list_ are all wrong --
    // rebuild them all from scratch

    typename List::iterator f = list_.begin();
    typename List::iterator l = list_.end();

    while(f != l)
    {
      value_type *cur = &(*f);

      int hash_code = hash(cur->data_.first);

      hash_code %= ht_.size();

      cur->bucket_next_ = ht_[hash_code];

      ht_[hash_code] = cur;

      ++f;
    }

    // done!
  }
};
} // namespace cxxtls
#endif