Subversion Repositories spk

Rev

Go to most recent revision | Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
1 cycrow 1 
#ifndef __HASH_H__
2 
#define __HASH_H__
3 
 
4 
#include "CyString.h"
5 
 
6 
#define HASH_DEFAULT_PRIME	383
7 
#define HASH_DEFAULT_MULTI	1024
8 
 
9 
#define CStringHashTable CHashTableNonPtr<CyString>
10 
 
11 
template <class DATA>
12 
class CHashNode
13 
{
14 
public:
15 
	CHashNode<DATA> ( CyString &name, DATA index ) { m_name = name; m_index = index; m_next = NULL; m_prev = NULL; }
16 
 
17 
	CHashNode<DATA> *Next	 () { return m_next;  }
18 
	CHashNode<DATA> *Prev	 () { return m_prev;  }
19 
	CyString		     &Name	 () { return m_name;  }
20 
	DATA             GetData () { return m_index; }
21 
 
22 
	void SetData ( DATA index )				{ m_index = index; }
23 
	void SetNext ( CHashNode<DATA> *next )  { m_next = next; }
24 
	void SetPrev ( CHashNode<DATA> *prev )  { m_prev = prev; }
25 
 
26 
private:
27 
	CyString		 m_name;
28 
	DATA			 m_index;
29 
	CHashNode<DATA> *m_next;
30 
	CHashNode<DATA> *m_prev;
31 
};
32 
 
33 
template <class DATA>
34 
class CHashTable
35 
{
36 
public:
37 
	CHashTable<DATA> ( unsigned int prime, unsigned int multi )
38 
	{
39 
		m_prime = prime;
40 
		m_multi = multi;
41 
 
42 
		m_null = null;
43 
 
44 
		#ifdef TESTHASH
45 
			m_count = (int *)malloc(sizeof(int) * m_prime);
46 
		#else
47 
			m_head = (CHashNode<DATA> **)malloc(sizeof(CHashNode<DATA> *) * m_prime);
48 
			m_tail = (CHashNode<DATA> **)malloc(sizeof(CHashNode<DATA> *) * m_prime);
49 
		#endif
50 
 
51 
		for ( unsigned int i = 0; i < m_prime; i++ )
52 
		{
53 
			#ifdef TESTHASH
54 
				m_count[i] = 0;
55 
			#else
56 
				m_head[i] = NULL;
57 
				m_tail[i] = NULL;
58 
			#endif
59 
		}
60 
		m_currentItr = NULL;
61 
		m_currentItrTable = 0;
62 
	}
63 
	~CHashTable<DATA> ()
64 
	{
65 
		#ifdef TESTHASH
66 
			free ( m_count );
67 
		#else
68 
			for ( unsigned int i = 0; i < m_prime; i++ )
69 
			{
70 
				CHashNode<DATA> *nextnode, *node = m_head[i];
71 
				while ( node )
72 
				{
73 
					nextnode = node->Next();
74 
					delete node;
75 
					node = nextnode;
76 
				}
77 
			}
78 
			free ( m_head );
79 
			free ( m_tail );
80 
		#endif
81 
	}
82 
 
83 
	void ClearIterate () { m_currentItrTable = 0; m_currentItr = NULL; }
84 
 
85 
	CHashNode<DATA> *Iterate ()
86 
	{
87 
		if ( !m_currentItr )
88 
		{
89 
			m_currentItrTable = 0;
90 
			m_currentItr = m_head[0];
91 
 
92 
			while ( !m_currentItr )
93 
			{
94 
				++m_currentItrTable;
95 
				if ( m_currentItrTable >= m_prime )
96 
					break;
97 
				m_currentItr = m_head[m_currentItrTable];
98 
			}
99 
		}
100 
		else
101 
		{
102 
			m_currentItr = m_currentItr->Next();
103 
			while ( !m_currentItr )
104 
			{
105 
				++m_currentItrTable;
106 
				if ( m_currentItrTable >= m_prime )
107 
					break;
108 
				m_currentItr = m_head[m_currentItrTable];
109 
			}
110 
		}
111 
		return m_currentItr;
112 
	}
113 
 
114 
	DATA IterateData ()
115 
	{
116 
		if ( m_currentItr )
117 
			return m_currentItr->GetData();
118 
		return NULL;
119 
	}
120 
 
121 
	void RemoveIterate ()
122 
	{
123 
		if ( !m_currentItr )
124 
			return;
125 
 
126 
		CHashNode<DATA> *nextnode = m_currentItr->Prev();
127 
		int table = m_currentItrTable;
128 
 
129 
		while ( (!nextnode) && (table >= 0) )
130 
		{
131 
			--table;
132 
			nextnode = m_tail[table];
133 
		}
134 
 
135 
		if ( m_currentItr->Next() )
136 
			m_currentItr->Next()->SetPrev ( m_currentItr->Prev() );
137 
		else
138 
			m_tail[m_currentItrTable] = m_currentItr->Prev();
139 
 
140 
		if ( m_currentItr->Prev() )
141 
			m_currentItr->Prev()->SetNext ( m_currentItr->Next() );
142 
		else
143 
			m_head[m_currentItrTable] = m_currentItr->Next();
144 
 
145 
		delete m_currentItr;
146 
		m_currentItrTable = table;
147 
		m_currentItr = nextnode;
148 
	}
149 
 
150 
/*#ifdef TESTHASH
151 
	void Add ( CyString &name )
152 
	{
153 
		++m_count[Hash ( name )];
154 
	}
155 
#else*/
156 
	void Remove ( CyString &name, bool deletenode = true )
157 
	{
158 
		unsigned int hash = Hash ( name );
159 
 
160 
		CHashNode<DATA> *node = FindEntity ( hash, name );
161 
		if ( node )
162 
		{
163 
			// only one in list?
164 
			if ( (m_head[hash] == node) && (m_tail[hash] == node) )
165 
			{
166 
				m_head[hash] = NULL;
167 
				m_tail[hash] = NULL;
168 
			}
169 
			// remove from front of list
170 
			else if ( m_head[hash] == node )
171 
			{
172 
				node->Next()->SetPrev ( NULL );
173 
				m_head[hash] = node->Next();
174 
			}
175 
			// remove from end of list
176 
			else if ( m_tail[hash] == node )
177 
			{
178 
				node->Prev()->SetNext ( NULL );
179 
				m_tail[hash] = node->Prev();
180 
			}
181 
			// some where in the middle
182 
			else
183 
			{
184 
				node->Prev()->SetNext ( node->Next() );
185 
				node->Next()->SetPrev ( node->Prev() );
186 
			}
187 
			if ( deletenode )
188 
				delete node;
189 
		}
190 
	}
191 
 
192 
	void Add ( CyString &name, DATA index, bool search = true )
193 
	{
194 
		unsigned int hash = Hash ( name );
195 
 
196 
		if ( search )
197 
		{
198 
			CHashNode<DATA> *node = FindEntity ( hash, name );
199 
			if ( node )
200 
				node->SetData ( index );
201 
			else
202 
				Put ( hash, name, index );
203 
		}
204 
		else
205 
			Put ( hash, name, index );
206 
 
207 
	}
208 
 
209 
	DATA FindData ( CyString &name )
210 
	{
211 
		unsigned int hash = Hash ( name );
212 
 
213 
		CHashNode<DATA> *node = FindEntity ( hash, name );
214 
 
215 
		if ( node )
216 
			return node->GetData ();
217 
 
218 
		return 0;
219 
	}
220 
	CHashNode<DATA> *FindEntity ( CyString &name )
221 
	{
222 
		return FindEntity ( Hash ( name ), name );
223 
	}
224 
 
225 
	void Empty ()
226 
	{
227 
		for ( int i = 0; i < m_prime; i++ )
228 
		{
229 
			CHashNode<DATA> *node = m_head[i], *curnode = NULL;
230 
			while ( node )
231 
			{
232 
				curnode = node;
233 
				node = node->Next();
234 
				delete curnode;
235 
			}
236 
			m_head[i] = m_tail[i] = NULL;
237 
		}
238 
	}
239 
//#endif
240 
 
241 
 
242 
private:
243 
#ifndef TESTHASH
244 
	CHashNode<DATA> *FindEntity ( unsigned int hash, CyString &name )
245 
	{
246 
		CHashNode<DATA> *node = m_head[hash];
247 
 
248 
		while ( node )
249 
		{
250 
			if ( node->Name() == name )
251 
				return node;
252 
 
253 
			node = node->Next();
254 
		}
255 
		return NULL;
256 
	}
257 
	void Put ( unsigned int pos, CyString &name, DATA index )
258 
	{
259 
		if ( pos >= m_prime )
260 
			pos %= m_prime;
261 
 
262 
		CHashNode<DATA> *node = new CHashNode<DATA> ( name, index );
263 
 
264 
		if ( !m_tail[pos] )
265 
			m_head[pos] = m_tail[pos] = node;
266 
		else
267 
		{
268 
			node->SetPrev ( m_tail[pos] );
269 
			m_tail[pos]->SetNext ( node );
270 
			m_tail[pos] = node;
271 
		}
272 
 
273 
	}
274 
#endif
275 
 
276 
	unsigned int Hash ( CyString &name )
277 
	{
278 
		unsigned int hash = 0;
279 
 
280 
		/*  transform the string into an integer  */
281 
		for ( int i = 0; i < name.Length(); i++ )
282 
			hash = (hash * m_multi) + name[i];
283 
 
284 
		/*  reduce the integer to the correct range  */
285 
		return hash % m_prime;
286 
	}
287 
 
288 
	unsigned int		m_prime;
289 
	unsigned int		m_multi;
290 
#ifndef TESTHASH
291 
	CHashNode<DATA>   **m_head;
292 
	CHashNode<DATA>   **m_tail;
293 
	CHashNode<DATA>   *m_currentItr;
294 
	unsigned int	   m_currentItrTable;
295 
#else
296 
	int *m_count;
297 
#endif
298 
};
299 
 
300 
 
301 
template <class DATA>
302 
class CHashNodeNonPtr
303 
{
304 
public:
305 
	CHashNodeNonPtr<DATA> ( CyString &name, DATA index ) { m_name = name; m_index = index; m_next = NULL; m_prev = NULL; }
306 
 
307 
	CHashNodeNonPtr<DATA> *Next	 () { return m_next;  }
308 
	CHashNodeNonPtr<DATA> *Prev	 () { return m_prev;  }
309 
	CyString		     &Name	 () { return m_name;  }
310 
	DATA             GetData () { return m_index; }
311 
 
312 
	void SetData ( DATA index )				{ m_index = index; }
313 
	void SetNext ( CHashNodeNonPtr<DATA> *next )  { m_next = next; }
314 
	void SetPrev ( CHashNodeNonPtr<DATA> *prev )  { m_prev = prev; }
315 
 
316 
private:
317 
	CyString		 m_name;
318 
	DATA			 m_index;
319 
	CHashNodeNonPtr<DATA> *m_next;
320 
	CHashNodeNonPtr<DATA> *m_prev;
321 
};
322 
 
323 
template <class DATA>
324 
class CHashTableNonPtr
325 
{
326 
public:
327 
	CHashTableNonPtr<DATA> ( unsigned int prime, unsigned int multi, DATA null )
328 
	{
329 
		m_prime = prime;
330 
		m_multi = multi;
331 
 
332 
		m_null = null;
333 
 
334 
		#ifdef TESTHASH
335 
			m_count = (int *)malloc(sizeof(int) * m_prime);
336 
		#else
337 
			m_head = (CHashNodeNonPtr<DATA> **)malloc(sizeof(CHashNodeNonPtr<DATA> *) * m_prime);
338 
			m_tail = (CHashNodeNonPtr<DATA> **)malloc(sizeof(CHashNodeNonPtr<DATA> *) * m_prime);
339 
		#endif
340 
 
341 
		for ( unsigned int i = 0; i < m_prime; i++ )
342 
		{
343 
			#ifdef TESTHASH
344 
				m_count[i] = 0;
345 
			#else
346 
				m_head[i] = NULL;
347 
				m_tail[i] = NULL;
348 
			#endif
349 
		}
350 
		m_bIgnoreCase = false;
351 
		m_currentItr = NULL;
352 
		m_currentItrTable = 0;
353 
	}
354 
	~CHashTableNonPtr<DATA> ()
355 
	{
356 
		#ifdef TESTHASH
357 
			free ( m_count );
358 
		#else
359 
			for ( unsigned int i = 0; i < m_prime; i++ )
360 
			{
361 
				CHashNodeNonPtr<DATA> *nextnode, *node = m_head[i];
362 
				while ( node )
363 
				{
364 
					nextnode = node->Next();
365 
					delete node;
366 
					node = nextnode;
367 
				}
368 
			}
369 
			free ( m_head );
370 
			free ( m_tail );
371 
		#endif
372 
	}
373 
 
374 
	void IgnoreCase(bool b) { m_bIgnoreCase = b; }
375 
	void ClearIterate () { m_currentItrTable = 0; m_currentItr = NULL; }
376 
 
377 
	CHashNodeNonPtr<DATA> *Iterate ()
378 
	{
379 
		if ( !m_currentItr )
380 
		{
381 
			m_currentItrTable = 0;
382 
			m_currentItr = m_head[0];
383 
 
384 
			while ( !m_currentItr )
385 
			{
386 
				++m_currentItrTable;
387 
				if ( m_currentItrTable >= m_prime )
388 
					break;
389 
				m_currentItr = m_head[m_currentItrTable];
390 
			}
391 
		}
392 
		else
393 
		{
394 
			m_currentItr = m_currentItr->Next();
395 
			while ( !m_currentItr )
396 
			{
397 
				++m_currentItrTable;
398 
				if ( m_currentItrTable >= m_prime )
399 
					break;
400 
				m_currentItr = m_head[m_currentItrTable];
401 
			}
402 
		}
403 
		return m_currentItr;
404 
	}
405 
 
406 
	DATA IterateData ()
407 
	{
408 
		if ( m_currentItr )
409 
			return m_currentItr->GetData();
410 
		return m_null;
411 
	}
412 
 
413 
	void RemoveIterate ()
414 
	{
415 
		if ( !m_currentItr )
416 
			return;
417 
 
418 
		CHashNodeNonPtr<DATA> *nextnode = m_currentItr->Prev();
419 
		int table = m_currentItrTable;
420 
 
421 
		while ( (!nextnode) && (table >= 0) )
422 
		{
423 
			--table;
424 
			nextnode = m_tail[table];
425 
		}
426 
 
427 
		if ( m_currentItr->Next() )
428 
			m_currentItr->Next()->SetPrev ( m_currentItr->Prev() );
429 
		else
430 
			m_tail[m_currentItrTable] = m_currentItr->Prev();
431 
 
432 
		if ( m_currentItr->Prev() )
433 
			m_currentItr->Prev()->SetNext ( m_currentItr->Next() );
434 
		else
435 
			m_head[m_currentItrTable] = m_currentItr->Next();
436 
 
437 
		delete m_currentItr;
438 
		m_currentItrTable = table;
439 
		m_currentItr = nextnode;
440 
	}
441 
 
442 
/*#ifdef TESTHASH
443 
	void Add ( CyString &name )
444 
	{
445 
		++m_count[Hash ( name )];
446 
	}
447 
#else*/
448 
	void Remove ( CyString &name, bool deletenode = true )
449 
	{
450 
		unsigned int hash = Hash ( name );
451 
 
452 
		CHashNodeNonPtr<DATA> *node = FindEntity ( hash, name );
453 
		if ( node )
454 
		{
455 
			// only one in list?
456 
			if ( (m_head[hash] == node) && (m_tail[hash] == node) )
457 
			{
458 
				m_head[hash] = NULL;
459 
				m_tail[hash] = NULL;
460 
			}
461 
			// remove from front of list
462 
			else if ( m_head[hash] == node )
463 
			{
464 
				node->Next()->SetPrev ( NULL );
465 
				m_head[hash] = node->Next();
466 
			}
467 
			// remove from end of list
468 
			else if ( m_tail[hash] == node )
469 
			{
470 
				node->Prev()->SetNext ( NULL );
471 
				m_tail[hash] = node->Prev();
472 
			}
473 
			// some where in the middle
474 
			else
475 
			{
476 
				node->Prev()->SetNext ( node->Next() );
477 
				node->Next()->SetPrev ( node->Prev() );
478 
			}
479 
			if ( deletenode )
480 
				delete node;
481 
		}
482 
	}
483 
 
484 
	void Add ( CyString &name, DATA index, bool search = true )
485 
	{
486 
		unsigned int hash = Hash ( name );
487 
 
488 
		if ( search )
489 
		{
490 
			CHashNodeNonPtr<DATA> *node = FindEntity ( hash, name );
491 
			if ( node )
492 
				node->SetData ( index );
493 
			else
494 
				Put ( hash, name, index );
495 
		}
496 
		else
497 
			Put ( hash, name, index );
498 
 
499 
	}
500 
 
501 
	DATA FindData ( CyString &name )
502 
	{
503 
		unsigned int hash = Hash ( name );
504 
 
505 
		CHashNodeNonPtr<DATA> *node = FindEntity ( hash, name );
506 
 
507 
		if ( node )
508 
			return node->GetData ();
509 
 
510 
		return m_null;
511 
	}
512 
	CHashNodeNonPtr<DATA> *FindEntity ( CyString &name )
513 
	{
514 
		return FindEntity ( Hash ( name ), name );
515 
	}
516 
 
517 
	void Empty ()
518 
	{
519 
		for ( int i = 0; i < m_prime; i++ )
520 
		{
521 
			CHashNodeNonPtr<DATA> *node = m_head[i], *curnode = NULL;
522 
			while ( node )
523 
			{
524 
				curnode = node;
525 
				node = node->Next();
526 
				delete curnode;
527 
			}
528 
			m_head[i] = m_tail[i] = NULL;
529 
		}
530 
	}
531 
//#endif
532 
 
533 
 
534 
protected:
535 
#ifndef TESTHASH
536 
	CHashNodeNonPtr<DATA> *FindEntity ( unsigned int hash, CyString &name )
537 
	{
538 
		CHashNodeNonPtr<DATA> *node = m_head[hash];
539 
 
540 
		while ( node )
541 
		{
542 
			if ( (!m_bIgnoreCase) && (node->Name() == name) )
543 
				return node;
544 
			else if ( (m_bIgnoreCase) && (node->Name().Compare(name)) )
545 
				return node;
546 
 
547 
			node = node->Next();
548 
		}
549 
		return NULL;
550 
	}
551 
	void Put ( unsigned int pos, CyString &name, DATA index )
552 
	{
553 
		if ( pos >= m_prime )
554 
			pos %= m_prime;
555 
 
556 
		CHashNodeNonPtr<DATA> *node = new CHashNodeNonPtr<DATA> ( name, index );
557 
 
558 
		if ( !m_tail[pos] )
559 
			m_head[pos] = m_tail[pos] = node;
560 
		else
561 
		{
562 
			node->SetPrev ( m_tail[pos] );
563 
			m_tail[pos]->SetNext ( node );
564 
			m_tail[pos] = node;
565 
		}
566 
 
567 
	}
568 
#endif
569 
 
570 
	unsigned int Hash ( CyString &name )
571 
	{
572 
		unsigned int hash = 0;
573 
 
574 
		/*  transform the string into an integer  */
575 
		for ( unsigned int i = 0; i < name.Length(); i++ )
576 
			hash = (hash * m_multi) + name[i];
577 
 
578 
		/*  reduce the integer to the correct range  */
579 
		return hash % m_prime;
580 
	}
581 
 
582 
	unsigned int		m_prime;
583 
	unsigned int		m_multi;
584 
#ifndef TESTHASH
585 
	CHashNodeNonPtr<DATA>   **m_head;
586 
	CHashNodeNonPtr<DATA>   **m_tail;
587 
	CHashNodeNonPtr<DATA>   *m_currentItr;
588 
	unsigned int	   m_currentItrTable;
589 
	DATA				m_null;
590 
	bool				m_bIgnoreCase;
591 
#else
592 
	int *m_count;
593 
#endif
594 
};
595 
 
596 
#endif //__HASH_H__