#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include "randomizer.h"
#include "cskiplist.h"

Include dependency graph for cskiplist.c:

Macros
#define	NULL 0

#define	CSKL_DEBUG 0

#define	NO_LAYER -1

#define	SIZEOF_CSKLNODE_T(L) (sizeof(csklnode_t) + sizeof(void) L)

#define	NUM_NODES 10

#define	NODE_STR_LEN 4096

Enumerations
enum	cskiplist_find_type { cskiplist_find_early_exit, cskiplist_find_full }

Functions
static csklnode_t *	csklnode_alloc_node (int height, mem_alloc m_alloc)

static void	csklnode_add_nodes_to_lfl (int maxheight, mem_alloc m_alloc)

static csklnode_t *	csklnode_alloc_from_lfl (void *val)

static void	csklnode_free_to_lfl (csklnode_t *node)

static void	csklnode_populate_lfl (int maxheight, mem_alloc m_alloc)

static csklnode_t *	csklnode_malloc (void *val, int maxheight, mem_alloc m_alloc)

static bool	cskiplist_node_is_removable (csklnode_t *candidate, int layer)

static int	cskiplist_find_helper (val_cmp compare, int max_height, csklnode_t pred, void val, csklnode_t preds[], csklnode_t succs[], cskiplist_find_type ft)

static csklnode_t *	cskiplist_find (val_cmp compare, cskiplist_t cskl, void value)

static void	unlock_preds (csklnode_t *preds[], mcs_node_t mcs_nodes[], int highestLocked)

static void	cskl_links_tostr (int max_height, char str[], int max_cskl_str_len)

static bool	cskl_del_bulk_unsynch (val_cmp cmpfn, cskiplist_t cskl, void lo, void *hi, mem_free m_free)

void	cskl_init ()

void	cskl_free (void *anode)

cskiplist_t *	cskl_new (void lsentinel, void rsentinel, int max_height, val_cmp compare, val_cmp inrange, mem_alloc m_alloc)

void *	cskl_cmp_find (cskiplist_t cskl, void value)

void *	cskl_inrange_find (cskiplist_t cskl, void value)

csklnode_t *	cskl_insert (cskiplist_t cskl, void value, mem_alloc m_alloc)

bool	cskl_delete (cskiplist_t cskl, void value)

bool	cskl_cmp_del_bulk_unsynch (cskiplist_t cskl, void lo, void *hi, mem_free m_free)

bool	cskl_inrange_del_bulk_unsynch (cskiplist_t cskl, void lo, void *hi, mem_free m_free)

void	cskl_levels_tostr (int height, int max_height, char str[], int max_cskl_str_len)

void	cskl_append_node_str (char nodestr[], char str[], int max_cskl_str_len)

void	cskl_tostr (cskiplist_t *cskl, cskl_node_tostr node_tostr, char csklstr[], int max_cskl_str_len)

static void	cskl_links_dump (csklnode_t *node, int max_height)

void	cskl_dump (cskiplist_t *cskl, cskl_node_tostr node_tostr)

static void	cskl_links_print (csklnode_t *node, int max_height)

void	cskl_print (cskiplist_t *cskl, cskl_node_tostr node_tostr)

int	cskl_check_node_dump (val_cmp compare, int max_height, cskl_node_tostr node_tostr, csklnode_t *node)

void	cskl_check_dump (cskiplist_t *cs, cskl_node_tostr node_tostr)

Variables
static csklnode_t *	GF_cskl_nodes = NULL

static mcs_lock_t	GFCN_lock

static __thread csklnode_t *	_lf_cskl_nodes = NULL

Macro Definition Documentation

◆ CSKL_DEBUG

#define CSKL_DEBUG 0

Definition at line 79 of file cskiplist.c.

◆ NO_LAYER

#define NO_LAYER -1

Definition at line 81 of file cskiplist.c.

◆ NODE_STR_LEN

#define NODE_STR_LEN 4096

Definition at line 757 of file cskiplist.c.

◆ NULL

#define NULL 0

Definition at line 76 of file cskiplist.c.

◆ NUM_NODES

#define NUM_NODES 10

Definition at line 86 of file cskiplist.c.

◆ SIZEOF_CSKLNODE_T

#define SIZEOF_CSKLNODE_T ( L ) (sizeof(csklnode_t) + sizeof(void*) * L)

Definition at line 84 of file cskiplist.c.

Enumeration Type Documentation

◆ cskiplist_find_type

enum cskiplist_find_type

Enumerator
cskiplist_find_early_exit
cskiplist_find_full

Definition at line 99 of file cskiplist.c.

Function Documentation

◆ cskiplist_find()

static csklnode_t* cskiplist_find	(	val_cmp	compare,
		cskiplist_t *	cskl,
		void *	value
	)

static

Definition at line 286 of file cskiplist.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ cskiplist_find_helper()

static int cskiplist_find_helper	(	val_cmp	compare,
		int	max_height,
		csklnode_t *	pred,
		void *	val,
		csklnode_t *	preds[],
		csklnode_t *	succs[],
		cskiplist_find_type	ft
	)

static

from Herlihy, 2006. pre-conditions: preds[] and succs[] are arrays of csklnode_t* of length cskl->max_height.

post-conditions: if val is in cskl, return the first layer where val is found, otherwise return NO_LAYER.

preds[i]->val < val <= succs[i] for i = low..cskl->max_height-1, where low = (ft == cskiplist_find_full)? 0: found_layer, in other words, preds[i] is the node that precedes the found node at level i succs[i] is the node that follows the found node at level i.

if val is found, val == succs[cskiplist_find_helper(compare, val, preds, succs, ft)]

Definition at line 246 of file cskiplist.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ cskiplist_node_is_removable()

static bool cskiplist_node_is_removable	(	csklnode_t *	candidate,
		int	layer
	)

inlinestatic

Definition at line 220 of file cskiplist.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ cskl_append_node_str()

void cskl_append_node_str	(	char	nodestr[],
		char	str[],
		int	max_cskl_str_len
	)

Definition at line 697 of file cskiplist.c.

◆ cskl_check_dump()

void cskl_check_dump	(	cskiplist_t *	cs,
		cskl_node_tostr	node_tostr
	)

Definition at line 861 of file cskiplist.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ cskl_check_node_dump()

int cskl_check_node_dump	(	val_cmp	compare,
		int	max_height,
		cskl_node_tostr	node_tostr,
		csklnode_t *	node
	)

Definition at line 826 of file cskiplist.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ cskl_cmp_del_bulk_unsynch()

bool cskl_cmp_del_bulk_unsynch	(	cskiplist_t *	cskl,
		void *	lo,
		void *	hi,
		mem_free	m_free
	)

Definition at line 666 of file cskiplist.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ cskl_cmp_find()

void* cskl_cmp_find	(	cskiplist_t *	cskl,
		void *	value
	)

Definition at line 468 of file cskiplist.c.

Here is the call graph for this function:

◆ cskl_del_bulk_unsynch()

static bool cskl_del_bulk_unsynch	(	val_cmp	cmpfn,
		cskiplist_t *	cskl,
		void *	lo,
		void *	hi,
		mem_free	m_free
	)

static

Definition at line 340 of file cskiplist.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ cskl_delete()

bool cskl_delete	(	cskiplist_t *	cskl,
		void *	value
	)

Definition at line 569 of file cskiplist.c.

Here is the call graph for this function:

◆ cskl_dump()

void cskl_dump	(	cskiplist_t *	cskl,
		cskl_node_tostr	node_tostr
	)

Definition at line 760 of file cskiplist.c.

Here is the call graph for this function:

◆ cskl_free()

void cskl_free ( void * anode )

Definition at line 422 of file cskiplist.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ cskl_init()

void cskl_init ( )

Definition at line 409 of file cskiplist.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ cskl_inrange_del_bulk_unsynch()

bool cskl_inrange_del_bulk_unsynch	(	cskiplist_t *	cskl,
		void *	lo,
		void *	hi,
		mem_free	m_free
	)

Definition at line 672 of file cskiplist.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ cskl_inrange_find()

void* cskl_inrange_find	(	cskiplist_t *	cskl,
		void *	value
	)

Definition at line 475 of file cskiplist.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ cskl_insert()

csklnode_t* cskl_insert	(	cskiplist_t *	cskl,
		void *	value,
		mem_alloc	m_alloc
	)

Definition at line 483 of file cskiplist.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ cskl_levels_tostr()

void cskl_levels_tostr	(	int	height,
		int	max_height,
		char	str[],
		int	max_cskl_str_len
	)

Definition at line 678 of file cskiplist.c.

Here is the caller graph for this function:

◆ cskl_links_dump()

static void cskl_links_dump	(	csklnode_t *	node,
		int	max_height
	)

static

Definition at line 738 of file cskiplist.c.

Here is the caller graph for this function:

◆ cskl_links_print()

static void cskl_links_print	(	csklnode_t *	node,
		int	max_height
	)

static

Definition at line 783 of file cskiplist.c.

Here is the caller graph for this function:

◆ cskl_links_tostr()

static void cskl_links_tostr	(	int	max_height,
		char	str[],
		int	max_cskl_str_len
	)

static

Definition at line 327 of file cskiplist.c.

Here is the caller graph for this function:

◆ cskl_new()

cskiplist_t* cskl_new	(	void *	lsentinel,
		void *	rsentinel,
		int	max_height,
		val_cmp	compare,
		val_cmp	inrange,
		mem_alloc	m_alloc
	)

Definition at line 441 of file cskiplist.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ cskl_print()

void cskl_print	(	cskiplist_t *	cskl,
		cskl_node_tostr	node_tostr
	)

Definition at line 804 of file cskiplist.c.

Here is the call graph for this function:

◆ cskl_tostr()

void cskl_tostr	(	cskiplist_t *	cskl,
		cskl_node_tostr	node_tostr,
		char	csklstr[],
		int	max_cskl_str_len
	)

Definition at line 706 of file cskiplist.c.

Here is the call graph for this function:

◆ csklnode_add_nodes_to_lfl()

static void csklnode_add_nodes_to_lfl	(	int	maxheight,
		mem_alloc	m_alloc
	)

static

Definition at line 132 of file cskiplist.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ csklnode_alloc_from_lfl()

static csklnode_t* csklnode_alloc_from_lfl ( void * val )

static

Definition at line 150 of file cskiplist.c.

Here is the caller graph for this function:

◆ csklnode_alloc_node()

static csklnode_t* csklnode_alloc_node	(	int	height,
		mem_alloc	m_alloc
	)

static

Definition at line 118 of file cskiplist.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ csklnode_free_to_lfl()

static void csklnode_free_to_lfl ( csklnode_t * node )

static

Definition at line 164 of file cskiplist.c.

Here is the caller graph for this function:

◆ csklnode_malloc()

static csklnode_t* csklnode_malloc	(	void *	val,
		int	maxheight,
		mem_alloc	m_alloc
	)

static

Definition at line 203 of file cskiplist.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ csklnode_populate_lfl()

static void csklnode_populate_lfl	(	int	maxheight,
		mem_alloc	m_alloc
	)

static

Definition at line 177 of file cskiplist.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ unlock_preds()

static void unlock_preds	(	csklnode_t *	preds[],
		mcs_node_t	mcs_nodes[],
		int	highestLocked
	)

inlinestatic

Definition at line 311 of file cskiplist.c.

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

◆ _lf_cskl_nodes

__thread csklnode_t* _lf_cskl_nodes = NULL

static

Definition at line 107 of file cskiplist.c.

◆ GF_cskl_nodes

csklnode_t* GF_cskl_nodes = NULL

static

Definition at line 105 of file cskiplist.c.

◆ GFCN_lock

mcs_lock_t GFCN_lock

static

Definition at line 106 of file cskiplist.c.

Macros

Enumerations

Functions

Variables

Macro Definition Documentation

◆ CSKL_DEBUG

◆ NO_LAYER

◆ NODE_STR_LEN

◆ NULL

◆ NUM_NODES

◆ SIZEOF_CSKLNODE_T

Enumeration Type Documentation

◆ cskiplist_find_type

Function Documentation

◆ cskiplist_find()

◆ cskiplist_find_helper()

◆ cskiplist_node_is_removable()

◆ cskl_append_node_str()

◆ cskl_check_dump()

◆ cskl_check_node_dump()

◆ cskl_cmp_del_bulk_unsynch()

◆ cskl_cmp_find()

◆ cskl_del_bulk_unsynch()

◆ cskl_delete()

◆ cskl_dump()

◆ cskl_free()

◆ cskl_init()

◆ cskl_inrange_del_bulk_unsynch()

◆ cskl_inrange_find()

◆ cskl_insert()

◆ cskl_levels_tostr()

◆ cskl_links_dump()

◆ cskl_links_print()

◆ cskl_links_tostr()

◆ cskl_new()

◆ cskl_print()

◆ cskl_tostr()

◆ csklnode_add_nodes_to_lfl()

◆ csklnode_alloc_from_lfl()

◆ csklnode_alloc_node()

◆ csklnode_free_to_lfl()

◆ csklnode_malloc()

◆ csklnode_populate_lfl()

◆ unlock_preds()

Variable Documentation

◆ _lf_cskl_nodes

◆ GF_cskl_nodes

◆ GFCN_lock