src/common/hash.cpp

/////////////////////////////////////////////////////////////////////////////
// Name:        hash.cpp
// Purpose:     wxHashTable implementation
// Author:      Julian Smart
// Modified by: VZ at 25.02.00: type safe hashes with WX_DECLARE_HASH()
// Created:     01/02/97
// RCS-ID:      $Id$
// Copyright:   (c) Julian Smart
// Licence:     wxWindows licence
/////////////////////////////////////////////////////////////////////////////

// ============================================================================
// declarations
// ============================================================================

// ----------------------------------------------------------------------------
// headers
// ----------------------------------------------------------------------------

#ifdef __GNUG__
#pragma implementation "hash.h"
#endif

// For compilers that support precompilation, includes "wx.h".
#include "wx/wxprec.h"

#ifdef __BORLANDC__
#pragma hdrstop
#endif

#ifndef WX_PRECOMP
#include "wx/list.h"
#endif

#include "wx/hash.h"

#if !wxUSE_STL

#include <string.h>
#include <stdarg.h>

// ----------------------------------------------------------------------------
// wxWin macros
// ----------------------------------------------------------------------------

IMPLEMENT_DYNAMIC_CLASS(wxHashTable, wxObject)

// ============================================================================
// implementation
// ============================================================================

// ----------------------------------------------------------------------------
// wxHashTablleBase for working with "void *" data
// ----------------------------------------------------------------------------

wxHashTableBase::wxHashTableBase()
{
    m_deleteContents = FALSE;
    m_hashTable = (wxListBase **)NULL;
    m_hashSize = 0;
    m_count = 0;
    m_keyType = wxKEY_NONE;
}

void wxHashTableBase::Create(wxKeyType keyType, size_t size)
{
    Destroy();

    m_hashSize = size;
    m_keyType = keyType;
    m_hashTable = new wxListBase *[size];
    for ( size_t n = 0; n < m_hashSize; n++ )
    {
        m_hashTable[n] = (wxListBase *) NULL;
    }
}

void wxHashTableBase::Destroy()
{
    if ( m_hashTable )
    {
        for ( size_t n = 0; n < m_hashSize; n++ )
        {
            delete m_hashTable[n];
        }

        delete [] m_hashTable;

        m_hashTable = (wxListBase **)NULL;

        m_count = 0;
    }
}

void wxHashTableBase::DeleteContents(bool flag)
{
    m_deleteContents = flag;
    for ( size_t n = 0; n < m_hashSize; n++ )
    {
        if ( m_hashTable[n] )
        {
            m_hashTable[n]->DeleteContents(flag);
        }
    }
}

wxNodeBase *wxHashTableBase::GetNode(long key, long value) const
{
    size_t slot = (size_t)abs((int)(key % (long)m_hashSize));

    wxNodeBase *node;
    if ( m_hashTable[slot] )
    {
        node = m_hashTable[slot]->Find(wxListKey(value));
    }
    else
    {
        node = (wxNodeBase *)NULL;
    }

    return node;
}

#if WXWIN_COMPATIBILITY_2_4

// ----------------------------------------------------------------------------
// wxHashTableLong
// ----------------------------------------------------------------------------

wxHashTableLong::~wxHashTableLong()
{
    Destroy();
}

void wxHashTableLong::Init(size_t size)
{
    m_hashSize = size;
    m_values = new wxArrayLong *[size];
    m_keys = new wxArrayLong *[size];

    for ( size_t n = 0; n < m_hashSize; n++ )
    {
        m_values[n] =
        m_keys[n] = (wxArrayLong *)NULL;
    }

    m_count = 0;
}

void wxHashTableLong::Create(size_t size)
{
    Init(size);
}

void wxHashTableLong::Destroy()
{
    for ( size_t n = 0; n < m_hashSize; n++ )
    {
        delete m_values[n];
        delete m_keys[n];
    }

    delete [] m_values;
    delete [] m_keys;
    m_hashSize = 0;
    m_count = 0;
}

void wxHashTableLong::Put(long key, long value)
{
    wxCHECK_RET( m_hashSize, _T("must call Create() first") );

    size_t slot = (size_t)abs((int)(key % (long)m_hashSize));

    if ( !m_keys[slot] )
    {
        m_keys[slot] = new wxArrayLong;
        m_values[slot] = new wxArrayLong;
    }

    m_keys[slot]->Add(key);
    m_values[slot]->Add(value);

    m_count++;
}

long wxHashTableLong::Get(long key) const
{
    wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") );

    size_t slot = (size_t)abs((int)(key % (long)m_hashSize));

    wxArrayLong *keys = m_keys[slot];
    if ( keys )
    {
        size_t count = keys->GetCount();
        for ( size_t n = 0; n < count; n++ )
        {
            if ( keys->Item(n) == key )
            {
                return m_values[slot]->Item(n);
            }
        }
    }

    return wxNOT_FOUND;
}

long wxHashTableLong::Delete(long key)
{
    wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") );

    size_t slot = (size_t)abs((int)(key % (long)m_hashSize));

    wxArrayLong *keys = m_keys[slot];
    if ( keys )
    {
        size_t count = keys->GetCount();
        for ( size_t n = 0; n < count; n++ )
        {
            if ( keys->Item(n) == key )
            {
                long val = m_values[slot]->Item(n);

                keys->RemoveAt(n);
                m_values[slot]->RemoveAt(n);

                m_count--;

                return val;
            }
        }
    }

    return wxNOT_FOUND;
}

// ----------------------------------------------------------------------------
// wxStringHashTable: more efficient than storing strings in a list
// ----------------------------------------------------------------------------

wxStringHashTable::wxStringHashTable(size_t sizeTable)
{
    m_keys = new wxArrayLong *[sizeTable];
    m_values = new wxArrayString *[sizeTable];

    m_hashSize = sizeTable;
    for ( size_t n = 0; n < m_hashSize; n++ )
    {
        m_values[n] = (wxArrayString *)NULL;
        m_keys[n] = (wxArrayLong *)NULL;
    }
}

wxStringHashTable::~wxStringHashTable()
{
    Destroy();
}

void wxStringHashTable::Destroy()
{
    for ( size_t n = 0; n < m_hashSize; n++ )
    {
        delete m_values[n];
        delete m_keys[n];
    }

    delete [] m_values;
    delete [] m_keys;
    m_hashSize = 0;
}

void wxStringHashTable::Put(long key, const wxString& value)
{
    wxCHECK_RET( m_hashSize, _T("must call Create() first") );

    size_t slot = (size_t)abs((int)(key % (long)m_hashSize));

    if ( !m_keys[slot] )
    {
        m_keys[slot] = new wxArrayLong;
        m_values[slot] = new wxArrayString;
    }

    m_keys[slot]->Add(key);
    m_values[slot]->Add(value);
}

wxString wxStringHashTable::Get(long key, bool *wasFound) const
{
    wxCHECK_MSG( m_hashSize, _T(""), _T("must call Create() first") );

    size_t slot = (size_t)abs((int)(key % (long)m_hashSize));

    wxArrayLong *keys = m_keys[slot];
    if ( keys )
    {
        size_t count = keys->GetCount();
        for ( size_t n = 0; n < count; n++ )
        {
            if ( keys->Item(n) == key )
            {
                if ( wasFound )
                    *wasFound = TRUE;

                return m_values[slot]->Item(n);
            }
        }
    }

    if ( wasFound )
        *wasFound = FALSE;

    return _T("");
}

bool wxStringHashTable::Delete(long key) const
{
    wxCHECK_MSG( m_hashSize, FALSE, _T("must call Create() first") );

    size_t slot = (size_t)abs((int)(key % (long)m_hashSize));

    wxArrayLong *keys = m_keys[slot];
    if ( keys )
    {
        size_t count = keys->GetCount();
        for ( size_t n = 0; n < count; n++ )
        {
            if ( keys->Item(n) == key )
            {
                keys->RemoveAt(n);
                m_values[slot]->RemoveAt(n);
                return TRUE;
            }
        }
    }

    return FALSE;
}

#endif // WXWIN_COMPATIBILITY_2_4

// ----------------------------------------------------------------------------
// old not type safe wxHashTable
// ----------------------------------------------------------------------------

wxHashTable::wxHashTable (int the_key_type, int size)
{
  n = 0;
  hash_table = (wxList**) NULL;
  Create(the_key_type, size);
  m_count = 0;
  m_deleteContents = FALSE;
/*
  n = size;
  current_position = -1;
  current_node = (wxNode *) NULL;

  key_type = the_key_type;
  hash_table = new wxList *[size];
  int i;
  for (i = 0; i < size; i++)
    hash_table[i] = (wxList *) NULL;
*/
}

wxHashTable::~wxHashTable ()
{
  Destroy();
}

void wxHashTable::Destroy()
{
  if (!hash_table) return;
  int i;
  for (i = 0; i < n; i++)
    if (hash_table[i])
      delete hash_table[i];
  delete[] hash_table;
  hash_table = NULL;
}

bool wxHashTable::Create(int the_key_type, int size)
{
  Destroy();

  n = size;
  current_position = -1;
  current_node = (wxNode *) NULL;

  key_type = the_key_type;
  hash_table = new wxList *[size];
  int i;
  for (i = 0; i < size; i++)
    hash_table[i] = (wxList *) NULL;
  return TRUE;
}


void wxHashTable::DoCopy(const wxHashTable& table)
{
  n = table.n;
  m_count = table.m_count;
  current_position = table.current_position;
  current_node = NULL; // doesn't matter - Next() will reconstruct it
  key_type = table.key_type;

  hash_table = new wxList *[n];
  for (int i = 0; i < n; i++) {
    if (table.hash_table[i] == NULL)
      hash_table[i] = NULL;
    else {
      hash_table[i] = new wxList(key_type);
      *(hash_table[i]) = *(table.hash_table[i]);
    }
  }
}

void wxHashTable::Put (long key, long value, wxObject * object)
{
  // Should NEVER be
  long k = (long) key;

  int position = (int) (k % n);
  if (position < 0) position = -position;

  if (!hash_table[position])
  {
    hash_table[position] = new wxList (wxKEY_INTEGER);
    if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
  }

  hash_table[position]->Append (value, object);
  m_count++;
}

void wxHashTable::Put (long key, const wxChar *value, wxObject * object)
{
  // Should NEVER be
  long k = (long) key;

  int position = (int) (k % n);
  if (position < 0) position = -position;

  if (!hash_table[position])
  {
    hash_table[position] = new wxList (wxKEY_STRING);
    if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
  }

  hash_table[position]->Append (value, object);
  m_count++;
}

void wxHashTable::Put (long key, wxObject * object)
{
  // Should NEVER be
  long k = (long) key;

  int position = (int) (k % n);
  if (position < 0) position = -position;

  if (!hash_table[position])
  {
    hash_table[position] = new wxList (wxKEY_INTEGER);
    if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
  }

  hash_table[position]->Append (k, object);
  m_count++;
}

void wxHashTable::Put (const wxChar *key, wxObject * object)
{
  int position = (int) (MakeKey (key) % n);
  if (position < 0) position = -position;

  if (!hash_table[position])
  {
    hash_table[position] = new wxList (wxKEY_STRING);
    if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
  }

  hash_table[position]->Append (key, object);
  m_count++;
}

wxObject *wxHashTable::Get (long key, long value) const
{
  // Should NEVER be
  long k = (long) key;

  int position = (int) (k % n);
  if (position < 0) position = -position;

  if (!hash_table[position])
    return (wxObject *) NULL;
  else
    {
      wxNode *node = hash_table[position]->Find (value);
      if (node)
        return node->GetData ();
      else
        return (wxObject *) NULL;
    }
}

wxObject *wxHashTable::Get (long key, const wxChar *value) const
{
  // Should NEVER be
  long k = (long) key;

  int position = (int) (k % n);
  if (position < 0) position = -position;

  if (!hash_table[position])
    return (wxObject *) NULL;
  else
    {
      wxNode *node = hash_table[position]->Find (value);
      if (node)
        return node->GetData ();
      else
        return (wxObject *) NULL;
    }
}

wxObject *wxHashTable::Get (long key) const
{
  // Should NEVER be
  long k = (long) key;

  int position = (int) (k % n);
  if (position < 0) position = -position;

  if (!hash_table[position])
    return (wxObject *) NULL;
  else
    {
      wxNode *node = hash_table[position]->Find (k);
      return node ? node->GetData () : (wxObject*)NULL;
    }
}

wxObject *wxHashTable::Get (const wxChar *key) const
{
  int position = (int) (MakeKey (key) % n);
  if (position < 0) position = -position;

  if (!hash_table[position])
    return (wxObject *) NULL;
  else
    {
      wxNode *node = hash_table[position]->Find (key);
      return node ? node->GetData () : (wxObject*)NULL;
    }
}

wxObject *wxHashTable::Delete (long key)
{
  // Should NEVER be
  long k = (long) key;

  int position = (int) (k % n);
  if (position < 0) position = -position;

  if (!hash_table[position])
    return (wxObject *) NULL;
  else
    {
      wxNode *node = hash_table[position]->Find (k);
      if (node)
        {
          wxObject *data = node->GetData ();
          delete node;
          m_count--;
          return data;
        }
      else
        return (wxObject *) NULL;
    }
}

wxObject *wxHashTable::Delete (const wxChar *key)
{
  int position = (int) (MakeKey (key) % n);
  if (position < 0) position = -position;

  if (!hash_table[position])
    return (wxObject *) NULL;
  else
    {
      wxNode *node = hash_table[position]->Find (key);
      if (node)
        {
          wxObject *data = node->GetData ();
          delete node;
          m_count--;
          return data;
        }
      else
        return (wxObject *) NULL;
    }
}

wxObject *wxHashTable::Delete (long key, int value)
{
  // Should NEVER be
  long k = (long) key;

  int position = (int) (k % n);
  if (position < 0) position = -position;

  if (!hash_table[position])
    return (wxObject *) NULL;
  else
    {
      wxNode *node = hash_table[position]->Find (value);
      if (node)
        {
          wxObject *data = node->GetData ();
          delete node;
          m_count--;
          return data;
        }
      else
        return (wxObject *) NULL;
    }
}

wxObject *wxHashTable::Delete (long key, const wxChar *value)
{
  int position = (int) (key % n);
  if (position < 0) position = -position;

  if (!hash_table[position])
    return (wxObject *) NULL;
  else
    {
      wxNode *node = hash_table[position]->Find (value);
      if (node)
        {
          wxObject *data = node->GetData ();
          delete node;
          m_count--;
          return data;
        }
      else
        return (wxObject *) NULL;
    }
}

long wxHashTable::MakeKey (const wxChar *string) const
{
  long int_key = 0;

  while (*string)
    int_key += (wxUChar) *string++;

  return int_key;
}

void wxHashTable::BeginFind ()
{
  current_position = -1;
  current_node = (wxNode *) NULL;
}

wxNode *wxHashTable::Next ()
{
  wxNode *found = (wxNode *) NULL;
  bool end = FALSE;
  while (!end && !found)
    {
      if (!current_node)
        {
          current_position++;
          if (current_position >= n)
            {
              current_position = -1;
              current_node = (wxNode *) NULL;
              end = TRUE;
            }
          else
            {
              if (hash_table[current_position])
                {
                  current_node = hash_table[current_position]->GetFirst ();
                  found = current_node;
                }
            }
        }
      else
        {
          current_node = current_node->GetNext ();
          found = current_node;
        }
    }
  return found;
}

void wxHashTable::DeleteContents (bool flag)
{
  int i;
  m_deleteContents = flag;
  for (i = 0; i < n; i++)
    {
      if (hash_table[i])
        hash_table[i]->DeleteContents (flag);
    }
}

void wxHashTable::Clear ()
{
    int i;
    if (hash_table)
    {
        for (i = 0; i < n; i++)
        {
            if (hash_table[i])
                hash_table[i]->Clear ();
        }
    }
  m_count = 0;
}

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