Subversion Repositories spk

Rev

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