| -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 |
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日" |