source: to-imperative/trunk/runtime/rf_table.hh @ 1123

#ifndef __rf_table_hh__
#define __rf_table_hh__

#include "rf_object.hh"
#include "rf_expr.hh"
#include "rf_types.hh"

namespace rftype
{

using namespace rfrt;  
  
class TableNode;

class Table :
    public Object
{
  private :
  
  static ObjectRegister reg;
  TableNode* root;    // root of RB-tree
  static size_t count;  

  void insert_node (TableNode*);
  void insert_node_RB (TableNode*);
  void left_rotate_RB (TableNode*);
  void right_rotate_RB (TableNode*);
  TableNode* search_node (Expr const&);
  void delete_fixup_RB (TableNode*);
  TableNode* delete_node_RB (TableNode*);

  public :

  inline Table ();
  inline ~Table();
  inline void unbind (Expr& _key);
  inline bool lookup (Expr const& _key, Expr& _val);
  inline bool in_table (Expr const& _key);
  inline Expr domain ();
  inline void table_copy (Table& _tab);
  inline void replace_table (Table const& _tab);
  inline void bind (Expr const& _key, Expr const& _val);
  inline unsigned get_type () const;
  inline uint32_t hash () const;
  inline bool operator == (Object const&) const; 
};
  
class TableNode 
{
  friend class Table;

  private: 
       
  int hash_key;
  enum {BLACK, RED} color;
  Expr key;       // key-expression
  Expr val;       // value-expression
  TableNode* left;    // left child
  TableNode* right;   // right child
  TableNode* p;       // parent   

  static TableNode* nil;    

  friend TableNode* tree_successor (TableNode*) ;
  friend TableNode* tree_minimum (TableNode*) ;
  friend void list_node (TableNode const&, Expr&) ;
  friend void copy_tree (TableNode const&, TableNode&) ;
  friend void delete_tree (TableNode*) ;
  friend bool table_equal (TableNode const&, TableNode const&) ;
};

}


#endif      //__rf_table_hh__