src/avltree.c
static int
avltree_rotate(struct avltree *tree, struct avltree_node *node, int balance)
{
    struct avltree_node *parent, *lnode, *lrnode, *lrlnode, *lrrnode;
    int left, right, lweight, rweight, lbalance;
    int index = 0; /* GCC */

    assert((balance == -2) || (balance == 2));

    left = avltree_d2i(balance);
    right = 1 - left;
    lweight = balance >> 1;
    rweight = -lweight;

    parent = avltree_node_parent(node);

    if (likely(parent != NULL)) {
        index = avltree_node_index(node, parent);
    }

    lnode = node->children[left];
    assert(lnode != NULL);
    lbalance = avltree_node_balance(lnode);
    lrnode = lnode->children[right];

    /*
     * Left-left case. Note that only a removal can set the left node balance
     * to 0 when rotating.
     */
    if (lbalance != rweight) {
        node->children[left] = lrnode;

        if (lrnode != NULL) {
            avltree_node_set_parent(lrnode, node);
        }

        lbalance += rweight;

        lnode->children[right] = node;

        avltree_node_set_parent(node, lnode);
        avltree_node_set_balance(node, -lbalance);

        avltree_node_set_parent(lnode, parent);
        avltree_node_set_balance(lnode, lbalance);

        if (unlikely(parent == NULL)) {
            tree->root = lnode;
        } else {
            parent->children[index] = lnode;
        }

        /*
         * If the adjusted balance is now 0, it means that the height of the
         * left subtree has decreased.
         */
        return (lbalance == 0);
    }

    /*
     * Left-right case.
     */

    assert(lrnode != NULL);
    lrlnode = lrnode->children[left];
    lrrnode = lrnode->children[right];

    node->children[left] = lrrnode;

    if (lrrnode != NULL) {
        avltree_node_set_parent(lrrnode, node);
    }

    lnode->children[right] = lrlnode;

    if (lrlnode != NULL) {
        avltree_node_set_parent(lrlnode, lnode);
    }

    balance = avltree_node_balance(lrnode);

    lrnode->children[left] = lnode;
    avltree_node_set_parent(lnode, lrnode);
    avltree_node_set_balance(lnode, ((balance == rweight) ? lweight : 0));

    lrnode->children[right] = node;
    avltree_node_set_parent(node, lrnode);
    avltree_node_set_balance(node, ((balance == lweight) ? rweight : 0));

    avltree_node_set_parent(lrnode, parent);
    avltree_node_set_balance(lrnode, 0);

    if (unlikely(parent == NULL)) {
        tree->root = lrnode;
    } else {
        parent->children[index] = lrnode;
    }

    /*
     * The balance of the new subtree root is always 0 in this case, which
     * implies the overall subtree height has decreased.
     */
    return 1;
}
/*
 * Rotate an unbalanced tree.
 *
 * This function is called after the insertion or the removal of a node made
 * a tree unbalanced. The node and balance parameters define the rotation root
 * (the balance being either -2 or 2).
 *
 * Return true if the overall height of the subtree rooted at node has
 * decreased, false otherwise.
 */
Rotate an unbalanced tree.
This function is called after the insertion or the removal of a node made
a tree unbalanced. The node and balance parameters define the rotation root
(the balance being either -2 or 2).

Return true if the overall height of the subtree rooted at node has
decreased, false otherwise.
Rotate an unbalanced tree . This function is called after the insertion or the removal of a node made a tree unbalanced . The node and balance parameters define the rotation root ( the balance being either - 2 or 2 ) . Return true if the overall height of the subtree rooted at node has decreased false otherwise .
static int
avltree_rotate(struct avltree *tree, struct avltree_node *node, int balance)
{
    struct avltree_node *parent, *lnode, *lrnode, *lrlnode, *lrrnode;
    int left, right, lweight, rweight, lbalance;
    int index = 0; 
    assert((balance == -2) || (balance == 2));
    left = avltree_d2i(balance);
    right = 1 - left;
    lweight = balance >> 1;
    rweight = -lweight;
    parent = avltree_node_parent(node);
    if (likely(parent != NULL)) {
        index = avltree_node_index(node, parent);
    }
    lnode = node->children[left];
    assert(lnode != NULL);
    lbalance = avltree_node_balance(lnode);
    lrnode = lnode->children[right];
    if (lbalance != rweight) {
        node->children[left] = lrnode;
        if (lrnode != NULL) {
            avltree_node_set_parent(lrnode, node);
        }
        lbalance += rweight;
        lnode->children[right] = node;
        avltree_node_set_parent(node, lnode);
        avltree_node_set_balance(node, -lbalance);
        avltree_node_set_parent(lnode, parent);
        avltree_node_set_balance(lnode, lbalance);
        if (unlikely(parent == NULL)) {
            tree->root = lnode;
        } else {
            parent->children[index] = lnode;
        }
        return (lbalance == 0);
    }
    assert(lrnode != NULL);
    lrlnode = lrnode->children[left];
    lrrnode = lrnode->children[right];
    node->children[left] = lrrnode;
    if (lrrnode != NULL) {
        avltree_node_set_parent(lrrnode, node);
    }
    lnode->children[right] = lrlnode;
    if (lrlnode != NULL) {
        avltree_node_set_parent(lrlnode, lnode);
    }
    balance = avltree_node_balance(lrnode);
    lrnode->children[left] = lnode;
    avltree_node_set_parent(lnode, lrnode);
    avltree_node_set_balance(lnode, ((balance == rweight) ? lweight : 0));
    lrnode->children[right] = node;
    avltree_node_set_parent(node, lrnode);
    avltree_node_set_balance(node, ((balance == lweight) ? rweight : 0));
    avltree_node_set_parent(lrnode, parent);
    avltree_node_set_balance(lrnode, 0);
    if (unlikely(parent == NULL)) {
        tree->root = lrnode;
    } else {
        parent->children[index] = lrnode;
    }
    return 1;
}
static int avltree_rotate ( struct avltree * tree , struct avltree_node * node , int balance ) { struct avltree_node * parent , * lnode , * lrnode , * lrlnode , * lrrnode ; int left , right , lweight , rweight , lbalance ; int index = 0 ; assert ( ( balance == -2 ) || ( balance == 2 ) ) ; left = avltree_d2i ( balance ) ; right = 1 - left ; lweight = balance >> 1 ; rweight = - lweight ; parent = avltree_node_parent ( node ) ; if ( likely ( parent != NULL ) ) { index = avltree_node_index ( node , parent ) ; } lnode = node -> children [ left ] ; assert ( lnode != NULL ) ; lbalance = avltree_node_balance ( lnode ) ; lrnode = lnode -> children [ right ] ; if ( lbalance != rweight ) { node -> children [ left ] = lrnode ; if ( lrnode != NULL ) { avltree_node_set_parent ( lrnode , node ) ; } lbalance += rweight ; lnode -> children [ right ] = node ; avltree_node_set_parent ( node , lnode ) ; avltree_node_set_balance ( node , - lbalance ) ; avltree_node_set_parent ( lnode , parent ) ; avltree_node_set_balance ( lnode , lbalance ) ; if ( unlikely ( parent == NULL ) ) { tree -> root = lnode ; } else { parent -> children [ index ] = lnode ; } return ( lbalance == 0 ) ; } assert ( lrnode != NULL ) ; lrlnode = lrnode -> children [ left ] ; lrrnode = lrnode -> children [ right ] ; node -> children [ left ] = lrrnode ; if ( lrrnode != NULL ) { avltree_node_set_parent ( lrrnode , node ) ; } lnode -> children [ right ] = lrlnode ; if ( lrlnode != NULL ) { avltree_node_set_parent ( lrlnode , lnode ) ; } balance = avltree_node_balance ( lrnode ) ; lrnode -> children [ left ] = lnode ; avltree_node_set_parent ( lnode , lrnode ) ; avltree_node_set_balance ( lnode , ( ( balance == rweight ) ? lweight : 0 ) ) ; lrnode -> children [ right ] = node ; avltree_node_set_parent ( node , lrnode ) ; avltree_node_set_balance ( node , ( ( balance == lweight ) ? rweight : 0 ) ) ; avltree_node_set_parent ( lrnode , parent ) ; avltree_node_set_balance ( lrnode , 0 ) ; if ( unlikely ( parent == NULL ) ) { tree -> root = lrnode ; } else { parent -> children [ index ] = lrnode ; } return 1 ; }
Rotate an unbalanced tree.
Rotate an unbalanced tree .
/* GCC */ /*
     * Left-left case. Note that only a removal can set the left node balance
     * to 0 when rotating.
     */ /*
         * If the adjusted balance is now 0, it means that the height of the
         * left subtree has decreased.
         */ /*
     * Left-right case.
     */ /*
     * The balance of the new subtree root is always 0 in this case, which
     * implies the overall subtree height has decreased.
     */