src/common/hash.cpp

/////////////////////////////////////////////////////////////////////////////
// Name:        hash.cpp
// Purpose:     wxHashTable implementation
// Author:      Julian Smart
// Modified by:
// Created:     01/02/97
// RCS-ID:      $Id$
// Copyright:   (c) Julian Smart and Markus Holzem
// Licence:   	wxWindows licence
/////////////////////////////////////////////////////////////////////////////

#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"

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

IMPLEMENT_DYNAMIC_CLASS(wxHashTable, wxObject)

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 (void)
{
  Destroy();
}

void wxHashTable::Destroy(void)
{
  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;
  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_INTEGER);
    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->Data ();
      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->Data ();
      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->Data () : (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->Data () : (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->Data ();
	  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->Data ();
	  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->Data ();
	  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->Data ();
	  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 (void)
{
  current_position = -1;
  current_node = (wxNode *) NULL;
}

wxNode *wxHashTable::Next (void)
{
  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]->First ();
		  found = current_node;
		}
	    }
	}
      else
	{
	  current_node = current_node->Next ();
	  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 (void)
{
  int i;
  for (i = 0; i < n; i++)
    {
      if (hash_table[i])
	hash_table[i]->Clear ();
    }
  m_count = 0;
}
Commit	Line	Data
	1	/////////////////////////////////////////////////////////////////////////////
	2	// Name: hash.cpp
	3	// Purpose: wxHashTable implementation
	4	// Author: Julian Smart
	5	// Modified by:
	6	// Created: 01/02/97
	7	// RCS-ID: $Id$
	8	// Copyright: (c) Julian Smart and Markus Holzem
	9	// Licence: wxWindows licence
	10	/////////////////////////////////////////////////////////////////////////////
	11
	12	#ifdef __GNUG__
	13	#pragma implementation "hash.h"
	14	#endif
	15
	16	// For compilers that support precompilation, includes "wx.h".
	17	#include "wx/wxprec.h"
	18
	19	#ifdef __BORLANDC__
	20	#pragma hdrstop
	21	#endif
	22
	23	#ifndef WX_PRECOMP
	24	#include "wx/list.h"
	25	#endif
	26
	27	#include "wx/hash.h"
	28
	29	#include <string.h>
	30	#include <stdarg.h>
	31
	32	IMPLEMENT_DYNAMIC_CLASS(wxHashTable, wxObject)
	33
	34	wxHashTable::wxHashTable (int the_key_type, int size)
	35	{
	36	n = 0;
	37	hash_table = (wxList**) NULL;
	38	Create(the_key_type, size);
	39	m_count = 0;
	40	m_deleteContents = FALSE;
	41	/*
	42	n = size;
	43	current_position = -1;
	44	current_node = (wxNode *) NULL;
	45
	46	key_type = the_key_type;
	47	hash_table = new wxList *[size];
	48	int i;
	49	for (i = 0; i < size; i++)
	50	hash_table[i] = (wxList *) NULL;
	51	*/
	52	}
	53
	54	wxHashTable::~wxHashTable (void)
	55	{
	56	Destroy();
	57	}
	58
	59	void wxHashTable::Destroy(void)
	60	{
	61	if (!hash_table) return;
	62	int i;
	63	for (i = 0; i < n; i++)
	64	if (hash_table[i])
	65	delete hash_table[i];
	66	delete[] hash_table;
	67	hash_table = NULL;
	68	}
	69
	70	bool wxHashTable::Create(int the_key_type, int size)
	71	{
	72	Destroy();
	73
	74	n = size;
	75	current_position = -1;
	76	current_node = (wxNode *) NULL;
	77
	78	key_type = the_key_type;
	79	hash_table = new wxList *[size];
	80	int i;
	81	for (i = 0; i < size; i++)
	82	hash_table[i] = (wxList *) NULL;
	83	return TRUE;
	84	}
	85
	86
	87	void wxHashTable::DoCopy(const wxHashTable& table)
	88	{
	89	n = table.n;
	90	current_position = table.current_position;
	91	current_node = NULL; // doesn't matter - Next() will reconstruct it
	92	key_type = table.key_type;
	93
	94	hash_table = new wxList *[n];
	95	for (int i = 0; i < n; i++) {
	96	if (table.hash_table[i] == NULL)
	97	hash_table[i] = NULL;
	98	else {
	99	hash_table[i] = new wxList(key_type);
	100	(hash_table[i]) = (table.hash_table[i]);
	101	}
	102	}
	103	}
	104
	105	void wxHashTable::Put (long key, long value, wxObject * object)
	106	{
	107	// Should NEVER be
	108	long k = (long) key;
	109
	110	int position = (int) (k % n);
	111	if (position < 0) position = -position;
	112
	113	if (!hash_table[position])
	114	{
	115	hash_table[position] = new wxList (wxKEY_INTEGER);
	116	if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
	117	}
	118
	119	hash_table[position]->Append (value, object);
	120	m_count++;
	121	}
	122
	123	void wxHashTable::Put (long key, const wxChar value, wxObject object)
	124	{
	125	// Should NEVER be
	126	long k = (long) key;
	127
	128	int position = (int) (k % n);
	129	if (position < 0) position = -position;
	130
	131	if (!hash_table[position])
	132	{
	133	hash_table[position] = new wxList (wxKEY_INTEGER);
	134	if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
	135	}
	136
	137	hash_table[position]->Append (value, object);
	138	m_count++;
	139	}
	140
	141	void wxHashTable::Put (long key, wxObject * object)
	142	{
	143	// Should NEVER be
	144	long k = (long) key;
	145
	146	int position = (int) (k % n);
	147	if (position < 0) position = -position;
	148
	149	if (!hash_table[position])
	150	{
	151	hash_table[position] = new wxList (wxKEY_INTEGER);
	152	if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
	153	}
	154
	155	hash_table[position]->Append (k, object);
	156	m_count++;
	157	}
	158
	159	void wxHashTable::Put (const wxChar key, wxObject object)
	160	{
	161	int position = (int) (MakeKey (key) % n);
	162	if (position < 0) position = -position;
	163
	164	if (!hash_table[position])
	165	{
	166	hash_table[position] = new wxList (wxKEY_STRING);
	167	if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
	168	}
	169
	170	hash_table[position]->Append (key, object);
	171	m_count++;
	172	}
	173
	174	wxObject *wxHashTable::Get (long key, long value) const
	175	{
	176	// Should NEVER be
	177	long k = (long) key;
	178
	179	int position = (int) (k % n);
	180	if (position < 0) position = -position;
	181
	182	if (!hash_table[position])
	183	return (wxObject *) NULL;
	184	else
	185	{
	186	wxNode *node = hash_table[position]->Find (value);
	187	if (node)
	188	return node->Data ();
	189	else
	190	return (wxObject *) NULL;
	191	}
	192	}
	193
	194	wxObject wxHashTable::Get (long key, const wxChar value) const
	195	{
	196	// Should NEVER be
	197	long k = (long) key;
	198
	199	int position = (int) (k % n);
	200	if (position < 0) position = -position;
	201
	202	if (!hash_table[position])
	203	return (wxObject *) NULL;
	204	else
	205	{
	206	wxNode *node = hash_table[position]->Find (value);
	207	if (node)
	208	return node->Data ();
	209	else
	210	return (wxObject *) NULL;
	211	}
	212	}
	213
	214	wxObject *wxHashTable::Get (long key) const
	215	{
	216	// Should NEVER be
	217	long k = (long) key;
	218
	219	int position = (int) (k % n);
	220	if (position < 0) position = -position;
	221
	222	if (!hash_table[position])
	223	return (wxObject *) NULL;
	224	else
	225	{
	226	wxNode *node = hash_table[position]->Find (k);
	227	return node ? node->Data () : (wxObject*)NULL;
	228	}
	229	}
	230
	231	wxObject wxHashTable::Get (const wxChar key) const
	232	{
	233	int position = (int) (MakeKey (key) % n);
	234	if (position < 0) position = -position;
	235
	236	if (!hash_table[position])
	237	return (wxObject *) NULL;
	238	else
	239	{
	240	wxNode *node = hash_table[position]->Find (key);
	241	return node ? node->Data () : (wxObject*)NULL;
	242	}
	243	}
	244
	245	wxObject *wxHashTable::Delete (long key)
	246	{
	247	// Should NEVER be
	248	long k = (long) key;
	249
	250	int position = (int) (k % n);
	251	if (position < 0) position = -position;
	252
	253	if (!hash_table[position])
	254	return (wxObject *) NULL;
	255	else
	256	{
	257	wxNode *node = hash_table[position]->Find (k);
	258	if (node)
	259	{
	260	wxObject *data = node->Data ();
	261	delete node;
	262	m_count--;
	263	return data;
	264	}
	265	else
	266	return (wxObject *) NULL;
	267	}
	268	}
	269
	270	wxObject wxHashTable::Delete (const wxChar key)
	271	{
	272	int position = (int) (MakeKey (key) % n);
	273	if (position < 0) position = -position;
	274
	275	if (!hash_table[position])
	276	return (wxObject *) NULL;
	277	else
	278	{
	279	wxNode *node = hash_table[position]->Find (key);
	280	if (node)
	281	{
	282	wxObject *data = node->Data ();
	283	delete node;
	284	m_count--;
	285	return data;
	286	}
	287	else
	288	return (wxObject *) NULL;
	289	}
	290	}
	291
	292	wxObject *wxHashTable::Delete (long key, int value)
	293	{
	294	// Should NEVER be
	295	long k = (long) key;
	296
	297	int position = (int) (k % n);
	298	if (position < 0) position = -position;
	299
	300	if (!hash_table[position])
	301	return (wxObject *) NULL;
	302	else
	303	{
	304	wxNode *node = hash_table[position]->Find (value);
	305	if (node)
	306	{
	307	wxObject *data = node->Data ();
	308	delete node;
	309	m_count--;
	310	return data;
	311	}
	312	else
	313	return (wxObject *) NULL;
	314	}
	315	}
	316
	317	wxObject wxHashTable::Delete (long key, const wxChar value)
	318	{
	319	int position = (int) (key % n);
	320	if (position < 0) position = -position;
	321
	322	if (!hash_table[position])
	323	return (wxObject *) NULL;
	324	else
	325	{
	326	wxNode *node = hash_table[position]->Find (value);
	327	if (node)
	328	{
	329	wxObject *data = node->Data ();
	330	delete node;
	331	m_count--;
	332	return data;
	333	}
	334	else
	335	return (wxObject *) NULL;
	336	}
	337	}
	338
	339	long wxHashTable::MakeKey (const wxChar *string) const
	340	{
	341	long int_key = 0;
	342
	343	while (*string)
	344	int_key += (wxUChar) *string++;
	345
	346	return int_key;
	347	}
	348
	349	void wxHashTable::BeginFind (void)
	350	{
	351	current_position = -1;
	352	current_node = (wxNode *) NULL;
	353	}
	354
	355	wxNode *wxHashTable::Next (void)
	356	{
	357	wxNode found = (wxNode ) NULL;
	358	bool end = FALSE;
	359	while (!end && !found)
	360	{
	361	if (!current_node)
	362	{
	363	current_position++;
	364	if (current_position >= n)
	365	{
	366	current_position = -1;
	367	current_node = (wxNode *) NULL;
	368	end = TRUE;
	369	}
	370	else
	371	{
	372	if (hash_table[current_position])
	373	{
	374	current_node = hash_table[current_position]->First ();
	375	found = current_node;
	376	}
	377	}
	378	}
	379	else
	380	{
	381	current_node = current_node->Next ();
	382	found = current_node;
	383	}
	384	}
	385	return found;
	386	}
	387
	388	void wxHashTable::DeleteContents (bool flag)
	389	{
	390	int i;
	391	m_deleteContents = flag;
	392	for (i = 0; i < n; i++)
	393	{
	394	if (hash_table[i])
	395	hash_table[i]->DeleteContents (flag);
	396	}
	397	}
	398
	399	void wxHashTable::Clear (void)
	400	{
	401	int i;
	402	for (i = 0; i < n; i++)
	403	{
	404	if (hash_table[i])
	405	hash_table[i]->Clear ();
	406	}
	407	m_count = 0;
	408	}
	409