1 /* $Id$ */
2 /*
3 * Copyright (c) 1990-1996 Sam Leffler
4 * Copyright (c) 1991-1996 Silicon Graphics, Inc.
5 * HylaFAX is a trademark of Silicon Graphics
6 *
7 * Permission to use, copy, modify, distribute, and sell this software and
8 * its documentation for any purpose is hereby granted without fee, provided
9 * that (i) the above copyright notices and this permission notice appear in
10 * all copies of the software and related documentation, and (ii) the names of
11 * Sam Leffler and Silicon Graphics may not be used in any advertising or
12 * publicity relating to the software without the specific, prior written
13 * permission of Sam Leffler and Silicon Graphics.
14 *
15 * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND,
16 * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY
17 * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
18 *
19 * IN NO EVENT SHALL SAM LEFFLER OR SILICON GRAPHICS BE LIABLE FOR
20 * ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND,
21 * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
22 * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF
23 * LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
24 * OF THIS SOFTWARE.
25 */
26 #ifndef _Dictionary_
27 #define _Dictionary_
28
29 #include "Types.h"
30 #include "Array.h"
31 #include "Str.h"
32 #include "DSmacros.h"
33 #include "stdlib.h"
34
35 class fxDictIter;
36 class fxDictionary;
37
38 /*******************************************
39 // fxDictionary interface
40 class DICT(KEY,VALUE) : public fxDictionary {
41 public:
42 DICT();
43 DICT(const DICT &);
44 virtual ~DICT();
45 u_int size() const;
46 u_int getKeySize() const;
47 u_int getValueSize() const;
48 void operator=(const DICT &);
49 void add(const KEY &,const VALUE &);
50 void remove(const KEY);
51 VALUE *cut(const KEY); // does a find & remove
52 const VALUE* find(const KEY&, const KEY** k = 0) const;
53 // returns null if not found, optionally returns pointer to key
54 VALUE& operator[](const KEY &); // creates the key/value if not
55 const VALUE& operator[](const KEY &) const; // creates the key/value if not
56 fxObj* copy() const;
57 protected:
58 virtual u_long hashKey(const void *) const;
59 virtual int compareKeys(const void *, void const *) const; // 0 => equal
60 virtual void copyKey(const void *, void *) const;
61 virtual void copyValue(const void *, void *) const;
62 virtual void destroyKey(void *) const;
63 virtual void destroyValue(void *) const;
64 virtual void createValue(void *) const;
65 }
66
67 class DICTIter(DICT,KEY,VALUE) : public fxDictIter {
68 public:
69 DICTIter();
70 DICTIter(DICT&);
71 operator=(DICT&);
72 operator++();
73 operator++(int);
74 operator KEY const &() const
75 KEY const& key() const;
76 VALUE& value() const;
77 bool removed();
78 bool notDone();
79 }
80 *******************************************/
81
82 //----------------------------------------------------------------------
83
84 class fxDictBucket {
85 public:
fxDictBucket(void * kv,fxDictBucket * n)86 fxDictBucket(void* kv,fxDictBucket* n) { kvmem = kv; next = n; }
87 ~fxDictBucket();
88
89 void* kvmem;
90 fxDictBucket* next;
91 };
92
fxDECLARE_PtrArray(fxDictBuckets,fxDictBucket *)93 fxDECLARE_PtrArray(fxDictBuckets, fxDictBucket*)
94 fxDECLARE_PtrArray(fxDictIters, fxDictIter*)
95
96 //----------------------------------------------------------------------
97
98 #define fxDictVirtuals(HOW) \
99 virtual u_long hashKey(const void*) const; \
100 virtual int compareKeys(const void*, const void*) const HOW; \
101 virtual void copyKey(const void*, void*) const HOW; \
102 virtual void destroyKey(void*) const; \
103 virtual void copyValue(const void*, void*) const HOW; \
104 virtual void destroyValue(void*) const; \
105 virtual void createValue(void*) const HOW; \
106 __enddef__
107
108 //----------------------------------------------------------------------
109
110 class fxDictionary : public fxObj {
111 friend class fxDictIter;
112 public:
113 u_int size() const { return numItems; }
114 u_int getKeySize() const { return keysize; }
115 u_int getValueSize() const { return valuesize; }
116 virtual char const *className() const = 0;
117
118 protected:
119 fxDictionary(u_int ksize, u_int vsize, u_int initsize = 0);
120 fxDictionary(const fxDictionary&);
121 virtual ~fxDictionary();
122
123 void cleanup();
124
125 void operator=(const fxDictionary&);
126
127 const void *find(const void*, const void** k = 0) const;
128 void *findCreate(const void*);
129 void remove(const void*);
130 void *cut(const void*);
131
132 virtual void addInternal(const void*, const void*);
133
134 fxDictVirtuals(= 0)
135
136 void addIter(fxDictIter*);
137 void removeIter(fxDictIter*);
138 void invalidateIters(const fxDictBucket*);
139
140 u_int numItems;
141 u_int keysize;
142 u_int valuesize;
143 fxDictBuckets buckets;
144 fxDictIters iters;
145 };
146
147 //----------------------------------------------------------------------
148
149 class fxDictIter {
150 friend class fxDictionary;
151 public:
152 fxDictIter();
153 ~fxDictIter();
154 fxDictIter(fxDictionary&);
155 void operator=(fxDictionary&); // not a const argument!
156 void operator++() { increment(); }
157 void operator++(int) { increment(); }
removed()158 bool removed() const { return invalid; }
notDone()159 bool notDone() const { return node != 0; }
160 protected:
161 void* getKey() const;
162 void* getValue() const;
163
164 void increment();
165 void advanceToValid();
166
167 fxDictionary* dict; // 0 if iterator isn't valid yet.
168 u_int bucket;
169 u_int invalid:1; // this is 1 if the element was deleted.
170 fxDictBucket* node; // if "invalid", points to the next node
171 };
172
173 //----------------------------------------------------------------------
174 // Iterator declaration & implementation macros
175
176 #define fxDECLARE_DictIter(DICT,KEY,VALUE) \
177 class fxCAT(DICT,Iter) : public fxDictIter {/*XXX*/ \
178 public: \
179 fxCAT(DICT,Iter)(); \
180 fxCAT(DICT,Iter)(DICT &); \
181 fxCAT(DICT,Iter)(DICT *); \
182 void operator=(DICT& d) /* not a const argument! */ \
183 { fxDictIter::operator=(d); } \
184 void operator=(DICT* d) /* not a const argument! */ \
185 { fxDictIter::operator=(*d); } \
186 operator KEY const &() const \
187 { return *(KEY *)fxDictIter::getKey(); } \
188 KEY const &key() const \
189 { return *(KEY *)fxDictIter::getKey(); } \
190 VALUE &value() const \
191 { return *(VALUE *)fxDictIter::getValue(); } \
192 }; \
193 __enddef__
194
195 #define fxIMPLEMENT_DictIter(DICT,KEY,VALUE) \
196 fxCAT(DICT,Iter)::fxCAT(DICT,Iter)() : fxDictIter() {} \
197 fxCAT(DICT,Iter)::fxCAT(DICT,Iter)(DICT &d) \
198 : fxDictIter((fxDictionary &)d) {} \
199 fxCAT(DICT,Iter)::fxCAT(DICT,Iter)(DICT *d) \
200 : fxDictIter(*(fxDictionary *)d) {} \
201 __enddef__
202
203 //----------------------------------------------------------------------
204 // Dictionary declaration macros
205
206 #define fxNOTHING
207 #define fxDECLARE_Dictionary(DICT,KEY,VALUE) \
208 class DICT : public fxDictionary {/*XXX*/ \
209 public: \
210 DICT(u_int initsize=0); \
211 ~DICT(); \
212 virtual char const *className() const; \
213 void operator=(const DICT &d) \
214 {fxDictionary::operator=((const fxDictionary &)d);} \
215 void add(const KEY &k, const VALUE &v) { addInternal(&k,&v); } \
216 VALUE* cut(const KEY k) \
217 { return (VALUE*)fxDictionary::cut(&k); } \
218 void remove(const KEY k) \
219 { fxDictionary::remove(&k); } \
220 const VALUE* find(const KEY& k, const KEY** kp = 0) const \
221 { return (const VALUE*)fxDictionary::find(&k, (const void**)&kp); }\
222 VALUE& operator[](const KEY& k) \
223 { return *(VALUE*)fxDictionary::findCreate(&k); } \
224 protected: \
225 fxDictVirtuals(fxNOTHING) \
226 }; \
227 fxDECLARE_Ptr(DICT); \
228 fxDECLARE_DictIter(DICT,KEY,VALUE) \
229 __enddef__
230
231 // StrDictionary: the key is a fxStr object. The
232 // user only has to define copyValue and destroyValue.
233
234 #define fxDECLARE_StrKeyDictionary(DICT,VALUE) \
235 fxDECLARE_Dictionary(DICT,fxStr,VALUE)
236 #define fxDECLARE_PtrKeyDictionary(DICT,KEY,VALUE) \
237 fxDECLARE_Dictionary(DICT,KEY,VALUE)
238 #define fxDECLARE_ObjKeyDictionary(DICT,KEY,VALUE) \
239 fxDECLARE_Dictionary(DICT,KEY,VALUE)
240
241 //----------------------------------------------------------------------
242 // Dictionary method macros. Used by the implement macros.
243
244 #define fxIMPLEMENT_DictionaryMethods(DICT,KEY,VALUE) \
245 DICT::DICT(u_int initsize) : \
246 fxDictionary(sizeof(KEY),sizeof(VALUE),initsize) {} \
247 DICT::~DICT() { cleanup(); } \
248 char const *DICT::className() const { return fxQUOTE(DICT); } \
249 fxIMPLEMENT_DictIter(DICT,KEY,VALUE) \
250 __enddef__
251
252 #define fxIMPLEMENT_StrKeyDictionaryMethods(DICT,VALUE) \
253 fxIMPLEMENT_copyObj(DICT,Key,fxStr) \
254 fxIMPLEMENT_destroyObj(DICT,Key,fxStr) \
255 u_long DICT::hashKey(const void* key) const \
256 { return ((const fxStr*)key)->hash(); } \
257 int DICT::compareKeys(const void* key1, const void* key2) const \
258 { return ::compare(*(const fxStr*)key1,*(const fxStr*)key2); } \
259 __enddef__
260
261 #define fxIMPLEMENT_ObjKeyDictionaryMethods(DICT,KEY,VALUE) \
262 fxIMPLEMENT_copyObj(DICT,Key,KEY) \
263 fxIMPLEMENT_destroyObj(DICT,Key,KEY) \
264 int DICT::compareKeys(const void* key1, const void* key2) const \
265 { return ((const KEY*)key1)->compare((const KEY*)key2); } \
266 __enddef__
267
268 #define fxIMPLEMENT_PtrKeyDictionaryMethods(DICT,KEY,VALUE) \
269 fxIMPLEMENT_copyPtr(DICT,Key,KEY) \
270 fxIMPLEMENT_destroyPtr(DICT,Key,KEY) \
271 u_long DICT::hashKey(const void* key) const \
272 { return u_long(((*(const u_int*)(key)) >> 2)); } \
273 int DICT::compareKeys(const void* key1, const void* key2) const \
274 { return (*(const char**)key1 - *(const char**)key2); } \
275 __enddef__
276
277 #define fxIMPLEMENT_ObjValueDictionaryMethods(DICT,VALUE) \
278 fxIMPLEMENT_copyObj(DICT,Value,VALUE) \
279 fxIMPLEMENT_destroyObj(DICT,Value,VALUE) \
280 fxIMPLEMENT_createObj(DICT,Value,VALUE) \
281 __enddef__
282
283 #define fxIMPLEMENT_PtrValueDictionaryMethods(DICT,VALUE) \
284 fxIMPLEMENT_copyPtr(DICT,Value,VALUE) \
285 fxIMPLEMENT_destroyPtr(DICT,Value,VALUE) \
286 fxIMPLEMENT_createPtr(DICT,Value,VALUE) \
287 __enddef__
288
289 //----------------------------------------------------------------------
290 // Dictionary implementation macros. These are used by the programmer
291 // to implement new dictionary types.
292
293 #define fxIMPLEMENT_Dictionary(DICT,KEY,VALUE) \
294 fxIMPLEMENT_DictionaryMethods(DICT,KEY,VALUE) \
295 __enddef__
296
297 #define fxIMPLEMENT_StrKeyDictionary(DICT,VALUE) \
298 fxIMPLEMENT_DictionaryMethods(DICT,fxStr,VALUE) \
299 fxIMPLEMENT_StrKeyDictionaryMethods(DICT,VALUE) \
300 __enddef__
301
302 #define fxIMPLEMENT_ObjKeyDictionary(DICT,KEY,VALUE) \
303 fxIMPLEMENT_DictionaryMethods(DICT,KEY,VALUE) \
304 fxIMPLEMENT_ObjKeyDictionaryMethods(DICT,KEY,VALUE) \
305 __enddef__
306
307 #define fxIMPLEMENT_PtrKeyDictionary(DICT,KEY,VALUE) \
308 fxIMPLEMENT_DictionaryMethods(DICT,KEY,VALUE) \
309 fxIMPLEMENT_PtrKeyDictionaryMethods(DICT,KEY,VALUE) \
310 __enddef__
311
312 #define fxIMPLEMENT_ObjValueDictionary(DICT,VALUE) \
313 fxIMPLEMENT_ObjValueDictionaryMethods(DICT,VALUE) \
314 __enddef__
315
316 #define fxIMPLEMENT_PtrValueDictionary(DICT,VALUE) \
317 fxIMPLEMENT_PtrValueDictionaryMethods(DICT,VALUE) \
318 __enddef__
319
320 #define fxIMPLEMENT_ObjKeyObjValueDictionary(DICT,VALUE) \
321 fxIMPLEMENT_DictionaryMethods(DICT,KEY,VALUE) \
322 fxIMPLEMENT_ObjKeyDictionaryMethods(DICT, VALUE) \
323 fxIMPLEMENT_ObjValueDictionaryMethods(DICT, VALUE) \
324 __enddef__
325
326 #define fxIMPLEMENT_StrKeyObjValueDictionary(DICT,VALUE) \
327 fxIMPLEMENT_DictionaryMethods(DICT,fxStr,VALUE) \
328 fxIMPLEMENT_StrKeyDictionaryMethods(DICT, VALUE) \
329 fxIMPLEMENT_ObjValueDictionaryMethods(DICT, VALUE) \
330 __enddef__
331
332 #define fxIMPLEMENT_StrKeyPtrValueDictionary(DICT,VALUE) \
333 fxIMPLEMENT_DictionaryMethods(DICT,fxStr,VALUE) \
334 fxIMPLEMENT_StrKeyDictionaryMethods(DICT,VALUE) \
335 fxIMPLEMENT_PtrValueDictionaryMethods(DICT,VALUE) \
336 __enddef__
337
338 #define fxIMPLEMENT_PtrKeyPtrValueDictionary(DICT,KEY,VALUE) \
339 fxIMPLEMENT_DictionaryMethods(DICT,KEY,VALUE) \
340 fxIMPLEMENT_PtrKeyDictionaryMethods(DICT,KEY,VALUE) \
341 fxIMPLEMENT_PtrValueDictionaryMethods(DICT,VALUE) \
342 __enddef__
343
344 #define fxIMPLEMENT_PtrKeyObjValueDictionary(DICT,KEY,VALUE) \
345 fxIMPLEMENT_DictionaryMethods(DICT,KEY,VALUE) \
346 fxIMPLEMENT_PtrKeyDictionaryMethods(DICT,KEY,VALUE) \
347 fxIMPLEMENT_ObjValueDictionaryMethods(DICT,VALUE) \
348 __enddef__
349 #endif /* _Dictionary_ */
350