69 #include <stk_util/diag/Mapv.hpp> 72 #if defined(SIERRA_IA64_OPTIMIZER_WARN) 73 #include <stk_util/diag/Env.hpp> 82 MapvNodeBase * MapvBase::minimum( MapvNodeBase * x )
83 {
while ( x->left ) x = x->left ;
return x ; }
86 MapvNodeBase * MapvBase::maximum( MapvNodeBase * x )
87 {
while ( x->right ) x = x->right ;
return x ; }
91 inline void MapvBase::rotate_left( MapvNodeBase * x )
93 MapvNodeBase * y = x->right ;
96 if ( y->left ) y->left->parent = x ;
97 y->parent = x->parent ;
99 if ( x == nRoot() ) root(y);
100 else if ( x == x->parent->left ) x->parent->left = y ;
101 else x->parent->right = y ;
107 inline void MapvBase::rotate_right( MapvNodeBase * x )
109 MapvNodeBase * y = x->left ;
112 if ( y->right ) y->right->parent = x;
113 y->parent = x->parent ;
115 if ( x == nRoot() ) root(y);
116 else if ( x == x->parent->right ) x->parent->right = y ;
117 else x->parent->left = y ;
125 void MapvBase::insert( MapvNodeBase * y , MapvNodeBase * z ,
bool z_lt_y )
127 z->remove_from_container();
133 z->parent = header() ;
139 if ( y == leftmost() ) leftmost(z);
144 if ( y == rightmost() ) rightmost(z);
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;
162 z->parent->parent->color = red;
163 z = z->parent->parent ;
166 if ( z == z->parent->right ) {
170 z->parent->color = black;
171 z->parent->parent->color = red;
172 rotate_right( z->parent->parent );
176 y = z->parent->parent->left ;
177 if ( y && y->color == red ) {
178 z->parent->color = black;
180 z->parent->parent->color = red;
181 z = z->parent->parent ;
184 if ( z == z->parent->left ) {
188 z->parent->color = black;
189 z->parent->parent->color = red;
190 rotate_left(z->parent->parent);
194 nRoot()->color = black;
199 void MapvBase::remove( MapvNodeBase * node )
201 static const char method_name[] =
"MapvBase::remove" ;
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 );
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 );
221 header()->color = red ;
222 node->left = node->right = node->parent = 0 ; node->color = 0 ;
226 MapvNodeBase * z = node ;
227 MapvNodeBase * y = node ;
228 MapvNodeBase * x = 0 ;
229 MapvNodeBase * x_parent = 0 ;
233 if ( y->left == 0 ) {
236 else if ( y->right == 0 ) {
241 while ( y->left ) y = y->left ;
246 z->left->parent = y ;
248 if ( y != z->right ) {
249 x_parent = y->parent ;
250 if ( x ) x->parent = x_parent ;
253 z->right->parent = y;
260 else if ( z->parent->left == z) {
264 z->parent->right = y;
266 y->parent = z->parent;
267 {
int c = y->color; y->color = z->color; z->color = c ; }
272 x_parent = y->parent ;
273 if ( x ) x->parent = x_parent ;
277 else if ( z->parent->left == z ) {
281 z->parent->right = x;
283 if ( leftmost() == z ) {
284 if ( z->right == 0 ) {
286 leftmost( z->parent );
289 leftmost( minimum(x) );
292 if ( rightmost() == z ) {
293 if ( z->left == 0 ) {
295 rightmost( z->parent );
298 rightmost( maximum(x) );
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 ) {
308 x_parent->color = red;
309 rotate_left(x_parent);
310 w = x_parent->right ;
312 if ((w->left == 0 || w->left->color == black) &&
313 (w->right == 0 || w->right->color == black)) {
316 x_parent = x_parent->parent ;
319 if (w->right == 0 || w->right->color == black) {
320 if ( w->left ) w->left->color = black;
323 w = x_parent->right ;
325 w->color = x_parent->color ;
326 x_parent->color = black;
327 if ( w->right ) w->right->color = black;
328 rotate_left(x_parent);
333 MapvNodeBase * w = x_parent->left ;
334 if ( w->color == red ) {
336 x_parent->color = red;
337 rotate_right(x_parent);
340 if ((w->right == 0 || w->right->color == black) &&
341 (w->left == 0 || w->left->color == black)) {
344 x_parent = x_parent->parent ;
347 if ( w->left == 0 || w->left->color == black ) {
348 if ( w->right ) w->right->color = black;
353 w->color = x_parent->color ;
354 x_parent->color = black;
355 if ( w->left ) w->left->color = black;
356 rotate_right(x_parent);
361 if ( x ) x->color = black;
364 y->left = y->right = y->parent = 0 ; y->color = 0 ;
372 MapvNodeBase * MapvBase::unbalancing_removal( MapvNodeBase ** n )
374 MapvNodeBase * t = *n ;
376 while ( t != header() && t->parent ) {
377 if ( t->left ) { t = t->left ; }
378 else if ( t->right ) { t = t->right ; }
380 *n = t->parent ; t->parent = 0 ;
381 if ( (*n)->left == t ) (*n)->left = 0 ;
382 else (*n)->right = 0 ;
386 if ( t == header() ) {
388 header()->parent = 0 ;
390 header()->right = 0 ;
391 header()->color = red ;
395 left_end.parent = 0 ;
398 left_end.color = black ;
400 right_end.parent = 0 ;
402 right_end.right = 0 ;
403 right_end.color = black ;
405 leftmost( header()->left = nREnd() );
406 rightmost( header()->right = nEnd() );
415 void MapvBase::WarnOptimize()
417 #if defined(SIERRA_IA64_OPTIMIZER_WARN) && defined(NDEBUG) 418 static bool warn_once=
true;
421 if ( warn_once && my_proc==0){
423 std::cerr <<
"Optimizing previous versions of the intel compiler " 424 <<
"caused errors in Mapv.\n" 425 <<
"Results may be suspect.\n";
433 MapvBase::~MapvBase()
435 if ( Count || nRoot() != 0 ) {
436 std::string msg(
"MapvBase destructor, container is not empty");
437 throw std::logic_error( msg );
int parallel_rank()
function parallel_rank returns the rank of this processor in the current mpi communicator.