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

Last change on this file since 1059 was 1059, checked in by sveta, 18 years ago
  • Function names are changed.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 1.7 KB
Line 
1#ifndef __rf_table_hh__
2#define __rf_table_hh__
3
4#include "rf_object.hh"
5#include "rf_expr.hh"
6#include "rf_types.hh"
7
8namespace rftype
9{
10
11using namespace rfrt; 
12 
13class TableNode;
14
15class Table :
16    public Object
17{
18  private :
19 
20  static ObjectRegister reg;
21  TableNode* root;    // root of RB-tree 
22
23  void insert_node (TableNode*);
24  void insert_node_RB (TableNode*);
25  void left_rotate_RB (TableNode*);
26  void right_rotate_RB (TableNode*);
27  TableNode* search_node (Expr const&);
28  void delete_fixup_RB (TableNode*);
29  TableNode* delete_node_RB (TableNode*);
30
31  public :
32
33  inline Table ();
34  inline ~Table();
35  inline void unbind (Expr& _key);
36  inline bool lookup (Expr const& _key, Expr& _val);
37  inline bool in_table (Expr const& _key);
38  inline Expr domain ();
39  inline void table_copy (Table& _tab);
40  inline void replace_table (Table const& _tab);
41  inline void bind (Expr const& _key, Expr const& _val);
42  inline unsigned get_type () const;
43  inline uint32_t hash () const;
44  inline bool operator == (Object const&) const; 
45};
46 
47class TableNode 
48{
49  friend class Table;
50
51  private: 
52       
53  int hash_key;
54  enum {BLACK, RED} color;
55  Expr key;       // key-expression
56  Expr val;       // value-expression
57  TableNode* left;    // left child
58  TableNode* right;   // right child
59  TableNode* p;       // parent   
60
61  static TableNode* nil;   
62
63  friend TableNode* tree_successor (TableNode*) ;
64  friend TableNode* tree_minimum (TableNode*) ;
65  friend void list_node (TableNode const&, Expr&) ;
66  friend void copy_tree (TableNode const&, TableNode&) ;
67  friend void delete_tree (TableNode*) ;
68  friend bool table_equal (TableNode const&, TableNode const&) ;
69};
70
71}
72
73
74#endif      //__rf_table_hh__
Note: See TracBrowser for help on using the repository browser.