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
229
230
231
232
|
/*
* Ivy League
*
* plain and generic hash tables and dictionnaries
* (Original C version by Michel Beaudouin-Lafon)
*
* Copyright 1991-2000
* Laboratoire de Recherche en Informatique (LRI)
* Centre d'Etudes de la Navigation Aerienne (CENA)
*
* by Stephane Chatty
*
* $Id$
*
*/
#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);
IvlHashItem* RemoveOne ();
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 ITEM* RemoveOne () { return (ITEM*) IvlHashTable::RemoveOne (); }
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 ITEM* RemoveOne () { return (ITEM*) IvlDictionnary::RemoveOne (); }
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 ITEM* RemoveOne () { return (ITEM*) IvlHashTable::RemoveOne (); }
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_ */
|
