Back to index

texmacs  1.0.7.15
memorizer.cpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : memorizer.cpp
00004 * DESCRIPTION: memorizing computations during style rewriting
00005 * COPYRIGHT  : (C) 2006  Joris van der Hoeven
00006 *******************************************************************************
00007 * This software falls under the GNU general public license version 3 or later.
00008 * It comes WITHOUT ANY WARRANTY WHATSOEVER. For details, see the file LICENSE
00009 * in the root directory or <http://www.gnu.org/licenses/gpl-3.0.html>.
00010 ******************************************************************************/
00011 
00012 #include "memorizer.hpp"
00013 #include "environment.hpp"
00014 
00015 /******************************************************************************
00016 * Default implementations
00017 ******************************************************************************/
00018 
00019 int memorizer_count= 0;
00020 
00021 void
00022 memorizer_rep::compute () {
00023   FAILED ("memorizer can't compute its own output");
00024 }
00025 
00026 void
00027 memorizer_rep::set_children (memorizer* a, int n) {
00028   (void) a; (void) n;
00029   FAILED ("not a compound memorizer");
00030 }
00031 
00032 void
00033 memorizer_rep::get_children (memorizer*& a, int& n) {
00034   a= NULL;
00035   n= 0;
00036 }
00037 
00038 void
00039 memorizer_rep::set_environment (environment env) {
00040   (void) env;
00041   FAILED ("not an environment memorizer");
00042 }
00043 
00044 environment
00045 memorizer_rep::get_environment () {
00046   FAILED ("not an environment memorizer");
00047   return environment ();
00048 }
00049 
00050 void
00051 memorizer_rep::set_tree (tree t) {
00052   (void) t;
00053   FAILED ("not a tree memorizer");
00054 }
00055 
00056 tree
00057 memorizer_rep::get_tree () {
00058   FAILED ("not a tree memorizer");
00059   return "";
00060 }
00061 
00062 /******************************************************************************
00063 * Compound memorizers
00064 ******************************************************************************/
00065 
00066 void
00067 compound_memorizer_rep::set_children (memorizer* a2, int n2) {
00068   if (n != 0) {
00069     n= 0;
00070     tm_delete_array (a);
00071   }
00072   if (n2 != 0) {
00073     n= n2;
00074     a= tm_new_array<memorizer> (n);
00075     for (int i=0; i<n; i++)
00076       a[i]= a2[i];
00077   }
00078 }
00079 
00080 void
00081 compound_memorizer_rep::get_children (memorizer*& a2, int& n2) {
00082   a2= a;
00083   n2= n;
00084 }
00085 
00086 void
00087 print_tree (memorizer mem) {
00088   mem->print (cout);
00089   cout << LF;
00090   memorizer* a;
00091   int n;
00092   mem->get_children (a, n);
00093   if (n != 0) {
00094     cout << INDENT;
00095     for (int i=0; i<n; i++)
00096       print_tree (a[i]);
00097     cout << UNINDENT;
00098   }
00099 }
00100 
00101 /******************************************************************************
00102 * Management of children
00103 ******************************************************************************/
00104 
00105 static int  mem_cur;
00106 static int  mem_max_pos;
00107 static int* mem_pos;
00108 static int  mem_max_stack;
00109 static memorizer* mem_stack;
00110 
00111 template<typename T> void
00112 double_size (T*& in, int& size) {
00113   T* out= tm_new_array<T> (2*size);
00114   for (int i=0; i<size; i++)
00115     out[i]= in[i];
00116   tm_delete_array (in);
00117   in= out;
00118   size *= 2;
00119 }
00120 
00121 void
00122 memorize_initialize () {
00123   cout << "Memorize initialize" << INDENT << LF;
00124   mem_max_pos  = 16;
00125   mem_pos      = tm_new_array<int> (mem_max_pos);
00126   mem_max_stack= 16;
00127   mem_stack    = tm_new_array<memorizer> (mem_max_stack);
00128   mem_cur      = 0;
00129   mem_pos[0]   = 0;
00130 }
00131 
00132 memorizer
00133 memorize_finalize () {
00134   cout << UNINDENT << "Memorize finalize" << LF;
00135   memorizer mem= mem_stack[0];
00136   tm_delete_array (mem_pos);
00137   tm_delete_array (mem_stack);
00138   mem_max_pos  = 0;
00139   mem_pos      = NULL;
00140   mem_max_stack= 0;
00141   mem_stack    = NULL;
00142   return mem;
00143 }
00144 
00145 void
00146 memorize_start () {
00147   //cout << "Memorize start" << INDENT << LF;
00148   mem_cur++;
00149   if (mem_cur == mem_max_pos)
00150     double_size (mem_pos, mem_max_pos);
00151   mem_pos[mem_cur]= mem_pos[mem_cur-1];
00152 }
00153 
00154 void
00155 memorize_end () {
00156   mem_cur--;
00157   int start= mem_pos[mem_cur], end= mem_pos[mem_cur+1];
00158   //cout << UNINDENT << "Memorize end [" << start << ", " << end << "]" << LF;
00159   mem_stack[start-1]->set_children (mem_stack + start, end - start);
00160 }
00161 
00162 /******************************************************************************
00163 * Global memorization
00164 ******************************************************************************/
00165 
00166 typedef memorizer_rep* memorizer_ptr;
00167 typedef memorizer_rep** memorizer_ptrs;
00168 
00169 static int bigmem_size= 0;
00170 static int bigmem_bags= 0; // zero or power of two
00171 static int bigmem_bags_mask= bigmem_bags-1;
00172 static memorizer_ptrs* bigmem_mem= NULL;
00173 static int* bigmem_len= NULL;
00174 static int* bigmem_cap= NULL; // elements are zeros or powers of two
00175 
00176 static memorizer_ptr
00177 bigmem_insert (memorizer_ptr ptr) {
00178   if (bigmem_size >= bigmem_bags) {
00179     if (bigmem_bags == 0) {
00180       bigmem_bags= 2;
00181       //bigmem_bags= 1<<24;
00182       //cout << "Construct bigmem " << bigmem_bags << LF;
00183       bigmem_mem = tm_new_array<memorizer_ptrs> (bigmem_bags);
00184       bigmem_len = tm_new_array<int> (bigmem_bags);
00185       bigmem_cap = tm_new_array<int> (bigmem_bags);
00186       for (int i=0; i<bigmem_bags; i++) {
00187        bigmem_mem[i]= NULL;
00188        bigmem_len[i]= 0;
00189        bigmem_cap[i]= 0;
00190       }
00191     }
00192     else {
00193       int new_bags= bigmem_bags << 1;
00194       //cout << "Larger bigmem " << new_bags << LF;
00195       int new_bags_mask= new_bags-1;
00196       memorizer_ptrs* new_mem= tm_new_array<memorizer_ptrs> (new_bags);
00197       int* new_len= tm_new_array<int> (new_bags);
00198       int* new_cap= tm_new_array<int> (new_bags);
00199       for (int i=0; i<bigmem_bags; i++) {
00200        int j= i+ bigmem_bags;
00201        int len= bigmem_len[i];
00202        int cap= bigmem_cap[i];
00203        //cout << "bag " << i << ": " << len << ", " << cap << LF;
00204        if (len == 0) cap= 0;
00205        else while ((len<<1) <= cap && cap >= 4) cap= cap>>1;
00206        new_len[i]= 0;
00207        new_len[j]= 0;
00208        new_cap[i]= cap;
00209        new_cap[j]= cap;
00210        if (cap == 0) {
00211          new_mem[i]= NULL;
00212          new_mem[j]= NULL;
00213        }
00214        else {
00215          new_mem[i]= tm_new_array<memorizer_ptr> (cap);
00216          new_mem[j]= tm_new_array<memorizer_ptr> (cap);
00217          for (int k=0; k<len; k++) {
00218            memorizer_ptr mem_ptr= bigmem_mem[i][k];
00219            int h= mem_ptr->hash () & new_bags_mask;
00220            //cout << "  insert " << h << LF;
00221            ASSERT (h == i || h == j, "failed assertion");
00222            new_mem[h][new_len[h]++]= mem_ptr;
00223          }
00224        }
00225        if (cap != 0) tm_delete_array (bigmem_mem[i]);
00226       }
00227       tm_delete_array (bigmem_mem);
00228       tm_delete_array (bigmem_len);
00229       tm_delete_array (bigmem_cap);
00230       bigmem_bags= new_bags;
00231       bigmem_mem = new_mem;
00232       bigmem_len = new_len;
00233       bigmem_cap = new_cap;
00234     }
00235     bigmem_bags_mask= bigmem_bags-1;
00236   }
00237 
00238   int h= ptr->hash () & bigmem_bags_mask;
00239   memorizer_ptrs a= bigmem_mem[h];
00240   int i, len= bigmem_len[h];
00241   for (i=0; i<len; i++)
00242     if (a[i]->type () == ptr->type () && a[i]->equal (ptr))
00243       return a[i];
00244   int cap= bigmem_cap[h];
00245   if (len >= cap) {
00246     if (cap == 0) {
00247       a  = tm_new_array<memorizer_ptr> (2);
00248       cap= 2;
00249     }
00250     else {
00251       int new_cap= cap<<1;
00252       memorizer_ptrs b= tm_new_array<memorizer_ptr> (new_cap);
00253       for (i=0; i<len; i++) b[i]= a[i];
00254       tm_delete_array (a);
00255       a  = b;
00256       cap= new_cap;
00257     }
00258     bigmem_mem[h]= a;
00259     bigmem_cap[h]= cap;
00260   }
00261   a[bigmem_len[h]++]= ptr;
00262   bigmem_size++;
00263   //cout << "Added [" << bigmem_size << ", " << ptr << "] ";
00264   //ptr->print (cout);
00265   //cout << LF;
00266   return ptr;
00267 }
00268 
00269 static void
00270 bigmem_remove (memorizer_ptr ptr) {
00271   int h= ptr->hash () & bigmem_bags_mask;
00272   memorizer_ptrs a= bigmem_mem[h];
00273   int i, len= bigmem_len[h];
00274   for (i=0; i<len; i++)
00275     if (a[i] == ptr) {
00276       len--;
00277       a[i]= a[len];
00278       bigmem_len[h]= len;
00279       bigmem_size--;
00280       //cout << "Removed [" << bigmem_size << ", " << ptr << "] ";
00281       //ptr->print (cout);
00282       //cout << LF;
00283       return;
00284     }
00285   FAILED ("pointer not found");
00286 }
00287 
00288 memorizer::memorizer (memorizer_rep* ptr) {
00289   rep= bigmem_insert (ptr);
00290   //cout << "construct " << ptr << " -> " << rep << LF;
00291   if (rep != ptr) tm_delete (ptr);
00292   //cout << "  set " << mem_pos[mem_cur] << ": " << rep << LF;
00293   memorizer_rep*& old_rep (mem_stack[mem_pos[mem_cur]++].rep);
00294   if (rep == old_rep) rep->ref_count++;
00295   else {
00296     if (old_rep != NULL) {
00297       old_rep->ref_count--;
00298       if (old_rep->ref_count == 0) tm_delete (old_rep);
00299     }
00300     old_rep= rep;
00301     rep->ref_count += 2;
00302   }
00303   if (mem_pos[mem_cur] == mem_max_stack)
00304     double_size (mem_stack, mem_max_stack);
00305 }
00306 
00307 memorizer::~memorizer () {
00308   if (rep != NULL) {
00309     rep->ref_count--;
00310     //cout << "destroy " << rep << ", " << rep->ref_count << LF;
00311     if (rep->ref_count == 0) {
00312       bigmem_remove (rep);
00313       tm_delete (rep);
00314     }
00315   }
00316 }
00317 
00318 memorizer&
00319 memorizer::operator = (memorizer mem) {
00320   //cout << "assign " << rep << ", " << mem.rep << LF;
00321   if (rep == mem.rep) return *this;
00322   if (rep != NULL) {
00323     rep->ref_count--;
00324     //cout << "refcount " << rep << ", " << rep->ref_count << "\n";
00325     if (rep->ref_count == 0) {
00326       bigmem_remove (rep);
00327       tm_delete (rep);
00328     }
00329   }
00330   rep= mem.rep;
00331   if (rep != NULL) rep->ref_count++;
00332   return *this;
00333 }