2 * yosys -- Yosys Open SYnthesis Suite
4 * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at>
6 * Permission to use, copy, modify, and/or distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
20 #ifndef YOSYS_HASHMAP_H
26 #define YOSYS_HASHTABLE_SIZE_FACTOR 3
28 inline unsigned int mkhash(unsigned int a
, unsigned int b
) {
29 return ((a
<< 5) + a
) ^ b
;
32 template<typename T
> struct hash_ops
{
33 bool cmp(const T
&a
, const T
&b
) const {
36 unsigned int hash(const T
&a
) const {
41 template<> struct hash_ops
<int> {
42 bool cmp(int a
, int b
) const {
45 unsigned int hash(int a
) const {
50 template<> struct hash_ops
<std::string
> {
51 bool cmp(const std::string
&a
, const std::string
&b
) const {
54 unsigned int hash(const std::string
&a
) const {
62 struct hash_cstr_ops
{
63 bool cmp(const char *a
, const char *b
) const {
64 for (int i
= 0; a
[i
] || b
[i
]; i
++)
69 unsigned int hash(const char *a
) const {
70 unsigned int hash
= 5381;
72 hash
= mkhash(hash
, *(a
++));
78 bool cmp(const void *a
, const void *b
) const {
81 unsigned int hash(const void *a
) const {
82 return (unsigned long)a
;
87 bool cmp(const void *a
, const void *b
) const {
91 unsigned int hash(const T
*a
) const {
92 return a
->name
.hash();
96 inline int hashtable_size(int old_size
)
98 // prime numbers, approx. in powers of two
99 if (old_size
< 53) return 53;
100 if (old_size
< 113) return 113;
101 if (old_size
< 251) return 251;
102 if (old_size
< 503) return 503;
103 if (old_size
< 1129) return 1129;
104 if (old_size
< 2503) return 2503;
105 if (old_size
< 5023) return 5023;
106 if (old_size
< 11299) return 11299;
107 if (old_size
< 25097) return 25097;
108 if (old_size
< 50291) return 50291;
109 if (old_size
< 112997) return 112997;
110 if (old_size
< 251003) return 251003;
111 if (old_size
< 503003) return 503003;
112 if (old_size
< 1129991) return 1129991;
113 if (old_size
< 2509993) return 2509993;
114 if (old_size
< 5029991) return 5029991;
115 if (old_size
< 11299997) return 11299997;
116 if (old_size
< 25099999) return 25099999;
117 if (old_size
< 50299999) return 50299999;
118 if (old_size
< 113000009) return 113000009;
119 if (old_size
< 250999999) return 250999999;
120 if (old_size
< 503000009) return 503000009;
121 if (old_size
< 1129999999) return 1129999999;
122 throw std::length_error("hash table exceeded maximum size");
125 template<typename K
, typename T
, typename OPS
= hash_ops
<K
>>
131 std::pair
<K
, T
> udata
;
133 entry_t() : link(-1) { }
134 entry_t(const std::pair
<K
, T
> &udata
) : link(1), udata(udata
) { }
136 bool is_free() const { return link
< 0; }
137 int get_next() const { return (link
> 0 ? link
: -link
) - 2; }
138 bool get_last() const { return get_next() == -1; }
139 void set_next_used(int next
) { link
= next
+ 2; }
140 void set_next_free(int next
) { link
= -(next
+ 2); }
143 std::vector
<int> hashtable
;
144 std::vector
<entry_t
> entries
;
145 int free_list
, counter
;
154 void init_from(const dict
<K
, T
, OPS
> &other
)
159 counter
= other
.size();
160 int new_size
= hashtable_size(YOSYS_HASHTABLE_SIZE_FACTOR
* counter
);
161 hashtable
.resize(new_size
);
162 new_size
= new_size
/ YOSYS_HASHTABLE_SIZE_FACTOR
+ 1;
163 entries
.reserve(new_size
);
165 for (auto &it
: other
)
166 entries
.push_back(entry_t(it
));
167 entries
.resize(new_size
);
171 int mkhash(const K
&key
) const
173 unsigned int hash
= 0;
174 if (!hashtable
.empty())
175 hash
= ops
.hash(key
) % (unsigned int)(hashtable
.size());
183 for (auto &h
: hashtable
)
186 for (int i
= 0; i
< int(entries
.size()); i
++)
187 if (entries
[i
].is_free()) {
188 entries
[i
].set_next_free(free_list
);
191 int hash
= mkhash(entries
[i
].udata
.first
);
192 entries
[i
].set_next_used(hashtable
[hash
]);
197 void do_erase(const K
&key
, int hash
)
200 int index
= hashtable
.empty() ? -1 : hashtable
[hash
];
204 if (ops
.cmp(entries
[index
].udata
.first
, key
)) {
206 hashtable
[hash
] = entries
[index
].get_next();
208 entries
[last_index
].set_next_used(entries
[index
].get_next());
209 entries
[index
].udata
= std::pair
<K
, T
>();
210 entries
[index
].set_next_free(free_list
);
217 index
= entries
[index
].get_next();
221 int lookup_index(const K
&key
, int hash
) const
223 int index
= hashtable
.empty() ? -1 : hashtable
[hash
];
227 if (ops
.cmp(entries
[index
].udata
.first
, key
))
229 index
= entries
[index
].get_next();
233 int insert_at(const std::pair
<K
, T
> &value
, int hash
)
237 int i
= entries
.size();
238 int new_size
= hashtable_size(YOSYS_HASHTABLE_SIZE_FACTOR
* entries
.size());
239 hashtable
.resize(new_size
);
240 entries
.resize(new_size
/ YOSYS_HASHTABLE_SIZE_FACTOR
+ 1);
241 entries
[i
].udata
= value
;
242 entries
[i
].set_next_used(0);
249 free_list
= entries
[i
].get_next();
250 entries
[i
].udata
= value
;
251 entries
[i
].set_next_used(hashtable
[hash
]);
260 dict
<K
, T
, OPS
> *ptr
;
264 iterator(dict
<K
, T
, OPS
> *ptr
, int index
) : ptr(ptr
), index(index
) { }
265 iterator
operator++() { do index
++; while (index
!= int(ptr
->entries
.size()) && ptr
->entries
[index
].is_free()); return *this; }
266 iterator
operator--() { do index
--; while (index
!= 0 && ptr
->entries
[index
].is_free()); return *this; }
267 bool operator==(const iterator
&other
) const { return index
== other
.index
; }
268 bool operator!=(const iterator
&other
) const { return index
!= other
.index
; }
269 std::pair
<K
, T
> &operator*() { return ptr
->entries
[index
].udata
; }
270 std::pair
<K
, T
> *operator->() { return &ptr
->entries
[index
].udata
; }
271 const std::pair
<K
, T
> &operator*() const { return ptr
->entries
[index
].udata
; }
272 const std::pair
<K
, T
> *operator->() const { return &ptr
->entries
[index
].udata
; }
277 const dict
<K
, T
, OPS
> *ptr
;
281 const_iterator(const dict
<K
, T
, OPS
> *ptr
, int index
) : ptr(ptr
), index(index
) { }
282 const_iterator
operator++() { do index
++; while (index
!= int(ptr
->entries
.size()) && ptr
->entries
[index
].is_free()); return *this; }
283 const_iterator
operator--() { do index
--; while (index
!= 0 && ptr
->entries
[index
].is_free()); return *this; }
284 bool operator==(const const_iterator
&other
) const { return index
== other
.index
; }
285 bool operator!=(const const_iterator
&other
) const { return index
!= other
.index
; }
286 const std::pair
<K
, T
> &operator*() const { return ptr
->entries
[index
].udata
; }
287 const std::pair
<K
, T
> *operator->() const { return &ptr
->entries
[index
].udata
; }
295 dict(const dict
<K
, T
, OPS
> &other
)
300 dict(dict
<K
, T
, OPS
> &&other
)
307 dict
<K
, T
, OPS
> &operator=(const dict
<K
, T
, OPS
> &other
) {
313 dict
<K
, T
, OPS
> &operator=(dict
<K
, T
, OPS
> &&other
) {
319 dict(const std::initializer_list
<std::pair
<K
, T
>> &list
)
322 for (auto &it
: list
)
326 template<class InputIterator
>
327 dict(InputIterator first
, InputIterator last
)
333 template<class InputIterator
>
334 void insert(InputIterator first
, InputIterator last
)
336 for (; first
!= last
; ++first
)
340 iterator
insert(const std::pair
<K
, T
> &value
)
342 int hash
= mkhash(value
.first
);
343 int i
= lookup_index(value
.first
, hash
);
345 return iterator(this, i
);
346 i
= insert_at(value
, hash
);
347 return iterator(this, i
);
350 void erase(const K
&key
)
352 int hash
= mkhash(key
);
356 void erase(const iterator it
)
358 int hash
= mkhash(it
->first
);
359 do_erase(it
->first
, hash
);
362 int count(const K
&key
) const
364 int hash
= mkhash(key
);
365 int i
= lookup_index(key
, hash
);
366 return i
< 0 ? 0 : 1;
369 iterator
find(const K
&key
)
371 int hash
= mkhash(key
);
372 int i
= lookup_index(key
, hash
);
375 return iterator(this, i
);
378 const_iterator
find(const K
&key
) const
380 int hash
= mkhash(key
);
381 int i
= lookup_index(key
, hash
);
384 return const_iterator(this, i
);
389 int hash
= mkhash(key
);
390 int i
= lookup_index(key
, hash
);
392 throw std::out_of_range("dict::at()");
393 return entries
[i
].udata
.second
;
396 const T
& at(const K
&key
) const
398 int hash
= mkhash(key
);
399 int i
= lookup_index(key
, hash
);
401 throw std::out_of_range("dict::at()");
402 return entries
[i
].udata
.second
;
405 T
& operator[](const K
&key
)
407 int hash
= mkhash(key
);
408 int i
= lookup_index(key
, hash
);
410 i
= insert_at(std::pair
<K
, T
>(key
, T()), hash
);
411 return entries
[i
].udata
.second
;
414 void swap(dict
<K
, T
, OPS
> &other
)
416 hashtable
.swap(other
.hashtable
);
417 entries
.swap(other
.entries
);
418 std::swap(free_list
, other
.free_list
);
419 std::swap(counter
, other
.counter
);
422 bool operator==(const dict
<K
, T
, OPS
> &other
) const {
423 if (counter
!= other
.counter
)
427 if (entries
.size() < other
.entries
.size())
428 for (auto &it
: *this) {
429 auto oit
= other
.find(it
.first
);
430 if (oit
== other
.end() || oit
->second
!= it
.second
)
434 for (auto &oit
: other
) {
435 auto it
= find(oit
.first
);
436 if (it
== end() || it
->second
!= oit
.second
)
442 bool operator!=(const dict
<K
, T
, OPS
> &other
) const {
443 return !(*this == other
);
446 size_t size() const { return counter
; }
447 bool empty() const { return counter
== 0; }
448 void clear() { hashtable
.clear(); entries
.clear(); init(); }
450 iterator
begin() { int index
= 0; while (index
!= int(entries
.size()) && entries
[index
].is_free()) index
++; return iterator(this, index
); }
451 iterator
end() { return iterator(this, entries
.size()); }
453 const_iterator
begin() const { int index
= 0; while (index
!= int(entries
.size()) && entries
[index
].is_free()) index
++; return const_iterator(this, index
); }
454 const_iterator
end() const { return const_iterator(this, entries
.size()); }
457 template<typename K
, typename OPS
= hash_ops
<K
>>
465 entry_t() : link(-1) { }
466 entry_t(const K
&key
) : link(1), key(key
) { }
468 bool is_free() const { return link
< 0; }
469 int get_next() const { return (link
> 0 ? link
: -link
) - 2; }
470 bool get_last() const { return get_next() == -1; }
471 void set_next_used(int next
) { link
= next
+ 2; }
472 void set_next_free(int next
) { link
= -(next
+ 2); }
475 std::vector
<int> hashtable
;
476 std::vector
<entry_t
> entries
;
477 int free_list
, counter
;
486 void init_from(const pool
<K
, OPS
> &other
)
491 counter
= other
.size();
492 int new_size
= hashtable_size(YOSYS_HASHTABLE_SIZE_FACTOR
* counter
);
493 hashtable
.resize(new_size
);
494 new_size
= new_size
/ YOSYS_HASHTABLE_SIZE_FACTOR
+ 1;
495 entries
.reserve(new_size
);
497 for (auto &it
: other
)
498 entries
.push_back(entry_t(it
));
499 entries
.resize(new_size
);
503 int mkhash(const K
&key
) const
505 unsigned int hash
= 0;
506 if (!hashtable
.empty())
507 hash
= ops
.hash(key
) % (unsigned int)(hashtable
.size());
515 for (auto &h
: hashtable
)
518 for (int i
= 0; i
< int(entries
.size()); i
++)
519 if (entries
[i
].is_free()) {
520 entries
[i
].set_next_free(free_list
);
523 int hash
= mkhash(entries
[i
].key
);
524 entries
[i
].set_next_used(hashtable
[hash
]);
529 void do_erase(const K
&key
, int hash
)
532 int index
= hashtable
.empty() ? -1 : hashtable
[hash
];
536 if (ops
.cmp(entries
[index
].key
, key
)) {
538 hashtable
[hash
] = entries
[index
].get_next();
540 entries
[last_index
].set_next_used(entries
[index
].get_next());
541 entries
[index
].key
= K();
542 entries
[index
].set_next_free(free_list
);
549 index
= entries
[index
].get_next();
553 int lookup_index(const K
&key
, int hash
) const
555 int index
= hashtable
.empty() ? -1 : hashtable
[hash
];
559 if (ops
.cmp(entries
[index
].key
, key
))
561 index
= entries
[index
].get_next();
565 int insert_at(const K
&key
, int hash
)
569 int i
= entries
.size();
570 int new_size
= hashtable_size(YOSYS_HASHTABLE_SIZE_FACTOR
* entries
.size());
571 hashtable
.resize(new_size
);
572 entries
.resize(new_size
/ YOSYS_HASHTABLE_SIZE_FACTOR
+ 1);
573 entries
[i
].key
= key
;
574 entries
[i
].set_next_used(0);
581 free_list
= entries
[i
].get_next();
582 entries
[i
].key
= key
;
583 entries
[i
].set_next_used(hashtable
[hash
]);
596 iterator(pool
<K
, OPS
> *ptr
, int index
) : ptr(ptr
), index(index
) { }
597 iterator
operator++() { do index
++; while (index
!= int(ptr
->entries
.size()) && ptr
->entries
[index
].is_free()); return *this; }
598 iterator
operator--() { do index
--; while (index
!= 0 && ptr
->entries
[index
].is_free()); return *this; }
599 bool operator==(const iterator
&other
) const { return index
== other
.index
; }
600 bool operator!=(const iterator
&other
) const { return index
!= other
.index
; }
601 K
&operator*() { return ptr
->entries
[index
].key
; }
602 K
*operator->() { return &ptr
->entries
[index
].key
; }
603 const K
&operator*() const { return ptr
->entries
[index
].key
; }
604 const K
*operator->() const { return &ptr
->entries
[index
].key
; }
609 const pool
<K
, OPS
> *ptr
;
613 const_iterator(const pool
<K
, OPS
> *ptr
, int index
) : ptr(ptr
), index(index
) { }
614 const_iterator
operator++() { do index
++; while (index
!= int(ptr
->entries
.size()) && ptr
->entries
[index
].is_free()); return *this; }
615 const_iterator
operator--() { do index
--; while (index
!= 0 && ptr
->entries
[index
].is_free()); return *this; }
616 bool operator==(const const_iterator
&other
) const { return index
== other
.index
; }
617 bool operator!=(const const_iterator
&other
) const { return index
!= other
.index
; }
618 const K
&operator*() const { return ptr
->entries
[index
].key
; }
619 const K
*operator->() const { return &ptr
->entries
[index
].key
; }
627 pool(const pool
<K
, OPS
> &other
)
632 pool(pool
<K
, OPS
> &&other
)
639 pool
<K
, OPS
> &operator=(const pool
<K
, OPS
> &other
) {
645 pool
<K
, OPS
> &operator=(pool
<K
, OPS
> &&other
) {
651 pool(const std::initializer_list
<K
> &list
)
654 for (auto &it
: list
)
658 template<class InputIterator
>
659 pool(InputIterator first
, InputIterator last
)
665 template<class InputIterator
>
666 void insert(InputIterator first
, InputIterator last
)
668 for (; first
!= last
; ++first
)
672 iterator
insert(const K
&key
)
674 int hash
= mkhash(key
);
675 int i
= lookup_index(key
, hash
);
677 return iterator(this, i
);
678 i
= insert_at(key
, hash
);
679 return iterator(this, i
);
682 void erase(const K
&key
)
684 int hash
= mkhash(key
);
688 void erase(const iterator it
)
690 int hash
= mkhash(it
->first
);
691 do_erase(it
->first
, hash
);
694 int count(const K
&key
) const
696 int hash
= mkhash(key
);
697 int i
= lookup_index(key
, hash
);
698 return i
< 0 ? 0 : 1;
701 iterator
find(const K
&key
)
703 int hash
= mkhash(key
);
704 int i
= lookup_index(key
, hash
);
707 return iterator(this, i
);
710 const_iterator
find(const K
&key
) const
712 int hash
= mkhash(key
);
713 int i
= lookup_index(key
, hash
);
716 return const_iterator(this, i
);
719 bool operator[](const K
&key
) const
721 int hash
= mkhash(key
);
722 int i
= lookup_index(key
, hash
);
726 void swap(pool
<K
, OPS
> &other
)
728 hashtable
.swap(other
.hashtable
);
729 entries
.swap(other
.entries
);
730 std::swap(free_list
, other
.free_list
);
731 std::swap(counter
, other
.counter
);
734 bool operator==(const pool
<K
, OPS
> &other
) const {
735 if (counter
!= other
.counter
)
739 if (entries
.size() < other
.entries
.size())
740 for (auto &it
: *this) {
741 auto oit
= other
.find(it
.first
);
742 if (oit
== other
.end() || oit
->second
!= it
.second
)
746 for (auto &oit
: other
) {
747 auto it
= find(oit
.first
);
748 if (it
== end() || it
->second
!= oit
.second
)
754 bool operator!=(const pool
<K
, OPS
> &other
) const {
755 return !(*this == other
);
758 size_t size() const { return counter
; }
759 bool empty() const { return counter
== 0; }
760 void clear() { hashtable
.clear(); entries
.clear(); init(); }
762 iterator
begin() { int index
= 0; while (index
!= int(entries
.size()) && entries
[index
].is_free()) index
++; return iterator(this, index
); }
763 iterator
end() { return iterator(this, entries
.size()); }
765 const_iterator
begin() const { int index
= 0; while (index
!= int(entries
.size()) && entries
[index
].is_free()) index
++; return const_iterator(this, index
); }
766 const_iterator
end() const { return const_iterator(this, entries
.size()); }