ls.c File Reference

#include <string.h>
#include "ls.h"

Go to the source code of this file.

Functions
RZ_API SdbList *	ls_newf (SdbListFree freefn)
RZ_API SdbList *	ls_new (void)
static void	ls_insertion_sort_iter (SdbListIter *iter, SdbListComparator cmp)
static void	ls_insertion_sort (SdbList *list, SdbListComparator cmp)
static SdbListIter *	_merge (SdbListIter *first, SdbListIter *second, SdbListComparator cmp)
static SdbListIter *	_sdb_list_split (SdbListIter *head)
static SdbListIter *	_merge_sort (SdbListIter *head, SdbListComparator cmp)
RZ_API bool	ls_merge_sort (SdbList *list, SdbListComparator cmp)
RZ_API bool	ls_sort (SdbList *list, SdbListComparator cmp)
RZ_API void	ls_delete (SdbList *list, SdbListIter *iter)
RZ_API bool	ls_delete_data (SdbList *list, void *ptr)
RZ_API void	ls_split_iter (SdbList *list, SdbListIter *iter)
RZ_API void	ls_destroy (SdbList *list)
RZ_API void	ls_free (SdbList *list)
RZ_API SdbListIter *	ls_append (SdbList *list, void *data)
RZ_API SdbListIter *	ls_prepend (SdbList *list, void *data)
RZ_API void *	ls_pop (SdbList *list)
RZ_API SdbList *	ls_clone (SdbList *list)
RZ_API int	ls_join (SdbList *list1, SdbList *list2)
RZ_API SdbListIter *	ls_insert (SdbList *list, int n, void *data)
RZ_API void *	ls_pop_head (SdbList *list)
RZ_API int	ls_del_n (SdbList *list, int n)

Function Documentation

_merge()

static SdbListIter* _merge ( SdbListIter *  first, SdbListIter *  second, SdbListComparator  cmp  )

static

Definition at line 41 of file ls.c.

                                                                                           {
    SdbListIter *next = NULL, *result = NULL, *head = NULL;
    while (first || second) {
        if (!second) {
            next = first;
            first = first->n;
        } else if (!first) {
            next = second;
            second = second->n;
        } else if (cmp(first->data, second->data) <= 0) {
            next = first;
            first = first->n;
        } else {
            next = second;
            second = second->n;
        }
        if (!head) {
            result = next;
            head = result;
            head->p = NULL;
        } else {
            result->n = next;
            next->p = result;
            result = result->n;
        }
    }
    head->p = NULL;
    next->n = NULL;
    return head;
}

References cmp(), ls_iter_t::data, test-lz4-versions::head, ls_iter_t::n, NULL, and ls_iter_t::p.

Referenced by _merge_sort().

_merge_sort()

static SdbListIter* _merge_sort ( SdbListIter *  head, SdbListComparator  cmp  )

static

Definition at line 90 of file ls.c.

                                                                          {
    SdbListIter *second;
    if (!head || !head->n) {
        return head;
    }
    second = _sdb_list_split(head);
    head = _merge_sort(head, cmp);
    second = _merge_sort(second, cmp);
    return _merge(head, second, cmp);
}

References _merge(), _sdb_list_split(), cmp(), and test-lz4-versions::head.

Referenced by ls_merge_sort().

_sdb_list_split()

static SdbListIter* _sdb_list_split ( SdbListIter *  head )

static

Definition at line 72 of file ls.c.

                                                       {
    SdbListIter *tmp;
    SdbListIter *fast;
    SdbListIter *slow;
    if (!head || !head->n) {
        return head;
    }
    slow = head;
    fast = head;
    while (fast && fast->n && fast->n->n) {
        fast = fast->n->n;
        slow = slow->n;
    }
    tmp = slow->n;
    slow->n = NULL;
    return tmp;
}

References fast(), test-lz4-versions::head, NULL, slow(), and autogen_x86imm::tmp.

Referenced by _merge_sort().

ls_append()

RZ_API SdbListIter* ls_append	(	SdbList *	list,
		void *	data
	)

Definition at line 200 of file ls.c.

                                                         {
    SdbListIter *it;
    if (!list) {
        return NULL;
    }
    it = RZ_NEW(SdbListIter);
    if (!it) {
        return NULL;
    }
    if (list->tail) {
        list->tail->n = it;
    }
    it->data = data;
    it->p = list->tail;
    it->n = NULL;
    list->tail = it;
    if (!list->head) {
        list->head = it;
    }
    list->length++;
    list->sorted = false;
    return it;
}

References ls_iter_t::data, list(), ls_iter_t::n, NULL, ls_iter_t::p, and RZ_NEW.

Referenced by ls_clone(), ls_insert(), ns_free_exc_list(), ns_sync(), sdb_foreach_list_cb(), sdb_foreach_list_filter_cb(), sdb_foreach_match_cb(), sdb_hook(), sdb_ns(), and sdb_ns_set().

ls_clone()

RZ_API SdbList* ls_clone

(

SdbList *

list

)

Definition at line 265 of file ls.c.

                                        {
    if (!list) {
        return NULL;
    }
    SdbList *r = ls_new(); // ownership of elements stays in original list
    if (!r) {
        return NULL;
    }
    void *v;
    SdbListIter *iter;
    ls_foreach (list, iter, v) {
        ls_append(r, v);
    }
    return r;
}

References list(), ls_append(), ls_foreach, ls_new(), NULL, r, and v.

Referenced by text_save().

ls_del_n()

RZ_API int ls_del_n	(	SdbList *	list,
		int	n
	)

Definition at line 353 of file ls.c.

                                          {
    SdbListIter *it;
    int i;
    if (!list) {
        return false;
    }
    for (it = list->head, i = 0; it && it->data; it = it->n, i++)
        if (i == n) {
            if (!it->p && !it->n) {
                list->head = list->tail = NULL;
            } else if (!it->p) {
                it->n->p = NULL;
                list->head = it->n;
            } else if (!it->n) {
                it->p->n = NULL;
                list->tail = it->p;
            } else {
                it->p->n = it->n;
                it->n->p = it->p;
            }
            free(it);
            list->length--;
            return true;
        }
    return false;
}

References ls_iter_t::data, free(), i, list(), n, ls_iter_t::n, NULL, and ls_iter_t::p.

ls_delete()

RZ_API void ls_delete	(	SdbList *	list,
		SdbListIter *	iter
	)

Definition at line 133 of file ls.c.

                                                        {
    if (!list || !iter) {
        return;
    }
    ls_split_iter(list, iter);
    if (list->free && iter->data) {
        list->free(iter->data);
        iter->data = NULL;
    }
    free(iter);
}

References free(), list(), ls_split_iter(), and NULL.

Referenced by ls_delete_data(), ls_destroy(), ns_free_exc_list(), sdb_ns_unset(), and sdb_unhook().

ls_delete_data()

RZ_API bool ls_delete_data	(	SdbList *	list,
		void *	ptr
	)

Definition at line 145 of file ls.c.

                                                     {
    void *kvp;
    SdbListIter *iter;
    ls_foreach (list, iter, kvp) {
        if (ptr == kvp) {
            ls_delete(list, iter);
            return true;
        }
    }
    return false;
}

References list(), ls_delete(), and ls_foreach.

ls_destroy()

RZ_API void ls_destroy

(

SdbList *

list

)

Definition at line 176 of file ls.c.

                                      {
    SdbListIter *it;
    if (!list) {
        return;
    }
    it = list->head;
    while (it) {
        SdbListIter *next = it->n;
        ls_delete(list, it);
        it = next;
    }
    list->head = list->tail = NULL;
    list->length = 0;
}

References list(), ls_delete(), ls_iter_t::n, and NULL.

Referenced by load_process_line(), and ls_free().

ls_free()

RZ_API void ls_free

(

SdbList *

list

)

Definition at line 191 of file ls.c.

                                   {
    if (!list) {
        return;
    }
    ls_destroy(list);
    list->free = NULL;
    free(list);
}

References free(), list(), ls_destroy(), and NULL.

Referenced by __set_rcb(), load_ctx_fini(), ns_free_exc_list(), rz_analysis_calling_conventions(), rz_analysis_class_get_inheritance_graph(), rz_analysis_class_list_handler(), rz_analysis_class_vtable_lookup_handler(), rz_analysis_dwarf_integrate_functions(), rz_analysis_noreturn_functions(), rz_core_visual_analysis_classes(), rz_flag_tags_list(), sdb_diff(), sdb_fini(), sdb_hook_free(), sdb_load_arch_profile(), sdb_load_base_types(), sdb_load_callables(), sdb_load_sysregs(), sdb_ns_free_all(), sdb_ns_sync(), sdb_querys(), sdb_text_save_fd(), and text_save().

ls_insert()

RZ_API SdbListIter* ls_insert	(	SdbList *	list,
		int	n,
		void *	data
	)

Definition at line 303 of file ls.c.

                                                                {
    SdbListIter *it, *item;
    int i;
    if (list) {
        if (!list->head || !n) {
            return ls_prepend(list, data);
        }
        for (it = list->head, i = 0; it && it->data; it = it->n, i++) {
            if (i == n) {
                item = RZ_NEW0(SdbListIter);
                if (!item) {
                    return NULL;
                }
                item->data = data;
                item->n = it;
                item->p = it->p;
                if (it->p) {
                    it->p->n = item;
                }
                it->p = item;
                list->length++;
                list->sorted = false;
                return item;
            }
        }
    }
    return ls_append(list, data);
}

References ls_iter_t::data, i, list(), ls_append(), ls_prepend(), n, ls_iter_t::n, NULL, ls_iter_t::p, and RZ_NEW0.

ls_insertion_sort()

static void ls_insertion_sort ( SdbList *  list, SdbListComparator  cmp  )

static

Definition at line 37 of file ls.c.

                                                                    {
    ls_insertion_sort_iter(list->head, cmp);
}

References cmp(), list(), and ls_insertion_sort_iter().

Referenced by ls_sort().

ls_insertion_sort_iter()

static void ls_insertion_sort_iter ( SdbListIter *  iter, SdbListComparator  cmp  )

static

Definition at line 24 of file ls.c.

                                                                             {
    SdbListIter *it, *it2;
    for (it = iter; it && it->data; it = it->n) {
        for (it2 = it->n; it2 && it2->data; it2 = it2->n) {
            if (cmp(it->data, it2->data) > 0) {
                void *t = it->data;
                it->data = it2->data;
                it2->data = t;
            }
        }
    }
}

References cmp(), ls_iter_t::data, and ls_iter_t::n.

Referenced by ls_insertion_sort().

ls_join()

RZ_API int ls_join	(	SdbList *	list1,
		SdbList *	list2
	)

Definition at line 281 of file ls.c.

                                                   {
    if (!list1 || !list2) {
        return 0;
    }
    if (!(list2->length)) {
        return 0;
    }
    if (!(list1->length)) {
        list1->head = list2->head;
        list1->tail = list2->tail;
    } else {
        list1->tail->n = list2->head;
        list2->head->p = list1->tail;
        list1->tail = list2->tail;
        list1->tail->n = NULL;
    }
    list1->length += list2->length;
    list2->head = list2->tail = NULL;
    list1->sorted = false;
    return 1;
}

References ls_t::head, ls_t::length, ls_iter_t::n, NULL, ls_iter_t::p, ls_t::sorted, and ls_t::tail.

ls_merge_sort()

RZ_API bool ls_merge_sort	(	SdbList *	list,
		SdbListComparator	cmp
	)

Definition at line 101 of file ls.c.

                                                                {
    if (!cmp) {
        return false;
    }
    if (list && list->head && cmp) {
        SdbListIter *iter;
        list->head = _merge_sort(list->head, cmp);
        // update tail reference
        iter = list->head;
        while (iter && iter->n) {
            iter = iter->n;
        }
        list->tail = iter;
        list->sorted = true;
    }
    return true;
}

References _merge_sort(), cmp(), and list().

Referenced by ls_sort().

ls_new()

RZ_API SdbList* ls_new

(

void

)

Definition at line 16 of file ls.c.

                             {
    SdbList *list = RZ_NEW0(SdbList);
    if (!list) {
        return NULL;
    }
    return list;
}

References list(), NULL, and RZ_NEW0.

Referenced by load_ctx_init(), ls_clone(), ls_newf(), sdb_diff(), sdb_hook(), sdb_new(), sdb_ns_free_all(), sdb_ns_sync(), and sdb_text_save_fd().

ls_newf()

RZ_API SdbList* ls_newf

(

SdbListFree

freefn

)

Definition at line 8 of file ls.c.

                                            {
    SdbList *list = ls_new();
    if (list) {
        list->free = freefn;
    }
    return list;
}

References freefn(), list(), and ls_new().

Referenced by sdb_foreach_list(), sdb_foreach_list_filter_user(), and sdb_foreach_match().

ls_pop()

RZ_API void* ls_pop

(

SdbList *

list

)

Definition at line 244 of file ls.c.

                                   {
    void *data = NULL;
    SdbListIter *iter;
    if (list) {
        if (list->tail) {
            iter = list->tail;
            if (list->head == list->tail) {
                list->head = list->tail = NULL;
            } else {
                list->tail = iter->p;
                list->tail->n = NULL;
            }
            data = iter->data;
            free(iter);
            list->length--;
        }
        return data;
    }
    return NULL;
}

References free(), list(), and NULL.

Referenced by sdb_diff_ctx(), sdb_diff_report(), and text_save().

ls_pop_head()

RZ_API void* ls_pop_head

(

SdbList *

list

)

Definition at line 332 of file ls.c.

                                        {
    void *data = NULL;
    SdbListIter *iter;
    if (list) {
        if (list->head) {
            iter = list->head;
            if (list->head == list->tail) {
                list->head = list->tail = NULL;
            } else {
                list->head = iter->n;
                list->head->p = NULL;
            }
            data = iter->data;
            free(iter);
        }
        list->length--;
        return data;
    }
    return NULL;
}

References free(), list(), and NULL.

ls_prepend()

RZ_API SdbListIter* ls_prepend	(	SdbList *	list,
		void *	data
	)

Definition at line 224 of file ls.c.

                                                          {
    SdbListIter *it = RZ_NEW(SdbListIter);
    if (!it) {
        return NULL;
    }
    if (list->head) {
        list->head->p = it;
    }
    it->data = data;
    it->n = list->head;
    it->p = NULL;
    list->head = it;
    if (!list->tail) {
        list->tail = it;
    }
    list->length++;
    list->sorted = false;
    return it;
}

References ls_iter_t::data, list(), ls_iter_t::n, NULL, ls_iter_t::p, and RZ_NEW.

Referenced by ls_insert().

ls_sort()

RZ_API bool ls_sort	(	SdbList *	list,
		SdbListComparator	cmp
	)

Definition at line 119 of file ls.c.

                                                          {
    if (!cmp || list->cmp == cmp) {
        return false;
    }
    if (list->length > 43) {
        ls_merge_sort(list, cmp);
    } else {
        ls_insertion_sort(list, cmp);
    }
    list->cmp = cmp;
    list->sorted = true;
    return true;
}

References cmp(), list(), ls_insertion_sort(), and ls_merge_sort().

Referenced by sdb_foreach_list(), sdb_foreach_list_filter_user(), and text_save().

ls_split_iter()

RZ_API void ls_split_iter	(	SdbList *	list,
		SdbListIter *	iter
	)

Definition at line 157 of file ls.c.

                                                            {
    if (!list || !iter) {
        return;
    }
    if (list->head == iter) {
        list->head = iter->n;
    }
    if (list->tail == iter) {
        list->tail = iter->p;
    }
    if (iter->p) {
        iter->p->n = iter->n;
    }
    if (iter->n) {
        iter->n->p = iter->p;
    }
    list->length--;
}

References list().

Referenced by ls_delete().