C-Skiplist API Reference

The Setup

The rest of the reference will refer to the following structure in examples:

typedef struct {
  char *key;
  int id;
  int value;
} test_t;

Core Types

• skiplist_t

The core skiplist structure.

skiplist_t list;

• skiplist_cmp_t = intmax_t

A comparison result – a negative number means less than, a positive number means greater than, and zero means equality. The SKIPLISTCMP\* constants can be used for clarity or convenience.

• skiplist_length_t = uintmax_t

A skiplist's length – the number of values it holds.

Callback Functions

• skiplist_cmp_fn

Compare list_value and user_value to determine sorting. A return value less than or equal to SKIPLIST_CMP_LT – a negative number – means list_value should be before user_value. A return value equal to SKIPLIST_CMP_EQ – zero – means list_value is user_value. A return value greater than or equal to SKIPLIST_CMP_GT – a positive number – means list_value should be after user_value.

typedef skiplist_cmp_t (*skiplist_cmp_fn)(const void *list_value,
                                          const void *user_value);

Given a compare function like:

skiplist_cmp_t cmp(const void *list_value, const void *user_value) {
  const test_t *l = list_value;
  const test_t *u = user_value;

  return strcmp(l->key, u->key);
}

The skiplist_set_cmp_fn function could be used to associate it with a skiplist:

skiplist_set_cmp_fn(&list, cmp);

• skiplist_search_fn

Used by skiplist_search to compare a skiplist value to a search value.

typedef skiplist_cmp_t (*skiplist_search_fn)(const void *value,
                                             const void *search);

The following search function could be used to search for a test_t by its key – a string:

skiplist_cmp_t search(const void *value, const void *search) {
  const test_t *test = value;
  const char *search_key = search;

  return strcmp(test->key, search_key);
}

It could be associated with a skiplist using skiplist_set_search_fn:

skiplist_set_search_fn(&list, search);

The skiplist_search function could then be used like:

test_t *found_test = skiplist_search(&list, "abcdef");

• skiplist_destroy_fn

Optionally used by skiplist_delete and skiplist_destroy to destroy the value of a node.

typedef void (*skiplist_destroy_fn)(void *value);

If each value is simple and allocated on the heap, then a function like this would work in most cases:

void destroy(void *value) {
  free(value);
}

• skiplist_inspect_fn

Optionally used by skiplist_inspect to pretty-print the value of a node.

typedef bool (*skiplist_inspect_fn)(const void *value, char buffer[],
                                    const size_t buffer_size);

The snprintf function is fine for this task:

bool inspect(const void *value, char buffer[],
             const size_t buffer_size)
{
  const test_t *test = value;

  return snprintf(buffer, buffer_size, "%s: {id: %d, value: %d}", test->key,
                                                                  test->id,
                                                                  test->value) > 0;
}

The skiplist_set_inspect_fn function is used to associate an inspect function with a skiplist:

skiplist_set_inspect_fn(&list, inspect);

Constants

• SKIPLIST_CMP_LT = -1
• SKIPLIST_CMP_EQ = 0
• SKIPLIST_CMP_GT = 1

The SKIPLISTCMP\* constants can be used to clarify a comparison result:

skiplist_cmp_t cmp(const void *list_value, const void *user_value) {
  const test_t *l = list_value;
  const test_t *u = user_value;

  if (l->id < u->id)
    return SKIPLIST_CMP_LT;

  if (l->id > u->id)
    return SKIPLIST_CMP_GT;

  return SKIPLIST_CMP_EQ;
}

Initialization and Destruction Functions

• void skiplist_global_init(void)

Initialize the random number environment used for generating skiplist levels:

void skiplist_global_init(void) {
  srand(time(NULL));
}

If your application already does something similar, then this function can be ignored. Otherwise, this function is mandatory.

• bool skiplist_init(skiplist_t *list)

Initialize list. Return true on success and false on failure. This function is mandatory and should be the first function called on list.

• void skiplist_destroy(skiplist_t *list)

Destroy list and free any used memory. If list has a destroy function, it will be used on each value. This function is mandatory if list has been initialized.

Callback-Setter Functions

• void skiplist_set_cmp_fn(skiplist_t *list, skiplist_cmp_fn fn)

Set list's compare function to fn. This function is mandatory.

• void skiplist_set_search_fn(skiplist_t *list, skiplist_search_fn fn)

Set list's search function to fn. This function is mandatory to use skiplist_search.

• void skiplist_set_destroy_fn(skiplist_t *list, skiplist_destroy_fn fn)

Set list's destroy function to fn.

• void skiplist_set_inspect_fn(skiplist_t *list, skiplist_inspect_fn fn)

Set list's inspect function to fn.

Operation Functions

• bool skiplist_insert(skiplist_t *list, void *value)

Insert value into list. Return true if value was inserted or already exists and false otherwise. If value equals an existing value, as determined by list's compare function, the existing value will be deleted and value will be inserted.

• bool skiplist_delete(skiplist_t *list, const void *value)

Delete value from list. Return true if value was deleted and false otherwise. If list has a destroy function, it will be used to destroy the deleted value.

• bool skiplist_contains(const skiplist_t *list, const void *value)

Check if list contains value, as determined by list's compare function. Return true if so and false if not.

• void *skiplist_search(skiplist_t *list, const void *search)

Search list for a value that matches search, as determined by list's search function. Return the matching value or NULL if one wasn't found.

Inspection Functions

• skiplist_length_t skiplist_length(const skiplist_t *list)

Get the number of values in list.

• void skiplist_inspect(const skiplist_t *list, FILE *stream)

Pretty-print the nodes in list to stream. Output resembles the following when list has no inspect function – the default:

Header 0xc2c010 {level: 5}
  |5| -> (nil)
  |4| -> 0xc2c090
  |3| -> 0xc2c090
  |2| -> 0xc2c090
  |1| -> 0xc2c090
  |0| -> 0xc2c230
Node 0xc2c230 {level: 0}
  |0| -> 0xc2c090
Node 0xc2c090 {level: 4}
  |4| -> (nil)
  |3| -> 0xc2c1c0
  |2| -> 0xc2c1c0
  |1| -> 0xc2c1c0
  |0| -> 0xc2c1c0
Node 0xc2c1c0 {level: 3}
  |3| -> (nil)
  |2| -> 0xc2c100
  |1| -> 0xc2c100
  |0| -> 0xc2c100
Node 0xc2c100 {level: 2}
  |2| -> (nil)
  |1| -> (nil)
  |0| -> (nil)

With an inspect function like this:

bool inspect(const void *value, char buffer[],
             const skiplist_inspect_size_t buffer_size)
{
  const test_t *test = value;

  return snprintf(buffer, buffer_size, "{%s: %d}", test->key,
                                                   test->value);
}

Output would resemble:

Header 0xc2c010 {level: 5}
  |5| -> (nil)
  |4| -> 0xc2c090
  |3| -> 0xc2c090
  |2| -> 0xc2c090
  |1| -> 0xc2c090
  |0| -> 0xc2c230
Node 0xc2c230 {level: 0, value: {def: 2}}
  |0| -> 0xc2c090
Node 0xc2c090 {level: 4, value: {ghi: 4}}
  |4| -> (nil)
  |3| -> 0xc2c1c0
  |2| -> 0xc2c1c0
  |1| -> 0xc2c1c0
  |0| -> 0xc2c1c0
Node 0xc2c1c0 {level: 3, value: {jkl: 5}}
  |3| -> (nil)
  |2| -> 0xc2c100
  |1| -> 0xc2c100
  |0| -> 0xc2c100
Node 0xc2c100 {level: 2, value: {mno: 6}}
  |2| -> (nil)
  |1| -> (nil)
  |0| -> (nil)

Iteration

Iteration is supported through the skiplistiter\* type and functions. Values are yielded as they're sorted in the skiplist.

skiplist_iter_t iter;
skiplist_iter_init(&iter, &list);

test_t *test;
while ((test = skiplist_iter_next(&iter)))
  printf("Got value %d\n", test->value);

• skiplist_iter_t

An iterator that's associated with a skiplist on initialization.

• void skiplist_iter_init(skiplist_iter_t *iter, skiplist_t *list)

Initialize iter and associate it with list. This function is mandatory and must be the first function called on iter.

• void skiplist_iter_reset(skiplist_iter_t *iter)

Reset iter to the beginning of its associated skiplist – the first value.

• void *skiplist_iter_next(skiplist_iter_t *iter)

Return the next value from iter or NULL if there are no more.

For Example

This code:

skiplist_cmp_t cmp(const void *list_value, const void *user_value) {
  const test_t *l = list_value;
  const test_t *u = user_value;

  return strcmp(l->key, u->key);
}

skiplist_cmp_t search(const void *value, const void *search) {
  const test_t *test = value;
  const char *search_key = search;

  printf("search: compare %s and %s\n", test->key, search_key);

  return strcmp(test->key, search_key);
}

void destroy(void *value) {
  printf("destroy: test #%d\n", ((test_t *)(value))->id);
}

int main() {
  skiplist_t list;
  skiplist_init(&list); // -> true

  skiplist_set_cmp_fn(&list, cmp);
  skiplist_set_search_fn(&list, search);
  skiplist_set_destroy_fn(&list, destroy);

  test_t a = {"abc", 0, 42};
  test_t b = {"def", 1, 13};
  test_t c = {"ghi", 2, 7};
  test_t d = {"abc", 3, 15};

  printf("--- insert\n");
  skiplist_insert(&list, &a); // -> true
  skiplist_insert(&list, &b); // -> true
  skiplist_insert(&list, &c); // -> true
  skiplist_insert(&list, &d); // -> true

  printf("--- contains\n");
  if (skiplist_contains(&list, &b))
    printf("list contains test #%d\n", b.id);

  printf("--- search\n");
  const test_t *found = skiplist_search(&list, "def"); // -> &b
  printf("found: test #%d with value %d\n", found->id, found->value);

  printf("--- delete\n");
  skiplist_delete(&list, &c); // -> true

  printf("--- destroy\n");
  skiplist_destroy(&list);

  return 0;
}

Produces this output:

--- insert
destroy: test #0
--- contains
list contains test #1
--- search
search: compare abc and def
search: compare def and def
found: test #1 with value 13
--- delete
destroy: test #2
--- destroy
destroy: test #3
destroy: test #1