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>

#if !USE_SHARED_LIBRARY
IMPLEMENT_DYNAMIC_CLASS(wxHashTable, wxObject)
#endif

wxHashTable::wxHashTable (int the_key_type, int size)
{
  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)
{
  n = size;
  current_position = -1;
  current_node = (wxNode *) NULL;

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

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

  int position = (int) (k % n);
  if (!hash_table[position])
    hash_table[position] = new wxList (wxKEY_INTEGER);

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

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

  int position = (int) (k % n);
  if (!hash_table[position])
    hash_table[position] = new wxList (wxKEY_INTEGER);

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

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

  int position = (int) (k % n);
  if (!hash_table[position])
    hash_table[position] = new wxList (wxKEY_INTEGER);

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

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

  if (!hash_table[position])
    hash_table[position] = new wxList (wxKEY_STRING);

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

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

  int position = (int) (k % n);
  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;
  if (k < 0)
    k = -k;

  int position = (int) (k % n);
  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;
  if (k < 0)
    k = -k;

  int position = (int) (k % n);
  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 (!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;
  if (k < 0)
    k = -k;

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

wxObject *wxHashTable::Delete (const wxChar *key)
{
  int position = (int) (MakeKey (key) % n);
  if (!hash_table[position])
    return (wxObject *) NULL;
  else
    {
      wxNode *node = hash_table[position]->Find (key);
      if (node)
	{
	  wxObject *data = node->Data ();
	  delete node;
	  return data;
	}
      else
	return (wxObject *) NULL;
    }
}

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

  int position = (int) (k % n);
  if (!hash_table[position])
    return (wxObject *) NULL;
  else
    {
      wxNode *node = hash_table[position]->Find (value);
      if (node)
	{
	  wxObject *data = node->Data ();
	  delete node;
	  return data;
	}
      else
	return (wxObject *) NULL;
    }
}

wxObject *wxHashTable::Delete (long key, const wxChar *value)
{
  int position = (int) (key % n);
  if (!hash_table[position])
    return (wxObject *) NULL;
  else
    {
      wxNode *node = hash_table[position]->Find (value);
      if (node)
	{
	  wxObject *data = node->Data ();
	  delete node;
	  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;
  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 ();
    }
}
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	#if !USE_SHARED_LIBRARY
	33	IMPLEMENT_DYNAMIC_CLASS(wxHashTable, wxObject)
	34	#endif
	35
	36	wxHashTable::wxHashTable (int the_key_type, int size)
	37	{
	38	n = size;
	39	current_position = -1;
	40	current_node = (wxNode *) NULL;
	41
	42	key_type = the_key_type;
	43	hash_table = new wxList *[size];
	44	int i;
	45	for (i = 0; i < size; i++)
	46	hash_table[i] = (wxList *) NULL;
	47	}
	48
	49	wxHashTable::~wxHashTable (void)
	50	{
	51	Destroy();
	52	}
	53
	54	void wxHashTable::Destroy(void)
	55	{
	56	if (!hash_table) return;
	57	int i;
	58	for (i = 0; i < n; i++)
	59	if (hash_table[i])
	60	delete hash_table[i];
	61	delete[] hash_table;
	62	hash_table = NULL;
	63	}
	64
	65	bool wxHashTable::Create(int the_key_type, int size)
	66	{
	67	n = size;
	68	current_position = -1;
	69	current_node = (wxNode *) NULL;
	70
	71	key_type = the_key_type;
	72	if (hash_table)
	73	delete[] hash_table;
	74	hash_table = new wxList *[size];
	75	int i;
	76	for (i = 0; i < size; i++)
	77	hash_table[i] = (wxList *) NULL;
	78	return TRUE;
	79	}
	80
	81	void wxHashTable::Put (long key, long value, wxObject * object)
	82	{
	83	// Should NEVER be
	84	long k = (long) key;
	85	if (k < 0)
	86	k = -k;
	87
	88	int position = (int) (k % n);
	89	if (!hash_table[position])
	90	hash_table[position] = new wxList (wxKEY_INTEGER);
	91
	92	hash_table[position]->Append (value, object);
	93	}
	94
	95	void wxHashTable::Put (long key, const wxChar value, wxObject object)
	96	{
	97	// Should NEVER be
	98	long k = (long) key;
	99	if (k < 0)
	100	k = -k;
	101
	102	int position = (int) (k % n);
	103	if (!hash_table[position])
	104	hash_table[position] = new wxList (wxKEY_INTEGER);
	105
	106	hash_table[position]->Append (value, object);
	107	}
	108
	109	void wxHashTable::Put (long key, wxObject * object)
	110	{
	111	// Should NEVER be
	112	long k = (long) key;
	113	if (k < 0)
	114	k = -k;
	115
	116	int position = (int) (k % n);
	117	if (!hash_table[position])
	118	hash_table[position] = new wxList (wxKEY_INTEGER);
	119
	120	hash_table[position]->Append (k, object);
	121	}
	122
	123	void wxHashTable::Put (const wxChar key, wxObject object)
	124	{
	125	int position = (int) (MakeKey (key) % n);
	126
	127	if (!hash_table[position])
	128	hash_table[position] = new wxList (wxKEY_STRING);
	129
	130	hash_table[position]->Append (key, object);
	131	}
	132
	133	wxObject *wxHashTable::Get (long key, long value) const
	134	{
	135	// Should NEVER be
	136	long k = (long) key;
	137	if (k < 0)
	138	k = -k;
	139
	140	int position = (int) (k % n);
	141	if (!hash_table[position])
	142	return (wxObject *) NULL;
	143	else
	144	{
	145	wxNode *node = hash_table[position]->Find (value);
	146	if (node)
	147	return node->Data ();
	148	else
	149	return (wxObject *) NULL;
	150	}
	151	}
	152
	153	wxObject wxHashTable::Get (long key, const wxChar value) const
	154	{
	155	// Should NEVER be
	156	long k = (long) key;
	157	if (k < 0)
	158	k = -k;
	159
	160	int position = (int) (k % n);
	161	if (!hash_table[position])
	162	return (wxObject *) NULL;
	163	else
	164	{
	165	wxNode *node = hash_table[position]->Find (value);
	166	if (node)
	167	return node->Data ();
	168	else
	169	return (wxObject *) NULL;
	170	}
	171	}
	172
	173	wxObject *wxHashTable::Get (long key) const
	174	{
	175	// Should NEVER be
	176	long k = (long) key;
	177	if (k < 0)
	178	k = -k;
	179
	180	int position = (int) (k % n);
	181	if (!hash_table[position])
	182	return (wxObject *) NULL;
	183	else
	184	{
	185	wxNode *node = hash_table[position]->Find (k);
	186	return node ? node->Data () : (wxObject*)NULL;
	187	}
	188	}
	189
	190	wxObject wxHashTable::Get (const wxChar key) const
	191	{
	192	int position = (int) (MakeKey (key) % n);
	193
	194	if (!hash_table[position])
	195	return (wxObject *) NULL;
	196	else
	197	{
	198	wxNode *node = hash_table[position]->Find (key);
	199	return node ? node->Data () : (wxObject*)NULL;
	200	}
	201	}
	202
	203	wxObject *wxHashTable::Delete (long key)
	204	{
	205	// Should NEVER be
	206	long k = (long) key;
	207	if (k < 0)
	208	k = -k;
	209
	210	int position = (int) (k % n);
	211	if (!hash_table[position])
	212	return (wxObject *) NULL;
	213	else
	214	{
	215	wxNode *node = hash_table[position]->Find (k);
	216	if (node)
	217	{
	218	wxObject *data = node->Data ();
	219	delete node;
	220	return data;
	221	}
	222	else
	223	return (wxObject *) NULL;
	224	}
	225	}
	226
	227	wxObject wxHashTable::Delete (const wxChar key)
	228	{
	229	int position = (int) (MakeKey (key) % n);
	230	if (!hash_table[position])
	231	return (wxObject *) NULL;
	232	else
	233	{
	234	wxNode *node = hash_table[position]->Find (key);
	235	if (node)
	236	{
	237	wxObject *data = node->Data ();
	238	delete node;
	239	return data;
	240	}
	241	else
	242	return (wxObject *) NULL;
	243	}
	244	}
	245
	246	wxObject *wxHashTable::Delete (long key, int value)
	247	{
	248	// Should NEVER be
	249	long k = (long) key;
	250	if (k < 0)
	251	k = -k;
	252
	253	int position = (int) (k % n);
	254	if (!hash_table[position])
	255	return (wxObject *) NULL;
	256	else
	257	{
	258	wxNode *node = hash_table[position]->Find (value);
	259	if (node)
	260	{
	261	wxObject *data = node->Data ();
	262	delete node;
	263	return data;
	264	}
	265	else
	266	return (wxObject *) NULL;
	267	}
	268	}
	269
	270	wxObject wxHashTable::Delete (long key, const wxChar value)
	271	{
	272	int position = (int) (key % n);
	273	if (!hash_table[position])
	274	return (wxObject *) NULL;
	275	else
	276	{
	277	wxNode *node = hash_table[position]->Find (value);
	278	if (node)
	279	{
	280	wxObject *data = node->Data ();
	281	delete node;
	282	return data;
	283	}
	284	else
	285	return (wxObject *) NULL;
	286	}
	287	}
	288
	289	long wxHashTable::MakeKey (const wxChar *string) const
	290	{
	291	long int_key = 0;
	292
	293	while (*string)
	294	int_key += (wxUChar) *string++;
	295
	296	return int_key;
	297	}
	298
	299	void wxHashTable::BeginFind (void)
	300	{
	301	current_position = -1;
	302	current_node = (wxNode *) NULL;
	303	}
	304
	305	wxNode *wxHashTable::Next (void)
	306	{
	307	wxNode found = (wxNode ) NULL;
	308	bool end = FALSE;
	309	while (!end && !found)
	310	{
	311	if (!current_node)
	312	{
	313	current_position++;
	314	if (current_position >= n)
	315	{
	316	current_position = -1;
	317	current_node = (wxNode *) NULL;
	318	end = TRUE;
	319	}
	320	else
	321	{
	322	if (hash_table[current_position])
	323	{
	324	current_node = hash_table[current_position]->First ();
	325	found = current_node;
	326	}
	327	}
	328	}
	329	else
	330	{
	331	current_node = current_node->Next ();
	332	found = current_node;
	333	}
	334	}
	335	return found;
	336	}
	337
	338	void wxHashTable::DeleteContents (bool flag)
	339	{
	340	int i;
	341	for (i = 0; i < n; i++)
	342	{
	343	if (hash_table[i])
	344	hash_table[i]->DeleteContents (flag);
	345	}
	346	}
	347
	348	void wxHashTable::Clear (void)
	349	{
	350	int i;
	351	for (i = 0; i < n; i++)
	352	{
	353	if (hash_table[i])
	354	hash_table[i]->Clear ();
	355	}
	356	}
	357