home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / wxos2233.zip / wxOS2-2_3_3.zip / wxWindows-2.3.3 / src / common / hash.cpp < prev    next >
C/C++ Source or Header  |  2002-06-07  |  17KB  |  721 lines
  1. /////////////////////////////////////////////////////////////////////////////
  2. // Name:        hash.cpp
  3. // Purpose:     wxHashTable implementation
  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.cpp,v 1.24 2002/06/06 16:06:17 JS Exp $
  8. // Copyright:   (c) Julian Smart and Markus Holzem
  9. // Licence:     wxWindows licence
  10. /////////////////////////////////////////////////////////////////////////////
  11.  
  12. // ============================================================================
  13. // declarations
  14. // ============================================================================
  15.  
  16. // ----------------------------------------------------------------------------
  17. // headers
  18. // ----------------------------------------------------------------------------
  19.  
  20. #ifdef __GNUG__
  21. #pragma implementation "hash.h"
  22. #endif
  23.  
  24. // For compilers that support precompilation, includes "wx.h".
  25. #include "wx/wxprec.h"
  26.  
  27. #ifdef __BORLANDC__
  28. #pragma hdrstop
  29. #endif
  30.  
  31. #ifndef WX_PRECOMP
  32. #include "wx/list.h"
  33. #endif
  34.  
  35. #include "wx/hash.h"
  36.  
  37. #include <string.h>
  38. #include <stdarg.h>
  39.  
  40. // ----------------------------------------------------------------------------
  41. // wxWin macros
  42. // ----------------------------------------------------------------------------
  43.  
  44. IMPLEMENT_DYNAMIC_CLASS(wxHashTable, wxObject)
  45.  
  46. // ============================================================================
  47. // implementation
  48. // ============================================================================
  49.  
  50. // ----------------------------------------------------------------------------
  51. // wxHashTablleBase for working with "void *" data
  52. // ----------------------------------------------------------------------------
  53.  
  54. wxHashTableBase::wxHashTableBase()
  55. {
  56.     m_deleteContents = FALSE;
  57.     m_hashTable = (wxListBase **)NULL;
  58.     m_hashSize = 0;
  59.     m_count = 0;
  60.     m_keyType = wxKEY_NONE;
  61. }
  62.  
  63. void wxHashTableBase::Create(wxKeyType keyType, size_t size)
  64. {
  65.     Destroy();
  66.  
  67.     m_hashSize = size;
  68.     m_keyType = keyType;
  69.     m_hashTable = new wxListBase *[size];
  70.     for ( size_t n = 0; n < m_hashSize; n++ )
  71.     {
  72.         m_hashTable[n] = (wxListBase *) NULL;
  73.     }
  74. }
  75.  
  76. void wxHashTableBase::Destroy()
  77. {
  78.     if ( m_hashTable )
  79.     {
  80.         for ( size_t n = 0; n < m_hashSize; n++ )
  81.         {
  82.             delete m_hashTable[n];
  83.         }
  84.  
  85.         delete [] m_hashTable;
  86.  
  87.         m_hashTable = (wxListBase **)NULL;
  88.  
  89.         m_count = 0;
  90.     }
  91. }
  92.  
  93. void wxHashTableBase::DeleteContents(bool flag)
  94. {
  95.     m_deleteContents = flag;
  96.     for ( size_t n = 0; n < m_hashSize; n++ )
  97.     {
  98.         if ( m_hashTable[n] )
  99.         {
  100.             m_hashTable[n]->DeleteContents(flag);
  101.         }
  102.     }
  103. }
  104.  
  105. wxNodeBase *wxHashTableBase::GetNode(long key, long value) const
  106. {
  107.     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
  108.  
  109.     wxNodeBase *node;
  110.     if ( m_hashTable[slot] )
  111.     {
  112.         node = m_hashTable[slot]->Find(wxListKey(value));
  113.     }
  114.     else
  115.     {
  116.         node = (wxNodeBase *)NULL;
  117.     }
  118.  
  119.     return node;
  120. }
  121.  
  122. // ----------------------------------------------------------------------------
  123. // wxHashTableLong
  124. // ----------------------------------------------------------------------------
  125.  
  126. wxHashTableLong::~wxHashTableLong()
  127. {
  128.     Destroy();
  129. }
  130.  
  131. void wxHashTableLong::Init(size_t size)
  132. {
  133.     m_hashSize = size;
  134.     m_values = new wxArrayLong *[size];
  135.     m_keys = new wxArrayLong *[size];
  136.  
  137.     for ( size_t n = 0; n < m_hashSize; n++ )
  138.     {
  139.         m_values[n] =
  140.         m_keys[n] = (wxArrayLong *)NULL;
  141.     }
  142.  
  143.     m_count = 0;
  144. }
  145.  
  146. void wxHashTableLong::Create(size_t size)
  147. {
  148.     Init(size);
  149. }
  150.  
  151. void wxHashTableLong::Destroy()
  152. {
  153.     for ( size_t n = 0; n < m_hashSize; n++ )
  154.     {
  155.         delete m_values[n];
  156.         delete m_keys[n];
  157.     }
  158.  
  159.     delete [] m_values;
  160.     delete [] m_keys;
  161.     m_hashSize = 0;
  162.     m_count = 0;
  163. }
  164.  
  165. void wxHashTableLong::Put(long key, long value)
  166. {
  167.     wxCHECK_RET( m_hashSize, _T("must call Create() first") );
  168.  
  169.     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
  170.  
  171.     if ( !m_keys[slot] )
  172.     {
  173.         m_keys[slot] = new wxArrayLong;
  174.         m_values[slot] = new wxArrayLong;
  175.     }
  176.  
  177.     m_keys[slot]->Add(key);
  178.     m_values[slot]->Add(value);
  179.  
  180.     m_count++;
  181. }
  182.  
  183. long wxHashTableLong::Get(long key) const
  184. {
  185.     wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") );
  186.  
  187.     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
  188.  
  189.     wxArrayLong *keys = m_keys[slot];
  190.     if ( keys )
  191.     {
  192.         size_t count = keys->GetCount();
  193.         for ( size_t n = 0; n < count; n++ )
  194.         {
  195.             if ( keys->Item(n) == key )
  196.             {
  197.                 return m_values[slot]->Item(n);
  198.             }
  199.         }
  200.     }
  201.  
  202.     return wxNOT_FOUND;
  203. }
  204.  
  205. long wxHashTableLong::Delete(long key)
  206. {
  207.     wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") );
  208.  
  209.     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
  210.  
  211.     wxArrayLong *keys = m_keys[slot];
  212.     if ( keys )
  213.     {
  214.         size_t count = keys->GetCount();
  215.         for ( size_t n = 0; n < count; n++ )
  216.         {
  217.             if ( keys->Item(n) == key )
  218.             {
  219.                 long val = m_values[slot]->Item(n);
  220.  
  221.                 keys->RemoveAt(n);
  222.                 m_values[slot]->RemoveAt(n);
  223.  
  224.                 m_count--;
  225.  
  226.                 return val;
  227.             }
  228.         }
  229.     }
  230.  
  231.     return wxNOT_FOUND;
  232. }
  233.  
  234. // ----------------------------------------------------------------------------
  235. // wxStringHashTable: more efficient than storing strings in a list
  236. // ----------------------------------------------------------------------------
  237.  
  238. wxStringHashTable::wxStringHashTable(size_t sizeTable)
  239. {
  240.     m_keys = new wxArrayLong *[sizeTable];
  241.     m_values = new wxArrayString *[sizeTable];
  242.  
  243.     m_hashSize = sizeTable;
  244.     for ( size_t n = 0; n < m_hashSize; n++ )
  245.     {
  246.         m_values[n] = (wxArrayString *)NULL;
  247.         m_keys[n] = (wxArrayLong *)NULL;
  248.     }
  249. }
  250.  
  251. wxStringHashTable::~wxStringHashTable()
  252. {
  253.     Destroy();
  254. }
  255.  
  256. void wxStringHashTable::Destroy()
  257. {
  258.     for ( size_t n = 0; n < m_hashSize; n++ )
  259.     {
  260.         delete m_values[n];
  261.         delete m_keys[n];
  262.     }
  263.  
  264.     delete [] m_values;
  265.     delete [] m_keys;
  266.     m_hashSize = 0;
  267. }
  268.  
  269. void wxStringHashTable::Put(long key, const wxString& value)
  270. {
  271.     wxCHECK_RET( m_hashSize, _T("must call Create() first") );
  272.  
  273.     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
  274.  
  275.     if ( !m_keys[slot] )
  276.     {
  277.         m_keys[slot] = new wxArrayLong;
  278.         m_values[slot] = new wxArrayString;
  279.     }
  280.  
  281.     m_keys[slot]->Add(key);
  282.     m_values[slot]->Add(value);
  283. }
  284.  
  285. wxString wxStringHashTable::Get(long key, bool *wasFound) const
  286. {
  287.     wxCHECK_MSG( m_hashSize, _T(""), _T("must call Create() first") );
  288.  
  289.     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
  290.  
  291.     wxArrayLong *keys = m_keys[slot];
  292.     if ( keys )
  293.     {
  294.         size_t count = keys->GetCount();
  295.         for ( size_t n = 0; n < count; n++ )
  296.         {
  297.             if ( keys->Item(n) == key )
  298.             {
  299.                 if ( wasFound )
  300.                     *wasFound = TRUE;
  301.  
  302.                 return m_values[slot]->Item(n);
  303.             }
  304.         }
  305.     }
  306.  
  307.     if ( wasFound )
  308.         *wasFound = FALSE;
  309.  
  310.     return _T("");
  311. }
  312.  
  313. bool wxStringHashTable::Delete(long key) const
  314. {
  315.     wxCHECK_MSG( m_hashSize, FALSE, _T("must call Create() first") );
  316.  
  317.     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
  318.  
  319.     wxArrayLong *keys = m_keys[slot];
  320.     if ( keys )
  321.     {
  322.         size_t count = keys->GetCount();
  323.         for ( size_t n = 0; n < count; n++ )
  324.         {
  325.             if ( keys->Item(n) == key )
  326.             {
  327.                 keys->RemoveAt(n);
  328.                 m_values[slot]->RemoveAt(n);
  329.                 return TRUE;
  330.             }
  331.         }
  332.     }
  333.  
  334.     return FALSE;
  335. }
  336.  
  337. // ----------------------------------------------------------------------------
  338. // old not type safe wxHashTable
  339. // ----------------------------------------------------------------------------
  340.  
  341. wxHashTable::wxHashTable (int the_key_type, int size)
  342. {
  343.   n = 0;
  344.   hash_table = (wxList**) NULL;
  345.   Create(the_key_type, size);
  346.   m_count = 0;
  347.   m_deleteContents = FALSE;
  348. /*
  349.   n = size;
  350.   current_position = -1;
  351.   current_node = (wxNode *) NULL;
  352.  
  353.   key_type = the_key_type;
  354.   hash_table = new wxList *[size];
  355.   int i;
  356.   for (i = 0; i < size; i++)
  357.     hash_table[i] = (wxList *) NULL;
  358. */
  359. }
  360.  
  361. wxHashTable::~wxHashTable ()
  362. {
  363.   Destroy();
  364. }
  365.  
  366. void wxHashTable::Destroy()
  367. {
  368.   if (!hash_table) return;
  369.   int i;
  370.   for (i = 0; i < n; i++)
  371.     if (hash_table[i])
  372.       delete hash_table[i];
  373.   delete[] hash_table;
  374.   hash_table = NULL;
  375. }
  376.  
  377. bool wxHashTable::Create(int the_key_type, int size)
  378. {
  379.   Destroy();
  380.  
  381.   n = size;
  382.   current_position = -1;
  383.   current_node = (wxNode *) NULL;
  384.  
  385.   key_type = the_key_type;
  386.   hash_table = new wxList *[size];
  387.   int i;
  388.   for (i = 0; i < size; i++)
  389.     hash_table[i] = (wxList *) NULL;
  390.   return TRUE;
  391. }
  392.  
  393.  
  394. void wxHashTable::DoCopy(const wxHashTable& table)
  395. {
  396.   n = table.n;
  397.   m_count = table.m_count;
  398.   current_position = table.current_position;
  399.   current_node = NULL; // doesn't matter - Next() will reconstruct it
  400.   key_type = table.key_type;
  401.  
  402.   hash_table = new wxList *[n];
  403.   for (int i = 0; i < n; i++) {
  404.     if (table.hash_table[i] == NULL)
  405.       hash_table[i] = NULL;
  406.     else {
  407.       hash_table[i] = new wxList(key_type);
  408.       *(hash_table[i]) = *(table.hash_table[i]);
  409.     }
  410.   }
  411. }
  412.  
  413. void wxHashTable::Put (long key, long value, wxObject * object)
  414. {
  415.   // Should NEVER be
  416.   long k = (long) key;
  417.  
  418.   int position = (int) (k % n);
  419.   if (position < 0) position = -position;
  420.  
  421.   if (!hash_table[position])
  422.   {
  423.     hash_table[position] = new wxList (wxKEY_INTEGER);
  424.     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
  425.   }
  426.  
  427.   hash_table[position]->Append (value, object);
  428.   m_count++;
  429. }
  430.  
  431. void wxHashTable::Put (long key, const wxChar *value, wxObject * object)
  432. {
  433.   // Should NEVER be
  434.   long k = (long) key;
  435.  
  436.   int position = (int) (k % n);
  437.   if (position < 0) position = -position;
  438.  
  439.   if (!hash_table[position])
  440.   {
  441.     hash_table[position] = new wxList (wxKEY_STRING);
  442.     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
  443.   }
  444.  
  445.   hash_table[position]->Append (value, object);
  446.   m_count++;
  447. }
  448.  
  449. void wxHashTable::Put (long key, wxObject * object)
  450. {
  451.   // Should NEVER be
  452.   long k = (long) key;
  453.  
  454.   int position = (int) (k % n);
  455.   if (position < 0) position = -position;
  456.  
  457.   if (!hash_table[position])
  458.   {
  459.     hash_table[position] = new wxList (wxKEY_INTEGER);
  460.     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
  461.   }
  462.  
  463.   hash_table[position]->Append (k, object);
  464.   m_count++;
  465. }
  466.  
  467. void wxHashTable::Put (const wxChar *key, wxObject * object)
  468. {
  469.   int position = (int) (MakeKey (key) % n);
  470.   if (position < 0) position = -position;
  471.  
  472.   if (!hash_table[position])
  473.   {
  474.     hash_table[position] = new wxList (wxKEY_STRING);
  475.     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
  476.   }
  477.  
  478.   hash_table[position]->Append (key, object);
  479.   m_count++;
  480. }
  481.  
  482. wxObject *wxHashTable::Get (long key, long value) const
  483. {
  484.   // Should NEVER be
  485.   long k = (long) key;
  486.  
  487.   int position = (int) (k % n);
  488.   if (position < 0) position = -position;
  489.  
  490.   if (!hash_table[position])
  491.     return (wxObject *) NULL;
  492.   else
  493.     {
  494.       wxNode *node = hash_table[position]->Find (value);
  495.       if (node)
  496.         return node->Data ();
  497.       else
  498.         return (wxObject *) NULL;
  499.     }
  500. }
  501.  
  502. wxObject *wxHashTable::Get (long key, const wxChar *value) const
  503. {
  504.   // Should NEVER be
  505.   long k = (long) key;
  506.  
  507.   int position = (int) (k % n);
  508.   if (position < 0) position = -position;
  509.  
  510.   if (!hash_table[position])
  511.     return (wxObject *) NULL;
  512.   else
  513.     {
  514.       wxNode *node = hash_table[position]->Find (value);
  515.       if (node)
  516.         return node->Data ();
  517.       else
  518.         return (wxObject *) NULL;
  519.     }
  520. }
  521.  
  522. wxObject *wxHashTable::Get (long key) const
  523. {
  524.   // Should NEVER be
  525.   long k = (long) key;
  526.  
  527.   int position = (int) (k % n);
  528.   if (position < 0) position = -position;
  529.  
  530.   if (!hash_table[position])
  531.     return (wxObject *) NULL;
  532.   else
  533.     {
  534.       wxNode *node = hash_table[position]->Find (k);
  535.       return node ? node->Data () : (wxObject*)NULL;
  536.     }
  537. }
  538.  
  539. wxObject *wxHashTable::Get (const wxChar *key) const
  540. {
  541.   int position = (int) (MakeKey (key) % n);
  542.   if (position < 0) position = -position;
  543.  
  544.   if (!hash_table[position])
  545.     return (wxObject *) NULL;
  546.   else
  547.     {
  548.       wxNode *node = hash_table[position]->Find (key);
  549.       return node ? node->Data () : (wxObject*)NULL;
  550.     }
  551. }
  552.  
  553. wxObject *wxHashTable::Delete (long key)
  554. {
  555.   // Should NEVER be
  556.   long k = (long) key;
  557.  
  558.   int position = (int) (k % n);
  559.   if (position < 0) position = -position;
  560.  
  561.   if (!hash_table[position])
  562.     return (wxObject *) NULL;
  563.   else
  564.     {
  565.       wxNode *node = hash_table[position]->Find (k);
  566.       if (node)
  567.         {
  568.           wxObject *data = node->Data ();
  569.           delete node;
  570.           m_count--;
  571.           return data;
  572.         }
  573.       else
  574.         return (wxObject *) NULL;
  575.     }
  576. }
  577.  
  578. wxObject *wxHashTable::Delete (const wxChar *key)
  579. {
  580.   int position = (int) (MakeKey (key) % n);
  581.   if (position < 0) position = -position;
  582.  
  583.   if (!hash_table[position])
  584.     return (wxObject *) NULL;
  585.   else
  586.     {
  587.       wxNode *node = hash_table[position]->Find (key);
  588.       if (node)
  589.         {
  590.           wxObject *data = node->Data ();
  591.           delete node;
  592.           m_count--;
  593.           return data;
  594.         }
  595.       else
  596.         return (wxObject *) NULL;
  597.     }
  598. }
  599.  
  600. wxObject *wxHashTable::Delete (long key, int value)
  601. {
  602.   // Should NEVER be
  603.   long k = (long) key;
  604.  
  605.   int position = (int) (k % n);
  606.   if (position < 0) position = -position;
  607.  
  608.   if (!hash_table[position])
  609.     return (wxObject *) NULL;
  610.   else
  611.     {
  612.       wxNode *node = hash_table[position]->Find (value);
  613.       if (node)
  614.         {
  615.           wxObject *data = node->Data ();
  616.           delete node;
  617.           m_count--;
  618.           return data;
  619.         }
  620.       else
  621.         return (wxObject *) NULL;
  622.     }
  623. }
  624.  
  625. wxObject *wxHashTable::Delete (long key, const wxChar *value)
  626. {
  627.   int position = (int) (key % n);
  628.   if (position < 0) position = -position;
  629.  
  630.   if (!hash_table[position])
  631.     return (wxObject *) NULL;
  632.   else
  633.     {
  634.       wxNode *node = hash_table[position]->Find (value);
  635.       if (node)
  636.         {
  637.           wxObject *data = node->Data ();
  638.           delete node;
  639.           m_count--;
  640.           return data;
  641.         }
  642.       else
  643.         return (wxObject *) NULL;
  644.     }
  645. }
  646.  
  647. long wxHashTable::MakeKey (const wxChar *string) const
  648. {
  649.   long int_key = 0;
  650.  
  651.   while (*string)
  652.     int_key += (wxUChar) *string++;
  653.  
  654.   return int_key;
  655. }
  656.  
  657. void wxHashTable::BeginFind ()
  658. {
  659.   current_position = -1;
  660.   current_node = (wxNode *) NULL;
  661. }
  662.  
  663. wxNode *wxHashTable::Next ()
  664. {
  665.   wxNode *found = (wxNode *) NULL;
  666.   bool end = FALSE;
  667.   while (!end && !found)
  668.     {
  669.       if (!current_node)
  670.         {
  671.           current_position++;
  672.           if (current_position >= n)
  673.             {
  674.               current_position = -1;
  675.               current_node = (wxNode *) NULL;
  676.               end = TRUE;
  677.             }
  678.           else
  679.             {
  680.               if (hash_table[current_position])
  681.                 {
  682.                   current_node = hash_table[current_position]->First ();
  683.                   found = current_node;
  684.                 }
  685.             }
  686.         }
  687.       else
  688.         {
  689.           current_node = current_node->Next ();
  690.           found = current_node;
  691.         }
  692.     }
  693.   return found;
  694. }
  695.  
  696. void wxHashTable::DeleteContents (bool flag)
  697. {
  698.   int i;
  699.   m_deleteContents = flag;
  700.   for (i = 0; i < n; i++)
  701.     {
  702.       if (hash_table[i])
  703.         hash_table[i]->DeleteContents (flag);
  704.     }
  705. }
  706.  
  707. void wxHashTable::Clear ()
  708. {
  709.     int i;
  710.     if (hash_table)
  711.     {
  712.         for (i = 0; i < n; i++)
  713.         {
  714.             if (hash_table[i])
  715.                 hash_table[i]->Clear ();
  716.         }
  717.     }
  718.   m_count = 0;
  719. }
  720.  
  721.