temelia/release/include/skip_list.h

/*!
 Temelia - Skip-list interface.

 Copyright (C) 2008, 2009 Ceata (http://cod.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.
 */

#ifndef SKIPLIST_H_
#define SKIPLIST_H_

#include "platform.h"

struct _skip_list_t;
typedef struct _skip_list_t *skip_list_t;

/*!
 * @brief Constructor - returns an empty skip list with given maximum level.
 * Complexity O(1)
 *
 * @param Max level
 */
DECLSPEC skip_list_t skip_list_new(int max_level);

/*!
 * @brief Destructor - frees the memory occupied by skip-list node.
 * Complexity O(1)
 *
 * @param Skip-list
 */
DECLSPEC void skip_list_node_delete(skip_list_t skip_list);

/*!
 * @brief Returns the key stored in node.
 * Complexity O(1)
 *
 * @param Skip-list node
 */
DECLSPEC void *skip_list_node_get_key(skip_list_t skip_list);

/*!
 * @brief Sets the key stored in node.
 * Complexity O(1)
 *
 * @param Skip-list node
 * @param Key
 */
DECLSPEC void skip_list_node_set_key(skip_list_t skip_list, void *key);

/*!
 * @brief Returns the maximum level of node.
 * Complexity O(1)
 *
 * @param Skip-list node
 */
DECLSPEC int skip_list_node_get_level(skip_list_t skip_list);

/*!
 * @brief Returns the next nodes; in order to use it
 * cast to (skip_list_t *), the last element is NULL.
 * Complexity O(1)
 *
 * @param Skip-list node
 */
DECLSPEC void *skip_list_node_get_next(skip_list_t skip_list);

/*!
 * @brief Returns the next node at given level.
 * Complexity O(1)
 *
 * @param Skip-list node
 * @param Level
 */
DECLSPEC void *skip_list_node_get_next_level(skip_list_t skip_list, int level);

/*!
 * @brief Destructor - frees the memory occupied by skip-list, by calling
 * skip_list_node_delete for each list's node.
 * Complexity O(n)
 *
 * @param Skip-list
 */
DECLSPEC void skip_list_delete(skip_list_t skip_list);

/*!
 * @brief Inserts a key in skip list. Returns a pointer to the node in which the key was added.
 * Complexity O(log(n))
 *
 * @param Skip list
 * @param Key
 * @param Pointer to comparison function
 * @param Comparison context
 */
DECLSPEC skip_list_t skip_list_insert(skip_list_t skip_list, void *key, int compare(
		void *x, void *y, void *context), void *context);

/*!
 * @brief Searches for key in skip-list.
 * Complexity O(log(n))
 *
 * @param Skip list
 * @param Key
 * @param Pointer to comparison function
 * @param Comparison context
 */
DECLSPEC skip_list_t skip_list_search(skip_list_t skip_list, void *key, int compare(
		void *x, void *y, void *context), void *context);

/*!
 * @brief Removes key from skip-list. Returns 1 if key removed successfully other value if an error
 * occurred.
 * Complexity O(log(n))
 *
 * @param Skip list
 * @param Key
 * @param Pointer to comparison function
 * @param Comparison context
 */
DECLSPEC int skip_list_remove(skip_list_t skip_list, void *key, int compare(void *x,
		void *y, void *context), void *context);

/*!
 * @brief Prints skip list by levels: for each key from level it calls skip_list_print_level
 * with the key and with NULL at the end.
 * Complexity O(n * log(n))
 *
 * @param Skip list
 * @param Pointer to iterating function
 * @param Comparison context
 */
DECLSPEC void skip_list_iterate(skip_list_t skip_list, void key_handler(void *x,
		void *context), void *context);

/*!
 * @brief Prints the keys of skip list, found on given level.
 * Complexity O(n) down to O(log(n)) depending on the level
 *
 * @param Skip list
 * @param Level
 * @param Pointer to iterating function
 * @param Comparison context
 */
DECLSPEC void skip_list_iterate_level(skip_list_t skip_list_, int level,
		void key_handler(void *x, void *fout), void *context);

#endif /* SKIPLIST_H_ */