skiplist.c File Reference

#include <rz_skiplist.h>

Go to the source code of this file.

Macros
#define	SKIPLIST_MAX_DEPTH   31

Functions
static RzSkipListNode *	rz_skiplist_node_new (void *data, int level)
static void	rz_skiplist_node_free (RzSkipList *list, RzSkipListNode *node)
static void	init_head (RzSkipListNode *head)
static RzSkipListNode *	find_insertpoint (RzSkipList *list, void *data, RzSkipListNode **updates, bool by_data)
static bool	delete_element (RzSkipList *list, void *data, bool by_data)
RZ_API RzSkipList *	rz_skiplist_new (RzListFree freefn, RzListComparator comparefn)
RZ_API void	rz_skiplist_purge (RzSkipList *list)
RZ_API void	rz_skiplist_free (RzSkipList *list)
RZ_API RzSkipListNode *	rz_skiplist_insert (RzSkipList *list, void *data)
RZ_API bool	rz_skiplist_delete (RzSkipList *list, void *data)
RZ_API bool	rz_skiplist_delete_node (RzSkipList *list, RzSkipListNode *node)
RZ_API RzSkipListNode *	rz_skiplist_find (RzSkipList *list, void *data)
RZ_API RzSkipListNode *	rz_skiplist_find_geq (RzSkipList *list, void *data)
RZ_API RzSkipListNode *	rz_skiplist_find_leq (RzSkipList *list, void *data)
RZ_API void	rz_skiplist_join (RzSkipList *l1, RzSkipList *l2)
RZ_API void *	rz_skiplist_get_first (RzSkipList *list)
RZ_API void *	rz_skiplist_get_n (RzSkipList *list, int n)
RZ_API void *	rz_skiplist_get_geq (RzSkipList *list, void *data)
RZ_API void *	rz_skiplist_get_leq (RzSkipList *list, void *data)
RZ_API bool	rz_skiplist_empty (RzSkipList *list)
RZ_API RzList *	rz_skiplist_to_list (RzSkipList *list)

Macro Definition Documentation

SKIPLIST_MAX_DEPTH

#define SKIPLIST_MAX_DEPTH   31

Definition at line 12 of file skiplist.c.

Function Documentation

delete_element()

static bool delete_element ( RzSkipList *  list, void *  data, bool  by_data  )

static

Definition at line 73 of file skiplist.c.

                                                                       {
    int i;
    RzSkipListNode *update[SKIPLIST_MAX_DEPTH + 1], *x;
 
    // locate delete points in the lists of all levels
    x = find_insertpoint(list, data, update, by_data);
    // do nothing if the element is not present in the list
    if (x == list->head || list->compare(x->data, data) != 0) {
        return false;
    }
 
    // update forward links for all `update` points,
    // by removing the element from the list in each level
    for (i = 0; i <= list->list_level; i++) {
        if (update[i]->forward[i] != x) {
            break;
        }
        update[i]->forward[i] = x->forward[i];
    }
    rz_skiplist_node_free(list, x);
 
    // update the level of the list
    while ((list->list_level > 0) &&
        (list->head->forward[list->list_level] == list->head)) {
        list->list_level--;
    }
    list->size--;
    return true;
}

References find_insertpoint(), i, list(), rz_skiplist_node_free(), SKIPLIST_MAX_DEPTH, update(), and x.

Referenced by rz_skiplist_delete(), and rz_skiplist_delete_node().

find_insertpoint()

static RzSkipListNode* find_insertpoint ( RzSkipList *  list, void *  data, RzSkipListNode **  updates, bool  by_data  )

static

Definition at line 51 of file skiplist.c.

                                                                                                              {
    RzSkipListNode *x = list->head;
    int i;
 
    for (i = list->list_level; i >= 0; i--) {
        if (by_data) {
            while (x->forward[i] != list->head && list->compare(x->forward[i]->data, data) < 0) {
                x = x->forward[i];
            }
        } else {
            while (x->forward[i] != list->head && x->forward[i] != data) {
                x = x->forward[i];
            }
        }
        if (updates) {
            updates[i] = x;
        }
    }
    x = x->forward[0];
    return x;
}

References i, list(), and x.

Referenced by delete_element(), rz_skiplist_find(), rz_skiplist_find_geq(), and rz_skiplist_insert().

init_head()

static void init_head ( RzSkipListNode *  head )

static

Definition at line 38 of file skiplist.c.

                                            {
    int i;
    for (i = 0; i <= SKIPLIST_MAX_DEPTH; i++) {
        head->forward[i] = head;
    }
}

References test-lz4-versions::head, i, and SKIPLIST_MAX_DEPTH.

Referenced by rz_skiplist_new(), and rz_skiplist_purge().

rz_skiplist_delete()

RZ_API bool rz_skiplist_delete	(	RzSkipList *	list,
		void *	data
	)

Definition at line 201 of file skiplist.c.

                                                             {
    return delete_element(list, data, true);
}

References delete_element(), and list().

Referenced by remove_offsetmap().

rz_skiplist_delete_node()

RZ_API bool rz_skiplist_delete_node	(	RzSkipList *	list,
		RzSkipListNode *	node
	)

Definition at line 206 of file skiplist.c.

                                                                            {
    return delete_element(list, node, false);
}

References delete_element(), and list().

rz_skiplist_empty()

RZ_API bool rz_skiplist_empty

(

RzSkipList *

list

)

Definition at line 284 of file skiplist.c.

                                                {
    return list->size == 0;
}

References list().

rz_skiplist_find()

RZ_API RzSkipListNode* rz_skiplist_find	(	RzSkipList *	list,
		void *	data
	)

Definition at line 210 of file skiplist.c.

                                                                      {
    RzSkipListNode *x = find_insertpoint(list, data, NULL, true);
    if (x != list->head && list->compare(x->data, data) == 0) {
        return x;
    }
    return NULL;
}

References find_insertpoint(), list(), NULL, and x.

Referenced by get_category_t(), and get_class_t().

rz_skiplist_find_geq()

RZ_API RzSkipListNode* rz_skiplist_find_geq	(	RzSkipList *	list,
		void *	data
	)

Definition at line 218 of file skiplist.c.

                                                                          {
    RzSkipListNode *x = find_insertpoint(list, data, NULL, true);
    return x != list->head ? x : NULL;
}

References find_insertpoint(), list(), NULL, and x.

Referenced by rz_skiplist_get_geq().

rz_skiplist_find_leq()

RZ_API RzSkipListNode* rz_skiplist_find_leq	(	RzSkipList *	list,
		void *	data
	)

Definition at line 223 of file skiplist.c.

                                                                          {
    RzSkipListNode *x = list->head;
    int i;
 
    for (i = list->list_level; i >= 0; i--) {
        while (x->forward[i] != list->head && list->compare(x->forward[i]->data, data) <= 0) {
            x = x->forward[i];
        }
    }
    return x != list->head ? x : NULL;
}

References i, list(), NULL, and x.

Referenced by rz_skiplist_get_leq().

rz_skiplist_free()

RZ_API void rz_skiplist_free

(

RzSkipList *

list

)

Definition at line 145 of file skiplist.c.

                                               {
    if (!list) {
        return;
    }
    rz_skiplist_purge(list);
    rz_skiplist_node_free(list, list->head);
    free(list);
}

References free(), list(), rz_skiplist_node_free(), and rz_skiplist_purge().

Referenced by get_relocs(), mach0_free(), and rz_flag_free().

rz_skiplist_get_first()

RZ_API void* rz_skiplist_get_first

(

RzSkipList *

list

)

Definition at line 248 of file skiplist.c.

                                                     {
    if (!list) {
        return NULL;
    }
    RzSkipListNode *res = list->head->forward[0];
    return res == list->head ? NULL : res->data;
}

References rz_skiplist_node_t::data, list(), and NULL.

rz_skiplist_get_geq()

RZ_API void* rz_skiplist_get_geq	(	RzSkipList *	list,
		void *	data
	)

Definition at line 273 of file skiplist.c.

                                                               {
    RzSkipListNode *x = rz_skiplist_find_geq(list, data);
    return x ? x->data : NULL;
}

References list(), NULL, rz_skiplist_find_geq(), and x.

Referenced by rz_flag_get_nearest_list().

rz_skiplist_get_leq()

RZ_API void* rz_skiplist_get_leq	(	RzSkipList *	list,
		void *	data
	)

Definition at line 278 of file skiplist.c.

                                                               {
    RzSkipListNode *x = rz_skiplist_find_leq(list, data);
    return x ? x->data : NULL;
}

References list(), NULL, rz_skiplist_find_leq(), and x.

Referenced by rz_flag_get_nearest_list().

rz_skiplist_get_n()

RZ_API void* rz_skiplist_get_n	(	RzSkipList *	list,
		int	n
	)

Definition at line 257 of file skiplist.c.

                                                        {
    int count = 0;
    RzSkipListNode *node;
    void *data;
    if (!list || n < 0) {
        return NULL;
    }
    rz_skiplist_foreach (list, node, data) {
        if (count == n) {
            return data;
        }
        ++count;
    }
    return NULL;
}

References count, list(), n, NULL, and rz_skiplist_foreach.

rz_skiplist_insert()

RZ_API RzSkipListNode* rz_skiplist_insert	(	RzSkipList *	list,
		void *	data
	)

Definition at line 156 of file skiplist.c.

                                                                        {
    RzSkipListNode *update[SKIPLIST_MAX_DEPTH + 1];
    RzSkipListNode *x;
    int i, x_level, new_level;
 
    // locate insertion points in the lists of all levels
    x = find_insertpoint(list, data, update, true);
    // check whether the element is already in the list
    if (x != list->head && !list->compare(x->data, data)) {
        return x;
    }
 
    // randomly choose the number of levels the new node will be put in
    for (x_level = 0; rand() < RAND_MAX / 2 && x_level < SKIPLIST_MAX_DEPTH; x_level++) {
        ;
    }
 
    // update the `update` array with default values when the current node
    // has a level greater than the current one
    new_level = list->list_level;
    if (x_level > list->list_level) {
        for (i = list->list_level + 1; i <= x_level; i++) {
            update[i] = list->head;
        }
        new_level = x_level;
    }
 
    x = rz_skiplist_node_new(data, x_level);
    if (!x) {
        return NULL;
    }
 
    // update forward links for all `update` points,
    // by inserting the new element in the list in each level
    for (i = 0; i <= x_level; i++) {
        x->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = x;
    }
 
    list->list_level = new_level;
    list->size++;
    return x;
}

References find_insertpoint(), i, list(), NULL, rz_skiplist_node_new(), SKIPLIST_MAX_DEPTH, update(), and x.

Referenced by flags_at_offset(), get_relocs(), parse_relocation_info(), and rz_skiplist_join().

rz_skiplist_join()

RZ_API void rz_skiplist_join	(	RzSkipList *	l1,
		RzSkipList *	l2
	)

Definition at line 236 of file skiplist.c.

                                                             {
    RzSkipListNode *it;
    void *data;
 
    rz_skiplist_foreach (l2, it, data) {
        (void)rz_skiplist_insert(l1, data);
    }
 
    rz_skiplist_purge(l2);
}

References rz_skiplist_foreach, rz_skiplist_insert(), and rz_skiplist_purge().

rz_skiplist_new()

RZ_API RzSkipList* rz_skiplist_new	(	RzListFree	freefn,
		RzListComparator	comparefn
	)

Definition at line 107 of file skiplist.c.

                                                                                  {
    RzSkipList *list = RZ_NEW0(RzSkipList);
    if (!list) {
        return NULL;
    }
 
    list->head = rz_skiplist_node_new(NULL, SKIPLIST_MAX_DEPTH);
    if (!list->head) {
        free(list);
        return NULL;
    }
 
    init_head(list->head);
    list->list_level = 0;
    list->size = 0;
    list->freefn = freefn;
    list->compare = comparefn;
    return list;
}

References free(), freefn(), init_head(), list(), NULL, RZ_NEW0, rz_skiplist_node_new(), and SKIPLIST_MAX_DEPTH.

Referenced by get_relocs(), and rz_flag_new().

rz_skiplist_node_free()

static void rz_skiplist_node_free ( RzSkipList *  list, RzSkipListNode *  node  )

static

Definition at line 28 of file skiplist.c.

                                                                          {
    if (node) {
        if (list->freefn && node->data) {
            list->freefn(node->data);
        }
        free(node->forward);
        free(node);
    }
}

References rz_skiplist_node_t::data, rz_skiplist_node_t::forward, free(), and list().

Referenced by delete_element(), rz_skiplist_free(), and rz_skiplist_purge().

rz_skiplist_node_new()

static RzSkipListNode* rz_skiplist_node_new ( void *  data, int  level  )

static

Definition at line 14 of file skiplist.c.

                                                                   {
    RzSkipListNode *res = RZ_NEW0(RzSkipListNode);
    if (!res) {
        return NULL;
    }
    res->forward = RZ_NEWS0(RzSkipListNode *, level + 1);
    if (!res->forward) {
        free(res);
        return NULL;
    }
    res->data = data;
    return res;
}

References rz_skiplist_node_t::data, rz_skiplist_node_t::forward, free(), level, NULL, RZ_NEW0, and RZ_NEWS0.

Referenced by rz_skiplist_insert(), and rz_skiplist_new().

rz_skiplist_purge()

RZ_API void rz_skiplist_purge

(

RzSkipList *

list

)

Definition at line 128 of file skiplist.c.

                                                {
    RzSkipListNode *n;
    if (!list) {
        return;
    }
    n = list->head->forward[0];
    while (n != list->head) {
        RzSkipListNode *x = n;
        n = n->forward[0];
        rz_skiplist_node_free(list, x);
    }
    init_head(list->head);
    list->size = 0;
    list->list_level = 0;
}

References init_head(), list(), n, rz_skiplist_node_free(), and x.

Referenced by rz_flag_unset_all(), rz_skiplist_free(), and rz_skiplist_join().

rz_skiplist_to_list()

RZ_API RzList* rz_skiplist_to_list

(

RzSkipList *

list

)

Definition at line 292 of file skiplist.c.

                                                     {
    RzList *res = rz_list_new();
    RzSkipListNode *n;
    void *data;
 
    rz_skiplist_foreach (list, n, data) {
        rz_list_append(res, data);
    }
 
    return res;
}

References list(), n, rz_list_append(), rz_list_new(), and rz_skiplist_foreach.