]>
git.saurik.com Git - wxWidgets.git/blob - src/common/hash.cpp
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::Destroy()
148 for ( size_t n
= 0; n
< m_hashSize
; n
++ )
160 void wxHashTableLong::Put(long key
, long value
)
162 wxCHECK_RET( m_hashSize
, _T("must call Create() first") );
164 size_t slot
= (size_t)abs((int)(key
% (long)m_hashSize
));
168 m_keys
[slot
] = new wxArrayLong
;
169 m_values
[slot
] = new wxArrayLong
;
172 m_keys
[slot
]->Add(key
);
173 m_values
[slot
]->Add(value
);
178 long wxHashTableLong::Get(long key
) const
180 wxCHECK_MSG( m_hashSize
, wxNOT_FOUND
, _T("must call Create() first") );
182 size_t slot
= (size_t)abs((int)(key
% (long)m_hashSize
));
184 wxArrayLong
*keys
= m_keys
[slot
];
187 size_t count
= keys
->GetCount();
188 for ( size_t n
= 0; n
< count
; n
++ )
190 if ( keys
->Item(n
) == key
)
192 return m_values
[slot
]->Item(n
);
200 long wxHashTableLong::Delete(long key
)
202 wxCHECK_MSG( m_hashSize
, wxNOT_FOUND
, _T("must call Create() first") );
204 size_t slot
= (size_t)abs((int)(key
% (long)m_hashSize
));
206 wxArrayLong
*keys
= m_keys
[slot
];
209 size_t count
= keys
->GetCount();
210 for ( size_t n
= 0; n
< count
; n
++ )
212 if ( keys
->Item(n
) == key
)
214 long val
= m_values
[slot
]->Item(n
);
217 m_values
[slot
]->RemoveAt(n
);
229 // ----------------------------------------------------------------------------
230 // old not type safe wxHashTable
231 // ----------------------------------------------------------------------------
233 wxHashTable::wxHashTable (int the_key_type
, int size
)
236 hash_table
= (wxList
**) NULL
;
237 Create(the_key_type
, size
);
239 m_deleteContents
= FALSE
;
242 current_position = -1;
243 current_node = (wxNode *) NULL;
245 key_type = the_key_type;
246 hash_table = new wxList *[size];
248 for (i = 0; i < size; i++)
249 hash_table[i] = (wxList *) NULL;
253 wxHashTable::~wxHashTable ()
258 void wxHashTable::Destroy()
260 if (!hash_table
) return;
262 for (i
= 0; i
< n
; i
++)
264 delete hash_table
[i
];
269 bool wxHashTable::Create(int the_key_type
, int size
)
274 current_position
= -1;
275 current_node
= (wxNode
*) NULL
;
277 key_type
= the_key_type
;
278 hash_table
= new wxList
*[size
];
280 for (i
= 0; i
< size
; i
++)
281 hash_table
[i
] = (wxList
*) NULL
;
286 void wxHashTable::DoCopy(const wxHashTable
& table
)
289 current_position
= table
.current_position
;
290 current_node
= NULL
; // doesn't matter - Next() will reconstruct it
291 key_type
= table
.key_type
;
293 hash_table
= new wxList
*[n
];
294 for (int i
= 0; i
< n
; i
++) {
295 if (table
.hash_table
[i
] == NULL
)
296 hash_table
[i
] = NULL
;
298 hash_table
[i
] = new wxList(key_type
);
299 *(hash_table
[i
]) = *(table
.hash_table
[i
]);
304 void wxHashTable::Put (long key
, long value
, wxObject
* object
)
309 int position
= (int) (k
% n
);
310 if (position
< 0) position
= -position
;
312 if (!hash_table
[position
])
314 hash_table
[position
] = new wxList (wxKEY_INTEGER
);
315 if (m_deleteContents
) hash_table
[position
]->DeleteContents(TRUE
);
318 hash_table
[position
]->Append (value
, object
);
322 void wxHashTable::Put (long key
, const wxChar
*value
, wxObject
* object
)
327 int position
= (int) (k
% n
);
328 if (position
< 0) position
= -position
;
330 if (!hash_table
[position
])
332 hash_table
[position
] = new wxList (wxKEY_INTEGER
);
333 if (m_deleteContents
) hash_table
[position
]->DeleteContents(TRUE
);
336 hash_table
[position
]->Append (value
, object
);
340 void wxHashTable::Put (long key
, wxObject
* object
)
345 int position
= (int) (k
% n
);
346 if (position
< 0) position
= -position
;
348 if (!hash_table
[position
])
350 hash_table
[position
] = new wxList (wxKEY_INTEGER
);
351 if (m_deleteContents
) hash_table
[position
]->DeleteContents(TRUE
);
354 hash_table
[position
]->Append (k
, object
);
358 void wxHashTable::Put (const wxChar
*key
, wxObject
* object
)
360 int position
= (int) (MakeKey (key
) % n
);
361 if (position
< 0) position
= -position
;
363 if (!hash_table
[position
])
365 hash_table
[position
] = new wxList (wxKEY_STRING
);
366 if (m_deleteContents
) hash_table
[position
]->DeleteContents(TRUE
);
369 hash_table
[position
]->Append (key
, object
);
373 wxObject
*wxHashTable::Get (long key
, long value
) const
378 int position
= (int) (k
% n
);
379 if (position
< 0) position
= -position
;
381 if (!hash_table
[position
])
382 return (wxObject
*) NULL
;
385 wxNode
*node
= hash_table
[position
]->Find (value
);
387 return node
->Data ();
389 return (wxObject
*) NULL
;
393 wxObject
*wxHashTable::Get (long key
, const wxChar
*value
) const
398 int position
= (int) (k
% n
);
399 if (position
< 0) position
= -position
;
401 if (!hash_table
[position
])
402 return (wxObject
*) NULL
;
405 wxNode
*node
= hash_table
[position
]->Find (value
);
407 return node
->Data ();
409 return (wxObject
*) NULL
;
413 wxObject
*wxHashTable::Get (long key
) const
418 int position
= (int) (k
% n
);
419 if (position
< 0) position
= -position
;
421 if (!hash_table
[position
])
422 return (wxObject
*) NULL
;
425 wxNode
*node
= hash_table
[position
]->Find (k
);
426 return node
? node
->Data () : (wxObject
*)NULL
;
430 wxObject
*wxHashTable::Get (const wxChar
*key
) const
432 int position
= (int) (MakeKey (key
) % n
);
433 if (position
< 0) position
= -position
;
435 if (!hash_table
[position
])
436 return (wxObject
*) NULL
;
439 wxNode
*node
= hash_table
[position
]->Find (key
);
440 return node
? node
->Data () : (wxObject
*)NULL
;
444 wxObject
*wxHashTable::Delete (long key
)
449 int position
= (int) (k
% n
);
450 if (position
< 0) position
= -position
;
452 if (!hash_table
[position
])
453 return (wxObject
*) NULL
;
456 wxNode
*node
= hash_table
[position
]->Find (k
);
459 wxObject
*data
= node
->Data ();
465 return (wxObject
*) NULL
;
469 wxObject
*wxHashTable::Delete (const wxChar
*key
)
471 int position
= (int) (MakeKey (key
) % n
);
472 if (position
< 0) position
= -position
;
474 if (!hash_table
[position
])
475 return (wxObject
*) NULL
;
478 wxNode
*node
= hash_table
[position
]->Find (key
);
481 wxObject
*data
= node
->Data ();
487 return (wxObject
*) NULL
;
491 wxObject
*wxHashTable::Delete (long key
, int value
)
496 int position
= (int) (k
% n
);
497 if (position
< 0) position
= -position
;
499 if (!hash_table
[position
])
500 return (wxObject
*) NULL
;
503 wxNode
*node
= hash_table
[position
]->Find (value
);
506 wxObject
*data
= node
->Data ();
512 return (wxObject
*) NULL
;
516 wxObject
*wxHashTable::Delete (long key
, const wxChar
*value
)
518 int position
= (int) (key
% n
);
519 if (position
< 0) position
= -position
;
521 if (!hash_table
[position
])
522 return (wxObject
*) NULL
;
525 wxNode
*node
= hash_table
[position
]->Find (value
);
528 wxObject
*data
= node
->Data ();
534 return (wxObject
*) NULL
;
538 long wxHashTable::MakeKey (const wxChar
*string
) const
543 int_key
+= (wxUChar
) *string
++;
548 void wxHashTable::BeginFind ()
550 current_position
= -1;
551 current_node
= (wxNode
*) NULL
;
554 wxNode
*wxHashTable::Next ()
556 wxNode
*found
= (wxNode
*) NULL
;
558 while (!end
&& !found
)
563 if (current_position
>= n
)
565 current_position
= -1;
566 current_node
= (wxNode
*) NULL
;
571 if (hash_table
[current_position
])
573 current_node
= hash_table
[current_position
]->First ();
574 found
= current_node
;
580 current_node
= current_node
->Next ();
581 found
= current_node
;
587 void wxHashTable::DeleteContents (bool flag
)
590 m_deleteContents
= flag
;
591 for (i
= 0; i
< n
; i
++)
594 hash_table
[i
]->DeleteContents (flag
);
598 void wxHashTable::Clear ()
601 for (i
= 0; i
< n
; i
++)
604 hash_table
[i
]->Clear ();