Changeset 983


Ignore:
Timestamp:
Jul 9, 2003, 12:45:35 PM (18 years ago)
Author:
sveta
Message:
  • Function format is changed.
Location:
to-imperative/trunk/runtime
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • to-imperative/trunk/runtime/rf_table.cc

    r969 r983  
    99TableNode* TableNode::nil = NULL;
    1010
    11 // zaglushka 
    12 int Expr_hash(Expr const&);
    13  
    14 
    15 void Table::Bind (Expr const& _key, Expr const& _val)
    16 {
    17   TableNode *newNode;
    18   if ((newNode = IterativeTreeSearch(_key)) == TableNode::nil) {
    19     newNode = new TableNode;
    20     newNode->key = _key;
    21     newNode->hashKey = Expr_hash(_key);
    22     newNode->left = TableNode::nil;
    23     newNode->right = TableNode::nil;
    24     newNode->p = TableNode::nil;
    25     newNode->val = _val;
    26     RB_Insert(newNode);
    27   }
    28   else
    29     newNode->val = _val;
    30 }
    31 
    32 void Table::Unbind (Expr& _key)
    33 {
    34   TableNode *newNode;
    35   if ((newNode = IterativeTreeSearch(_key)) != TableNode::nil) {
    36     newNode = RB_Delete(newNode);
    37     delete(newNode);
    38   }
    39 }
    40 
    41 
    42 bool Table::Lookup (Expr const& _key, Expr& _val)
    43 {   
    44   TableNode *newNode;
    45   if ((newNode = IterativeTreeSearch(_key)) == TableNode::nil)
    46     return false;   
    47   else {
    48     _val = newNode->val;
    49     return true;
    50   }
    51 }
    52 
    53 
    54 bool Table::InTable (Expr const& _key)
    55 {
    56   TableNode *newNode;
    57   if ((newNode = IterativeTreeSearch(_key)) == TableNode::nil)
    58     return false;
    59   else
    60     return true;
    61 }
    62 
    63  
    64 //
    65 // Table_copy : this - sourceTable, newTable - result
    66 void Table::TableCopy (Table& _new_table)
    67 { 
    68   TableNode *node;
    69   if (root != TableNode::nil) {
    70     node = new TableNode;
    71     node->p = TableNode::nil;       
    72     _new_table.root = node;   // p - root 
    73     CopyTree(root, node);  // p - root
    74   }
    75 }
    76 
    77  
    78 //
    79 //  ReplaceTable: this - TargetTable
    80 void Table::ReplaceTable (Table const& _source_table)   
    81 {   
    82   TableNode* x;
    83   if (root != TableNode::nil) {
    84     DeleteTree(root);
    85     root = TableNode::nil;   
    86   }
    87   if (_source_table.root != TableNode::nil) {   
    88     x = new TableNode;
    89     x->p = TableNode::nil;
    90     root = x;     
    91     CopyTree(_source_table.root, root);
    92   }
    93 }
    94 
    95 
    9611// 
    9712// inserting of element newNode in this-Table
    98 void Table::TreeInsert (TableNode* _newNode)
     13void Table::InsertNode (TableNode* _newNode)
    9914{
    10015  TableNode* x;
    … …  
    14661
    14762
    148 void Table::LeftRotate (TableNode* _x)
     63void Table::LeftRotate_RB (TableNode* _x)
    14964{
    15065  TableNode* y;
    … …  
    16580
    16681
    167 void Table::RightRotate (TableNode* _y)
     82void Table::RightRotate_RB (TableNode* _y)
    16883{
    16984  TableNode* x;
    … …  
    18499
    185100
    186 void Table::RB_Insert (TableNode* _x)
     101void Table::InsertNode_RB (TableNode* _x)
    187102{ 
    188103  TableNode *y;
    189   TreeInsert(_x);
     104  InsertNode(_x);
    190105  _x->color = RED;
    191106  while ((_x != root) && (_x->p->color == RED)) {   
    … …  
    200115        if (_x == _x->p->right) {
    201116          _x = _x->p;
    202           LeftRotate(_x);
     117          LeftRotate_RB(_x);
    203118        }
    204119        _x->p->color = BLACK;
    205120        _x->p->p->color =RED;
    206         RightRotate(_x->p->p);
     121        RightRotate_RB(_x->p->p);
    207122      }
    208123    } else {
    … …  
    216131        if (_x == _x->p->left) {
    217132          _x = _x->p;
    218           RightRotate(_x);
     133          RightRotate_RB(_x);
    219134        }
    220135        _x->p->color = BLACK;
    221136        _x->p->p->color = RED;
    222         LeftRotate(_x->p->p);
     137        LeftRotate_RB(_x->p->p);
    223138      }
    224139    }
    … …  
    228143
    229144
    230 TableNode* Table::RB_Delete (TableNode *_z)
     145TableNode* Table::DeleteNode_RB (TableNode *_z)
    231146{
    232147  TableNode* x;
    … …  
    254169  }
    255170  if (y->color == BLACK)
    256     RB_DeleteFixup(x);
     171    DeleteFixup_RB(x);
    257172  return y;
    258173}
    259174
    260175
    261 void Table::RB_DeleteFixup (TableNode* _x)
     176void Table::DeleteFixup_RB (TableNode* _x)
    262177{
    263178  TableNode* w;
    … …  
    268183        w->color = BLACK;
    269184        _x->p->color = RED;
    270         LeftRotate(_x->p);
     185        LeftRotate_RB(_x->p);
    271186        w = _x->p->right;
    272187      }
    … …  
    278193          w->left->color = BLACK;
    279194          w->color = RED;
    280           RightRotate(w);
     195          RightRotate_RB(w);
    281196          w = _x->p->right;
    282197        }
    … …  
    284199        _x->p->color = BLACK;
    285200        w->right->color = BLACK;
    286         LeftRotate(_x->p);
     201        LeftRotate_RB(_x->p);
    287202        _x=root; 
    288203      }
    … …  
    292207        w->color = BLACK;
    293208        _x->p->color = RED;
    294         RightRotate(_x->p);
     209        RightRotate_RB(_x->p);
    295210        w = _x->p->left;
    296211      }
    … …  
    302217          w->right->color = BLACK;
    303218          w->color = RED;
    304           LeftRotate(w);
     219          LeftRotate_RB(w);
    305220          w = _x->p->left;
    306221        }
    … …  
    308223        _x->p->color = BLACK;
    309224        w->left->color = BLACK;
    310         RightRotate(_x->p);
     225        RightRotate_RB(_x->p);
    311226        _x=root; 
    312227      }
    … …  
    317232
    318233
    319 TableNode* Table::IterativeTreeSearch (Expr const& _key)
     234TableNode* Table::SearchNode (Expr const& _key)
    320235{ 
    321236  TableNode* node;
    … …  
    370285}
    371286
    372 
    373287bool TableEqual(TableNode* _tab1, TableNode* _tab2)
    374288{ 
    … …  
    404318
    405319
    406 void InorderTreeWalk (TableNode* _node, Expr& _res)
     320void ListNode (TableNode* _node, Expr& _res)
    407321{
    408322  if (_node != TableNode::nil) { 
    409     InorderTreeWalk(_node->left, _res);
    410     InorderTreeWalk(_node->right, _res);
     323    ListNode(_node->left, _res);
     324    ListNode(_node->right, _res);
    411325    _res = _res + (_node->key)();
    412326  }
    … …  
    436350
    437351
    438 //  hash - zaglushka
    439 int Expr_hash (Expr const& _key)
    440 {
    441   return _key.get_len();
    442 }
    443 
    444 
    445 }
     352}

  • to-imperative/trunk/runtime/rf_table.hh

    r969 r983  
    2424  TableNode* root;    // root of RB-tree 
    2525
    26   void TreeInsert (TableNode*);
    27   void RB_Insert (TableNode*);
    28   void LeftRotate (TableNode*);
    29   void RightRotate (TableNode*);
    30   TableNode* IterativeTreeSearch (Expr const&);
    31   void RB_DeleteFixup (TableNode*);
    32   TableNode* RB_Delete (TableNode*);
     26  void InsertNode (TableNode*);
     27  void InsertNode_RB (TableNode*);
     28  void LeftRotate_RB (TableNode*);
     29  void RightRotate_RB (TableNode*);
     30  TableNode* SearchNode (Expr const&);
     31  void DeleteFixup_RB (TableNode*);
     32  TableNode* DeleteNode_RB (TableNode*);
    3333
    3434  public :
    3535  inline Table ();
    3636  inline ~Table();
    37   void Unbind (Expr& _key);
    38   bool Lookup (Expr const& _key, Expr& _val);
    39   bool InTable (Expr const& _key);
     37  inline void Unbind (Expr& _key);
     38  inline bool Lookup (Expr const& _key, Expr& _val);
     39  inline bool InTable (Expr const& _key);
    4040  inline Expr Domain ();
    41   void TableCopy (Table& _tab);
    42   void ReplaceTable (Table const& _tab);
    43   void Bind (Expr const& _key, Expr const& _val);
     41  inline void TableCopy (Table& _tab);
     42  inline void ReplaceTable (Table const& _tab);
     43  inline void Bind (Expr const& _key, Expr const& _val);
    4444  inline unsigned get_type () const;
    4545  inline uint32_t hash () const;
    … …  
    6565  friend TableNode* TreeSuccessor (TableNode*) ;
    6666  friend TableNode* TreeMinimum (TableNode*) ;
    67   friend void InorderTreeWalk (TableNode*, Expr&) ;
     67  friend void ListNode (TableNode*, Expr&) ;
    6868  friend void CopyTree (TableNode*, TableNode*) ;
    6969  friend void DeleteTree (TableNode*) ;

  • to-imperative/trunk/runtime/rf_table.ih

    r969 r983  
    5757{ 
    5858  Expr res = Expr();
    59   InorderTreeWalk(root, res);   
     59  ListNode(root, res);   
    6060  return res;
    6161}
     62
     63//  zaglushka  - hash-function
     64inline int Expr_hash (Expr const& _key)
     65{
     66  return _key.get_len();
     67}
     68
     69inline void Table::Bind (Expr const& _key, Expr const& _val)
     70{
     71  TableNode *newNode;
     72  if ((newNode = SearchNode(_key)) == TableNode::nil) {
     73    newNode = new TableNode;
     74    newNode->key = _key;
     75    newNode->hashKey = Expr_hash(_key);
     76    newNode->left = TableNode::nil;
     77    newNode->right = TableNode::nil;
     78    newNode->p = TableNode::nil;
     79    newNode->val = _val;
     80    InsertNode_RB(newNode);
     81  }
     82  else
     83    newNode->val = _val;
     84}
     85
     86inline void Table::Unbind (Expr& _key)
     87{
     88  TableNode *newNode;
     89  if ((newNode = SearchNode(_key)) != TableNode::nil) {
     90    newNode = DeleteNode_RB(newNode);
     91    delete(newNode);
     92  }
     93}
     94
     95
     96inline bool Table::Lookup (Expr const& _key, Expr& _val)
     97{   
     98  TableNode *newNode;
     99  if ((newNode = SearchNode(_key)) == TableNode::nil)
     100    return false;   
     101  else {
     102    _val = newNode->val;
     103    return true;
     104  }
     105}
     106
     107
     108inline bool Table::InTable (Expr const& _key)
     109{
     110  TableNode *newNode;
     111  if ((newNode = SearchNode(_key)) == TableNode::nil)
     112    return false;
     113  else
     114    return true;
     115}
     116
     117 
     118//
     119// Table_copy : this - sourceTable, newTable - result
     120inline void Table::TableCopy (Table& _new_table)
     121{ 
     122  TableNode *node;
     123  if (root != TableNode::nil) {
     124    node = new TableNode;
     125    node->p = TableNode::nil;       
     126    _new_table.root = node;   // p - root 
     127    CopyTree(root, node);  // p - root
     128  }
     129}
     130
     131 
     132//
     133//  ReplaceTable: this - TargetTable
     134inline void Table::ReplaceTable (Table const& _source_table)   
     135{   
     136  TableNode* x;
     137  if (root != TableNode::nil) {
     138    DeleteTree(root);
     139    root = TableNode::nil;   
     140  }
     141  if (_source_table.root != TableNode::nil) {   
     142    x = new TableNode;
     143    x->p = TableNode::nil;
     144    root = x;     
     145    CopyTree(_source_table.root, root);
     146  }
     147}
     148
    62149 
    63150}
Note: See TracChangeset for help on using the changeset viewer.