Index: uspace/lib/c/Makefile
===================================================================
--- uspace/lib/c/Makefile	(revision d776329b69ef4b29a8601fe5affe7faa8c58b51d)
+++ uspace/lib/c/Makefile	(revision 97b8ca970e38244c08a9fa57840bd46ae9acfb8f)
@@ -141,4 +141,5 @@
 	generic/adt/list.c \
 	generic/adt/hash_table.c \
+	generic/adt/odict.c \
 	generic/adt/prodcons.c \
 	generic/time.c \
@@ -174,4 +175,5 @@
 TEST_SOURCES = \
 	test/main.c \
+	test/odict.c \
 	test/sprintf.c
 
Index: uspace/lib/c/generic/adt/odict.c
===================================================================
--- uspace/lib/c/generic/adt/odict.c	(revision 97b8ca970e38244c08a9fa57840bd46ae9acfb8f)
+++ uspace/lib/c/generic/adt/odict.c	(revision 97b8ca970e38244c08a9fa57840bd46ae9acfb8f)
@@ -0,0 +1,1123 @@
+/*
+ * 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 int odict_validate_tree(odlink_t *cur, int *rbd)
+{
+	int 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
+ */
+int odict_validate(odict_t *odict)
+{
+	int bd;
+	int 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;
+}
+
+/** @}
+ */
Index: uspace/lib/c/include/adt/odict.h
===================================================================
--- uspace/lib/c/include/adt/odict.h	(revision 97b8ca970e38244c08a9fa57840bd46ae9acfb8f)
+++ uspace/lib/c/include/adt/odict.h	(revision 97b8ca970e38244c08a9fa57840bd46ae9acfb8f)
@@ -0,0 +1,68 @@
+/*
+ * 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
+ */
+
+#ifndef LIBC_ODICT_H_
+#define LIBC_ODICT_H_
+
+#include <stdbool.h>
+#include <stddef.h>
+#include <types/adt/odict.h>
+
+#define odict_get_instance(odlink, type, member) \
+	((type *)( (void *)(odlink) - ((void *) &((type *) NULL)->member)))
+
+extern void odict_initialize(odict_t *, odgetkey_t, odcmp_t);
+extern void odlink_initialize(odlink_t *);
+extern void odict_insert(odlink_t *, odict_t *, odlink_t *);
+extern void odict_remove(odlink_t *);
+extern void odict_key_update(odlink_t *, odict_t *);
+extern bool odlink_used(odlink_t *);
+extern bool odict_empty(odict_t *);
+extern unsigned long odict_count(odict_t *);
+extern odlink_t *odict_first(odict_t *);
+extern odlink_t *odict_last(odict_t *);
+extern odlink_t *odict_prev(odlink_t *, odict_t *);
+extern odlink_t *odict_next(odlink_t *, odict_t *);
+extern odlink_t *odict_find_eq(odict_t *, void *, odlink_t *);
+extern odlink_t *odict_find_eq_last(odict_t *, void *, odlink_t *);
+extern odlink_t *odict_find_geq(odict_t *, void *, odlink_t *);
+extern odlink_t *odict_find_gt(odict_t *, void *, odlink_t *);
+extern odlink_t *odict_find_leq(odict_t *, void *, odlink_t *);
+extern odlink_t *odict_find_lt(odict_t *, void *, odlink_t *);
+extern int odict_validate(odict_t *);
+
+#endif
+
+/** @}
+ */
Index: uspace/lib/c/include/types/adt/odict.h
===================================================================
--- uspace/lib/c/include/types/adt/odict.h	(revision 97b8ca970e38244c08a9fa57840bd46ae9acfb8f)
+++ uspace/lib/c/include/types/adt/odict.h	(revision 97b8ca970e38244c08a9fa57840bd46ae9acfb8f)
@@ -0,0 +1,89 @@
+/*
+ * 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
+ */
+
+#ifndef LIBC_TYPES_ODICT_H_
+#define LIBC_TYPES_ODICT_H_
+
+#include <adt/list.h>
+
+typedef struct odlink odlink_t;
+typedef struct odict odict_t;
+
+typedef void *(*odgetkey_t)(odlink_t *);
+typedef int (*odcmp_t)(void *, void *);
+
+typedef enum {
+	odc_black,
+	odc_red
+} odict_color_t;
+
+typedef enum {
+	/** Child A */
+	odcs_a,
+	/** Child B */
+	odcs_b
+} odict_child_sel_t;
+
+/** Ordered dictionary link */
+struct odlink {
+	/** Containing dictionary */
+	odict_t *odict;
+	/** Parent node */
+	odlink_t *up;
+	/** First child */
+	odlink_t *a;
+	/** Second child */
+	odlink_t *b;
+	/** Node color */
+	odict_color_t color;
+	/** Link to odict->entries */
+	link_t lentries;
+};
+
+/** Ordered dictionary */
+struct odict {
+	/** Root of the tree */
+	odlink_t *root;
+	/** List of entries in ascending order */
+	list_t entries;
+	/** Get key operation */
+	odgetkey_t getkey;
+	/** Compare operation */
+	odcmp_t cmp;
+};
+
+#endif
+
+/** @}
+ */
Index: uspace/lib/c/test/main.c
===================================================================
--- uspace/lib/c/test/main.c	(revision d776329b69ef4b29a8601fe5affe7faa8c58b51d)
+++ uspace/lib/c/test/main.c	(revision 97b8ca970e38244c08a9fa57840bd46ae9acfb8f)
@@ -32,4 +32,5 @@
 PCUT_INIT
 
+PCUT_IMPORT(odict);
 PCUT_IMPORT(sprintf);
 
Index: uspace/lib/c/test/odict.c
===================================================================
--- uspace/lib/c/test/odict.c	(revision 97b8ca970e38244c08a9fa57840bd46ae9acfb8f)
+++ uspace/lib/c/test/odict.c	(revision 97b8ca970e38244c08a9fa57840bd46ae9acfb8f)
@@ -0,0 +1,278 @@
+/*
+ * 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.
+ */
+
+#include <adt/odict.h>
+#include <pcut/pcut.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+/** Test entry */
+typedef struct {
+	odlink_t odict;
+	int key;
+} test_entry_t;
+
+enum {
+	/** Length of test number sequences */
+	test_seq_len = 100
+};
+
+/** Test get key function.
+ *
+ * @param odlink Ordered dictionary link
+ * @return Pointer to key
+ */
+static void *test_getkey(odlink_t *odlink)
+{
+	return &odict_get_instance(odlink, test_entry_t, odict)->key;
+}
+
+/** Test compare function.
+ *
+ * @param a First key
+ * @param b Second key
+ * @return <0, 0, >0 if @a a is less than, equal or greater than @a b
+ */
+static int test_cmp(void *a, void *b)
+{
+	int *ia = (int *)a;
+	int *ib = (int *)b;
+
+	return *ia - *ib;
+}
+
+PCUT_INIT
+
+PCUT_TEST_SUITE(odict);
+
+/** Increasing sequence test.
+ *
+ * Test initialization, emptiness, insertion of increasing sequence and walking.
+ */
+PCUT_TEST(incr_seq)
+{
+	odict_t odict;
+	test_entry_t *e;
+	odlink_t *c;
+	int i;
+
+	odict_initialize(&odict, test_getkey, test_cmp);
+
+	PCUT_ASSERT_EQUALS(true, odict_empty(&odict));
+
+	for (i = 0; i < test_seq_len; i++) {
+		e = calloc(1, sizeof(test_entry_t));
+		PCUT_ASSERT_NOT_NULL(e);
+
+		e->key = i;
+		odict_insert(&e->odict, &odict, NULL);
+		PCUT_ASSERT_ERRNO_VAL(EOK, odict_validate(&odict));
+	}
+
+	i = 0;
+	c = odict_first(&odict);
+	while (c != NULL) {
+		e = odict_get_instance(c, test_entry_t, odict);
+		PCUT_ASSERT_INT_EQUALS(i, e->key);
+		c = odict_next(c, &odict);
+		++i;
+	}
+	PCUT_ASSERT_INT_EQUALS(test_seq_len, i);
+
+	i = test_seq_len;
+	c = odict_last(&odict);
+	while (c != NULL) {
+		--i;
+		e = odict_get_instance(c, test_entry_t, odict);
+		PCUT_ASSERT_INT_EQUALS(i, e->key);
+		c = odict_prev(c, &odict);
+	}
+
+	PCUT_ASSERT_INT_EQUALS(0, i);
+}
+
+/** Decreasing sequence test.
+ *
+ * Test initialization, emptiness, insertion of decreasing sequence and walking.
+ */
+PCUT_TEST(decr_seq)
+{
+	odict_t odict;
+	test_entry_t *e;
+	odlink_t *c;
+	int i;
+
+	odict_initialize(&odict, test_getkey, test_cmp);
+
+	PCUT_ASSERT_EQUALS(true, odict_empty(&odict));
+
+	for (i = 0; i < test_seq_len; i++) {
+		e = calloc(1, sizeof(test_entry_t));
+		PCUT_ASSERT_NOT_NULL(e);
+
+		e->key = test_seq_len - i - 1;
+		odict_insert(&e->odict, &odict, NULL);
+		PCUT_ASSERT_ERRNO_VAL(EOK, odict_validate(&odict));
+	}
+
+	i = 0;
+	c = odict_first(&odict);
+	while (c != NULL) {
+		e = odict_get_instance(c, test_entry_t, odict);
+		PCUT_ASSERT_INT_EQUALS(i, e->key);
+		c = odict_next(c, &odict);
+		++i;
+	}
+	PCUT_ASSERT_INT_EQUALS(test_seq_len, i);
+
+	i = test_seq_len;
+	c = odict_last(&odict);
+	while (c != NULL) {
+		--i;
+		e = odict_get_instance(c, test_entry_t, odict);
+		PCUT_ASSERT_INT_EQUALS(i, e->key);
+		c = odict_prev(c, &odict);
+	}
+
+	PCUT_ASSERT_INT_EQUALS(0, i);
+}
+
+/** Increasing sequence insertion and removal test.
+ *
+ * Test sequential insertion of increasing sequence and sequential removal.
+ */
+PCUT_TEST(incr_seq_ins_rem)
+{
+	odict_t odict;
+	test_entry_t *e;
+	odlink_t *c;
+	int i;
+
+	odict_initialize(&odict, test_getkey, test_cmp);
+
+	PCUT_ASSERT_EQUALS(true, odict_empty(&odict));
+
+	for (i = 0; i < test_seq_len; i++) {
+		e = calloc(1, sizeof(test_entry_t));
+		PCUT_ASSERT_NOT_NULL(e);
+
+		e->key = i;
+		odict_insert(&e->odict, &odict, NULL);
+		PCUT_ASSERT_ERRNO_VAL(EOK, odict_validate(&odict));
+	}
+
+	i = 0;
+	c = odict_first(&odict);
+	while (c != NULL) {
+		e = odict_get_instance(c, test_entry_t, odict);
+		PCUT_ASSERT_INT_EQUALS(i, e->key);
+
+		odict_remove(c);
+		PCUT_ASSERT_ERRNO_VAL(EOK, odict_validate(&odict));
+
+		c = odict_first(&odict);
+		++i;
+	}
+
+	PCUT_ASSERT_INT_EQUALS(test_seq_len, i);
+}
+
+/** Generate pseudorandom sequence. */
+static int seq_next(int cur)
+{
+	return (cur * 1951) % 1000000;
+}
+
+/** Test 4.
+ *
+ * Test inserting a pseudorandom sequence and then extracting it again.
+ */
+PCUT_TEST(prseq_ins_extract)
+{
+	odict_t odict;
+	test_entry_t *e, *ep;
+	odlink_t *c, *d;
+	int prev;
+	int i;
+	int v;
+
+	odict_initialize(&odict, test_getkey, test_cmp);
+
+	PCUT_ASSERT_EQUALS(true, odict_empty(&odict));
+
+	v = 1; ep = NULL;
+	for (i = 0; i < test_seq_len; i++) {
+		e = calloc(1, sizeof(test_entry_t));
+		PCUT_ASSERT_NOT_NULL(e);
+
+		e->key = v;
+		odict_insert(&e->odict, &odict, &ep->odict);
+		PCUT_ASSERT_ERRNO_VAL(EOK, odict_validate(&odict));
+		v = seq_next(v);
+		ep = e;
+	}
+
+	/* Verify that entries are in ascending order */
+	c = odict_first(&odict);
+	prev = -1;
+	i = 0;
+	while (c != NULL) {
+		e = odict_get_instance(c, test_entry_t, odict);
+		PCUT_ASSERT_EQUALS(true, e->key > prev);
+
+		prev = e->key;
+		c = odict_next(c, &odict);
+		++i;
+	}
+
+	PCUT_ASSERT_INT_EQUALS(test_seq_len, i);
+
+	/* Try extracting the sequence */
+	v = 1;
+	for (i = 0; i < test_seq_len; i++) {
+		c = odict_find_eq(&odict, (void *)&v, NULL);
+		PCUT_ASSERT_NOT_NULL(c);
+
+		e = odict_get_instance(c, test_entry_t, odict);
+		PCUT_ASSERT_INT_EQUALS(v, e->key);
+
+		d = odict_find_eq_last(&odict, (void *)&v, NULL);
+		PCUT_ASSERT_NOT_NULL(d);
+
+		e = odict_get_instance(d, test_entry_t, odict);
+		PCUT_ASSERT_INT_EQUALS(v, e->key);
+
+		odict_remove(c);
+		PCUT_ASSERT_ERRNO_VAL(EOK, odict_validate(&odict));
+
+		v = seq_next(v);
+		++i;
+	}
+}
+
+PCUT_EXPORT(odict);