Single linked circular list data structure; where each list element can be of different length. Each element has a pointer to the next element of the list. More...

Classes
struct	tagSRING
Defines
#define	SRING_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	SRING_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	SRING_FOREACH_SAVE_END(loopvarname, loopvarnext, list) }
Typedefs
typedef struct tagSRING	SRING
typedef void(*	SRING_VISITOR_V )(SRING entry, void context)
typedef int32_t(*	SRING_VISITOR )(SRING entry, void context)
typedef int32_t(*	SRING_COMPARE )(SRING , SRING )
Functions
M_INLINE void	SRING_init (SRING *list)
	initialises an empty list head
M_INLINE int	SRING_isempty (SRING *list)
	checks if argument list is empty
M_INLINE void	SRING_insert_after (SRING list, SRING newentry)
	insert new entry after a given entry.
M_INLINE SRING *	SRING_unlink_after (SRING *list)
M_INLINE void	SRING_push_front (SRING list, SRING newentry)
M_INLINE SRING *	SRING_pop_front (SRING *elem)
	remove the first element from list (used to maintain double ended queue)
M_INLINE SRING *	SRING_get_first (SRING *list)
M_INLINE SRING *	SRING_get_last (SRING *list)
M_INLINE SRING *	SRING_get_next (SRING end, SRING cur)
M_INLINE size_t	SRING_size (SRING *list)
M_INLINE SRING *	SRING_get_nth (SRING *list, size_t nth)
M_INLINE SRING *	SRING_get_nth_reverse (SRING *list, size_t nth)
M_INLINE void	SRING_foreach (SRING lst, SRING_VISITOR_V eval, void context)
	iterate over all elements of a list, callback is invoked for either element of the list.
M_INLINE SRING *	SRING_findif (SRING lst, SRING_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 size_t	SRING_deleteif (SRING list, SRING_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	SRING_deleteall (SRING list, SRING_VISITOR_V on_delete, void context, int offset_of_link)
	iterate over all entries of the list and delete them.
M_INLINE void	SRING_insert_sorted (SRING list, SRING_COMPARE compare, SRING 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	SRING_reverse (SRING *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 size_t	SRING_check (SRING *head)

Detailed Description

Single linked circular list data structure; where each list element can be of different length. Each element has a pointer to the next element of the list.

In a circularly-linked list, the first and final nodes are linked together. To traverse a circular linked list, you begin at any node and follow the list in either direction until you return to the original node. Viewed another way, circularly-linked lists can be seen as having no beginning or end. This type of list is most useful for managing buffers for data ingest, and in cases where you have one object in a list and wish to see all other objects in the list. The pointer pointing to the whole list is usually called the end pointer. (quoted from http://en.wikipedia.org/wiki/Linked_list )

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

Note: unlike SLIST it is not easy to get the last element in the list; in SLIST we have a pointer to the last element int the list header; with SRING we have to traverse the whole list in order to get to the last element.

Define Documentation

#define SRING_FOREACH	(	loopvarname,
		list
	)

Value:

for((loopvarname) = (list)->next;\
      (loopvarname) != (list);\
      (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 SRING *) pointer to the current element
list	(type SRING *) pointer to the list that is traversed

Definition at line 146 of file sring.h.

#define SRING_FOREACH_SAVE	(	loopvarname,
		loopvarnext,
		list
	)

Value:

for((loopvarname) = (list)->next, (loopvarnext) = (loopvarname)->next;  \
      (loopvarname) != (list);\
      (loopvarname) = (loopvarnext), (loopvarnext) = (loopvarname)->next   )

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 DRING *) pointer to the current element
loopvarnamenext	(type DRING *) do not modify! pointer to next element after current element (used for iteration).
list	(type DRING *) pointer to the list that is traversed

Definition at line 159 of file sring.h.

#define SRING_FOREACH_SAVE_END	(	loopvarname,
		loopvarnext,
		list
	)	}

Definition at line 165 of file sring.h.

Typedef Documentation

typedef struct tagSRING SRING

typedef int32_t(* SRING_COMPARE)(SRING *, SRING *)

Definition at line 40 of file sring.h.

typedef int32_t(* SRING_VISITOR)(SRING *entry, void *context)

Definition at line 39 of file sring.h.

typedef void(* SRING_VISITOR_V)(SRING *entry, void *context)

Definition at line 38 of file sring.h.

Function Documentation

M_INLINE size_t SRING_check ( SRING * head )

verify list for consistency, i.e. that it does not have loops. Uses Floyds cycle finding algorithm. http://en.literateprograms.org/Floyd%27s_cycle-finding_algorithm_%28C%29

Returns:: 0 if list is inconsistent.

Definition at line 390 of file sring.h.

{
        SRING *slow, *fast = head->next;

        SRING_FOREACH( slow, head ) {
                if (!slow) {
                        return 0;
                }
                fast = fast->next;
                if (!fast) {
                        return 0;
                }
                if (fast == head) {
                        return 1;
                }
                if (fast == slow) {
                        return 0;
                }

                fast = fast->next;
                if (!fast) {
                        return 0;
                }
                if (fast == head) {
                        return 1;
                }
                if (fast == slow) {
                        return 0;
                }
        }
        return 1;
}

M_INLINE void SRING_deleteall	(	SRING *	list,
		SRING_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.

Returns:: nunmber of elements deleted.

Definition at line 313 of file sring.h.

{
    SRING *cur,*prev,*del;

        prev = list;

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

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

M_INLINE size_t SRING_deleteif	(	SRING *	list,
		SRING_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 SRING in embedded structure.

Definition at line 274 of file sring.h.

{
    SRING *cur,*prev,*del;
        size_t  ret;

        prev = list;
        ret = 0;

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

                        cur = cur->next;
                        del = SRING_unlink_after( prev );
                        if (offset_of_link != -1) {
                                free( _MEMBEROF(del, offset_of_link) );
                        }
                        ret++;

                } else {

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

M_INLINE SRING* SRING_findif	(	SRING *	lst,
		SRING_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 240 of file sring.h.

{
        int ret;
        SRING *cur;

        if (retval) {
                *retval = 0;
        }

        if (!eval) {
          return 0;
        }

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

        return 0;
}

M_INLINE void SRING_foreach	(	SRING *	lst,
		SRING_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 217 of file sring.h.

{
        SRING *cur;

        if (!eval) {
          return ;
        }

        SRING_FOREACH(  cur, lst ) {
                eval( cur, context );

        }               
}

M_INLINE SRING* SRING_get_first ( SRING * list )

Definition at line 109 of file sring.h.

{

  if (SRING_isempty(list)) {
    return 0;
  }  
  return list->next;
}

M_INLINE SRING* SRING_get_last ( SRING * list )

Definition at line 119 of file sring.h.

{
  SRING *cur;

  if (SRING_isempty(list)) {
    return 0;
  }  
  
  for(cur = list;cur->next != list; cur = cur->next);

  return cur;
}

M_INLINE SRING* SRING_get_next	(	SRING *	end,
		SRING *	cur
	)

Definition at line 132 of file sring.h.

{
  if (cur->next == end) { 
    return 0;
  }
  return cur->next;

}

M_INLINE SRING* SRING_get_nth	(	SRING *	list,
		size_t	nth
	)

Definition at line 188 of file sring.h.

{

        SRING *elm;

        for(elm = SRING_get_first(list); elm != 0 && nth > 0; nth -= 1, elm = SRING_get_next(list, elm)); 

        return elm;
}

M_INLINE SRING* SRING_get_nth_reverse	(	SRING *	list,
		size_t	nth
	)

Definition at line 204 of file sring.h.

{       
        return SRING_get_nth( list, SRING_size( list ) - nth );
}

M_INLINE void SRING_init ( SRING * list )

initialises an empty list head

Parameters:

head list head

Definition at line 46 of file sring.h.

{ 
  list->next = list; 
}

M_INLINE void SRING_insert_after	(	SRING *	list,
		SRING *	newentry
	)

insert new entry after a given entry.

Parameters:

newentry	pointer to new list entry (to be inserted).
list	current position (newentry inserted after this one).

Definition at line 66 of file sring.h.

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

M_INLINE void SRING_insert_sorted	(	SRING *	list,
		SRING_COMPARE	compare,
		SRING *	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 341 of file sring.h.

{
        SRING *cur,*prev;
        
        prev = list;
        SRING_FOREACH(  cur, list ) {
                if (compare(cur,newentry) > 0) {

                        SRING_insert_after(prev,newentry);
                        return;
                }
                prev = cur;
        }

        SRING_insert_after(prev,newentry);
}

M_INLINE int SRING_isempty ( SRING * list )

checks if argument list is empty

Parameters:

list	pointer to list.

Returns:: not zero for non empty list.

Definition at line 56 of file sring.h.

{
  return list->next == list;
}

M_INLINE SRING* SRING_pop_front ( SRING * elem )

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

Parameters:

elem	(in) list head

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

Definition at line 97 of file sring.h.

{
  SRING *ret;
  if (SRING_isempty( elem )) {
    return 0;
  }
  ret = elem->next;
  SRING_unlink_after(elem);
  return ret;  
}

M_INLINE void SRING_push_front	(	SRING *	list,
		SRING *	newentry
	)

Definition at line 87 of file sring.h.

{
  SRING_insert_after( list, newentry );
}

M_INLINE void SRING_reverse ( SRING * 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 364 of file sring.h.

{
        SRING *cur = lst->next, *next, *tmp;

        if (cur) {
                next = cur->next;
                cur->next = lst;

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

M_INLINE size_t SRING_size ( SRING * list )

Definition at line 172 of file sring.h.

{
        size_t sz;
        SRING * cur;
        
        SRING_FOREACH( cur, list ) {
                sz += 1;
        }
        return sz;
}

M_INLINE SRING* SRING_unlink_after ( SRING * list )

Definition at line 73 of file sring.h.

{
   SRING *ret;
   
   if (SRING_isempty(list)) {
                return 0;
   }

   ret = list->next;
   list->next = list->next->next;
   return ret;
}

Classes

Defines

Typedefs

Functions

Detailed Description

Define Documentation

Typedef Documentation

Function Documentation