]>
git.saurik.com Git - wxWidgets.git/blob - src/common/hash.cpp
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()
8 // Copyright: (c) Julian Smart
9 // Licence: wxWindows licence
10 /////////////////////////////////////////////////////////////////////////////
12 // ============================================================================
14 // ============================================================================
16 // ----------------------------------------------------------------------------
18 // ----------------------------------------------------------------------------
20 // For compilers that support precompilation, includes "wx.h".
21 #include "wx/wxprec.h"
32 #if wxUSE_OLD_HASH_TABLE
37 // ----------------------------------------------------------------------------
39 // ----------------------------------------------------------------------------
41 IMPLEMENT_DYNAMIC_CLASS(wxHashTable
, wxObject
)
43 // ============================================================================
45 // ============================================================================
47 // ----------------------------------------------------------------------------
48 // wxHashTablleBase for working with "void *" data
49 // ----------------------------------------------------------------------------
51 wxHashTableBase::wxHashTableBase()
53 m_deleteContents
= false;
54 m_hashTable
= (wxListBase
**)NULL
;
57 m_keyType
= wxKEY_NONE
;
60 void wxHashTableBase::Create(wxKeyType keyType
, size_t size
)
66 m_hashTable
= new wxListBase
*[size
];
67 for ( size_t n
= 0; n
< m_hashSize
; n
++ )
69 m_hashTable
[n
] = (wxListBase
*) NULL
;
73 void wxHashTableBase::Destroy()
77 for ( size_t n
= 0; n
< m_hashSize
; n
++ )
79 delete m_hashTable
[n
];
82 delete [] m_hashTable
;
84 m_hashTable
= (wxListBase
**)NULL
;
90 void wxHashTableBase::DeleteContents(bool flag
)
92 m_deleteContents
= flag
;
93 for ( size_t n
= 0; n
< m_hashSize
; n
++ )
97 m_hashTable
[n
]->DeleteContents(flag
);
102 wxNodeBase
*wxHashTableBase::GetNode(long key
, long value
) const
104 size_t slot
= (size_t)abs((int)(key
% (long)m_hashSize
));
107 if ( m_hashTable
[slot
] )
109 node
= m_hashTable
[slot
]->Find(wxListKey(value
));
113 node
= (wxNodeBase
*)NULL
;
119 // ----------------------------------------------------------------------------
120 // old not type safe wxHashTable
121 // ----------------------------------------------------------------------------
123 wxHashTable::wxHashTable (int the_key_type
, int size
)
126 hash_table
= (wxList
**) NULL
;
127 Create(the_key_type
, size
);
129 m_deleteContents
= false;
132 current_position = -1;
133 current_node = (wxNode *) NULL;
135 key_type = the_key_type;
136 hash_table = new wxList *[size];
138 for (i = 0; i < size; i++)
139 hash_table[i] = (wxList *) NULL;
143 wxHashTable::~wxHashTable ()
148 void wxHashTable::Destroy()
150 if (!hash_table
) return;
152 for (i
= 0; i
< n
; i
++)
154 delete hash_table
[i
];
159 bool wxHashTable::Create(int the_key_type
, int size
)
164 current_position
= -1;
165 current_node
= (wxNode
*) NULL
;
167 key_type
= the_key_type
;
168 hash_table
= new wxList
*[size
];
170 for (i
= 0; i
< size
; i
++)
171 hash_table
[i
] = (wxList
*) NULL
;
176 void wxHashTable::DoCopy(const wxHashTable
& table
)
179 m_count
= table
.m_count
;
180 current_position
= table
.current_position
;
181 current_node
= NULL
; // doesn't matter - Next() will reconstruct it
182 key_type
= table
.key_type
;
184 hash_table
= new wxList
*[n
];
185 for (int i
= 0; i
< n
; i
++) {
186 if (table
.hash_table
[i
] == NULL
)
187 hash_table
[i
] = NULL
;
189 hash_table
[i
] = new wxList(key_type
);
190 *(hash_table
[i
]) = *(table
.hash_table
[i
]);
195 void wxHashTable::Put (long key
, long value
, wxObject
* object
)
200 int position
= (int) (k
% n
);
201 if (position
< 0) position
= -position
;
203 if (!hash_table
[position
])
205 hash_table
[position
] = new wxList (wxKEY_INTEGER
);
206 if (m_deleteContents
) hash_table
[position
]->DeleteContents(true);
209 hash_table
[position
]->Append (value
, object
);
213 void wxHashTable::Put (long key
, const wxChar
*value
, wxObject
* object
)
218 int position
= (int) (k
% n
);
219 if (position
< 0) position
= -position
;
221 if (!hash_table
[position
])
223 hash_table
[position
] = new wxList (wxKEY_STRING
);
224 if (m_deleteContents
) hash_table
[position
]->DeleteContents(true);
227 hash_table
[position
]->Append (value
, object
);
231 void wxHashTable::Put (long key
, wxObject
* object
)
236 int position
= (int) (k
% n
);
237 if (position
< 0) position
= -position
;
239 if (!hash_table
[position
])
241 hash_table
[position
] = new wxList (wxKEY_INTEGER
);
242 if (m_deleteContents
) hash_table
[position
]->DeleteContents(true);
245 hash_table
[position
]->Append (k
, object
);
249 void wxHashTable::Put (const wxChar
*key
, wxObject
* object
)
251 int position
= (int) (MakeKey (key
) % n
);
252 if (position
< 0) position
= -position
;
254 if (!hash_table
[position
])
256 hash_table
[position
] = new wxList (wxKEY_STRING
);
257 if (m_deleteContents
) hash_table
[position
]->DeleteContents(true);
260 hash_table
[position
]->Append (key
, object
);
264 wxObject
*wxHashTable::Get (long key
, long value
) const
269 int position
= (int) (k
% n
);
270 if (position
< 0) position
= -position
;
272 if (!hash_table
[position
])
273 return (wxObject
*) NULL
;
276 wxNode
*node
= hash_table
[position
]->Find (value
);
278 return node
->GetData ();
280 return (wxObject
*) NULL
;
284 wxObject
*wxHashTable::Get (long key
, const wxChar
*value
) const
289 int position
= (int) (k
% n
);
290 if (position
< 0) position
= -position
;
292 if (!hash_table
[position
])
293 return (wxObject
*) NULL
;
296 wxNode
*node
= hash_table
[position
]->Find (value
);
298 return node
->GetData ();
300 return (wxObject
*) NULL
;
304 wxObject
*wxHashTable::Get (long key
) const
309 int position
= (int) (k
% n
);
310 if (position
< 0) position
= -position
;
312 if (!hash_table
[position
])
313 return (wxObject
*) NULL
;
316 wxNode
*node
= hash_table
[position
]->Find (k
);
317 return node
? node
->GetData () : (wxObject
*)NULL
;
321 wxObject
*wxHashTable::Get (const wxChar
*key
) const
323 int position
= (int) (MakeKey (key
) % n
);
324 if (position
< 0) position
= -position
;
326 if (!hash_table
[position
])
327 return (wxObject
*) NULL
;
330 wxNode
*node
= hash_table
[position
]->Find (key
);
331 return node
? node
->GetData () : (wxObject
*)NULL
;
335 wxObject
*wxHashTable::Delete (long key
)
340 int position
= (int) (k
% n
);
341 if (position
< 0) position
= -position
;
343 if (!hash_table
[position
])
344 return (wxObject
*) NULL
;
347 wxNode
*node
= hash_table
[position
]->Find (k
);
350 wxObject
*data
= node
->GetData ();
356 return (wxObject
*) NULL
;
360 wxObject
*wxHashTable::Delete (const wxChar
*key
)
362 int position
= (int) (MakeKey (key
) % n
);
363 if (position
< 0) position
= -position
;
365 if (!hash_table
[position
])
366 return (wxObject
*) NULL
;
369 wxNode
*node
= hash_table
[position
]->Find (key
);
372 wxObject
*data
= node
->GetData ();
378 return (wxObject
*) NULL
;
382 wxObject
*wxHashTable::Delete (long key
, int value
)
387 int position
= (int) (k
% n
);
388 if (position
< 0) position
= -position
;
390 if (!hash_table
[position
])
391 return (wxObject
*) NULL
;
394 wxNode
*node
= hash_table
[position
]->Find (value
);
397 wxObject
*data
= node
->GetData ();
403 return (wxObject
*) NULL
;
407 wxObject
*wxHashTable::Delete (long key
, const wxChar
*value
)
409 int position
= (int) (key
% n
);
410 if (position
< 0) position
= -position
;
412 if (!hash_table
[position
])
413 return (wxObject
*) NULL
;
416 wxNode
*node
= hash_table
[position
]->Find (value
);
419 wxObject
*data
= node
->GetData ();
425 return (wxObject
*) NULL
;
429 long wxHashTable::MakeKey (const wxChar
*string
) const
434 int_key
+= (wxUChar
) *string
++;
439 void wxHashTable::BeginFind ()
441 current_position
= -1;
442 current_node
= (wxNode
*) NULL
;
445 wxHashTable::Node
* wxHashTable::Next ()
447 wxNode
*found
= (wxNode
*) NULL
;
449 while (!end
&& !found
)
454 if (current_position
>= n
)
456 current_position
= -1;
457 current_node
= (wxNode
*) NULL
;
462 if (hash_table
[current_position
])
464 current_node
= hash_table
[current_position
]->GetFirst ();
465 found
= current_node
;
471 current_node
= current_node
->GetNext ();
472 found
= current_node
;
478 void wxHashTable::DeleteContents (bool flag
)
481 m_deleteContents
= flag
;
482 for (i
= 0; i
< n
; i
++)
485 hash_table
[i
]->DeleteContents (flag
);
489 void wxHashTable::Clear ()
494 for (i
= 0; i
< n
; i
++)
497 hash_table
[i
]->Clear ();
503 #else // if !wxUSE_OLD_HASH_TABLE
505 wxHashTableBase_Node::wxHashTableBase_Node( long key
, void* value
,
506 wxHashTableBase
* table
)
507 : m_value( value
), m_hashPtr( table
)
512 wxHashTableBase_Node::wxHashTableBase_Node( const wxChar
* key
, void* value
,
513 wxHashTableBase
* table
)
514 : m_value( value
), m_hashPtr( table
)
516 m_key
.string
= wxStrcpy( new wxChar
[wxStrlen( key
) + 1], key
);
519 wxHashTableBase_Node::~wxHashTableBase_Node()
521 if( m_hashPtr
) m_hashPtr
->DoRemoveNode( this );
526 wxHashTableBase::wxHashTableBase()
527 : m_size( 0 ), m_count( 0 ), m_table( NULL
), m_keyType( wxKEY_NONE
),
528 m_deleteContents( false )
532 void wxHashTableBase::Create( wxKeyType keyType
, size_t size
)
536 m_table
= new wxHashTableBase_Node
*[ m_size
];
538 for( size_t i
= 0; i
< m_size
; ++i
)
542 void wxHashTableBase::Clear()
544 for( size_t i
= 0; i
< m_size
; ++i
)
546 Node
* end
= m_table
[i
];
551 Node
*curr
, *next
= end
->GetNext();
556 next
= curr
->GetNext();
558 DoDestroyNode( curr
);
562 while( curr
!= end
);
570 void wxHashTableBase::DoRemoveNode( wxHashTableBase_Node
* node
)
572 size_t bucket
= ( m_keyType
== wxKEY_INTEGER
?
573 node
->m_key
.integer
:
574 MakeKey( node
->m_key
.string
) ) % m_size
;
576 if( node
->GetNext() == node
)
578 // single-node chain (common case)
579 m_table
[bucket
] = NULL
;
583 Node
*start
= m_table
[bucket
], *curr
;
586 for( curr
= prev
->GetNext(); curr
!= node
;
587 prev
= curr
, curr
= curr
->GetNext() ) ;
589 DoUnlinkNode( bucket
, node
, prev
);
592 DoDestroyNode( node
);
595 void wxHashTableBase::DoDestroyNode( wxHashTableBase_Node
* node
)
597 // if it is called from DoRemoveNode, node has already been
598 // removed, from other places it does not matter
599 node
->m_hashPtr
= NULL
;
601 if( m_keyType
== wxKEY_STRING
)
602 delete[] node
->m_key
.string
;
603 if( m_deleteContents
)
604 DoDeleteContents( node
);
607 void wxHashTableBase::Destroy()
617 void wxHashTableBase::DoInsertNode( size_t bucket
, wxHashTableBase_Node
* node
)
619 if( m_table
[bucket
] == NULL
)
621 m_table
[bucket
] = node
->m_next
= node
;
625 Node
*prev
= m_table
[bucket
];
626 Node
*next
= prev
->m_next
;
630 m_table
[bucket
] = node
;
636 void wxHashTableBase::DoPut( long key
, long hash
, void* data
)
638 wxASSERT( m_keyType
== wxKEY_INTEGER
);
640 size_t bucket
= size_t(hash
) % m_size
;
641 Node
* node
= new wxHashTableBase_Node( key
, data
, this );
643 DoInsertNode( bucket
, node
);
646 void wxHashTableBase::DoPut( const wxChar
* key
, long hash
, void* data
)
648 wxASSERT( m_keyType
== wxKEY_STRING
);
650 size_t bucket
= size_t(hash
) % m_size
;
651 Node
* node
= new wxHashTableBase_Node( key
, data
, this );
653 DoInsertNode( bucket
, node
);
656 void* wxHashTableBase::DoGet( long key
, long hash
) const
658 wxASSERT( m_keyType
== wxKEY_INTEGER
);
660 size_t bucket
= size_t(hash
) % m_size
;
662 if( m_table
[bucket
] == NULL
)
665 Node
*first
= m_table
[bucket
]->GetNext(),
670 if( curr
->m_key
.integer
== key
)
671 return curr
->m_value
;
673 curr
= curr
->GetNext();
675 while( curr
!= first
);
680 void* wxHashTableBase::DoGet( const wxChar
* key
, long hash
) const
682 wxASSERT( m_keyType
== wxKEY_STRING
);
684 size_t bucket
= size_t(hash
) % m_size
;
686 if( m_table
[bucket
] == NULL
)
689 Node
*first
= m_table
[bucket
]->GetNext(),
694 if( wxStrcmp( curr
->m_key
.string
, key
) == 0 )
695 return curr
->m_value
;
697 curr
= curr
->GetNext();
699 while( curr
!= first
);
704 void wxHashTableBase::DoUnlinkNode( size_t bucket
, wxHashTableBase_Node
* node
,
705 wxHashTableBase_Node
* prev
)
707 if( node
== m_table
[bucket
] )
708 m_table
[bucket
] = prev
;
710 if( prev
== node
&& prev
== node
->GetNext() )
711 m_table
[bucket
] = NULL
;
713 prev
->m_next
= node
->m_next
;
715 DoDestroyNode( node
);
719 void* wxHashTableBase::DoDelete( long key
, long hash
)
721 wxASSERT( m_keyType
== wxKEY_INTEGER
);
723 size_t bucket
= size_t(hash
) % m_size
;
725 if( m_table
[bucket
] == NULL
)
728 Node
*first
= m_table
[bucket
]->GetNext(),
730 *prev
= m_table
[bucket
];
734 if( curr
->m_key
.integer
== key
)
736 void* retval
= curr
->m_value
;
737 curr
->m_value
= NULL
;
739 DoUnlinkNode( bucket
, curr
, prev
);
746 curr
= curr
->GetNext();
748 while( curr
!= first
);
753 void* wxHashTableBase::DoDelete( const wxChar
* key
, long hash
)
755 wxASSERT( m_keyType
== wxKEY_STRING
);
757 size_t bucket
= size_t(hash
) % m_size
;
759 if( m_table
[bucket
] == NULL
)
762 Node
*first
= m_table
[bucket
]->GetNext(),
764 *prev
= m_table
[bucket
];
768 if( wxStrcmp( curr
->m_key
.string
, key
) == 0 )
770 void* retval
= curr
->m_value
;
771 curr
->m_value
= NULL
;
773 DoUnlinkNode( bucket
, curr
, prev
);
780 curr
= curr
->GetNext();
782 while( curr
!= first
);
787 long wxHashTableBase::MakeKey( const wxChar
*str
)
792 int_key
+= (wxUChar
)*str
++;
797 // ----------------------------------------------------------------------------
799 // ----------------------------------------------------------------------------
801 wxHashTable::wxHashTable( const wxHashTable
& table
)
807 const wxHashTable
& wxHashTable::operator=( const wxHashTable
& table
)
815 void wxHashTable::DoCopy( const wxHashTable
& WXUNUSED(table
) )
817 Create( m_keyType
, m_size
);
822 void wxHashTable::DoDeleteContents( wxHashTableBase_Node
* node
)
824 delete ((wxHashTable_Node
*)node
)->GetData();
827 void wxHashTable::GetNextNode( size_t bucketStart
)
829 for( size_t i
= bucketStart
; i
< m_size
; ++i
)
831 if( m_table
[i
] != NULL
)
833 m_curr
= ((Node
*)m_table
[i
])->GetNext();
843 wxHashTable::Node
* wxHashTable::Next()
849 m_curr
= m_curr
->GetNext();
851 if( m_curr
== ( (Node
*)m_table
[m_currBucket
] )->GetNext() )
852 GetNextNode( m_currBucket
+ 1 );
858 #endif // !wxUSE_OLD_HASH_TABLE