2 Copyright (c) 2004, 2005 John Tsiombikas <nuclear@siggraph.org>
4 This is a hash table implementation with chaining collision resolution.
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
21 /* Hash table with chaining.
23 * Author: John Tsiombikas 2004
26 // TODO: create a decent hash table and get rid of this mess.
28 #ifndef _HASHTABLE_HPP_
29 #define _HASHTABLE_HPP_
36 template <class KeyT, class ValT>
42 template <class KeyType, class ValType>
46 std::vector<std::list<Pair<KeyType, ValType> > > table;
48 unsigned int (*hash_func)(const KeyType &key, unsigned long size);
49 unsigned int hash(const KeyType &key) {return (unsigned int)hash_func(key, (unsigned long)size);}
51 void (*data_destructor)(ValType);
54 HashTable(unsigned long size = 101);
57 void set_hash_function(unsigned int (*hash_func)(const KeyType&, unsigned long));
59 void insert(KeyType key, ValType value);
60 void remove(KeyType key);
62 Pair<KeyType, ValType> *find(KeyType key);
64 void set_data_destructor(void (*destructor)(ValType));
68 // hash table member functions
69 template <class KeyType, class ValType>
70 HashTable<KeyType, ValType>::HashTable(unsigned long size) {
76 template <class KeyType, class ValType>
77 HashTable<KeyType, ValType>::~HashTable() {
78 for(unsigned long i=0; i<size; i++) {
80 std::list<ValType> hacklist;
82 typename std::list<Pair<KeyType, ValType> >::iterator iter = table[i].begin();
83 while(iter != table[i].end()) {
84 if(std::find(hacklist.begin(), hacklist.end(), iter->val) == hacklist.end()) {
85 hacklist.push_back(iter->val);
86 data_destructor((iter++)->val);
95 template <class KeyType, class ValType>
96 void HashTable<KeyType, ValType>::set_hash_function(unsigned int (*hash_func)(const KeyType&, unsigned long)) {
97 this->hash_func = hash_func;
100 template <class KeyType, class ValType>
101 void HashTable<KeyType, ValType>::insert(KeyType key, ValType value) {
102 Pair<KeyType, ValType> newpair;
106 table[hash(key)].push_back(newpair);
109 template <class KeyType, class ValType>
110 void HashTable<KeyType, ValType>::remove(KeyType key) {
112 unsigned int pos = hash(key);
114 typename std::list<Pair<KeyType, ValType> >::iterator iter = table[pos].begin();
116 while(iter != table[pos].end()) {
117 if(iter->key == key) {
118 table[pos].erase(iter);
125 template <class KeyType, class ValType>
126 Pair<KeyType, ValType> *HashTable<KeyType, ValType>::find(KeyType key) {
128 unsigned int pos = hash(key);
130 typename std::list<Pair<KeyType, ValType> >::iterator iter = table[pos].begin();
131 while(iter != table[pos].end()) {
132 if(iter->key == key) {
141 template <class KeyType, class ValType>
142 void HashTable<KeyType, ValType>::set_data_destructor(void (*destructor)(ValType)) {
143 data_destructor = destructor;
146 #endif // _HASHTABLE_HPP_