Changeset 1059


Ignore:
Timestamp:
Jul 28, 2003, 4:03:54 PM (17 years ago)
Author:
sveta
Message:
  • Function names are changed.
Location:
to-imperative/trunk
Files:
10 edited

Legend:

Unmodified
Added
Removed
  • to-imperative/trunk/library/Table/bind.cc

    r1000 r1059  
    1919    if (!_t)
    2020      RF_LIB_ERROR("Invalid argument");
    21     _t -> Bind(_key,_val);   
     21    _t -> bind(_key,_val);   
    2222  } else
    2323   RF_LIB_ERROR("Invalid argument");
  • to-imperative/trunk/library/Table/domain.cc

    r1000 r1059  
    1919   if (!t)
    2020     RF_LIB_ERROR("Invalid argument");
    21    _res=t->Domain();   
     21   _res=t->domain();   
    2222   } else
    2323     RF_LIB_ERROR("Invalid argument");
  • to-imperative/trunk/library/Table/in_table.cc

    r1000 r1059  
    1919    if (!_t)
    2020      RF_LIB_ERROR("Invalid argument");
    21     if (!(_t->InTable(_key)))
     21    if (!(_t->in_table(_key)))
    2222      retfail;   
    2323  } else
  • to-imperative/trunk/library/Table/lookup.cc

    r1000 r1059  
    2020    if (!_t)
    2121      RF_LIB_ERROR("Invalid argument"); 
    22     if (!(_t->Lookup(_key, result)))
     22    if (!(_t->lookup(_key, result)))
    2323      retfail;
    2424    _val=result;   
  • to-imperative/trunk/library/Table/replace_table.cc

    r1000 r1059  
    2424      if (!source)
    2525        RF_LIB_ERROR("Invalid argument");
    26       target->ReplaceTable(*source);       
     26      target->replace_table(*source);       
    2727    } else
    2828      RF_LIB_ERROR("Invalid argument");   
  • to-imperative/trunk/library/Table/table_copy.cc

    r1000 r1059  
    2222      RF_LIB_ERROR("Invalid argument");         
    2323    rftype::Table* copy = new rftype::Table();
    24     t->TableCopy(*copy);     
     24    t->table_copy(*copy);     
    2525    _tabcopy = Expr (new rftype::Table(*copy));   
    2626  } else
  • to-imperative/trunk/library/Table/unbind.cc

    r1000 r1059  
    1919    if (!t)
    2020      RF_LIB_ERROR("Invalid argument");
    21     t -> Unbind(_key);                                                   
     21    t -> unbind(_key);                                                   
    2222  } else
    2323    RF_LIB_ERROR("Invalid argument");
  • to-imperative/trunk/runtime/rf_table.cc

    r1001 r1059  
    1111// 
    1212// inserting of element newNode in this-Table
    13 void Table::InsertNode (TableNode* _newNode)
     13void Table::insert_node (TableNode* _node)
    1414{
    1515  TableNode* x;
     
    2020  while (x != TableNode::nil) {
    2121    y=x;
    22     if ((_newNode->hashKey) == (x->hashKey)) { 
    23       flag = Expr::compare(_newNode->key, x->key);
     22    if ((_node->hash_key) == (x->hash_key)) { 
     23      flag = Expr::compare(_node->key, x->key);
    2424      if (!flag)                    //   case 0 :  ==
    2525        return;
     
    3232      }
    3333    }
    34     if ((_newNode->hashKey) < (x->hashKey))
     34    if ((_node->hash_key) < (x->hash_key))
    3535      x = x->left;
    3636    else
    3737      x = x->right;
    3838  }
    39   _newNode->p = y;
     39  _node->p = y;
    4040  if (y == TableNode::nil)
    41     root = _newNode; 
    42   else
    43     if ((_newNode->hashKey) == (x->hashKey)) { 
    44       flag = Expr::compare(_newNode->key, x->key);
     41    root = _node; 
     42  else
     43    if ((_node->hash_key) == (x->hash_key)) { 
     44      flag = Expr::compare(_node->key, x->key);
    4545      if (flag == -1) {          //  case -1 : <
    46         y->left = _newNode;
     46        y->left = _node;
    4747        return;
    4848      } else {
    49         y->right = _newNode;
     49        y->right = _node;
    5050        return;
    5151      }
    5252    }   
    53   if ((_newNode->hashKey) < (y->hashKey))
    54     y->left = _newNode;
    55   else
    56     y->right = _newNode;
    57 }
    58 
    59 
    60 void Table::LeftRotate_RB (TableNode* _x)
     53  if ((_node->hash_key) < (y->hash_key))
     54    y->left = _node;
     55  else
     56    y->right = _node;
     57}
     58
     59
     60void Table::left_rotate_RB (TableNode* _x)
    6161{
    6262  TableNode* y;
     
    7777
    7878
    79 void Table::RightRotate_RB (TableNode* _y)
     79void Table::right_rotate_RB (TableNode* _y)
    8080{
    8181  TableNode* x;
     
    9696
    9797
    98 void Table::InsertNode_RB (TableNode* _x)
     98void Table::insert_node_RB (TableNode* _x)
    9999
    100100  TableNode *y;
    101   InsertNode(_x);
     101  insert_node(_x);
    102102  _x->color = TableNode::RED;
    103103  while ((_x != root) && (_x->p->color == TableNode::RED)) {   
     
    112112        if (_x == _x->p->right) {
    113113          _x = _x->p;
    114           LeftRotate_RB(_x);
     114          left_rotate_RB(_x);
    115115        }
    116116        _x->p->color = TableNode::BLACK;
    117117        _x->p->p->color =TableNode::RED;
    118         RightRotate_RB(_x->p->p);
     118        right_rotate_RB(_x->p->p);
    119119      }
    120120    } else {
     
    128128        if (_x == _x->p->left) {
    129129          _x = _x->p;
    130           RightRotate_RB(_x);
     130          right_rotate_RB(_x);
    131131        }
    132132        _x->p->color = TableNode::BLACK;
    133133        _x->p->p->color = TableNode::RED;
    134         LeftRotate_RB(_x->p->p);
     134        left_rotate_RB(_x->p->p);
    135135      }
    136136    }
     
    140140
    141141
    142 TableNode* Table::DeleteNode_RB (TableNode *_z)
     142TableNode* Table::delete_node_RB (TableNode *_z)
    143143{
    144144  TableNode* x;
     
    147147    y = _z;
    148148  else
    149     y = TreeSuccessor(_z);
     149    y = tree_successor(_z);
    150150  if (y->left != TableNode::nil)
    151151    x = y->left;
     
    161161      y->p->right = x;
    162162  if (y != _z) {
    163     _z->hashKey = y->hashKey;
     163    _z->hash_key = y->hash_key;
    164164    _z->val = y->val;
    165165    _z->key = y->key;
    166166  }
    167167  if (y->color == TableNode::BLACK)
    168     DeleteFixup_RB(x);
     168    delete_fixup_RB(x);
    169169  return y;
    170170}
    171171
    172172
    173 void Table::DeleteFixup_RB (TableNode* _x)
     173void Table::delete_fixup_RB (TableNode* _x)
    174174{
    175175  TableNode* w;
     
    180180        w->color = TableNode::BLACK;
    181181        _x->p->color = TableNode::RED;
    182         LeftRotate_RB(_x->p);
     182        left_rotate_RB(_x->p);
    183183        w = _x->p->right;
    184184      }
     
    190190          w->left->color = TableNode::BLACK;
    191191          w->color = TableNode::RED;
    192           RightRotate_RB(w);
     192          right_rotate_RB(w);
    193193          w = _x->p->right;
    194194        }
     
    196196        _x->p->color = TableNode::BLACK;
    197197        w->right->color = TableNode::BLACK;
    198         LeftRotate_RB(_x->p);
     198        left_rotate_RB(_x->p);
    199199        _x=root; 
    200200      }
     
    204204        w->color = TableNode::BLACK;
    205205        _x->p->color = TableNode::RED;
    206         RightRotate_RB(_x->p);
     206        right_rotate_RB(_x->p);
    207207        w = _x->p->left;
    208208      }
     
    214214          w->right->color = TableNode::BLACK;
    215215          w->color = TableNode::RED;
    216           LeftRotate_RB(w);
     216          left_rotate_RB(w);
    217217          w = _x->p->left;
    218218        }
     
    220220        _x->p->color = TableNode::BLACK;
    221221        w->left->color = TableNode::BLACK;
    222         RightRotate_RB(_x->p);
     222        right_rotate_RB(_x->p);
    223223        _x=root; 
    224224      }
     
    229229
    230230
    231 TableNode* Table::SearchNode (Expr const& _key)
     231TableNode* Table::search_node (Expr const& _key)
    232232
    233233  TableNode* node;
    234234  int hash, flag;
    235235
    236   hash = Expr_hash(_key);
     236  hash = expr_hash(_key);
    237237  node = root; 
    238   while ((node != TableNode::nil) && (node->hashKey != hash))
    239     if (hash < node->hashKey)
     238  while ((node != TableNode::nil) && (node->hash_key != hash))
     239    if (hash < node->hash_key)
    240240      node = node->left;
    241241    else
    242242      node = node->right;   
    243   while ((node != TableNode::nil) && (hash == node->hashKey)) {
     243  while ((node != TableNode::nil) && (hash == node->hash_key)) {
    244244    flag = Expr::compare(_key, node->key);
    245245    if (!flag)            //   case 0 : ==
     
    254254
    255255
    256 void CopyTree (TableNode const&  _tab, TableNode& _copy)
     256void copy_tree (TableNode const&  _tab, TableNode& _copy)
    257257{   
    258258  TableNode* child;   
    259   _copy.hashKey = _tab.hashKey;
     259  _copy.hash_key = _tab.hash_key;
    260260  _copy.key = _tab.key;
    261261  _copy.val = _tab.val;
     
    267267    child->p = &_copy;
    268268    _copy.left = child;
    269     CopyTree(*(_tab.left), *child);
     269    copy_tree(*(_tab.left), *child);
    270270  }
    271271  if (_tab.right == TableNode::nil)
     
    275275    child->p = &_copy;
    276276    _copy.right = child;
    277     CopyTree( *(_tab.right), *child);
    278   }
    279 }
    280 
    281 bool TableEqual(TableNode const& _tab1, TableNode const& _tab2)
     277    copy_tree( *(_tab.right), *child);
     278  }
     279}
     280
     281bool table_equal(TableNode const& _tab1, TableNode const& _tab2)
    282282
    283283  if ((&_tab1) == TableNode::nil) {
     
    289289    if ((&_tab2) == TableNode::nil)
    290290      return false;
    291     if ( (_tab1.hashKey == _tab2.hashKey) &&
     291    if ( (_tab1.hash_key == _tab2.hash_key) &&
    292292      (_tab1.color == _tab2.color) &&
    293293      (_tab1.key == _tab2.key) &&
    294294      (_tab1.val == _tab2.val) &&
    295       (TableEqual(*_tab1.right, *_tab2.right)) &&
    296       (TableEqual(*_tab1.left, *_tab2.left)) )
     295      (table_equal(*_tab1.right, *_tab2.right)) &&
     296      (table_equal(*_tab1.left, *_tab2.left)) )
    297297      return true;
    298298    else
     
    302302
    303303
    304 void DeleteTree (TableNode* _node)
     304void delete_tree (TableNode* _node)
    305305{   
    306306  if (_node->left != TableNode::nil)
    307     DeleteTree(_node->left);
     307    delete_tree(_node->left);
    308308  if (_node->right != TableNode::nil)
    309     DeleteTree(_node->right);
     309    delete_tree(_node->right);
    310310  delete(_node);
    311311}
    312312
    313313
    314 void ListNode (TableNode const& _node, Expr& _res)
     314void list_node (TableNode const& _node, Expr& _res)
    315315{
    316316  if (_node.left != TableNode::nil)   
    317     ListNode( * _node.left, _res);
     317    list_node( * _node.left, _res);
    318318  if (_node.right != TableNode::nil)
    319     ListNode( * _node.right, _res);
     319    list_node( * _node.right, _res);
    320320  _res = _res + (_node.key)();
    321321}
    322322
    323323
    324 TableNode*  TreeSuccessor(TableNode* _x)
     324TableNode*  tree_successor(TableNode* _x)
    325325{
    326326  TableNode* y;
    327327  if (_x->right != TableNode::nil)
    328     return TreeMinimum(_x->right);
     328    return tree_minimum(_x->right);
    329329  y=_x->p;
    330330  while ((y != TableNode::nil) && (_x == y->right)) {
     
    336336
    337337
    338 TableNode* TreeMinimum (TableNode* _x)
     338TableNode* tree_minimum (TableNode* _x)
    339339{
    340340  while (_x->left != TableNode::nil)
  • to-imperative/trunk/runtime/rf_table.hh

    r1001 r1059  
    2121  TableNode* root;    // root of RB-tree 
    2222
    23   void InsertNode (TableNode*);
    24   void InsertNode_RB (TableNode*);
    25   void LeftRotate_RB (TableNode*);
    26   void RightRotate_RB (TableNode*);
    27   TableNode* SearchNode (Expr const&);
    28   void DeleteFixup_RB (TableNode*);
    29   TableNode* DeleteNode_RB (TableNode*);
     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*);
    3030
    3131  public :
     
    3333  inline Table ();
    3434  inline ~Table();
    35   inline void Unbind (Expr& _key);
    36   inline bool Lookup (Expr const& _key, Expr& _val);
    37   inline bool InTable (Expr const& _key);
    38   inline Expr Domain ();
    39   inline void TableCopy (Table& _tab);
    40   inline void ReplaceTable (Table const& _tab);
    41   inline void Bind (Expr const& _key, Expr const& _val);
     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);
    4242  inline unsigned get_type () const;
    4343  inline uint32_t hash () const;
     
    5151  private:
    5252       
    53   int hashKey;
     53  int hash_key;
    5454  enum {BLACK, RED} color;
    5555  Expr key;       // key-expression
     
    6161  static TableNode* nil;   
    6262
    63   friend TableNode* TreeSuccessor (TableNode*) ;
    64   friend TableNode* TreeMinimum (TableNode*) ;
    65   friend void ListNode (TableNode const&, Expr&) ;
    66   friend void CopyTree (TableNode const&, TableNode&) ;
    67   friend void DeleteTree (TableNode*) ;
    68   friend bool TableEqual (TableNode const&, TableNode const&) ;
     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&) ;
    6969};
    7070
  • to-imperative/trunk/runtime/rf_table.ih

    r1001 r1059  
    3838  try {
    3939    Table const&  t = static_cast <Table const&>(_table); 
    40     return TableEqual(*root, *t.root);
     40    return table_equal(*root, *t.root);
    4141 }
    4242  catch (std::bad_cast&)
     
    5151
    5252   if (root != TableNode::nil)
    53      DeleteTree(root);
     53     delete_tree(root);
    5454}
    5555
    56 inline Expr Table::Domain ()
     56inline Expr Table::domain ()
    5757
    5858  Expr res = Expr();
    5959  if (root != TableNode::nil)
    60     ListNode(*root, res);   
     60    list_node(*root, res);   
    6161  return res;
    6262}
    6363
    6464//  zaglushka  - hash-function
    65 inline int Expr_hash (Expr const& _key)
     65inline int expr_hash (Expr const& _key)
    6666{
    6767  return _key.get_len();
    6868}
    6969
    70 inline void Table::Bind (Expr const& _key, Expr const& _val)
     70inline void Table::bind (Expr const& _key, Expr const& _val)
    7171{
    72   TableNode *newNode;
    73   if ((newNode = SearchNode(_key)) == TableNode::nil) {
    74     newNode = new TableNode;
    75     newNode->key = _key;
    76     newNode->hashKey = Expr_hash(_key);
    77     newNode->left = TableNode::nil;
    78     newNode->right = TableNode::nil;
    79     newNode->p = TableNode::nil;
    80     newNode->val = _val;
    81     InsertNode_RB(newNode);
     72  TableNode* new_node;
     73  if ((new_node = search_node(_key)) == TableNode::nil) {
     74    new_node = new TableNode;
     75    new_node->key = _key;
     76    new_node->hash_key = expr_hash(_key);
     77    new_node->left = TableNode::nil;
     78    new_node->right = TableNode::nil;
     79    new_node->p = TableNode::nil;
     80    new_node->val = _val;
     81    insert_node_RB(new_node);
    8282  }
    8383  else
    84     newNode->val = _val;
     84    new_node->val = _val;
    8585}
    8686
    87 inline void Table::Unbind (Expr& _key)
     87inline void Table::unbind (Expr& _key)
    8888{
    89   TableNode *newNode;
    90   if ((newNode = SearchNode(_key)) != TableNode::nil) {
    91     newNode = DeleteNode_RB(newNode);
    92     delete(newNode);
     89  TableNode* new_node;
     90  if ((new_node = search_node(_key)) != TableNode::nil) {
     91    new_node = delete_node_RB(new_node);
     92    delete(new_node);
    9393  }
    9494}
    9595
    9696
    97 inline bool Table::Lookup (Expr const& _key, Expr& _val)
     97inline bool Table::lookup (Expr const& _key, Expr& _val)
    9898{   
    99   TableNode *newNode;
    100   if ((newNode = SearchNode(_key)) == TableNode::nil)
     99  TableNode* new_node;
     100  if ((new_node = search_node(_key)) == TableNode::nil)
    101101    return false;   
    102102  else {
    103     _val = newNode->val;
     103    _val = new_node->val;
    104104    return true;
    105105  }
     
    107107
    108108
    109 inline bool Table::InTable (Expr const& _key)
     109inline bool Table::in_table (Expr const& _key)
    110110{
    111   TableNode *newNode;
    112   if ((newNode = SearchNode(_key)) == TableNode::nil)
     111  TableNode* new_node;
     112  if ((new_node = search_node(_key)) == TableNode::nil)
    113113    return false;
    114114  else
     
    119119//
    120120// Table_copy : this - sourceTable, newTable - result
    121 inline void Table::TableCopy (Table& _new_table)
     121inline void Table::table_copy (Table& _new_table)
    122122
    123   TableNode *node;
     123  TableNode* node;
    124124  if (root != TableNode::nil) {
    125125    node = new TableNode;
    126126    node->p = TableNode::nil;       
    127127    _new_table.root = node;   // p - root 
    128     CopyTree(*root, *node);  // p - root
     128    copy_tree(*root, *node);  // p - root
    129129  }
    130130}
     
    133133//
    134134//  ReplaceTable: this - TargetTable
    135 inline void Table::ReplaceTable (Table const& _source_table)   
     135inline void Table::replace_table (Table const& _source_table)   
    136136{   
    137137  TableNode* x;
    138138  if (root != TableNode::nil) {
    139     DeleteTree(root);
     139    delete_tree(root);
    140140    root = TableNode::nil;   
    141141  }
     
    144144    x->p = TableNode::nil;
    145145    root = x;     
    146     CopyTree(*_source_table.root, *root);
     146    copy_tree(*_source_table.root, *root);
    147147  }
    148148}
Note: See TracChangeset for help on using the changeset viewer.