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

Macros
#define	skip_list_cursor_move_to_priority(cur, ...) skip_list_cursor_move_to_priority_arr(cur, (double[]){__VA_ARGS__})
	Move a cursor to the first item with the given priority tuple. More...

#define	skip_list_remove_by_priority(sl, ...) skip_list_remove_by_priority_arr(sl, (double[]){__VA_ARGS__})
	Remove the first node found with the given priority tuple. More...

#define	skip_list_insert(lst, item, ...) skip_list_insert_arr(lst, item, (double[]){__VA_ARGS__})
	Insert an item with priority into the skip list. More...

#define	SKIP_LIST_ITERATE(cursor, item) for(; skip_list_get(cursor, (void **)&item); skip_list_next(cursor))
	Iterate over all items in a skip list (highest to lowest priority). More...

Functions
struct skip_list *	skip_list_create (unsigned priority_size, double probability)
	Create an empty skip list with priority-based sorting. More...

bool	skip_list_delete (struct skip_list *sl)
	Delete a skip list. More...

int	skip_list_size (struct skip_list *sl)
	Get the number of items in a skip list. More...

const double *	skip_list_peek_head_priority (struct skip_list *sl)
	Get the priority tuple of the first item in the skip list. More...

const void *	skip_list_peek_head (struct skip_list *sl)
	Get the first item in the skip list without removing it. More...

void *	skip_list_pop_head (struct skip_list *sl)
	Remove and return the first item in the skip list. More...

struct skip_list_cursor *	skip_list_cursor_create (struct skip_list *sl)
	Create a cursor for traversing a skip list. More...

void	skip_list_cursor_delete (struct skip_list_cursor *cur)
	Delete a previously created cursor. More...

struct skip_list_cursor *	skip_list_cursor_clone (struct skip_list_cursor *cur)
	Get a copy of an existing cursor. More...

void	skip_list_cursor_move (struct skip_list_cursor to_move, struct skip_list_cursor destination)
	Move a cursor's position to match another cursor. More...

void	skip_list_reset (struct skip_list_cursor *cur)
	Reset the position of a cursor. More...

bool	skip_list_seek (struct skip_list_cursor *cur, int index)
	Move a cursor to an item by index. More...

bool	skip_list_tell (struct skip_list_cursor cur, unsigned index)
	Get the position of a cursor within a skip list. More...

bool	skip_list_next (struct skip_list_cursor *cur)
	Move a cursor to the next item. More...

bool	skip_list_prev (struct skip_list_cursor *cur)
	Move a cursor to the previous item. More...

bool	skip_list_cursor_move_to_priority_arr (struct skip_list_cursor cur, double priority)
	Move a cursor to the first item with the given priority tuple (internal function). More...

bool	skip_list_get (struct skip_list_cursor cur, void *item)
	Get the item under a cursor. More...

const double *	skip_list_get_priority (struct skip_list_cursor *cur)
	Get the priority tuple of the item under a cursor. More...

bool	skip_list_set (struct skip_list_cursor cur, void item)
	Set the value under the cursor. More...

bool	skip_list_remove_here (struct skip_list_cursor *cur)
	Remove the item under the cursor. More...

bool	skip_list_remove (struct skip_list sl, void data)
	Remove the first node found with the given data pointer. More...

bool	skip_list_remove_by_priority_arr (struct skip_list sl, double priority)
	Remove the first node found with the given priority tuple. More...

void	skip_list_insert_arr (struct skip_list lst, void item, double *priority)
	Insert an item with priority into the skip list (internal function). More...

Detailed Description

Skip list structure built on top of list.h

A skip list is a probabilistic data structure that allows O(log n) search, insertion, and deletion. This implementation uses multiple levels of linked lists, where each level contains ceil(log(n)) elements from the level below.

Items are stored sorted by priority tuples in descending order (highest priority first). Priority tuples are compared lexicographically.

Example: Creating and populating a skip list with 2-element priority tuples

struct skip_list *sl = skip_list_create(2, 0.5);  // 2-element priority tuples, 0.5 probability
struct skip_list_cursor *cur = skip_list_cursor_create(sl);
char *apple = "apple", *banana = "banana", *cherry = "cherry";

skip_list_insert(cur, apple, 10.0, 5.0);   // Priority: (10.0, 5.0)
skip_list_insert(cur, banana, 20.0, 3.0);  // Priority: (20.0, 3.0) - highest
skip_list_insert(cur, cherry, 10.0, 8.0);  // Priority: (10.0, 8.0)

skip_list_cursor_delete(cur);
skip_list_delete(sl);

Example: Iterating through all items (in priority order)

struct skip_list_cursor *cur = skip_list_cursor_create(sl);
skip_list_seek(cur, 0);

void *item;
do {
    if (skip_list_get(cur, &item)) {
        printf("%s\n", (char *)item);  // Prints: banana, cherry, apple
    }
} while (skip_list_next(cur));

skip_list_cursor_delete(cur);

Macro Definition Documentation

◆ skip_list_cursor_move_to_priority

#define skip_list_cursor_move_to_priority	(	cur,
		...
	)	skip_list_cursor_move_to_priority_arr(cur, (double[]){__VA_ARGS__})

Move a cursor to the first item with the given priority tuple.

This uses the skip list structure for faster O(log n) lookup. Priority values should be passed as doubles matching the priority_size from skip_list_create.

Parameters

cur	The cursor to move.
...	Priority values (doubles) matching the priority_size.

Returns: true if the cursor moved to an item with matching priority.; false if no item with that priority was found.

◆ skip_list_remove_by_priority

#define skip_list_remove_by_priority	(	sl,
		...
	)	skip_list_remove_by_priority_arr(sl, (double[]){__VA_ARGS__})

Remove the first node found with the given priority tuple.

This uses the skip list structure for faster O(log n) lookup.

Parameters

sl	The skip list to search.
...	Priority values (doubles) matching the priority_size.

Returns: true if an item was successfully removed.; false if no item with that priority was found.

◆ skip_list_insert

#define skip_list_insert	(	lst,
		item,
		...
	)	skip_list_insert_arr(lst, item, (double[]){__VA_ARGS__})

Insert an item with priority into the skip list.

Items are automatically inserted in sorted order by priority (high to low). Priority values should be passed as doubles matching the priority_size from skip_list_create.

Example for priority_size=2: skip_list_insert(cur, data, 10.0, 5.0);

Example for priority_size=3: skip_list_insert(cur, data, 10.0, 5.0, 2.5);

Parameters

lst	The skip list to insert into.
item	The pointer to insert.
...	Priority values (doubles) matching the priority_size.

◆ SKIP_LIST_ITERATE

#define SKIP_LIST_ITERATE	(	cursor,
		item
	)	for(; skip_list_get(cursor, (void **)&item); skip_list_next(cursor))

Iterate over all items in a skip list (highest to lowest priority).

These macros provide a convenient way to iterate over all items while maintaining a cursor that points to the current item during each iteration.

Parameters

cursor	A pre-existing cursor (struct skip_list_cursor *) that will be positioned at each item during iteration. Can be used to modify or remove the current item. Iteration starts at the position of that the cursor is currently at.
item	A pointer variable that will receive each item's data.

Example usage:

struct skip_list *sl = skip_list_create(1, 0.5);
struct skip_list_cursor *cur = skip_list_cursor_create(sl);
struct my_data *data;

// Insert some items...

skip_list_seek(cur, 0);
SKIP_LIST_ITERATE_START(cur, data)
    printf("Processing: %s\n", data->name);
    if (should_remove(data)) {
        skip_list_remove_here(cur);
    }
SKIP_LIST_ITERATE_END(cur)

skip_list_cursor_delete(cur);

Note: The cursor is valid during each iteration and can be used with skip_list_remove_here(), skip_list_get_priority(), etc.; Safe to use break/continue within the loop body.

Function Documentation

◆ skip_list_create()

struct skip_list* skip_list_create	(	unsigned	priority_size,
		double	probability
	)

Create an empty skip list with priority-based sorting.

Items are sorted by priority tuples in descending (high to low) order. Priority tuples are compared lexicographically.

Parameters

priority_size	The number of doubles in each priority tuple.
probability	The probability (0 < p <= 0.5) of promoting an item to the next level (default: 0.5).

Returns: A pointer to the newly created skip list.

◆ skip_list_delete()

bool skip_list_delete ( struct skip_list * sl )

Delete a skip list.

The caller is responsible for removing all items before deleting. If the skip list is non-empty or there are living cursors, this call fails.

Parameters

sl	The skip list to delete.

Returns: true if the skip list was deleted.; false if the skip list is non-empty or there are live cursors.

◆ skip_list_size()

int skip_list_size ( struct skip_list * sl )

Get the number of items in a skip list.

Parameters

sl	The skip list to examine.

Returns: The number of items in the skip list.

◆ skip_list_peek_head_priority()

const double* skip_list_peek_head_priority ( struct skip_list * sl )

Get the priority tuple of the first item in the skip list.

Parameters

sl	The skip list to examine.

Returns: Pointer to the priority array (owned by the struct skip_list), or NULL if list is empty.

◆ skip_list_peek_head()

const void* skip_list_peek_head ( struct skip_list * sl )

Get the first item in the skip list without removing it.

Parameters

sl	The skip list to examine.

Returns: Pointer to the first item, or NULL if list is empty.

◆ skip_list_pop_head()

void* skip_list_pop_head ( struct skip_list * sl )

Remove and return the first item in the skip list.

Parameters

sl	The skip list to examine.

Returns: Pointer to the removed item, or NULL if list is empty.

◆ skip_list_cursor_create()

struct skip_list_cursor* skip_list_cursor_create ( struct skip_list * sl )

Create a cursor for traversing a skip list.

Parameters

sl	The skip list to create a cursor for.

Returns: A new cursor positioned at no item (use skip_list_seek to position it).

◆ skip_list_cursor_delete()

void skip_list_cursor_delete ( struct skip_list_cursor * cur )

Delete a previously created cursor.

Parameters

cur	The cursor to free.

◆ skip_list_cursor_clone()

struct skip_list_cursor* skip_list_cursor_clone ( struct skip_list_cursor * cur )

Get a copy of an existing cursor.

Parameters

cur	The cursor to clone.

Returns: A new cursor at the same position.

◆ skip_list_cursor_move()

void skip_list_cursor_move	(	struct skip_list_cursor *	to_move,
		struct skip_list_cursor *	destination
	)

Move a cursor's position to match another cursor.

After this call, to_move will point to the same item as destination.

Parameters

to_move	The cursor whose position will be updated.
destination	The source cursor whose position will be copied.

◆ skip_list_reset()

void skip_list_reset ( struct skip_list_cursor * cur )

Reset the position of a cursor.

Parameters

cur	The cursor to reset.

◆ skip_list_seek()

bool skip_list_seek	(	struct skip_list_cursor *	cur,
		int	index
	)

Move a cursor to an item by index.

Parameters

cur	The cursor to move.
index	The position (negative indices from the tail).

Returns: true if the cursor moved.; false if the index is out of bounds.

◆ skip_list_tell()

bool skip_list_tell	(	struct skip_list_cursor *	cur,
		unsigned *	index
	)

Get the position of a cursor within a skip list.

Parameters

cur	The cursor to check.
index	The location to store the index.

Returns: true if the cursor's index was written.; false if the cursor position is undefined.

◆ skip_list_next()

bool skip_list_next ( struct skip_list_cursor * cur )

Move a cursor to the next item.

Parameters

cur	The cursor to move.

Returns: true if the cursor moved to the next item.; false if the cursor moved off the end.

◆ skip_list_prev()

bool skip_list_prev ( struct skip_list_cursor * cur )

Move a cursor to the previous item.

Parameters

cur	The cursor to move.

Returns: true if the cursor moved to the previous item.; false if the cursor moved off the beginning.

◆ skip_list_cursor_move_to_priority_arr()

bool skip_list_cursor_move_to_priority_arr	(	struct skip_list_cursor *	cur,
		double *	priority
	)

Move a cursor to the first item with the given priority tuple (internal function).

This uses the skip list structure for faster O(log n) lookup. Use the skip_list_cursor_move_to_priority macro instead of calling this directly.

Parameters

cur	The cursor to move.
priority	Array of doubles representing the priority tuple to find.

Returns: true if the cursor moved to an item with matching priority.; false if no item with that priority was found.

◆ skip_list_get()

bool skip_list_get	(	struct skip_list_cursor *	cur,
		void **	item
	)

Get the item under a cursor.

Parameters

cur	The cursor to look at.
item	The location to store the value.

Returns: true if the value was stored.; false if the cursor position is undefined.

◆ skip_list_get_priority()

const double* skip_list_get_priority ( struct skip_list_cursor * cur )

Get the priority tuple of the item under a cursor.

Parameters

cur	The cursor to look at.

Returns: Pointer to the priority array (owned by the struct skip_list), or NULL if cursor position is undefined.

◆ skip_list_set()

bool skip_list_set	(	struct skip_list_cursor *	cur,
		void *	item
	)

Set the value under the cursor.

Parameters

cur	The cursor position to set.
item	The value to set.

Returns: true on success.; false if the cursor position is undefined.

◆ skip_list_remove_here()

bool skip_list_remove_here ( struct skip_list_cursor * cur )

Remove the item under the cursor.

Parameters

cur	The cursor to use.

Returns: true if an item was successfully removed.; false if the cursor position is undefined.

◆ skip_list_remove()

bool skip_list_remove	(	struct skip_list *	sl,
		void *	data
	)

Remove the first node found with the given data pointer.

Parameters

sl	The skip list to search.
data	The data pointer to find and remove.

Returns: true if an item was successfully removed.; false if the item was not found.

◆ skip_list_remove_by_priority_arr()

bool skip_list_remove_by_priority_arr	(	struct skip_list *	sl,
		double *	priority
	)

Remove the first node found with the given priority tuple.

This uses the skip list structure for faster O(log n) lookup.

Parameters

sl	The skip list to search.
priority	Array of doubles representing the priority tuple to find and remove.

Returns: true if an item was successfully removed.; false if no item with that priority was found.

◆ skip_list_insert_arr()

void skip_list_insert_arr	(	struct skip_list *	lst,
		void *	item,
		double *	priority
	)

Insert an item with priority into the skip list (internal function).

Items are inserted in sorted order by priority (descending). Use the skip_list_insert macro instead of calling this directly.

Parameters

lst	The skip list to insert into.
item	The pointer to insert.
priority	Array of doubles representing the priority tuple.

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ skip_list_cursor_move_to_priority

◆ skip_list_remove_by_priority

◆ skip_list_insert

◆ SKIP_LIST_ITERATE

Function Documentation

◆ skip_list_create()

◆ skip_list_delete()

◆ skip_list_size()

◆ skip_list_peek_head_priority()

◆ skip_list_peek_head()

◆ skip_list_pop_head()

◆ skip_list_cursor_create()

◆ skip_list_cursor_delete()

◆ skip_list_cursor_clone()

◆ skip_list_cursor_move()

◆ skip_list_reset()

◆ skip_list_seek()

◆ skip_list_tell()

◆ skip_list_next()

◆ skip_list_prev()

◆ skip_list_cursor_move_to_priority_arr()

◆ skip_list_get()

◆ skip_list_get_priority()

◆ skip_list_set()

◆ skip_list_remove_here()

◆ skip_list_remove()

◆ skip_list_remove_by_priority_arr()

◆ skip_list_insert_arr()