find cache - gnucap.git - Gnu Circuit Analysis Package

index : gnucap.git
Gnu Circuit Analysis Package
summary refs log tree commit diff
diff options
context:
space:
mode:
authorFelix Salfelder <felix@salfelder.org>2025年11月10日 00:00:00 +0000
committerFelix Salfelder <felix@salfelder.org>2025年11月10日 00:00:00 +0000
commit45dc85d3d8f76cfef0da93c962a2ec37be599bc3 (patch)
tree35af6ed580d5929d86b2e775348d3e8ffc7d3bdd
parent7c6b160441b25a87d1214283c6c2833be6a45664 (diff)
downloadgnucap-find_cache.tar.gz
find cachefind_cache
- stuff matches into std::set and std::multiset. - caches "find_" and "find_again" results. - add some reversed interface -- multiset is best used as FILO - add more keys to cache if they exist
Diffstat
-rw-r--r--include/MakeList 2
-rw-r--r--include/e_cardlist.h 23
-rw-r--r--include/l_find_cache.h 123
-rw-r--r--include/patchlev.h 2
-rw-r--r--lib/e_card.cc 20
-rw-r--r--lib/e_cardlist.cc 37
6 files changed, 192 insertions, 15 deletions
diff --git a/include/MakeList b/include/MakeList
index c01bc950..75b13737 100644
--- a/include/MakeList
+++ b/include/MakeList
@@ -35,7 +35,7 @@ e_logicmod.h e_logicnode.h e_logicval.h \
e_elemnt.h e_model.h e_node.h e_paramlist.h e_storag.h e_subckt.h \
globals.h io_.h io_error.h io_dir.h io_trace.h l_compar.h l_denoise.h \
l_dispatcher.h l_indirect.h l_lib.h l_stlextra.h l_timer.h m_base.h \
-l_smallset.h \
+l_smallset.h l_find_cache.h \
m_base_vams.h m_cpoly.h m_random.h \
m_divdiff.h m_expression.h m_interp.h m_matrix.h m_phase.h m_spline.h \
m_matrix_solver.h m_union.h \
diff --git a/include/e_cardlist.h b/include/e_cardlist.h
index fac46893..c084b09b 100644
--- a/include/e_cardlist.h
+++ b/include/e_cardlist.h
@@ -36,17 +36,22 @@ class PARAM_LIST;
class NODE_MAP;
class LANGUAGE;
struct TIME_PAIR;
+template<class T> class FIND_CACHE;
/*--------------------------------------------------------------------------*/
class INTERFACE CARD_LIST {
public: // base types
- typedef std::list<CARD*> list;
+ typedef CARD value_type;
+ typedef std::list<value_type*> list;
typedef list::iterator iterator;
typedef list::const_iterator const_iterator;
typedef list::reverse_iterator reverse_iterator;
+ typedef list::const_reverse_iterator const_reverse_iterator;
+ typedef FIND_CACHE<CARD_LIST> find_cache_t;
private: // data members
const CARD_LIST* _parent;
mutable NODE_MAP* _nm;
mutable PARAM_LIST* _params;
+ mutable find_cache_t *_find_cache{nullptr};
list _cl;
public: // more types
class fat_iterator {
@@ -85,6 +90,11 @@ public: // more types
size_t size()const {return _cl.size();}
const CARD_LIST* parent()const {return _parent;}
+ // find
+ find_cache_t& find_cache()const;
+ void clear_find_cache();
+ void add_to_find_cache(CARD*);
+
// return an iterator
iterator begin() {return _cl.begin();}
iterator end() {return _cl.end();}
@@ -94,20 +104,25 @@ public: // more types
reverse_iterator rbegin() { return _cl.rbegin();}
reverse_iterator rend() { return _cl.rend();}
+ const_reverse_iterator rbegin()const { return _cl.rbegin();}
+ const_reverse_iterator rend()const { return _cl.rend();}
public:
// return a const_iterator
const_iterator begin()const {return _cl.begin();}
const_iterator end()const {return _cl.end();}
const_iterator find_again(const std::string& short_name, const_iterator)const;
+ const_reverse_iterator find_again(const std::string& short_name, const_reverse_iterator)const;
const_iterator find_(const std::string& short_name)const
{return find_again(short_name, begin());}
+ const_reverse_iterator find_reverse_(const std::string& short_name)const
+ {return find_again(short_name, rbegin());}
// add to it
- CARD_LIST& push_front(CARD* c) {_cl.push_front(c); return *this;}
- CARD_LIST& push_back(CARD* c) {_cl.push_back(c); return *this;}
+ CARD_LIST& push_front(CARD* c) {clear_find_cache(); _cl.push_front(c); return *this;}
+ CARD_LIST& push_back(CARD* c) {add_to_find_cache(c); _cl.push_back(c); return *this;}
CARD_LIST& insert(CARD_LIST::iterator i, CARD* c)
- {_cl.insert(i, c); return *this;}
+ {clear_find_cache(); _cl.insert(i, c); return *this;}
// take things out
CARD_LIST& erase(iterator i);
diff --git a/include/l_find_cache.h b/include/l_find_cache.h
new file mode 100644
index 00000000..055402eb
--- /dev/null
+++ b/include/l_find_cache.h
@@ -0,0 +1,123 @@
+/* -*- C++ -*-
+ * Copyright (C) 2025 Felix Salfelder
+ *
+ * This file is part of "Gnucap", the Gnu Circuit Analysis Package
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3, or (at your option)
+ * any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ * 02110-1301, USA.
+ *------------------------------------------------------------------
+ */
+#ifndef L_FIND_CACHE_H
+#define L_FIND_CACHE_H
+/*--------------------------------------------------------------------------*/
+#include <e_card.h>
+#include <set>
+/*--------------------------------------------------------------------------*/
+template<class CONTAINER>
+class FIND_CACHE {
+ struct compare {
+ typedef void is_transparent;
+ bool operator()(std::string const& a, std::string const& b)const {
+ return a<b;
+ }
+ bool operator()(CARD const* a, std::string const& b)const {
+ assert(a);
+ return a->short_label()<b;
+ }
+ bool operator()(std::string const& a, CARD const* b)const {
+ assert(b);
+ return a < b->short_label();
+ }
+ bool operator()(CARD const* a, CARD const* b)const {
+ assert(a);
+ assert(b);
+ return a->short_label() < b->short_label();
+ }
+ };
+private:
+ typedef typename CONTAINER::value_type value_type;
+ typedef std::multiset<value_type const*, compare> cache;
+ cache _cache;
+ std::set<std::string> _miss;
+ CONTAINER const& _c;
+public:
+ typedef typename cache::const_iterator const_iterator;
+ FIND_CACHE(CONTAINER const& c) : _c(c) {}
+ ~FIND_CACHE() {}
+
+public:
+ void add(CARD* c);
+ const_iterator find(std::string const& key);
+ const_iterator find_again(const_iterator current);
+ const_iterator end()const { return _cache.end(); }
+};
+/*--------------------------------------------------------------------------*/
+template<class C>
+void FIND_CACHE<C>::add(CARD* c)
+{
+ std::string key = c->short_label();
+ if(_miss.erase(key)){ untested();
+ assert(_cache.find(key) == _cache.end());
+ }else{
+ const_iterator pos = _cache.lower_bound(key);
+ if(pos == _cache.end()){
+ }else if((*pos)->short_label() == key){
+ pos = _cache.upper_bound(key);
+ _cache.insert(pos, c); // insert before pos
+ }else{
+ }
+ }
+}
+/*--------------------------------------------------------------------------*/
+template<class C>
+typename FIND_CACHE<C>::const_iterator FIND_CACHE<C>::find(std::string const& key)
+{
+ if(_miss.count(key)){
+ // tried before. it's not there.
+ return _cache.end();
+ }else{
+ const_iterator pos = _cache.lower_bound(key);
+ bool is_cached;
+ if(pos == _cache.end()){
+ is_cached = false;
+ }else if((*pos)->short_label() == key){
+ is_cached = true;
+ }else{
+ is_cached = false;
+ }
+ if(is_cached) {
+ return pos;
+ }else{
+ // unknown key. fill cache as needed.
+ CARD_LIST::const_reverse_iterator it = _c.find_reverse_(key);
+ if(it == _c.rend()){
+ _miss.insert(key);
+ return end();
+ }else{
+ while(it != _c.rend()){
+ pos = _cache.insert(pos, *it); // insert before pos
+ it = _c.find_again(key, ++it);
+ }
+
+ return pos;
+ }
+ }
+ }
+}
+/*--------------------------------------------------------------------------*/
+#endif
+/*--------------------------------------------------------------------------*/
+/*--------------------------------------------------------------------------*/
+// vim:ts=8:sw=2:noet:
diff --git a/include/patchlev.h b/include/patchlev.h
index 0c77c270..332e1746 100644
--- a/include/patchlev.h
+++ b/include/patchlev.h
@@ -1 +1 @@
-#define PATCHLEVEL "ctof 2025年10月31日"
+#define PATCHLEVEL "find_cache 2025年11月10日"
diff --git a/lib/e_card.cc b/lib/e_card.cc
index 9178a7d3..8de2c9e1 100644
--- a/lib/e_card.cc
+++ b/lib/e_card.cc
@@ -29,6 +29,7 @@
#include "u_time_pair.h"
#include "e_cardlist.h"
#include "e_node.h"
+#include "l_find_cache.h"
/*--------------------------------------------------------------------------*/
double CARD::tr_probe_num(const std::string&)const {return NOT_VALID;}
XPROBE CARD::ac_probe_ext(const std::string&)const {return XPROBE(NOT_VALID, mtNONE);}
@@ -187,13 +188,13 @@ CARD* CARD::find_in_my_scope(const std::string& name)
assert(name != "");
assert(scope());
- CARD_LIST::iterator i = scope()->find_(name);
- if (i == scope()->end()) {
+ auto i = scope()->find_cache().find(name);
+ if (i == scope()->find_cache().end()) {
throw Exception_Cant_Find(long_label(), name,
((owner()) ? owner()->long_label() : "(root)"));
}else{
}
- return *i;
+ return const_cast<CARD*>(*i);
}
/*--------------------------------------------------------------------------*/
/* find_in_my_scope: find in same scope as myself
@@ -206,8 +207,8 @@ const CARD* CARD::find_in_my_scope(const std::string& name)const
assert(name != "");
assert(scope());
- CARD_LIST::const_iterator i = scope()->find_(name);
- if (i == scope()->end()) {
+ auto i = scope()->find_cache().find(name);
+ if (i == scope()->find_cache().end()) {
throw Exception_Cant_Find(long_label(), name,
((owner()) ? owner()->long_label() : "(root)"));
}else{
@@ -226,8 +227,8 @@ const CARD* CARD::find_in_parent_scope(const std::string& name)const
assert(name != "");
const CARD_LIST* p_scope = (scope()->parent()) ? scope()->parent() : scope();
- CARD_LIST::const_iterator i = p_scope->find_(name);
- if (i == p_scope->end()) {
+ auto i = p_scope->find_cache().find(name);
+ if (i == p_scope->find_cache().end()) {
throw Exception_Cant_Find(long_label(), name);
}else{
}
@@ -247,8 +248,9 @@ const CARD* CARD::find_looking_out(const std::string& name)const
return owner()->find_looking_out(name);
}else if (makes_own_scope()) {
// probably a subckt or "module"
- CARD_LIST::const_iterator i = CARD_LIST::card_list.find_(name);
- if (i != CARD_LIST::card_list.end()) {
+ // BUG? why not "find_again?"
+ auto i = CARD_LIST::card_list.find_cache().find(name);
+ if (i != CARD_LIST::card_list.find_cache().end()) {
return *i;
}else{
throw;
diff --git a/lib/e_cardlist.cc b/lib/e_cardlist.cc
index 5275b4d9..9db5b3ff 100644
--- a/lib/e_cardlist.cc
+++ b/lib/e_cardlist.cc
@@ -29,6 +29,7 @@
#include "e_node.h"
#include "e_model.h"
#include "m_union.h"
+#include "l_find_cache.h"
/*--------------------------------------------------------------------------*/
#define trace_func_comp() trace1(__func__, (**ci).short_label())
/*--------------------------------------------------------------------------*/
@@ -116,8 +117,15 @@ CARD_LIST::const_iterator CARD_LIST::find_again(const std::string& short_name,
return notstd::find_ptr(Begin, end(), short_name);
}
/*--------------------------------------------------------------------------*/
+CARD_LIST::const_reverse_iterator CARD_LIST::find_again(const std::string& short_name,
+ CARD_LIST::const_reverse_iterator Begin)const
+{
+ return notstd::find_ptr(Begin, rend(), short_name);
+}
+/*--------------------------------------------------------------------------*/
CARD_LIST& CARD_LIST::erase(iterator ci)
{
+ clear_find_cache();
assert(ci != end());
if (*ci) {
(*ci)->purge();
@@ -131,6 +139,7 @@ CARD_LIST& CARD_LIST::erase(iterator ci)
CARD_LIST& CARD_LIST::erase(CARD* c)
{
if (c) {
+ clear_find_cache();
c->purge();
delete c;
_cl.remove(c);
@@ -144,6 +153,7 @@ CARD_LIST& CARD_LIST::erase(CARD* c)
*/
CARD_LIST& CARD_LIST::erase_all()
{
+ clear_find_cache();
while (!_cl.empty()) {
if (_cl.back()) {
_cl.back()->purge();
@@ -557,6 +567,7 @@ void CARD_LIST::shallow_copy(const CARD_LIST* p)
{
assert(p);
_parent = p;
+ clear_find_cache();
for (const_iterator ci = p->begin(); ci != p->end(); ++ci) {
trace_func_comp();
if ((**ci).is_device() || dynamic_cast<MODEL_CARD*>(*ci)) {
@@ -653,5 +664,31 @@ void CARD_LIST::set_verilog_math(bool m)
_params->set_verilog(m);
}
/*--------------------------------------------------------------------------*/
+CARD_LIST::find_cache_t& CARD_LIST::find_cache() const
+{
+ if(_find_cache){
+ }else{
+ _find_cache = new find_cache_t(*this);
+ }
+ return *_find_cache;
+}
+/*--------------------------------------------------------------------------*/
+void CARD_LIST::add_to_find_cache(CARD* c)
+{
+ assert(c);
+ if(_find_cache){ itested();
+ // this is really needed in repeat finds during sckt parse.
+ // (most calls are no-ops)
+ _find_cache->add(c);
+ }else{
+ }
+}
+/*--------------------------------------------------------------------------*/
+void CARD_LIST::clear_find_cache()
+{
+ delete _find_cache;
+ _find_cache = nullptr;
+}
+/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
// vim:ts=8:sw=2:noet:
generated by cgit v1.2.3 (git 2.39.1) at 2025年11月24日 02:18:31 +0000

AltStyle によって変換されたページ (->オリジナル) /