1 /** \file lvhashtable.h
2 \brief hash table template
3
4 CoolReader Engine
5
6 (c) Vadim Lopatin, 2000-2006
7 This source code is distributed under the terms of
8 GNU General Public License.
9 See LICENSE file for details.
10
11 */
12
13 #ifndef __LVHASHTABLE_H_INCLUDED__
14 #define __LVHASHTABLE_H_INCLUDED__
15
16 #include "lvtypes.h"
17 #include <stdlib.h>
18 #include <string.h>
19
getHash(lUInt16 n)20 inline lUInt32 getHash( lUInt16 n )
21 {
22 return (lUInt32)n * 1975317 + 164521;
23 }
24
getHash(lUInt32 n)25 inline lUInt32 getHash( lUInt32 n )
26 {
27 return n * 1975317 + 164521;
28 }
29
getHash(lUInt64 n)30 inline lUInt32 getHash( lUInt64 n )
31 {
32 return (lUInt32)(n * 1975317 + (n >> 32) * 31 + 164521);
33 }
34
35 class LVFont;
getHash(LVFont * n)36 inline lUInt32 getHash(LVFont * n )
37 {
38 return getHash((lUInt64)n);
39 }
40
getHash(void * n)41 inline lUInt32 getHash(void * n )
42 {
43 return getHash((lUInt64)n);
44 }
45
46 /// Hash table
47 /**
48 Implements hash table map
49 */
50 template <typename keyT, typename valueT> class LVHashTable
51 {
52 friend class iterator;
53 public:
54 class pair {
55 friend class LVHashTable;
56 public:
57 pair * next; // extend
58 keyT key;
59 valueT value;
pair(const keyT & nkey,valueT nvalue,pair * pnext)60 pair( const keyT & nkey, valueT nvalue, pair * pnext ) : next(pnext), key(nkey), value(nvalue) { }
61 };
62
63 class iterator {
64 friend class LVHashTable;
65 const LVHashTable & _tbl;
66 int index;
67 pair * ptr;
68 iterator & operator = (iterator &) {
69 // no assignment
70 return *this;
71 }
72 public:
iterator(const LVHashTable & table)73 iterator( const LVHashTable & table )
74 : _tbl( table ), index(0), ptr(NULL)
75 {
76 }
iterator(const iterator & v)77 iterator( const iterator & v )
78 : _tbl( v._tbl ), index(v.index), ptr(v.ptr)
79 {
80 }
next()81 pair * next()
82 {
83 if ( index>=_tbl._size )
84 return NULL;
85 if ( ptr )
86 ptr = ptr->next;
87 if ( !ptr ) {
88 for ( ; index < _tbl._size; ) {
89 ptr = _tbl._table[ index++ ];
90 if ( ptr )
91 return ptr;
92 }
93 }
94 return ptr;
95 }
96 };
97
forwardIterator()98 iterator forwardIterator() const
99 {
100 return iterator(*this);
101 }
102
LVHashTable(int size)103 LVHashTable( int size )
104 {
105 if (size < 16 )
106 size = 16;
107 _table = new pair* [ size ]();
108 _size = size;
109 _count = 0;
110 }
~LVHashTable()111 ~LVHashTable()
112 {
113 if ( _table ) {
114 clear();
115 delete[] _table;
116 }
117 }
clear()118 void clear()
119 {
120 for ( int i=0; i<_size; i++ ) {
121 pair * p = _table[i];
122 while ( p ) {
123 pair * tmp = p;
124 p = p->next;
125 delete tmp;
126 }
127 }
128 memset( _table, 0, sizeof(pair*) * _size );
129 _count = 0;
130 }
length()131 int length() const { return _count; }
size()132 int size() const { return _size; }
resize(int nsize)133 void resize( int nsize )
134 {
135 pair ** new_table = new pair * [ nsize ]();
136 if (_table) {
137 for ( int i=0; i<_size; i++ ) {
138 pair * p = _table[i];
139 while ( p )
140 {
141 lUInt32 index = getHash( p->key ) % ( nsize );
142 new_table[index] = new pair( p->key, p->value, new_table[index] );
143 pair * tmp = p;
144 p = p->next;
145 delete tmp;
146 }
147 }
148 delete[] _table;
149 }
150 _table = new_table;
151 _size = nsize;
152
153 }
set(const keyT & key,valueT value)154 void set( const keyT & key, valueT value )
155 {
156 lUInt32 index = getHash( key ) % ( _size );
157 pair ** p = &_table[index];
158 for ( ;*p ;p = &(*p)->next )
159 {
160 if ( (*p)->key == key )
161 {
162 (*p)->value = value;
163 return;
164 }
165 }
166 if ( _count >= _size ) {
167 resize( _size * 2 );
168 index = getHash( key ) % ( _size );
169 p = &_table[index];
170 for ( ;*p ;p = &(*p)->next )
171 {
172 }
173 }
174 *p = new pair( key, value, NULL );
175 _count++;
176 }
remove(const keyT & key)177 void remove( const keyT & key )
178 {
179 lUInt32 index = getHash( key ) % ( _size );
180 pair ** p = &_table[index];
181 for ( ;*p ;p = &(*p)->next )
182 {
183 if ( (*p)->key == key )
184 {
185 pair * tmp = *p;
186 *p = (*p)->next;
187 delete tmp;
188 _count--;
189 return;
190 }
191 }
192 }
get(const keyT & key)193 valueT get( const keyT & key ) const
194 {
195 lUInt32 index = getHash( key ) % ( _size );
196 pair * p = _table[index];
197 for ( ;p ;p = p->next )
198 {
199 if ( p->key == key )
200 {
201 return p->value;
202 }
203 }
204 return valueT();
205 }
get(const keyT & key,valueT & res)206 bool get( const keyT & key, valueT & res ) const
207 {
208 lUInt32 index = getHash( key ) % ( _size );
209 pair * p = _table[index];
210 for ( ;p ;p = p->next )
211 {
212 if ( p->key == key )
213 {
214 res = p->value;
215 return true;
216 }
217 }
218 return false;
219 }
220 private:
221 int _size;
222 int _count;
223 pair ** _table;
224 };
225
226
227 #endif
228