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
|
/*
* CENA C++ Utilities
*
* by Stephane Chatty
*
* Copyright 1991-1995
* 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 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 (size_t);
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 (const 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 CcuHashIter& operator ++ () { return (CcuHashIter&)(this->CcuHashCellIter::operator ++ ()); }
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_ */
|
