1 /////////////////////////////////////////////////////////////////////////////
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 and Markus Holzem
9 // Licence: wxWindows licence
10 /////////////////////////////////////////////////////////////////////////////
12 // ============================================================================
14 // ============================================================================
16 // ----------------------------------------------------------------------------
18 // ----------------------------------------------------------------------------
21 #pragma implementation "hash.h"
24 // For compilers that support precompilation, includes "wx.h".
25 #include "wx/wxprec.h"
40 // ----------------------------------------------------------------------------
42 // ----------------------------------------------------------------------------
44 IMPLEMENT_DYNAMIC_CLASS(wxHashTable
, wxObject
)
46 // ============================================================================
48 // ============================================================================
50 // ----------------------------------------------------------------------------
51 // wxHashTablleBase for working with "void *" data
52 // ----------------------------------------------------------------------------
54 wxHashTableBase::wxHashTableBase()
56 m_deleteContents
= FALSE
;
57 m_hashTable
= (wxListBase
**)NULL
;
60 m_keyType
= wxKEY_NONE
;
63 void wxHashTableBase::Create(wxKeyType keyType
, size_t size
)
69 m_hashTable
= new wxListBase
*[size
];
70 for ( size_t n
= 0; n
< m_hashSize
; n
++ )
72 m_hashTable
[n
] = (wxListBase
*) NULL
;
76 void wxHashTableBase::Destroy()
80 for ( size_t n
= 0; n
< m_hashSize
; n
++ )
82 delete m_hashTable
[n
];
85 delete [] m_hashTable
;
87 m_hashTable
= (wxListBase
**)NULL
;
93 void wxHashTableBase::DeleteContents(bool flag
)
95 m_deleteContents
= flag
;
96 for ( size_t n
= 0; n
< m_hashSize
; n
++ )
100 m_hashTable
[n
]->DeleteContents(flag
);
105 wxNodeBase
*wxHashTableBase::GetNode(long key
, long value
) const
107 size_t slot
= (size_t)abs((int)(key
% (long)m_hashSize
));
110 if ( m_hashTable
[slot
] )
112 node
= m_hashTable
[slot
]->Find(wxListKey(value
));
116 node
= (wxNodeBase
*)NULL
;
122 // ----------------------------------------------------------------------------
124 // ----------------------------------------------------------------------------
126 wxHashTableLong::~wxHashTableLong()
131 void wxHashTableLong::Init(size_t size
)
134 m_values
= new wxArrayLong
*[size
];
135 m_keys
= new wxArrayLong
*[size
];
137 for ( size_t n
= 0; n
< m_hashSize
; n
++ )
140 m_keys
[n
] = (wxArrayLong
*)NULL
;
146 void wxHashTableLong::Create(size_t size
)
151 void wxHashTableLong::Destroy()
153 for ( size_t n
= 0; n
< m_hashSize
; n
++ )
165 void wxHashTableLong::Put(long key
, long value
)
167 wxCHECK_RET( m_hashSize
, _T("must call Create() first") );
169 size_t slot
= (size_t)abs((int)(key
% (long)m_hashSize
));
173 m_keys
[slot
] = new wxArrayLong
;
174 m_values
[slot
] = new wxArrayLong
;
177 m_keys
[slot
]->Add(key
);
178 m_values
[slot
]->Add(value
);
183 long wxHashTableLong::Get(long key
) const
185 wxCHECK_MSG( m_hashSize
, wxNOT_FOUND
, _T("must call Create() first") );
187 size_t slot
= (size_t)abs((int)(key
% (long)m_hashSize
));
189 wxArrayLong
*keys
= m_keys
[slot
];
192 size_t count
= keys
->GetCount();
193 for ( size_t n
= 0; n
< count
; n
++ )
195 if ( keys
->Item(n
) == key
)
197 return m_values
[slot
]->Item(n
);
205 long wxHashTableLong::Delete(long key
)
207 wxCHECK_MSG( m_hashSize
, wxNOT_FOUND
, _T("must call Create() first") );
209 size_t slot
= (size_t)abs((int)(key
% (long)m_hashSize
));
211 wxArrayLong
*keys
= m_keys
[slot
];
214 size_t count
= keys
->GetCount();
215 for ( size_t n
= 0; n
< count
; n
++ )
217 if ( keys
->Item(n
) == key
)
219 long val
= m_values
[slot
]->Item(n
);
222 m_values
[slot
]->RemoveAt(n
);
234 // ----------------------------------------------------------------------------
235 // wxStringHashTable: more efficient than storing strings in a list
236 // ----------------------------------------------------------------------------
238 wxStringHashTable::wxStringHashTable(size_t sizeTable
)
240 m_keys
= new wxArrayLong
*[sizeTable
];
241 m_values
= new wxArrayString
*[sizeTable
];
243 m_hashSize
= sizeTable
;
244 for ( size_t n
= 0; n
< m_hashSize
; n
++ )
246 m_values
[n
] = (wxArrayString
*)NULL
;
247 m_keys
[n
] = (wxArrayLong
*)NULL
;
251 wxStringHashTable::~wxStringHashTable()
256 void wxStringHashTable::Destroy()
258 for ( size_t n
= 0; n
< m_hashSize
; n
++ )
269 void wxStringHashTable::Put(long key
, const wxString
& value
)
271 wxCHECK_RET( m_hashSize
, _T("must call Create() first") );
273 size_t slot
= (size_t)abs((int)(key
% (long)m_hashSize
));
277 m_keys
[slot
] = new wxArrayLong
;
278 m_values
[slot
] = new wxArrayString
;
281 m_keys
[slot
]->Add(key
);
282 m_values
[slot
]->Add(value
);
285 wxString
wxStringHashTable::Get(long key
, bool *wasFound
) const
287 wxCHECK_MSG( m_hashSize
, _T(""), _T("must call Create() first") );
289 size_t slot
= (size_t)abs((int)(key
% (long)m_hashSize
));
291 wxArrayLong
*keys
= m_keys
[slot
];
294 size_t count
= keys
->GetCount();
295 for ( size_t n
= 0; n
< count
; n
++ )
297 if ( keys
->Item(n
) == key
)
302 return m_values
[slot
]->Item(n
);
313 // ----------------------------------------------------------------------------
314 // old not type safe wxHashTable
315 // ----------------------------------------------------------------------------
317 wxHashTable::wxHashTable (int the_key_type
, int size
)
320 hash_table
= (wxList
**) NULL
;
321 Create(the_key_type
, size
);
323 m_deleteContents
= FALSE
;
326 current_position = -1;
327 current_node = (wxNode *) NULL;
329 key_type = the_key_type;
330 hash_table = new wxList *[size];
332 for (i = 0; i < size; i++)
333 hash_table[i] = (wxList *) NULL;
337 wxHashTable::~wxHashTable ()
342 void wxHashTable::Destroy()
344 if (!hash_table
) return;
346 for (i
= 0; i
< n
; i
++)
348 delete hash_table
[i
];
353 bool wxHashTable::Create(int the_key_type
, int size
)
358 current_position
= -1;
359 current_node
= (wxNode
*) NULL
;
361 key_type
= the_key_type
;
362 hash_table
= new wxList
*[size
];
364 for (i
= 0; i
< size
; i
++)
365 hash_table
[i
] = (wxList
*) NULL
;
370 void wxHashTable::DoCopy(const wxHashTable
& table
)
373 current_position
= table
.current_position
;
374 current_node
= NULL
; // doesn't matter - Next() will reconstruct it
375 key_type
= table
.key_type
;
377 hash_table
= new wxList
*[n
];
378 for (int i
= 0; i
< n
; i
++) {
379 if (table
.hash_table
[i
] == NULL
)
380 hash_table
[i
] = NULL
;
382 hash_table
[i
] = new wxList(key_type
);
383 *(hash_table
[i
]) = *(table
.hash_table
[i
]);
388 void wxHashTable::Put (long key
, long value
, wxObject
* object
)
393 int position
= (int) (k
% n
);
394 if (position
< 0) position
= -position
;
396 if (!hash_table
[position
])
398 hash_table
[position
] = new wxList (wxKEY_STRING
);
399 if (m_deleteContents
) hash_table
[position
]->DeleteContents(TRUE
);
402 hash_table
[position
]->Append (value
, object
);
406 void wxHashTable::Put (long key
, const wxChar
*value
, wxObject
* object
)
411 int position
= (int) (k
% n
);
412 if (position
< 0) position
= -position
;
414 if (!hash_table
[position
])
416 hash_table
[position
] = new wxList (wxKEY_INTEGER
);
417 if (m_deleteContents
) hash_table
[position
]->DeleteContents(TRUE
);
420 hash_table
[position
]->Append (value
, object
);
424 void wxHashTable::Put (long key
, wxObject
* object
)
429 int position
= (int) (k
% n
);
430 if (position
< 0) position
= -position
;
432 if (!hash_table
[position
])
434 hash_table
[position
] = new wxList (wxKEY_INTEGER
);
435 if (m_deleteContents
) hash_table
[position
]->DeleteContents(TRUE
);
438 hash_table
[position
]->Append (k
, object
);
442 void wxHashTable::Put (const wxChar
*key
, wxObject
* object
)
444 int position
= (int) (MakeKey (key
) % n
);
445 if (position
< 0) position
= -position
;
447 if (!hash_table
[position
])
449 hash_table
[position
] = new wxList (wxKEY_STRING
);
450 if (m_deleteContents
) hash_table
[position
]->DeleteContents(TRUE
);
453 hash_table
[position
]->Append (key
, object
);
457 wxObject
*wxHashTable::Get (long key
, long value
) const
462 int position
= (int) (k
% n
);
463 if (position
< 0) position
= -position
;
465 if (!hash_table
[position
])
466 return (wxObject
*) NULL
;
469 wxNode
*node
= hash_table
[position
]->Find (value
);
471 return node
->Data ();
473 return (wxObject
*) NULL
;
477 wxObject
*wxHashTable::Get (long key
, const wxChar
*value
) const
482 int position
= (int) (k
% n
);
483 if (position
< 0) position
= -position
;
485 if (!hash_table
[position
])
486 return (wxObject
*) NULL
;
489 wxNode
*node
= hash_table
[position
]->Find (value
);
491 return node
->Data ();
493 return (wxObject
*) NULL
;
497 wxObject
*wxHashTable::Get (long key
) const
502 int position
= (int) (k
% n
);
503 if (position
< 0) position
= -position
;
505 if (!hash_table
[position
])
506 return (wxObject
*) NULL
;
509 wxNode
*node
= hash_table
[position
]->Find (k
);
510 return node
? node
->Data () : (wxObject
*)NULL
;
514 wxObject
*wxHashTable::Get (const wxChar
*key
) const
516 int position
= (int) (MakeKey (key
) % n
);
517 if (position
< 0) position
= -position
;
519 if (!hash_table
[position
])
520 return (wxObject
*) NULL
;
523 wxNode
*node
= hash_table
[position
]->Find (key
);
524 return node
? node
->Data () : (wxObject
*)NULL
;
528 wxObject
*wxHashTable::Delete (long key
)
533 int position
= (int) (k
% n
);
534 if (position
< 0) position
= -position
;
536 if (!hash_table
[position
])
537 return (wxObject
*) NULL
;
540 wxNode
*node
= hash_table
[position
]->Find (k
);
543 wxObject
*data
= node
->Data ();
549 return (wxObject
*) NULL
;
553 wxObject
*wxHashTable::Delete (const wxChar
*key
)
555 int position
= (int) (MakeKey (key
) % n
);
556 if (position
< 0) position
= -position
;
558 if (!hash_table
[position
])
559 return (wxObject
*) NULL
;
562 wxNode
*node
= hash_table
[position
]->Find (key
);
565 wxObject
*data
= node
->Data ();
571 return (wxObject
*) NULL
;
575 wxObject
*wxHashTable::Delete (long key
, int value
)
580 int position
= (int) (k
% n
);
581 if (position
< 0) position
= -position
;
583 if (!hash_table
[position
])
584 return (wxObject
*) NULL
;
587 wxNode
*node
= hash_table
[position
]->Find (value
);
590 wxObject
*data
= node
->Data ();
596 return (wxObject
*) NULL
;
600 wxObject
*wxHashTable::Delete (long key
, const wxChar
*value
)
602 int position
= (int) (key
% n
);
603 if (position
< 0) position
= -position
;
605 if (!hash_table
[position
])
606 return (wxObject
*) NULL
;
609 wxNode
*node
= hash_table
[position
]->Find (value
);
612 wxObject
*data
= node
->Data ();
618 return (wxObject
*) NULL
;
622 long wxHashTable::MakeKey (const wxChar
*string
) const
627 int_key
+= (wxUChar
) *string
++;
632 void wxHashTable::BeginFind ()
634 current_position
= -1;
635 current_node
= (wxNode
*) NULL
;
638 wxNode
*wxHashTable::Next ()
640 wxNode
*found
= (wxNode
*) NULL
;
642 while (!end
&& !found
)
647 if (current_position
>= n
)
649 current_position
= -1;
650 current_node
= (wxNode
*) NULL
;
655 if (hash_table
[current_position
])
657 current_node
= hash_table
[current_position
]->First ();
658 found
= current_node
;
664 current_node
= current_node
->Next ();
665 found
= current_node
;
671 void wxHashTable::DeleteContents (bool flag
)
674 m_deleteContents
= flag
;
675 for (i
= 0; i
< n
; i
++)
678 hash_table
[i
]->DeleteContents (flag
);
682 void wxHashTable::Clear ()
687 for (i
= 0; i
< n
; i
++)
690 hash_table
[i
]->Clear ();