[Olena-patches] r4491: Implement basic LRU cache algorithm

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox ChangeLog: 2009-09-16 Fabien Freling &lt;fabien.freling(a)lrde.epita.fr&gt; Implement basic LRU cache algorithm. * fabien/mln/core/image/cache.hh: Implement basic LRU cache algorithm. * fabien/tests/core/image/tiled2d.cc: Minor update. --- mln/core/image/cache.hh | 67 +++++++++++++++++++++++++++++++++++--------- tests/core/image/tiled2d.cc | 2 - 2 files changed, 55 insertions(+), 14 deletions(-) Index: trunk/milena/sandbox/fabien/tests/core/image/tiled2d.cc =================================================================== --- trunk/milena/sandbox/fabien/tests/core/image/tiled2d.cc (revision 4490) +++ trunk/milena/sandbox/fabien/tests/core/image/tiled2d.cc (revision 4491) @@ -43,7 +43,7 @@ mln_piter_(tiled2d<rgb8>) p(tiled_ima.domain()); for_all(p) - if (p.row() % 7 == 0) + if (p.row() % 256 == 0) { //std::cout << tiled_ima(p); tiled_ima(p) = literal::green; Index: trunk/milena/sandbox/fabien/mln/core/image/cache.hh =================================================================== --- trunk/milena/sandbox/fabien/mln/core/image/cache.hh (revision 4490) +++ trunk/milena/sandbox/fabien/mln/core/image/cache.hh (revision 4491) @@ -49,10 +49,13 @@ void set_number_pages(unsigned number_pages); V read(mln_psite(D) p); void write(const mln_psite(D)& p, const V& value); + unsigned insert_new_page(const mln_psite(D)& p); protected: util::array<page<D, V>* > pages_; + util::array<unsigned> order_; + unsigned count_; unsigned number_pages_; // Image info. @@ -70,7 +73,8 @@ inline cache<D, V>::cache(D domain, std::streampos pos, unsigned ncols, std::fstream* f) { - this->number_pages_ = 1; + this->number_pages_ = 5; // Default value. + this->count_ = 1; this->domain_ = domain; this->pos_ = pos; @@ -85,6 +89,7 @@ for (unsigned i = 0; i < this->pages_.nelements(); ++i) delete this->pages_[i]; this->pages_.clear(); + this->order_.clear(); } template <typename D, typename V> @@ -92,6 +97,10 @@ void cache<D, V>::set_number_pages(unsigned number_pages) { + if (number_pages == 0) + { + // FIXME: We must not allow that. + } if (number_pages < this->number_pages_) { // FIXME: Prune pages array. @@ -110,15 +119,9 @@ return this->pages_[i]->read(p); } - // If we have not found a valid page, we just add one. - // FIXME: We should test that we have room for a new page. - page<D, V>* new_page = new page<D, V>(this->domain_, - p, - this->pos_, - this->ncols_, - this->f_); - this->pages_.append(new_page); - return new_page->read(p); + // In case we have not found a valid page, we insert a new one. + unsigned new_page_index = insert_new_page(p); + return this->pages_[new_page_index]->read(p); } template <typename D, typename V> @@ -136,19 +139,57 @@ } } + // In case we have not found a valid page, we insert a new one. if (!found) { - // If we have not found a valid page, we just add one. - // FIXME: We should test that we have room for a new page. + unsigned new_page_index = insert_new_page(p); + this->pages_[new_page_index]->write(p, value); + } + } + + // Basic LRU cache algorithm implementation. + template <typename D, typename V> + inline + unsigned + cache<D, V>::insert_new_page(const mln_psite(D)& p) + { page<D, V>* new_page = new page<D, V>(this->domain_, p, this->pos_, this->ncols_, this->f_); + + unsigned new_index; + + // If there is still room for a new page. + if (this->pages_.nelements() < this->number_pages_) + { this->pages_.append(new_page); - new_page->write(p, value); + this->order_.append(this->count_++); + new_index = this->pages_.nelements() - 1; + } + else // We must find which page to discard. + { + unsigned min = this->order_[0]; + unsigned new_index = 0; + for (unsigned i = 1; i < this->pages_.nelements(); ++i) + { + if (this->order_[i] < min) + { + min = this->order_[i]; + new_index = i; } } + delete this->pages_[new_index]; + this->pages_[new_index] = new_page; + for (unsigned i = 0; i < this->order_.nelements(); ++i) + this->order_[i] -= min; + this->count_ -= min; + this->order_[new_index] = this->count_++; + } + + return new_index; + } # endif // ! MLN_INCLUDE_ONLY