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

Last change on this file since 1123 was 1123, checked in by sveta, 17 years ago
  • Bugs at work with memory are corrected (added counter of table number).
  • 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  static size_t count; 
23
24  void insert_node (TableNode*);
25  void insert_node_RB (TableNode*);
26  void left_rotate_RB (TableNode*);
27  void right_rotate_RB (TableNode*);
28  TableNode* search_node (Expr const&);
29  void delete_fixup_RB (TableNode*);
30  TableNode* delete_node_RB (TableNode*);
31
32  public :
33
34  inline Table ();
35  inline ~Table();
36  inline void unbind (Expr& _key);
37  inline bool lookup (Expr const& _key, Expr& _val);
38  inline bool in_table (Expr const& _key);
39  inline Expr domain ();
40  inline void table_copy (Table& _tab);
41  inline void replace_table (Table const& _tab);
42  inline void bind (Expr const& _key, Expr const& _val);
43  inline unsigned get_type () const;
44  inline uint32_t hash () const;
45  inline bool operator == (Object const&) const; 
46};
47 
48class TableNode 
49{
50  friend class Table;
51
52  private: 
53       
54  int hash_key;
55  enum {BLACK, RED} color;
56  Expr key;       // key-expression
57  Expr val;       // value-expression
58  TableNode* left;    // left child
59  TableNode* right;   // right child
60  TableNode* p;       // parent   
61
62  static TableNode* nil;   
63
64  friend TableNode* tree_successor (TableNode*) ;
65  friend TableNode* tree_minimum (TableNode*) ;
66  friend void list_node (TableNode const&, Expr&) ;
67  friend void copy_tree (TableNode const&, TableNode&) ;
68  friend void delete_tree (TableNode*) ;
69  friend bool table_equal (TableNode const&, TableNode const&) ;
70};
71
72}
73
74
75#endif      //__rf_table_hh__
Note: See TracBrowser for help on using the repository browser.