source: to-imperative/trunk/runtime/rf_table.cc @ 1226

Last change on this file since 1226 was 1226, checked in by pooh, 17 years ago
  • Table::insert_node() fixes.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 7.8 KB
Line 
1#include "rf_table.ih"
2#include <new>
3
4namespace rftype
5{
6
7using namespace rfrt; 
8
9TableNode* TableNode::nil = NULL;
10 
11size_t Table::count = 0;
12
13//
14// inserting of element newNode in this-Table
15void Table::insert_node (TableNode* _node)
16{
17  TableNode* x;
18  TableNode* y;
19  int flag;
20  y = TableNode::nil;
21  x = root;
22  while (x != TableNode::nil) {
23    y=x;
24    if ((_node->hash_key) == (x->hash_key)) {
25      flag = Expr::compare(_node->key, x->key);
26      if (!flag) {                      //   case 0 :  ==
27        return;
28      } else if (flag < 0) {            //   case < 0 : <
29        x = x->left;
30      } else {
31        x = x->right;
32      }
33    } else if ((_node->hash_key) < (x->hash_key)) {
34      x = x->left;
35    } else {
36      x = x->right;
37    }
38  }
39  _node->p = y;
40  if (y == TableNode::nil) {
41    root = _node;
42  } else {
43    //
44    // FIXME: Here we already chosen valid direction, so probably we
45    // should introduce a flag indicating that direction to avoid possible
46    // duplicated compare(). [pooh 2003-08-15]
47    if ((_node->hash_key) == (y->hash_key)) {
48      flag = Expr::compare(_node->key, y->key);
49      if (flag < 0) {
50        y->left = _node;
51      } else {
52        y->right = _node;
53      }
54    } else if ((_node->hash_key) < (y->hash_key)) {
55      y->left = _node;
56    } else {
57      y->right = _node;
58    }
59  }
60}
61
62
63void Table::left_rotate_RB (TableNode* _x)
64{ 
65  TableNode* y;
66  y = _x->right;
67  _x->right = y->left;
68  y->left->p = _x;
69  y->p = _x->p;
70  if (_x->p == TableNode::nil)
71    root = y;   
72  else
73    if (_x == _x->p->left)
74      _x->p->left = y;
75    else
76      _x->p->right = y;
77  y->left = _x;
78  _x->p = y;
79}
80
81
82void Table::right_rotate_RB (TableNode* _y)
83{ 
84  TableNode* x;
85  x = _y->left;
86  _y->left = x->right;
87  x->right->p = _y;
88  x->p = _y->p;
89  if (_y->p == TableNode::nil)
90    root = x; 
91  else
92    if (_y == _y->p->right)
93      _y->p->right = x;
94    else
95      _y->p->left = x;
96  x->right = _y;
97  _y->p = x;
98}
99
100
101void Table::insert_node_RB (TableNode* _x)
102{ 
103  TableNode *y;
104  insert_node(_x);
105  _x->color = TableNode::RED;
106  while ((_x != root) && (_x->p->color == TableNode::RED)) {   
107    if (_x->p == _x->p->p->left) {
108      y = _x->p->p->right;
109      if ((y != TableNode::nil) && (y->color == TableNode::RED)) {
110        _x->p->color = TableNode::BLACK;
111        y->color = TableNode::BLACK;
112        _x->p->p->color = TableNode::RED;
113        _x = _x->p->p;
114      } else {
115        if (_x == _x->p->right) {
116          _x = _x->p;
117          left_rotate_RB(_x);
118        }
119        _x->p->color = TableNode::BLACK;
120        _x->p->p->color =TableNode::RED;
121        right_rotate_RB(_x->p->p);
122      }
123    } else {
124      y=_x->p->p->left;
125      if ((y != TableNode::nil) && (y->color == TableNode::RED)) {
126        _x->p->color = TableNode::BLACK;
127        y->color = TableNode::BLACK;
128        _x->p->p->color = TableNode::RED;
129        _x = _x->p->p;
130      } else {
131        if (_x == _x->p->left) {
132          _x = _x->p;
133          right_rotate_RB(_x);
134        }
135        _x->p->color = TableNode::BLACK;
136        _x->p->p->color = TableNode::RED;
137        left_rotate_RB(_x->p->p);
138      }
139    }
140  }
141  root->color=TableNode::BLACK;   
142}
143
144
145TableNode* Table::delete_node_RB (TableNode *_z)
146{ 
147  TableNode* x;
148  TableNode* y;
149  if ((_z->left == TableNode::nil) || (_z->right == TableNode::nil))
150    y = _z;
151  else
152    y = tree_successor(_z);
153  if (y->left != TableNode::nil)
154    x = y->left;
155  else
156    x = y->right;
157  x->p = y->p;
158  if (y->p == TableNode::nil)
159    root = x;     
160  else
161    if (y == y->p->left)
162      y->p->left = x;
163    else
164      y->p->right = x;
165  if (y != _z) {
166    _z->hash_key = y->hash_key;
167    _z->val = y->val;
168    _z->key = y->key;
169  }
170  if (y->color == TableNode::BLACK)
171    delete_fixup_RB(x);
172  return y;
173}
174
175
176void Table::delete_fixup_RB (TableNode* _x)
177{ 
178  TableNode* w;
179  while ((_x != root) && (_x->color == TableNode::BLACK)) {
180    if (_x == _x->p->left) {
181      w = _x->p->right;
182      if (w->color == TableNode::RED) {
183        w->color = TableNode::BLACK;
184        _x->p->color = TableNode::RED;
185        left_rotate_RB(_x->p);
186        w = _x->p->right;
187      }
188      if ((w->left->color == TableNode::BLACK) && (w->right->color == TableNode::BLACK)) {
189        w->color = TableNode::RED;
190        _x = _x->p;
191      } else {
192        if (w->right->color == TableNode::BLACK) {
193          w->left->color = TableNode::BLACK;
194          w->color = TableNode::RED;
195          right_rotate_RB(w);
196          w = _x->p->right;
197        }
198        w->color = _x->p->color;
199        _x->p->color = TableNode::BLACK;
200        w->right->color = TableNode::BLACK;
201        left_rotate_RB(_x->p);
202        _x=root; 
203      }
204    } else {
205      w = _x->p->left;
206      if (w->color == TableNode::RED) {
207        w->color = TableNode::BLACK;
208        _x->p->color = TableNode::RED;
209        right_rotate_RB(_x->p);
210        w = _x->p->left;
211      }
212      if ((w->right->color == TableNode::BLACK) && (w->left->color == TableNode::BLACK)) {
213        w->color = TableNode::RED;
214        _x = _x->p;
215      } else {
216        if (w->left->color == TableNode::BLACK) {
217          w->right->color = TableNode::BLACK;
218          w->color = TableNode::RED;
219          left_rotate_RB(w);
220          w = _x->p->left;
221        }
222        w->color = _x->p->color;
223        _x->p->color = TableNode::BLACK;
224        w->left->color = TableNode::BLACK;
225        right_rotate_RB(_x->p);
226        _x=root; 
227      }
228    }
229  }
230  _x->color=TableNode::BLACK;
231}
232
233
234TableNode* Table::search_node (Expr const& _key)
235{ 
236  TableNode* node;
237  int hash, flag;
238
239  hash = expr_hash(_key);
240  node = root; 
241  while ((node != TableNode::nil) && (node->hash_key != hash)) {
242    if (hash < node->hash_key)
243      node = node->left;
244    else
245      node = node->right;
246  }
247  while ((node != TableNode::nil) && (hash == node->hash_key)) {
248    flag = Expr::compare(_key, node->key);
249    if (!flag)            //   case 0 : ==
250      return (node);
251    if (flag < 0)         //   case < 0 : <
252      node = node->left;
253    else
254      node = node->right;   
255  }
256  return TableNode::nil;
257}
258
259
260void copy_tree (TableNode const&  _tab, TableNode& _copy)
261{   
262  TableNode* child;   
263  _copy.hash_key = _tab.hash_key;
264  _copy.key = _tab.key;
265  _copy.val = _tab.val;
266  _copy.color = _tab.color;
267  if (_tab.left == TableNode::nil)
268    _copy.left = TableNode::nil;
269  else {     
270    child = new TableNode;
271    child->p = &_copy;
272    _copy.left = child;
273    copy_tree(*(_tab.left), *child);
274  }
275  if (_tab.right == TableNode::nil)
276    _copy.right = TableNode::nil;
277  else {     
278    child = new TableNode;
279    child->p = &_copy;
280    _copy.right = child;
281    copy_tree( *(_tab.right), *child);
282  }
283}
284
285bool table_equal(TableNode const& _tab1, TableNode const& _tab2)
286{ 
287  if ((&_tab1) == TableNode::nil) {
288    if ((&_tab2) == TableNode::nil)
289      return true;
290    return false;
291  }
292  else {
293    if ((&_tab2) == TableNode::nil)
294      return false;
295    if ( (_tab1.hash_key == _tab2.hash_key) &&
296      (_tab1.color == _tab2.color) &&
297      (_tab1.key == _tab2.key) &&
298      (_tab1.val == _tab2.val) &&
299      (table_equal(*_tab1.right, *_tab2.right)) &&
300      (table_equal(*_tab1.left, *_tab2.left)) )
301      return true;
302    else 
303      return false; 
304  }
305}
306
307
308void delete_tree (TableNode* _node)
309{   
310  if (_node->left != TableNode::nil)
311    delete_tree(_node->left);
312  if (_node->right != TableNode::nil)
313    delete_tree(_node->right);
314  delete(_node);
315}
316
317
318void list_node (TableNode const& _node, Expr& _res)
319{ 
320  if (_node.left != TableNode::nil)   
321    list_node( * _node.left, _res);
322  if (_node.right != TableNode::nil)
323    list_node( * _node.right, _res);
324  _res = _res + (_node.key)();
325}
326
327
328TableNode*  tree_successor(TableNode* _x)
329{
330  TableNode* y;
331  if (_x->right != TableNode::nil)
332    return tree_minimum(_x->right);
333  y=_x->p;
334  while ((y != TableNode::nil) && (_x == y->right)) {
335    _x = y;
336    y = y->p;
337  }
338  return y;
339}
340
341
342TableNode* tree_minimum (TableNode* _x)
343{
344  while (_x->left != TableNode::nil)
345    _x = _x->left;
346  return _x;
347}
348
349
350}
Note: See TracBrowser for help on using the repository browser.