1 /* -*- mode: C++; tab-width: 4; c-basic-offset: 4; -*- */
2
3 /* AbiSource Program Utilities
4 *
5 * Copyright (C) 2001 Mike Nordell <tamlin@alogonet.se>
6 * Copyright (C) 2001 Dom Lachowicz <cinamod@hotmail.com>
7 *
8 * This program is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU General Public License
10 * as published by the Free Software Foundation; either version 2
11 * of the License, or (at your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21 * 02110-1301 USA.
22 */
23
24 #ifndef UT_HASH_H
25 #define UT_HASH_H
26
27 #include <string.h>
28
29 /* pre-emptive dismissal; ut_types.h is needed by just about everything,
30 * so even if it's commented out in-file that's still a lot of work for
31 * the preprocessor to do...
32 */
33 #ifndef UT_TYPES_H
34 #include "ut_types.h"
35 #endif
36
37 #ifndef UTVECTOR_H
38 #include "ut_vector.h"
39 #endif
40
41 #include "ut_debugmsg.h"
42 #include "ut_string_class.h"
43
44 #if _MSC_VER >= 1310
45 // MSVC++ 7.1 warns about debug output limitations.
46 #pragma warning(disable: 4292)
47 #endif
48
49 // fwd. decl.
50 template <class T> class hash_slot;
51
52 template <class T> class UT_GenericStringMap;
53
54 template <class T> class UT_GenericStringMap
55 {
56 public:
57 UT_GenericStringMap(size_t expected_cardinality = 11);
58 virtual ~UT_GenericStringMap();
59
60 // insertion/addition
61 bool insert(const char* key, T value);
62 bool insert(const UT_String & key, T value);
63
64 void set (const char* key, T val);
65 void set (const UT_String & key, T val);
66
67 // "find"
68 T pick(const char* key) const;
69 T pick(const UT_String & key) const;
70
71 // contains - if contains(key) val will be the result of the lookup
72 bool contains(const char* key, T val) const;
73 bool contains(const UT_String & key, T val) const;
74
75 // these are for removal
76 void remove(const char* key, T /* ignored */);
77 void remove(const UT_String & key, T /* ignored */);
78 void clear();
79
80 /* IMPORTANT: list() is for use only with <XML_C/char*> maps
81 */
82 const gchar ** list ();
83
84 UT_GenericVector<T>* enumerate(bool strip_null_values = true) const;
85 UT_GenericVector<const UT_String*>* keys(bool strip_null_values = true) const;
86
87 // getting the # keys
size()88 inline size_t size() const { return n_keys; }
89
90 class UT_Cursor
91 {
92 friend class UT_GenericStringMap<T>;
93
94 public:
UT_Cursor(const UT_GenericStringMap<T> * owner)95 UT_Cursor(const UT_GenericStringMap<T> * owner)
96 : m_d(owner), m_index(-1)
97 {
98 //m_d._first(this);
99 }
100
~UT_Cursor()101 ~UT_Cursor() { }
102
103 // these can't be const since we're passing a non-const this ptr
key()104 inline const UT_String &key()
105 {return m_d->_key(*this); }
make_deleted()106 inline void make_deleted()
107 {m_d->_make_deleted(*this); }
first()108 inline const T first()
109 { return m_d->_first(*this); }
next()110 inline const T next()
111 { return m_d->_next(*this); }
prev()112 inline const T prev()
113 { return m_d->_prev(*this); }
is_valid()114 inline bool is_valid()
115 { return (m_index != -1); }
116
117 private:
118
_set_index(UT_sint32 i)119 inline void _set_index(UT_sint32 i)
120 { m_index = i; }
_get_index()121 inline UT_sint32 _get_index()
122 { return m_index; }
123
124 const UT_GenericStringMap<T>* m_d;
125 UT_sint32 m_index;
126 };
127
128 friend class UT_Cursor;
129
130 /* purge objects by deleting them */
purgeData(void)131 void purgeData(void)
132 {
133 UT_Cursor hc1(this);
134 for ( T hval1 = hc1.first(); hc1.is_valid(); hval1 = hc1.next() ) {
135 if (hval1) {
136 hc1.make_deleted();
137 delete hval1;
138 }
139 }
140 };
141
142 /* purge objects by freeing them */
freeData(void)143 void freeData(void)
144 {
145 UT_Cursor hc1(this);
146 for ( T hval1 = hc1.first(); hc1.is_valid(); hval1 = hc1.next() ) {
147 if (hval1) {
148 hc1.make_deleted();
149 g_free((gpointer)(hval1));
150 }
151 }
152 }
153
154 private:
155 UT_GenericStringMap(const UT_GenericStringMap<T>&); // no impl
156 void operator=(const UT_GenericStringMap<T>&); // no impl
157
158
159 enum SM_search_type
160 {
161 SM_INSERT,
162 SM_LOOKUP,
163 SM_REORG
164 };
165
166 void reorg(size_t slots_to_allocate);
167 void grow();
168
169 void assign_slots(hash_slot<T>* p, size_t old_num_slots);
170
171 static size_t compute_reorg_threshold(size_t nslots);
172
too_full()173 bool too_full() const
174 { return (n_keys + n_deleted) >= reorg_threshold; }
175
too_many_deleted()176 bool too_many_deleted() const
177 { return n_deleted > (reorg_threshold / 4); }
178
exceeds_n_delete_threshold()179 bool exceeds_n_delete_threshold() const
180 { return n_deleted > (reorg_threshold / 2); }
181
182 hash_slot<T>* find_slot(const UT_String& k,
183 SM_search_type search_type,
184 size_t& slot,
185 bool& key_found,
186 size_t& hashval,
187 const void* v,
188 bool* v_found,
189 void* vi,
190 size_t hashval_in) const;
191
192 hash_slot<T>* find_slot(const char * k,
193 SM_search_type search_type,
194 size_t& slot,
195 bool& key_found,
196 size_t& hashval,
197 const void* v,
198 bool* v_found,
199 void* vi,
200 size_t hashval_in) const;
201
202 // enumeration of the elements
203 const T _first(UT_Cursor& c) const;
204 const T _next(UT_Cursor& c) const;
205 const T _prev(UT_Cursor& c) const;
206 const UT_String& _key(UT_Cursor& c) const;
207 void _make_deleted(UT_Cursor& c) const;
208
209 // data
210 hash_slot<T>* m_pMapping;
211
212 size_t n_keys;
213 size_t n_deleted;
214 size_t m_nSlots;
215 size_t reorg_threshold;
216 size_t flags;
217
218 gchar ** m_list;
219 };
220
221 #if 0 //def _MSC_VER // have to intialise the templates in order to have class exported
222
223 struct _dataItemPair;
224 template class ABI_EXPORT UT_GenericStringMap<struct _dataItemPair*>;
225
226 class UT_UTF8String;
227 template class ABI_EXPORT UT_GenericStringMap<UT_UTF8String *>;
228
229 class PD_Style;
230 template class ABI_EXPORT UT_GenericStringMap<PD_Style *>;
231
232 class GR_Font;
233 template class ABI_EXPORT UT_GenericStringMap<GR_Font *>;
234
235 template class ABI_EXPORT UT_GenericStringMap<char *>;
236
237 //template class ABI_EXPORT UT_GenericStringMap<void const*>;
238 #endif
239
240 // TODO Rob: try to export like this once plugin loading is fixed:
241 // template class ABI_EXPORT UT_GenericStringMap<void const *>;
242 class ABI_EXPORT UT_StringPtrMap : public UT_GenericStringMap<void const *> {
243 public:
244 UT_StringPtrMap(size_t expected_cardinality = 11)
245 : UT_GenericStringMap<void const *>(expected_cardinality)
246 {}
247 };
248
249 // Template implementation
250
251 // fwd. decls.
252 ABI_EXPORT UT_uint32 _Recommended_hash_size(UT_uint32 size);
253
254
255 // wrapper class for keys
256 class ABI_EXPORT key_wrapper
257 {
258 public:
key_wrapper()259 key_wrapper()
260 : m_hashval(0) { }
261
die()262 void die()
263 { m_val.clear(); }
264
eq(const UT_String & key)265 bool eq(const UT_String &key) const
266 {
267 return (m_val == key);
268 }
269
eq(const char * key)270 bool eq(const char *key) const
271 {
272 return (!strcmp(m_val.c_str(),key));
273 }
274
275 void operator=(const UT_String &k)
276 { m_val = k; }
277
hashval()278 UT_uint32 hashval() const
279 { return m_hashval; }
set_hashval(UT_uint32 h)280 void set_hashval(UT_uint32 h)
281 { m_hashval = h; }
282
value(void)283 UT_String &value(void)
284 {return m_val;}
285
286 void operator=(const key_wrapper& rhs)
287 { m_val = rhs.m_val; m_hashval = rhs.m_hashval; }
288
compute_hash(const UT_String & key)289 static UT_uint32 compute_hash(const UT_String &key)
290 {
291 return hashcode(key); // UT_String::hashcode
292 }
293
compute_hash(const char * key)294 static UT_uint32 compute_hash(const char *key)
295 {
296 return hashcode(key);
297 }
298
299 private:
300 UT_String m_val;
301 UT_uint32 m_hashval;
302 };
303
304
305
306
307 // bucket for data
308 template <class T> class hash_slot
309 {
310 public:
hash_slot()311 hash_slot()
312 : m_value(0) { }
313
make_deleted()314 void make_deleted()
315 {
316 // this is a HACK: if the value of the slot is this, then slot is empty.
317 m_value = reinterpret_cast<T>(this);
318 m_key.die();
319 }
make_empty()320 void make_empty()
321 { m_value = 0; }
322
value()323 const T value() const
324 { return m_value; }
325
insert(const T v,const UT_String & k,UT_uint32 h)326 void insert(const T v, const UT_String &k, UT_uint32 h)
327 {
328 m_value = v;
329 m_key = k;
330 m_key.set_hashval(h);
331 }
332
assign(hash_slot<T> * s)333 void assign(hash_slot<T>* s)
334 {
335 m_value = s->value();
336 m_key = s->m_key;
337 }
338
empty()339 bool empty() const
340 { return (m_value == 0); }
341
deleted()342 bool deleted() const
343 {
344 return static_cast<const void*>(this) == m_value;
345 }
346
key_eq(const UT_String & test,size_t h)347 bool key_eq(const UT_String &test, size_t h) const
348 {
349 #if 1
350 UT_UNUSED(h);
351 return m_key.eq(test);
352 #else
353 return m_key.hashval() == h;
354 #endif
355 }
356
key_eq(const char * test,size_t h)357 bool key_eq(const char *test, size_t h) const
358 {
359 #if 1
360 UT_UNUSED(h);
361 return m_key.eq(test);
362 #else
363 return m_key.hashval() == h;
364 #endif
365 }
366
367 T m_value;
368 key_wrapper m_key;
369 };
370
371 /*!
372 * This class represents a mapping between key/value pairs where the keys are
373 * represented by UT_String (a wrapper around char*) and the values may be of
374 * any pointer type (void*)
375 */
376 template <class T>
UT_GenericStringMap(size_t expected_cardinality)377 UT_GenericStringMap<T>::UT_GenericStringMap(size_t expected_cardinality)
378 : n_keys(0),
379 n_deleted(0),
380 m_nSlots(_Recommended_hash_size(expected_cardinality)),
381 reorg_threshold(compute_reorg_threshold(m_nSlots)),
382 flags(0),
383 m_list(0)
384 {
385 m_pMapping = new hash_slot<T>[m_nSlots];
386 }
387
388
389 template <class T>
~UT_GenericStringMap()390 UT_GenericStringMap<T>::~UT_GenericStringMap()
391 {
392 DELETEPV(m_pMapping);
393 FREEP(m_list);
394 }
395
396 /* IMPORTANT: for use only with <char*> -> <char*> maps
397 TODO: make this a specialized method.
398 */
399 template <class T>
list()400 const gchar ** UT_GenericStringMap<T>::list()
401 {
402 if (!m_list)
403 {
404 m_list = reinterpret_cast<gchar **>(g_try_malloc (2 * (n_keys + 1) * sizeof (gchar *)));
405 if (m_list == 0)
406 return 0;
407
408 UT_uint32 index = 0;
409
410 UT_Cursor c(this);
411
412 for (const gchar * value = (gchar*)(c.first ());
413 c.is_valid ();
414 value = (gchar*)(c.next ()))
415 {
416 const char * key = c.key().c_str ();
417
418 if (!key || !value)
419 continue;
420
421 m_list[index++] = static_cast<gchar *>(const_cast<char *>(key));
422 m_list[index++] = static_cast<gchar *>(const_cast<char *>(value));
423 }
424 m_list[index++] = NULL;
425 m_list[index ] = NULL;
426 }
427 return const_cast<const gchar **>(m_list);
428 }
429
430 /*!
431 * Find the value associated with the key \k
432 * \return 0 if key not found, object if found
433 */
434 template <class T>
pick(const char * k)435 T UT_GenericStringMap<T>::pick(const char* k) const
436 {
437 hash_slot<T>* sl = 0;
438 bool key_found = false;
439 size_t slot;
440 size_t hashval;
441
442 sl = find_slot(k, SM_LOOKUP, slot, key_found, hashval, 0, 0, 0, 0);
443 return key_found ? sl->value() : 0;
444 }
445
446 template <class T>
pick(const UT_String & k)447 T UT_GenericStringMap<T>::pick(const UT_String & k) const
448 {
449 return pick (k.c_str());
450 }
451
452 /*!
453 * See if the map contains the (key, value) pair represented by (\k, \v)
454 * If \v is null, just see if the key \k exists
455 * \return truth
456 */
457 template <class T>
contains(const char * k,T v)458 bool UT_GenericStringMap<T>::contains(const char* k, T v) const
459 {
460 UT_String aKey(k);
461 return contains (aKey, v);
462 }
463
464 template <class T>
contains(const UT_String & k,T v)465 bool UT_GenericStringMap<T>::contains(const UT_String& k, T v) const
466 {
467 // hash_slot<T> * sl;
468 bool key_found = false;
469 bool v_found = false;
470 size_t slot = 0;
471 size_t hashval = 0;
472
473 // DOM: TODO: make this call work
474 /*sl =*/ find_slot (k, SM_LOOKUP, slot, key_found,
475 hashval, v, &v_found, 0, 0);
476 return v_found;
477 }
478
479
480 /*!
481 * Insert this key/value pair into the map
482 */
483 template <class T>
insert(const char * key,T value)484 bool UT_GenericStringMap<T>::insert(const char* key, T value)
485 {
486 UT_String aKey(key);
487 return insert (aKey, value);
488 }
489
490 template <class T>
insert(const UT_String & key,T value)491 bool UT_GenericStringMap<T>::insert(const UT_String& key, T value)
492 {
493 FREEP(m_list);
494
495 size_t slot = 0;
496 bool key_found = false;
497 size_t hashval = 0;
498
499 hash_slot<T>* sl = find_slot(key, SM_INSERT, slot, key_found,
500 hashval, 0, 0, 0, 0);
501
502 if(key_found)
503 return false;
504
505 sl->insert(value, key, hashval);
506 ++n_keys;
507
508 if (too_full())
509 {
510 if (too_many_deleted())
511 {
512 reorg(m_nSlots);
513 }
514 else
515 {
516 grow();
517 }
518 }
519
520 return true;
521 }
522
523 /*!
524 * Set the item determined by \key to the value \value
525 * If item(\key) does not exist, insert it into the map
526 */
527 template <class T>
set(const char * key,T value)528 void UT_GenericStringMap<T>::set(const char* key, T value)
529 {
530 UT_String aKey(key);
531 set (aKey, value);
532 }
533
534 template <class T>
set(const UT_String & key,T value)535 void UT_GenericStringMap<T>::set(const UT_String& key, T value)
536 {
537 FREEP(m_list);
538
539 size_t slot = 0;
540 bool key_found = false;
541 size_t hashval = 0;
542
543 hash_slot<T>* sl = find_slot(key, SM_LOOKUP, slot, key_found,
544 hashval, 0, 0, 0, 0);
545
546 if (!sl || !key_found) // TODO: should we insert or just return?
547 {
548 insert(key, value);
549 return;
550
551 }
552
553 sl->insert(value, key, hashval);
554 }
555
556 /*!
557 * Return a UT_Vector of elements in the HashTable that you must
558 * Later g_free with a call to delete
559 */
560 template <class T>
enumerate(bool strip_null_values)561 UT_GenericVector<T>* UT_GenericStringMap<T>::enumerate (bool strip_null_values) const
562 {
563 UT_GenericVector<T> * pVec = new UT_GenericVector<T>(size());
564
565 UT_Cursor cursor(this);
566
567 T val = NULL;
568
569 for (val = cursor.first(); cursor.is_valid(); val = cursor.next ())
570 {
571 // we don't allow nulls since so much of our code depends on this
572 // behavior
573 if (!strip_null_values || val)
574 {
575 pVec->addItem (val);
576 }
577 }
578
579 return pVec;
580 }
581
582 /*!
583 * Return a UT_Vector of pointers to our UT_String keys in the Hashtable
584 * You must FREEP the UT_Vector* but not the keys
585 */
586 template <class T>
keys(bool strip_null_values)587 UT_GenericVector<const UT_String*>* UT_GenericStringMap<T>::keys (bool strip_null_values) const
588 {
589 UT_GenericVector<const UT_String*>* pVec = new UT_GenericVector<const UT_String*>(size());
590
591 UT_Cursor cursor(this);
592
593 T val = NULL;
594
595 for (val = cursor.first(); cursor.is_valid(); val = cursor.next ())
596 {
597 // we don't allow nulls since so much of our code depends on this
598 // behavior
599 if (!strip_null_values || val)
600 {
601 pVec->addItem (&cursor.key());
602 }
603 }
604
605 return pVec;
606 }
607
608
609 /*!
610 * Remove the item referenced by \key in the map
611 */
612 template <class T>
remove(const char * key,T)613 void UT_GenericStringMap<T>::remove(const char* key, T)
614 {
615 UT_String aKey(key);
616 remove (aKey, 0);
617 }
618
619 template <class T>
remove(const UT_String & key,T)620 void UT_GenericStringMap<T>::remove(const UT_String& key, T)
621 {
622 FREEP(m_list);
623
624 size_t slot = 0, hashval;
625 bool bFound = false;
626 hash_slot<T>* sl = find_slot(key, SM_LOOKUP, slot, bFound,
627 hashval, 0, 0, 0, 0);
628
629 if (bFound)
630 {
631 sl->make_deleted();
632 --n_keys;
633 ++n_deleted;
634 if (m_nSlots > 11 && m_nSlots / 4 >= n_keys)
635 {
636 reorg(_Recommended_hash_size(m_nSlots/2));
637 }
638 }
639 }
640
641 /*!
642 * Remove all key/value pairs from the map
643 */
644 template <class T>
clear()645 void UT_GenericStringMap<T>::clear()
646 {
647 FREEP(m_list);
648
649 hash_slot<T>* the_slots = m_pMapping;
650 for (size_t x=0; x < m_nSlots; x++)
651 {
652 hash_slot<T>& this_slot = the_slots[x];
653 if (!this_slot.empty())
654 {
655 if (!this_slot.deleted())
656 {
657 this_slot.make_deleted();
658 }
659 this_slot.make_empty();
660 }
661 }
662 n_keys = 0;
663 n_deleted = 0;
664 }
665
666
667 /*********************************************************************/
668 /*********************************************************************/
669
670 template <class T>
assign_slots(hash_slot<T> * p,size_t old_num_slot)671 void UT_GenericStringMap<T>::assign_slots(hash_slot<T>* p, size_t old_num_slot)
672 {
673 size_t target_slot = 0;
674
675 for (size_t slot_num=0; slot_num < old_num_slot; ++slot_num, ++p)
676 {
677 if (!p->empty() && !p->deleted())
678 {
679 bool kf = false;
680
681 size_t hv;
682 hash_slot<T>* sl = find_slot(p->m_key.value(),
683 SM_REORG,
684 target_slot,
685 kf,
686 hv,
687 0,
688 0,
689 NULL,
690 p->m_key.hashval());
691 sl->assign(p);
692 }
693 }
694 }
695
696 template <class T>
compute_reorg_threshold(size_t nSlots)697 size_t UT_GenericStringMap<T>::compute_reorg_threshold(size_t nSlots)
698 {
699 return nSlots * 7 / 10; // reorg threshold = 70% of nSlots
700 }
701
702
703 template <class T> hash_slot<T>*
find_slot(const UT_String & k,SM_search_type search_type,size_t & slot,bool & key_found,size_t & hashval,const void * v,bool * v_found,void * vi,size_t hashval_in)704 UT_GenericStringMap<T>::find_slot(const UT_String& k,
705 SM_search_type search_type,
706 size_t& slot,
707 bool& key_found,
708 size_t& hashval,
709 const void* v,
710 bool* v_found,
711 void* vi,
712 size_t hashval_in) const
713 {
714 return find_slot( k.c_str(), search_type, slot, key_found, hashval, v, v_found, vi, hashval_in);
715 }
716
717 template <class T> hash_slot<T>*
find_slot(const char * k,SM_search_type search_type,size_t & slot,bool & key_found,size_t & hashval,const void * v,bool * v_found,void *,size_t hashval_in)718 UT_GenericStringMap<T>::find_slot(const char *k,
719 SM_search_type search_type,
720 size_t& slot,
721 bool& key_found,
722 size_t& hashval,
723 const void* v,
724 bool* v_found,
725 void* /*vi*/,
726 size_t hashval_in) const
727 {
728 if ( m_nSlots == 0 )
729 {
730 key_found = false ; return NULL ;
731 }
732
733 hashval = (hashval_in ? hashval_in : key_wrapper::compute_hash(k));
734 int nSlot = hashval % m_nSlots;
735
736 xxx_UT_DEBUGMSG(("DOM: hashval for \"%s\" is %d (#%dth slot)\n", k, hashval, nSlot));
737
738 hash_slot<T>* sl = &m_pMapping[nSlot];
739
740 if (sl->empty())
741 {
742
743 xxx_UT_DEBUGMSG(("DOM: empty slot\n"));
744
745 slot = nSlot;
746 key_found = false;
747 return sl;
748 }
749 else
750 {
751 if (search_type != SM_REORG &&
752 !sl->deleted() &&
753 sl->key_eq(k, hashval))
754 {
755 slot = nSlot;
756 key_found = true;
757
758 if (v_found)
759 {
760 // so, if v_found is non-null, we should set it.
761 // if v is also non-null, sl->value() must match v
762 // otherwise we already have a key match, so we win!
763 if (v)
764 {
765 *v_found = (sl->value() == v);
766 } else {
767 *v_found = true;
768 }
769 }
770
771 xxx_UT_DEBUGMSG(("DOM: found something #1\n"));
772
773 return sl;
774 }
775 }
776
777 int delta = (nSlot ? (m_nSlots - nSlot) : 1);
778 hash_slot<T>* tmp_sl = sl;
779 sl = 0;
780 size_t s = 0;
781 key_found = false;
782
783 while (1)
784 {
785 nSlot -= delta;
786 if (nSlot < 0)
787 {
788 nSlot += m_nSlots;
789 tmp_sl += (m_nSlots - delta);
790 }
791 else
792 {
793 tmp_sl -= delta;
794 }
795
796 if (tmp_sl->empty())
797 {
798 if (!s)
799 {
800 s = nSlot;
801 sl = tmp_sl;
802 }
803 break;
804
805 }
806
807 if (tmp_sl->deleted())
808 {
809 if (!s)
810 {
811 s = nSlot;
812 sl = tmp_sl;
813 }
814 }
815 else if (search_type != SM_REORG && tmp_sl->key_eq(k, hashval))
816 {
817 s = nSlot;
818 sl = tmp_sl;
819 key_found = true;
820
821 if (v_found)
822 {
823 if (v)
824 {
825 *v_found = (sl->value() == v);
826 } else {
827 *v_found = true;
828 }
829 }
830 break;
831 }
832 }
833
834 slot = s;
835 return sl;
836 }
837
838
839 template <class T>
grow()840 void UT_GenericStringMap<T>::grow()
841 {
842 size_t slots_to_allocate = ::_Recommended_hash_size(m_nSlots / 2 + m_nSlots);
843 reorg(slots_to_allocate);
844 }
845
846
847 template <class T>
reorg(size_t slots_to_allocate)848 void UT_GenericStringMap<T>::reorg(size_t slots_to_allocate)
849 {
850 hash_slot<T>* pOld = m_pMapping;
851
852 if (slots_to_allocate < 11)
853 {
854 slots_to_allocate = 11;
855 }
856
857 m_pMapping = new hash_slot<T>[slots_to_allocate];
858
859 const size_t old_num_slot = m_nSlots;
860
861 m_nSlots = slots_to_allocate;
862 reorg_threshold = compute_reorg_threshold(m_nSlots);
863
864 assign_slots(pOld, old_num_slot);
865 DELETEPV(pOld);
866
867 n_deleted = 0;
868 }
869
870
871 template <class T> const T
_first(UT_Cursor & c)872 UT_GenericStringMap<T>::_first(UT_Cursor& c) const
873 {
874 const hash_slot<T>* map = m_pMapping;
875 size_t x;
876 for (x=0; x < m_nSlots; ++x)
877 {
878 if (!map[x].empty() && !map[x].deleted())
879 {
880 break;
881 }
882 }
883 if (x < m_nSlots)
884 {
885 c._set_index(x); // c = 'UT_Cursor etc'
886 return map[x].value();
887 }
888
889 c._set_index(-1);
890 return 0;
891 }
892
893 template <class T>
_key(UT_Cursor & c)894 const UT_String& UT_GenericStringMap<T>::_key(UT_Cursor& c) const
895 {
896 hash_slot<T> & slot = m_pMapping[c._get_index()];
897
898 // we used to return a reference to a static variable here in case the
899 // following conditions failed, but that breaks some compilers (the
900 // variable has to be instantiated somewhere for each template instance
901 // and this can lead to multiple instances of it in different abi
902 // modules (for example with the cs2005q3.2 compiler for Maemo 2) --
903 // the caller must ensure that the cursor is valid; that is not that
904 // much to ask
905 UT_ASSERT_HARMLESS(!slot.empty() && !slot.deleted());
906
907 return slot.m_key.value();
908 }
909
910 template <class T>
_make_deleted(UT_Cursor & c)911 void UT_GenericStringMap<T>::_make_deleted(UT_Cursor& c) const
912 {
913 hash_slot<T> & slot = m_pMapping[c._get_index()];
914
915 if (!slot.empty() && !slot.deleted())
916 {
917 slot.make_deleted();
918 }
919 }
920
921 template <class T> const T
_next(UT_Cursor & c)922 UT_GenericStringMap<T>::_next(UT_Cursor& c) const
923 {
924 const hash_slot<T>* map = m_pMapping;
925 size_t x;
926 for (x = c._get_index() + 1; x < m_nSlots; ++x)
927 {
928 if (!map[x].empty() && !map[x].deleted())
929 {
930 break;
931 }
932 }
933 if (x < m_nSlots)
934 {
935 c._set_index(x);
936 return map[x].value();
937 }
938
939 c._set_index(-1);
940 return 0;
941 }
942
943
944 template <class T> const T
_prev(UT_Cursor & c)945 UT_GenericStringMap<T>::_prev(UT_Cursor& c) const
946 {
947 const hash_slot<T>* map = m_pMapping;
948 UT_sint32 x;
949 for (x = c._get_index() - 1; x >= 0; --x)
950 {
951 if (!map[x].empty() && !map[x].deleted())
952 {
953 break;
954 }
955 }
956 if (x >= 0)
957 {
958 c._set_index(x);
959 return map[x].value();
960 }
961
962 c._set_index(-1);
963 return 0;
964 }
965
966
967 #endif /* UT_HASH_H */
968