rz_skiplist.h File Reference

#include <rz_list.h>

Go to the source code of this file.

Classes
struct	rz_skiplist_node_t
struct	rz_skiplist_t

Macros
#define	rz_skiplist_islast(list, el)   (el->forward[0] == list->head)
#define	rz_skiplist_length(list)   (list->size)
#define	rz_skiplist_foreach(list, it, pos)
#define	rz_skiplist_foreach_safe(list, it, tmp, pos)

Typedefs
typedef struct rz_skiplist_node_t	RzSkipListNode
typedef struct rz_skiplist_t	RzSkipList

Functions
RZ_API RzSkipList *	rz_skiplist_new (RzListFree freefn, RzListComparator comparefn)
RZ_API void	rz_skiplist_free (RzSkipList *list)
RZ_API void	rz_skiplist_purge (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

rz_skiplist_foreach

#define rz_skiplist_foreach	(		list,
			it,
			pos
	)

Value:

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

Definition at line 48 of file rz_skiplist.h.

rz_skiplist_foreach_safe

#define rz_skiplist_foreach_safe	(		list,
			it,
			tmp,
			pos
	)

Value:

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

Definition at line 52 of file rz_skiplist.h.

rz_skiplist_islast

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

Definition at line 44 of file rz_skiplist.h.

rz_skiplist_length

#define rz_skiplist_length

(

list

)

(list->size)

Definition at line 46 of file rz_skiplist.h.

Typedef Documentation

RzSkipList

typedef struct rz_skiplist_t RzSkipList

RzSkipListNode

typedef struct rz_skiplist_node_t RzSkipListNode

Function Documentation

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_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.