/*
* 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 kernel_generic_adt
* @{
*/
/** @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 <stddef.h>
#include <stdio.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) {
printf(" ");
odict_print_tree(cur->a);
printf(" ");
odict_print_tree(cur->b);
}
printf("]");
}
/** 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 Function 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;
}
/** Finalize ordered dictionary.
*
* @param odict Ordered dictionary (must be empty)
*/
void odict_finalize(odict_t *odict)
{
assert(odict->root == NULL);
}
/** 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;
}
/** @}
*/