libStatGen Software 1
Loading...
Searching...
No Matches
LongHash< ObjectT > Class Template Reference

Public Member Functions

 LongHash (int startsize=32)
 
void Grow ()
 
void Shrink ()
 
void SetSize (int newsize)
 
void Clear ()
 
int Capacity () const
 
int Entries () const
 
ObjectT Object (int i) const
 
ObjectT & Object (int i)
 
void SetObject (int i, ObjectT object)
 
unsigned int Add (long long key, ObjectT object)
 
unsigned int Find (long long key)
 
unsigned int Rehash (long long key, unsigned int h)
 
LongHashoperator= (const LongHash &rhs)
 
ObjectT operator[] (int i) const
 
ObjectT operator[] (unsigned int i) const
 
void Delete (unsigned int index)
 
bool SlotInUse (int index) const
 
bool SlotInUse (unsigned int index) const
 
long long GetKey (int index) const
 
long long GetKey (const unsigned int index) const
 
void SetAllowDuplicateKeys (bool toggle)
 

Protected Attributes

ObjectT * objects
 
long long * keys
 
bool * occupancy
 
unsigned int count
 
unsigned int size
 
unsigned int mask
 
bool allowDuplicates
 

Detailed Description

template<class ObjectT>
class LongHash< ObjectT >

Definition at line 31 of file LongHash.h.

Constructor & Destructor Documentation

◆ LongHash()

template<class ObjectT >
LongHash< ObjectT >::LongHash ( int  startsize = 32)
inline

Definition at line 42 of file LongHash.h.

43 {
44 count = 0;
45 size = startsize;
46 mask = startsize - 1;
47
48 // In this implementation, the size of hash tables must be a power of two
49 if (startsize & mask)
50 error("LongHash: Hash table size must be a power of two.\n");
51
52 occupancy = new bool [size];
53 objects = new ObjectT [size];
54 keys = new long long [size];
55
56 allowDuplicates = false;
57
58 for (unsigned int i = 0; i < size; i++)
59 {
60 occupancy[i] = false;
61 }
62 };

◆ ~LongHash()

template<class ObjectT >
LongHash< ObjectT >::~LongHash ( )
inline

Definition at line 64 of file LongHash.h.

65 {
66 delete [] occupancy;
67 delete [] objects;
68 delete [] keys;
69 }

Member Function Documentation

◆ Add()

template<class ObjectT >
unsigned int LongHash< ObjectT >::Add ( long long  key,
ObjectT  object 
)
inline

Definition at line 154 of file LongHash.h.

155 {
156 if (count * 2 > size)
157 Grow();
158
159 unsigned int h = Iterate(key);
160
161 while (allowDuplicates && occupancy[h] && objects[h] != object)
162 h = ReIterate(key, h);
163
164 if (!occupancy[h])
165 {
166 occupancy[h] = true;
167 keys[h] = key;
168 count++;
169 }
170
171 objects[h] = object;
172
173 return h;
174 }

◆ Capacity()

template<class ObjectT >
int LongHash< ObjectT >::Capacity ( ) const
inline

Definition at line 131 of file LongHash.h.

132 {
133 return size;
134 }

◆ Clear()

template<class ObjectT >
void LongHash< ObjectT >::Clear ( )
inline

Definition at line 120 of file LongHash.h.

121 {
122 count = 0;
123
124 if (size > 32)
125 SetSize(32);
126
127 for (unsigned int i = 0; i < size; i++)
128 occupancy[i] = false;
129 }

◆ Delete()

template<class ObjectT >
void LongHash< ObjectT >::Delete ( unsigned int  index)
inline

Definition at line 201 of file LongHash.h.

202 {
203 if (index >= size || !occupancy[index])
204 return;
205
206 occupancy[index] = false;
207 count--;
208
209 if (count * 8 < size && size > 32)
210 Shrink();
211 else
212 {
213 // rehash the next entries until we find empty slot
214 index = (index + 1) & mask;
215
216 while (occupancy[index])
217 {
218 if ((keys[index] & mask) != index)
219 {
220 unsigned int h = Iterate(keys[index]);
221
222 while (occupancy[h] && objects[h] != objects[index])
223 h = ReIterate(keys[index], h);
224
225 if (h != (unsigned int) index)
226 {
227 keys[h] = keys[index];
228 occupancy[h] = true;
229 objects[h] = objects[index];
230
231 occupancy[index] = false;
232 }
233 }
234
235 index = (index + 1) & mask;
236 }
237 }
238 }

◆ Entries()

template<class ObjectT >
int LongHash< ObjectT >::Entries ( ) const
inline

Definition at line 135 of file LongHash.h.

136 {
137 return count;
138 }

◆ Find()

template<class ObjectT >
unsigned int LongHash< ObjectT >::Find ( long long  key)
inline

Definition at line 176 of file LongHash.h.

177 {
178 unsigned int h = Iterate(key);
179
180 return occupancy[h] ? h : LH_NOTFOUND;
181 }

◆ GetKey() [1/2]

template<class ObjectT >
long long LongHash< ObjectT >::GetKey ( const unsigned int  index) const
inline

Definition at line 256 of file LongHash.h.

257 {
258 return keys[index];
259 }

◆ GetKey() [2/2]

template<class ObjectT >
long long LongHash< ObjectT >::GetKey ( int  index) const
inline

Definition at line 251 of file LongHash.h.

252 {
253 return keys[index];
254 }

◆ Grow()

template<class ObjectT >
void LongHash< ObjectT >::Grow ( )
inline

Definition at line 71 of file LongHash.h.

72 {
73 SetSize(size * 2);
74 }

◆ Object() [1/2]

template<class ObjectT >
ObjectT & LongHash< ObjectT >::Object ( int  i)
inline

Definition at line 144 of file LongHash.h.

145 {
146 return objects[i];
147 }

◆ Object() [2/2]

template<class ObjectT >
ObjectT LongHash< ObjectT >::Object ( int  i) const
inline

Definition at line 140 of file LongHash.h.

141 {
142 return objects[i];
143 }

◆ operator[]() [1/2]

template<class ObjectT >
ObjectT LongHash< ObjectT >::operator[] ( int  i) const
inline

Definition at line 192 of file LongHash.h.

193 {
194 return objects[i];
195 }

◆ operator[]() [2/2]

template<class ObjectT >
ObjectT LongHash< ObjectT >::operator[] ( unsigned int  i) const
inline

Definition at line 196 of file LongHash.h.

197 {
198 return objects[i];
199 }

◆ Rehash()

template<class ObjectT >
unsigned int LongHash< ObjectT >::Rehash ( long long  key,
unsigned int  h 
)
inline

Definition at line 183 of file LongHash.h.

184 {
185 h = ReIterate(key, h);
186
187 return occupancy[h] ? h : LH_NOTFOUND;
188 }

◆ SetAllowDuplicateKeys()

template<class ObjectT >
void LongHash< ObjectT >::SetAllowDuplicateKeys ( bool  toggle)
inline

Definition at line 261 of file LongHash.h.

262 {
263 allowDuplicates = toggle;
264
265 if (count && !allowDuplicates)
266 SetSize(size);
267 }

◆ SetObject()

template<class ObjectT >
void LongHash< ObjectT >::SetObject ( int  i,
ObjectT  object 
)
inline

Definition at line 149 of file LongHash.h.

150 {
151 objects[i] = object;
152 }

◆ SetSize()

template<class ObjectT >
void LongHash< ObjectT >::SetSize ( int  newsize)
inline

Definition at line 80 of file LongHash.h.

81 {
82 int newmask = newsize - 1;
83
84 bool * newoccupancy = new bool [newsize];
85 ObjectT * newobjects = new ObjectT [newsize];
86 long long * newkeys = new long long [newsize];
87
88 for (int i = 0; i < newsize; i++)
89 newoccupancy[i] = false;
90
91 if (count)
92 for (unsigned int i = 0; i < size; i++)
93 if (occupancy[i] != false)
94 {
95 long long key = keys[i];
96 unsigned int h = newmask & (unsigned int) key;
97
98 while (newoccupancy[h] == true && (newkeys[h] != key || allowDuplicates))
99 h = (h + 1) & newmask;
100
101 if (newoccupancy[h])
102 count--;
103
104 newkeys[h] = key;
105 newobjects[h] = objects[i];
106 newoccupancy[h] = true;
107 }
108
109 delete [] occupancy;
110 delete [] objects;
111 delete [] keys;
112
113 occupancy = newoccupancy;
114 objects = newobjects;
115 keys = newkeys;
116 size = newsize;
117 mask = newmask;
118 }

◆ Shrink()

template<class ObjectT >
void LongHash< ObjectT >::Shrink ( )
inline

Definition at line 75 of file LongHash.h.

76 {
77 SetSize(size / 2);
78 }

◆ SlotInUse() [1/2]

template<class ObjectT >
bool LongHash< ObjectT >::SlotInUse ( int  index) const
inline

Definition at line 241 of file LongHash.h.

242 {
243 return occupancy[index] == true;
244 }

◆ SlotInUse() [2/2]

template<class ObjectT >
bool LongHash< ObjectT >::SlotInUse ( unsigned int  index) const
inline

Definition at line 245 of file LongHash.h.

246 {
247 return occupancy[index] == true;
248 }

Member Data Documentation

◆ allowDuplicates

template<class ObjectT >
bool LongHash< ObjectT >::allowDuplicates
protected

Definition at line 39 of file LongHash.h.

◆ count

template<class ObjectT >
unsigned int LongHash< ObjectT >::count
protected

Definition at line 37 of file LongHash.h.

◆ keys

template<class ObjectT >
long long* LongHash< ObjectT >::keys
protected

Definition at line 35 of file LongHash.h.

◆ mask

template<class ObjectT >
unsigned int LongHash< ObjectT >::mask
protected

Definition at line 38 of file LongHash.h.

◆ objects

template<class ObjectT >
ObjectT* LongHash< ObjectT >::objects
protected

Definition at line 34 of file LongHash.h.

◆ occupancy

template<class ObjectT >
bool* LongHash< ObjectT >::occupancy
protected

Definition at line 36 of file LongHash.h.

◆ size

template<class ObjectT >
unsigned int LongHash< ObjectT >::size
protected

Definition at line 37 of file LongHash.h.


The documentation for this class was generated from the following file: