source: mainline/uspace/lib/c/generic/adt/odict.c@ ab6edb6

/*
 * Copyright (c) 2016 Jiri Svoboda
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/** @addtogroup libc
 * @{
 */

/** @file Ordered dictionary.
 *
 * Implementation based on red-black trees.
 * Note that non-data ('leaf') nodes are implemented as NULLs, not
 * as actual nodes.
 */

#include <adt/list.h>
#include <adt/odict.h>
#include <assert.h>
#include <errno.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

static void odict_pgu(odlink_t *, odlink_t **, odict_child_sel_t *,
    odlink_t **, odict_child_sel_t *, odlink_t **);

static void odict_rotate_left(odlink_t *);
static void odict_rotate_right(odlink_t *);
static void odict_swap_node(odlink_t *, odlink_t *);
static void odict_replace_subtree(odlink_t *, odlink_t *);
static void odict_unlink(odlink_t *);
static void odict_link_child_a(odlink_t *, odlink_t *);
static void odict_link_child_b(odlink_t *, odlink_t *);
static void odict_sibling(odlink_t *, odlink_t *, odict_child_sel_t *,
    odlink_t **);
static odlink_t *odict_search_start_node(odict_t *, void *, odlink_t *);

/** Print subtree.
 *
 * Print subtree rooted at @a cur
 *
 * @param cur Root of tree to print
 */
static void odict_print_tree(odlink_t *cur)
{
        if (cur == NULL) {
                printf("0");
                return;
        }

        printf("[%p/%c", cur, cur->color == odc_red ? 'r' : 'b');
        if (cur->a != NULL || cur->b != NULL) {
                putchar(' ');
                odict_print_tree(cur->a);
                putchar(',');
                odict_print_tree(cur->b);
        }
        putchar(']');
}

/** Validate ordered dictionary subtree.
 *
 * Verify that red-black tree properties are satisfied.
 *
 * @param cur Root of tree to verify
 * @param rbd Place to store black depth of the subtree
 *
 * @return EOK on success, EINVAL on failure
 */
static errno_t odict_validate_tree(odlink_t *cur, int *rbd)
{
        errno_t rc;
        int bd_a, bd_b;
        int cur_d;

        if (cur->up == NULL) {
                /* Verify root pointer */
                if (cur->odict->root != cur) {
                        printf("cur->up == NULL and yet cur != root\n");
                        return EINVAL;
                }

                /* Verify root color */
                if (cur->color != odc_black) {
                        printf("Root is not black\n");
                        return EINVAL;
                }
        }

        if (cur->a != NULL) {
                /* Verify symmetry of a - up links */
                if (cur->a->up != cur) {
                        printf("cur->a->up != cur\n");
                        return EINVAL;
                }

                /* Verify that if a node is red, its left child is red */
                if (cur->a->color == odc_red && cur->color == odc_red) {
                        printf("cur->a is red, cur is red\n");
                        return EINVAL;
                }

                /* Recurse to left child */
                rc = odict_validate_tree(cur->a, &bd_a);
                if (rc != EOK)
                        return rc;
        } else {
                bd_a = -1;
        }

        if (cur->b != NULL) {
                /* Verify symmetry of b - up links */
                if (cur->b->up != cur) {
                        printf("cur->b->up != cur\n");
                        return EINVAL;
                }

                /* Verify that if a node is red, its right child is red */
                if (cur->b->color == odc_red && cur->color == odc_red) {
                        printf("cur->b is red, cur is red\n");
                        return EINVAL;
                }

                /* Recurse to right child */
                rc = odict_validate_tree(cur->b, &bd_b);
                if (rc != EOK)
                        return rc;
        } else {
                bd_b = -1;
        }

        /* Verify that black depths of both children are equal */
        if (bd_a >= 0 && bd_b >= 0) {
                if (bd_a != bd_b) {
                        printf("Black depth %d != %d\n", bd_a, bd_b);
                        return EINVAL;
                }
        }

        cur_d = cur->color == odc_black ? 1 : 0;
        if (bd_a >= 0)
                *rbd = bd_a + cur_d;
        else if (bd_b >= 0)
                *rbd = bd_b + cur_d;
        else
                *rbd = cur_d;

        return EOK;
}

/** Validate ordered dictionary properties.
 *
 * @param odict Ordered dictionary
 */
errno_t odict_validate(odict_t *odict)
{
        int bd;
        errno_t rc;

        if (odict->root == NULL)
                return EOK;

        rc = odict_validate_tree(odict->root, &bd);
        if (rc != EOK)
                odict_print_tree(odict->root);

        return rc;
}

/** Initialize ordered dictionary.
 *
 * @param odict Ordered dictionary
 * @param getkey Funcition to get key
 * @param cmp Function to compare entries
 */
void odict_initialize(odict_t *odict, odgetkey_t getkey, odcmp_t cmp)
{
        odict->root = NULL;
        list_initialize(&odict->entries);
        odict->getkey = getkey;
        odict->cmp = cmp;
}

/** Initialize ordered dictionary link.
 *
 * @param odlink Ordered dictionary link
 */
void odlink_initialize(odlink_t *odlink)
{
        odlink->odict = NULL;
        odlink->up = NULL;
        odlink->a = NULL;
        odlink->b = NULL;
        link_initialize(&odlink->lentries);
}

/** Insert entry in ordered dictionary.
 *
 * Insert entry in ordered dictionary, placing it after other entries
 * with the same key.
 *
 * @param odlink New entry
 * @param odict Ordered dictionary
 * @param hint An entry that might be near the new entry or @c NULL
 */
void odict_insert(odlink_t *odlink, odict_t *odict, odlink_t *hint)
{
        int d;
        odlink_t *cur;
        odlink_t *p;
        odlink_t *g;
        odlink_t *u;
        odict_child_sel_t pcs, gcs;

        assert(!odlink_used(odlink));

        if (odict->root == NULL) {
                /* odlink is the root node */
                odict->root = odlink;
                odlink->odict = odict;
                odlink->color = odc_black;
                list_append(&odlink->lentries, &odict->entries);
                return;
        }

        cur = odict_search_start_node(odict, odict->getkey(odlink), hint);
        while (true) {
                d = odict->cmp(odict->getkey(odlink), odict->getkey(cur));
                if (d < 0) {
                        if (cur->a == NULL) {
                                odict_link_child_a(odlink, cur);
                                break;
                        }
                        cur = cur->a;
                } else {
                        if (cur->b == NULL) {
                                odict_link_child_b(odlink, cur);
                                break;
                        }
                        cur = cur->b;
                }
        }


        odlink->color = odc_red;

        while (true) {
                /* Fix up odlink and its parent potentially being red */
                if (odlink->up == NULL) {
                        odlink->color = odc_black;
                        break;
                }

                if (odlink->up->color == odc_black)
                        break;

                /* Get parent, grandparent, uncle */
                odict_pgu(odlink, &p, &pcs, &g, &gcs, &u);

                if (g == NULL) {
                        p->color = odc_black;
                        break;
                }

                if (p->color == odc_red && u != NULL && u->color == odc_red) {
                        /* Parent and uncle are both red */
                        p->color = odc_black;
                        u->color = odc_black;
                        g->color = odc_red;
                        odlink = g;
                        continue;
                }

                /* Parent is red but uncle is black, odlink-P-G is trans */
                if (pcs != gcs) {
                        if (gcs == odcs_a) {
                                /* odlink is right child of P */
                                /* P is left child of G */
                                odict_rotate_left(p);
                        } else {
                                /* odlink is left child of P */
                                /* P is right child of G */
                                odict_rotate_right(p);
                        }

                        odlink = p;
                        odict_pgu(odlink, &p, &pcs, &g, &gcs, &u);
                }

                /* odlink-P-G is now cis */
                assert(pcs == gcs);
                if (pcs == odcs_a) {
                        /* odlink is left child of P */
                        /* P is left child of G */
                        odict_rotate_right(g);
                } else {
                        /* odlink is right child of P */
                        /* P is right child of G */
                        odict_rotate_left(g);
                }

                p->color = odc_black;
                g->color = odc_red;
                break;
        }
}

/** Remove entry from ordered dictionary.
 *
 * @param odlink Ordered dictionary link
 */
void odict_remove(odlink_t *odlink)
{
        odlink_t *n;
        odlink_t *c;
        odlink_t *p;
        odlink_t *s;
        odlink_t *sc, *st;
        odict_child_sel_t pcs;

        if (odlink->a != NULL && odlink->b != NULL) {
                n = odict_next(odlink, odlink->odict);
                assert(n != NULL);

                odict_swap_node(odlink, n);
        }

        /* odlink has at most one child */
        if (odlink->a != NULL) {
                assert(odlink->b == NULL);
                c = odlink->a;
        } else {
                c = odlink->b;
        }

        if (odlink->color == odc_red) {
                /* We can remove it harmlessly */
                assert(c == NULL);
                odict_unlink(odlink);
                return;
        }

        /* odlink->color == odc_black */
        if (c != NULL && c->color == odc_red) {
                /* Child is red: swap colors of S and C */
                c->color = odc_black;
                odict_replace_subtree(c, odlink);
                odlink->up = odlink->a = odlink->b = NULL;
                odlink->odict = NULL;
                list_remove(&odlink->lentries);
                return;
        }

        /* There cannot be one black child */
        assert(c == NULL);

        n = NULL;
        p = odlink->up;
        odict_unlink(odlink);
        /* We removed one black node, creating imbalance */
again:
        /* Case 1: N is the new root */
        if (p == NULL)
                return;

        odict_sibling(n, p, &pcs, &s);

        /* Paths through N have one less black node than paths through S */

        /* Case 2: S is red */
        if (s->color == odc_red) {
                assert(p->color == odc_black);
                p->color = odc_red;
                s->color = odc_black;
                if (n == p->a)
                        odict_rotate_left(p);
                else
                        odict_rotate_right(p);
                odict_sibling(n, p, &pcs, &s);
                /* Now S is black */
                assert(s->color == odc_black);
        }

        /* Case 3: P, S and S's children are black */
        if (p->color == odc_black &&
            s->color == odc_black &&
            (s->a == NULL || s->a->color == odc_black) &&
            (s->b == NULL || s->b->color == odc_black)) {
                /*
                 * Changing S to red means all paths through S or N have one
                 * less black node than they should. So redo the same for P.
                 */
                s->color = odc_red;
                n = p;
                p = n->up;
                goto again;
        }

        /* Case 4: P is red, S and S's children are black */
        if (p->color == odc_red &&
            s->color == odc_black &&
            (s->a == NULL || s->a->color == odc_black) &&
            (s->b == NULL || s->b->color == odc_black)) {
                /* Swap colors of S and P */
                s->color = odc_red;
                p->color = odc_black;
                return;
        }

        /* N is the left child */
        if (pcs == odcs_a) {
                st = s->a;
                sc = s->b;
        } else {
                st = s->b;
                sc = s->a;
        }

        /* Case 5: S is black and S's trans child is red, S's cis child is black */
        if (s->color == odc_black &&
            (st != NULL && st->color == odc_red) &&
            (sc == NULL || sc->color == odc_black)) {
                /* N is the left child */
                if (pcs == odcs_a)
                        odict_rotate_right(s);
                else
                        odict_rotate_left(s);
                s->color = odc_red;
                s->up->color = odc_black;
                /* Now N has a black sibling whose cis child is red */
                odict_sibling(n, p, &pcs, &s);
                /* N is the left child */
                if (pcs == odcs_a) {
                        st = s->a;
                        sc = s->b;
                } else {
                        st = s->b;
                        sc = s->a;
                }
        }

        /* Case 6: S is black, S's cis child is red */
        assert(s->color == odc_black);
        assert(sc != NULL);
        assert(sc->color == odc_red);

        if (pcs == odcs_a)
                odict_rotate_left(p);
        else
                odict_rotate_right(p);

        s->color = p->color;
        p->color = odc_black;
        sc->color = odc_black;
}

/** Update dictionary after entry key has been changed.
 *
 * After the caller modifies the key of an entry, they need to call
 * this function so that the dictionary can update itself accordingly.
 *
 * @param odlink Ordered dictionary entry
 * @param odict Ordered dictionary
 */
void odict_key_update(odlink_t *odlink, odict_t *odict)
{
        odlink_t *n;

        n = odict_next(odlink, odict);
        odict_remove(odlink);
        odict_insert(odlink, odict, n);
}

/** Return true if entry is in a dictionary.
 *
 * @param odlink Ordered dictionary entry
 * @return @c true if entry is in a dictionary, @c false otherwise
 */
bool odlink_used(odlink_t *odlink)
{
        return odlink->odict != NULL;
}

/** Return true if ordered dictionary is empty.
 *
 * @param odict Ordered dictionary
 * @return @c true if @a odict is emptry, @c false otherwise
 */
bool odict_empty(odict_t *odict)
{
        return odict->root == NULL;
}

/** Return the number of entries in @a odict.
 *
 * @param odict Ordered dictionary
 */
unsigned long odict_count(odict_t *odict)
{
        unsigned long cnt;
        odlink_t *cur;

        cnt = 0;
        cur = odict_first(odict);
        while (cur != NULL) {
                ++cnt;
                cur = odict_next(cur, odict);
        }

        return cnt;
}

/** Return first entry in a list or @c NULL if list is empty.
 *
 * @param odict Ordered dictionary
 * @return First entry
 */
odlink_t *odict_first(odict_t *odict)
{
        link_t *link;

        link = list_first(&odict->entries);
        if (link == NULL)
                return NULL;

        return list_get_instance(link, odlink_t, lentries);
}

/** Return last entry in a list or @c NULL if list is empty
 *
 * @param odict Ordered dictionary
 * @return Last entry
 */
odlink_t *odict_last(odict_t *odict)
{
        link_t *link;

        link = list_last(&odict->entries);
        if (link == NULL)
                return NULL;

        return list_get_instance(link, odlink_t, lentries);
}

/** Return previous entry in list or @c NULL if @a link is the first one.
 *
 * @param odlink Entry
 * @param odict Ordered dictionary
 * @return Previous entry
 */
odlink_t *odict_prev(odlink_t *odlink, odict_t *odict)
{
        link_t *link;

        link = list_prev(&odlink->lentries, &odlink->odict->entries);
        if (link == NULL)
                return NULL;

        return list_get_instance(link, odlink_t, lentries);
}

/** Return next entry in dictionary or @c NULL if @a odlink is the last one
 *
 * @param odlink Entry
 * @param odict Ordered dictionary
 * @return Next entry
 */
odlink_t *odict_next(odlink_t *odlink, odict_t *odict)
{
        link_t *link;

        link = list_next(&odlink->lentries, &odlink->odict->entries);
        if (link == NULL)
                return NULL;

        return list_get_instance(link, odlink_t, lentries);
}

/** Find first entry whose key is equal to @a key/
 *
 * @param odict Ordered dictionary
 * @param key Key
 * @param hint Nearby entry
 * @return Pointer to entry on success, @c NULL on failure
 */
odlink_t *odict_find_eq(odict_t *odict, void *key, odlink_t *hint)
{
        odlink_t *geq;

        geq = odict_find_geq(odict, key, hint);
        if (geq == NULL)
                return NULL;

        if (odict->cmp(odict->getkey(geq), key) == 0)
                return geq;
        else
                return NULL;
}

/** Find last entry whose key is equal to @a key/
 *
 * @param odict Ordered dictionary
 * @param key Key
 * @param hint Nearby entry
 * @return Pointer to entry on success, @c NULL on failure
 */
odlink_t *odict_find_eq_last(odict_t *odict, void *key, odlink_t *hint)
{
        odlink_t *leq;

        leq = odict_find_leq(odict, key, hint);
        if (leq == NULL)
                return NULL;

        if (odict->cmp(odict->getkey(leq), key) == 0)
                return leq;
        else
                return NULL;
}

/** Find first entry whose key is greater than or equal to @a key
 *
 * @param odict Ordered dictionary
 * @param key Key
 * @param hint Nearby entry
 * @return Pointer to entry on success, @c NULL on failure
 */
odlink_t *odict_find_geq(odict_t *odict, void *key, odlink_t *hint)
{
        odlink_t *cur;
        odlink_t *next;
        int d;

        cur = odict_search_start_node(odict, key, hint);
        if (cur == NULL)
                return NULL;

        while (true) {
                d = odict->cmp(odict->getkey(cur), key);
                if (d >= 0)
                        next = cur->a;
                else
                        next = cur->b;

                if (next == NULL)
                        break;

                cur = next;
        }

        if (d >= 0) {
                return cur;
        } else {
                return odict_next(cur, odict);
        }
}

/** Find last entry whose key is greater than @a key.
 *
 * @param odict Ordered dictionary
 * @param key Key
 * @param hint Nearby entry
 * @return Pointer to entry on success, @c NULL on failure
 */
odlink_t *odict_find_gt(odict_t *odict, void *key, odlink_t *hint)
{
        odlink_t *leq;

        leq = odict_find_leq(odict, key, hint);
        if (leq != NULL)
                return odict_next(leq, odict);
        else
                return odict_first(odict);
}

/** Find last entry whose key is less than or equal to @a key
 *
 * @param odict Ordered dictionary
 * @param key Key
 * @param hint Nearby entry
 * @return Pointer to entry on success, @c NULL on failure
 */
odlink_t *odict_find_leq(odict_t *odict, void *key, odlink_t *hint)
{
        odlink_t *cur;
        odlink_t *next;
        int d;

        cur = odict_search_start_node(odict, key, hint);
        if (cur == NULL)
                return NULL;

        while (true) {
                d = odict->cmp(key, odict->getkey(cur));
                if (d >= 0)
                        next = cur->b;
                else
                        next = cur->a;

                if (next == NULL)
                        break;

                cur = next;
        }

        if (d >= 0) {
                return cur;
        } else {
                return odict_prev(cur, odict);
        }
}

/** Find last entry whose key is less than @a key.
 *
 * @param odict Ordered dictionary
 * @param key Key
 * @param hint Nearby entry
 * @return Pointer to entry on success, @c NULL on failure
 */
odlink_t *odict_find_lt(odict_t *odict, void *key, odlink_t *hint)
{
        odlink_t *geq;

        geq = odict_find_geq(odict, key, hint);
        if (geq != NULL)
                return odict_prev(geq, odict);
        else
                return odict_last(odict);
}

/** Return parent, grandparent and uncle.
 *
 * @param n Node
 * @param p Place to store pointer to parent of @a n
 * @param pcs Place to store position of @a n w.r.t. @a p
 * @param g Place to store pointer to grandparent of @a n
 * @param gcs Place to store position of @a p w.r.t. @a g
 * @param u Place to store pointer to uncle of @a n
 */
static void odict_pgu(odlink_t *n, odlink_t **p, odict_child_sel_t *pcs,
    odlink_t **g, odict_child_sel_t *gcs, odlink_t **u)
{
        *p = n->up;

        if (*p == NULL) {
                /* No parent */
                *g = NULL;
                *u = NULL;
                return;
        }

        if ((*p)->a == n) {
                *pcs = odcs_a;
        } else {
                assert((*p)->b == n);
                *pcs = odcs_b;
        }

        *g = (*p)->up;
        if (*g == NULL) {
                /* No grandparent */
                *u = NULL;
                return;
        }

        if ((*g)->a == *p) {
                *gcs = odcs_a;
                *u = (*g)->b;
        } else {
                assert((*g)->b == *p);
                *gcs = odcs_b;
                *u = (*g)->a;
        }
}

/** Return sibling and parent w.r.t. parent.
 *
 * @param n Node
 * @param p Parent of @ an
 * @param pcs Place to store position of @a n w.r.t. @a p.
 * @param rs Place to strore pointer to sibling
 */
static void odict_sibling(odlink_t *n, odlink_t *p, odict_child_sel_t *pcs,
    odlink_t **rs)
{
        if (p->a == n) {
                *pcs = odcs_a;
                *rs = p->b;
        } else {
                *pcs = odcs_b;
                *rs = p->a;
        }
}

/** Ordered dictionary left rotation.
 *
 *    Q           P
 *  P   C   <- A    Q
 * A B             B C
 *
 */
static void odict_rotate_left(odlink_t *p)
{
        odlink_t *q;

        q = p->b;
        assert(q != NULL);

        /* Replace P with Q as the root of the subtree */
        odict_replace_subtree(q, p);

        /* Relink P under Q, B under P */
        p->up = q;
        p->b = q->a;
        if (p->b != NULL)
                p->b->up = p;
        q->a = p;

        /* Fix odict root */
        if (p->odict->root == p)
                p->odict->root = q;
}

/** Ordered dictionary right rotation.
 *
 *    Q           P
 *  P   C   -> A    Q
 * A B             B C
 *
 */
static void odict_rotate_right(odlink_t *q)
{
        odlink_t *p;

        p = q->a;
        assert(p != NULL);

        /* Replace Q with P as the root of the subtree */
        odict_replace_subtree(p, q);

        /* Relink Q under P, B under Q */
        q->up = p;
        q->a = p->b;
        if (q->a != NULL)
                q->a->up = q;
        p->b = q;

        /* Fix odict root */
        if (q->odict->root == q)
                q->odict->root = p;
}

/** Swap two nodes.
 *
 * Swap position of two nodes in the tree, keeping their identity.
 * This means we don't copy the contents, instead we shuffle around pointers
 * from and to the nodes.
 *
 * @param a First node
 * @param b Second node
 */
static void odict_swap_node(odlink_t *a, odlink_t *b)
{
        odlink_t *n;
        odict_color_t c;

        /* Backlink from A's parent */
        if (a->up != NULL && a->up != b) {
                if (a->up->a == a) {
                        a->up->a = b;
                } else {
                        assert(a->up->b == a);
                        a->up->b = b;
                }
        }

        /* Backlink from A's left child */
        if (a->a != NULL && a->a != b)
                a->a->up = b;
        /* Backling from A's right child */
        if (a->b != NULL && a->b != b)
                a->b->up = b;

        /* Backlink from B's parent */
        if (b->up != NULL && b->up != a) {
                if (b->up->a == b) {
                        b->up->a = a;
                } else {
                        assert(b->up->b == b);
                        b->up->b = a;
                }
        }

        /* Backlink from B's left child */
        if (b->a != NULL && b->a != a)
                b->a->up = a;
        /* Backling from B's right child */
        if (b->b != NULL && b->b != a)
                b->b->up = a;

        /*
         * Swap links going out of A and out of B
         */
        n = a->up;
        a->up = b->up;
        b->up = n;

        n = a->a;
        a->a = b->a;
        b->a = n;

        n = a->b;
        a->b = b->b;
        b->b = n;

        c = a->color;
        a->color = b->color;
        b->color = c;

        /* When A and B are adjacent, fix self-loops that might have arisen */
        if (a->up == a)
                a->up = b;
        if (a->a == a)
                a->a = b;
        if (a->b == a)
                a->b = b;
        if (b->up == b)
                b->up = a;
        if (b->a == b)
                b->a = a;
        if (b->b == b)
                b->b = a;

        /* Fix odict root */
        if (a == a->odict->root)
                a->odict->root = b;
        else if (b == a->odict->root)
                a->odict->root = a;
}

/** Replace subtree.
 *
 * Replace subtree @a old with another subtree @a n. This makes the parent
 * point to the new subtree root and the up pointer of @a n to point to
 * the parent.
 *
 * @param old Subtree to be replaced
 * @param n New subtree
 */
static void odict_replace_subtree(odlink_t *n, odlink_t *old)
{
        if (old->up != NULL) {
                if (old->up->a == old) {
                        old->up->a = n;
                } else {
                        assert(old->up->b == old);
                        old->up->b = n;
                }
        } else {
                assert(old->odict->root == old);
                old->odict->root = n;
        }

        n->up = old->up;
}

/** Unlink node.
 *
 * @param n Ordered dictionary node
 */
static void odict_unlink(odlink_t *n)
{
        if (n->up != NULL) {
                if (n->up->a == n) {
                        n->up->a = NULL;
                } else {
                        assert(n->up->b == n);
                        n->up->b = NULL;
                }

                n->up = NULL;
        } else {
                assert(n->odict->root == n);
                n->odict->root = NULL;
        }

        if (n->a != NULL) {
                n->a->up = NULL;
                n->a = NULL;
        }

        if (n->b != NULL) {
                n->b->up = NULL;
                n->b = NULL;
        }

        n->odict = NULL;
        list_remove(&n->lentries);
}

/** Link node as left child.
 *
 * Append new node @a n as left child of existing node @a old.
 *
 * @param n New node
 * @param old Old node
 */
static void odict_link_child_a(odlink_t *n, odlink_t *old)
{
        old->a = n;
        n->up = old;
        n->odict = old->odict;
        list_insert_before(&n->lentries, &old->lentries);
}

/** Link node as right child.
 *
 * Append new node @a n as right child of existing node @a old.
 *
 * @param n New node
 * @param old Old node
 */
static void odict_link_child_b(odlink_t *n, odlink_t *old)
{
        old->b = n;
        n->up = old;
        n->odict = old->odict;
        list_insert_after(&n->lentries, &old->lentries);
}

/** Get node where search should be started.
 *
 * @param odict Ordered dictionary
 * @param key Key being searched for
 * @param hint Node that might be near the search target or @c NULL
 *
 * @return Node from where search should be started
 */
static odlink_t *odict_search_start_node(odict_t *odict, void *key,
    odlink_t *hint)
{
        odlink_t *a;
        odlink_t *b;
        odlink_t *cur;
        int d, da, db;

        assert(hint == NULL || hint->odict == odict);

        /* If the key is greater than the maximum, start search in the maximum */
        b = odict_last(odict);
        if (b != NULL) {
                d = odict->cmp(odict->getkey(b), key);
                if (d < 0)
                        return b;
        }

        /* If the key is less tna the minimum, start search in the minimum */
        a = odict_first(odict);
        if (a != NULL) {
                d = odict->cmp(key, odict->getkey(a));
                if (d < 0)
                        return a;
        }

        /*
         * Proposition: Let A, B be two BST nodes such that B is a descendant
         * of A. Let N be a node such that either key(A) < key(N) < key(B)
         * Then N is a descendant of A.
         * Corollary: We can start searching for N from A, instead from
         * the root.
         *
         * Proof: When walking the BST in order, visit_tree(A) does a
         * visit_tree(A->a), visit(A), visit(A->b). If key(A) < key(B),
         * we will first visit A, then while visiting all nodes with values
         * between A and B we will not leave subtree A->b.
         */

        /* If there is no hint, start search from the root */
        if (hint == NULL)
                return odict->root;

        /*
         * Start from hint and walk up to the root, keeping track of
         * minimum and maximum. Once key is strictly between them,
         * we can return the current node, which we've proven to be
         * an ancestor of a potential node with the given key
         */
        a = b = cur = hint;
        while (cur->up != NULL) {
                cur = cur->up;

                d = odict->cmp(odict->getkey(cur), odict->getkey(a));
                if (d < 0)
                        a = cur;

                d = odict->cmp(odict->getkey(b), odict->getkey(cur));
                if (d < 0)
                        b = cur;

                da = odict->cmp(odict->getkey(a), key);
                db = odict->cmp(key, odict->getkey(b));
                if (da < 0 && db < 0) {
                        /* Both a and b are descendants of cur */
                        return cur;
                }
        }

        return odict->root;
}

/** @}
 */