unrolled list where each list node contains an array of nodes. Unlike other lists here, each element in a list is of the same size. More...

Classes
struct	DLISTUNR
struct	DLISTUNR_position
Defines
#define	DLISTUNR_FOREACH(loopvarname, list)
	Macro for iterate over all elements of a list, the list is traversed in forward direction from first element to the last element.
#define	DLISTUNR_FOREACH_REVERSE(loopvarname, list)
	Macro for iterate over all elements of a list, the list is traversed in reverse direction from last element to the first element.
#define	DLISTUNR_FOREACH_SAVE(loopvarname, loopvarnext, list)
	Macro for iterate over all elements of a list, You may delete the current element; the list is traversed in forward direction from first element to the last element.
#define	DLISTUNR_FOREACH_REVERSE_SAVE(loopvarname, loopvarnext, list)
	Macro for iterate over all elements of a list, You may delete the current element; the list is traversed in reverse direction from last element to the first element.
Typedefs
typedef void(*	DLISTUNR_VISITOR_V )(DLISTUNR list, void entry, void *context)
typedef int(*	DLISTUNR_VISITOR )(DLISTUNR list, void entry, void *context)
Functions
M_INLINE int	DLISTUNR_init (DLISTUNR *list, size_t elmsize, size_t elmmaxcount)
	initialises a new unrolled list. List entries are all of a fixed size.
M_INLINE int	DLISTUNR_check (DLISTUNR *list)
	check validity of unrolled list instance
M_INLINE int	DLISTUNR_isempty (DLISTUNR *list)
	checks if argument list is empty
M_INLINE size_t	DLISTUNR_size (DLISTUNR *list)
M_INLINE size_t	DLISTUNR_maxsize (DLISTUNR *list)
M_INLINE DLISTUNR_position	DLISTUNR_get_first (DLISTUNR *list)
	Returns position structure of first element in unrolled linked list.
M_INLINE DLISTUNR_position	DLISTUNR_get_last (DLISTUNR *list)
	Returns position structure of last element in unrolled linked list.
M_INLINE DLISTUNR_position	DLISTUNR_next (DLISTUNR_position pos)
	Returns position to the next element in unrolled linked list.
M_INLINE int	DLISTUNR_is_eof (DLISTUNR *list, DLISTUNR_position pos)
M_INLINE DLISTUNR_position	DLISTUNR_prev (DLISTUNR_position pos)
	Returns position to the previous element in unrolled linked list.
M_INLINE int	DLISTUNR_check_position (DLISTUNR_position pos)
	verify a position structure.
M_INLINE int	DLISTUNR_copy_at (DLISTUNR list, DLISTUNR_position pos, void data, size_t size)
	copy list entry identified by position structure (pos) into user supplied memory area
M_INLINE uint8_t *	DLISTUNR_at (DLISTUNR *list, DLISTUNR_position pos)
	return pointer to list entry identified by position structure (pos).
int	DLISTUNR_insert_after (DLISTUNR list, DLISTUNR_position pos, void data, size_t size)
	insert new entry after a given entry into this unrolled linked list
M_INLINE int	DLISTUNR_insert_before (DLISTUNR list, DLISTUNR_position pos, void data, size_t size)
	insert new entry before a given entry into this unrolled linked list
int	DLISTUNR_unlink (DLISTUNR *list, DLISTUNR_position pos)
	delete an element from a unrolled list.
M_INLINE int	DLISTUNR_push_back (DLISTUNR list, void data, size_t size)
	insert element as last in list (used to maintain queue)
M_INLINE int	DLISTUNR_push_front (DLISTUNR list, void data, size_t size)
	insert element as last in list (used to maintain queue)
M_INLINE int	DLISTUNR_pop_back (DLISTUNR list, void data, size_t size)
	copy data of last element into user supplied buffer and remove the last element from list (used to maintain double ended queue)
M_INLINE int	DLISTUNR_pop_front (DLISTUNR list, void data, size_t size)
	copy data of first element into user supplied buffer and remove the first element from list (used to maintain double ended queue)
M_INLINE void	DLISTUNR_free (DLISTUNR list, DLISTUNR_VISITOR_V free_func, void context)
	list free all entries of the list. The list will then be an empty list.
Variables
size_t	tagDLISTUNR_entry::elmcount
uint8_t	tagDLISTUNR_entry::buffer []
size_t	DLISTUNR::elmmaxcount
size_t	DLISTUNR::elmcount
size_t	DLISTUNR::entrycount
DLISTUNR_entry	DLISTUNR::root
size_t	DLISTUNR_position::index

Detailed Description

unrolled list where each list node contains an array of nodes. Unlike other lists here, each element in a list is of the same size.

an unrolled linked list is a variation on the linked list which stores multiple elements in each node. It can drastically increase cache performance, while decreasing the memory overhead associated with storing links to other list elements..

Each node holds up to a certain maximum number of elements, typically just large enough so that the node fills a single cache line or a small multiple thereof. A position in the list is indicated by both a reference to the node and a position in the elements array. It's also possible to include a previous pointer for an unrolled doubly-linked linked list. Quoted from http://en.wikipedia.org/wiki/Unrolled_linked_list

Define Documentation

#define DLISTUNR_FOREACH	(	loopvarname,
		list
	)

Value:

for((loopvarname) = DLISTUNR_get_first( list );\
      (loopvarname).entry != (DLISTUNR_entry *) &(list)->root;\
      (loopvarname) = DLISTUNR_next( loopvarname ) )

Macro for iterate over all elements of a list, the list is traversed in forward direction from first element to the last element.

Parameters:

loopvarname	(type DLISTUNR_position) struct that identifies current element
list	(type DLISTUNR *) pointer to the list that is traversed

Definition at line 412 of file dlistunr.h.

#define DLISTUNR_FOREACH_REVERSE	(	loopvarname,
		list
	)

Value:

for((loopvarname) = DLISTUNR_get_last( list );\
      (loopvarname).entry != (DLISTUNR_entry *) &(list)->root;\
      (loopvarname) = DLISTUNR_prev( loopvarname ) )

Macro for iterate over all elements of a list, the list is traversed in reverse direction from last element to the first element.

Parameters:

loopvarname	(type DLISTUNR_position) pointer to the current element
list	(type DLISTUNR *) pointer to the list that is traversed

Definition at line 422 of file dlistunr.h.

#define DLISTUNR_FOREACH_REVERSE_SAVE	(	loopvarname,
		loopvarnext,
		list
	)

Value:

for((loopvarname) = DLISTUNR_get_last(list);\
      (loopvarname).entry != (DLISTUNR_entry *) &(list)->root;\
      (loopvarname) = (loopvarnext), (loopvarnext) = DLISTUNR_prev(loopvarname) )

Macro for iterate over all elements of a list, You may delete the current element; the list is traversed in reverse direction from last element to the first element.

Parameters:

loopvarname	(type DLISTUNR_position) pointer to the current element
loopvarnamenext	(type DLISTUNR_position) do not modify! pointer to next element after current element (used for iteration).
list	(type DLISTUNR *) pointer to the list that is traversed

Definition at line 444 of file dlistunr.h.

#define DLISTUNR_FOREACH_SAVE	(	loopvarname,
		loopvarnext,
		list
	)

Value:

for((loopvarname) = DLISTUNR_get_first( list ), (loopvarnext) = DLISTUNR_next( loopvarname );\
      (loopvarname).entry != (DLISTUNR_entry *) &(list)->root;\
      (loopvarname) = (loopvarnext), (loopvarnext) = DLISTUNR_next(loopvarname) )

Macro for iterate over all elements of a list, You may delete the current element; the list is traversed in forward direction from first element to the last element.

Parameters:

loopvarname	(type DLISTUNR_position) pointer to the current element
loopvarnamenext	(type DLISTUNR_position) do not modify! pointer to next element after current element (used for iteration).
list	(type DLISTUNR *) pointer to the list that is traversed

Definition at line 433 of file dlistunr.h.

Typedef Documentation

typedef int(* DLISTUNR_VISITOR)(DLISTUNR *list, void *entry, void *context)

Definition at line 54 of file dlistunr.h.

typedef void(* DLISTUNR_VISITOR_V)(DLISTUNR *list, void *entry, void *context)

Definition at line 53 of file dlistunr.h.

Function Documentation

M_INLINE uint8_t* DLISTUNR_at	(	DLISTUNR *	list,
		DLISTUNR_position	pos
	)

return pointer to list entry identified by position structure (pos).

Parameters:

list	(in) the object
pos	(in) position pointer

Returns:: pointer to data entry in linked list.

Definition at line 284 of file dlistunr.h.

{
        if (DLISTUNR_check_position(pos)) {
                return 0;
        }

        return pos.entry->buffer + pos.index * list->elmsize;
}

M_INLINE int DLISTUNR_check ( DLISTUNR * list )

check validity of unrolled list instance

Parameters:

list	the object

Returns:: 0 if list is invalid.

Definition at line 90 of file dlistunr.h.

{
        size_t elmcount, size = 0;
        size_t cursize = 0;
        DRING *cur,*next;

        if (list->root.elmcount != (size_t) -1) {
                return 0;
        }

        DRING_FOREACH( cur, &list->root.ring)   {

                next = cur->next;
                if (!next || next->prev != cur) {               
                        return 0;
                }
                elmcount = ((DLISTUNR_entry *) cur)->elmcount;
                if ( elmcount > list->elmmaxcount) {
                        return 0;
                }
                if (elmcount == 0) {
                        return 0;
                }
                size++;
                cursize += elmcount;
        }

        if (size != list->entrycount) {
                return 0;
        }
        if (cursize != list->elmcount) {
                return 0;
        }

        return 1;
}

M_INLINE int DLISTUNR_check_position ( DLISTUNR_position pos )

verify a position structure.

Definition at line 242 of file dlistunr.h.

{
        if (!pos.entry) {
                return -1;
        }
        if (pos.index >= pos.entry->elmcount) {
                return -1;
        }
        return 0;
}

M_INLINE int DLISTUNR_copy_at	(	DLISTUNR *	list,
		DLISTUNR_position	pos,
		void *	data,
		size_t	size
	)

copy list entry identified by position structure (pos) into user supplied memory area

Parameters:

list	(in) the object
pos	(in) position pointer
data	(in\|out) user supplied buffer
size	(in) size of user supplied buffer (must be equal to the size of one element).

Returns:: 0 on success -1 on failure

Definition at line 261 of file dlistunr.h.

{
        void *ptr;
        if (size != list->elmsize) {
                return -1;
        }
        if (DLISTUNR_check_position(pos)) {
                return -1;
        }

        ptr = pos.entry->buffer + pos.index * size;
        memcpy(data, ptr, size);

        return 0;
}

M_INLINE void DLISTUNR_free	(	DLISTUNR *	list,
		DLISTUNR_VISITOR_V	free_func,
		void *	context
	)

list free all entries of the list. The list will then be an empty list.

Definition at line 453 of file dlistunr.h.

{
        DRING *next,*cur;
        DLISTUNR_entry *curr;
        size_t pos,elmsize,i;
        
        elmsize = list->elmsize;

        DRING_FOREACH_SAVE( cur, next, &list->root.ring) {
        
                curr = (DLISTUNR_entry *) cur;
                if (free_func) {
                        for(pos = 0,i=0;i<curr->elmcount;i++) {
                                free_func(list,  (void *) (curr->buffer +pos), context);
                                pos += elmsize;
                        }
                }
                /*list->ctx->free( DRING_unlink(cur) );*/
                free( cur );
                
        }       
        DRING_init( &list->root.ring );
        list->entrycount = 0;
        list->elmcount = 0;
}

M_INLINE DLISTUNR_position DLISTUNR_get_first ( DLISTUNR * list )

Returns position structure of first element in unrolled linked list.

Parameters:

list	(in) the object

Returns:: position structure of first element

Definition at line 155 of file dlistunr.h.

{
        DLISTUNR_position ret;

        ret.entry = (DLISTUNR_entry *) list->root.ring.next;
        ret.index = 0;

        return ret;
}

M_INLINE DLISTUNR_position DLISTUNR_get_last ( DLISTUNR * list )

Returns position structure of last element in unrolled linked list.

Parameters:

list	(in) the object

Returns:: position structure of first element

Definition at line 171 of file dlistunr.h.

{
        DLISTUNR_position ret;

        if (list->elmcount) {
                ret.entry = (DLISTUNR_entry *) list->root.ring.prev;
                ret.index = ret.entry->elmcount - 1;            
        } else  {
                ret = DLISTUNR_get_first( list);
        }
        
        return ret;
}

M_INLINE int DLISTUNR_init	(	DLISTUNR *	list,
		size_t	elmsize,
		size_t	elmmaxcount
	)

initialises a new unrolled list. List entries are all of a fixed size.

Parameters:

ctx	(in) allocator interface. (if null we are using the default allocator)
list	(in) object that is initialised
elmsize	(in) size of one element in list.
elmmaxcount	(in) number of element stored in one list entry

Definition at line 72 of file dlistunr.h.

{       
        list->elmmaxcount = elmmaxcount;
        list->elmsize = elmsize;

        list->elmcount = list->entrycount = 0;

        DRING_init( &list->root.ring );
        list->root.elmcount = (size_t) -1;

        return 0;
}

int DLISTUNR_insert_after	(	DLISTUNR *	list,
		DLISTUNR_position	pos,
		void *	data,
		size_t	size
	)

insert new entry after a given entry into this unrolled linked list

Parameters:

list	(in) pointer to list head
pos	(in) current position (newentry inserted after this one).
data	(in) pointer to element that is to be inserted into this list.
size	(in) size of area identified by data pointer.

Definition at line 57 of file dlistunr.c.

{
        size_t elmsize = list->elmsize;
        size_t elmmaxcount = list->elmmaxcount;
        DLISTUNR_position insert_pos = pos;
        DLISTUNR_entry *next;
        void *newnodepos;

        if (size != list->elmsize) {
                return -1;
        }

        if (!insert_pos.entry) {
                insert_pos.entry = (DLISTUNR_entry *) list->root.ring.prev;
        }

        if ((newnodepos = DLISTUNR_insert_entry(
                                                                insert_pos.entry, 
                                                                insert_pos.index, 
                                                                elmmaxcount, 
                                                                elmsize)) == 0) {
                
                next = (DLISTUNR_entry *) insert_pos.entry->ring.next;
                 
                if ((newnodepos = DLISTUNR_insert_entry(next, (size_t) -1, elmmaxcount, elmsize)) == 0){

                        if ((newnodepos = DLISTUNR_insert_newnode(list, insert_pos)) == 0) {
                                return -1;
                        }
                        list->entrycount ++;
                        next = (DLISTUNR_entry *) insert_pos.entry->ring.next;

                } 
                        
                if (insert_pos.entry->elmcount != (size_t) -1 && 
                        insert_pos.index < (insert_pos.entry->elmcount - 1) ) {

                        /* bad bad */
                        insert_pos.index ++;

                        /* move elements from prev node to new node */
                        memcpy(next->buffer, 
                                   insert_pos.entry->buffer + (list->elmmaxcount - 1) * elmsize,
                                   elmsize);

                        /* move elements in current node */             
                        memmove(insert_pos.entry->buffer + (insert_pos.index + 1) * elmsize,
                                        insert_pos.entry->buffer + insert_pos.index  * elmsize,
                                        (insert_pos.entry->elmcount - insert_pos.index - 1) * elmsize);
                
                        /* copy new node into insert_pos.index */
                        newnodepos = insert_pos.entry->buffer + insert_pos.index  * elmsize;
                }
        } 
        
        memcpy(newnodepos, data, elmsize);
        list->elmcount ++;
        return 0;
}

M_INLINE int DLISTUNR_insert_before	(	DLISTUNR *	list,
		DLISTUNR_position	pos,
		void *	data,
		size_t	size
	)

insert new entry before a given entry into this unrolled linked list

Parameters:

list	(in) pointer to list head
pos	(in) current position (newentry inserted before this one).
data	(in) pointer to element that is to be inserted into this list.
size	(in) size of area identified by data pointer.

Definition at line 309 of file dlistunr.h.

{
        DLISTUNR_position insert_pos = DLISTUNR_prev(pos);
        
        return DLISTUNR_insert_after( list, insert_pos, data, size);
}

M_INLINE int DLISTUNR_is_eof	(	DLISTUNR *	list,
		DLISTUNR_position	pos
	)

Definition at line 207 of file dlistunr.h.

{
    return pos.entry == (DLISTUNR_entry *) &list->root; 
}

M_INLINE int DLISTUNR_isempty ( DLISTUNR * list )

checks if argument list is empty

Parameters:

list	pointer to list.

Returns:: not zero for non empty list.

Definition at line 133 of file dlistunr.h.

{
        return list->elmcount == 0;
}

M_INLINE size_t DLISTUNR_maxsize ( DLISTUNR * list )

Definition at line 145 of file dlistunr.h.

{
        return list->elmmaxcount;
}

M_INLINE DLISTUNR_position DLISTUNR_next ( DLISTUNR_position pos )

Returns position to the next element in unrolled linked list.

Parameters:

list	(in) the object
pos	(in) iteration position in list.

Returns:: position structure of the element that follows the element identified by pos structure.

Definition at line 191 of file dlistunr.h.

{
        DLISTUNR_position ret;
        DLISTUNR_entry *entry;

        ret = pos;
        entry = pos.entry;

        ret.index++;
        if (ret.index >= entry->elmcount) {
                ret.entry = (DLISTUNR_entry *) entry->ring.next;
                ret.index = 0;
        }
        return ret;
}

M_INLINE int DLISTUNR_pop_back	(	DLISTUNR *	list,
		void *	data,
		size_t	size
	)

copy data of last element into user supplied buffer and remove the last element from list (used to maintain double ended queue)

Parameters:

list	(in) the object
data	(in) pointer to element that is to receive data of list entry
size	(in) size of area identified by data pointer.

Returns:: return 0 on success.

Definition at line 359 of file dlistunr.h.

{
        DLISTUNR_position pos;

        
        if (DLISTUNR_isempty(list)) {
                return -1;
        }
        
        pos = DLISTUNR_get_last( list );
        
        if (DLISTUNR_copy_at(list, pos, data, size)) {
                return -1;
        }

        if (DLISTUNR_unlink(list,pos)) {
                return -1;
        }
        return 0;
}

M_INLINE int DLISTUNR_pop_front	(	DLISTUNR *	list,
		void *	data,
		size_t	size
	)

copy data of first element into user supplied buffer and remove the first element from list (used to maintain double ended queue)

Parameters:

list	(in) the object
data	(in) pointer to element that is to receive data of list entry
size	(in) size of area identified by data pointer.

Returns:: return 0 on success.

Definition at line 387 of file dlistunr.h.

{
        DLISTUNR_position pos;

        
        if (DLISTUNR_isempty(list)) {
                return -1;
        }
        
        pos = DLISTUNR_get_first( list );

        if (DLISTUNR_copy_at(list, pos, data, size)) {
                return -1;
        }
        if (DLISTUNR_unlink(list,pos)) {
                return -1;
        }
        return 0;
}

M_INLINE DLISTUNR_position DLISTUNR_prev ( DLISTUNR_position pos )

Returns position to the previous element in unrolled linked list.

Parameters:

list	(in) the object
pos	(in) iteration position in list.

Returns:: position structure of the element that precedes the element identified by pos structure.

Definition at line 219 of file dlistunr.h.

{
        DLISTUNR_position ret;
        DLISTUNR_entry *entry;

        ret = pos;
        entry = pos.entry;
        if (ret.index) {
                ret.index--;
        } else {
                ret.entry = (DLISTUNR_entry *) entry->ring.prev;
                ret.index = 0;
                if (ret.entry && ret.entry->elmcount != (size_t) -1) {
                        ret.index = ret.entry->elmcount - 1;
                } 
        }
        return ret;
}

M_INLINE int DLISTUNR_push_back	(	DLISTUNR *	list,
		void *	data,
		size_t	size
	)

insert element as last in list (used to maintain queue)

Parameters:

list	(in) the object
data	(in) pointer to element that is to be inserted into this list.
size	(in) size of area identified by data pointer.

Definition at line 332 of file dlistunr.h.

{
        DLISTUNR_position last = DLISTUNR_get_last( list );
        return DLISTUNR_insert_after(list, last, data, size);
                
}

M_INLINE int DLISTUNR_push_front	(	DLISTUNR *	list,
		void *	data,
		size_t	size
	)

insert element as last in list (used to maintain queue)

Parameters:

list	(in) the object
data	(in) pointer to element that is to be inserted into this list.
size	(in) size of area identified by data pointer.

Definition at line 345 of file dlistunr.h.

{
        DLISTUNR_position last = DLISTUNR_get_first( list );
        return DLISTUNR_insert_before(list, last, data, size);
}

M_INLINE size_t DLISTUNR_size ( DLISTUNR * list )

Definition at line 139 of file dlistunr.h.

{
        return list->elmcount;
}

int DLISTUNR_unlink	(	DLISTUNR *	list,
		DLISTUNR_position	pos
	)

delete an element from a unrolled list.

Parameters:

list	(in) the object
pos	(in) deletes element identified by this position structure return -1 on failure 0 on success.

Definition at line 118 of file dlistunr.c.

{
        DLISTUNR_entry *entry;
        size_t elmsize = list->elmsize;

        if (DLISTUNR_check_position(pos)) {
                return -1;
        }
        entry = pos.entry;

        if (entry->elmcount == (size_t) -1) {
                return -1;
        }

        if (entry->elmcount != 1) {
                if (pos.index < (entry->elmcount-1)) {
                        memmove(entry->buffer + pos.index * elmsize,
                                        entry->buffer + (pos.index + 1) * elmsize, 
                                        (entry->elmcount - pos.index - 1) * elmsize );
                }
                entry->elmcount --;
        } else {
                DRING_unlink((DRING *)pos.entry);
                free( pos.entry);
                list->entrycount --;
        }

        list->elmcount --;
        return 0;
}