Single linked list data structure; where each list element can be of different length. More...

Classes
struct	SLIST
Defines
#define	SLIST_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	SLIST_FOREACH_SAVE(loopvarname, loopvarnamenext, list)
	Macro for iterate over all elements of a list, the list is traversed in forward direction from first element to the last element.
Typedefs
typedef void(*	SLIST_VISITOR_V )(SLIST list, SLIST_entry entry, void *context)
typedef int32_t(*	SLIST_VISITOR )(SLIST list, SLIST_entry entry, void *context)
typedef int32_t(*	SLIST_COMPARE )(SLIST_entry , SLIST_entry )
Functions
M_INLINE void	SLIST_init (SLIST *head)
	initialises an empty list head
M_INLINE int	SLIST_isempty (SLIST *head)
	checks if argument list is empty
M_INLINE void	SLIST_insert_after (SLIST list, SLIST_entry pos, SLIST_entry *newentry)
	insert new entry after a given entry.
M_INLINE SLIST_entry *	SLIST_unlink_after (SLIST list, SLIST_entry link)
	delete an element from a list.
M_INLINE void	SLIST_push_back (SLIST list, SLIST_entry newentry)
	insert element as last in list.
M_INLINE void	SLIST_push_front (SLIST list, SLIST_entry newentry)
	insert element as first in list (used to maintain queue)
M_INLINE void	SLIST_append (SLIST dest, SLIST src)
	append contents of one list onto the other
M_INLINE SLIST_entry *	SLIST_pop_front (SLIST *list)
	remove the first element from list (used to maintain queue)
M_INLINE SLIST_entry *	SLIST_get_first (SLIST *list)
M_INLINE SLIST_entry *	SLIST_get_last (SLIST *list)
M_INLINE SLIST_entry *	SLIST_get_next (SLIST_entry *cur)
M_INLINE size_t	SLIST_size (SLIST *list)
	: return number of elements in list if we don't have element count in list (SLIST_NO_ELMCOUNT defined), then the whole list structure is traversed.
M_INLINE SLIST_entry *	SLIST_get_nth (SLIST *list, size_t nth)
M_INLINE SLIST_entry *	SLIST_get_nth_reverse (SLIST *list, size_t nth)
	get the nth element of a list as counted from the end of the list.
M_INLINE void	SLIST_foreach (SLIST lst, SLIST_VISITOR_V eval, void context)
	iterate over all elements of a list, callback is invoked for either element of the list.
M_INLINE SLIST_entry *	SLIST_findif (SLIST lst, SLIST_VISITOR eval, void context, int32_t *retval)
	find an element within the linked list. callback is invoked for each element of the list, in forward direction from first element to last element; when the callback returns non zero value the iteration stops as we have found what we searched for.
M_INLINE void	SLIST_insert_sorted (SLIST list, SLIST_COMPARE compare, SLIST_entry newentry)
	insert new element into sorted list; Maintains ordering relationship between elements of linked list (sort by ascending order) A sorting algorithm based on this function is not very efficient; it is of complexity O(n^2); nevertheless usefull if a list is modified and has to be always maintained in sorted order.
M_INLINE void	SLIST_deleteif (SLIST list, SLIST_VISITOR check_if, void context, int offset_of_link)
	iterate over all entries of the list and delete entries that match predicate from the list, and frees the memory (optionally)
M_INLINE void	SLIST_deleteall (SLIST list, SLIST_VISITOR_V on_delete, void context, int offset_of_link)
	iterate over all entries of the list and delete them.
M_INLINE void	SLIST_reverse (SLIST *lst)
	Reverse a list This function turns the first element into the last element, the second element into the one before the last, and so on and on.
M_INLINE int	SLIST_check (SLIST *header)
	check consistency of list This function checks for loops in the list, and if count of elements in list is the same as counter of elements in list header.

Detailed Description

Single linked list data structure; where each list element can be of different length.

This single linked list has a list header (SLIST). The list header points to the first and last element in the list. last elements next pointer is NULL.

Usage: If the user wants to link his struct(ure) into a list, then he must embed a SLIST_entry into his structure. Access to user defined structure is via embedded SLIST_entry.

The list header contains a counter of elements (feature can be surpressed by defining #define SLIST_NO_ELMCOUNT

Define Documentation

#define SLIST_FOREACH	(	loopvarname,
		list
	)

Value:

for((loopvarname) = (list)->prev;\
      (loopvarname) != 0;\
      (loopvarname) = (loopvarname)->next )

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 SLIST_entry *) pointer to the current element
list	(type SLIST *) pointer to the list that is traversed

Definition at line 250 of file slist.h.

#define SLIST_FOREACH_SAVE	(	loopvarname,
		loopvarnamenext,
		list
	)

Value:

for((loopvarname) = (list)->prev, (loopvarnamenext) = (loopvarname) ? (loopvarname)->next : 0;\
      (loopvarname) != 0;\
      (loopvarname) = (loopvarnamenext),  (loopvarnamenext) = (loopvarname) ? (loopvarname)->next : 0 )

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

Parameters:

loopvsarname	(type SLIST_entry *) pointer to the current element
list	(type SLIST *) pointer to the list that is traversed

Definition at line 260 of file slist.h.

Typedef Documentation

typedef int32_t(* SLIST_COMPARE)(SLIST_entry *, SLIST_entry *)

Definition at line 56 of file slist.h.

typedef int32_t(* SLIST_VISITOR)(SLIST *list, SLIST_entry *entry, void *context)

Definition at line 55 of file slist.h.

typedef void(* SLIST_VISITOR_V)(SLIST *list, SLIST_entry *entry, void *context)

Definition at line 54 of file slist.h.

Function Documentation

M_INLINE void SLIST_append	(	SLIST *	dest,
		SLIST *	src
	)

append contents of one list onto the other

Parameters:

dest
src	content of this list is appended onto dest list. postcondition: src list is empty

Definition at line 183 of file slist.h.

{
        if (SLIST_isempty(dest)) {
                
                if (!SLIST_isempty(src)) {

                        dest->prev = src->prev;
                        dest->next = src->next;
#ifndef SLIST_NO_ELMCOUNT
                        dest->elmcount = src->elmcount;
#endif  

                        //SLIST_init(src);
                } 

        } else {

                if (!SLIST_isempty(src)) {
                        dest->next->next = src->prev;
                        dest->next = src->next;
#ifndef SLIST_NO_ELMCOUNT
                        dest->elmcount += src->elmcount;
#endif  
                        //SLIST_init(src);

                }
        }


}

M_INLINE int SLIST_check ( SLIST * header )

check consistency of list This function checks for loops in the list, and if count of elements in list is the same as counter of elements in list header.

Parameters:

header (in) the object

Returns:: zero if list contains errors.

Definition at line 499 of file slist.h.

{
        SLIST_entry *cur,*prev = 0,*fast= 0;
#ifndef SLIST_NO_ELMCOUNT
        size_t count = 0;
#endif

        if (!header->prev || !header->next) {
                if (header->prev || header->next) {
                        return 0;
                }
                return 1;
        }
        
        fast = header->prev;
        SLIST_FOREACH( cur, header ) {

#ifndef SLIST_NO_ELMCOUNT
                count += 1;
#endif      
                prev = fast;
                fast = fast->next;
                if (!fast) {
                        break;
                }
                if (fast == cur) {
                        return 0;
                }

#ifndef SLIST_NO_ELMCOUNT
                count += 1;
#endif
            prev = fast;
                fast = fast->next;
                if (!fast) {
                        break;
                }
                if (fast == cur) {
                        return 0;
                }
        }

        if (header->next != prev) {
                return 0;
        }


#ifndef SLIST_NO_ELMCOUNT
        if (header->elmcount != count) {
                return 0;
        }
#endif  
        return 1;
}

M_INLINE void SLIST_deleteall	(	SLIST *	list,
		SLIST_VISITOR_V	on_delete,
		void *	context,
		int	offset_of_link
	)

iterate over all entries of the list and delete them.

Parameters:

list	(in) the object
on_delete(in)	if not NULL then this callback is called prior to deleting each list element.
context	(in) if on_delete is not NULL then this pointer is passed as argument to on_delete.
free_ctx	(in) allocation interface used to free data of entry.
offset_of_link	(in) offset of SRING in embedded structure.

Definition at line 445 of file slist.h.

{
    SLIST_entry *cur,*del;


        for(cur = list->prev; cur;) {
    
                if (on_delete)  {
                        on_delete( list, cur, context );
                }

                cur = cur->next;
                del = SLIST_unlink_after( list, 0 );
                if (offset_of_link != -1) {
                        free( _MEMBEROF(del, offset_of_link) );
                }
        }
}

M_INLINE void SLIST_deleteif	(	SLIST *	list,
		SLIST_VISITOR	check_if,
		void *	context,
		int	offset_of_link
	)

iterate over all entries of the list and delete entries that match predicate from the list, and frees the memory (optionally)

Parameters:

list	(in) the object.
check_if	(in) predicate function; the function returns 1 then inspected argument element will be deleted; if argument pointer is NULL then all entries will be deleted.
context	(in) data pointer passed to every invocation of check_if
free_ctx	(in) interface used to free data of entry, is argument pointer is NULL then nothing is freed.
offset_of_link	(in) offset of DLIST_entry in embedded structure.

Definition at line 410 of file slist.h.

{
    SLIST_entry *cur,*prev,*del;

        prev = 0;

        for(cur = list->prev; cur;) {
    
                if (!check_if || check_if( list, cur, context))  {

                        cur = cur->next;
                        del = SLIST_unlink_after( list, prev );
                        if (offset_of_link != -1) {
                                free( _MEMBEROF(del, offset_of_link) );
                        }
                        

                } else {

                        prev = cur;
                        cur = cur->next;
                }
        }
}

M_INLINE SLIST_entry* SLIST_findif	(	SLIST *	lst,
		SLIST_VISITOR	eval,
		void *	context,
		int32_t *	retval
	)

find an element within the linked list. callback is invoked for each element of the list, in forward direction from first element to last element; when the callback returns non zero value the iteration stops as we have found what we searched for.

Parameters:

lst	(in) the object.
eval	(in) callback that is called to visit each set (or cleared) bit.
context	(in) pointer that is passed as context on each invocation of callback.
retval	(out) optional - the first non zero value returned by eval callback, if NULL then ignored.

Returns:: the list element that has matched (i.e. element that has been found).

Definition at line 349 of file slist.h.

{
        int ret;
    SLIST_entry  *cur;

        if (retval) {
                *retval = 0;
        }

        if (!eval) {
          return 0;
        }

        SLIST_FOREACH(  cur, lst ) {
                ret = eval( lst, cur, context);
                if (ret) {
                        if (retval) {
                                *retval = ret;
                        }

                        return cur;
                }

        }

        return 0;
}

M_INLINE void SLIST_foreach	(	SLIST *	lst,
		SLIST_VISITOR_V	eval,
		void *	context
	)

iterate over all elements of a list, callback is invoked for either element of the list.

Parameters:

lst	(in) the object.
eval	(in) callback that is called to visit each set (or cleared) bit.
context	(in) pointer that is passed as context on each invocation of callback.

Definition at line 326 of file slist.h.

{
    SLIST_entry *cur;

        if (!eval) {
          return;
        }

        SLIST_FOREACH( cur, lst) {
                eval( lst, cur, context);
        }
        
}

M_INLINE SLIST_entry* SLIST_get_first ( SLIST * list )

Definition at line 226 of file slist.h.

{
  return list->prev;
}

M_INLINE SLIST_entry* SLIST_get_last ( SLIST * list )

Definition at line 231 of file slist.h.

{
  return list->next;
}

M_INLINE SLIST_entry* SLIST_get_next ( SLIST_entry * cur )

Definition at line 237 of file slist.h.

{
  return cur->next;
}

M_INLINE SLIST_entry* SLIST_get_nth	(	SLIST *	list,
		size_t	nth
	)

Definition at line 290 of file slist.h.

{

        SLIST_entry *elm;

#ifndef SLIST_NO_ELMCOUNT
        if (nth >= list->elmcount) {
                return 0;
        }

        for(elm = SLIST_get_first(list); nth > 0; nth -= 1, elm = SLIST_get_next(elm)); 
#else
        for(elm = SLIST_get_first(list); elm != 0 && nth > 0; nth -= 1, elm = SLIST_get_next(elm)); 
#endif

        return elm;
}

M_INLINE SLIST_entry* SLIST_get_nth_reverse	(	SLIST *	list,
		size_t	nth
	)

get the nth element of a list as counted from the end of the list.

list (IN) the object nth (IN) index of element to retrieve (null based).

Definition at line 313 of file slist.h.

{       
        return SLIST_get_nth( list, SLIST_size( list ) - nth );
}

M_INLINE void SLIST_init ( SLIST * head )

initialises an empty list head

Parameters:

head list head

Definition at line 63 of file slist.h.

{ 
  head->next = head->prev = 0; 
#ifndef SLIST_NO_ELMCOUNT
  head->elmcount = 0;
#endif
}

M_INLINE void SLIST_insert_after	(	SLIST *	list,
		SLIST_entry *	pos,
		SLIST_entry *	newentry
	)

insert new entry after a given entry.

Parameters:

list	pointer to list head
pos	current posision (newentry inserted after this one).
newentry	pointer to new list entry (to be inserted).

Definition at line 88 of file slist.h.

{
        if (list->next) {

                if (pos){
                
                        newentry->next = pos->next;
                        pos->next = newentry;

                        if (!newentry->next) {
                                list->next = newentry;
                        } 

                } else  {
                        newentry->next = list->prev;
                        list->prev = newentry;
                } 


        } else {

                list->next = list->prev = newentry;
                newentry->next =  0;            

        }


#ifndef SLIST_NO_ELMCOUNT
        list->elmcount ++;
#endif
}

M_INLINE void SLIST_insert_sorted	(	SLIST *	list,
		SLIST_COMPARE	compare,
		SLIST_entry *	newentry
	)

insert new element into sorted list; Maintains ordering relationship between elements of linked list (sort by ascending order) A sorting algorithm based on this function is not very efficient; it is of complexity O(n^2); nevertheless usefull if a list is modified and has to be always maintained in sorted order.

Parameters:

list	(in) the object
compare	(in) comparison function.
newentry	(in) element that is to be inserted into list.

Definition at line 385 of file slist.h.

{
        SLIST_entry *cur,*prev;
        
        prev = 0;
        SLIST_FOREACH(  cur, list ) {
                if (compare(cur,newentry) > 0) {

                        SLIST_insert_after(list, prev,newentry);
                        return;
                }
                prev = cur;
        }

        SLIST_push_back( list, newentry );
}

M_INLINE int SLIST_isempty ( SLIST * head )

checks if argument list is empty

Parameters:

list	pointer to list.

Returns:: not zero for non empty list.

Definition at line 76 of file slist.h.

{
  return head->next == 0;
}

M_INLINE SLIST_entry* SLIST_pop_front ( SLIST * list )

remove the first element from list (used to maintain queue)

Parameters:

list	(in) the object

Returns:: the first element of list, NULL if list empty

Definition at line 220 of file slist.h.

{
  return SLIST_unlink_after(list, 0);
}

M_INLINE void SLIST_push_back	(	SLIST *	list,
		SLIST_entry *	newentry
	)

insert element as last in list.

Parameters:

list	list head.
newentry	entry to be inserted into list

Definition at line 162 of file slist.h.

{
  SLIST_insert_after( list, list->next, newentry );
}

M_INLINE void SLIST_push_front	(	SLIST *	list,
		SLIST_entry *	newentry
	)

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

Parameters:

list	list head
newentry	entry to be inserted into list

Definition at line 172 of file slist.h.

{
  SLIST_insert_after( list, 0, newentry );
}

M_INLINE void SLIST_reverse ( SLIST * lst )

Reverse a list This function turns the first element into the last element, the second element into the one before the last, and so on and on.

Parameters:

header (in) the object

Definition at line 471 of file slist.h.

{
        SLIST_entry *cur = lst->prev, *next;
        SLIST_entry *tmp;
        if (cur) {
                next = cur->next;
                cur->next = 0;

                while(next) {
                        tmp = next->next;
                        
                        next->next = cur;
                        cur = next;
                        next = tmp;
                }

                tmp = lst->prev;
                lst->prev = lst->next;
                lst->next = tmp;
        }
}

M_INLINE size_t SLIST_size ( SLIST * list )

: return number of elements in list if we don't have element count in list (SLIST_NO_ELMCOUNT defined), then the whole list structure is traversed.

Definition at line 270 of file slist.h.

{
#ifndef SLIST_NO_ELMCOUNT
        return list->elmcount;
#else
        size_t sz;
        SLIST_entry * cur;
        
        SLIST_FOREACH( cur, list ) {
                sz += 1;
        }
        return sz;
#endif
}

M_INLINE SLIST_entry* SLIST_unlink_after	(	SLIST *	list,
		SLIST_entry *	link
	)

delete an element from a list.

Parameters:

list	deletes this list element

Definition at line 125 of file slist.h.

{
        SLIST_entry *ret;

        if (!link) {
                ret = list->prev;
                list->prev = ret->next;
                if (!list->prev) {
                        list->next = 0;
                }
                
        } else {
                ret = link->next;       
                if (!ret) {
                        return 0;
                }

                link->next = ret ? ret->next : 0;

                if (link->next == 0) {
                        list->next = link;
                }

        }
#ifndef SLIST_NO_ELMCOUNT
                list->elmcount --;
#endif

        return ret;
}

Classes

Defines

Typedefs

Functions

Detailed Description

Define Documentation

Typedef Documentation

Function Documentation