git.mutantstargoat.com Git - summerhack/blob - src/3dengfx/src/common/hashtable.hpp

   1 /*
   2 Copyright (c) 2004, 2005 John Tsiombikas <nuclear@siggraph.org>
   3
   4 This is a hash table implementation with chaining collision resolution.
   5
   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.
  10
  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.
  15
  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
  19 */
  20
  21 /* Hash table with chaining.
  22  *
  23  * Author: John Tsiombikas 2004
  24  */
  25
  26 // TODO: create a decent hash table and get rid of this mess.
  27
  28 #ifndef _HASHTABLE_HPP_
  29 #define _HASHTABLE_HPP_
  30
  31 #include <iostream>
  32 #include <list>
  33 #include <vector>
  34 #include <algorithm>
  35
  36 template <class KeyT, class ValT>
  37 struct Pair {
  38         KeyT key;
  39         ValT val;
  40 };
  41
  42 template <class KeyType, class ValType>
  43 class HashTable {
  44 private:
  45         size_t size;
  46         std::vector<std::list<Pair<KeyType, ValType> > > table;
  47
  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);}
  50
  51         void (*data_destructor)(ValType);
  52 public:
  53
  54         HashTable(unsigned long size = 101);
  55         ~HashTable();
  56
  57         void set_hash_function(unsigned int (*hash_func)(const KeyType&, unsigned long));
  58
  59         void insert(KeyType key, ValType value);
  60         void remove(KeyType key);
  61
  62         Pair<KeyType, ValType> *find(KeyType key);
  63
  64         void set_data_destructor(void (*destructor)(ValType));
  65 };
  66
  67
  68 // hash table member functions
  69 template <class KeyType, class ValType>
  70 HashTable<KeyType, ValType>::HashTable(unsigned long size) {
  71         this->size = size;
  72         table.resize(size);
  73         data_destructor = 0;
  74 }
  75
  76 template <class KeyType, class ValType>
  77 HashTable<KeyType, ValType>::~HashTable() {
  78         for(unsigned long i=0; i<size; i++) {
  79                 if(data_destructor) {
  80                         std::list<ValType> hacklist;
  81
  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);
  87                                 }
  88                         }
  89                 }
  90
  91                 table[i].clear();
  92         }
  93 }
  94
  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;
  98 }
  99
 100 template <class KeyType, class ValType>
 101 void HashTable<KeyType, ValType>::insert(KeyType key, ValType value) {
 102         Pair<KeyType, ValType> newpair;
 103         newpair.key = key;
 104         newpair.val = value;
 105
 106         table[hash(key)].push_back(newpair);
 107 }
 108
 109 template <class KeyType, class ValType>
 110 void HashTable<KeyType, ValType>::remove(KeyType key) {
 111
 112         unsigned int pos = hash(key);
 113
 114         typename std::list<Pair<KeyType, ValType> >::iterator iter = table[pos].begin();
 115
 116         while(iter != table[pos].end()) {
 117                 if(iter->key == key) {
 118                         table[pos].erase(iter);
 119                         return;
 120                 }
 121                 iter++;
 122         }
 123 }
 124
 125 template <class KeyType, class ValType>
 126 Pair<KeyType, ValType> *HashTable<KeyType, ValType>::find(KeyType key) {
 127
 128         unsigned int pos = hash(key);
 129
 130         typename std::list<Pair<KeyType, ValType> >::iterator iter = table[pos].begin();
 131         while(iter != table[pos].end()) {
 132                 if(iter->key == key) {
 133                         return &(*iter);
 134                 }
 135                 iter++;
 136         }
 137
 138         return 0;
 139 }
 140
 141 template <class KeyType, class ValType>
 142 void HashTable<KeyType, ValType>::set_data_destructor(void (*destructor)(ValType)) {
 143         data_destructor = destructor;
 144 }
 145
 146 #endif  // _HASHTABLE_HPP_