gcclibs/libmudflap/mf-runtime.c

126 static void mfsplay_tree_rebalance (mfsplay_tree sp);
2313 mfsplay_tree_splay_helper (mfsplay_tree sp,
2344       if (sp->depth > sp->max_depth)
2346           sp->rebalance_p = 1;
2351       sp->depth ++;
2352       n = mfsplay_tree_splay_helper (sp, key, next, node, parent);
2353       sp->depth --;
2357       if (*node != n || sp->rebalance_p)
2468 mfsplay_tree_rebalance (mfsplay_tree sp)
2472   if (sp->num_keys <= 2)
2475   all_nodes = mfsplay_tree_xmalloc (sizeof (mfsplay_tree_node) * sp->num_keys);
2479   mfsplay_tree_foreach (sp, mfsplay_tree_rebalance_helper1,
2483   sp->root = mfsplay_tree_rebalance_helper2 (all_nodes, 0, sp->num_keys - 1);
2491 mfsplay_tree_splay (mfsplay_tree sp, mfsplay_tree_key key)
2493   if (sp->root == 0)
2497   if (sp->last_splayed_key_p &&
2498       (sp->last_splayed_key == key))
2510   sp->max_depth = 2500;
2511   sp->rebalance_p = sp->depth = 0;
2513   mfsplay_tree_splay_helper (sp, key, &sp->root, NULL, NULL);
2514   if (sp->rebalance_p)
2516       mfsplay_tree_rebalance (sp);
2518       sp->rebalance_p = sp->depth = 0;
2519       mfsplay_tree_splay_helper (sp, key, &sp->root, NULL, NULL);
2521       if (sp->rebalance_p)
2527   sp->last_splayed_key = key;
2528   sp->last_splayed_key_p = 1;
2537   mfsplay_tree sp = mfsplay_tree_xmalloc (sizeof (struct mfsplay_tree_s));
2538   sp->root = NULL;
2539   sp->last_splayed_key_p = 0;
2540   sp->num_keys = 0;
2542   return sp;
2551 mfsplay_tree_insert (mfsplay_tree sp, mfsplay_tree_key key, mfsplay_tree_value value)
2555   mfsplay_tree_splay (sp, key);
2557   if (sp->root)
2558     comparison = ((sp->root->key > key) ? 1 :
2559                   ((sp->root->key < key) ? -1 : 0));
2561   if (sp->root && comparison == 0)
2565       sp->root->value = value;
2575       sp->num_keys++;
2576       if (!sp->root)
2580           node->left = sp->root;
2586           node->right = sp->root;
2591       sp->root = node;
2592       sp->last_splayed_key_p = 0;
2595   return sp->root;
2601 mfsplay_tree_remove (mfsplay_tree sp, mfsplay_tree_key key)
2603   mfsplay_tree_splay (sp, key);
2604   sp->last_splayed_key_p = 0;
2605   if (sp->root && (sp->root->key == key))
2608       left = sp->root->left;
2609       right = sp->root->right;
2611       mfsplay_tree_free (sp->root);
2612       sp->num_keys--;
2617           sp->root = left;
2628         sp->root = right;
2636 mfsplay_tree_lookup (mfsplay_tree sp, mfsplay_tree_key key)
2638   mfsplay_tree_splay (sp, key);
2639   if (sp->root && (sp->root->key == key))
2640     return sp->root;
2650 mfsplay_tree_predecessor (mfsplay_tree sp, mfsplay_tree_key key)
2655   if (!sp->root)
2659   mfsplay_tree_splay (sp, key);
2660   comparison = ((sp->root->key > key) ? 1 :
2661                 ((sp->root->key < key) ? -1 : 0));
2665     return sp->root;
2667   node = sp->root->left;
2678 mfsplay_tree_successor (mfsplay_tree sp, mfsplay_tree_key key)
2683   if (!sp->root)
2687   mfsplay_tree_splay (sp, key);
2688   comparison = ((sp->root->key > key) ? 1 :
2689                 ((sp->root->key < key) ? -1 : 0));
2692     return sp->root;
2694   node = sp->root->right;
2715   unsigned sp;
2725   sp = 0;
2726   stack1 [sp] = st->root;
2727   stack2 [sp] = s_left;
2734       n = stack1 [sp];
2735       s = stack2 [sp];
2742           stack2 [sp] = s_here;
2745               sp ++;
2746               stack1 [sp] = n->left;
2747               stack2 [sp] = s_left;
2754           stack2 [sp] = s_right;
2762           stack2 [sp] = s_up;
2765               sp ++;
2766               stack1 [sp] = n->right;
2767               stack2 [sp] = s_left;
2775           if (sp == 0) break; /* Popping off the root note: we're finished!  */
2776           sp --;