Useful Public-Domain C Stuff

assert-macros.h

/*	@file assert-macros.h
**	@author Robert Quattlebaum <darco@deepdarc.com>
**
**	Originally published 2010-8-31.
**
**	This file was written by Robert Quattlebaum <darco@deepdarc.com>.
**
**	This work is provided as-is. Unless otherwise provided in writing,
**	Robert Quattlebaum makes no representations or warranties of any
**	kind concerning this work, express, implied, statutory or otherwise,
**	including without limitation warranties of title, merchantability,
**	fitness for a particular purpose, non infringement, or the absence
**	of latent or other defects, accuracy, or the present or absence of
**	errors, whether or not discoverable, all to the greatest extent
**	permissible under applicable law.
**
**	To the extent possible under law, Robert Quattlebaum has waived all
**	copyright and related or neighboring rights to this work. This work
**	is published from the United States.
**
**	I, Robert Quattlebaum, dedicate any and all copyright interest in
**	this work to the public domain. I make this dedication for the
**	benefit of the public at large and to the detriment of my heirs and
**	successors. I intend this dedication to be an overt act of
**	relinquishment in perpetuity of all present and future rights to
**	this code under copyright law. In jurisdictions where this is not
**	possible, I hereby release this code under the Creative Commons
**	Zero (CC0) license.
**
**	 * <http://creativecommons.org/publicdomain/zero/1.0/>
**
**	See <http://www.deepdarc.com/> for other cool stuff.
**
**	-------------------------------------------------------------------
**
**	See <http://www.mactech.com/articles/develop/issue_11/Parent_final.html>
**	for an explanation about how to use these macros and justification
**	for using this pattern in general.
*/

#ifndef __DARC_ASSERT_MACROS__
#define __DARC_ASSERT_MACROS__

#if CONTIKI
#define assert_error_stream     stdout
#else
#define assert_error_stream     stderr
#endif

#if !DEBUG && !defined(NDEBUG)
#define NDEBUG 1
#endif

#if ASSERT_MACROS_USE_SYSLOG
#include <syslog.h>
#endif

#if HAS_ASSERTMACROS_H
 #include <AssertMacros.h>
#else
#include <stdio.h>
#include <assert.h>
#if !DEBUG && !VERBOSE_DEBUG
 #define assert_printf(fmt, ...) do { } while(0)
 #define check_string(c, s)   do { } while(0)
 #define require_action_string(c, l, a, s) \
    do { if(!(c)) { \
			 a; goto l; \
		 } \
	} while(0)
#else
 #if __AVR__
  #define assert_printf(fmt, ...) \
    fprintf_P(assert_error_stream, \
				PSTR(__FILE__ ":%d: "fmt"\n"), \
				__LINE__, \
				__VA_ARGS__)
 #else
  #if ASSERT_MACROS_USE_SYSLOG
   #define assert_printf(fmt, ...) \
    syslog(7, \
				__FILE__ ":%d: "fmt"\n", \
				__LINE__, \
				__VA_ARGS__)
  #else
   #define assert_printf(fmt, ...) \
    fprintf(assert_error_stream, \
				__FILE__ ":%d: "fmt"\n", \
				__LINE__, \
				__VA_ARGS__)
  #endif
 #endif
 #define check_string(c, s) \
   do { if(!(c)) assert_printf("Check Failed (%s)", \
			s); } while(0)
 #define require_action_string(c, l, a, s) \
	do { if(!(c)) { \
		assert_printf("Requirement Failed (%s)", \
			s); a; goto l; \
		 } \
	} while(0)
#endif

 #define check(c)   check_string(c, # c)
 #define check_noerr(c)   check((c) == 0)
 #define require_quiet(c, l)   do { if(!(c)) goto l; } while(0)
 #define require(c, l)   require_action_string(c, l, {}, # c)

 #define require_noerr(c, l)   require((c) == 0, l)
 #define require_action(c, l, a)   require_action_string(c, l, a, # c)
 #define require_string(c, l, s) \
    require_action_string(c, l, \
	    do {} while(0), s)
#endif

#if OVERRIDE_ASSERT_H
#undef assert
#undef __assert
#define assert(e)  \
    ((void) ((e) ? 0 : __assert (#e, __FILE__, __LINE__)))
#define __assert(e, file, line) \
    ((void)assert_printf ("%s:%u: failed assertion `%s'\n", file, line, e), abort())
#endif // OVERRIDE_ASSERT_H

#endif

btree.c

/*	@file btree.c
**	@author Robert Quattlebaum <darco@deepdarc.com>
**
**	Originally published 2010-8-31.
**
**	This file was written by Robert Quattlebaum <darco@deepdarc.com>.
**
**	This work is provided as-is. Unless otherwise provided in writing,
**	Robert Quattlebaum makes no representations or warranties of any
**	kind concerning this work, express, implied, statutory or otherwise,
**	including without limitation warranties of title, merchantability,
**	fitness for a particular purpose, non infringement, or the absence
**	of latent or other defects, accuracy, or the present or absence of
**	errors, whether or not discoverable, all to the greatest extent
**	permissible under applicable law.
**
**	To the extent possible under law, Robert Quattlebaum has waived all
**	copyright and related or neighboring rights to this work. This work
**	is published from the United States.
**
**	I, Robert Quattlebaum, dedicate any and all copyright interest in
**	this work to the public domain. I make this dedication for the
**	benefit of the public at large and to the detriment of my heirs and
**	successors. I intend this dedication to be an overt act of
**	relinquishment in perpetuity of all present and future rights to
**	this code under copyright law. In jurisdictions where this is not
**	possible, I hereby release this code under the Creative Commons
**	Zero (CC0) license.
**
**	 * <http://creativecommons.org/publicdomain/zero/1.0/>
**
**	-------------------------------------------------------------------
**
**	## Unit Test ##
**
**	This file includes its own unit test. To compile the unit test,
**	simply compile this file with the macro BTREE_SELF_TEST set to 1.
**	For example:
**
**	    cc btree.c -Wall -DBTREE_SELF_TEST=1 -o btree
**
**	## Todo ##
**
**	 * Add some sort of automatic tree-balancing algorithm,
**	   like <http://en.wikipedia.org/wiki/Scapegoat_tree>.
*/

#include "btree.h"
#include <assert.h>

int
bt_insert(
	void** bt,
	void* item,
	bt_compare_func_t compare_func,
	bt_delete_func_t delete_func,
	void* context
) {
	int depth = 0;
	bt_item_t const item_ = item;
	bt_item_t location_;

again:

	location_ = *bt;

	if(location_) {
		bt_compare_result_t result =
		    (*compare_func)(location_, item_, context);

		if(result) {
			// One more step down the rabit hole...
			item_->parent = location_;
			bt = (result < 0) ?
				(void**)&location_->rhs : (void**)&location_->lhs;
			depth++;
			goto again;
		} else if(item_ != location_) {
			// Item already exists, so we replace.
			item_->parent = location_->parent;
			if(item_->parent) {
				if(location_->parent->rhs == location_)
					location_->parent->rhs = item;
				else
					location_->parent->lhs = item;
			}
			item_->lhs = location_->lhs;
			if(location_->lhs)
				location_->lhs->parent = item_;
			item_->rhs = location_->rhs;
			if(location_->rhs)
				location_->rhs->parent = item_;
			*bt = item_;
			(*delete_func)(location_, context);
		}
	} else {
		// Found ourselves a good spot. Put the item here.
		*bt = item_;
	}

	return depth;
}

void*
bt_find(
	void*const* bt,
	const void* item,
	bt_compare_func_t compare_func,
	void* context
) {
	bt_item_t location_ = *bt;
	bt_compare_result_t result = -1;

	while(location_) {
		result = (*compare_func)(location_, item, context);

		if(result)
			location_ = (result < 0) ? location_->rhs : location_->lhs;
		else
			break;
	}

	return location_;
}

bool
bt_remove(
	void** bt,
	void* item,
	bt_compare_func_t compare_func,
	bt_delete_func_t delete_func,
	void* context
) {
	bt_item_t const item_ = bt_find(bt, item, compare_func, context);

	if(item_) {
		if(item_->parent) {
			bt = (void**)((item_->parent->lhs == item_)?&item_->parent->lhs:&item_->parent->rhs);
		}

		if(item_->lhs && !item_->rhs) {
			*bt = item_->lhs;
			item_->lhs->parent = item_->parent;
		} else if(item_->rhs && !item_->lhs) {
			*bt = item_->rhs;
			item_->rhs->parent = item_->parent;
		} else if(!item_->rhs && !item_->lhs) {
			*bt = NULL;
		} else {
			bt_item_t last_item = (bt_item_t)bt_last(item_->lhs);
			item_->rhs->parent = last_item;
			last_item->rhs = item_->rhs;

			*bt = item_->lhs;
			item_->lhs->parent = item_->parent;
		}

		item_->lhs = NULL;
		item_->rhs = NULL;
		item_->parent = NULL;

		if(delete_func)
			(*delete_func)(item_, context);

		return true;
	}

	return false;
}

void*
bt_first(void* item) {
	bt_item_t item_ = item;

	if(item_)
		while(item_->lhs)
			item_ = item_->lhs;

	return (void*)item_;
}

void*
bt_next(void* item) {
	bt_item_t item_ = item;

	if(item) {
		if(item_->rhs) {
			item_ = bt_first(item_->rhs);
		} else {
			while(item_->parent && (item_->parent->rhs == item_)) {
				item_ = item_->parent;
			}
			item_ = item_->parent;
		}
	}

	return (void*)item_;
}

void*
bt_last(void* item) {
	bt_item_t item_ = item;

	if(item_)
		while(item_->rhs)
			item_ = item_->rhs;

	return (void*)item_;
}

void*
bt_prev(void* item) {
	bt_item_t item_ = item;

	if(item) {
		if(item_->lhs) {
			item_ = bt_last(item_->lhs);
		} else {
			while(item_->parent && (item_->parent->lhs == item_)) {
				item_ = item_->parent;
			}
			item_ = item_->parent;
		}
	}

	return (void*)item_;
}

size_t
bt_count(void*const* bt) {
	size_t ret = 0;

	if(*bt) {
		bt_item_t iter = bt_first(*bt);
		const bt_item_t end = bt_last(*bt);

		// We start at 1 here because our end
		// iterator is pointing at the last
		// item instead of the end marker.
		// Without this, this method will
		// be off by 1.
		ret = 1;

		for(; iter != end; iter = bt_next(iter))
			ret++;
	}
	return ret;
}

void
bt_rotate_right(void** bt) {
	bt_item_t item = *bt;

	if(item && item->lhs) {
		item->lhs->parent = item->parent;
		item->parent = item->lhs;
		*bt = item->lhs;
		if(item->lhs->rhs)
			item->lhs->rhs->parent = item;
		item->lhs = item->lhs->rhs;
		((bt_item_t)*bt)->rhs = item;
	}
}

void
bt_rotate_left(void** bt) {
	bt_item_t item = *bt;

	if(item && item->rhs) {
		item->rhs->parent = item->parent;
		item->parent = item->rhs;
		*bt = item->rhs;
		if(item->rhs->lhs)
			item->rhs->lhs->parent = item;
		item->rhs = item->rhs->lhs;
		((bt_item_t)*bt)->lhs = item;
	}
}

unsigned int
bt_unbalance(void** bt) {
	unsigned int ret = 0;
	bt_item_t item = *bt;

	if(!item)
		goto bail;

	while(item->lhs) {
		bt_rotate_right(bt);
		item = *bt;
		ret++;
	}

	ret += bt_unbalance((void**)&item->rhs);

bail:
	return ret;
}

unsigned int
bt_splay(void** bt, void* root) {
	unsigned int ret = 0;
	bt_item_t item = root;

	if(*bt==root)
		goto bail;

	while((item!=*bt) && item && item->parent&& item->parent->parent) {
		void** pivot;

		if(item->parent->parent->lhs==item->parent)
			pivot=(void**)&item->parent->parent->lhs;
		else
			pivot=(void**)&item->parent->parent->rhs;

		if(item->parent->lhs==item)
			bt_rotate_right(pivot);
		else
			bt_rotate_left(pivot);

		ret++;
	}

	if(*bt!=root) {
		if(((bt_item_t)*bt)->lhs==root)
			bt_rotate_right(bt);
		else
			bt_rotate_left(bt);
		ret++;
	}

	assert(*bt==root);

bail:
	return ret;
}

int
bt_get_balance(void* node) {
	int ret = 0;
	int root_index = 0;

	bt_item_t iter = bt_first(node);
	const bt_item_t end = bt_next(bt_last(node));

	for(;iter!=end;iter=bt_next(iter)) {
		if(iter==node)
			root_index = ret;
		ret++;
	}

	ret /= 2;
	ret -= root_index;

	return ret;
}

unsigned int
bt_rebalance(void** bt) {
	unsigned int ret = 0;

	bt_item_t iter = bt_first(*bt);
	bt_item_t median = iter;
	const bt_item_t end = bt_next(bt_last(*bt));

	if(!iter)
		goto bail;

	// Find the median node.
	while(iter!=end) {
		iter = bt_next(iter);
		if(iter==end)
			break;
		iter = bt_next(iter);
		median = bt_next(median);
	}

	// Splay the tree so that the median node is at the root.
	ret += bt_splay(bt,median);

	// Rinse and repeat on both child branches.
	iter = *bt;
	ret += bt_rebalance((void**)&iter->lhs);
	ret += bt_rebalance((void**)&iter->rhs);

bail:
	return ret;
}

/* -------------------------------------------------------------------------- */

#if BTREE_SELF_TEST

#include <stdlib.h>
#include <string.h>

static int nodes_alive = 0;

struct self_test_node_s {
	struct bt_item_s item;
	char* name;
};

typedef struct self_test_node_s *self_test_node_t;

void
self_test_node_delete(self_test_node_t item, void* context) {
	free(item->name);
	memset(item, 0, sizeof(*item));
	free(item);

	// Decrement total node count.
	(*(int*)context)--;
}

bt_compare_result_t
self_test_node_compare(
	self_test_node_t lhs,
	self_test_node_t rhs,
	void* context
) {
	(void)context; // This parameter is not used. Supress warning.

	if(lhs->name == rhs->name)
		return 0;
	if(!lhs->name)
		return 1;
	if(!rhs->name)
		return -1;
	return strcmp(lhs->name, rhs->name);
}

bt_compare_result_t
self_test_node_compare_cstr(
	self_test_node_t lhs,
	const char* rhs,
	void* context
) {
	(void)context; // This parameter is not used. Supress warning.

	if(lhs->name == rhs)
		return 0;
	if(!lhs->name)
		return 1;
	if(!rhs)
		return -1;
	return strcmp(lhs->name, rhs);
}

void
forward_traversal_test(self_test_node_t root) {
	int j = 0;
	self_test_node_t iter;

	printf("Forward traversal test...");

	fflush(stdout);

	for(iter = bt_first(root); iter; iter = bt_next(iter)) {
		j++;

		if(nodes_alive < j) {
			printf("Bad node count in forward traversal, too many nodes!\n");
			exit(-1);
		}
	}

	if(nodes_alive != j) {
		printf("Bad node count in forward traversal, not enough nodes!\n");
		exit(-1);
	}
	printf("OK\n");
}

void
reverse_traversal_test(self_test_node_t root) {
	int j = 0;
	self_test_node_t iter;

	printf("Reverse traversal test...");

	fflush(stdout);

	for(iter = bt_last(root); iter; iter = bt_prev(iter)) {
		j++;
		if(nodes_alive < j) {
			printf("Bad node count in forward traversal.\n");
			exit(-1);
		}
	}

	if(nodes_alive != j) {
		printf("Bad node count in reverse traversal.\n");
		exit(-1);
	}
	printf("OK\n");
}

int
main(void) {
	int ret = 0;
	self_test_node_t root = NULL;
	unsigned char c = 0;
	int i;

	// Insert in pseudo random order. Here we are using a very simple
	// linear congruential generator with a=97, c=101, and m=2^8. It
	// will produce a somewhat randomish distribution of numbers between
	// 0 and 255. If you would like to learn more about these types of
	// pseudo random number generators, see wikipedia:
	//
	//  * <http://en.wikipedia.org/wiki/Linear_congruential_generator>
	//
again:
	printf("Inserting nodes in pseudo random order.\n");
	for(c = c * 97 + 101; c; c = c * 97 + 101) {
		self_test_node_t new_node = calloc(sizeof(struct self_test_node_s),
			1);

		asprintf(&new_node->name, "item_%d", c);

		nodes_alive++;

		bt_insert(
			(void**)&root,
			new_node,
			(bt_compare_func_t)&self_test_node_compare,
			(bt_delete_func_t)&self_test_node_delete,
			&nodes_alive
		);
	}

	printf("Inserted %d nodes.\n", (int)bt_count((void**)&root));

	if(nodes_alive != (int)bt_count((void**)&root)) {
		printf("error: Bad node count.\n");
		ret++;
	}

	printf(" * balance = %d\n",bt_get_balance(root));

	forward_traversal_test(root);
	reverse_traversal_test(root);

	bt_find((void**)&root, "item_1", &self_test_node_compare_cstr, &nodes_alive);

	printf("Removing nodes in pseudo random order.\n");
	for(c = 4 * 97 + 101; c!=4; c = c * 97 + 101) {
		char* name = NULL;

		asprintf(&name, "item_%d", (c==0)?4:c);

		if(!bt_remove(
			(void**)&root,
			name,
			(bt_compare_func_t)&self_test_node_compare_cstr,
			(bt_delete_func_t)&self_test_node_delete,
			&nodes_alive
		)) {
			printf("error: REMOVE FAILED FOR %d\n",c);
			ret++;
		}
		free(name);
		if(nodes_alive != (int)bt_count((void**)&root)) {
			printf("error: Bad node count.\n");
			ret++;
			break;
		}
		forward_traversal_test(root);
		reverse_traversal_test(root);
	}

	if(nodes_alive) {
		printf("error: Bad node count, should be zero.\n");
		ret++;
	}

	forward_traversal_test(root);
	reverse_traversal_test(root);

	printf("Inserting more nodes in pseudo random order.\n");
	for(c = 5 * 97 + 101; c; c = c * 97 + 101) {
		self_test_node_t new_node = calloc(sizeof(struct self_test_node_s),
			1);

		asprintf(&new_node->name, "item_%d", c);

		nodes_alive++;

		bt_insert(
			(void**)&root,
			new_node,
			(bt_compare_func_t)&self_test_node_compare,
			(bt_delete_func_t)&self_test_node_delete,
			&nodes_alive
		);
	}

	i = bt_rebalance((void**)&root);
	printf("Rebalance operation took %u rotations\n", i);

	printf(" * balance = %d\n",bt_get_balance(root));

	forward_traversal_test(root);
	reverse_traversal_test(root);

	i = bt_rebalance((void**)&root);
	printf("Rebalance operation took %u rotations\n", i);

	printf(" * balance = %d\n",bt_get_balance(root));

	forward_traversal_test(root);
	reverse_traversal_test(root);

	// Insert in sequential order.
	printf("Inserting nodes in sequential order.\n");
	for(i = 0; i != 255; i++) {
		self_test_node_t new_node =
			calloc(sizeof(struct self_test_node_s),1);

		asprintf(&new_node->name, "item_%d", i);

		nodes_alive++;

		bt_insert(
			(void**)&root,
			new_node,
			(bt_compare_func_t)&self_test_node_compare,
			(bt_delete_func_t)&self_test_node_delete,
			&nodes_alive
		);
	}

	printf(" * balance = %d\n",bt_get_balance(root));

	forward_traversal_test(root);
	reverse_traversal_test(root);

	i = bt_rebalance((void**)&root);
	printf("Rebalance operation took %u rotations\n", i);

	printf(" * balance = %d\n",bt_get_balance(root));

	forward_traversal_test(root);
	reverse_traversal_test(root);

	i = bt_rebalance((void**)&root);
	printf("Rebalance operation took %u rotations\n", i);

	printf(" * balance = %d\n",bt_get_balance(root));

	i = bt_unbalance((void**)&root);
	printf("Unbalance operation took %u rotations\n", i);

	printf(" * balance = %d\n",bt_get_balance(root));

	i = bt_rebalance((void**)&root);
	printf("Rebalance operation took %u rotations\n", i);

	if(bt_get_balance(root)) {
		printf(
			"error: Tree doesn't seem balanced even after rebalancing. "
			"balance = %d\n",
			bt_get_balance(root)
		);
		ret++;
	}

	i = bt_rebalance((void**)&root);
	printf("Rebalance operation took %u rotations\n", i);

	if(i != 0) {
		printf(
			"error: Rebalance operation should have been trivial, "
			"but did %d rotations anyway.\n",
			i
		);
		ret++;
	}

	forward_traversal_test(root);
	reverse_traversal_test(root);

	// Cleanup.
	printf("Removing all nodes...\n");
	while(root)
		bt_remove(
			(void**)&root,
			root,
			(bt_compare_func_t)&self_test_node_compare,
			(bt_delete_func_t)&self_test_node_delete,
			&nodes_alive
		);

	bt_find((void**)&root, "item_1", &self_test_node_compare_cstr, &nodes_alive);

	printf("Adding more nodes...\n");
	{
		self_test_node_t new_node;

		new_node = calloc(sizeof(struct self_test_node_s),1);
		asprintf(&new_node->name, "proxy");
		nodes_alive++;
		bt_insert(
			(void**)&root,
			new_node,
			(bt_compare_func_t)&self_test_node_compare,
			(bt_delete_func_t)&self_test_node_delete,
			&nodes_alive
		);

		new_node = calloc(sizeof(struct self_test_node_s),1);
		asprintf(&new_node->name, ".p");
		nodes_alive++;
		bt_insert(
			(void**)&root,
			new_node,
			(bt_compare_func_t)&self_test_node_compare,
			(bt_delete_func_t)&self_test_node_delete,
			&nodes_alive
		);

		new_node = calloc(sizeof(struct self_test_node_s),1);
		asprintf(&new_node->name, "device");
		nodes_alive++;
		bt_insert(
			(void**)&root,
			new_node,
			(bt_compare_func_t)&self_test_node_compare,
			(bt_delete_func_t)&self_test_node_delete,
			&nodes_alive
		);

		new_node = calloc(sizeof(struct self_test_node_s),1);
		asprintf(&new_node->name, "timer");
		nodes_alive++;
		bt_insert(
			(void**)&root,
			new_node,
			(bt_compare_func_t)&self_test_node_compare,
			(bt_delete_func_t)&self_test_node_delete,
			&nodes_alive
		);

		new_node = calloc(sizeof(struct self_test_node_s),1);
		asprintf(&new_node->name, "async_response");
		nodes_alive++;
		bt_insert(
			(void**)&root,
			new_node,
			(bt_compare_func_t)&self_test_node_compare,
			(bt_delete_func_t)&self_test_node_delete,
			&nodes_alive
		);

		new_node = calloc(sizeof(struct self_test_node_s),1);
		asprintf(&new_node->name, "lots_of_devices");
		nodes_alive++;
		bt_insert(
			(void**)&root,
			new_node,
			(bt_compare_func_t)&self_test_node_compare,
			(bt_delete_func_t)&self_test_node_delete,
			&nodes_alive
		);
	}

	forward_traversal_test(root);
	reverse_traversal_test(root);

	i = bt_rebalance((void**)&root);
	printf("Rebalance operation took %u rotations\n", i);

	forward_traversal_test(root);
	reverse_traversal_test(root);

	// Cleanup.
	while(root)
		bt_remove((void**)&root,
			root,
			(bt_compare_func_t)&self_test_node_compare,
			(bt_delete_func_t)&self_test_node_delete,
			&nodes_alive
		);

	// Should have no leaks at this point.
	if(nodes_alive != 0) {
		printf("error: nodes_alive = %d, when it should be 0\n", nodes_alive);
		ret++;
	}

	if(ret)
		printf("Failed with %d errors.\n",ret);
	else {
		printf("OK\n");
		//goto again;
	}

	return ret;
}

#endif

btree.h

/*	@file btree.h
**	@author Robert Quattlebaum <darco@deepdarc.com>
**
**	Originally published 2010-8-31.
**
**	This file was written by Robert Quattlebaum <darco@deepdarc.com>.
**
**	This work is provided as-is. Unless otherwise provided in writing,
**	Robert Quattlebaum makes no representations or warranties of any
**	kind concerning this work, express, implied, statutory or otherwise,
**	including without limitation warranties of title, merchantability,
**	fitness for a particular purpose, non infringement, or the absence
**	of latent or other defects, accuracy, or the present or absence of
**	errors, whether or not discoverable, all to the greatest extent
**	permissible under applicable law.
**
**	To the extent possible under law, Robert Quattlebaum has waived all
**	copyright and related or neighboring rights to this work. This work
**	is published from the United States.
**
**	I, Robert Quattlebaum, dedicate any and all copyright interest in
**	this work to the public domain. I make this dedication for the
**	benefit of the public at large and to the detriment of my heirs and
**	successors. I intend this dedication to be an overt act of
**	relinquishment in perpetuity of all present and future rights to
**	this code under copyright law. In jurisdictions where this is not
**	possible, I hereby release this code under the Creative Commons
**	Zero (CC0) license.
**
**	 * <http://creativecommons.org/publicdomain/zero/1.0/>
*/

#ifndef __BTREE_HEADER__
#define __BTREE_HEADER__ 1

#if !defined(__BEGIN_DECLS) || !defined(__END_DECLS)
#if defined(__cplusplus)
#define __BEGIN_DECLS   extern "C" {
#define __END_DECLS \
	}
#else
#define __BEGIN_DECLS
#define __END_DECLS
#endif
#endif

#include <stdbool.h>
#include <stdio.h>      // For ssize_t

__BEGIN_DECLS

struct bt_item_s;

typedef struct bt_item_s *bt_item_t;

struct bt_item_s {
	bt_item_t	lhs;
	bt_item_t	rhs;
	bt_item_t	parent;
};

typedef signed char bt_compare_result_t;

typedef bt_compare_result_t (*bt_compare_func_t)(const void* lhs,
    const void* rhs, void* context);

typedef void (*bt_delete_func_t)(void* item, void* context);

//! Inserts the given item into the tree.
extern int bt_insert(
	void**				bt,
	void*				item,
	bt_compare_func_t	compare_func,
	bt_delete_func_t	delete_func,
	void*				context);

//! Finds and returns a node matching the given criteria.
extern void* bt_find(
	void*const*			bt,
	const void*			item,
	bt_compare_func_t	compare_func,
	void*				context);

//! Removes the given item from the tree, if present.
extern bool bt_remove(
	void**				bt,
	void*				item,
	bt_compare_func_t	compare_func,
	bt_delete_func_t	delete_func,
	void*				context);

//!	Finds the left-most node in the subtree described by item.
extern void* bt_first(void* item);

//!	Finds the right-most node in the subtree described by item.
extern void* bt_last(void* item);

//!	Returns the next node in the tree, or NULL the given item is the last (right-most) node in the tree.
//! Performs an in-order depth-first traversal.
extern void* bt_next(void* item);

//!	Returns the previous node in the tree, or NULL the given item is the first (left-most) node in the tree.
//! Performs a reverse-order depth-first traversal.
extern void* bt_prev(void* item);

//!	Traverses the given tree to determine the number of nodes it contains.
extern size_t bt_count(void*const* bt);

extern int bt_get_balance(void* node);

extern void bt_rotate_left(void** pivot);

extern void bt_rotate_right(void** pivot);

extern unsigned int bt_rebalance(void** bt);

extern unsigned int bt_unbalance(void** bt);

extern unsigned int bt_splay(void** bt, void* root);

__END_DECLS

#endif

fgetln.h

/*	@file fgetln.h
**	@author Robert Quattlebaum <darco@deepdarc.com>
**
**	Originally published 2012-10-24.
**
**	This file was written by Robert Quattlebaum <darco@deepdarc.com>.
**
**	This work is provided as-is. Unless otherwise provided in writing,
**	Robert Quattlebaum makes no representations or warranties of any
**	kind concerning this work, express, implied, statutory or otherwise,
**	including without limitation warranties of title, merchantability,
**	fitness for a particular purpose, non infringement, or the absence
**	of latent or other defects, accuracy, or the present or absence of
**	errors, whether or not discoverable, all to the greatest extent
**	permissible under applicable law.
**
**	To the extent possible under law, Robert Quattlebaum has waived all
**	copyright and related or neighboring rights to this work. This work
**	is published from the United States.
**
**	I, Robert Quattlebaum, dedicate any and all copyright interest in
**	this work to the public domain. I make this dedication for the
**	benefit of the public at large and to the detriment of my heirs and
**	successors. I intend this dedication to be an overt act of
**	relinquishment in perpetuity of all present and future rights to
**	this code under copyright law. In jurisdictions where this is not
**	possible, I hereby release this code under the Creative Commons
**	Zero (CC0) license.
**
**	 * <http://creativecommons.org/publicdomain/zero/1.0/>
**
**	-------------------------------------------------------------------
**
**	This is a simple implementation of the BSD function `fgetln()`,
**	for use on operating systems which do not have a copy.
**
**	Man page URL: <http://www.openbsd.org/cgi-bin/man.cgi?query=fgetln>
**
**	NOTE: This implementation is *NOT* thread safe!
*/

#include <stdio.h>

#if !defined(HAVE_FGETLN)
#define HAVE_FGETLN	(__DARWIN_C_LEVEL>=__DARWIN_C_FULL)
#endif

#if !defined(fgetln) && !HAVE_FGETLN
static char *
fgetln_(FILE *stream, size_t *len) {
	static char* linep = NULL;
	static size_t linecap = 0;
	ssize_t length = getline(&linep,&linecap,stream);
	if(length==-1) {
		free(linep);
		linep = NULL;
		linecap = 0;
		length = 0;
	}
	if(len)
		*len = length;
	return linep;
}
#define fgetln	fgetln_
#endif

ll.h

/*	@file ll.h
**	@author Robert Quattlebaum <darco@deepdarc.com>
**
**	Originally published 2010-8-31.
**
**	This file was written by Robert Quattlebaum <darco@deepdarc.com>.
**
**	This work is provided as-is. Unless otherwise provided in writing,
**	Robert Quattlebaum makes no representations or warranties of any
**	kind concerning this work, express, implied, statutory or otherwise,
**	including without limitation warranties of title, merchantability,
**	fitness for a particular purpose, non infringement, or the absence
**	of latent or other defects, accuracy, or the present or absence of
**	errors, whether or not discoverable, all to the greatest extent
**	permissible under applicable law.
**
**	To the extent possible under law, Robert Quattlebaum has waived all
**	copyright and related or neighboring rights to this work. This work
**	is published from the United States.
**
**	I, Robert Quattlebaum, dedicate any and all copyright interest in
**	this work to the public domain. I make this dedication for the
**	benefit of the public at large and to the detriment of my heirs and
**	successors. I intend this dedication to be an overt act of
**	relinquishment in perpetuity of all present and future rights to
**	this code under copyright law. In jurisdictions where this is not
**	possible, I hereby release this code under the Creative Commons
**	Zero (CC0) license.
**
**	 * <http://creativecommons.org/publicdomain/zero/1.0/>
*/

#ifndef __LL_HEADER__
#define __LL_HEADER__ 1

#if !defined(__BEGIN_DECLS) || !defined(__END_DECLS)
#if defined(__cplusplus)
#define __BEGIN_DECLS   extern "C" {
#define __END_DECLS \
	}
#else
#define __BEGIN_DECLS
#define __END_DECLS
#endif
#endif

#include <stdbool.h>

#if LL_DEBUG
#include <assert.h>
#define LL_ASSERT(x)	assert(x)
#else
#define LL_ASSERT(x)	do { } while(0)
#endif

__BEGIN_DECLS

struct ll_item_s;
typedef struct ll_item_s *ll_item_t;
struct ll_item_s {
	ll_item_t	next;
	ll_item_t	prev;
};

typedef int ll_compare_result_t;
typedef ll_compare_result_t (*ll_compare_func_t)(const void* lhs,
    const void* rhs, void* context);

static inline void*
ll_last(
	void* item
) {
	ll_item_t iter = item;
	if(iter)
	while(iter->next) {
		iter = iter->next;
	}
	return iter;
}

static inline bool
ll_verify(void* item) {
	int ret = 0;
	ll_item_t item_ = item;
	if(item) {
		while(item_->prev)
			item_ = item_->prev;
		for(; item_->next; item_ = item_->next)
			ret++;
		for(; item_->prev; item_ = item_->prev)
			ret--;
	}

	return ret == 0;
}

static inline void
ll_insert_after(
	void* where, void* item
) {
	ll_item_t const location_ = where;
	ll_item_t const item_ = item;

	LL_ASSERT(ll_verify(where));

	item_->prev = location_;
	if((item_->next = location_->next))
		item_->next->prev = item_;
	location_->next = item_;

	LL_ASSERT(ll_verify(where));
}

static inline void
ll_insert(
	void* where, void* item
) {
	ll_item_t const location_ = where;
	ll_item_t const item_ = item;

	LL_ASSERT(ll_verify(where));

	item_->next = location_;
	item_->prev = location_->prev;
	location_->prev = item;
	if(item_->prev)
		item_->prev->next = item_;

	LL_ASSERT(ll_verify(item));
}

static inline void
ll_prepend(
	void** list, void* item
) {
	ll_insert(*list, item);
	*list = item;
	LL_ASSERT(ll_verify(*list));
}

static inline void
ll_sorted_insert(
	void** list, void* item, ll_compare_func_t compare_func, void* context
) {
	ll_item_t location_ = *list;

	LL_ASSERT(ll_verify(location_));

	if(location_) {
		while(compare_func(item, location_, context) >= 0) {
			LL_ASSERT(ll_verify(location_));
			if(location_->next) {
				location_ = location_->next;
			} else {
				// We are at the end of the list,
				// so go ahead and add us to the end.
				ll_insert_after(location_, item);
				return;
			}
		}
		if(location_!=*list)
			ll_insert(location_,item);
		else
			ll_prepend(list,item);
	} else {
		*list = item;
	}
	LL_ASSERT(ll_verify(*list));
}

static inline void
ll_remove(
	void** list, void* item
) {
	ll_item_t const item_ = item;

	LL_ASSERT(ll_verify(*list));

	if(item_->prev)
		item_->prev->next = item_->next;
	if(item_->next)
		item_->next->prev = item_->prev;
	if(*list == item_)
		*list = item_->next;

	LL_ASSERT(ll_verify(*list));
}

static inline void*
ll_pop(
	void** list
) {
	void* item = *list;
	ll_remove(list,item);
	return item;
}

static inline void
ll_push(
	void** list, void* item
) {
	if(*list)
		ll_insert_after(ll_last(*list),item);
	else
		*list = item;

	LL_ASSERT(ll_verify(*list));
}

static inline size_t
ll_count(void* item) {
	size_t ret = 0;
	ll_item_t item_ = item;

	for(; item_; item_ = item_->next)
		ret++;
	return ret;
}

__END_DECLS

#endif

url-helpers.c

/*	@file url-helpers.c
**	@author Robert Quattlebaum <darco@deepdarc.com>
**
**	Originally published 2010-8-31.
**
**	This file was written by Robert Quattlebaum <darco@deepdarc.com>.
**
**	This work is provided as-is. Unless otherwise provided in writing,
**	Robert Quattlebaum makes no representations or warranties of any
**	kind concerning this work, express, implied, statutory or otherwise,
**	including without limitation warranties of title, merchantability,
**	fitness for a particular purpose, non infringement, or the absence
**	of latent or other defects, accuracy, or the present or absence of
**	errors, whether or not discoverable, all to the greatest extent
**	permissible under applicable law.
**
**	To the extent possible under law, Robert Quattlebaum has waived all
**	copyright and related or neighboring rights to this work. This work
**	is published from the United States.
**
**	I, Robert Quattlebaum, dedicate any and all copyright interest in
**	this work to the public domain. I make this dedication for the
**	benefit of the public at large and to the detriment of my heirs and
**	successors. I intend this dedication to be an overt act of
**	relinquishment in perpetuity of all present and future rights to
**	this code under copyright law. In jurisdictions where this is not
**	possible, I hereby release this code under the Creative Commons
**	Zero (CC0) license.
**
**	 * <http://creativecommons.org/publicdomain/zero/1.0/>
**
**	See <http://www.deepdarc.com/> for other cool stuff.
*/

#include <ctype.h>
#include <string.h>
#include "assert-macros.h"
#include "url-helpers.h"

#ifdef __SDCC
#include <malloc.h>
#endif

static bool
isurlchar(char src_char) {
	return isalnum(src_char)
	   || (src_char == '$')
	   || (src_char == '-')
	   || (src_char == '_')
	   || (src_char == '.')
	   || (src_char == '+')
	   || (src_char == '!')
	   || (src_char == '*')
	   || (src_char == '\'')
	   || (src_char == '(')
	   || (src_char == ')')
	   || (src_char == ',');
}

#if __AVR__
#include <avr/pgmspace.h>
static char int_to_hex_digit(uint8_t x) {
	return pgm_read_byte_near(PSTR(
			"0123456789ABCDEF") + (x & 0xF));
}
#else
static char int_to_hex_digit(uint8_t x) {
	return "0123456789ABCDEF"[x &
	    0xF];
}
#endif

size_t
url_encode_cstr(
	char *dest, const char*src, size_t max_size
) {
	size_t ret = 0;

	if(!max_size--)
		return 0;

	while(true) {
		const char src_char = *src++;
		if(src_char==0)
			break;

		if(max_size==0) {
			ret++;
			break;
		}

		if(isurlchar(src_char)) {
			*dest++ = src_char;
			ret++;
			max_size--;
		} else if(src_char == ' ') {
			*dest++ = '+';  // Stupid legacy space encoding.
			ret++;
			max_size--;
		} else {
			if(max_size < 3) {
				// Too small for the next character.
				ret++;
				break;
			}

			*dest++ = '%';
			*dest++ = int_to_hex_digit(src_char >> 4);
			*dest++ = int_to_hex_digit(src_char & 0xF);
			ret += 3;
			max_size -= 3;
		}
	}

	*dest = 0;

	return ret;
}

static char
hex_digit_to_int(char c) {
	if(c>='0' && c<='9')
		return c-'0';
	if(c>='A' && c<='F')
		return 10+c-'A';
	if(c>='a' && c<='f')
		return 10+c-'a';
	return 0;
}

size_t
url_decode_str(
	char *dest,
	size_t max_size,
	const char* src,		// Length determined by src_len.
	size_t src_len
) {
	size_t ret = 0;

	if(!max_size--)
		return 0;

	while(src_len--) {
		const char src_char = *src++;
		if(!src_char)
			break;

		if(!max_size) {
			ret++;
			break;
		}

		if((src_char == '%')
			&& (src_len>=2)
			&& src[0]
			&& src[1]
		) {
			*dest++ = (hex_digit_to_int(src[0]) << 4) + hex_digit_to_int(
				src[1]);
			src += 2;
			src_len -= 2;
		} else if(src_char == '+') {
			*dest++ = ' ';  // Stupid legacy space encoding.
		} else {
			*dest++ = src_char;
		}

		ret++;
		max_size--;
	}

	*dest = 0;

	return ret;
}

size_t
url_decode_cstr(
	char *dest,
	const char*src,
	size_t max_size
) {
	size_t ret = 0;
#if DEBUG
	char*const dest_check = dest;
#endif

	if(!max_size--)
		goto bail;

	while(true) {
		const char src_char = *src++;
		if(!src_char) {
			break;
		}

		if(!max_size) {
			ret++;
			break;
		}

		if((src_char == '%')
			&& src[0]
			&& src[1]
		) {
			*dest++ = (hex_digit_to_int(src[0]) << 4) + hex_digit_to_int(
				src[1]);
			src += 2;
		} else if(src_char == '+') {
			*dest++ = ' ';  // Stupid legacy space encoding.
		} else {
			*dest++ = src_char;
		}

		ret++;
		max_size--;
	}

bail:
	*dest = 0;
#if DEBUG
	assert(strlen(dest_check)==ret);
#endif
	return ret;
}

void
url_decode_cstr_inplace(char *str) {
	url_decode_cstr(str, str, -1);
}

size_t
url_form_next_value(
	char** form_string, char** key, char** value, bool decodeValue
) {
	size_t bytes_parsed = 0;
	char c = **form_string;
	char* v = NULL;

	if(!c) {
		*key = NULL;
		goto bail;
	}

	*key = *form_string;

	while(true) {
		c = **form_string;

		if(!c)
			goto bail;

		if(c == '=')
			break;

		bytes_parsed++;

		if((c == ';') || (c == '&')) {
			*(*form_string)++ = 0;
			goto bail;
		}

		(*form_string)++;
	}

	// Zero terminate the key.
	if(value)
		**form_string = 0;

	(*form_string)++;

	bytes_parsed++;

	v = *form_string;

	while(true) {
		c = **form_string;

		if(!c || (c == ';') || (c == '&'))
			break;

		bytes_parsed++;
		(*form_string)++;
	}

	// Zero terminate the value
	if(*form_string[0]) {
		*(*form_string)++ = 0;
		bytes_parsed++;
	}

bail:
	if(v && decodeValue)
		url_decode_cstr_inplace(v);
	if(value)
		*value = v;

	return bytes_parsed;
}

size_t
url_path_next_component(
	char** path_string, char** component
) {
	size_t bytes_parsed = 0;
	char c = **path_string;

	if(!c) {
		*component = NULL;
		goto bail;
	}

	*component = *path_string;

	while(true) {
		c = **path_string;

		if(!c || (c == '/'))
			break;

		bytes_parsed++;
		(*path_string)++;
	}

	// Zero terminate the value
	if(*path_string[0]) {
		*(*path_string)++ = 0;
		bytes_parsed++;
	}

bail:
	if(*component)
		url_decode_cstr_inplace(*component);

	return bytes_parsed;
}

int
url_parse(
	char*	uri,
	char**	protocol,
	char**	username,	// Not yet supported: will be skipped if present.
	char**	password,	// Not yet supported: will be skipped if present.
	char**	host,
	char**	port,
	char**	path,
	char**	query
) {
	int bytes_parsed = 0;
	char tmp;

	require_string(uri, bail, "NULL uri parameter");

	if(protocol)
		*protocol = uri;

	while(*uri != ':') {
		require_string(*uri, bail, "unexpected end of string");
		uri++;
		bytes_parsed++;
	}

	// Zero terminate the protocol;
	*uri++ = 0;
	bytes_parsed++;

	require_string(*uri, bail, "unexpected end of string");

	if(uri[0] == '/' && uri[1] == '/') {
		char* addr_end;
		char* addr_begin;
		bool got_port = false;

		// Contains a hostname. Parse it.
		uri += 2;
		bytes_parsed += 2;

		addr_begin = uri;

		while( (tmp=*uri) != '/'
			&& ( isurlchar(tmp)
				|| (tmp == '[')
				|| (tmp == ']')
				|| (tmp == ':')
				|| (tmp == '@')
			)
		) {
			uri++;
			bytes_parsed++;
		}

		addr_end = uri - 1;

		if(*uri) {
			*uri++ = 0;
			bytes_parsed++;
		}

		for(;
		        (addr_end >= addr_begin) && (*addr_end != '@') &&
		        (*addr_end != '[');
		    addr_end--) {
			if(*addr_end == ']') {
				*addr_end = 0;
				got_port = true;
			} else if(!got_port && (*addr_end == ':')) {
				if(port)
					*port = addr_end + 1;
				*addr_end = 0;
				got_port = true;
			}
		}
		if(host)
			*host = addr_end + 1;
	}

	if(path)
		*path = uri;

	// Move to the end of the path.
	while( ((tmp=*uri) != '#')
		&& (tmp != '?')
		&& ( isurlchar(tmp)
			|| (tmp == '[')
			|| (tmp == ']')
			|| (tmp == ':')
			|| (tmp == '/')
			|| (tmp == '=')
			|| (tmp == '&')
			|| (tmp == '%')
		)
	) {
		uri++;
		bytes_parsed++;
	}

	// Handle query component
	if(*uri == '?') {
		*uri++ = 0;
		bytes_parsed++;

		if(query)
			*query = uri;

		// Move to the end of the query.
		while( ((tmp=*uri) != '#')
			&& ( isurlchar(tmp)
				|| (tmp == '[')
				|| (tmp == ']')
				|| (tmp == ':')
				|| (tmp == '/')
				|| (tmp == '=')
				|| (tmp == '&')
				|| (tmp == '%')
				|| (tmp == ';')
			)
		) {
			uri++;
			bytes_parsed++;
		}
	}

	// Zero terminate
	if(*uri) {
		*uri = 0;
		bytes_parsed++;
	}

bail:
	return bytes_parsed;
}

bool
url_is_absolute(const char* uri) {
	bool ret = false;
	int bytes_parsed = 0;

	require(uri, bail);

	while(*uri && isalpha(*uri) && (*uri != ':')) {
		require(*uri, bail);
		uri++;
		bytes_parsed++;
	}

	if(bytes_parsed && *uri == ':')
		ret = true;

bail:
	return ret;
}

bool
url_is_root(const char* url) {
	bool ret = false;

	require(url, bail);
	require(isalpha(url[0]),bail);

	if(url_is_absolute(url)) {
		while(*url && isalpha(*url) && (*url != ':')) {
			require(*url, bail);
			url++;
		}
		if(	(url[0] != ':')
			|| (url[1] != '/')
			|| (url[2] != '/')
		)	goto bail;

		url+=3;

		while(*url && (*url != '/')) {
			url++;
		}
	}

	while(url[0]=='/' && url[1]=='/') url++;
	ret = (url[0]==0) || ((url[0]=='/') && (url[1]==0));

bail:
	return ret;
}

//!< Used to identify IPv6 address strings
bool
string_contains_colons(const char* str) {
	if(!str)
		return false;
	for(; (*str != ':') && *str; str++) ;
	return *str == ':';
}

url-helpers.h

/*	@file url-helpers.h
**	@author Robert Quattlebaum <darco@deepdarc.com>
**
**	Originally published 2010-8-31.
**
**	This file was written by Robert Quattlebaum <darco@deepdarc.com>.
**
**	This work is provided as-is. Unless otherwise provided in writing,
**	Robert Quattlebaum makes no representations or warranties of any
**	kind concerning this work, express, implied, statutory or otherwise,
**	including without limitation warranties of title, merchantability,
**	fitness for a particular purpose, non infringement, or the absence
**	of latent or other defects, accuracy, or the present or absence of
**	errors, whether or not discoverable, all to the greatest extent
**	permissible under applicable law.
**
**	To the extent possible under law, Robert Quattlebaum has waived all
**	copyright and related or neighboring rights to this work. This work
**	is published from the United States.
**
**	I, Robert Quattlebaum, dedicate any and all copyright interest in
**	this work to the public domain. I make this dedication for the
**	benefit of the public at large and to the detriment of my heirs and
**	successors. I intend this dedication to be an overt act of
**	relinquishment in perpetuity of all present and future rights to
**	this code under copyright law. In jurisdictions where this is not
**	possible, I hereby release this code under the Creative Commons
**	Zero (CC0) license.
**
**	 * <http://creativecommons.org/publicdomain/zero/1.0/>
**
**	See <http://www.deepdarc.com/> for other cool stuff.
*/

#ifndef __URL_HELPERS_H__
#define __URL_HELPERS_H__ 1

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

#define URL_HELPERS_MAX_URL_COMPONENTS      (15)
#define MAX_URL_SIZE        (256)

/*!	Perfoms a URL encoding of the given string.
**	@returns	Number of bytes in encoded string
*/
extern size_t url_encode_cstr(
	char *dest,
	const char* src,		// Must be zero-terminated.
	size_t dest_max_size
);

extern size_t url_decode_str(
	char *dest,
	size_t dest_max_size,
	const char* src,		// Length determined by src_len.
	size_t src_len
);

/*!	Perfoms a URL decoding of the given string.
**	@returns	Number of bytes in decoded string
*/
extern size_t url_decode_cstr(
	char *dest,
	const char* src,		// Must be zero-terminated.
	size_t dest_max_size
);

extern void url_decode_cstr_inplace(char *str);

extern size_t url_form_next_value(
	char** form_string,
	char** key,
	char** value,
	bool decodeValue
);

extern size_t url_path_next_component(
	char** path_string, char** component
);

extern int url_parse(
	char*	url,
	char**	protocol,
	char**	username,
	char**	password,
	char**	host,
	char**	port,
	char**	path,
	char**	query
);
extern bool url_is_absolute(const char* url);

extern bool url_is_root(const char* url);

#if defined(__SDCC)
#define path_is_absolute(path) ((path)[0] == '/')
#else
inline static bool path_is_absolute(const char* path) { return path[0] == '/'; }
#endif

extern bool string_contains_colons(const char* str);

#endif // __URL_HELPERS_H__