pre { line-height: 125%; }
td.linenos .normal { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
span.linenos { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
td.linenos .special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .ges { font-weight: bold; font-style: italic } /* Generic.EmphStrong */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; backgroun
/*
This is used for quick userlist insertion and lookup. It's not really
a tree, but it could be :)
*/

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

#include "tree.h"

#define ARRAY_GROW 32

struct _tree
{
	int elements;
	int array_size;
	void **array;
	tree_cmp_func *cmp;
	void *data;
};

tree *
tree_new (tree_cmp_func *cmp, void *data)
{
	tree *t = calloc (1, sizeof (tree));
	t->cmp = cmp;
	t->data = data;
	return t;
}

void
tree_destroy (tree *t)
{
	if (t)
	{
		if (t->array)
			free (t->array);
		free (t);
	}
}

static int
tree_find_insertion_pos (tree *t, void *key, int *done)
{
	int c, u, l, idx;

	if (t->elements < 1)
	{
		*done = 1;
		t->array[0] = key;
		t->elements++;
		return 0;
	}

	if (t->elements < 2)
	{
		*done = 1;
		c = t->cmp (key, t->array[0], t->data);
		if (c == 0)
			return -1;
		t->elements++;
		if (c > 0)
		{
			t->array[1] = key;
			return 1;
		}
		t->array[1] = t->array[0];
		t->array[0] = key;
		return 0;
	}

	*done = 0;

	c = t->cmp (key, t->array[0], t->data);
	if (c < 0)
		return 0;	/* prepend */

	c = t->cmp (key, t->array[t->elements - 1], t->data);
	if (c > 0)
		return t->elements;	/* append */

	l = 0;
	u = t->elements - 1;
	while (1)
	{
		idx = (l + u) / 2;
		c = t->cmp (key, t->array[idx], t->data);

		if (0 > c)
			u = idx;
		else if (0 < c && 0 > t->cmp (key, t->array[idx+1], t->data))
			return idx + 1;
		else if (c == 0)
			return -1;
		else
			l = idx + 1;
	}
}

static void
tree_insert_at_pos (tree *t, void *key, int pos)
{
	int post_bytes;

	/* append is easy */
	if (pos != t->elements)
	{
		post_bytes = (t->elements - pos) * sizeof (void *);
		memmove (&t->array[pos + 1], &t->array[pos], post_bytes);
	}

	t->array[pos] = key;
	t->elements++;
}

static void *
mybsearch (const void *key, void **array, size_t nmemb,
			  int (*compar) (const void *, const void *, void *data), void *data, int *pos)
{
	int l, u, idx;
	int comparison;

	l = 0;
	u = nmemb;
	while (l < u)
	{
		idx = (l + u) / 2;
		comparison = (*compar) (key, array[idx], data);
		if (comparison < 0)
			u = idx;
		else if (comparison > 0)
			l = idx + 1;
		else
		{
			*pos = idx;
			return array[idx];
		}
	}

	return NULL;
}

void *
tree_find (tree *t, void *key, tree_cmp_func *cmp, void *data, int *pos)
{
	if (!t || !t->array)
		return NULL;

	return mybsearch (key, &t->array[0], t->elements, cmp, data, pos);
}

static void
tree_remove_at_pos (tree *t, int pos)
{
	int post_bytes;

	t->elements--;
	if (pos != t->elements)
	{
		post_bytes = (t->elements - pos) * sizeof (void *);
		memmove (&t->array[pos], &t->array[pos + 1], post_bytes);
	}
}

int
tree_remove (tree *t, void *key, int *pos)
{
	void *data;

	data = tree_find (t, key, t->cmp, t->data, pos);
	if (!data)
		return 0;

	tree_remove_at_pos (t, *pos);
	return 1;
}

void
tree_foreach (tree *t, tree_traverse_func *func, void *data)
{
	int j;

	if (!t || !t->array)
		return;

	for (j = 0; j < t->elements; j++)
	{
		if (!func (t->array[j], data))
			break;
	}
}

int
tree_insert (tree *t, void *key)
{
	int pos, done;

	if (!t)
		return -1;

	if (t->array_size < t->elements + 1)
	{
		int new_size = t->array_size + ARRAY_GROW;

		t->array = realloc (t->array, sizeof (void *) * new_size);
		t->array_size = new_size;
	}

	pos = tree_find_insertion_pos (t, key, &done);
	if (!done && pos != -1)
		tree_insert_at_pos (t, key, pos);

	return pos;
}