]> git.saurik.com Git - wxWidgets.git/blob - include/wx/hash.h
Initial import of wxWebKitCtrl sources and htmlctrl (right now wxWebKit) sample.
[wxWidgets.git] / include / wx / hash.h
1 /////////////////////////////////////////////////////////////////////////////
2 // Name: wx/hash.h
3 // Purpose: wxHashTable class
4 // Author: Julian Smart
5 // Modified by: VZ at 25.02.00: type safe hashes with WX_DECLARE_HASH()
6 // Created: 01/02/97
7 // RCS-ID: $Id$
8 // Copyright: (c)
9 // Licence: wxWindows licence
10 /////////////////////////////////////////////////////////////////////////////
11
12 #ifndef _WX_HASH_H__
13 #define _WX_HASH_H__
14
15 #if defined(__GNUG__) && !defined(NO_GCC_PRAGMA)
16 #pragma interface "hash.h"
17 #endif
18
19 #include "wx/defs.h"
20
21 #if !wxUSE_STL && WXWIN_COMPATIBILITY_2_4
22 #define wxUSE_OLD_HASH_TABLE 1
23 #else
24 #define wxUSE_OLD_HASH_TABLE 0
25 #endif
26
27 #if !wxUSE_STL
28 #include "wx/object.h"
29 #else
30 class WXDLLIMPEXP_BASE wxObject;
31 #endif
32 #if wxUSE_OLD_HASH_TABLE
33 #include "wx/list.h"
34 #endif
35 #if WXWIN_COMPATIBILITY_2_4
36 #include "wx/dynarray.h"
37 #endif
38
39 // the default size of the hash
40 #define wxHASH_SIZE_DEFAULT (1000)
41
42 /*
43 * A hash table is an array of user-definable size with lists
44 * of data items hanging off the array positions. Usually there'll
45 * be a hit, so no search is required; otherwise we'll have to run down
46 * the list to find the desired item.
47 */
48
49 // ----------------------------------------------------------------------------
50 // this is the base class for object hashes: hash tables which contain
51 // pointers to objects
52 // ----------------------------------------------------------------------------
53
54 #if wxUSE_OLD_HASH_TABLE
55
56 class WXDLLIMPEXP_BASE wxHashTableBase : public wxObject
57 {
58 public:
59 wxHashTableBase();
60
61 void Create(wxKeyType keyType = wxKEY_INTEGER,
62 size_t size = wxHASH_SIZE_DEFAULT);
63 void Destroy();
64
65 size_t GetSize() const { return m_hashSize; }
66 size_t GetCount() const { return m_count; }
67
68 void DeleteContents(bool flag);
69
70 protected:
71 // find the node for (key, value)
72 wxNodeBase *GetNode(long key, long value) const;
73
74 // the array of lists in which we store the values for given key hash
75 wxListBase **m_hashTable;
76
77 // the size of m_lists array
78 size_t m_hashSize;
79
80 // the type of indexing we use
81 wxKeyType m_keyType;
82
83 // the total number of elements in the hash
84 size_t m_count;
85
86 // should we delete our data?
87 bool m_deleteContents;
88
89 private:
90 // no copy ctor/assignment operator (yet)
91 DECLARE_NO_COPY_CLASS(wxHashTableBase)
92 };
93
94 #else // if !wxUSE_OLD_HASH_TABLE
95
96 #if !defined(wxENUM_KEY_TYPE_DEFINED)
97 #define wxENUM_KEY_TYPE_DEFINED
98
99 enum wxKeyType
100 {
101 wxKEY_NONE,
102 wxKEY_INTEGER,
103 wxKEY_STRING
104 };
105
106 #endif
107
108 union wxHashKeyValue
109 {
110 long integer;
111 wxChar *string;
112 };
113
114 class WXDLLIMPEXP_BASE wxHashTableBase_Node
115 {
116 friend class WXDLLIMPEXP_BASE wxHashTableBase;
117 typedef class WXDLLIMPEXP_BASE wxHashTableBase_Node _Node;
118 public:
119 wxHashTableBase_Node( long key, void* value,
120 wxHashTableBase* table );
121 wxHashTableBase_Node( const wxChar* key, void* value,
122 wxHashTableBase* table );
123 ~wxHashTableBase_Node();
124
125 long GetKeyInteger() const { return m_key.integer; }
126 const wxChar* GetKeyString() const { return m_key.string; }
127
128 void* GetData() const { return m_value; }
129 void SetData( void* data ) { m_value = data; }
130
131 protected:
132 _Node* GetNext() const { return m_next; }
133
134 protected:
135 // next node in the chain
136 wxHashTableBase_Node* m_next;
137
138 // key
139 wxHashKeyValue m_key;
140
141 // value
142 void* m_value;
143
144 // pointer to the hash containing the node, used to remove the
145 // node from the hash when the user deletes the node iterating
146 // through it
147 // TODO: move it to wxHashTable_Node (only wxHashTable supports
148 // iteration)
149 wxHashTableBase* m_hashPtr;
150 };
151
152 class WXDLLIMPEXP_BASE wxHashTableBase
153 #if !wxUSE_STL
154 : public wxObject
155 #endif
156 {
157 friend class WXDLLIMPEXP_BASE wxHashTableBase_Node;
158 public:
159 typedef wxHashTableBase_Node Node;
160
161 wxHashTableBase();
162 virtual ~wxHashTableBase() { };
163
164 void Create( wxKeyType keyType = wxKEY_INTEGER,
165 size_t size = wxHASH_SIZE_DEFAULT );
166 void Clear();
167 void Destroy();
168
169 size_t GetSize() const { return m_size; }
170 size_t GetCount() const { return m_count; }
171
172 void DeleteContents( bool flag ) { m_deleteContents = flag; }
173
174 static long MakeKey(const wxChar *string);
175
176 protected:
177 void DoPut( long key, long hash, void* data );
178 void DoPut( const wxChar* key, long hash, void* data );
179 void* DoGet( long key, long hash ) const;
180 void* DoGet( const wxChar* key, long hash ) const;
181 void* DoDelete( long key, long hash );
182 void* DoDelete( const wxChar* key, long hash );
183
184 private:
185 // Remove the node from the hash, *only called from
186 // ~wxHashTable*_Node destructor
187 void DoRemoveNode( wxHashTableBase_Node* node );
188
189 // destroys data contained in the node if appropriate:
190 // deletes the key if it is a string and destrys
191 // the value if m_deleteContents is true
192 void DoDestroyNode( wxHashTableBase_Node* node );
193
194 // inserts a node in the table (at the end of the chain)
195 void DoInsertNode( size_t bucket, wxHashTableBase_Node* node );
196
197 // removes a node from the table (fiven a pointer to the previous
198 // but does not delete it (only deletes its contents)
199 void DoUnlinkNode( size_t bucket, wxHashTableBase_Node* node,
200 wxHashTableBase_Node* prev );
201
202 // unconditionally deletes node value (invoking the
203 // correct destructor)
204 virtual void DoDeleteContents( wxHashTableBase_Node* node ) = 0;
205
206 protected:
207 // number of buckets
208 size_t m_size;
209
210 // number of nodes (key/value pairs)
211 size_t m_count;
212
213 // table
214 Node** m_table;
215
216 // key typ (INTEGER/STRING)
217 wxKeyType m_keyType;
218
219 // delete contents when hash is cleared
220 bool m_deleteContents;
221
222 private:
223 DECLARE_NO_COPY_CLASS(wxHashTableBase)
224 };
225
226 #endif // wxUSE_OLD_HASH_TABLE
227
228 #if !wxUSE_STL
229
230 #if WXWIN_COMPATIBILITY_2_4
231
232 // ----------------------------------------------------------------------------
233 // a hash table which stores longs
234 // ----------------------------------------------------------------------------
235
236 class WXDLLIMPEXP_BASE wxHashTableLong : public wxObject
237 {
238 public:
239 wxHashTableLong(size_t size = wxHASH_SIZE_DEFAULT)
240 { Init(size); }
241 virtual ~wxHashTableLong();
242
243 void Create(size_t size = wxHASH_SIZE_DEFAULT);
244 void Destroy();
245
246 size_t GetSize() const { return m_hashSize; }
247 size_t GetCount() const { return m_count; }
248
249 void Put(long key, long value);
250 long Get(long key) const;
251 long Delete(long key);
252
253 protected:
254 void Init(size_t size);
255
256 private:
257 wxArrayLong **m_values,
258 **m_keys;
259
260 // the size of array above
261 size_t m_hashSize;
262
263 // the total number of elements in the hash
264 size_t m_count;
265
266 // not implemented yet
267 DECLARE_NO_COPY_CLASS(wxHashTableLong)
268 };
269
270 // ----------------------------------------------------------------------------
271 // wxStringHashTable: a hash table which indexes strings with longs
272 // ----------------------------------------------------------------------------
273
274 class WXDLLIMPEXP_BASE wxStringHashTable : public wxObject
275 {
276 public:
277 wxStringHashTable(size_t sizeTable = wxHASH_SIZE_DEFAULT);
278 virtual ~wxStringHashTable();
279
280 // add a string associated with this key to the table
281 void Put(long key, const wxString& value);
282
283 // get the string from the key: if not found, an empty string is returned
284 // and the wasFound is set to FALSE if not NULL
285 wxString Get(long key, bool *wasFound = NULL) const;
286
287 // remove the item, returning TRUE if the item was found and deleted
288 bool Delete(long key) const;
289
290 // clean up
291 void Destroy();
292
293 private:
294 wxArrayLong **m_keys;
295 wxArrayString **m_values;
296
297 // the size of array above
298 size_t m_hashSize;
299
300 DECLARE_NO_COPY_CLASS(wxStringHashTable)
301 };
302
303 #endif // WXWIN_COMPATIBILITY_2_4
304
305 #endif // !wxUSE_STL
306
307 // ----------------------------------------------------------------------------
308 // for compatibility only
309 // ----------------------------------------------------------------------------
310
311 #if !wxUSE_OLD_HASH_TABLE
312
313 class WXDLLIMPEXP_BASE wxHashTable_Node : public wxHashTableBase_Node
314 {
315 friend class WXDLLIMPEXP_BASE wxHashTable;
316 public:
317 wxHashTable_Node( long key, void* value,
318 wxHashTableBase* table )
319 : wxHashTableBase_Node( key, value, table ) { }
320 wxHashTable_Node( const wxChar* key, void* value,
321 wxHashTableBase* table )
322 : wxHashTableBase_Node( key, value, table ) { }
323
324 wxObject* GetData() const
325 { return (wxObject*)wxHashTableBase_Node::GetData(); }
326 void SetData( wxObject* data )
327 { wxHashTableBase_Node::SetData( data ); }
328
329 wxHashTable_Node* GetNext() const
330 { return (wxHashTable_Node*)wxHashTableBase_Node::GetNext(); }
331 };
332
333 // should inherit protectedly, but it is public for compatibility in
334 // order to publicly inherit from wxObject
335 class WXDLLIMPEXP_BASE wxHashTable : public wxHashTableBase
336 {
337 typedef wxHashTableBase hash;
338 public:
339 typedef wxHashTable_Node Node;
340 typedef wxHashTable_Node* compatibility_iterator;
341 public:
342 wxHashTable( wxKeyType keyType = wxKEY_INTEGER,
343 size_t size = wxHASH_SIZE_DEFAULT )
344 : wxHashTableBase() { Create( keyType, size ); BeginFind(); }
345 wxHashTable( const wxHashTable& table );
346
347 virtual ~wxHashTable() { Destroy(); }
348
349 const wxHashTable& operator=( const wxHashTable& );
350
351 void Destroy() { Clear(); }
352
353 // key and value are the same
354 void Put(long value, wxObject *object)
355 { DoPut( value, value, object ); }
356 void Put(long hash, long value, wxObject *object)
357 { DoPut( value, hash, object ); }
358 void Put(const wxChar *value, wxObject *object)
359 { DoPut( value, MakeKey( value ), object ); }
360 void Put(long hash, const wxChar *value, wxObject *object)
361 { DoPut( value, hash, object ); }
362
363 // key and value are the same
364 wxObject *Get(long value) const
365 { return (wxObject*)DoGet( value, value ); }
366 wxObject *Get(long hash, long value) const
367 { return (wxObject*)DoGet( value, hash ); }
368 wxObject *Get(const wxChar *value) const
369 { return (wxObject*)DoGet( value, MakeKey( value ) ); }
370 wxObject *Get(long hash, const wxChar *value) const
371 { return (wxObject*)DoGet( value, hash ); }
372
373 // Deletes entry and returns data if found
374 wxObject *Delete(long key)
375 { return (wxObject*)DoDelete( key, key ); }
376 wxObject *Delete(long hash, long key)
377 { return (wxObject*)DoDelete( key, hash ); }
378 wxObject *Delete(const wxChar *key)
379 { return (wxObject*)DoDelete( key, MakeKey( key ) ); }
380 wxObject *Delete(long hash, const wxChar *key)
381 { return (wxObject*)DoDelete( key, hash ); }
382
383 // Construct your own integer key from a string, e.g. in case
384 // you need to combine it with something
385 long MakeKey(const wxChar *string) const
386 { return wxHashTableBase::MakeKey(string); }
387
388 // Way of iterating through whole hash table (e.g. to delete everything)
389 // Not necessary, of course, if you're only storing pointers to
390 // objects maintained separately
391 void BeginFind() { m_curr = NULL; m_currBucket = 0; }
392 Node* Next();
393
394 void Clear() { wxHashTableBase::Clear(); }
395
396 size_t GetCount() const { return wxHashTableBase::GetCount(); }
397 protected:
398 virtual void DoDeleteContents( wxHashTableBase_Node* node );
399
400 // copy helper
401 void DoCopy( const wxHashTable& copy );
402
403 // searches the next node starting from bucket bucketStart and sets
404 // m_curr to it and m_currBucket to its bucket
405 void GetNextNode( size_t bucketStart );
406 private:
407 // current node
408 Node* m_curr;
409
410 // bucket the current node belongs to
411 size_t m_currBucket;
412 };
413
414 #else // if wxUSE_OLD_HASH_TABLE
415
416 class WXDLLIMPEXP_BASE wxHashTable : public wxObject
417 {
418 public:
419 typedef wxNode Node;
420 typedef wxNode* compatibility_iterator;
421
422 int n;
423 int current_position;
424 wxNode *current_node;
425
426 unsigned int key_type;
427 wxList **hash_table;
428
429 wxHashTable(int the_key_type = wxKEY_INTEGER,
430 int size = wxHASH_SIZE_DEFAULT);
431 ~wxHashTable();
432
433 // copy ctor and assignment operator
434 wxHashTable(const wxHashTable& table) : wxObject()
435 { DoCopy(table); }
436 wxHashTable& operator=(const wxHashTable& table)
437 { Clear(); DoCopy(table); return *this; }
438
439 void DoCopy(const wxHashTable& table);
440
441 void Destroy();
442
443 bool Create(int the_key_type = wxKEY_INTEGER,
444 int size = wxHASH_SIZE_DEFAULT);
445
446 // Note that there are 2 forms of Put, Get.
447 // With a key and a value, the *value* will be checked
448 // when a collision is detected. Otherwise, if there are
449 // 2 items with a different value but the same key,
450 // we'll retrieve the WRONG ONE. So where possible,
451 // supply the required value along with the key.
452 // In fact, the value-only versions make a key, and still store
453 // the value. The use of an explicit key might be required
454 // e.g. when combining several values into one key.
455 // When doing that, it's highly likely we'll get a collision,
456 // e.g. 1 + 2 = 3, 2 + 1 = 3.
457
458 // key and value are NOT necessarily the same
459 void Put(long key, long value, wxObject *object);
460 void Put(long key, const wxChar *value, wxObject *object);
461
462 // key and value are the same
463 void Put(long value, wxObject *object);
464 void Put(const wxChar *value, wxObject *object);
465
466 // key and value not the same
467 wxObject *Get(long key, long value) const;
468 wxObject *Get(long key, const wxChar *value) const;
469
470 // key and value are the same
471 wxObject *Get(long value) const;
472 wxObject *Get(const wxChar *value) const;
473
474 // Deletes entry and returns data if found
475 wxObject *Delete(long key);
476 wxObject *Delete(const wxChar *key);
477
478 wxObject *Delete(long key, int value);
479 wxObject *Delete(long key, const wxChar *value);
480
481 // Construct your own integer key from a string, e.g. in case
482 // you need to combine it with something
483 long MakeKey(const wxChar *string) const;
484
485 // Way of iterating through whole hash table (e.g. to delete everything)
486 // Not necessary, of course, if you're only storing pointers to
487 // objects maintained separately
488
489 void BeginFind();
490 Node* Next();
491
492 void DeleteContents(bool flag);
493 void Clear();
494
495 // Returns number of nodes
496 size_t GetCount() const { return m_count; }
497
498 private:
499 size_t m_count; // number of elements in the hashtable
500 bool m_deleteContents;
501
502 DECLARE_DYNAMIC_CLASS(wxHashTable)
503 };
504
505 #endif // wxUSE_OLD_HASH_TABLE
506
507 #if !wxUSE_OLD_HASH_TABLE
508
509 // defines a new type safe hash table which stores the elements of type eltype
510 // in lists of class listclass
511 #define _WX_DECLARE_HASH(eltype, dummy, hashclass, classexp) \
512 classexp hashclass : public wxHashTableBase \
513 { \
514 public: \
515 hashclass(wxKeyType keyType = wxKEY_INTEGER, \
516 size_t size = wxHASH_SIZE_DEFAULT) \
517 : wxHashTableBase() { Create(keyType, size); } \
518 \
519 virtual ~hashclass() { Destroy(); } \
520 \
521 void Destroy() { Clear(); } \
522 void Put(long key, eltype *data) { DoPut(key, key, (void*)data); } \
523 void Put(long hash, long key, eltype *data) \
524 { DoPut(key, hash, (void*)data); } \
525 eltype *Get(long key) const { return (eltype*)DoGet(key, key); } \
526 eltype *Get(long hash, long key) const \
527 { return (eltype*)DoGet(key, hash); } \
528 eltype *Delete(long key) { return (eltype*)DoDelete(key, key); } \
529 eltype *Delete(long hash, long key) \
530 { return (eltype*)DoDelete(key, hash); } \
531 protected: \
532 virtual void DoDeleteContents( wxHashTableBase_Node* node ) \
533 { delete (eltype*)node->GetData(); } \
534 \
535 DECLARE_NO_COPY_CLASS(hashclass) \
536 }
537
538 #else // if wxUSE_OLD_HASH_TABLE
539
540 #define _WX_DECLARE_HASH(eltype, listclass, hashclass, classexp) \
541 classexp hashclass : public wxHashTableBase \
542 { \
543 public: \
544 hashclass(wxKeyType keyType = wxKEY_INTEGER, \
545 size_t size = wxHASH_SIZE_DEFAULT) \
546 { Create(keyType, size); } \
547 \
548 ~hashclass() { Destroy(); } \
549 \
550 void Put(long key, long val, eltype *data) { DoPut(key, val, data); } \
551 void Put(long key, eltype *data) { DoPut(key, key, data); } \
552 \
553 eltype *Get(long key, long value) const \
554 { \
555 wxNodeBase *node = GetNode(key, value); \
556 return node ? ((listclass::Node *)node)->GetData() : (eltype *)0; \
557 } \
558 eltype *Get(long key) const { return Get(key, key); } \
559 \
560 eltype *Delete(long key, long value) \
561 { \
562 eltype *data; \
563 \
564 wxNodeBase *node = GetNode(key, value); \
565 if ( node ) \
566 { \
567 data = ((listclass::Node *)node)->GetData(); \
568 \
569 delete node; \
570 m_count--; \
571 } \
572 else \
573 { \
574 data = (eltype *)0; \
575 } \
576 \
577 return data; \
578 } \
579 eltype *Delete(long key) { return Delete(key, key); } \
580 \
581 protected: \
582 void DoPut(long key, long value, eltype *data) \
583 { \
584 size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); \
585 \
586 if ( !m_hashTable[slot] ) \
587 { \
588 m_hashTable[slot] = new listclass(m_keyType); \
589 if ( m_deleteContents ) \
590 m_hashTable[slot]->DeleteContents(TRUE); \
591 } \
592 \
593 ((listclass *)m_hashTable[slot])->Append(value, data); \
594 m_count++; \
595 } \
596 \
597 DECLARE_NO_COPY_CLASS(hashclass) \
598 }
599
600 #endif // wxUSE_OLD_HASH_TABLE
601
602 // this macro is to be used in the user code
603 #define WX_DECLARE_HASH(el, list, hash) \
604 _WX_DECLARE_HASH(el, list, hash, class)
605
606 // and this one does exactly the same thing but should be used inside the
607 // library
608 #define WX_DECLARE_EXPORTED_HASH(el, list, hash) \
609 _WX_DECLARE_HASH(el, list, hash, class WXDLLEXPORT)
610
611 #define WX_DECLARE_USER_EXPORTED_HASH(el, list, hash, usergoo) \
612 _WX_DECLARE_HASH(el, list, hash, class usergoo)
613
614 // delete all hash elements
615 //
616 // NB: the class declaration of the hash elements must be visible from the
617 // place where you use this macro, otherwise the proper destructor may not
618 // be called (a decent compiler should give a warning about it, but don't
619 // count on it)!
620 #define WX_CLEAR_HASH_TABLE(hash) \
621 { \
622 (hash).BeginFind(); \
623 wxHashTable::compatibility_iterator it = (hash).Next(); \
624 while( it ) \
625 { \
626 delete it->GetData(); \
627 it = (hash).Next(); \
628 } \
629 (hash).Clear(); \
630 }
631
632 #endif
633 // _WX_HASH_H__