diff options
-rw-r--r-- | Makefile | 2 | ||||
-rw-r--r-- | kernel/hashmap.h | 238 | ||||
-rw-r--r-- | kernel/log.cc | 6 | ||||
-rw-r--r-- | kernel/log.h | 4 | ||||
-rw-r--r-- | kernel/rtlil.cc | 2 | ||||
-rw-r--r-- | kernel/yosys.h | 1 |
6 files changed, 246 insertions, 7 deletions
@@ -11,7 +11,7 @@ ENABLE_ABC := 1 ENABLE_PLUGINS := 1 ENABLE_READLINE := 1 ENABLE_VERIFIC := 0 -ENABLE_COVER := 0 +ENABLE_COVER := 1 # other configuration flags ENABLE_GPROF := 0 diff --git a/kernel/hashmap.h b/kernel/hashmap.h new file mode 100644 index 000000000..bd4fc4d22 --- /dev/null +++ b/kernel/hashmap.h @@ -0,0 +1,238 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#ifndef YOSYS_HASHMAP_H + +#include <string> +#include <vector> + +inline unsigned int mkhash(unsigned int a, unsigned int b) { + return ((a << 5) + a) ^ b; +} + +template<typename T> struct hash_ops { + bool cmp(const T &a, const T &b) { + return a == b; + } + unsigned int hash(const T &a) { + return a.hash(); + } +}; + +template<> struct hash_ops<int> { + bool cmp(int a, int b) { + return a == b; + } + unsigned int hash(int a) { + return a; + } +}; + +template<> struct hash_ops<std::string> { + bool cmp(const std::string &a, const std::string &b) { + return a == b; + } + unsigned int hash(const std::string &a) { + unsigned int v = 0; + for (auto c : a) + v = mkhash(v, c); + return v; + } +}; + +template<typename K, typename T, typename OPS = hash_ops<K>> +class new_dict +{ + struct entry_t + { + int link; + std::pair<K, T> udata; + entry_t() : link(-1) { } + + bool is_free() const { return link < 0; } + int get_next() const { return (link > 0 ? link : -link) - 2; } + bool get_last() const { return get_next() == -1; } + void set_next_used(int next) { link = next + 2; } + void set_next_free(int next) { link = -(next + 2); } + }; + + std::vector<int> hashtable; + std::vector<entry_t> entries; + int free_list, counter; + OPS ops; + + void init() + { + counter = 0; + entries.resize(61); + rehash(); + } + + int mkhash(const K &key) + { + return ops.hash(key) % int(hashtable.size()); + } + +public: + void rehash() + { + free_list = -1; + + hashtable.resize(entries.size()); + for (auto &h : hashtable) + h = -1; + + for (int i = 0; i < int(entries.size()); i++) + if (entries[i].is_free()) { + entries[i].set_next_free(free_list); + free_list = i; + } else { + int hash = mkhash(entries[i].udata.first); + entries[i].set_next_used(hashtable[hash]); + hashtable[hash] = i; + } + } + + void do_erase(const K &key, int hash) + { + int last_index = -1; + int index = hashtable[hash]; + while (1) { + if (index < 0) + return; + if (ops.cmp(entries[index].udata.first, key)) { + if (last_index < 0) + hashtable[hash] = entries[index].get_next(); + else + entries[last_index].set_next_used(entries[index].get_next()); + entries[index].udata = std::pair<K, T>(); + entries[index].set_next_free(free_list); + free_list = index; + counter--; + return; + } + last_index = index; + index = entries[index].get_next(); + } + } + + int lookup_index(const K &key, int hash) + { + int index = hashtable[hash]; + while (1) { + if (index < 0) + return -1; + if (ops.cmp(entries[index].udata.first, key)) + return index; + index = entries[index].get_next(); + } + } + + int insert_at(const std::pair<K, T> &value, int hash) + { + if (free_list < 0) + { + int i = entries.size(); + entries.resize(2*entries.size()); + entries[i].udata = value; + entries[i].set_next_used(0); + counter++; + rehash(); + return i; + } + + int i = free_list; + free_list = entries[i].get_next(); + entries[i].udata = value; + entries[i].set_next_used(hashtable[hash]); + hashtable[hash] = i; + counter++; + return i; + } + +public: + class iterator + { + new_dict<K, T, OPS> *ptr; + int index; + public: + iterator(new_dict<K, T, OPS> *ptr, int index) : ptr(ptr), index(index) { } + iterator operator++() { do index++; while (index != int(ptr->entries.size()) && ptr->entries[index].is_free()); return *this; } + iterator operator--() { do index--; while (index != 0 && ptr->entries[index].is_free()); return *this; } + bool operator==(const iterator &other) const { return index == other.index; } + bool operator!=(const iterator &other) const { return index != other.index; } + std::pair<K, T> &operator*() { return ptr->entries[index].udata; } + }; + + new_dict() + { + init(); + } + + template<class InputIterator> + new_dict(InputIterator first, InputIterator last) + { + init(); + insert(first, last); + } + + template<class InputIterator> + void insert(InputIterator first, InputIterator last) + { + for (; first != last; ++first) + insert(*first); + } + + iterator insert(const std::pair<K, T> &value) + { + int hash = mkhash(value.first); + int i = lookup_index(value.first, hash); + if (i >= 0) + return iterator(this, i); + i = insert_at(value, hash); + return iterator(this, i); + } + + void erase(const K &key) + { + int hash = mkhash(key); + do_erase(key, hash); + } + + int count(const K &key) + { + int hash = mkhash(key); + int i = lookup_index(key, hash); + return i < 0 ? 0 : 1; + } + + T& operator[](const K &key) + { + int hash = mkhash(key); + int i = lookup_index(key, hash); + if (i < 0) + i = insert_at(std::pair<K, T>(key, T()), hash); + return entries[i].udata.second; + } + + iterator begin() { int index = 0; while (index != int(entries.size()) && entries[index].is_free()) index++; return iterator(this, index); } + iterator end() { return iterator(this, entries.size()); } +}; + +#endif diff --git a/kernel/log.cc b/kernel/log.cc index 0773429a6..677884c97 100644 --- a/kernel/log.cc +++ b/kernel/log.cc @@ -301,7 +301,7 @@ void log_cell(RTLIL::Cell *cell, std::string indent) // --------------------------------------------------- #ifdef YOSYS_ENABLE_COVER -std::map<std::string, std::pair<std::string, int>> extra_coverage_data; +new_dict<std::string, std::pair<std::string, int>> extra_coverage_data; void cover_extra(std::string parent, std::string id, bool increment) { if (extra_coverage_data.count(id) == 0) { @@ -314,9 +314,9 @@ void cover_extra(std::string parent, std::string id, bool increment) { extra_coverage_data[id].second++; } -std::map<std::string, std::pair<std::string, int>> get_coverage_data() +new_dict<std::string, std::pair<std::string, int>> get_coverage_data() { - std::map<std::string, std::pair<std::string, int>> coverage_data; + new_dict<std::string, std::pair<std::string, int>> coverage_data; for (auto &it : pass_register) { std::string key = stringf("passes.%s", it.first.c_str()); diff --git a/kernel/log.h b/kernel/log.h index 278e35b41..eec071991 100644 --- a/kernel/log.h +++ b/kernel/log.h @@ -106,10 +106,10 @@ struct CoverData { extern "C" struct CoverData __start_yosys_cover_list[]; extern "C" struct CoverData __stop_yosys_cover_list[]; -extern std::map<std::string, std::pair<std::string, int>> extra_coverage_data; +extern new_dict<std::string, std::pair<std::string, int>> extra_coverage_data; void cover_extra(std::string parent, std::string id, bool increment = true); -std::map<std::string, std::pair<std::string, int>> get_coverage_data(); +new_dict<std::string, std::pair<std::string, int>> get_coverage_data(); #define cover_list(_id, ...) do { cover(_id); \ std::string r = cover_list_worker(_id, __VA_ARGS__); \ diff --git a/kernel/rtlil.cc b/kernel/rtlil.cc index 2d3d83f42..28fdeecdd 100644 --- a/kernel/rtlil.cc +++ b/kernel/rtlil.cc @@ -2171,7 +2171,7 @@ RTLIL::SigSpec::SigSpec(std::vector<RTLIL::SigBit> bits) RTLIL::SigSpec::SigSpec(nodict<RTLIL::SigBit> bits) { - cover("kernel.rtlil.sigspec.init.stdset_bits"); + cover("kernel.rtlil.sigspec.init.nodict_bits"); width_ = 0; hash_ = 0; diff --git a/kernel/yosys.h b/kernel/yosys.h index e2daabfae..b14852eaf 100644 --- a/kernel/yosys.h +++ b/kernel/yosys.h @@ -126,6 +126,7 @@ YOSYS_NAMESPACE_BEGIN #define dict std::unordered_map #define nodict std::unordered_set +#include "kernel/hashmap.h" using std::vector; namespace RTLIL { |