Click
Loading...
Searching...
No Matches
hashmap.hh
1#ifndef CLICK_HASHMAP_HH
2#define CLICK_HASHMAP_HH
3#include <click/hashcode.hh>
4CLICK_DECLS
6class HashMap_Arena;
7class HashMap_ArenaFactory;
8
9// K AND V REQUIREMENTS:
10//
11// K::K(const K &)
12// k1 == k2
13// hashcode_t hashcode(const K &)
14// If hashcode(k1) != hashcode(k2), then k1 != k2.
15// hashcode() can return any unsigned value.
16//
17// V::V() -- only used for default value
18// V::V(const V &)
19// V & V::operator=(const V &)
20
21template <class K, class V = void> class _HashMap_const_iterator;
22template <class K, class V = void> class _HashMap_iterator;
23template <class K, class V = void> class HashMap;
24
25template <class K, class V>
26class HashMap { public:
27
28 typedef K key_type;
29 typedef V mapped_type;
30 struct Pair;
31
32 HashMap();
33 explicit HashMap(const V &, HashMap_ArenaFactory * = 0);
34 HashMap(const HashMap<K, V> &);
35 ~HashMap();
36
37 void set_arena(HashMap_ArenaFactory *);
38
39 size_t size() const { return _n; }
40 bool empty() const { return _n == 0; }
41 size_t nbuckets() const { return _nbuckets; }
42
43 Pair *find_pair(const K &) const;
44 inline V *findp(const K &) const;
45 inline const V &find(const K &, const V &) const;
46 inline const V &find(const K &) const;
47 inline const V &operator[](const K &) const;
48
49 Pair *find_pair_force(const K &, const V &);
50 Pair *find_pair_force(const K &k) { return find_pair_force(k, _default_value); }
51 V *findp_force(const K &k, const V &v) { if (Pair *p = find_pair_force(k, v)) return &p->value; else return 0; }
52 V &find_force(const K &k, const V &v) { return *findp_force(k, v); }
53 V *findp_force(const K &k) { return findp_force(k, _default_value); }
54 V &find_force(const K &k) { return *findp_force(k, _default_value); }
55
56 bool insert(const K &, const V &);
57 bool erase(const K &);
58 bool remove(const K &key) {
59 return erase(key);
60 }
61 void clear();
62
63 void swap(HashMap<K, V> &);
64
65 // iteration
66 typedef _HashMap_const_iterator<K, V> const_iterator;
67 typedef _HashMap_iterator<K, V> iterator;
68 inline const_iterator begin() const;
69 inline iterator begin();
70 inline const_iterator end() const;
71 inline iterator end();
72
73 // dynamic resizing
74 void resize(size_t);
75 bool dynamic_resizing() const { return _capacity < 0x7FFFFFFF; }
76 void set_dynamic_resizing(bool);
77
78 HashMap<K, V> &operator=(const HashMap<K, V> &);
79
80 struct Pair {
81 K key;
82 V value;
83 };
84
85 enum { MAX_NBUCKETS = 4194303,
86 DEFAULT_INITIAL_NBUCKETS = 127,
87 DEFAULT_RESIZE_THRESHOLD = 2 };
88
89 private:
90
91 struct Elt : public Pair {
92 Elt *next;
93#if defined(__GNUC__) && __GNUC__ < 4
94 /* Shut up compiler about Pair lacking default constructor */
95 Elt(const Pair &p) : Pair(p) { }
96#endif
97 };
98
99 Elt **_buckets;
100 size_t _nbuckets;
101 V _default_value;
102
103 size_t _n;
104 size_t _capacity;
105
106 HashMap_Arena *_arena;
107
108 void initialize(HashMap_ArenaFactory *, size_t);
109 void copy_from(const HashMap<K, V> &);
110 void resize0(size_t);
111 size_t bucket(const K &) const;
112
113 friend class _HashMap_iterator<K, V>;
114 friend class _HashMap_const_iterator<K, V>;
115
116};
117
118template <class K, class V>
119class _HashMap_const_iterator { public:
120
121 bool live() const { return _elt; }
122 typedef bool (_HashMap_const_iterator::*unspecified_bool_type)() const;
123 inline operator unspecified_bool_type() const CLICK_DEPRECATED;
124 void operator++(int);
125 void operator++() { (*this)++; }
126
127 typedef typename HashMap<K, V>::Pair Pair;
128 const Pair *pair() const { return _elt; }
129
130 const K &key() const { return _elt->key; }
131 const V &value() const { return _elt->value; }
132
133 private:
134
135 const HashMap<K, V> *_hm;
136 typename HashMap<K, V>::Elt *_elt;
137 size_t _bucket;
138
139 _HashMap_const_iterator(const HashMap<K, V> *m, bool begin);
140 friend class HashMap<K, V>;
141 friend class _HashMap_iterator<K, V>;
142
143};
144
145template <class K, class V>
146class _HashMap_iterator : public _HashMap_const_iterator<K, V> { public:
147
148 typedef _HashMap_const_iterator<K, V> inherited;
149
150 typedef typename HashMap<K, V>::Pair Pair;
151 Pair *pair() const { return const_cast<Pair *>(inherited::pair()); }
152 V &value() const { return const_cast<V &>(inherited::value()); }
153
154 private:
155
156 _HashMap_iterator(HashMap<K, V> *m, bool begin) : inherited(m, begin) { }
157 friend class HashMap<K, V>;
158
159};
160
161template <class K, class V>
162inline typename HashMap<K, V>::const_iterator
163HashMap<K, V>::begin() const
164{
165 return const_iterator(this, true);
166}
167
168template <class K, class V>
169inline typename HashMap<K, V>::iterator
170HashMap<K, V>::begin()
171{
172 return iterator(this, true);
173}
174
175template <class K, class V>
176inline typename HashMap<K, V>::const_iterator
177HashMap<K, V>::end() const
178{
179 return const_iterator(this, false);
180}
181
182template <class K, class V>
183inline typename HashMap<K, V>::iterator
184HashMap<K, V>::end()
185{
186 return iterator(this, false);
187}
188
189template <class K, class V>
190inline V *
191HashMap<K, V>::findp(const K &key) const
192{
193 Pair *p = find_pair(key);
194 return (p ? &p->value : 0);
195}
196
197template <class K, class V>
198inline const V &
199HashMap<K, V>::find(const K &key, const V &default_value) const
200{
201 Pair *p = find_pair(key);
202 const V *v = (p ? &p->value : &default_value);
203 return *v;
204}
205
206template <class K, class V>
207inline const V &
208HashMap<K, V>::find(const K &key) const
209{
210 return find(key, _default_value);
211}
212
213template <class K, class V>
214inline const V &
215HashMap<K, V>::operator[](const K &key) const
216{
217 return find(key);
218}
219
220template <class K, class V>
221inline
222_HashMap_const_iterator<K, V>::operator unspecified_bool_type() const
223{
224 return live() ? &_HashMap_const_iterator::live : 0;
225}
226
227
228template <class K>
229class HashMap<K, void *> { public:
230
231 typedef K key_type;
232 typedef void *mapped_type;
233 struct Pair;
234
235 HashMap();
236 explicit HashMap(void *, HashMap_ArenaFactory * = 0);
237 HashMap(const HashMap<K, void *> &);
238 ~HashMap();
239
240 void set_arena(HashMap_ArenaFactory *);
241
242 size_t size() const { return _n; }
243 bool empty() const { return _n == 0; }
244 size_t nbuckets() const { return _nbuckets; }
245
246 Pair *find_pair(const K &) const;
247 inline void **findp(const K &) const;
248 inline void *find(const K &, void *) const;
249 inline void *find(const K &) const;
250 inline void *operator[](const K &) const;
251
252 Pair *find_pair_force(const K &, void *);
253 Pair *find_pair_force(const K &k) { return find_pair_force(k, _default_value); }
254 void **findp_force(const K &k, void *v) { if (Pair *p = find_pair_force(k, v)) return &p->value; else return 0; }
255 void *&find_force(const K &k, void *v) { return *findp_force(k, v); }
256 void **findp_force(const K &k) { return findp_force(k, _default_value); }
257 void *&find_force(const K &k) { return *findp_force(k, _default_value); }
258
259 bool insert(const K &, void *);
260 bool erase(const K &);
261 bool remove(const K &key) {
262 return erase(key);
263 }
264 void clear();
265
266 void swap(HashMap<K, void *> &);
267
268 // iterators
269 typedef _HashMap_const_iterator<K, void *> const_iterator;
270 typedef _HashMap_iterator<K, void *> iterator;
271 inline const_iterator begin() const;
272 inline iterator begin();
273 inline const_iterator end() const;
274 inline iterator end();
275
276 // dynamic resizing
277 void resize(size_t);
278 bool dynamic_resizing() const { return _capacity < 0x7FFFFFFF; }
279 void set_dynamic_resizing(bool);
280
281 HashMap<K, void *> &operator=(const HashMap<K, void *> &);
282
283 struct Pair {
284 K key;
285 void *value;
286 };
287
288 enum { MAX_NBUCKETS = 32767,
289 DEFAULT_INITIAL_NBUCKETS = 127,
290 DEFAULT_RESIZE_THRESHOLD = 2 };
291
292 private:
293
294 struct Elt : public Pair {
295 Elt *next;
296#if defined(__GNUC__) && __GNUC__ < 4
297 /* Shut up compiler about Pair lacking default constructor */
298 Elt(const Pair &p) : Pair(p) { }
299#endif
300 };
301
302 Elt **_buckets;
303 size_t _nbuckets;
304 void *_default_value;
305
306 size_t _n;
307 size_t _capacity;
308
309 HashMap_Arena *_arena;
310
311 void initialize(HashMap_ArenaFactory *, size_t);
312 void copy_from(const HashMap<K, void *> &);
313 void resize0(size_t);
314 size_t bucket(const K &) const;
315
316 friend class _HashMap_iterator<K, void *>;
317 friend class _HashMap_const_iterator<K, void *>;
318
319};
320
321template <class K>
322class _HashMap_const_iterator<K, void *> { public:
323
324 bool live() const { return _elt; }
325 typedef bool (_HashMap_const_iterator::*unspecified_bool_type)() const;
326 inline operator unspecified_bool_type() const CLICK_DEPRECATED;
327 void operator++(int);
328 void operator++() { (*this)++; }
329
330 typedef typename HashMap<K, void *>::Pair Pair;
331 const Pair *pair() const { return _elt; }
332
333 const K &key() const { return _elt->key; }
334 void *value() const { return _elt->value; }
335
336 private:
337
338 const HashMap<K, void *> *_hm;
339 typename HashMap<K, void *>::Elt *_elt;
340 size_t _bucket;
341
342 _HashMap_const_iterator(const HashMap<K, void *> *, bool begin);
343 template <class, class> friend class _HashMap_const_iterator;
344 template <class, class> friend class _HashMap_iterator;
345 template <class, class> friend class HashMap;
346
347};
348
349template <class K>
350class _HashMap_iterator<K, void *> : public _HashMap_const_iterator<K, void *> { public:
351
352 typedef _HashMap_const_iterator<K, void *> inherited;
353
354 typedef typename HashMap<K, void *>::Pair Pair;
355 Pair *pair() const { return const_cast<Pair *>(inherited::pair()); }
356 void *&value() const { return this->_elt->value; }
357
358 private:
359
360 _HashMap_iterator(HashMap<K, void *> *m, bool begin) : inherited(m, begin) { }
361 template <class, class> friend class HashMap;
362
363};
364
365template <class K>
366inline typename HashMap<K, void *>::const_iterator
367HashMap<K, void *>::begin() const
368{
369 return const_iterator(this, true);
370}
371
372template <class K>
373inline typename HashMap<K, void *>::iterator
374HashMap<K, void *>::begin()
375{
376 return iterator(this, true);
377}
378
379template <class K>
380inline typename HashMap<K, void *>::const_iterator
381HashMap<K, void *>::end() const
382{
383 return const_iterator(this, false);
384}
385
386template <class K>
387inline typename HashMap<K, void *>::iterator
388HashMap<K, void *>::end()
389{
390 return iterator(this, false);
391}
392
393template <class K>
394inline void **
395HashMap<K, void *>::findp(const K &key) const
396{
397 Pair *p = find_pair(key);
398 return (p ? &p->value : 0);
399}
400
401template <class K>
402inline void *
403HashMap<K, void *>::find(const K &key, void *default_value) const
404{
405 Pair *p = find_pair(key);
406 return (p ? p->value : default_value);
407}
408
409template <class K>
410inline void *
411HashMap<K, void *>::find(const K &key) const
412{
413 return find(key, _default_value);
414}
415
416template <class K>
417inline void *
418HashMap<K, void *>::operator[](const K &key) const
419{
420 return find(key);
421}
422
423template <class K>
424inline
425_HashMap_const_iterator<K, void *>::operator unspecified_bool_type() const
426{
427 return live() ? &_HashMap_const_iterator::live : 0;
428}
429
430
431template <class K, class T>
432class HashMap<K, T *> : public HashMap<K, void *> { public:
433
434 typedef K key_type;
435 typedef T *mapped_type;
436 typedef HashMap<K, void *> inherited;
437 struct Pair;
438
439 HashMap() : inherited() { }
440 explicit HashMap(T *def, HashMap_ArenaFactory *factory = 0)
441 : inherited(def, factory) { }
442 HashMap(const HashMap<K, T *> &o) : inherited(o) { }
443 ~HashMap() { }
444
445 void set_arena(HashMap_ArenaFactory *af) { inherited::set_arena(af); }
446
447 // size_t size() const inherited
448 // bool empty() const inherited
449 // size_t nbuckets() const inherited
450
451 Pair *find_pair(const K &k) const { return reinterpret_cast<Pair *>(inherited::find_pair(k)); }
452 T **findp(const K &k) const { return reinterpret_cast<T **>(inherited::findp(k)); }
453 T *find(const K &k, T *v) const { return reinterpret_cast<T *>(inherited::find(k, v)); }
454 T *find(const K &k) const { return reinterpret_cast<T *>(inherited::find(k)); }
455 T *operator[](const K &k) const { return reinterpret_cast<T *>(inherited::operator[](k)); }
456
457 Pair *find_pair_force(const K &k, T *v) { return reinterpret_cast<Pair *>(inherited::find_pair_force(k, v)); }
458 Pair *find_pair_force(const K &k) { return reinterpret_cast<Pair *>(inherited::find_pair_force(k)); }
459 T **findp_force(const K &k, T *v) { return reinterpret_cast<T **>(inherited::findp_force(k, v)); }
460 T *&find_force(const K &k, T *v) { return *reinterpret_cast<T **>(inherited::findp_force(k, v)); }
461 T **findp_force(const K &k) { return reinterpret_cast<T **>(inherited::findp_force(k)); }
462 T *&find_force(const K &k) { return *reinterpret_cast<T **>(inherited::findp_force(k)); }
463
464 bool insert(const K &k, T *v) { return inherited::insert(k, v); }
465 // bool erase(const K &) inherited
466 // bool remove(const K &) inherited
467 // void clear() inherited
468
469 void swap(HashMap<K, T *> &o) { inherited::swap(o); }
470
471 // iteration
472 typedef _HashMap_const_iterator<K, T *> const_iterator;
473 typedef _HashMap_iterator<K, T *> iterator;
474 inline const_iterator begin() const;
475 inline iterator begin();
476 inline const_iterator end() const;
477 inline iterator end();
478
479 // dynamic resizing methods inherited
480
481 HashMap<K, T *> &operator=(const HashMap<K, T *> &o) { return static_cast<HashMap<K, T *> &>(inherited::operator=(o)); }
482
483 struct Pair {
484 K key;
485 T *value;
486 };
487
488};
489
490template <class K, class T>
491class _HashMap_const_iterator<K, T *> { public:
492
493 typedef _HashMap_const_iterator<K, void *> inherited;
494
495 bool live() const { return _i.live(); }
496 typedef typename inherited::unspecified_bool_type unspecified_bool_type;
497 inline operator unspecified_bool_type() const CLICK_DEPRECATED;
498 void operator++(int) { _i.operator++(0); }
499 void operator++() { _i.operator++(); }
500
501 typedef typename HashMap<K, T *>::Pair Pair;
502 const Pair *pair() const { return reinterpret_cast<const Pair *>(_i.pair()); }
503
504 const K &key() const { return _i.key(); }
505 T *value() const { return reinterpret_cast<T *>(_i.value()); }
506
507 private:
508
509 inherited _i;
510
511 _HashMap_const_iterator(const HashMap<K, T *> *t, bool begin) : _i(t, begin) { }
512 friend class _HashMap_iterator<K, T *>;
513 template <class, class> friend class HashMap;
514
515};
516
517template <class K, class T>
518class _HashMap_iterator<K, T *> : public _HashMap_const_iterator<K, T *> { public:
519
520 typedef _HashMap_const_iterator<K, T *> inherited;
521
522 typedef typename HashMap<K, T *>::Pair Pair;
523 Pair *pair() const { return const_cast<Pair *>(inherited::pair()); }
524 T *&value() const { return pair()->value; }
525
526 private:
527
528 _HashMap_iterator(HashMap<K, T *> *t, bool begin) : inherited(t, begin) { }
529 template <class, class> friend class HashMap;
530
531};
532
533template <class K, class T>
534inline typename HashMap<K, T *>::const_iterator
535HashMap<K, T *>::begin() const
536{
537 return const_iterator(this, true);
538}
539
540template <class K, class T>
541inline typename HashMap<K, T *>::iterator
542HashMap<K, T *>::begin()
543{
544 return iterator(this, true);
545}
546
547template <class K, class T>
548inline typename HashMap<K, T *>::const_iterator
549HashMap<K, T *>::end() const
550{
551 return const_iterator(this, false);
552}
553
554template <class K, class T>
555inline typename HashMap<K, T *>::iterator
556HashMap<K, T *>::end()
557{
558 return iterator(this, false);
559}
560
561template <class K, class T>
562inline
563_HashMap_const_iterator<K, T *>::operator unspecified_bool_type() const
564{
565 return inherited::live() ? &inherited::live : 0;
566}
567
568template <class K, class V>
569inline bool
570operator==(const _HashMap_const_iterator<K, V> &a, const _HashMap_const_iterator<K, V> &b)
571{
572 return a.pair() == b.pair();
573}
574
575template <class K, class V>
576inline bool
577operator!=(const _HashMap_const_iterator<K, V> &a, const _HashMap_const_iterator<K, V> &b)
578{
579 return a.pair() != b.pair();
580}
581
583CLICK_ENDDECLS
584#include <click/hashmap.cc>
585#endif
Generated on Mon Nov 2 2026 11:59:47 for Click by doxygen 1.9.8