summaryrefslogtreecommitdiff
path: root/utils/HashTable.h
blob: c30e5c78331853d617c39cbebc9f7eb75a6712d2 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
/*
 *	CENA C++ Utilities
 *
 *	by Stephane Chatty
 *
 *	Copyright 1991, 1992
 *	Laboratoire de Recherche en Informatique (LRI)
 *	Centre d'Etudes de la Navigation Aerienne (CENA)
 *
 *	plain and generic hash tables and dictionnaries
 *	(Original C version by Michel Beaudouin-Lafon)
 *
 *	$Id$
 *	$CurLog$
 */

#ifndef HashTable_H_
#define HashTable_H_


#include "cplus_bugs.h"

class CcuAllocator;

typedef void CcuHashItem;

class CcuHashCell {
protected:
friend	class	CcuHashTable;
friend	class	CcuHashCellIter;
static	CcuAllocator*	HashCellMem;
static	void	ClassInit ();

	const void*	Key;		/* hash key */
	CcuHashItem*	Info;			/* data */
	CcuHashCell*	Next;			/* synonyms */
	
inline		CcuHashCell (const void* k, CcuHashCell* n) : Key (k), Info (0), Next (n)	{}

public:
inline	void	SetInfo (CcuHashItem* p)			{ Info = p; }
inline	CcuHashItem*	GetInfo () const			{ return Info; }
inline	const void*	GetKey () const			{ return Key; }

	void*	operator new (unsigned long);
	void	operator delete (void*);
};

class CcuHashCellRef {
friend	class	CcuHashTable;
protected:
		const CcuHashTable&	Table;
		const void*	Key;
inline	CcuHashCellRef (const CcuHashTable& t, const void* key) : Table (t), Key (key)	{}
#ifdef CPLUS_BUG1
inline	CcuHashCellRef (const CcuHashCellRef& t) : Table (t.Table), Key (t.Key)	{}
#endif
public:
	CcuHashItem*	operator = (CcuHashItem*);
		operator CcuHashItem* ();
};


typedef unsigned int (*HASH_F) (const void*, int);
typedef int (*HCMP_F) (const void*, const void*);
typedef void* (*HCP_F) (const void*);
typedef void (*HDEL_F) (const void*);

class CcuHashTable {
private:
friend	class	CcuHashCellIter;
friend	class	CcuHashCellRef;

protected :
	CcuHashCell**	Table;
	unsigned int	Size;
	HASH_F	Hash;
	HCP_F	Copy;
	HDEL_F	Delete;
	HCMP_F	Compare;

	CcuHashCell**	HashKey (const void*) const;
	CcuHashCell*	FindCell (CcuHashCell**, const void*) const;
	CcuHashCell*	AddCell (CcuHashCell**, const void*) const;

public:
static	unsigned int	HashPtr (const void*, int);

		CcuHashTable (unsigned int, HASH_F = 0, HCP_F = 0, HDEL_F = 0, HCMP_F = 0);
		CcuHashTable (const CcuHashTable&);
		~CcuHashTable ();
	CcuHashCell*	Add (const void*, int* = 0);
	CcuHashCell*	Get (const void*);
	CcuHashItem*	Remove (const void*, int* = 0);
	void	Clear ();
	void	Resize (int);
inline	int	GetSize () const		{ return Size; }
	CcuHashCellRef operator [] (const void*) const;

#ifdef TUNE
	void	HashStats ();
	void	CollStats ();
#endif
};

class CcuDictionnary : public CcuHashTable {
protected:
static	void*	CopyString (const void*);
static	void	DeleteString (void*);
static	int	CompareString (const void*, const void*);


public:
		CcuDictionnary (int size, HASH_F = 0);
		~CcuDictionnary ();

	void	KeyCopy (int);
static	unsigned int	HashString (const void*, int);
};


class CcuHashCellIter {
public:
	enum	hashiter_status	{ Normal, StartOfTable, EndOfTable, BadTable };

protected:
	const CcuHashTable&	TheTable;
	int	CurIndex;
	CcuHashCell*	CurCell;

public:
inline		CcuHashCellIter (const CcuHashTable& t) : TheTable (t) { CurIndex = -1; CurCell = 0; }
inline		~CcuHashCellIter () {}

inline	void	Reset ()	{ CurCell = 0; CurIndex = -1; }
	CcuHashCellIter&	operator ++ ();
#ifndef CPLUS_BUG16
	CcuHashCellIter	operator ++ (int);
#endif
inline	CcuHashCell*	operator * () const	{ return CurCell; }
	hashiter_status	GetStatus () const;
inline	operator int () const	{ return CurCell != 0; }
};

class CcuHashIter : public CcuHashCellIter {
public:
inline		CcuHashIter (const CcuHashTable& t) : CcuHashCellIter (t) { }
inline		~CcuHashIter () {}

inline	CcuHashIter&	operator ++ ()	{ ++((CcuHashCellIter) (*this)); return *this; }
inline	CcuHashItem*	operator * () const	{ return CurCell ? CurCell->GetInfo () : 0; }
};

#ifndef CPLUS_BUG19

template <class ITEM> class CcuHashTableOf;
template <class ITEM> class CcuDictionnaryOf;

template <class ITEM> class CcuHashCellOf : public CcuHashCell {
protected:
inline		CcuHashCellOf (const void* k, CcuHashCellOf<ITEM>* n) : CcuHashCell (k, n)	{}
public:
inline	void	SetInfo (ITEM* p)			{ CcuHashCell::SetInfo (p); }
inline	ITEM*	GetInfo () const			{ return (ITEM*) CcuHashCell::GetInfo (); }
};

template <class ITEM> class CcuHashCellRefOf : public CcuHashCellRef {
friend	class	CcuHashTableOf<ITEM>;
friend	class	CcuDictionnaryOf<ITEM>;
protected:
inline	CcuHashCellRefOf (const CcuHashTableOf<ITEM>& t, const void* key) : CcuHashCellRef (t, key)	{}
#ifdef CPLUS_BUG1
inline	CcuHashCellRefOf (const CcuHashCellRefOf<ITEM>& t) : CcuHashCellRef (t)	{}
#endif
public:
inline	ITEM*	operator = (ITEM* it)		{ return (ITEM*) (CcuHashCellRef::operator = (it)); }
inline		operator ITEM* ()		{ return (ITEM*) (CcuHashCellRef::operator CcuHashItem* ()); }
};


template <class ITEM> class CcuHashTableOf : public CcuHashTable {
public:
inline		CcuHashTableOf (unsigned int size, HASH_F hash = 0, HCP_F cp = 0, HDEL_F del = 0, HCMP_F cmp= 0)
				: CcuHashTable (size, hash, cp, del, cmp)	{}
inline		~CcuHashTableOf ()	{}
inline	CcuHashCellOf<ITEM>*	Add (const void* key, int* found = 0)	{ return (CcuHashCellOf<ITEM>*) CcuHashTable::Add (key, found); }
inline	CcuHashCellOf<ITEM>*	Get (const void* key)		{ return (CcuHashCellOf<ITEM>*) CcuHashTable::Get (key); }
inline	ITEM*	Remove (const void* key, int* found = 0)	{ return (ITEM*) CcuHashTable::Remove (key, found); }
inline	CcuHashCellRefOf<ITEM> operator [] (const void* key) const	{ return CcuHashCellRefOf<ITEM> (*this, key); }
};

template <class ITEM> class CcuDictionnaryOf : public CcuDictionnary {
public:
inline		CcuDictionnaryOf (unsigned int size, HASH_F hash = 0) : CcuDictionnary (size, hash)	{}
inline		~CcuDictionnaryOf ()	{}
inline	CcuHashCellOf<ITEM>*	Add (const void* key, int* found = 0)	{ return (CcuHashCellOf<ITEM>*) CcuDictionnary::Add (key, found); }
inline	CcuHashCellOf<ITEM>*	Get (const void* key)		{ return (CcuHashCellOf<ITEM>*) CcuDictionnary::Get (key); }
inline	ITEM*	Remove (const void* key, int* found = 0)	{ return (ITEM*) CcuDictionnary::Remove (key, found); }
inline		operator const CcuHashTableOf<ITEM>& () const	{ return *(const CcuHashTableOf<ITEM>*) this; }
inline	CcuHashCellRefOf<ITEM> operator [] (const char* key) const	{ return CcuHashCellRefOf<ITEM> (*(const CcuHashTableOf<ITEM>*)this, key); }
};


template <class ITEM> class CcuHashIterOf : public CcuHashIter {
public:
inline		CcuHashIterOf (const CcuHashTableOf<ITEM>& t) : CcuHashIter (t) { }
inline		~CcuHashIterOf () {}
inline	CcuHashIterOf<ITEM>&	operator ++ ()	{ ++((CcuHashIter) (*this)); return *this; }
inline	ITEM*	operator * () const	{ return (ITEM*) (CcuHashIter::operator  * ()); }
};

#endif	/* CPLUS_BUG19 */

#endif	/* HashTable_H_ */