summaryrefslogtreecommitdiff
path: root/utils/HashTable.h
blob: 6586efe8d24cd7ee930bb29c1ea1cda6a7d38b5e (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
216
217
218
219
220
221
222
223
224
225
226
227
228
/*
 *	CENA C++ Utilities
 *
 *	by Stephane Chatty
 *
 *	Copyright 1991-1997
 *	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"
#include <sys/types.h>

class IvlAllocator;

typedef void IvlHashItem;

class IvlHashCell {
protected:
friend	class	IvlHashTable;
friend	class	IvlHashCellIter;
static	IvlAllocator*	HashCellMem;
static	void	ClassInit ();

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

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

	void*	operator new (size_t);
	void	operator delete (void*);
};

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

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 IvlHashTable {
private:
friend	class	IvlHashCellIter;
friend	class	IvlHashCellRef;

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

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

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

		IvlHashTable (unsigned int, HASH_F = 0, HCP_F = 0, HDEL_F = 0, HCMP_F = 0);
		IvlHashTable (const IvlHashTable&);
		~IvlHashTable ();
	IvlHashCell*	Add (const void*, int* = 0);
	IvlHashCell*	Get (const void*);
	IvlHashItem*	Remove (const void*, int* = 0);
	void	Clear ();
	void	Resize (int);
inline	int	GetSize () const		{ return Size; }
	IvlHashCellRef operator [] (const void*) const;

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

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

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

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

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

protected:
	const IvlHashTable&	TheTable;
	int	CurIndex;
	IvlHashCell*	CurCell;

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

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

class IvlHashIter : public IvlHashCellIter {
public:
inline		IvlHashIter (const IvlHashTable& t) : IvlHashCellIter (t) { }
inline		~IvlHashIter () {}

inline	IvlHashIter&	operator ++ ()	{ return (IvlHashIter&)(this->IvlHashCellIter::operator ++ ()); }
inline	IvlHashItem*	operator * () const	{ return CurCell ? CurCell->GetInfo () : 0; }
};

#ifndef CPLUS_BUG19

template <class ITEM> class IvlHashTableOf;
template <class ITEM> class IvlDictionnaryOf;

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

template <class ITEM> class IvlHashCellRefOf : public IvlHashCellRef {
public:
inline	IvlHashCellRefOf (const IvlHashTableOf<ITEM>& t, const void* key) : IvlHashCellRef (t, key)	{}
#ifdef CPLUS_BUG1
inline	IvlHashCellRefOf (const IvlHashCellRefOf<ITEM>& t) : IvlHashCellRef (t)	{}
#endif
inline	ITEM*	operator = (ITEM* it)		{ return (ITEM*) (IvlHashCellRef::operator = (it)); }
inline		operator ITEM* ()		{ return (ITEM*) (IvlHashCellRef::operator IvlHashItem* ()); }
};

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

template <class ITEM> class IvlDictionnaryOf : public IvlDictionnary {
public:
inline		IvlDictionnaryOf (unsigned int size, HASH_F hash = 0) : IvlDictionnary (size, hash)	{}
inline		~IvlDictionnaryOf ()	{}
inline	IvlHashCellOf<ITEM>*	Add (const void* key, int* found = 0)	{ return (IvlHashCellOf<ITEM>*) IvlDictionnary::Add (key, found); }
inline	IvlHashCellOf<ITEM>*	Get (const void* key)		{ return (IvlHashCellOf<ITEM>*) IvlDictionnary::Get (key); }
inline	ITEM*	Remove (const void* key, int* found = 0)	{ return (ITEM*) IvlDictionnary::Remove (key, found); }
inline		operator const IvlHashTableOf<ITEM>& () const	{ return *(const IvlHashTableOf<ITEM>*) this; }
inline	IvlHashCellRefOf<ITEM> operator [] (const char* key) const	{ return IvlHashCellRefOf<ITEM> (*(const IvlHashTableOf<ITEM>*)this, key); }
};

template <class ITEM> class IvlHashedArrayOf : public IvlHashTable {
public:
inline		IvlHashedArrayOf (unsigned int size, HASH_F hash = 0) : IvlHashTable (size, hash)	{}
inline		~IvlHashedArrayOf ()	{}
inline	IvlHashCellOf<ITEM>*	Add (int key, int* found = 0)	{ return (IvlHashCellOf<ITEM>*) IvlHashTable::Add ((void*)key, found); }
inline	IvlHashCellOf<ITEM>*	Get (int key)		{ return (IvlHashCellOf<ITEM>*) IvlHashTable::Get ((void*)key); }
inline	ITEM*	Remove (int key, int* found = 0)	{ return (ITEM*) IvlHashTable::Remove ((void*) key, found); }
inline		operator const IvlHashTableOf<ITEM>& () const	{ return *(const IvlHashTableOf<ITEM>*) this; }
inline	IvlHashCellRefOf<ITEM> operator [] (int key) const	{ return IvlHashCellRefOf<ITEM> (*(const IvlHashTableOf<ITEM>*)this, (void*)key); }
};

template <class ITEM> class IvlHashIterOf : public IvlHashIter {
public:
inline		IvlHashIterOf (const IvlHashTableOf<ITEM>& t) : IvlHashIter (t) { }
inline		~IvlHashIterOf () {}
inline	IvlHashIterOf<ITEM>&	operator ++ ()	{ return (IvlHashIterOf<ITEM>&)(this->IvlHashIter::operator ++ ()); }
inline	ITEM*	operator * () const	{ return (ITEM*) (IvlHashIter::operator  * ()); }
};

template <class ITEM> class IvlHashCellIterOf : public IvlHashCellIter {
public:
inline		IvlHashCellIterOf (const IvlHashTableOf<ITEM>& t) : IvlHashCellIter (t) { }
inline		~IvlHashCellIterOf () {}
inline	IvlHashCellIterOf<ITEM>&	operator ++ ()	{ return (IvlHashCellIterOf<ITEM>&)(this->IvlHashCellIter::operator ++ ()); }
#ifndef CPLUS_BUG16
inline	IvlHashCellIterOf<ITEM>	operator ++ (int i)	{ return *(IvlHashCellIterOf<ITEM>*)&(this->IvlHashCellIter::operator ++ (i)); }
#endif
inline	IvlHashCellOf<ITEM>*	operator * () const	{ return (IvlHashCellOf<ITEM>*) (IvlHashCellIter::operator  * ()); }
};

#endif	/* CPLUS_BUG19 */

#endif	/* HashTable_H_ */