/[pcsx2_0.9.7]/branch/r3113_0.9.7_beta/3rdparty/wxWidgets/include/wx/hash.h
ViewVC logotype

Contents of /branch/r3113_0.9.7_beta/3rdparty/wxWidgets/include/wx/hash.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 32 - (show annotations) (download)
Tue Sep 7 03:29:01 2010 UTC (9 years, 5 months ago) by william
File MIME type: text/plain
File size: 23374 byte(s)
branching from upstream revision (http://pcsx2.googlecode.com/svn/trunk
): r3113 to
https://svn.netsolutions.dnsalias.com/websvn/ps2/pcsx2/pcsx2_0.9.7/branch/r3113_0.9.7_beta
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: hash.h 53135 2008-04-12 02:31:04Z VZ $
8 // Copyright: (c) Julian Smart
9 // Licence: wxWindows licence
10 /////////////////////////////////////////////////////////////////////////////
11
12 #ifndef _WX_HASH_H__
13 #define _WX_HASH_H__
14
15 #include "wx/defs.h"
16
17 #if !wxUSE_STL && WXWIN_COMPATIBILITY_2_4
18 #define wxUSE_OLD_HASH_TABLE 1
19 #else
20 #define wxUSE_OLD_HASH_TABLE 0
21 #endif
22
23 #if !wxUSE_STL
24 #include "wx/object.h"
25 #else
26 class WXDLLIMPEXP_BASE wxObject;
27 #endif
28 #if wxUSE_OLD_HASH_TABLE
29 #include "wx/list.h"
30 #endif
31 #if WXWIN_COMPATIBILITY_2_4
32 #include "wx/dynarray.h"
33 #endif
34
35 // the default size of the hash
36 #define wxHASH_SIZE_DEFAULT (1000)
37
38 /*
39 * A hash table is an array of user-definable size with lists
40 * of data items hanging off the array positions. Usually there'll
41 * be a hit, so no search is required; otherwise we'll have to run down
42 * the list to find the desired item.
43 */
44
45 // ----------------------------------------------------------------------------
46 // this is the base class for object hashes: hash tables which contain
47 // pointers to objects
48 // ----------------------------------------------------------------------------
49
50 #if wxUSE_OLD_HASH_TABLE
51
52 class WXDLLIMPEXP_BASE wxHashTableBase : public wxObject
53 {
54 public:
55 wxHashTableBase();
56
57 void Create(wxKeyType keyType = wxKEY_INTEGER,
58 size_t size = wxHASH_SIZE_DEFAULT);
59 void Destroy();
60
61 size_t GetSize() const { return m_hashSize; }
62 size_t GetCount() const { return m_count; }
63
64 void DeleteContents(bool flag);
65
66 protected:
67 // find the node for (key, value)
68 wxNodeBase *GetNode(long key, long value) const;
69
70 // the array of lists in which we store the values for given key hash
71 wxListBase **m_hashTable;
72
73 // the size of m_lists array
74 size_t m_hashSize;
75
76 // the type of indexing we use
77 wxKeyType m_keyType;
78
79 // the total number of elements in the hash
80 size_t m_count;
81
82 // should we delete our data?
83 bool m_deleteContents;
84
85 private:
86 // no copy ctor/assignment operator (yet)
87 DECLARE_NO_COPY_CLASS(wxHashTableBase)
88 };
89
90 #else // if !wxUSE_OLD_HASH_TABLE
91
92 #if !defined(wxENUM_KEY_TYPE_DEFINED)
93 #define wxENUM_KEY_TYPE_DEFINED
94
95 enum wxKeyType
96 {
97 wxKEY_NONE,
98 wxKEY_INTEGER,
99 wxKEY_STRING
100 };
101
102 #endif
103
104 union wxHashKeyValue
105 {
106 long integer;
107 wxChar *string;
108 };
109
110 // for some compilers (AIX xlC), defining it as friend inside the class is not
111 // enough, so provide a real forward declaration
112 class WXDLLIMPEXP_FWD_BASE wxHashTableBase;
113
114 class WXDLLIMPEXP_BASE wxHashTableBase_Node
115 {
116 friend class WXDLLIMPEXP_FWD_BASE wxHashTableBase;
117 typedef class WXDLLIMPEXP_FWD_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_FWD_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_FWD_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 // key and value are the same
352 void Put(long value, wxObject *object)
353 { DoPut( value, value, object ); }
354 void Put(long lhash, long value, wxObject *object)
355 { DoPut( value, lhash, object ); }
356 void Put(const wxChar *value, wxObject *object)
357 { DoPut( value, MakeKey( value ), object ); }
358 void Put(long lhash, const wxChar *value, wxObject *object)
359 { DoPut( value, lhash, object ); }
360
361 // key and value are the same
362 wxObject *Get(long value) const
363 { return (wxObject*)DoGet( value, value ); }
364 wxObject *Get(long lhash, long value) const
365 { return (wxObject*)DoGet( value, lhash ); }
366 wxObject *Get(const wxChar *value) const
367 { return (wxObject*)DoGet( value, MakeKey( value ) ); }
368 wxObject *Get(long lhash, const wxChar *value) const
369 { return (wxObject*)DoGet( value, lhash ); }
370
371 // Deletes entry and returns data if found
372 wxObject *Delete(long key)
373 { return (wxObject*)DoDelete( key, key ); }
374 wxObject *Delete(long lhash, long key)
375 { return (wxObject*)DoDelete( key, lhash ); }
376 wxObject *Delete(const wxChar *key)
377 { return (wxObject*)DoDelete( key, MakeKey( key ) ); }
378 wxObject *Delete(long lhash, const wxChar *key)
379 { return (wxObject*)DoDelete( key, lhash ); }
380
381 // Construct your own integer key from a string, e.g. in case
382 // you need to combine it with something
383 long MakeKey(const wxChar *string) const
384 { return wxHashTableBase::MakeKey(string); }
385
386 // Way of iterating through whole hash table (e.g. to delete everything)
387 // Not necessary, of course, if you're only storing pointers to
388 // objects maintained separately
389 void BeginFind() { m_curr = NULL; m_currBucket = 0; }
390 Node* Next();
391
392 void Clear() { wxHashTableBase::Clear(); }
393
394 size_t GetCount() const { return wxHashTableBase::GetCount(); }
395 protected:
396 // copy helper
397 void DoCopy( const wxHashTable& copy );
398
399 // searches the next node starting from bucket bucketStart and sets
400 // m_curr to it and m_currBucket to its bucket
401 void GetNextNode( size_t bucketStart );
402 private:
403 virtual void DoDeleteContents( wxHashTableBase_Node* node );
404
405 // current node
406 Node* m_curr;
407
408 // bucket the current node belongs to
409 size_t m_currBucket;
410 };
411
412 #else // if wxUSE_OLD_HASH_TABLE
413
414 class WXDLLIMPEXP_BASE wxHashTable : public wxObject
415 {
416 public:
417 typedef wxNode Node;
418 typedef wxNode* compatibility_iterator;
419
420 int n;
421 int current_position;
422 wxNode *current_node;
423
424 unsigned int key_type;
425 wxList **hash_table;
426
427 wxHashTable(int the_key_type = wxKEY_INTEGER,
428 int size = wxHASH_SIZE_DEFAULT);
429 virtual ~wxHashTable();
430
431 // copy ctor and assignment operator
432 wxHashTable(const wxHashTable& table) : wxObject()
433 { DoCopy(table); }
434 wxHashTable& operator=(const wxHashTable& table)
435 { Clear(); DoCopy(table); return *this; }
436
437 void DoCopy(const wxHashTable& table);
438
439 void Destroy();
440
441 bool Create(int the_key_type = wxKEY_INTEGER,
442 int size = wxHASH_SIZE_DEFAULT);
443
444 // Note that there are 2 forms of Put, Get.
445 // With a key and a value, the *value* will be checked
446 // when a collision is detected. Otherwise, if there are
447 // 2 items with a different value but the same key,
448 // we'll retrieve the WRONG ONE. So where possible,
449 // supply the required value along with the key.
450 // In fact, the value-only versions make a key, and still store
451 // the value. The use of an explicit key might be required
452 // e.g. when combining several values into one key.
453 // When doing that, it's highly likely we'll get a collision,
454 // e.g. 1 + 2 = 3, 2 + 1 = 3.
455
456 // key and value are NOT necessarily the same
457 void Put(long key, long value, wxObject *object);
458 void Put(long key, const wxChar *value, wxObject *object);
459
460 // key and value are the same
461 void Put(long value, wxObject *object);
462 void Put(const wxChar *value, wxObject *object);
463
464 // key and value not the same
465 wxObject *Get(long key, long value) const;
466 wxObject *Get(long key, const wxChar *value) const;
467
468 // key and value are the same
469 wxObject *Get(long value) const;
470 wxObject *Get(const wxChar *value) const;
471
472 // Deletes entry and returns data if found
473 wxObject *Delete(long key);
474 wxObject *Delete(const wxChar *key);
475
476 wxObject *Delete(long key, int value);
477 wxObject *Delete(long key, const wxChar *value);
478
479 // Construct your own integer key from a string, e.g. in case
480 // you need to combine it with something
481 long MakeKey(const wxChar *string) const;
482
483 // Way of iterating through whole hash table (e.g. to delete everything)
484 // Not necessary, of course, if you're only storing pointers to
485 // objects maintained separately
486
487 void BeginFind();
488 Node* Next();
489
490 void DeleteContents(bool flag);
491 void Clear();
492
493 // Returns number of nodes
494 size_t GetCount() const { return m_count; }
495
496 private:
497 size_t m_count; // number of elements in the hashtable
498 bool m_deleteContents;
499
500 DECLARE_DYNAMIC_CLASS(wxHashTable)
501 };
502
503 #endif // wxUSE_OLD_HASH_TABLE
504
505 #if !wxUSE_OLD_HASH_TABLE
506
507 // defines a new type safe hash table which stores the elements of type eltype
508 // in lists of class listclass
509 #define _WX_DECLARE_HASH(eltype, dummy, hashclass, classexp) \
510 classexp hashclass : public wxHashTableBase \
511 { \
512 public: \
513 hashclass(wxKeyType keyType = wxKEY_INTEGER, \
514 size_t size = wxHASH_SIZE_DEFAULT) \
515 : wxHashTableBase() { Create(keyType, size); } \
516 \
517 virtual ~hashclass() { Destroy(); } \
518 \
519 void Put(long key, eltype *data) { DoPut(key, key, (void*)data); } \
520 void Put(long lhash, long key, eltype *data) \
521 { DoPut(key, lhash, (void*)data); } \
522 eltype *Get(long key) const { return (eltype*)DoGet(key, key); } \
523 eltype *Get(long lhash, long key) const \
524 { return (eltype*)DoGet(key, lhash); } \
525 eltype *Delete(long key) { return (eltype*)DoDelete(key, key); } \
526 eltype *Delete(long lhash, long key) \
527 { return (eltype*)DoDelete(key, lhash); } \
528 private: \
529 virtual void DoDeleteContents( wxHashTableBase_Node* node ) \
530 { delete (eltype*)node->GetData(); } \
531 \
532 DECLARE_NO_COPY_CLASS(hashclass) \
533 }
534
535 #else // if wxUSE_OLD_HASH_TABLE
536
537 #define _WX_DECLARE_HASH(eltype, listclass, hashclass, classexp) \
538 classexp hashclass : public wxHashTableBase \
539 { \
540 public: \
541 hashclass(wxKeyType keyType = wxKEY_INTEGER, \
542 size_t size = wxHASH_SIZE_DEFAULT) \
543 { Create(keyType, size); } \
544 \
545 virtual ~hashclass() { Destroy(); } \
546 \
547 void Put(long key, long val, eltype *data) { DoPut(key, val, data); } \
548 void Put(long key, eltype *data) { DoPut(key, key, data); } \
549 \
550 eltype *Get(long key, long value) const \
551 { \
552 wxNodeBase *node = GetNode(key, value); \
553 return node ? ((listclass::Node *)node)->GetData() : (eltype *)0; \
554 } \
555 eltype *Get(long key) const { return Get(key, key); } \
556 \
557 eltype *Delete(long key, long value) \
558 { \
559 eltype *data; \
560 \
561 wxNodeBase *node = GetNode(key, value); \
562 if ( node ) \
563 { \
564 data = ((listclass::Node *)node)->GetData(); \
565 \
566 delete node; \
567 m_count--; \
568 } \
569 else \
570 { \
571 data = (eltype *)0; \
572 } \
573 \
574 return data; \
575 } \
576 eltype *Delete(long key) { return Delete(key, key); } \
577 \
578 protected: \
579 void DoPut(long key, long value, eltype *data) \
580 { \
581 size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); \
582 \
583 if ( !m_hashTable[slot] ) \
584 { \
585 m_hashTable[slot] = new listclass(m_keyType); \
586 if ( m_deleteContents ) \
587 m_hashTable[slot]->DeleteContents(true); \
588 } \
589 \
590 ((listclass *)m_hashTable[slot])->Append(value, data); \
591 m_count++; \
592 } \
593 \
594 DECLARE_NO_COPY_CLASS(hashclass) \
595 }
596
597 #endif // wxUSE_OLD_HASH_TABLE
598
599 // this macro is to be used in the user code
600 #define WX_DECLARE_HASH(el, list, hash) \
601 _WX_DECLARE_HASH(el, list, hash, class)
602
603 // and this one does exactly the same thing but should be used inside the
604 // library
605 #define WX_DECLARE_EXPORTED_HASH(el, list, hash) \
606 _WX_DECLARE_HASH(el, list, hash, class WXDLLEXPORT)
607
608 #define WX_DECLARE_USER_EXPORTED_HASH(el, list, hash, usergoo) \
609 _WX_DECLARE_HASH(el, list, hash, class usergoo)
610
611 // delete all hash elements
612 //
613 // NB: the class declaration of the hash elements must be visible from the
614 // place where you use this macro, otherwise the proper destructor may not
615 // be called (a decent compiler should give a warning about it, but don't
616 // count on it)!
617 #define WX_CLEAR_HASH_TABLE(hash) \
618 { \
619 (hash).BeginFind(); \
620 wxHashTable::compatibility_iterator it = (hash).Next(); \
621 while( it ) \
622 { \
623 delete it->GetData(); \
624 it = (hash).Next(); \
625 } \
626 (hash).Clear(); \
627 }
628
629 #endif
630 // _WX_HASH_H__

  ViewVC Help
Powered by ViewVC 1.1.22