// (c) 2016 Jeffrey Crowell
// BSD 3 Clause License
// radare2

// Skiplists are a probabilistic datastructure than can be used as a k-v store
// with average case O(lg n) lookup time, and worst case O(n).

// https://en.wikipedia.org/wiki/Skip_list

#ifndef R2_SKIP_LIST_H
#define R2_SKIP_LIST_H

#include <r_list.h>

#ifdef __cplusplus
extern "C" {
#endif

// Extracts the sort key of an element. When a list is created with one, the
// key is cached in every node, so traversal never dereferences the payload.
// Contract: keyfn(a) < keyfn(b) exactly when compare(a, b) < 0, and
// keyfn(a) == keyfn(b) exactly when compare(a, b) == 0.
typedef ut64 (*RSkipListKey)(const void *data);

typedef struct r_skiplist_node_t {
	void *data;	// pointer to the value
	ut64 key;	// cached sort key, only meaningful when the list has a keyfn
	// level + 1 forward pointers, stored in the same allocation as the
	// node so every hop of a traversal costs one load instead of two
	struct r_skiplist_node_t *forward[];
} RSkipListNode;

typedef struct r_skiplist_t {
	RSkipListNode *head;	// list header
	int list_level; // current level of the list.
	int size;
	RListFree freefn;
	RListComparator compare;
	RSkipListKey keyfn; // optional, see RSkipListKey
} RSkipList;

R_API RSkipList* r_skiplist_new(RListFree freefn, RListComparator comparefn);
R_API RSkipList* r_skiplist_new_with_key(RListFree freefn, RListComparator comparefn, RSkipListKey keyfn);
R_API void r_skiplist_free(RSkipList *list);
R_API void r_skiplist_purge(RSkipList *list);
R_API RSkipListNode* r_skiplist_insert(RSkipList* list, void* data);
R_API bool r_skiplist_insert_autofree(RSkipList* list, void* data);
R_API bool r_skiplist_delete(RSkipList* list, void* data);
R_API bool r_skiplist_delete_node(RSkipList *list, RSkipListNode *node);
R_API RSkipListNode* r_skiplist_find(const RSkipList* list, void* data);
R_API RSkipListNode* r_skiplist_find_geq(RSkipList* list, void* data);
R_API RSkipListNode* r_skiplist_find_leq(RSkipList* list, void* data);
R_API void r_skiplist_join(RSkipList *l1, RSkipList *l2);
R_API void *r_skiplist_get_first(RSkipList *list);
R_API void *r_skiplist_get_n(RSkipList *list, int n);
R_API void* r_skiplist_get_geq(RSkipList* list, void* data);
R_API void* r_skiplist_get_leq(RSkipList* list, void* data);
// Key-based lookups. Only valid on a list created with r_skiplist_new_with_key.
// These never build a probe element and never touch any payload.
R_API void* r_skiplist_get_geq_key(RSkipList* list, ut64 key);
R_API void* r_skiplist_get_leq_key(RSkipList* list, ut64 key);
R_API bool r_skiplist_empty(RSkipList *list);
R_API RList *r_skiplist_to_list(RSkipList *list);

#define r_skiplist_islast(list, el) (el->forward[0] == list->head)

#define r_skiplist_length(list) (list->size)

#define r_skiplist_foreach(list, it, pos)\
	if (list)\
		for (it = list->head->forward[0]; it != list->head && ((pos = it->data) || 1); it = it->forward[0])

#define r_skiplist_foreach_safe(list, it, tmp, pos)\
	if (list)\
		for (it = list->head->forward[0]; it != list->head && ((pos = it->data) || 1) && ((tmp = it->forward[0]) || 1); it = tmp)

#ifdef __cplusplus
}
#endif

#endif // R2_SKIP_LIST_H