home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / wxos2240.zip / wxWindows-2.4.0 / include / wx / hash.h < prev    next >
C/C++ Source or Header  |  2002-08-31  |  12KB  |  310 lines
  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,v 1.20 2002/08/31 11:29:10 GD Exp $
  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(__APPLE__)
  16. #pragma interface "hash.h"
  17. #endif
  18.  
  19. #include "wx/list.h"
  20. #include "wx/dynarray.h"
  21.  
  22. // the default size of the hash
  23. #define wxHASH_SIZE_DEFAULT     (1000)
  24.  
  25. /*
  26.  * A hash table is an array of user-definable size with lists
  27.  * of data items hanging off the array positions.  Usually there'll
  28.  * be a hit, so no search is required; otherwise we'll have to run down
  29.  * the list to find the desired item.
  30. */
  31.  
  32. // ----------------------------------------------------------------------------
  33. // this is the base class for object hashes: hash tables which contain
  34. // pointers to objects
  35. // ----------------------------------------------------------------------------
  36.  
  37. class WXDLLEXPORT wxHashTableBase : public wxObject
  38. {
  39. public:
  40.     wxHashTableBase();
  41.  
  42.     void Create(wxKeyType keyType = wxKEY_INTEGER,
  43.                 size_t size = wxHASH_SIZE_DEFAULT);
  44.     void Destroy();
  45.  
  46.     size_t GetSize() const { return m_hashSize; }
  47.     size_t GetCount() const { return m_count; }
  48.  
  49.     void DeleteContents(bool flag);
  50.  
  51. protected:
  52.     // find the node for (key, value)
  53.     wxNodeBase *GetNode(long key, long value) const;
  54.  
  55.     // the array of lists in which we store the values for given key hash
  56.     wxListBase **m_hashTable;
  57.  
  58.     // the size of m_lists array
  59.     size_t m_hashSize;
  60.  
  61.     // the type of indexing we use
  62.     wxKeyType m_keyType;
  63.  
  64.     // the total number of elements in the hash
  65.     size_t m_count;
  66.  
  67.     // should we delete our data?
  68.     bool m_deleteContents;
  69.  
  70. private:
  71.     // no copy ctor/assignment operator (yet)
  72.     DECLARE_NO_COPY_CLASS(wxHashTableBase)
  73. };
  74.  
  75. // ----------------------------------------------------------------------------
  76. // a hash table which stores longs
  77. // ----------------------------------------------------------------------------
  78.  
  79. class WXDLLEXPORT wxHashTableLong : public wxObject
  80. {
  81. public:
  82.     wxHashTableLong(size_t size = wxHASH_SIZE_DEFAULT)
  83.         { Init(size); }
  84.     virtual ~wxHashTableLong();
  85.  
  86.     void Create(size_t size = wxHASH_SIZE_DEFAULT);
  87.     void Destroy();
  88.  
  89.     size_t GetSize() const { return m_hashSize; }
  90.     size_t GetCount() const { return m_count; }
  91.  
  92.     void Put(long key, long value);
  93.     long Get(long key) const;
  94.     long Delete(long key);
  95.  
  96. protected:
  97.     void Init(size_t size);
  98.  
  99. private:
  100.     wxArrayLong **m_values,
  101.                 **m_keys;
  102.  
  103.     // the size of array above
  104.     size_t m_hashSize;
  105.  
  106.     // the total number of elements in the hash
  107.     size_t m_count;
  108.  
  109.     // not implemented yet
  110.     DECLARE_NO_COPY_CLASS(wxHashTableLong)
  111. };
  112.  
  113. // ----------------------------------------------------------------------------
  114. // wxStringHashTable: a hash table which indexes strings with longs
  115. // ----------------------------------------------------------------------------
  116.  
  117. class WXDLLEXPORT wxStringHashTable : public wxObject
  118. {
  119. public:
  120.     wxStringHashTable(size_t sizeTable = wxHASH_SIZE_DEFAULT);
  121.     virtual ~wxStringHashTable();
  122.  
  123.     // add a string associated with this key to the table
  124.     void Put(long key, const wxString& value);
  125.  
  126.     // get the string from the key: if not found, an empty string is returned
  127.     // and the wasFound is set to FALSE if not NULL
  128.     wxString Get(long key, bool *wasFound = NULL) const;
  129.  
  130.     // remove the item, returning TRUE if the item was found and deleted
  131.     bool Delete(long key) const;
  132.  
  133.     // clean up
  134.     void Destroy();
  135.  
  136. private:
  137.     wxArrayLong **m_keys;
  138.     wxArrayString **m_values;
  139.  
  140.     // the size of array above
  141.     size_t m_hashSize;
  142.  
  143.     DECLARE_NO_COPY_CLASS(wxStringHashTable)
  144. };
  145.  
  146. // ----------------------------------------------------------------------------
  147. // for compatibility only
  148. // ----------------------------------------------------------------------------
  149.  
  150. class WXDLLEXPORT wxHashTable : public wxObject
  151. {
  152. public:
  153.     int n;
  154.     int current_position;
  155.     wxNode *current_node;
  156.  
  157.     unsigned int key_type;
  158.     wxList **hash_table;
  159.  
  160.     wxHashTable(int the_key_type = wxKEY_INTEGER,
  161.                 int size = wxHASH_SIZE_DEFAULT);
  162.     ~wxHashTable();
  163.  
  164.     // copy ctor and assignment operator
  165.     wxHashTable(const wxHashTable& table) : wxObject()
  166.         { DoCopy(table); }
  167.     wxHashTable& operator=(const wxHashTable& table)
  168.         { Clear(); DoCopy(table); return *this; }
  169.  
  170.     void DoCopy(const wxHashTable& table);
  171.  
  172.     void Destroy();
  173.  
  174.     bool Create(int the_key_type = wxKEY_INTEGER,
  175.                 int size = wxHASH_SIZE_DEFAULT);
  176.  
  177.     // Note that there are 2 forms of Put, Get.
  178.     // With a key and a value, the *value* will be checked
  179.     // when a collision is detected. Otherwise, if there are
  180.     // 2 items with a different value but the same key,
  181.     // we'll retrieve the WRONG ONE. So where possible,
  182.     // supply the required value along with the key.
  183.     // In fact, the value-only versions make a key, and still store
  184.     // the value. The use of an explicit key might be required
  185.     // e.g. when combining several values into one key.
  186.     // When doing that, it's highly likely we'll get a collision,
  187.     // e.g. 1 + 2 = 3, 2 + 1 = 3.
  188.  
  189.     // key and value are NOT necessarily the same
  190.     void Put(long key, long value, wxObject *object);
  191.     void Put(long key, const wxChar *value, wxObject *object);
  192.  
  193.     // key and value are the same
  194.     void Put(long value, wxObject *object);
  195.     void Put(const wxChar *value, wxObject *object);
  196.  
  197.     // key and value not the same
  198.     wxObject *Get(long key, long value) const;
  199.     wxObject *Get(long key, const wxChar *value) const;
  200.  
  201.     // key and value are the same
  202.     wxObject *Get(long value) const;
  203.     wxObject *Get(const wxChar *value) const;
  204.  
  205.     // Deletes entry and returns data if found
  206.     wxObject *Delete(long key);
  207.     wxObject *Delete(const wxChar *key);
  208.  
  209.     wxObject *Delete(long key, int value);
  210.     wxObject *Delete(long key, const wxChar *value);
  211.  
  212.     // Construct your own integer key from a string, e.g. in case
  213.     // you need to combine it with something
  214.     long MakeKey(const wxChar *string) const;
  215.  
  216.     // Way of iterating through whole hash table (e.g. to delete everything)
  217.     // Not necessary, of course, if you're only storing pointers to
  218.     // objects maintained separately
  219.  
  220.     void BeginFind();
  221.     wxNode *Next();
  222.  
  223.     void DeleteContents(bool flag);
  224.     void Clear();
  225.  
  226.     // Returns number of nodes
  227.     size_t GetCount() const { return m_count; }
  228.  
  229. private:
  230.     size_t m_count;             // number of elements in the hashtable
  231.     bool m_deleteContents;
  232.  
  233.     DECLARE_DYNAMIC_CLASS(wxHashTable)
  234. };
  235.  
  236. // defines a new type safe hash table which stores the elements of type eltype
  237. // in lists of class listclass
  238. #define _WX_DECLARE_HASH(eltype, listclass, hashclass, classexp)               \
  239.     classexp hashclass : public wxHashTableBase                                \
  240.     {                                                                          \
  241.     public:                                                                    \
  242.         hashclass(wxKeyType keyType = wxKEY_INTEGER,                           \
  243.                   size_t size = wxHASH_SIZE_DEFAULT)                           \
  244.             { Create(keyType, size); }                                         \
  245.                                                                                \
  246.         ~hashclass() { Destroy(); }                                            \
  247.                                                                                \
  248.         void Put(long key, long val, eltype *data) { DoPut(key, val, data); }  \
  249.         void Put(long key, eltype *data) { DoPut(key, key, data); }            \
  250.                                                                                \
  251.         eltype *Get(long key, long value) const                                \
  252.         {                                                                      \
  253.             wxNodeBase *node = GetNode(key, value);                            \
  254.             return node ? ((listclass::Node *)node)->GetData() : (eltype *)0;  \
  255.         }                                                                      \
  256.         eltype *Get(long key) const { return Get(key, key); }                  \
  257.                                                                                \
  258.         eltype *Delete(long key, long value)                                   \
  259.         {                                                                      \
  260.             eltype *data;                                                      \
  261.                                                                                \
  262.             wxNodeBase *node = GetNode(key, value);                            \
  263.             if ( node )                                                        \
  264.             {                                                                  \
  265.                 data = ((listclass::Node *)node)->GetData();                   \
  266.                                                                                \
  267.                 delete node;                                                   \
  268.                 m_count--;                                                     \
  269.             }                                                                  \
  270.             else                                                               \
  271.             {                                                                  \
  272.                 data = (eltype *)0;                                            \
  273.             }                                                                  \
  274.                                                                                \
  275.             return data;                                                       \
  276.         }                                                                      \
  277.         eltype *Delete(long key) { return Delete(key, key); }                  \
  278.                                                                                \
  279.     protected:                                                                 \
  280.         void DoPut(long key, long value, eltype *data)                         \
  281.         {                                                                      \
  282.             size_t slot = (size_t)abs((int)(key % (long)m_hashSize));          \
  283.                                                                                \
  284.             if ( !m_hashTable[slot] )                                          \
  285.             {                                                                  \
  286.                 m_hashTable[slot] = new listclass(m_keyType);                  \
  287.                 if ( m_deleteContents )                                        \
  288.                     m_hashTable[slot]->DeleteContents(TRUE);                   \
  289.             }                                                                  \
  290.                                                                                \
  291.             ((listclass *)m_hashTable[slot])->Append(value, data);             \
  292.             m_count++;                                                         \
  293.         }                                                                      \
  294.     }
  295.  
  296. // this macro is to be used in the user code
  297. #define WX_DECLARE_HASH(el, list, hash) \
  298.     _WX_DECLARE_HASH(el, list, hash, class)
  299.  
  300. // and this one does exactly the same thing but should be used inside the
  301. // library
  302. #define WX_DECLARE_EXPORTED_HASH(el, list, hash)  \
  303.     _WX_DECLARE_HASH(el, list, hash, class WXDLLEXPORT)
  304.  
  305. #define WX_DECLARE_USER_EXPORTED_HASH(el, list, hash, usergoo)  \
  306.     _WX_DECLARE_HASH(el, list, hash, class usergoo)
  307.  
  308. #endif
  309.     // _WX_HASH_H__
  310.