Back to index

texmacs  1.0.7.15
basic_environment.cpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : basic_environment.cpp
00004 * DESCRIPTION: hash tables as environments
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 "basic_environment.hpp"
00013 
00014 tree hash_node::uninit (UNINIT);
00015 tree basic_environment_rep::uninit (UNINIT);
00016 
00017 /******************************************************************************
00018 * Raw access methods which assume an appropriate size for the hash table
00019 ******************************************************************************/
00020 
00021 void
00022 basic_environment_rep::raw_insert (int key, const tree& val) {
00023   //cout << "Raw insert " << key << ", " << val << "\n";
00024   int h= key & (n-1), f= free;
00025   free      = a[f].next;
00026   a[f].key  = key;
00027   a[f].val  = val;
00028   a[f].next = a[h].start;
00029   a[h].start= f;
00030   size++;
00031 }
00032 
00033 void
00034 basic_environment_rep::raw_write (int key, const tree& val) {
00035   //cout << "Raw write " << key << ", " << val << "\n";
00036   int h= key & (n-1), i= a[h].start;
00037   while (i >= 0) {
00038     if (a[i].key == key) {
00039       a[i].val= val;
00040       return;
00041     }
00042     i= a[i].next;
00043   }
00044   int f= free;
00045   free      = a[f].next;
00046   a[f].key  = key;
00047   a[f].val  = val;
00048   a[f].next = a[h].start;
00049   a[h].start= f;
00050   size++;
00051 }
00052 
00053 tree*
00054 basic_environment_rep::raw_read (int key) {
00055   //cout << "Raw read " << key << "\n";
00056   int h= key & (n-1), i= a[h].start;
00057   while (i >= 0) {
00058     if (a[i].key == key)
00059       return & (a[i].val);
00060     i= a[i].next;
00061   }
00062   return NULL;
00063 }
00064 
00065 void
00066 basic_environment_rep::raw_remove (int key) {
00067   //cout << "Raw remove " << key << "\n";
00068   int h= key & (n-1), i= a[h].start, p= -1;
00069   while (i >= 0) {
00070     if (a[i].key == key) {
00071       a[i].val= uninit;
00072       if (p >= 0) a[p].next= a[i].next;
00073       else a[h].start= a[i].next;
00074       a[i].next= free;
00075       free= i;
00076       size--;
00077       return;
00078     }
00079     p= i;
00080     i= a[i].next;
00081   }
00082 }
00083 
00084 /******************************************************************************
00085 * Methods for multiple accesses
00086 ******************************************************************************/
00087 
00088 void
00089 basic_environment_rep::multiple_insert (hash_node* b, int k) {
00090   for (int h=0; h<k; h++) {
00091     int i= b[h].start;
00092     while (i >= 0) {
00093       raw_insert (b[i].key, b[i].val);
00094       i= b[i].next;
00095     }
00096   }
00097 }
00098 
00099 void
00100 basic_environment_rep::multiple_write (hash_node* b, int k) {
00101   for (int h=0; h<k; h++) {
00102     int i= b[h].start;
00103     while (i >= 0) {
00104       raw_write (b[i].key, b[i].val);
00105       i= b[i].next;
00106     }
00107   }
00108 }
00109 
00110 void
00111 basic_environment_rep::multiple_remove (hash_node* b, int k) {
00112   for (int h=0; h<k; h++) {
00113     int i= b[h].start;
00114     while (i >= 0) {
00115       raw_remove (b[i].key);
00116       i= b[i].next;
00117     }
00118   }
00119 }
00120 
00121 void
00122 basic_environment_rep::resize (int new_n) {
00123   //cout << "Resize " << n << " -> " << new_n << " (" << size << ")\n";
00124   ASSERT (new_n >= size, "too small number of bags");
00125   int old_n= n;
00126   hash_node* old_a= a;
00127   n= new_n;
00128   a= tm_new_array<hash_node> (n);
00129   size= 0;
00130   free= 0;
00131   for (int i=0; i<n; i++)
00132     a[i].next= i+1;
00133   multiple_insert (old_a, old_n);
00134 }
00135 
00136 /******************************************************************************
00137 * Printing
00138 ******************************************************************************/
00139 
00140 void
00141 basic_environment_rep::print (const string& prefix) {
00142   cout << prefix << "Basic environment" << LF;
00143   for (int h=0; h<n; h++) {
00144     int i= a[h].start;
00145     while (i >= 0) {
00146       cout << prefix << "| " << a[i].key
00147           << ": " << as_string ((tree_label) a[i].key)
00148           << " -> " << a[i].val << LF;
00149       i= a[i].next;
00150     }
00151   }
00152 }