Index: kernel/generic/src/adt/bitmap.c
===================================================================
--- kernel/generic/src/adt/bitmap.c	(revision 55c5cb056e5a70788603b6b8a7c72a8ee64389b5)
+++ 	(revision )
@@ -1,338 +1,0 @@
-/*
- * Copyright (c) 2006 Jakub Jermar
- * 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
- * @brief Implementation of bitmap ADT.
- *
- * This file implements bitmap ADT and provides functions for
- * setting and clearing ranges of bits and for finding ranges
- * of unset bits.
- */
-
-#include <adt/bitmap.h>
-#include <align.h>
-#include <assert.h>
-#include <macros.h>
-#include <typedefs.h>
-
-#define ALL_ONES    0xff
-#define ALL_ZEROES  0x00
-
-/** Unchecked version of bitmap_get()
- *
- * This version of bitmap_get() does not do any boundary checks.
- *
- * @param bitmap  Bitmap to access.
- * @param element Element to access.
- *
- * @return Bit value of the element in the bitmap.
- *
- */
-static unsigned int bitmap_get_fast(bitmap_t *bitmap, size_t element)
-{
-	size_t byte = element / BITMAP_ELEMENT;
-	uint8_t mask = 1 << (element & BITMAP_REMAINER);
-
-	return !!((bitmap->bits)[byte] & mask);
-}
-
-/** Get bitmap size
- *
- * Return the size (in bytes) required for the bitmap.
- *
- * @param elements   Number bits stored in bitmap.
- *
- * @return Size (in bytes) required for the bitmap.
- *
- */
-size_t bitmap_size(size_t elements)
-{
-	size_t size = elements / BITMAP_ELEMENT;
-
-	if ((elements % BITMAP_ELEMENT) != 0)
-		size++;
-
-	return size;
-}
-
-/** Initialize bitmap.
- *
- * No portion of the bitmap is set or cleared by this function.
- *
- * @param bitmap     Bitmap structure.
- * @param elements   Number of bits stored in bitmap.
- * @param data       Address of the memory used to hold the map.
- *                   The optional 2nd level bitmap follows the 1st
- *                   level bitmap.
- *
- */
-void bitmap_initialize(bitmap_t *bitmap, size_t elements, void *data)
-{
-	bitmap->elements = elements;
-	bitmap->bits = (uint8_t *) data;
-	bitmap->next_fit = 0;
-}
-
-/** Set range of bits.
- *
- * @param bitmap Bitmap structure.
- * @param start  Starting bit.
- * @param count  Number of bits to set.
- *
- */
-void bitmap_set_range(bitmap_t *bitmap, size_t start, size_t count)
-{
-	assert(start + count <= bitmap->elements);
-
-	if (count == 0)
-		return;
-
-	size_t start_byte = start / BITMAP_ELEMENT;
-	size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT);
-
-	/* Leading unaligned bits */
-	size_t lub = min(aligned_start - start, count);
-
-	/* Aligned middle bits */
-	size_t amb = (count > lub) ? (count - lub) : 0;
-
-	/* Trailing aligned bits */
-	size_t tab = amb % BITMAP_ELEMENT;
-
-	if (start + count < aligned_start) {
-		/* Set bits in the middle of byte. */
-		bitmap->bits[start_byte] |=
-		    ((1 << lub) - 1) << (start & BITMAP_REMAINER);
-		return;
-	}
-
-	if (lub) {
-		/* Make sure to set any leading unaligned bits. */
-		bitmap->bits[start_byte] |=
-		    ~((1 << (BITMAP_ELEMENT - lub)) - 1);
-	}
-
-	size_t i;
-
-	for (i = 0; i < amb / BITMAP_ELEMENT; i++) {
-		/* The middle bits can be set byte by byte. */
-		bitmap->bits[aligned_start / BITMAP_ELEMENT + i] =
-		    ALL_ONES;
-	}
-
-	if (tab) {
-		/* Make sure to set any trailing aligned bits. */
-		bitmap->bits[aligned_start / BITMAP_ELEMENT + i] |=
-		    (1 << tab) - 1;
-	}
-}
-
-/** Clear range of bits.
- *
- * @param bitmap Bitmap structure.
- * @param start  Starting bit.
- * @param count  Number of bits to clear.
- *
- */
-void bitmap_clear_range(bitmap_t *bitmap, size_t start, size_t count)
-{
-	assert(start + count <= bitmap->elements);
-
-	if (count == 0)
-		return;
-
-	size_t start_byte = start / BITMAP_ELEMENT;
-	size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT);
-
-	/* Leading unaligned bits */
-	size_t lub = min(aligned_start - start, count);
-
-	/* Aligned middle bits */
-	size_t amb = (count > lub) ? (count - lub) : 0;
-
-	/* Trailing aligned bits */
-	size_t tab = amb % BITMAP_ELEMENT;
-
-	if (start + count < aligned_start) {
-		/* Set bits in the middle of byte */
-		bitmap->bits[start_byte] &=
-		    ~(((1 << lub) - 1) << (start & BITMAP_REMAINER));
-		return;
-	}
-
-	if (lub) {
-		/* Make sure to clear any leading unaligned bits. */
-		bitmap->bits[start_byte] &=
-		    (1 << (BITMAP_ELEMENT - lub)) - 1;
-	}
-
-	size_t i;
-
-	for (i = 0; i < amb / BITMAP_ELEMENT; i++) {
-		/* The middle bits can be cleared byte by byte. */
-		bitmap->bits[aligned_start / BITMAP_ELEMENT + i] =
-		    ALL_ZEROES;
-	}
-
-	if (tab) {
-		/* Make sure to clear any trailing aligned bits. */
-		bitmap->bits[aligned_start / BITMAP_ELEMENT + i] &=
-		    ~((1 << tab) - 1);
-	}
-
-	bitmap->next_fit = start_byte;
-}
-
-/** Copy portion of one bitmap into another bitmap.
- *
- * @param dst   Destination bitmap.
- * @param src   Source bitmap.
- * @param count Number of bits to copy.
- *
- */
-void bitmap_copy(bitmap_t *dst, bitmap_t *src, size_t count)
-{
-	assert(count <= dst->elements);
-	assert(count <= src->elements);
-
-	size_t i;
-
-	for (i = 0; i < count / BITMAP_ELEMENT; i++)
-		dst->bits[i] = src->bits[i];
-
-	if (count % BITMAP_ELEMENT) {
-		bitmap_clear_range(dst, i * BITMAP_ELEMENT,
-		    count % BITMAP_ELEMENT);
-		dst->bits[i] |= src->bits[i] &
-		    ((1 << (count % BITMAP_ELEMENT)) - 1);
-	}
-}
-
-static int constraint_satisfy(size_t index, size_t base, size_t constraint)
-{
-	return (((base + index) & constraint) == 0);
-}
-
-/** Find a continuous zero bit range
- *
- * Find a continuous zero bit range in the bitmap. The address
- * computed as the sum of the index of the first zero bit and
- * the base argument needs to be compliant with the constraint
- * (those bits that are set in the constraint cannot be set in
- * the address).
- *
- * If the index argument is non-NULL, the continuous zero range
- * is set and the index of the first bit is stored to index.
- * Otherwise the bitmap stays untouched.
- *
- * @param bitmap     Bitmap structure.
- * @param count      Number of continuous zero bits to find.
- * @param base       Address of the first bit in the bitmap.
- * @param prefered   Prefered address to start searching from.
- * @param constraint Constraint for the address of the first zero bit.
- * @param index      Place to store the index of the first zero
- *                   bit. Can be NULL (in which case the bitmap
- *                   is not modified).
- *
- * @return Non-zero if a continuous range of zero bits satisfying
- *         the constraint has been found.
- * @return Zero otherwise.
- *
- */
-bool bitmap_allocate_range(bitmap_t *bitmap, size_t count, size_t base,
-    size_t prefered, size_t constraint, size_t *index)
-{
-	if (count == 0)
-		return false;
-
-	size_t size = bitmap_size(bitmap->elements);
-	size_t next_fit = bitmap->next_fit;
-
-	/*
-	 * Adjust the next-fit value according to the address
-	 * the caller prefers to start the search at.
-	 */
-	if ((prefered > base) && (prefered < base + bitmap->elements)) {
-		size_t prefered_fit = (prefered - base) / BITMAP_ELEMENT;
-
-		if (prefered_fit > next_fit)
-			next_fit = prefered_fit;
-	}
-
-	for (size_t pos = 0; pos < size; pos++) {
-		size_t byte = (next_fit + pos) % size;
-
-		/* Skip if the current byte has all bits set */
-		if (bitmap->bits[byte] == ALL_ONES)
-			continue;
-
-		size_t byte_bit = byte * BITMAP_ELEMENT;
-
-		for (size_t bit = 0; bit < BITMAP_ELEMENT; bit++) {
-			size_t i = byte_bit + bit;
-
-			if (i >= bitmap->elements)
-				break;
-
-			if (!constraint_satisfy(i, base, constraint))
-				continue;
-
-			if (!bitmap_get_fast(bitmap, i)) {
-				size_t continuous = 1;
-
-				for (size_t j = 1; j < count; j++) {
-					if ((i + j < bitmap->elements) &&
-					    (!bitmap_get_fast(bitmap, i + j)))
-						continuous++;
-					else
-						break;
-				}
-
-				if (continuous == count) {
-					if (index != NULL) {
-						bitmap_set_range(bitmap, i, count);
-						bitmap->next_fit = i / BITMAP_ELEMENT;
-						*index = i;
-					}
-
-					return true;
-				} else
-					i += continuous;
-			}
-		}
-	}
-
-	return false;
-}
-
-/** @}
- */
Index: kernel/generic/src/adt/hash_table.c
===================================================================
--- kernel/generic/src/adt/hash_table.c	(revision 55c5cb056e5a70788603b6b8a7c72a8ee64389b5)
+++ 	(revision )
@@ -1,473 +1,0 @@
-/*
- * Copyright (c) 2008 Jakub Jermar
- * Copyright (c) 2012 Adam Hraska
- *
- * 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
- * @{
- */
-/** @file
- */
-
-/*
- * This is an implementation of a generic resizable chained hash table.
- *
- * The table grows to 2*n+1 buckets each time, starting at n == 89,
- * per Thomas Wang's recommendation:
- * http://www.concentric.net/~Ttwang/tech/hashsize.htm
- *
- * This policy produces prime table sizes for the first five resizes
- * and generally produces table sizes which are either prime or
- * have fairly large (prime/odd) divisors. Having a prime table size
- * mitigates the use of suboptimal hash functions and distributes
- * items over the whole table.
- */
-
-#include <adt/hash_table.h>
-#include <adt/list.h>
-#include <assert.h>
-#include <stdlib.h>
-#include <str.h>
-
-/* Optimal initial bucket count. See comment above. */
-#define HT_MIN_BUCKETS  89
-/* The table is resized when the average load per bucket exceeds this number. */
-#define HT_MAX_LOAD     2
-
-static size_t round_up_size(size_t);
-static bool alloc_table(size_t, list_t **);
-static void clear_items(hash_table_t *);
-static void resize(hash_table_t *, size_t);
-static void grow_if_needed(hash_table_t *);
-static void shrink_if_needed(hash_table_t *);
-
-/* Dummy do nothing callback to invoke in place of remove_callback == NULL. */
-static void nop_remove_callback(ht_link_t *item)
-{
-	/* no-op */
-}
-
-/** Create chained hash table.
- *
- * @param h        Hash table structure. Will be initialized by this call.
- * @param init_size Initial desired number of hash table buckets. Pass zero
- *                 if you want the default initial size.
- * @param max_load The table is resized when the average load per bucket
- *                 exceeds this number. Pass zero if you want the default.
- * @param op       Hash table operations structure. remove_callback()
- *                 is optional and can be NULL if no action is to be taken
- *                 upon removal. equal() is optional if and only if
- *                 hash_table_insert_unique() will never be invoked.
- *                 All other operations are mandatory.
- *
- * @return True on success
- *
- */
-bool hash_table_create(hash_table_t *h, size_t init_size, size_t max_load,
-    const hash_table_ops_t *op)
-{
-	assert(h);
-	assert(op && op->hash && op->key_hash && op->key_equal);
-
-	/* Check for compulsory ops. */
-	if (!op || !op->hash || !op->key_hash || !op->key_equal)
-		return false;
-
-	h->bucket_cnt = round_up_size(init_size);
-
-	if (!alloc_table(h->bucket_cnt, &h->bucket))
-		return false;
-
-	h->max_load = (max_load == 0) ? HT_MAX_LOAD : max_load;
-	h->item_cnt = 0;
-	h->op = op;
-	h->full_item_cnt = h->max_load * h->bucket_cnt;
-	h->apply_ongoing = false;
-
-	return true;
-}
-
-/** Destroy a hash table instance.
- *
- * @param h Hash table to be destroyed.
- *
- */
-void hash_table_destroy(hash_table_t *h)
-{
-	assert(h && h->bucket);
-	assert(!h->apply_ongoing);
-
-	clear_items(h);
-
-	free(h->bucket);
-
-	h->bucket = NULL;
-	h->bucket_cnt = 0;
-}
-
-/** Returns true if there are no items in the table. */
-bool hash_table_empty(hash_table_t *h)
-{
-	assert(h && h->bucket);
-	return h->item_cnt == 0;
-}
-
-/** Returns the number of items in the table. */
-size_t hash_table_size(hash_table_t *h)
-{
-	assert(h && h->bucket);
-	return h->item_cnt;
-}
-
-/** Remove all elements from the hash table
- *
- * @param h Hash table to be cleared
- */
-void hash_table_clear(hash_table_t *h)
-{
-	assert(h && h->bucket);
-	assert(!h->apply_ongoing);
-
-	clear_items(h);
-
-	/* Shrink the table to its minimum size if possible. */
-	if (HT_MIN_BUCKETS < h->bucket_cnt) {
-		resize(h, HT_MIN_BUCKETS);
-	}
-}
-
-/** Unlinks and removes all items but does not resize. */
-static void clear_items(hash_table_t *h)
-{
-	if (h->item_cnt == 0)
-		return;
-
-	void (*remove_cb)(ht_link_t *) = h->op->remove_callback ? h->op->remove_callback : nop_remove_callback;
-
-	for (size_t idx = 0; idx < h->bucket_cnt; ++idx) {
-		list_foreach_safe(h->bucket[idx], cur, next) {
-			assert(cur);
-			ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
-
-			list_remove(cur);
-			remove_cb(cur_link);
-		}
-	}
-
-	h->item_cnt = 0;
-}
-
-/** Insert item into a hash table.
- *
- * @param h    Hash table.
- * @param item Item to be inserted into the hash table.
- */
-void hash_table_insert(hash_table_t *h, ht_link_t *item)
-{
-	assert(item);
-	assert(h && h->bucket);
-	assert(!h->apply_ongoing);
-
-	size_t idx = h->op->hash(item) % h->bucket_cnt;
-
-	list_append(&item->link, &h->bucket[idx]);
-	++h->item_cnt;
-	grow_if_needed(h);
-}
-
-/** Insert item into a hash table if not already present.
- *
- * @param h    Hash table.
- * @param item Item to be inserted into the hash table.
- *
- * @return False if such an item had already been inserted.
- * @return True if the inserted item was the only item with such a lookup key.
- */
-bool hash_table_insert_unique(hash_table_t *h, ht_link_t *item)
-{
-	assert(item);
-	assert(h && h->bucket && h->bucket_cnt);
-	assert(h->op && h->op->hash && h->op->equal);
-	assert(!h->apply_ongoing);
-
-	size_t idx = h->op->hash(item) % h->bucket_cnt;
-
-	/* Check for duplicates. */
-	list_foreach(h->bucket[idx], link, ht_link_t, cur_link) {
-		/*
-		 * We could filter out items using their hashes first, but
-		 * calling equal() might very well be just as fast.
-		 */
-		if (h->op->equal(cur_link, item))
-			return false;
-	}
-
-	list_append(&item->link, &h->bucket[idx]);
-	++h->item_cnt;
-	grow_if_needed(h);
-
-	return true;
-}
-
-/** Search hash table for an item matching keys.
- *
- * @param h   Hash table.
- * @param key Array of all keys needed to compute hash index.
- *
- * @return Matching item on success, NULL if there is no such item.
- *
- */
-ht_link_t *hash_table_find(const hash_table_t *h, const void *key)
-{
-	assert(h && h->bucket);
-
-	size_t idx = h->op->key_hash(key) % h->bucket_cnt;
-
-	list_foreach(h->bucket[idx], link, ht_link_t, cur_link) {
-		/*
-		 * Is this is the item we are looking for? We could have first
-		 * checked if the hashes match but op->key_equal() may very well be
-		 * just as fast as op->hash().
-		 */
-		if (h->op->key_equal(key, cur_link)) {
-			return cur_link;
-		}
-	}
-
-	return NULL;
-}
-
-/** Find the next item equal to item. */
-ht_link_t *
-hash_table_find_next(const hash_table_t *h, ht_link_t *first, ht_link_t *item)
-{
-	assert(item);
-	assert(h && h->bucket);
-
-	size_t idx = h->op->hash(item) % h->bucket_cnt;
-
-	/* Traverse the circular list until we reach the starting item again. */
-	for (link_t *cur = item->link.next; cur != &first->link;
-	    cur = cur->next) {
-		assert(cur);
-
-		if (cur == &h->bucket[idx].head)
-			continue;
-
-		ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
-		/*
-		 * Is this is the item we are looking for? We could have first
-		 * checked if the hashes match but op->equal() may very well be
-		 * just as fast as op->hash().
-		 */
-		if (h->op->equal(cur_link, item)) {
-			return cur_link;
-		}
-	}
-
-	return NULL;
-}
-
-/** Remove all matching items from hash table.
- *
- * For each removed item, h->remove_callback() is called.
- *
- * @param h    Hash table.
- * @param key  Array of keys that will be compared against items of
- *             the hash table.
- *
- * @return Returns the number of removed items.
- */
-size_t hash_table_remove(hash_table_t *h, const void *key)
-{
-	assert(h && h->bucket);
-	assert(!h->apply_ongoing);
-
-	size_t idx = h->op->key_hash(key) % h->bucket_cnt;
-
-	size_t removed = 0;
-
-	list_foreach_safe(h->bucket[idx], cur, next) {
-		ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
-
-		if (h->op->key_equal(key, cur_link)) {
-			++removed;
-			list_remove(cur);
-
-			if (h->op->remove_callback)
-				h->op->remove_callback(cur_link);
-		}
-	}
-
-	h->item_cnt -= removed;
-	shrink_if_needed(h);
-
-	return removed;
-}
-
-/** Removes an item already present in the table. The item must be in the table. */
-void hash_table_remove_item(hash_table_t *h, ht_link_t *item)
-{
-	assert(item);
-	assert(h && h->bucket);
-	assert(link_in_use(&item->link));
-
-	list_remove(&item->link);
-	--h->item_cnt;
-
-	if (h->op->remove_callback)
-		h->op->remove_callback(item);
-	shrink_if_needed(h);
-}
-
-/** Apply function to all items in hash table.
- *
- * @param h   Hash table.
- * @param f   Function to be applied. Return false if no more items
- *            should be visited. The functor may only delete the supplied
- *            item. It must not delete the successor of the item passed
- *            in the first argument.
- * @param arg Argument to be passed to the function.
- */
-void hash_table_apply(hash_table_t *h, bool (*f)(ht_link_t *, void *), void *arg)
-{
-	assert(f);
-	assert(h && h->bucket);
-
-	if (h->item_cnt == 0)
-		return;
-
-	h->apply_ongoing = true;
-
-	for (size_t idx = 0; idx < h->bucket_cnt; ++idx) {
-		list_foreach_safe(h->bucket[idx], cur, next) {
-			ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
-			/*
-			 * The next pointer had already been saved. f() may safely
-			 * delete cur (but not next!).
-			 */
-			if (!f(cur_link, arg))
-				goto out;
-		}
-	}
-out:
-	h->apply_ongoing = false;
-
-	shrink_if_needed(h);
-	grow_if_needed(h);
-}
-
-/** Rounds up size to the nearest suitable table size. */
-static size_t round_up_size(size_t size)
-{
-	size_t rounded_size = HT_MIN_BUCKETS;
-
-	while (rounded_size < size) {
-		rounded_size = 2 * rounded_size + 1;
-	}
-
-	return rounded_size;
-}
-
-/** Allocates and initializes the desired number of buckets. True if successful. */
-static bool alloc_table(size_t bucket_cnt, list_t **pbuckets)
-{
-	assert(pbuckets && HT_MIN_BUCKETS <= bucket_cnt);
-
-	list_t *buckets = malloc(bucket_cnt * sizeof(list_t));
-	if (!buckets)
-		return false;
-
-	for (size_t i = 0; i < bucket_cnt; i++)
-		list_initialize(&buckets[i]);
-
-	*pbuckets = buckets;
-	return true;
-}
-
-/** Shrinks the table if the table is only sparely populated. */
-static inline void shrink_if_needed(hash_table_t *h)
-{
-	if (h->item_cnt <= h->full_item_cnt / 4 && HT_MIN_BUCKETS < h->bucket_cnt) {
-		/*
-		 * Keep the bucket_cnt odd (possibly also prime).
-		 * Shrink from 2n + 1 to n. Integer division discards the +1.
-		 */
-		size_t new_bucket_cnt = h->bucket_cnt / 2;
-		resize(h, new_bucket_cnt);
-	}
-}
-
-/** Grows the table if table load exceeds the maximum allowed. */
-static inline void grow_if_needed(hash_table_t *h)
-{
-	/* Grow the table if the average bucket load exceeds the maximum. */
-	if (h->full_item_cnt < h->item_cnt) {
-		/* Keep the bucket_cnt odd (possibly also prime). */
-		size_t new_bucket_cnt = 2 * h->bucket_cnt + 1;
-		resize(h, new_bucket_cnt);
-	}
-}
-
-/** Allocates and rehashes items to a new table. Frees the old table. */
-static void resize(hash_table_t *h, size_t new_bucket_cnt)
-{
-	assert(h && h->bucket);
-	assert(HT_MIN_BUCKETS <= new_bucket_cnt);
-
-	/* We are traversing the table and resizing would mess up the buckets. */
-	if (h->apply_ongoing)
-		return;
-
-	list_t *new_buckets;
-
-	/* Leave the table as is if we cannot resize. */
-	if (!alloc_table(new_bucket_cnt, &new_buckets))
-		return;
-
-	if (0 < h->item_cnt) {
-		/* Rehash all the items to the new table. */
-		for (size_t old_idx = 0; old_idx < h->bucket_cnt; ++old_idx) {
-			list_foreach_safe(h->bucket[old_idx], cur, next) {
-				ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
-
-				size_t new_idx = h->op->hash(cur_link) % new_bucket_cnt;
-				list_remove(cur);
-				list_append(cur, &new_buckets[new_idx]);
-			}
-		}
-	}
-
-	free(h->bucket);
-	h->bucket = new_buckets;
-	h->bucket_cnt = new_bucket_cnt;
-	h->full_item_cnt = h->max_load * h->bucket_cnt;
-}
-
-/** @}
- */
Index: kernel/generic/src/adt/list.c
===================================================================
--- kernel/generic/src/adt/list.c	(revision 55c5cb056e5a70788603b6b8a7c72a8ee64389b5)
+++ 	(revision )
@@ -1,115 +1,0 @@
-/*
- * Copyright (c) 2004 Jakub Jermar
- * 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
- * @brief	Functions completing doubly linked circular list implementation.
- *
- * This file contains some of the functions implementing doubly linked circular lists.
- * However, this ADT is mostly implemented in @ref list.h.
- */
-
-#include <adt/list.h>
-
-/** Check for membership
- *
- * Check whether link is contained in a list.
- * Membership is defined as pointer equivalence.
- *
- * @param link	Item to look for.
- * @param list	List to look in.
- *
- * @return true if link is contained in list, false otherwise.
- *
- */
-bool list_member(const link_t *link, const list_t *list)
-{
-	bool found = false;
-	link_t *hlp = list->head.next;
-
-	while (hlp != &list->head) {
-		if (hlp == link) {
-			found = true;
-			break;
-		}
-		hlp = hlp->next;
-	}
-
-	return found;
-}
-
-/** Moves items of one list into another after the specified item.
- *
- * Inserts all items of @a list after item at @a pos in another list.
- * Both lists may be empty.
- *
- * @param list Source list to move after pos. Empty afterwards.
- * @param pos Source items will be placed after this item.
- */
-void list_splice(list_t *list, link_t *pos)
-{
-	if (list_empty(list))
-		return;
-
-	/* Attach list to destination. */
-	list->head.next->prev = pos;
-	list->head.prev->next = pos->next;
-
-	/* Link destination list to the added list. */
-	pos->next->prev = list->head.prev;
-	pos->next = list->head.next;
-
-	list_initialize(list);
-}
-
-/** Count list items
- *
- * Return the number of items in the list.
- *
- * @param list		List to count.
- * @return		Number of items in the list.
- */
-unsigned long list_count(const list_t *list)
-{
-	unsigned long count = 0;
-
-	link_t *link = list_first(list);
-	while (link != NULL) {
-		count++;
-		link = list_next(link, list);
-	}
-
-	return count;
-}
-
-/** @}
- */
Index: kernel/generic/src/adt/odict.c
===================================================================
--- kernel/generic/src/adt/odict.c	(revision 55c5cb056e5a70788603b6b8a7c72a8ee64389b5)
+++ 	(revision )
@@ -1,1144 +1,0 @@
-/*
- * 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;
-}
-
-/** @}
- */
