Sierra Toolkit  Version of the Day
Mapv.cpp
1 
10 // ---------------------------------------------------------------------
11 // Author: H. Carter Edwards
12 //
13 // Purpose: Associative container for allocated data objects
14 // ---------------------------------------------------------------------
15 // Acknowledgements:
16 //
17 // Most all of the algorithms in this class were obtained from
18 // the Hewlett-Packard source for the Standard Template Library,
19 // thus the inclusion of Hewlett-Packard's copyright notice.
20 // Some minor modifications were obtained from Silicon Graphics'
21 // Standard Template Library source.
22 // ---------------------------------------------------------------------
23 /*
24  * Copyright (c) 1996,1997
25  * Silicon Graphics Computer Systems, Inc.
26  *
27  * Permission to use, copy, modify, distribute and sell this software
28  * and its documentation for any purpose is hereby granted without fee,
29  * provided that the above copyright notice appear in all copies and
30  * that both that copyright notice and this permission notice appear
31  * in supporting documentation. Silicon Graphics makes no
32  * representations about the suitability of this software for any
33  * purpose. It is provided "as is" without express or implied warranty.
34  *
35  *
36  * Copyright (c) 1994
37  * Hewlett-Packard Company
38  *
39  * Permission to use, copy, modify, distribute and sell this software
40  * and its documentation for any purpose is hereby granted without fee,
41  * provided that the above copyright notice appear in all copies and
42  * that both that copyright notice and this permission notice appear
43  * in supporting documentation. Hewlett-Packard Company makes no
44  * representations about the suitability of this software for any
45  * purpose. It is provided "as is" without express or implied warranty.
46  *
47  */
48 /*
49 Red-black tree class, designed for use in implementing STL
50 associative containers (set, multiset, map, and multimap). The
51 insertion and deletion algorithms are based on those in Cormen,
52 Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
53 except that
54 
55 (1) the header cell is maintained with links not only to the root
56 but also to the leftmost node of the tree, to enable constant time
57 begin(), and to the rightmost node of the tree, to enable linear time
58 performance when used with the generic set algorithms (set_union,
59 etc.);
60 
61 (2) when a node being deleted has two children its successor node is
62 relinked into its place, rather than copied, so that the only
63 iterators invalidated are those referring to the deleted node.
64 */
65 // ---------------------------------------------------------------------
66 
67 // The header
68 
69 #include <stk_util/diag/Mapv.hpp>
70 
71 #include <stdexcept>
72 #if defined(SIERRA_IA64_OPTIMIZER_WARN)
73 #include <stk_util/diag/Env.hpp>
74 #endif
75 #include <string>
76 
77 namespace sierra {
78 
79 // ---------------------------------------------------------------------
80 
81 inline
82 MapvNodeBase * MapvBase::minimum( MapvNodeBase * x )
83  { while ( x->left ) x = x->left ; return x ; }
84 
85 inline
86 MapvNodeBase * MapvBase::maximum( MapvNodeBase * x )
87  { while ( x->right ) x = x->right ; return x ; }
88 
89 // ---------------------------------------------------------------------
90 
91 inline void MapvBase::rotate_left( MapvNodeBase * x )
92 {
93  MapvNodeBase * y = x->right ;
94 
95  x->right = y->left ;
96  if ( y->left ) y->left->parent = x ;
97  y->parent = x->parent ;
98 
99  if ( x == nRoot() ) root(y);
100  else if ( x == x->parent->left ) x->parent->left = y ;
101  else x->parent->right = y ;
102 
103  y->left = x ;
104  x->parent = y ;
105 }
106 
107 inline void MapvBase::rotate_right( MapvNodeBase * x )
108 {
109  MapvNodeBase * y = x->left ;
110 
111  x->left = y->right ;
112  if ( y->right ) y->right->parent = x;
113  y->parent = x->parent ;
114 
115  if ( x == nRoot() ) root(y);
116  else if ( x == x->parent->right ) x->parent->right = y ;
117  else x->parent->left = y ;
118 
119  y->right = x;
120  x->parent = y;
121 }
122 
123 // ---------------------------------------------------------------------
124 
125 void MapvBase::insert( MapvNodeBase * y , MapvNodeBase * z , bool z_lt_y )
126 {
127  z->remove_from_container();
128 
129  if ( y == nEnd() ) { // First node inserted
130  root(z);
131  leftmost(z);
132  rightmost(z);
133  z->parent = header() ; // header is 'super-root'
134  }
135  else {
136  if ( z_lt_y ) {
137  y->left = z ;
138  // maintain leftmost() pointing to minimum node
139  if ( y == leftmost() ) leftmost(z);
140  }
141  else {
142  y->right = z;
143  // maintain rightmost() pointing to maximum node
144  if ( y == rightmost() ) rightmost(z);
145  }
146  z->parent = y ;
147  }
148  z->left = 0 ;
149  z->right = 0 ;
150  z->color = red ;
151  ++Count ;
152 
153  // -------------------------------------------------------------------
154  // Rebalance, 'y' and 'z' are reused as a local variable
155 
156  while ( z != nRoot() && z->parent->color == red ) {
157  if ( z->parent == z->parent->parent->left ) {
158  y = z->parent->parent->right ;
159  if ( y && y->color == red ) {
160  z->parent->color = black;
161  y->color = black;
162  z->parent->parent->color = red;
163  z = z->parent->parent ;
164  }
165  else {
166  if ( z == z->parent->right ) {
167  z = z->parent ;
168  rotate_left(z);
169  }
170  z->parent->color = black;
171  z->parent->parent->color = red;
172  rotate_right( z->parent->parent );
173  }
174  }
175  else {
176  y = z->parent->parent->left ;
177  if ( y && y->color == red ) {
178  z->parent->color = black;
179  y->color = black;
180  z->parent->parent->color = red;
181  z = z->parent->parent ;
182  }
183  else {
184  if ( z == z->parent->left ) {
185  z = z->parent ;
186  rotate_right(z);
187  }
188  z->parent->color = black;
189  z->parent->parent->color = red;
190  rotate_left(z->parent->parent);
191  }
192  }
193  }
194  nRoot()->color = black;
195 }
196 
197 // ---------------------------------------------------------------------
198 
199 void MapvBase::remove( MapvNodeBase * node )
200 {
201  static const char method_name[] = "MapvBase::remove" ;
202 
203  if ( container(node) != this ) {
204  std::string msg(method_name);
205  msg.append(" given object not in this container");
206  throw std::invalid_argument( msg );
207  }
208 
209  if ( 1 == Count ) { // The last node ?
210 
211  if ( node != leftmost() || node != rightmost() || node != nRoot() ) {
212  std::string msg(method_name);
213  msg.append(" internal data structure corrupted" );
214  throw std::runtime_error( msg );
215  }
216 
217  leftmost( nREnd() );
218  rightmost( nEnd() );
219  root(0);
220  Count = 0 ;
221  header()->color = red ;
222  node->left = node->right = node->parent = 0 ; node->color = 0 ;
223  return ;
224  }
225 
226  MapvNodeBase * z = node ;
227  MapvNodeBase * y = node ;
228  MapvNodeBase * x = 0 ;
229  MapvNodeBase * x_parent = 0 ;
230 
231  // Ready to remove
232 
233  if ( y->left == 0 ) { // z has at most one non-null child. y == z
234  x = y->right ; // x might be null
235  }
236  else if ( y->right == 0 ) { // z has exactly one non-null child. y == z
237  x = y->left ; // z is not null
238  }
239  else { // z has two non-null children.
240  y = y->right ; // Set y to z's successor.
241  while ( y->left ) y = y->left ;
242  x = y->right ; // x might be null
243  }
244 
245  if ( y != z ) { // relink y in place of z. y is z's successor
246  z->left->parent = y ;
247  y->left = z->left ;
248  if ( y != z->right ) {
249  x_parent = y->parent ;
250  if ( x ) x->parent = x_parent ;
251  y->parent->left = x; // y must be a left child
252  y->right = z->right;
253  z->right->parent = y;
254  } else {
255  x_parent = y; // needed in case x == 0
256  }
257  if ( nRoot() == z) {
258  root(y);
259  }
260  else if ( z->parent->left == z) {
261  z->parent->left = y;
262  }
263  else {
264  z->parent->right = y;
265  }
266  y->parent = z->parent;
267  { int c = y->color; y->color = z->color; z->color = c ; }
268  y = z;
269  // y points to node to be actually deleted
270  }
271  else { // y == z
272  x_parent = y->parent ;
273  if ( x ) x->parent = x_parent ; // possibly x == 0
274  if ( nRoot() == z) {
275  root(x);
276  }
277  else if ( z->parent->left == z ) {
278  z->parent->left = x;
279  }
280  else {
281  z->parent->right = x;
282  }
283  if ( leftmost() == z ) {
284  if ( z->right == 0 ) { // z->left must be null also
285  // makes leftmost() == nEnd() if z == nRoot()
286  leftmost( z->parent );
287  }
288  else {
289  leftmost( minimum(x) );
290  }
291  }
292  if ( rightmost() == z ) {
293  if ( z->left == 0 ) { // z->right must be null also
294  // makes rightmost() == nEnd() if z == nRoot()
295  rightmost( z->parent );
296  }
297  else { // x == z->left
298  rightmost( maximum(x) );
299  }
300  }
301  }
302  if ( y->color != red ) {
303  while ( x != nRoot() && ( x == 0 || x->color == black ) ) {
304  if ( x == x_parent->left ) {
305  MapvNodeBase * w = x_parent->right ;
306  if ( w->color == red ) {
307  w->color = black;
308  x_parent->color = red;
309  rotate_left(x_parent);
310  w = x_parent->right ;
311  }
312  if ((w->left == 0 || w->left->color == black) &&
313  (w->right == 0 || w->right->color == black)) {
314  w->color = red ;
315  x = x_parent ;
316  x_parent = x_parent->parent ;
317  }
318  else {
319  if (w->right == 0 || w->right->color == black) {
320  if ( w->left ) w->left->color = black;
321  w->color = red;
322  rotate_right(w);
323  w = x_parent->right ;
324  }
325  w->color = x_parent->color ;
326  x_parent->color = black;
327  if ( w->right ) w->right->color = black;
328  rotate_left(x_parent);
329  break;
330  }
331  }
332  else { // same as then clause with "right" and "left" exchanged
333  MapvNodeBase * w = x_parent->left ;
334  if ( w->color == red ) {
335  w->color = black;
336  x_parent->color = red;
337  rotate_right(x_parent);
338  w = x_parent->left ;
339  }
340  if ((w->right == 0 || w->right->color == black) &&
341  (w->left == 0 || w->left->color == black)) {
342  w->color = red;
343  x = x_parent ;
344  x_parent = x_parent->parent ;
345  }
346  else {
347  if ( w->left == 0 || w->left->color == black ) {
348  if ( w->right ) w->right->color = black;
349  w->color = red;
350  rotate_left(w);
351  w = x_parent->left ;
352  }
353  w->color = x_parent->color ;
354  x_parent->color = black;
355  if ( w->left ) w->left->color = black;
356  rotate_right(x_parent);
357  break;
358  }
359  }
360  }
361  if ( x ) x->color = black;
362  }
363 
364  y->left = y->right = y->parent = 0 ; y->color = 0 ;
365 
366  --Count ; // Decrement the tree's count
367 }
368 
369 // ---------------------------------------------------------------------
370 // A reverse communicating method for deleting all entries
371 
372 MapvNodeBase * MapvBase::unbalancing_removal( MapvNodeBase ** n )
373 {
374  MapvNodeBase * t = *n ;
375 
376  while ( t != header() && t->parent ) {
377  if ( t->left ) { t = t->left ; }
378  else if ( t->right ) { t = t->right ; }
379  else { // Move to parent and remove this leaf
380  *n = t->parent ; t->parent = 0 ;
381  if ( (*n)->left == t ) (*n)->left = 0 ;
382  else (*n)->right = 0 ;
383  }
384  }
385 
386  if ( t == header() ) {
387 
388  header()->parent = 0 ;
389  header()->left = 0 ;
390  header()->right = 0 ;
391  header()->color = red ; /* Color the header node red */
392 
393  Count = 0 ;
394 
395  left_end.parent = 0 ;
396  left_end.left = 0 ;
397  left_end.right = 0 ;
398  left_end.color = black ;
399 
400  right_end.parent = 0 ;
401  right_end.left = 0 ;
402  right_end.right = 0 ;
403  right_end.color = black ;
404 
405  leftmost( header()->left = nREnd() ); // left end of the tree
406  rightmost( header()->right = nEnd() ); // right end of the tree
407 
408  t = 0 ;
409  }
410 
411  return t ;
412 }
413 
414 // ---------------------------------------------------------------------
415 void MapvBase::WarnOptimize()
416 {
417 #if defined(SIERRA_IA64_OPTIMIZER_WARN) && defined(NDEBUG)
418  static bool warn_once=true;
419  int my_proc=Env::parallel_rank();
420 
421  if ( warn_once && my_proc==0){
422  warn_once = false;
423  std::cerr << "Optimizing previous versions of the intel compiler "
424  << "caused errors in Mapv.\n"
425  << "Results may be suspect.\n";
426  }
427 #endif
428 }
429 
430 // ---------------------------------------------------------------------
431 // Virtual destructor
432 
433 MapvBase::~MapvBase()
434 {
435  if ( Count || nRoot() != 0 ) {
436  std::string msg("MapvBase destructor, container is not empty");
437  throw std::logic_error( msg );
438  }
439 }
440 
441 }
Definition: Env.cpp:53
int parallel_rank()
function parallel_rank returns the rank of this processor in the current mpi communicator.
Definition: Env.cpp:318