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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 31 - (hide annotations) (download)
Tue Sep 7 03:24:11 2010 UTC (9 years, 10 months ago) by william
Original Path: trunk/3rdparty/wxWidgets/include/wx/hash.h
File MIME type: text/plain
File size: 23374 byte(s)
committing r3113 initial commit again...
1 william 31 /////////////////////////////////////////////////////////////////////////////
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