PLearn 0.1
BoundedMemoryCache.h
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // PLearn (A C++ Machine Learning Library)
00004 // Copyright (C) 1998 Pascal Vincent
00005 // Copyright (C) 1999-2002 Pascal Vincent, Yoshua Bengio and University of Montreal
00006 //
00007 
00008 // Redistribution and use in source and binary forms, with or without
00009 // modification, are permitted provided that the following conditions are met:
00010 // 
00011 //  1. Redistributions of source code must retain the above copyright
00012 //     notice, this list of conditions and the following disclaimer.
00013 // 
00014 //  2. Redistributions in binary form must reproduce the above copyright
00015 //     notice, this list of conditions and the following disclaimer in the
00016 //     documentation and/or other materials provided with the distribution.
00017 // 
00018 //  3. The name of the authors may not be used to endorse or promote
00019 //     products derived from this software without specific prior written
00020 //     permission.
00021 // 
00022 // THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
00023 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00024 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
00025 // NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00026 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
00027 // TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00028 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00029 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00030 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00031 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00032 // 
00033 // This file is part of the PLearn library. For more information on the PLearn
00034 // library, go to the PLearn Web site at www.plearn.org
00035 
00036 
00037  
00038 
00039 /* *******************************************************      
00040  * $Id$
00041  * AUTHORS: Yoshua Bengio
00042  * This file is part of the PLearn library.
00043  ******************************************************* */
00044 
00045 
00048 #ifndef BoundedMemoryTVec_INC
00049 #define BoundedMemoryTVec_INC
00050 
00051 #include <map>
00052 #include <plearn/base/DoublyLinkedList.h>
00053 #include <plearn/base/general.h>
00054 
00055 namespace PLearn {
00056 using namespace std;
00057 
00071 template <class KeyType, class ValueType>
00072 class BoundedMemoryCache
00073 {
00074 protected:
00075     int      n_elements; 
00076     int      max_memory; 
00077     int      current_memory; 
00078 public:
00079     DoublyLinkedList<KeyType>* doubly_linked_list;
00080     mutable int      n_successful_hits; 
00081     mutable int      n_failures; 
00083     map<KeyType, pair<ValueType,DoublyLinkedListElement<KeyType>*> > elements; 
00085     inline BoundedMemoryCache(int max_memory_=0) 
00086         : n_elements(0), max_memory(max_memory_), current_memory(0), doubly_linked_list(new DoublyLinkedList<KeyType>),
00087           n_successful_hits(0), n_failures(0)
00088     {}
00089 
00090     inline void clear() { 
00091 /*
00092         int mm = max_memory;
00093         max_memory = 0;
00094         removeExcess(); // this is mostly useful when removeExcess is redefined, e.g. in sub-class Cache
00095         max_memory = mm;
00096         elements.clear();
00097 */
00098         removeAll(); // this is mostly useful when removeAll is redefined, e.g. in sub-class Cache
00099         if (elements.size() != 0)
00100             PLERROR("Weird");
00101     }
00102 
00105     const ValueType* operator()(const KeyType& key) const { 
00106         typename map<KeyType,pair<ValueType,DoublyLinkedListElement<KeyType>*> >::const_iterator it = elements.find(key);
00107         if (it==elements.end()) 
00108         {
00109             n_failures++;
00110             return 0;
00111         }
00112         n_successful_hits++;
00113         doubly_linked_list->moveToFront(it->second.second); 
00114 #ifdef BOUNDCHECK
00115         if (!doubly_linked_list->last || doubly_linked_list->last->next)
00116             PLERROR("something wrong with last element of doubly linked list!");
00117         if (dbg)
00118             verifyInvariants();
00119 #endif
00120         return &(it->second.first);
00121     }
00122     ValueType* operator()(const KeyType& key) { 
00123         typename map<KeyType,pair<ValueType,DoublyLinkedListElement<KeyType>*> >::iterator it = elements.find(key);
00124         if (it==elements.end()) 
00125         {
00126             n_failures++;
00127             return 0;
00128         }
00129         n_successful_hits++;
00130         doubly_linked_list->moveToFront(it->second.second); 
00131 #ifdef BOUNDCHECK
00132         if (!doubly_linked_list->last || doubly_linked_list->last->next)
00133             PLERROR("something wrong with last element of doubly linked list!");
00134         if (dbg)
00135             verifyInvariants();
00136 #endif
00137         return &(it->second.first);
00138     }
00139 
00140     typedef int* pointer;
00141 
00144     void set(const KeyType& key, const ValueType& value) {
00145         typename map<KeyType,pair<ValueType,DoublyLinkedListElement<KeyType>*> >::iterator it = elements.find(key);
00146         if (it==elements.end()) { // first time set
00147             DoublyLinkedListElement<KeyType>* p=doubly_linked_list->pushOnTop(key);
00148 #ifdef BOUNDCHECK
00149             if (!doubly_linked_list->last || doubly_linked_list->last->next)
00150                 PLERROR("something wrong with last element of doubly linked list!");
00151 #endif
00152             pair<ValueType,DoublyLinkedListElement<KeyType>*> el(value,p);
00153             elements[key] = el;
00154             current_memory += sizeInBytes(el);
00155             n_elements++;
00156 #ifdef BOUNDCHECK
00157             if (dbg)
00158                 verifyInvariants();
00159 #endif
00160         }
00161         else { // already there, move it to front of list and update the value
00162             ValueType& v = elements[key].first;
00163             current_memory += sizeInBytes(value) - sizeInBytes(v);
00164             doubly_linked_list->moveToFront(it->second.second);
00165 #ifdef BOUNDCHECK
00166             if (!doubly_linked_list->last || doubly_linked_list->last->next)
00167                 PLERROR("something wrong with last element of doubly linked list!");
00168 #endif
00169             v = value;
00170 #ifdef BOUNDCHECK
00171             if (dbg)
00172                 verifyInvariants();
00173 #endif
00174         }
00175         removeExcess();
00176     }
00178     inline  bool isCached(const KeyType& key) const { return elements.find(key)!=elements.end(); }
00179     inline  int nElements() const { return n_elements; }
00180     inline  int currentMemory() const { return current_memory; }
00181     inline  int maxMemory() const { return max_memory; }
00182     inline  void setMaxMemory(int new_max_memory) {
00183         max_memory=new_max_memory;
00184         removeExcess();
00185     }
00186 
00187     inline  float successRate() { return float(n_successful_hits)/(n_successful_hits + n_failures); }
00188 
00189     inline virtual ~BoundedMemoryCache() { clear(); }
00190 
00191     // check that all pointers to doubly linked list elements are still valid
00192     void verifyInvariants() {
00193         if (!doubly_linked_list->last || doubly_linked_list->last->next)
00194             PLERROR("something wrong with last element of doubly linked list!");
00195         if (max_memory - current_memory>500) return;
00196         typename map<KeyType,pair<ValueType,DoublyLinkedListElement<KeyType>*> >::iterator it = elements.begin();
00197         for (;it!=elements.end();++it)
00198         {
00199             DoublyLinkedListElement<KeyType>* p = it->second.second;
00200             if (!p) 
00201                 PLERROR("BoundedMemoryCache::verifyInvariants(): null linked list pointer!");
00202             DoublyLinkedListElement<KeyType>* next = p->next;
00203             DoublyLinkedListElement<KeyType>* previous = p->previous;
00204             if (previous && previous->next != p)
00205                 PLERROR("BoundedMemoryCache::verifyInvariants(): element not part of list (previous->next != element)\n");
00206             if (next && next->previous != p)
00207                 PLERROR("BoundedMemoryCache::verifyInvariants(): element not part of list (next->previous != element)\n");
00208             typename map<KeyType,pair<ValueType,DoublyLinkedListElement<KeyType>*> >::iterator pi = elements.find(p->entry);
00209             if (pi->second.second!=p)
00210                 PLERROR("BoundedMemoryCache::verifyInvariants(): incoherent pointers between map and list\n");
00211             if (pi->first!=p->entry)
00212                 PLERROR("BoundedMemoryCache::verifyInvariants(): incoherent keys between map and list\n");
00213         }
00214     }
00215 
00216 protected:
00218     inline  virtual void removeExcess()
00219     {
00220         while (current_memory > max_memory)
00221         {
00222             KeyType& key = doubly_linked_list->last->entry;
00223             current_memory -= sizeInBytes(elements[key]);
00224             elements[key].second=0; elements.erase(key);
00225             doubly_linked_list->removeLast();
00226             n_elements--;
00227 #ifdef BOUNDCHECK
00228             if (!doubly_linked_list->last || doubly_linked_list->last->next)
00229                 PLERROR("something wrong with last element of doubly linked list!");
00230             if (dbg)
00231                 verifyInvariants();
00232 #endif
00233         }
00234     }
00235 
00237     inline virtual void removeAll()
00238     {
00239         while (n_elements)
00240         {
00241             KeyType& key = doubly_linked_list->last->entry;
00242 //            current_memory -= sizeInBytes(elements[key]);
00243             elements[key].second=0; elements.erase(key);
00244             doubly_linked_list->removeLast();
00245             n_elements--;
00246 #ifdef BOUNDCHECK
00247             if (!doubly_linked_list->last || doubly_linked_list->last->next)
00248                 PLERROR("something wrong with last element of doubly linked list!");
00249             if (dbg)
00250                 verifyInvariants();
00251 #endif            
00252         }
00253         current_memory = 0;
00254     }
00255 
00256 };
00257 
00258 } // end of namespace PLearn
00259 
00260 
00261 #endif
00262 
00263 
00264 /*
00265   Local Variables:
00266   mode:c++
00267   c-basic-offset:4
00268   c-file-style:"stroustrup"
00269   c-file-offsets:((innamespace . 0)(inline-open . 0))
00270   indent-tabs-mode:nil
00271   fill-column:79
00272   End:
00273 */
00274 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=79 :
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines