Back to index

texmacs  1.0.7.15
basic_environment.hpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : basic_environment.hpp
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 #ifndef BASIC_ENVIRONMENT_H
00013 #define BASIC_ENVIRONMENT_H
00014 #include "assoc_environment.hpp"
00015 
00016 /******************************************************************************
00017 * Basic environments are represented by an array of hash_nodes of length n=2^p
00018 * The hash table both has n slots and maximal size n. The association list
00019 * corresponding to hash code h starts at index 'a[h%n].start'. Each item in
00020 * the list is a hash_node with a key-value pair and the index 'next' of
00021 * the next item. The end of the list is indicated by the index -1.
00022 * A list with unused space is also maintained and it starts at index 'free'.
00023 ******************************************************************************/
00024 
00025 class basic_environment_rep;
00026 class hash_node {
00027   static tree uninit;
00028 public:
00029   int  key;    // key of the pair
00030   tree val;    // value of the pair
00031   int  start;  // index of list associated to hash code
00032   int  next;   // next index in list after this pair (or next free space)
00033 public:
00034   inline hash_node (): val (uninit), start (-1) {}
00035 };
00036 
00037 /******************************************************************************
00038 * Basic environments
00039 ******************************************************************************/
00040 
00041 class basic_environment_rep: public environment_rep {
00042   static tree uninit;
00043 public:
00044   int size;      // total number of elements
00045   int n;         // allocated number of bags (power of two and size <= n)
00046   hash_node* a;  // the nodes, which are bags at the same time
00047   int free;      // index of free space
00048 
00049 public:
00050   inline basic_environment_rep (int n2):
00051     size (0), n (n2), a (tm_new_array<hash_node> (n)), free (0) {
00052       for (int i=0; i<n; i++) a[i].next= i+1; }
00053   inline ~basic_environment_rep () {
00054     tm_delete_array (a); }
00055 
00056   void raw_insert (int key, const tree& val);
00057   void raw_write (int key, const tree& val);
00058   tree* raw_read (int key);
00059   void raw_remove (int key);
00060   void multiple_insert (hash_node* b, int k);
00061   void multiple_write (hash_node* b, int k);
00062   void multiple_remove (hash_node* b, int k);
00063   void resize (int new_n);
00064 
00065   inline bool contains (int key) {
00066     return raw_read (key) != 0; }
00067   inline tree read (int key) {
00068     tree* ptr= raw_read (key);
00069     return ptr==NULL? uninit: *ptr; }
00070   inline void write (int key, const tree& val) {
00071     if (size >= n) resize (n << 1);
00072     raw_write (key, val); }
00073   inline void remove (int key) {
00074     raw_remove (key);
00075     if (size < (n>>2)) resize (n>>1); }
00076   void print (const string& prefix);
00077 };
00078 
00079 class basic_environment {
00080   ABSTRACT_NULL(basic_environment);
00081   inline tree operator [] (int key) {
00082     return rep->read (key); }
00083   inline basic_environment (int n):
00084     rep (tm_new<basic_environment_rep> (n)) {}
00085   inline basic_environment (assoc_environment env):
00086     rep (tm_new<basic_environment_rep> (round_pow2 (env->n))) {
00087       for (int i=0; i<env->n; i++)
00088        rep->raw_insert (env->a[i].key, env->a[i].val); }
00089   inline friend environment as_environment (const basic_environment& env) {
00090     return environment ((environment_rep*) env.rep); }
00091   inline friend basic_environment as_basic_environment (const environment& e) {
00092     return basic_environment ((basic_environment_rep*) as_pointer (e)); }
00093 };
00094 ABSTRACT_NULL_CODE(basic_environment);
00095 
00096 #endif // defined BASIC_ENVIRONMENT_H