temelia/src/skip_list.c

/*!
 Temelia - Skip-list implementation source file.

 Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#include "include/skip_list.h"
#include "include/common.h"
#include <stdlib.h>

struct _skip_list_t
{
	/*! key reference */
	void *key;

	/*! node's level */
	int level;

	/*! array of pointers to neighbors */
	struct _skip_list_t **next;
};

static INLINE int _calculate_level(int max_level);

skip_list_t skip_list_new(int max_level)
{
	int i;
	skip_list_t skip_list;

	_ASSERT(max_level, <=, 0, INVALID_INPUT, NULL);

	/*
	 * The first node in a skip list is used as sentinel; it doesn't store any key.
	 */
	skip_list = (struct _skip_list_t *) _new(sizeof(struct _skip_list_t));

	_ASSERT(skip_list, ==, NULL, NULL_POINTER, NULL);

	skip_list->key = NULL;
	skip_list->level = max_level;
	skip_list->next = (struct _skip_list_t **) _new(max_level
			* sizeof(struct _skip_list_t *));

	if (skip_list->next == NULL)
	{
		_delete(skip_list);
		temelia_errno = NULL_POINTER;
		return NULL;
	}

	for (i = 0; i < max_level; i++)
		skip_list->next[i] = NULL;
	return skip_list;
}

void skip_list_node_delete(skip_list_t skip_list)
{
	int i;

	_ASSERT(skip_list, ==, NULL, NULL_POINTER,);

	for (i = 0; i < skip_list->level; i++)
		skip_list->next[i] = NULL;
	skip_list->level = 0;
	skip_list->key = NULL;
	_delete(skip_list->next);
	_delete(skip_list);
}

void *skip_list_node_get_key(skip_list_t skip_list)
{
	_ASSERT(skip_list, ==, NULL, NULL_POINTER, NULL);

	return skip_list->key;
}

void skip_list_node_set_key(skip_list_t skip_list, void *key)
{
	_ASSERT(skip_list, ==, NULL, NULL_POINTER,);

	skip_list->key = key;
}

int skip_list_node_get_level(skip_list_t skip_list)
{
	_ASSERT(skip_list, ==, NULL, NULL_POINTER, -1);

	return skip_list->level;
}

void *skip_list_node_get_next(skip_list_t skip_list)
{
	_ASSERT(skip_list, ==, NULL, NULL_POINTER, NULL);

	return skip_list->next;
}

void *skip_list_node_get_next_level(skip_list_t skip_list, int level)
{
	_ASSERT(skip_list, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(level, <, 0, INVALID_INPUT, NULL);
	_ASSERT(level, >=, skip_list->level, INVALID_INPUT, NULL);

	return skip_list->next[level];
}

void skip_list_delete(skip_list_t skip_list)
{
	skip_list_t it, prev;

	_ASSERT(skip_list, ==, NULL, NULL_POINTER,);

	it = skip_list;

	while (it)
	{
		prev = it;
		it = it->next[0];
		skip_list_node_delete(prev);
	}
}

skip_list_t skip_list_insert(skip_list_t skip_list, void *key, int compare(
		void *x, void *y, void *context), void *context)
{
	skip_list_t *prevs, add, it;
	int level, i;

	_ASSERT(skip_list, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(compare, ==, NULL, NULL_POINTER, NULL);

	prevs = (skip_list_t *) _new(skip_list->level * sizeof(skip_list_t));

	it = skip_list;

	for (level = skip_list->level - 1; level >= 0; level--)
	{
		while (it->next[level] != NULL && compare(it->next[level]->key, key,
				context) < 0)
			it = it->next[level];
		prevs[level] = it;
	}

	// Key already exists.
	if (it->next[0] && !compare(it->next[0]->key, key, context))
	{
		_delete(prevs);

		/*
		 * FIXME: return NULL if key already exists in skip-list ?
		 * Or return the node containing that key ?
		 */
		return NULL;
		//return it->next[0];
	}

	level = _calculate_level(skip_list->level);

	add = skip_list_new(level);
	_ASSERT(add, ==, NULL, NULL_POINTER, NULL);
	add->key = key;

	for (i = 0; i < level; i++)
	{
		add->next[i] = prevs[i]->next[i];
		prevs[i]->next[i] = add;
	}

	_delete(prevs);
	return add;
}

skip_list_t skip_list_search(skip_list_t skip_list, void *key, int compare(
		void *x, void *y, void *context), void *context)
{
	skip_list_t *prevs;
	skip_list_t it;
	int level;

	_ASSERT(skip_list, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(compare, ==, NULL, NULL_POINTER, NULL);

	prevs = (skip_list_t *) _new(skip_list->level * sizeof(skip_list_t));

	it = skip_list;

	for (level = skip_list->level - 1; level >= 0; level--)
	{
		while (it->next[level] != NULL && compare(it->next[level]->key, key,
				context) < 0)
			it = it->next[level];
		prevs[level] = it;
	}

	// return NULL if key isn't found.
	if (it->next[0] == NULL || compare(it->next[0]->key, key, context))
	{
		_delete(prevs);
		return NULL;
	}

	_delete(prevs);
	return it->next[0];
}

int skip_list_remove(skip_list_t skip_list, void *key, int compare(void *x,
		void *y, void *context), void *context)
{
	skip_list_t *prevs;
	skip_list_t it;
	int level, i;

	_ASSERT(skip_list, ==, NULL, NULL_POINTER, -1);
	_ASSERT(compare, ==, NULL, NULL_POINTER, -1);

	prevs = (skip_list_t *) _new(skip_list->level * sizeof(skip_list_t));

	it = skip_list;

	for (level = skip_list->level - 1; level >= 0; level--)
	{
		while (it->next[level] != NULL && compare(it->next[level]->key, key,
				context) < 0)
			it = it->next[level];
		prevs[level] = it;
	}

	// return NULL if key isn't found.
	if (it->next[0] == NULL || compare(it->next[0]->key, key, context))
	{
		_delete(prevs);
		return 0;
	}

	it = it->next[0];
	for (i = 0; i < it->level; i++)
		prevs[i]->next[i] = it->next[i];

	_delete(prevs);
	skip_list_node_delete(it);
	return 1;
}

void skip_list_iterate(skip_list_t skip_list_, void key_handler(void *x,
		void *context), void *context)
{
	skip_list_t it;
	_ASSERT(skip_list_, ==, NULL, NULL_POINTER,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	for (it = skip_list_->next[0]; it != NULL; key_handler(it->key, context), it
			= it->next[0])
		;
}

void skip_list_iterate_level(skip_list_t skip_list_, int level,
		void key_handler(void *x, void *context), void *context)
{
	skip_list_t it;

	_ASSERT(skip_list_, ==, NULL, NULL_POINTER,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);
	_ASSERT(level, <, 0, INVALID_INPUT,);
	_ASSERT(level, >=, skip_list_->level, INVALID_INPUT,);

	it = skip_list_->next[level];

	while (it)
	{
		key_handler(it->key, context);
		it = it->next[level];
	}
}

static INLINE int _calculate_level(int max_level)
{
	int level = 1;

	while (_rand() % 2)
		++level;

	return level;
}