list.h File Reference

List datatype. More...

#include <assert.h>
#include <memory.h>
#include <stddef.h>

Include dependency graph for list.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	list
	This structure defines a generic list. Nodes of the list must have a next/prev pointer properly typed. More...

Macros
#define	my_offsetof(st, m)   ((size_t)( (unsigned char *)&((st)->m ) - (unsigned char *)(st)))
	This macro is a slightly-different implementation of the standard offsetof macro.
#define	list(type)   type *
	Declare a "typed" list. This is a pointer to type, but the variable will instead reference a struct rootsim_list!
#define	new_list(type)
#define	list_sizeof(list)   ((struct list *)list)->size
#define	list_head(li)   ((__typeof__ (li))(((struct list *)(li))->head))
#define	list_tail(li)   ((__typeof__ (li))(((struct list *)(li))->tail))
#define	list_next(ptr)   ((ptr)->next)
#define	list_prev(ptr)   ((ptr)->prev)
#define	get_key(data)
	This macro retrieves the key of a payload data structure given its offset, and casts the value to double. More...
#define	list_empty(list)   (((struct list *)list)->size == 0)
#define	list_insert_tail(li, data)
#define	list_insert_head(li, data)
#define	list_insert(li, key_name, data)
	Insert a new node in the list.
#define	list_detach_by_content(li, node)
#define	list_pop(list)
#define	list_trunc(list, key_name, key_value, release_fn)
	Truncate a list up to a certain point, starting from the head. More...
#define	list_size(li)   ((struct list *)(li))->size

Detailed Description

List datatype.

A generic doubly-linked list

Copyright

Copyright (C) 2008-2022 HPDCS Group https://hpdcs.github.io

Macro Definition Documentation

get_key

#define get_key

(

data

)

Value:

            ({\
            char *__key_ptr = ((char *)(data) + __key_position);\
            double *__key_double_ptr = (double *)__key_ptr;\
            *__key_double_ptr;\
              })

This macro retrieves the key of a payload data structure given its offset, and casts the value to double.

list_detach_by_content

#define list_detach_by_content	(		li,
			node
	)

Value:

    do {                                                                                                           \
        __typeof__(node) __n = (node); /* in-block scope variable */                                           \
        struct list *__l;                                                                                      \
        __l = (struct list *)(li);                                                                             \
        assert(__l);                                                                                           \
        /* Unchain the node */                                                                                 \
        if(__l->head == __n) {                                                                                 \
            __l->head = __n->next;                                                                         \
            if(__l->head != NULL) {                                                                        \
                ((__typeof(node))__l->head)->prev = NULL;                                              \
            }\
        }\
        if(__l->tail == __n) {\
            __l->tail = __n->prev;\
            if(__l->tail != NULL) {\
                ((__typeof(node))__l->tail)->next = NULL;\
            }\
        }\
        if(__n->next != NULL) {\
            __n->next->prev = __n->prev;\
        }\
        if(__n->prev != NULL) {\
            __n->prev->next = __n->next;\
        }\
        __n->next = (void *)0xBEEFC0DE;\
        __n->prev = (void *)0xDEADC0DE;\
        __l->size--;\
    } while(0)

list_empty

#define list_empty

(

list

)

(((struct list *)list)->size == 0)

Given a pointer to a list, this macro evaluates to a boolean telling whether the list is empty or not.

Parameters

list	a pointer to a list created using the new_list() macro.

list_head

#define list_head

(

li

)

((__typeof__ (li))(((struct list *)(li))->head))

This macro retrieves a pointer to the head node of a list.

Parameters

li	a pointer to a list created using the new_list() macro.

list_insert_head

#define list_insert_head	(		li,
			data
	)

Value:

    do {    \
        __typeof__(data) __new_n = (data); /* in-block scope variable */\
        struct list *__l;\
        __new_n->next = NULL;\
        __new_n->prev = NULL;\
        __l = (struct list *)(li);\
        assert(__l);\
        if(__l->size == 0) { /* is the list empty? */\
            __l->head = __new_n;\
            __l->tail = __new_n;\
        }else{\
            __new_n->prev = NULL; /* Otherwise add at the beginning */\
            __new_n->next = __l->head;\
            ((__typeof(data))__l->head)->prev = __new_n;\
            __l->head = __new_n;\
        }\
        __l->size++;\
    } while(0)

list_insert_tail

#define list_insert_tail	(		li,
			data
	)

Value:

    do {    \
        __typeof__(data) __new_n = (data); /* in-block scope variable */\
        struct list *__l;\
        __new_n->next = NULL;\
        __new_n->prev = NULL;\
        do {\
            __l = (struct list *)(li);\
            assert(__l);\
            if(__l->size == 0) { /* is the list empty? */\
                __l->head = __new_n;\
                __l->tail = __new_n;\
                break; /* leave the inner do-while */\
            }\
            __new_n->next = NULL; /* Otherwise add at the end */\
            __new_n->prev = __l->tail;\
            ((__typeof__(data))(__l->tail))->next = __new_n;\
            __l->tail = __new_n;\
        } while(0);\
        __l->size++;\
    } while(0)

list_next

#define list_next

(

ptr

)

((ptr)->next)

Given a pointer to a list node, this macro retrieves a pointer to the next node, if any.

Parameters

ptr	a pointer to a list node.

list_pop

#define list_pop

(

list

)

Value:

    do {\
        struct list *__l;\
        size_t __size_before;\
        __typeof__ (list) __n;\
        __typeof__ (list) __n_next;\
        __l = (struct list *)(list);\
        assert(__l);\
        __size_before = __l->size;\
        __n = __l->head;\
        if(__n != NULL) {\
            __l->head = __n->next;\
            if(__n->next != NULL) {\
                __n->next->prev = NULL;\
            }\
            __n_next = __n->next;\
            __n->next = (void *)0xDEFEC8ED;\
            __n->prev = (void *)0xDEFEC8ED;\
            __n = __n_next;\
            __l->size--;\
            assert(__l->size == (__size_before - 1));\
        }\
    } while(0)

list_prev

#define list_prev

(

ptr

)

((ptr)->prev)

Given a pointer to a list node, this macro retrieves a pointer to the prev node, if any.

Parameters

ptr	a pointer to a list node.

list_tail

#define list_tail

(

li

)

((__typeof__ (li))(((struct list *)(li))->tail))

This macro retrieves a pointer to the tail node of a list.

Parameters

li	a pointer to a list created using the new_list() macro.

list_trunc

#define list_trunc	(		list,
			key_name,
			key_value,
			release_fn
	)

Value:

    ({\
    struct list *__l = (struct list *)(list);\
    __typeof__(list) __n;\
    __typeof__(list) __n_adjacent;\
    unsigned int __deleted = 0;\
    size_t __key_position = my_offsetof((list), key_name);\
    assert(__l);\
    size_t __size_before = __l->size;\
    /* Attempting to truncate an empty list? */\
    if(__l->size > 0) {\
        __n = __l->head;\
        while(__n != NULL && get_key(__n) < (key_value)) {\
            __deleted++;\
                    __n_adjacent = __n->next;\
                    __n->next = (void *)0xBAADF00D;\
                    __n->prev = (void *)0xBAADF00D;\
            release_fn(__n);\
            __n = __n_adjacent;\
        }\
        __l->head = __n;\
        if(__l->head != NULL)\
        ((__typeof__(list))__l->head)->prev = NULL;\
    }\
    __l->size -= __deleted;\
    assert(__l->size == (__size_before - __deleted));\
    __deleted;\
    })

Truncate a list up to a certain point, starting from the head.

new_list

#define new_list

(

type

)

Value:

    __extension__({ \
        void *__lmptr; \
        __lmptr = malloc(sizeof(struct list)); \
        memset(__lmptr, 0, sizeof(struct list));\
        __lmptr;\
    })

This macro allocates a struct rootsim_list object and cast it to the type pointer. It can be used to mimic the C++ syntax of templated lists, like:

list(int) = new_list(int);