---

hashtable.h

Go to the documentation of this file.

/*
 * Ethereal
 * Copyright (C) 2001-2002 Daniel Horn & Alan Shieh
 *
 * http://vegastrike.sourceforge.net/ethereabl
 *
 * 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.
 *
 * 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.
 */

#ifndef _HASHTABLE_H_
#define _HASHTABLE_H_

#include <math.h>
#include <string>
#include <vector>
//#include <set>

template<class KEY, class VALUE, int SIZ=256> class Hashtable {
    typedef std::pair <KEY, VALUE> HashElement;
public:
    typedef std::vector<HashElement> vector_type;
    typedef HashElement value_type; 

    template <class Type> static int hash(const Type key) {
      return ((unsigned int)key)%SIZ;
    }
    template <class it> class HashIterator {
        KEY key;
        vector_type *v;
        it i;
        void findnext() {
            const it e= v->end();
            for (;i!=e;++i) {
                if (key==(*i).first)
                    break;
            }
        }
        friend class Hashtable<KEY,VALUE,SIZ>;
    public:
        typedef it it_type;
        bool operator ==(const HashIterator &o) const {return i==o.i;}
        bool operator !=(const HashIterator &o) const {return i!=o.i;}
        bool operator ==(const it &o) const {return i==o;}
        bool operator !=(const it &o) const {return i!=o;}
        it end() {return v->end();}
        it begin() {return v->begin();}
        unsigned int size() {return v->size();}
        value_type &operator * () {
            return *i;
        }
        const value_type &operator * () const {
            return *i;
        }
        value_type *operator-> () {
            return &(*i);
        }
        const value_type &operator-> () const {
            return &(*i);
        }
        HashIterator (const KEY &key, vector_type *v):key(key), v(v), i(v->begin()) {;findnext();}
        HashIterator (const KEY &key, vector_type *v, it i):key(key), v(v), i(i) {}
//      HashIterator (it iter) : key(), v(NULL), i(iter) {}
//      HashIterator (const HashIterator<it> &hi):key(hi.key),v (hi.v),i (&(*hi))  {}
/*      HashIterator & operator= (HashIterator &oth) {
            i=(&(*oth));
            key=oth.key;
            v=oth.v;
            return (*this);
            }*/
        operator it_type () {
            return i;
        }
        operator const it_type () const{
            return i;
        }
        HashIterator & operator ++ (){
            i++;
            findnext();
            return *this;
        }
        HashIterator operator ++ (int){
            HashIterator<it> oldthis (*this);
            i++;
            findnext();
            return oldthis;
        }
        HashIterator & operator + (int inc) const{
            HashIterator<it> newit (this);
            for (int ii=0;ii<inc;++ii) {
                newit++;
            }
            return newit;
        }
    };
    typedef HashIterator<typename vector_type::iterator> iterator; 
    typedef HashIterator<typename vector_type::const_iterator> const_iterator; 
        
        

    static int hash(const std::string &key) {
        unsigned int k = 0;
        std::string::const_iterator start = key.begin();
        
        for(;start!=key.end(); start++) {
            k += (k * 128) + *start;
        }
        k %= SIZ;
        return k;
    }
private:
    vector_type table[SIZ];
    void swapiter (iterator iter1, iterator iter2) {
        value_type backup=(*iter1);
        (*iter1)=(*iter2);
        (*iter2)=backup;
    }
    iterator SwapIn (vector_type *tbl, HashElement elem) {
        tbl.push_back(elem);
        iterator iter=tbl.back()-1;
        return iter;
    }
public:

    vector_type &GetAll(const KEY &key)
    {
        int hashval = hash(key);
        return table[hashval];
    }
    VALUE *Get(const KEY &key)
    {
        int hashval = hash(key);
        typename vector_type::iterator iter = table[hashval].begin();
        typename vector_type::const_iterator end = table[hashval].end();
        for(;;iter++) {
            if (iter==end)
                return NULL;
            if((*iter).first == key)
                break;
        }
        return &(*iter).second;
    }
    const VALUE *Get(const KEY &key) const
    {
        int hashval = hash(key);
        typename vector_type::const_iterator iter = table[hashval].find(key);
        typename vector_type::const_iterator end = table[hashval].end();
        for(;iter!=end;iter++)
            if((*iter).first == key)
                break;
        if (iter==end)
            return NULL;
        else
            return &(*iter).second;
    }
    bool Get (const KEY & key, VALUE & k){
        VALUE * g = Get(key);
        if (g) {
            k=*g;
            return true;
        }
        return false;
    }
    

    iterator find(const KEY &key) {
        int tablenum=hash(key);
        vector_type *mytyp=&table[tablenum];
        return iterator(key, mytyp);
    }

    const_iterator find(const KEY &key) const{
        int tablenum=hash(key);
        const vector_type *mytyp=&table[tablenum];
        return const_iterator (key, mytyp);
    }
    void Put(const KEY &key, const VALUE &value) {
        int hashval = hash(key);
        table[hashval].push_back(HashElement(key, value));
    }
    iterator insert(value_type valty) {
        int hashval = hash(valty.first);
        vector_type &tab=table[hashval];
        tab.push_back (valty);
        return iterator(valty.first, &tab, tab.end()-1);//fulliterator (SwapIn(table[hashval],valty), hashval);
    }
    void Delete(const KEY &key)
    {
        int hashval = hash(key);
        typename vector_type::iterator iter = table[hashval].begin(), end = table[hashval].end();

        for(;iter!=end;iter++)
            if((*iter).key == key)
                break;
        if(iter==end)
            return;
        else {
            table[hashval].erase(iter);
        }
    }
    iterator erase (const iterator &iter) {
        iterator ret(iter.key,iter.v,iter.v->erase(iter.i));
        ret.findnext();
        return ret;
    }

    unsigned int size (int vectorname) const {
        return table[vectorname].size();
    }

};

#endif

---