Miscellany

void
mowgli_dictionary_retune(mowgli_dictionary_t *dict, const char *key)
{
        mowgli_dictionary_elem_t n, *tn, *left, *right, *node;
        int ret;

        return_if_fail(dict != NULL);

        /*
         * we initialize n with known values, since it's on stack
         * memory. otherwise the dict would become corrupted.
         *
         * n is used for temporary storage while the tree is retuned.
         *    -nenolod
         */
        n.left = n.right = NULL;
        left = right = &n;

        /* this for(;;) loop is the main workhorse of the rebalancing */
        for (node = dict->root; ; )
        {
                if ((ret = dict->compare_cb(key, node->key)) == 0)
                        break;

                if (ret < 0)
                {
                        if (node->left == NULL)
                                break;

                        if ((ret = dict->compare_cb(key, node->left->key)) < 0)
                        {
                                tn = node->left;
                                node->left = tn->right;
                                tn->right = node;
                                node = tn;

                                if (node->left == NULL)
                                        break;
                        }

                        right->left = node;
                        right = node;
                        node = node->left;
                }
                else
                {
                        if (node->right == NULL)
                                break;

                        if ((ret = dict->compare_cb(key, node->right->key)) > 0)
                        {
                                tn = node->right;
                                node->right = tn->left;
                                tn->left = node;
                                node = tn;

                                if (node->right == NULL)
                                        break;
                        }

                        left->right = node;
                        left = node;
                        node = node->right;
                }
        }

        left->right = node->left;
        right->left = node->right;

        node->left = n.right;
        node->right = n.left;

        dict->root = node;
}