Lines Matching defs:sp
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 --;