/src/wxwidgets/src/common/hash.cpp

Source
/////////////////////////////////////////////////////////////////////////////
// Name:        src/common/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
// Copyright:   (c) Julian Smart
// Licence:     wxWindows licence
/////////////////////////////////////////////////////////////////////////////

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

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

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


#ifndef WX_PRECOMP
    #include "wx/hash.h"
    #include "wx/object.h"
#endif

wxHashTableBase_Node::wxHashTableBase_Node( long key, void* value,
                                            wxHashTableBase* table )
    : m_value( value ), m_hashPtr( table )
{
    m_key.integer = key;
}

wxHashTableBase_Node::wxHashTableBase_Node( const wxString& key, void* value,
                                            wxHashTableBase* table )
    : m_value( value ), m_hashPtr( table )
{
    m_key.string = new wxString(key);
}

wxHashTableBase_Node::~wxHashTableBase_Node()
{
    if( m_hashPtr ) m_hashPtr->DoRemoveNode( this );
}

//

wxHashTableBase::wxHashTableBase()
    : m_size( 0 ), m_count( 0 ), m_table( nullptr ), m_keyType( wxKEY_NONE ),
      m_deleteContents( false )
{
}

void wxHashTableBase::Create( wxKeyType keyType, size_t size )
{
    m_keyType = keyType;
    m_size = size;
    m_table = new wxHashTableBase_Node*[ m_size ];

    for( size_t i = 0; i < m_size; ++i )
        m_table[i] = nullptr;
}

void wxHashTableBase::Clear()
{
    for( size_t i = 0; i < m_size; ++i )
    {
        Node* end = m_table[i];

        if( end == nullptr )
            continue;

        Node *curr, *next = end->GetNext();

        do
        {
            curr = next;
            next = curr->GetNext();

            DoDestroyNode( curr );

            delete curr;
        }
        while( curr != end );

        m_table[i] = nullptr;
    }

    m_count = 0;
}

void wxHashTableBase::DoRemoveNode( wxHashTableBase_Node* node )
{
    size_t bucket = ( m_keyType == wxKEY_INTEGER ?
                      node->m_key.integer        :
                      MakeKey( *node->m_key.string ) ) % m_size;

    if( node->GetNext() == node )
    {
        // single-node chain (common case)
        m_table[bucket] = nullptr;
    }
    else
    {
        Node *start = m_table[bucket], *curr;
        Node* prev = start;

        for( curr = prev->GetNext(); curr != node;
             prev = curr, curr = curr->GetNext() ) ;

        DoUnlinkNode( bucket, node, prev );
    }

    DoDestroyNode( node );
}

void wxHashTableBase::DoDestroyNode( wxHashTableBase_Node* node )
{
    // if it is called from DoRemoveNode, node has already been
    // removed, from other places it does not matter
    node->m_hashPtr = nullptr;

    if( m_keyType == wxKEY_STRING )
        delete node->m_key.string;
    if( m_deleteContents )
        DoDeleteContents( node );
}

void wxHashTableBase::Destroy()
{
    Clear();

    wxDELETEA(m_table);
    m_size = 0;
}

void wxHashTableBase::DoInsertNode( size_t bucket, wxHashTableBase_Node* node )
{
    if( m_table[bucket] == nullptr )
    {
        m_table[bucket] = node->m_next = node;
    }
    else
    {
        Node *prev = m_table[bucket];
        Node *next = prev->m_next;

        prev->m_next = node;
        node->m_next = next;
        m_table[bucket] = node;
    }

    ++m_count;
}

void wxHashTableBase::DoPut( long key, long hash, void* data )
{
    wxASSERT( m_keyType == wxKEY_INTEGER );

    size_t bucket = size_t(hash) % m_size;
    Node* node = new wxHashTableBase_Node( key, data, this );

    DoInsertNode( bucket, node );
}

void wxHashTableBase::DoPut( const wxString& key, long hash, void* data )
{
    wxASSERT( m_keyType == wxKEY_STRING );

    size_t bucket = size_t(hash) % m_size;
    Node* node = new wxHashTableBase_Node( key, data, this );

    DoInsertNode( bucket, node );
}

void* wxHashTableBase::DoGet( long key, long hash ) const
{
    wxASSERT( m_keyType == wxKEY_INTEGER );

    size_t bucket = size_t(hash) % m_size;

    if( m_table[bucket] == nullptr )
        return nullptr;

    Node *first = m_table[bucket]->GetNext(),
         *curr = first;

    do
    {
        if( curr->m_key.integer == key )
            return curr->m_value;

        curr = curr->GetNext();
    }
    while( curr != first );

    return nullptr;
}

void* wxHashTableBase::DoGet( const wxString& key, long hash ) const
{
    wxASSERT( m_keyType == wxKEY_STRING );

    size_t bucket = size_t(hash) % m_size;

    if( m_table[bucket] == nullptr )
        return nullptr;

    Node *first = m_table[bucket]->GetNext(),
         *curr = first;

    do
    {
        if( *curr->m_key.string == key )
            return curr->m_value;

        curr = curr->GetNext();
    }
    while( curr != first );

    return nullptr;
}

void wxHashTableBase::DoUnlinkNode( size_t bucket, wxHashTableBase_Node* node,
                                    wxHashTableBase_Node* prev )
{
    if( node == m_table[bucket] )
        m_table[bucket] = prev;

    if( prev == node && prev == node->GetNext() )
        m_table[bucket] = nullptr;
    else
        prev->m_next = node->m_next;

    DoDestroyNode( node );
    --m_count;
}

void* wxHashTableBase::DoDelete( long key, long hash )
{
    wxASSERT( m_keyType == wxKEY_INTEGER );

    size_t bucket = size_t(hash) % m_size;

    if( m_table[bucket] == nullptr )
        return nullptr;

    Node *first = m_table[bucket]->GetNext(),
         *curr = first,
         *prev = m_table[bucket];

    do
    {
        if( curr->m_key.integer == key )
        {
            void* retval = curr->m_value;
            curr->m_value = nullptr;

            DoUnlinkNode( bucket, curr, prev );
            delete curr;

            return retval;
        }

        prev = curr;
        curr = curr->GetNext();
    }
    while( curr != first );

    return nullptr;
}

void* wxHashTableBase::DoDelete( const wxString& key, long hash )
{
    wxASSERT( m_keyType == wxKEY_STRING );

    size_t bucket = size_t(hash) % m_size;

    if( m_table[bucket] == nullptr )
        return nullptr;

    Node *first = m_table[bucket]->GetNext(),
         *curr = first,
         *prev = m_table[bucket];

    do
    {
        if( *curr->m_key.string == key )
        {
            void* retval = curr->m_value;
            curr->m_value = nullptr;

            DoUnlinkNode( bucket, curr, prev );
            delete curr;

            return retval;
        }

        prev = curr;
        curr = curr->GetNext();
    }
    while( curr != first );

    return nullptr;
}

long wxHashTableBase::MakeKey( const wxString& str )
{
    long int_key = 0;

    const wxStringCharType *p = str.wx_str();
    while( *p )
        int_key += *p++;

    return int_key;
}

// ----------------------------------------------------------------------------
// wxHashTable
// ----------------------------------------------------------------------------

wxHashTable::wxHashTable( const wxHashTable& table )
           : wxHashTableBase()
{
    DoCopy( table );
}

const wxHashTable& wxHashTable::operator=( const wxHashTable& table )
{
    Destroy();
    DoCopy( table );

    return *this;
}

void wxHashTable::DoCopy( const wxHashTable& WXUNUSED(table) )
{
    Create( m_keyType, m_size );

    wxFAIL;
}

void wxHashTable::DoDeleteContents( wxHashTableBase_Node* node )
{
    delete ((wxHashTable_Node*)node)->GetData();
}

void wxHashTable::GetNextNode( size_t bucketStart )
{
    for( size_t i = bucketStart; i < m_size; ++i )
    {
        if( m_table[i] != nullptr )
        {
            m_curr = ((Node*)m_table[i])->GetNext();
            m_currBucket = i;
            return;
        }
    }

    m_curr = nullptr;
    m_currBucket = 0;
}

wxHashTable::Node* wxHashTable::Next()
{
    if( m_curr == nullptr )
        GetNextNode( 0 );
    else
    {
        m_curr = m_curr->GetNext();

        if( m_curr == ( (Node*)m_table[m_currBucket] )->GetNext() )
            GetNextNode( m_currBucket + 1 );
    }

    return m_curr;
}


Coverage Report

Created: 2026-09-20 06:25

Line	Count	Source
1		/////////////////////////////////////////////////////////////////////////////
2		// Name: src/common/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		// Copyright: (c) Julian Smart
8		// Licence: wxWindows licence
9		/////////////////////////////////////////////////////////////////////////////
10
11		// ============================================================================
12		// declarations
13		// ============================================================================
14
15		// ----------------------------------------------------------------------------
16		// headers
17		// ----------------------------------------------------------------------------
18
19		// For compilers that support precompilation, includes "wx.h".
20		#include "wx/wxprec.h"
21
22
23		#ifndef WX_PRECOMP
24		#include "wx/hash.h"
25		#include "wx/object.h"
26		#endif
27
28		wxHashTableBase_Node::wxHashTableBase_Node( long key, void* value,
29		wxHashTableBase* table )
30	0	: m_value( value ), m_hashPtr( table )
31	0	{
32	0	m_key.integer = key;
33	0	}
34
35		wxHashTableBase_Node::wxHashTableBase_Node( const wxString& key, void* value,
36		wxHashTableBase* table )
37	212	: m_value( value ), m_hashPtr( table )
38	212	{
39	212	m_key.string = new wxString(key);
40	212	}
41
42		wxHashTableBase_Node::~wxHashTableBase_Node()
43	0	{
44	0	if( m_hashPtr ) m_hashPtr->DoRemoveNode( this );
45	0	}
46
47		//
48
49		wxHashTableBase::wxHashTableBase()
50	6	: m_size( 0 ), m_count( 0 ), m_table( nullptr ), m_keyType( wxKEY_NONE ),
51	6	m_deleteContents( false )
52	6	{
53	6	}
54
55		void wxHashTableBase::Create( wxKeyType keyType, size_t size )
56	6	{
57	6	m_keyType = keyType;
58	6	m_size = size;
59	6	m_table = new wxHashTableBase_Node*[ m_size ];
60
61	6.00k	for( size_t i = 0; i < m_size; ++i )
62	6.00k	m_table[i] = nullptr;
63	6	}
64
65		void wxHashTableBase::Clear()
66	0	{
67	0	for( size_t i = 0; i < m_size; ++i )
68	0	{
69	0	Node* end = m_table[i];
70
71	0	if( end == nullptr )
72	0	continue;
73
74	0	Node curr, next = end->GetNext();
75
76	0	do
77	0	{
78	0	curr = next;
79	0	next = curr->GetNext();
80
81	0	DoDestroyNode( curr );
82
83	0	delete curr;
84	0	}
85	0	while( curr != end );
86
87	0	m_table[i] = nullptr;
88	0	}
89
90	0	m_count = 0;
91	0	}
92
93		void wxHashTableBase::DoRemoveNode( wxHashTableBase_Node* node )
94	0	{
95	0	size_t bucket = ( m_keyType == wxKEY_INTEGER ?
96	0	node->m_key.integer :
97	0	MakeKey( *node->m_key.string ) ) % m_size;
98
99	0	if( node->GetNext() == node )
100	0	{
101		// single-node chain (common case)
102	0	m_table[bucket] = nullptr;
103	0	}
104	0	else
105	0	{
106	0	Node start = m_table[bucket], curr;
107	0	Node* prev = start;
108
109	0	for( curr = prev->GetNext(); curr != node;
110	0	prev = curr, curr = curr->GetNext() ) ;
111
112	0	DoUnlinkNode( bucket, node, prev );
113	0	}
114
115	0	DoDestroyNode( node );
116	0	}
117
118		void wxHashTableBase::DoDestroyNode( wxHashTableBase_Node* node )
119	0	{
120		// if it is called from DoRemoveNode, node has already been
121		// removed, from other places it does not matter
122	0	node->m_hashPtr = nullptr;
123
124	0	if( m_keyType == wxKEY_STRING )
125	0	delete node->m_key.string;
126	0	if( m_deleteContents )
127	0	DoDeleteContents( node );
128	0	}
129
130		void wxHashTableBase::Destroy()
131	0	{
132	0	Clear();
133
134	0	wxDELETEA(m_table);
135	0	m_size = 0;
136	0	}
137
138		void wxHashTableBase::DoInsertNode( size_t bucket, wxHashTableBase_Node* node )
139	212	{
140	212	if( m_table[bucket] == nullptr )
141	206	{
142	206	m_table[bucket] = node->m_next = node;
143	206	}
144	6	else
145	6	{
146	6	Node *prev = m_table[bucket];
147	6	Node *next = prev->m_next;
148
149	6	prev->m_next = node;
150	6	node->m_next = next;
151	6	m_table[bucket] = node;
152	6	}
153
154	212	++m_count;
155	212	}
156
157		void wxHashTableBase::DoPut( long key, long hash, void* data )
158	0	{
159	0	wxASSERT( m_keyType == wxKEY_INTEGER );
160
161	0	size_t bucket = size_t(hash) % m_size;
162	0	Node* node = new wxHashTableBase_Node( key, data, this );
163
164	0	DoInsertNode( bucket, node );
165	0	}
166
167		void wxHashTableBase::DoPut( const wxString& key, long hash, void* data )
168	212	{
169	212	wxASSERT( m_keyType == wxKEY_STRING );
170
171	212	size_t bucket = size_t(hash) % m_size;
172	212	Node* node = new wxHashTableBase_Node( key, data, this );
173
174	212	DoInsertNode( bucket, node );
175	212	}
176
177		void* wxHashTableBase::DoGet( long key, long hash ) const
178	0	{
179	0	wxASSERT( m_keyType == wxKEY_INTEGER );
180
181	0	size_t bucket = size_t(hash) % m_size;
182
183	0	if( m_table[bucket] == nullptr )
184	0	return nullptr;
185
186	0	Node *first = m_table[bucket]->GetNext(),
187	0	*curr = first;
188
189	0	do
190	0	{
191	0	if( curr->m_key.integer == key )
192	0	return curr->m_value;
193
194	0	curr = curr->GetNext();
195	0	}
196	0	while( curr != first );
197
198	0	return nullptr;
199	0	}
200
201		void* wxHashTableBase::DoGet( const wxString& key, long hash ) const
202	212	{
203	212	wxASSERT( m_keyType == wxKEY_STRING );
204
205	212	size_t bucket = size_t(hash) % m_size;
206
207	212	if( m_table[bucket] == nullptr )
208	206	return nullptr;
209
210	6	Node *first = m_table[bucket]->GetNext(),
211	6	*curr = first;
212
213	6	do
214	6	{
215	6	if( *curr->m_key.string == key )
216	0	return curr->m_value;
217
218	6	curr = curr->GetNext();
219	6	}
220	6	while( curr != first );
221
222	6	return nullptr;
223	6	}
224
225		void wxHashTableBase::DoUnlinkNode( size_t bucket, wxHashTableBase_Node* node,
226		wxHashTableBase_Node* prev )
227	0	{
228	0	if( node == m_table[bucket] )
229	0	m_table[bucket] = prev;
230
231	0	if( prev == node && prev == node->GetNext() )
232	0	m_table[bucket] = nullptr;
233	0	else
234	0	prev->m_next = node->m_next;
235
236	0	DoDestroyNode( node );
237	0	--m_count;
238	0	}
239
240		void* wxHashTableBase::DoDelete( long key, long hash )
241	0	{
242	0	wxASSERT( m_keyType == wxKEY_INTEGER );
243
244	0	size_t bucket = size_t(hash) % m_size;
245
246	0	if( m_table[bucket] == nullptr )
247	0	return nullptr;
248
249	0	Node *first = m_table[bucket]->GetNext(),
250	0	*curr = first,
251	0	*prev = m_table[bucket];
252
253	0	do
254	0	{
255	0	if( curr->m_key.integer == key )
256	0	{
257	0	void* retval = curr->m_value;
258	0	curr->m_value = nullptr;
259
260	0	DoUnlinkNode( bucket, curr, prev );
261	0	delete curr;
262
263	0	return retval;
264	0	}
265
266	0	prev = curr;
267	0	curr = curr->GetNext();
268	0	}
269	0	while( curr != first );
270
271	0	return nullptr;
272	0	}
273
274		void* wxHashTableBase::DoDelete( const wxString& key, long hash )
275	0	{
276	0	wxASSERT( m_keyType == wxKEY_STRING );
277
278	0	size_t bucket = size_t(hash) % m_size;
279
280	0	if( m_table[bucket] == nullptr )
281	0	return nullptr;
282
283	0	Node *first = m_table[bucket]->GetNext(),
284	0	*curr = first,
285	0	*prev = m_table[bucket];
286
287	0	do
288	0	{
289	0	if( *curr->m_key.string == key )
290	0	{
291	0	void* retval = curr->m_value;
292	0	curr->m_value = nullptr;
293
294	0	DoUnlinkNode( bucket, curr, prev );
295	0	delete curr;
296
297	0	return retval;
298	0	}
299
300	0	prev = curr;
301	0	curr = curr->GetNext();
302	0	}
303	0	while( curr != first );
304
305	0	return nullptr;
306	0	}
307
308		long wxHashTableBase::MakeKey( const wxString& str )
309	424	{
310	424	long int_key = 0;
311
312	424	const wxStringCharType *p = str.wx_str();
313	6.90k	while( *p )
314	6.48k	int_key += *p++;
315
316	424	return int_key;
317	424	}
318
319		// ----------------------------------------------------------------------------
320		// wxHashTable
321		// ----------------------------------------------------------------------------
322
323		wxHashTable::wxHashTable( const wxHashTable& table )
324	0	: wxHashTableBase()
325	0	{
326	0	DoCopy( table );
327	0	}
328
329		const wxHashTable& wxHashTable::operator=( const wxHashTable& table )
330	0	{
331	0	Destroy();
332	0	DoCopy( table );
333
334	0	return *this;
335	0	}
336
337		void wxHashTable::DoCopy( const wxHashTable& WXUNUSED(table) )
338	0	{
339	0	Create( m_keyType, m_size );
340
341	0	wxFAIL;
342	0	}
343
344		void wxHashTable::DoDeleteContents( wxHashTableBase_Node* node )
345	0	{
346	0	delete ((wxHashTable_Node*)node)->GetData();
347	0	}
348
349		void wxHashTable::GetNextNode( size_t bucketStart )
350	0	{
351	0	for( size_t i = bucketStart; i < m_size; ++i )
352	0	{
353	0	if( m_table[i] != nullptr )
354	0	{
355	0	m_curr = ((Node*)m_table[i])->GetNext();
356	0	m_currBucket = i;
357	0	return;
358	0	}
359	0	}
360
361	0	m_curr = nullptr;
362	0	m_currBucket = 0;
363	0	}
364
365		wxHashTable::Node* wxHashTable::Next()
366	0	{
367	0	if( m_curr == nullptr )
368	0	GetNextNode( 0 );
369	0	else
370	0	{
371	0	m_curr = m_curr->GetNext();
372
373	0	if( m_curr == ( (Node*)m_table[m_currBucket] )->GetNext() )
374	0	GetNextNode( m_currBucket + 1 );
375	0	}
376
377	0	return m_curr;
378	0	}
379