1 /********************************************************************************
2 * *
3 * H a s h T a b l e C l a s s *
4 * *
5 *********************************************************************************
6 * Copyright (C) 2003,2005 by Jeroen van der Zijp. All Rights Reserved. *
7 *********************************************************************************
8 * This library is free software; you can redistribute it and/or *
9 * modify it under the terms of the GNU Lesser General Public *
10 * License as published by the Free Software Foundation; either *
11 * version 2.1 of the License, or (at your option) any later version. *
12 * *
13 * This library is distributed in the hope that it will be useful, *
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
16 * Lesser General Public License for more details. *
17 * *
18 * You should have received a copy of the GNU Lesser General Public *
19 * License along with this library; if not, write to the Free Software *
20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. *
21 *********************************************************************************
22 * $Id: FXHash.cpp,v 1.21 2005/01/16 16:06:07 fox Exp $ *
23 ********************************************************************************/
24 #include "fxver.h"
25 #include "fxdefs.h"
26 #include "FXHash.h"
27
28
29 /*
30 Notes:
31 - The members used and free keep track of the number of slots
32 in the table which are used and which are free.
33 - When an item is inserted, used is incremented if the item isn't in the table
34 yet, and free is decremented if a free slot is used; if an empty slot is
35 used, free stays the same. If the table exceeds the load factor, its
36 size is doubled.
37 - When an item is removed, used is decremented but free stays the same
38 because the slot remains marked as empty instead of free; when the
39 number of used items drops below some minimum, the table's size is
40 halved.
41 - If the table is resized, the empty slots all become free slots since
42 the empty holes are not copied into the table; only used items will
43 be rehashed into the new table.
44 */
45
46 #define HASH1(x,m) (((FXuint)((FXuval)(key)^(((FXuval)(key))>>13)))&(m))
47 #define HASH2(x,m) (((FXuint)((FXuval)(key)^(((FXuval)(key))>>17)|1))&(m))
48
49
50
51 using namespace FX;
52
53 /*******************************************************************************/
54
55 namespace FX {
56
57 // Make empty table
FXHash()58 FXHash::FXHash(){
59 FXMALLOC(&table,FXEntry,2);
60 table[0].key=NULL;
61 table[0].val=NULL;
62 table[1].key=NULL;
63 table[1].val=NULL;
64 used=0;
65 free=2;
66 max=1;
67 }
68
69
70 // Resize hash table, and rehash old stuff into it
resize(FXuint m)71 void FXHash::resize(FXuint m){
72 register void *key,*val;
73 register FXuint p,x,i;
74 FXEntry *newtable;
75 FXCALLOC(&newtable,FXEntry,m+1);
76 for(i=0; i<=max; i++){
77 key=table[i].key;
78 val=table[i].val;
79 if(key==NULL || key==(void*)-1L) continue;
80 p=HASH1(key,m);
81 x=HASH2(key,m);
82 while(newtable[p].key) p=(p+x)&m;
83 newtable[p].key=key;
84 newtable[p].val=val;
85 }
86 FXFREE(&table);
87 table=newtable;
88 free=m+1-used;
89 max=m;
90 }
91
92
93 // Insert key into the table
insert(void * key,void * val)94 void* FXHash::insert(void* key,void* val){
95 register FXuint p,pp,x;
96 if(key){
97 if((free<<1)<=max+1) resize((max<<1)|1);
98 p=pp=HASH1(key,max);
99 x=HASH2(key,max);
100 while(table[p].key){
101 if(table[p].key==key) goto y; // Return existing
102 p=(p+x)&max;
103 }
104 p=pp;
105 while(table[p].key){
106 if(table[p].key==(void*)-1L) goto x; // Put it in empty slot
107 p=(p+x)&max;
108 }
109 free--;
110 x: used++;
111 table[p].key=key;
112 table[p].val=val;
113 y: return table[p].val;
114 }
115 return NULL;
116 }
117
118
119 // Replace key in the table
replace(void * key,void * val)120 void* FXHash::replace(void* key,void* val){
121 register FXuint p,pp,x;
122 if(key){
123 if((free<<1)<=max+1) resize((max<<1)|1);
124 p=pp=HASH1(key,max);
125 x=HASH2(key,max);
126 while(table[p].key){
127 if(table[p].key==key) goto y; // Replace existing
128 p=(p+x)&max;
129 }
130 p=pp;
131 while(table[p].key){
132 if(table[p].key==(void*)-1L) goto x; // Put it in empty slot
133 p=(p+x)&max;
134 }
135 free--;
136 x: used++;
137 table[p].key=key;
138 y: table[p].val=val;
139 return table[p].val;
140 }
141 return NULL;
142 }
143
144
145 // Remove association from the table
remove(void * key)146 void* FXHash::remove(void* key){
147 register FXuint p,x;
148 register void* val;
149 if(key){
150 p=HASH1(key,max);
151 x=HASH2(key,max);
152 while(table[p].key!=key){
153 if(table[p].key==NULL) goto x;
154 p=(p+x)&max;
155 }
156 val=table[p].val;
157 table[p].key=(void*)-1L; // Empty but not free
158 table[p].val=NULL;
159 used--;
160 if(used<((max+1)>>2)) resize(max>>1);
161 return val;
162 }
163 x:return NULL;
164 }
165
166
167 // Return true if association in table
find(void * key) const168 void* FXHash::find(void* key) const {
169 register FXuint p,x;
170 if(key){
171 p=HASH1(key,max);
172 x=HASH2(key,max);
173 while(table[p].key!=key){
174 if(table[p].key==NULL) goto x;
175 p=(p+x)&max;
176 }
177 return table[p].val;
178 }
179 x:return NULL;
180 }
181
182
183 // Clear hash table
clear()184 void FXHash::clear(){
185 FXRESIZE(&table,FXEntry,2);
186 table[0].key=NULL;
187 table[0].val=NULL;
188 table[1].key=NULL;
189 table[1].val=NULL;
190 used=0;
191 free=2;
192 max=1;
193 }
194
195
196 // Destroy table
~FXHash()197 FXHash::~FXHash(){
198 FXFREE(&table);
199 table=(FXEntry*)-1L;
200 }
201
202 }
203
204