Click
Loading...
Searching...
No Matches
hashmap.cc
1/*
2 * hashmap.{cc,hh} -- a hash table template
3 * Eddie Kohler
4 *
5 * Copyright (c) 2000 Mazu Networks, Inc.
6 * Copyright (c) 2003 International Computer Science Institute
7 *
8 * Permission is hereby granted, free of charge, to any person obtaining a
9 * copy of this software and associated documentation files (the "Software"),
10 * to deal in the Software without restriction, subject to the conditions
11 * listed in the Click LICENSE file. These conditions include: you must
12 * preserve this copyright notice, and you cannot mention the copyright
13 * holders in advertising related to the Software without their permission.
14 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
15 * notice is a summary of the Click LICENSE file; the license in that file is
16 * legally binding.
17 */
18
19#ifndef CLICK_HASHMAP_CC
20#define CLICK_HASHMAP_CC
21#include <click/hashmap.hh>
22#include <click/bighashmap_arena.hh>
23#include <click/glue.hh>
24CLICK_DECLS
27#define BIGHASHMAP_REARRANGE_ON_FIND 0
28
29template <class K, class V>
30void
31HashMap<K, V>::initialize(HashMap_ArenaFactory *factory, size_t initial_nbuckets)
32{
33 _nbuckets = initial_nbuckets;
34 _buckets = (Elt **) CLICK_LALLOC(_nbuckets * sizeof(Elt *));
35 for (size_t i = 0; i < _nbuckets; i++)
36 _buckets[i] = 0;
37 set_dynamic_resizing(true);
38
39 _n = 0;
40
41 set_arena(factory);
42}
43
44template <class K, class V>
45HashMap<K, V>::HashMap()
46 : _default_value(), _arena(0)
47{
48 initialize(0, DEFAULT_INITIAL_NBUCKETS);
49}
50
51template <class K, class V>
52HashMap<K, V>::HashMap(const V &def, HashMap_ArenaFactory *factory)
53 : _default_value(def), _arena(0)
54{
55 initialize(factory, DEFAULT_INITIAL_NBUCKETS);
56}
57
58template <class K, class V>
59void
60HashMap<K, V>::copy_from(const HashMap<K, V> &o)
61 // requires that 'this' is empty and has the same number of buckets as 'o'
62 // and the same resize policy
63{
64 for (size_t i = 0; i < _nbuckets; i++) {
65 Elt **pprev = &_buckets[i];
66 *pprev = 0;
67 for (const Elt *e = o._buckets[i]; e; e = e->next) {
68 Elt *ee = reinterpret_cast<Elt *>(_arena->alloc());
69 new(reinterpret_cast<void *>(&ee->key)) K(e->key);
70 new(reinterpret_cast<void *>(&ee->value)) V(e->value);
71 ee->next = 0;
72 *pprev = ee;
73 pprev = &ee->next;
74 }
75 }
76 _n = o._n;
77}
78
79template <class K, class V>
80HashMap<K, V>::HashMap(const HashMap<K, V> &o)
81 : _buckets((Elt **) CLICK_LALLOC(o._nbuckets * sizeof(Elt *))),
82 _nbuckets(o._nbuckets), _default_value(o._default_value),
83 _capacity(o._capacity), _arena(o._arena)
84{
85 _arena->use();
86 copy_from(o);
87}
88
89template <class K, class V>
90HashMap<K, V> &
91HashMap<K, V>::operator=(const HashMap<K, V> &o)
92{
93 if (&o != this) {
94 clear();
95 _default_value = o._default_value;
96 if (_nbuckets < o._nbuckets)
97 resize0(o._nbuckets);
98 _nbuckets = o._nbuckets;
99 _capacity = o._capacity;
100 copy_from(o);
101 }
102 return *this;
103}
104
105template <class K, class V>
106HashMap<K, V>::~HashMap()
107{
108 for (size_t i = 0; i < _nbuckets; i++)
109 for (Elt *e = _buckets[i]; e; ) {
110 Elt *next = e->next;
111 e->key.~K();
112 e->value.~V();
113 _arena->free(e);
114 e = next;
115 }
116 CLICK_LFREE(_buckets, _nbuckets * sizeof(Elt *));
117 _arena->unuse();
118}
119
120template <class K, class V>
121void
122HashMap<K, V>::set_dynamic_resizing(bool on)
123{
124 if (!on)
125 _capacity = 0x7FFFFFFF;
126 else if (_nbuckets >= MAX_NBUCKETS)
127 _capacity = 0x7FFFFFFE;
128 else
129 _capacity = DEFAULT_RESIZE_THRESHOLD * _nbuckets;
130}
131
132template <class K, class V>
133void
134HashMap<K, V>::set_arena(HashMap_ArenaFactory *factory)
135{
136 assert(empty());
137 if (_arena)
138 _arena->unuse();
139 _arena = HashMap_ArenaFactory::get_arena(sizeof(Elt), factory);
140 _arena->use();
141}
142
143template <class K, class V>
144inline size_t
145HashMap<K, V>::bucket(const K &key) const
146{
147 return ((size_t) hashcode(key)) % _nbuckets;
148}
149
150template <class K, class V>
151typename HashMap<K, V>::Pair *
152HashMap<K, V>::find_pair(const K &key) const
153{
154#if BIGHASHMAP_REARRANGE_ON_FIND
155 Elt *prev = 0;
156 size_t b = bucket(key);
157 for (Elt *e = _buckets[b]; e; prev = e, e = e->next)
158 if (e->key == key) {
159 if (prev) {
160 // move to front
161 prev->next = e->next;
162 e->next = _buckets[b];
163 _buckets[b] = e;
164 }
165 return e;
166 }
167 return 0;
168#else
169 for (Elt *e = _buckets[bucket(key)]; e; e = e->next)
170 if (e->key == key)
171 return e;
172 return 0;
173#endif
174}
175
176
177template <class K, class V>
178void
179HashMap<K, V>::resize0(size_t new_nbuckets)
180{
181 Elt **new_buckets = (Elt **) CLICK_LALLOC(new_nbuckets * sizeof(Elt *));
182 for (size_t i = 0; i < new_nbuckets; i++)
183 new_buckets[i] = 0;
184
185 size_t old_nbuckets = _nbuckets;
186 Elt **old_buckets = _buckets;
187 _nbuckets = new_nbuckets;
188 _buckets = new_buckets;
189 if (dynamic_resizing())
190 set_dynamic_resizing(true); // reset threshold
191
192 for (size_t i = 0; i < old_nbuckets; i++)
193 for (Elt *e = old_buckets[i]; e; ) {
194 Elt *n = e->next;
195 size_t b = bucket(e->key);
196 e->next = new_buckets[b];
197 new_buckets[b] = e;
198 e = n;
199 }
200
201 CLICK_LFREE(old_buckets, old_nbuckets * sizeof(Elt *));
202}
203
204template <class K, class V>
205void
206HashMap<K, V>::resize(size_t want_nbuckets)
207{
208 size_t new_nbuckets = 1;
209 while (new_nbuckets < want_nbuckets && new_nbuckets < MAX_NBUCKETS)
210 new_nbuckets = ((new_nbuckets + 1) << 1) - 1;
211 assert(new_nbuckets > 0 && new_nbuckets <= MAX_NBUCKETS);
212 if (_nbuckets != new_nbuckets)
213 resize0(new_nbuckets);
214}
215
216template <class K, class V>
217bool
218HashMap<K, V>::insert(const K &key, const V &value)
219{
220 size_t b = bucket(key);
221 for (Elt *e = _buckets[b]; e; e = e->next)
222 if (e->key == key) {
223 e->value = value;
224 return false;
225 }
226
227 if (_n >= _capacity) {
228 resize(_nbuckets + 1);
229 b = bucket(key);
230 }
231
232 if (Elt *e = reinterpret_cast<Elt *>(_arena->alloc())) {
233 new(reinterpret_cast<void *>(&e->key)) K(key);
234 new(reinterpret_cast<void *>(&e->value)) V(value);
235 e->next = _buckets[b];
236 _buckets[b] = e;
237 _n++;
238 }
239 return true;
240}
241
242template <class K, class V>
243bool
244HashMap<K, V>::erase(const K &key)
245{
246 size_t b = bucket(key);
247 Elt *prev = 0;
248 Elt *e = _buckets[b];
249 while (e && !(e->key == key)) {
250 prev = e;
251 e = e->next;
252 }
253 if (e) {
254 if (prev)
255 prev->next = e->next;
256 else
257 _buckets[b] = e->next;
258 e->key.~K();
259 e->value.~V();
260 _arena->free(e);
261 _n--;
262 return true;
263 } else
264 return false;
265}
266
267template <class K, class V>
268typename HashMap<K, V>::Pair *
269HashMap<K, V>::find_pair_force(const K &key, const V &default_value)
270{
271 size_t b = bucket(key);
272 for (Elt *e = _buckets[b]; e; e = e->next)
273 if (e->key == key)
274 return e;
275 if (_n >= _capacity) {
276 resize(_nbuckets + 1);
277 b = bucket(key);
278 }
279 if (Elt *e = reinterpret_cast<Elt *>(_arena->alloc())) {
280 new(reinterpret_cast<void *>(&e->key)) K(key);
281 new(reinterpret_cast<void *>(&e->value)) V(default_value);
282 e->next = _buckets[b];
283 _buckets[b] = e;
284 _n++;
285 return e;
286 } else
287 return 0;
288}
289
290template <class K, class V>
291void
292HashMap<K, V>::clear()
293{
294 for (size_t i = 0; i < _nbuckets; i++) {
295 for (Elt *e = _buckets[i]; e; ) {
296 Elt *next = e->next;
297 e->key.~K();
298 e->value.~V();
299 _arena->free(e);
300 e = next;
301 }
302 _buckets[i] = 0;
303 }
304 _n = 0;
305}
306
307template <class K, class V>
308void
309HashMap<K, V>::swap(HashMap<K, V> &o)
310{
311 Elt **t_elts;
312 V t_v;
313 size_t t_size;
314 HashMap_Arena *t_arena;
315
316 t_elts = _buckets; _buckets = o._buckets; o._buckets = t_elts;
317 t_size = _nbuckets; _nbuckets = o._nbuckets; o._nbuckets = t_size;
318 t_v = _default_value; _default_value = o._default_value; o._default_value = t_v;
319
320 t_size = _n; _n = o._n; o._n = t_size;
321 t_size = _capacity; _capacity = o._capacity; o._capacity = t_size;
322
323 t_arena = _arena; _arena = o._arena; o._arena = t_arena;
324}
325
326template <class K, class V>
327_HashMap_const_iterator<K, V>::_HashMap_const_iterator(const HashMap<K, V> *hm, bool begin)
328 : _hm(hm)
329{
330 size_t nb = _hm->_nbuckets;
331 typename HashMap<K, V>::Elt **b = _hm->_buckets;
332 for (_bucket = 0; _bucket < nb && begin; _bucket++)
333 if (b[_bucket]) {
334 _elt = b[_bucket];
335 return;
336 }
337 _elt = 0;
338}
339
340template <class K, class V>
341void
342_HashMap_const_iterator<K, V>::operator++(int)
343{
344 if (_elt->next)
345 _elt = _elt->next;
346 else {
347 size_t nb = _hm->_nbuckets;
348 typename HashMap<K, V>::Elt **b = _hm->_buckets;
349 for (_bucket++; _bucket < nb; _bucket++)
350 if (b[_bucket]) {
351 _elt = b[_bucket];
352 return;
353 }
354 _elt = 0;
355 }
356}
357
358#if 0
359static size_t
360HashMap_partition_elts(void **elts, size_t left, size_t right)
361{
362 void *pivot = elts[(left + right) / 2];
363
364 // loop invariant:
365 // elts[i] < pivot for all left_init <= i < left
366 // elts[i] > pivot for all right < i <= right_init
367 while (left < right) {
368 if (elts[left] < pivot)
369 left++;
370 else if (elts[right] > pivot)
371 right--;
372 else {
373 void *x = elts[left];
374 elts[left] = elts[right];
375 elts[right] = x;
376 }
377 }
378
379 return left;
380}
381
382void
383HashMap_qsort_elts(void **elts, size_t left, size_t right)
384{
385 if (left < right) {
386 size_t split = HashMap_partition_elts(elts, left, right);
387 HashMap_qsort_elts(elts, left, split);
388 HashMap_qsort_elts(elts, split, right);
389 }
390}
391#endif
392
393
394// void * partial specialization
395
396template <class K>
397void
398HashMap<K, void *>::initialize(HashMap_ArenaFactory *factory, size_t initial_nbuckets)
399{
400 _nbuckets = initial_nbuckets;
401 _buckets = (Elt **) CLICK_LALLOC(_nbuckets * sizeof(Elt *));
402 for (size_t i = 0; i < _nbuckets; i++)
403 _buckets[i] = 0;
404 set_dynamic_resizing(true);
405
406 _n = 0;
407
408 set_arena(factory);
409}
410
411template <class K>
412HashMap<K, void *>::HashMap()
413 : _default_value(0), _arena(0)
414{
415 initialize(0, DEFAULT_INITIAL_NBUCKETS);
416}
417
418template <class K>
419HashMap<K, void *>::HashMap(void *def, HashMap_ArenaFactory *factory)
420 : _default_value(def), _arena(0)
421{
422 initialize(factory, DEFAULT_INITIAL_NBUCKETS);
423}
424
425template <class K>
426void
427HashMap<K, void *>::copy_from(const HashMap<K, void *> &o)
428{
429 for (size_t i = 0; i < _nbuckets; i++) {
430 Elt **pprev = &_buckets[i];
431 *pprev = 0;
432 for (const Elt *e = o._buckets[i]; e; e = e->next) {
433 Elt *ee = reinterpret_cast<Elt *>(_arena->alloc());
434 new(reinterpret_cast<void *>(&ee->key)) K(e->key);
435 ee->value = e->value;
436 ee->next = 0;
437 *pprev = ee;
438 pprev = &ee->next;
439 }
440 }
441 _n = o._n;
442}
443
444template <class K>
445HashMap<K, void *>::HashMap(const HashMap<K, void *> &o)
446 : _buckets((Elt **) CLICK_LALLOC(o._nbuckets * sizeof(Elt *))),
447 _nbuckets(o._nbuckets), _default_value(o._default_value),
448 _capacity(o._capacity), _arena(o._arena)
449{
450 _arena->use();
451 copy_from(o);
452}
453
454template <class K>
455HashMap<K, void *> &
456HashMap<K, void *>::operator=(const HashMap<K, void *> &o)
457{
458 if (&o != this) {
459 clear();
460 _default_value = o._default_value;
461 if (_nbuckets < o._nbuckets)
462 resize0(o._nbuckets);
463 _nbuckets = o._nbuckets;
464 _capacity = o._capacity;
465 copy_from(o);
466 }
467 return *this;
468}
469
470template <class K>
471HashMap<K, void *>::~HashMap()
472{
473 for (size_t i = 0; i < _nbuckets; i++)
474 for (Elt *e = _buckets[i]; e; ) {
475 Elt *next = e->next;
476 e->key.~K();
477 _arena->free(e);
478 e = next;
479 }
480 CLICK_LFREE(_buckets, _nbuckets * sizeof(Elt *));
481 _arena->unuse();
482}
483
484template <class K>
485void
486HashMap<K, void *>::set_dynamic_resizing(bool on)
487{
488 if (!on)
489 _capacity = 0x7FFFFFFF;
490 else if (_nbuckets >= MAX_NBUCKETS)
491 _capacity = 0x7FFFFFFE;
492 else
493 _capacity = DEFAULT_RESIZE_THRESHOLD * _nbuckets;
494}
495
496template <class K>
497void
498HashMap<K, void *>::set_arena(HashMap_ArenaFactory *factory)
499{
500 assert(empty());
501 if (_arena)
502 _arena->unuse();
503 _arena = HashMap_ArenaFactory::get_arena(sizeof(Elt), factory);
504 _arena->use();
505}
506
507template <class K>
508inline size_t
509HashMap<K, void *>::bucket(const K &key) const
510{
511 return ((size_t) hashcode(key)) % _nbuckets;
512}
513
514template <class K>
515typename HashMap<K, void *>::Pair *
516HashMap<K, void *>::find_pair(const K &key) const
517{
518#if BIGHASHMAP_REARRANGE_ON_FIND
519 Elt *prev = 0;
520 size_t b = bucket(key);
521 for (Elt *e = _buckets[b]; e; prev = e, e = e->next)
522 if (e->key == key) {
523 if (prev) {
524 // move to front
525 prev->next = e->next;
526 e->next = _buckets[b];
527 _buckets[b] = e;
528 }
529 return e;
530 }
531 return 0;
532#else
533 for (Elt *e = _buckets[bucket(key)]; e; e = e->next)
534 if (e->key == key)
535 return e;
536 return 0;
537#endif
538}
539
540
541template <class K>
542void
543HashMap<K, void *>::resize0(size_t new_nbuckets)
544{
545 Elt **new_buckets = (Elt **) CLICK_LALLOC(new_nbuckets * sizeof(Elt *));
546 for (size_t i = 0; i < new_nbuckets; i++)
547 new_buckets[i] = 0;
548
549 size_t old_nbuckets = _nbuckets;
550 Elt **old_buckets = _buckets;
551 _nbuckets = new_nbuckets;
552 _buckets = new_buckets;
553 if (dynamic_resizing())
554 set_dynamic_resizing(true); // reset threshold
555
556 for (size_t i = 0; i < old_nbuckets; i++)
557 for (Elt *e = old_buckets[i]; e; ) {
558 Elt *n = e->next;
559 size_t b = bucket(e->key);
560 e->next = new_buckets[b];
561 new_buckets[b] = e;
562 e = n;
563 }
564
565 CLICK_LFREE(old_buckets, old_nbuckets * sizeof(Elt *));
566}
567
568template <class K>
569void
570HashMap<K, void *>::resize(size_t want_nbuckets)
571{
572 size_t new_nbuckets = 1;
573 while (new_nbuckets < want_nbuckets && new_nbuckets < MAX_NBUCKETS)
574 new_nbuckets = ((new_nbuckets + 1) << 1) - 1;
575 assert(new_nbuckets > 0 && new_nbuckets <= MAX_NBUCKETS);
576 if (_nbuckets != new_nbuckets)
577 resize0(new_nbuckets);
578}
579
580template <class K>
581bool
582HashMap<K, void *>::insert(const K &key, void *value)
583{
584 size_t b = bucket(key);
585 for (Elt *e = _buckets[b]; e; e = e->next)
586 if (e->key == key) {
587 e->value = value;
588 return false;
589 }
590
591 if (_n >= _capacity) {
592 resize(_nbuckets + 1);
593 b = bucket(key);
594 }
595
596 if (Elt *e = reinterpret_cast<Elt *>(_arena->alloc())) {
597 new(reinterpret_cast<void *>(&e->key)) K(key);
598 e->value = value;
599 e->next = _buckets[b];
600 _buckets[b] = e;
601 _n++;
602 }
603 return true;
604}
605
606template <class K>
607bool
608HashMap<K, void *>::erase(const K &key)
609{
610 size_t b = bucket(key);
611 Elt *prev = 0;
612 Elt *e = _buckets[b];
613 while (e && !(e->key == key)) {
614 prev = e;
615 e = e->next;
616 }
617 if (e) {
618 if (prev)
619 prev->next = e->next;
620 else
621 _buckets[b] = e->next;
622 e->key.~K();
623 _arena->free(e);
624 _n--;
625 return true;
626 } else
627 return false;
628}
629
630template <class K>
631typename HashMap<K, void *>::Pair *
632HashMap<K, void *>::find_pair_force(const K &key, void *default_value)
633{
634 size_t b = bucket(key);
635 for (Elt *e = _buckets[b]; e; e = e->next)
636 if (e->key == key)
637 return e;
638 if (_n >= _capacity) {
639 resize(_nbuckets + 1);
640 b = bucket(key);
641 }
642 if (Elt *e = reinterpret_cast<Elt *>(_arena->alloc())) {
643 new(reinterpret_cast<void *>(&e->key)) K(key);
644 e->value = default_value;
645 e->next = _buckets[b];
646 _buckets[b] = e;
647 _n++;
648 return e;
649 } else
650 return 0;
651}
652
653template <class K>
654void
655HashMap<K, void *>::clear()
656{
657 for (size_t i = 0; i < _nbuckets; i++) {
658 for (Elt *e = _buckets[i]; e; ) {
659 Elt *next = e->next;
660 e->key.~K();
661 _arena->free(e);
662 e = next;
663 }
664 _buckets[i] = 0;
665 }
666 _n = 0;
667}
668
669template <class K>
670void
671HashMap<K, void *>::swap(HashMap<K, void *> &o)
672{
673 Elt **t_elts;
674 void *t_v;
675 size_t t_size;
676 HashMap_Arena *t_arena;
677
678 t_elts = _buckets; _buckets = o._buckets; o._buckets = t_elts;
679 t_size = _nbuckets; _nbuckets = o._nbuckets; o._nbuckets = t_size;
680 t_v = _default_value; _default_value = o._default_value; o._default_value = t_v;
681
682 t_size = _n; _n = o._n; o._n = t_size;
683 t_size = _capacity; _capacity = o._capacity; o._capacity = t_size;
684
685 t_arena = _arena; _arena = o._arena; o._arena = t_arena;
686}
687
688
689template <class K>
690_HashMap_const_iterator<K, void *>::_HashMap_const_iterator(const HashMap<K, void *> *hm, bool begin)
691 : _hm(hm)
692{
693 size_t nb = _hm->_nbuckets;
694 typename HashMap<K, void *>::Elt **b = _hm->_buckets;
695 for (_bucket = 0; _bucket < nb && begin; _bucket++)
696 if (b[_bucket]) {
697 _elt = b[_bucket];
698 return;
699 }
700 _elt = 0;
701}
702
703template <class K>
704void
705_HashMap_const_iterator<K, void *>::operator++(int)
706{
707 if (_elt->next)
708 _elt = _elt->next;
709 else {
710 size_t nb = _hm->_nbuckets;
711 typename HashMap<K, void *>::Elt **b = _hm->_buckets;
712 for (_bucket++; _bucket < nb; _bucket++)
713 if (b[_bucket]) {
714 _elt = b[_bucket];
715 return;
716 }
717 _elt = 0;
718 }
719}
720
722CLICK_ENDDECLS
723#endif
Generated on Mon Nov 2 2026 11:59:47 for Click by doxygen 1.9.8