Simple data structures / objects in plain C Snapshot
Classes | Defines | Typedefs | Functions
DRING

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

Classes

struct  tagDRING

Defines

#define DRING_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 DRING_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 DRING_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 DRING_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 struct tagDRING DRING
typedef void(* DRING_VISITOR_V )(DRING *entry, void *context)
typedef int32_t(* DRING_VISITOR )(DRING *entry, void *context)
typedef int32_t(* DRING_COMPARE )(DRING *, DRING *)

Functions

M_INLINE void DRING_init (DRING *head)
 initialises an empty list head
M_INLINE int DRING_isempty (DRING *list)
 checks if argument list is empty
M_INLINE void DRING_insert_before (DRING *list, DRING *newentry)
 insert new entry before a given entry.
M_INLINE void DRING_insert_after (DRING *list, DRING *newentry)
 insert new entry after a given entry.
void DRING_insert_sorted (DRING *list, DRING_COMPARE compare, DRING *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 DRING * DRING_unlink (DRING *list)
 delete an element from a list.
M_INLINE void DRING_push_back (DRING *list, DRING *newentry)
 insert element as last in list (used to maintain double ended queue)
M_INLINE void DRING_push_front (DRING *list, DRING *newentry)
 insert element as first in list (used to maintain double ended queue)
M_INLINE DRING * DRING_pop_front (DRING *elem)
 remove first element from list (used to maintain double ended queue)
M_INLINE DRING * DRING_pop_back (DRING *elem)
 remove last element from list (used to maintain double ended queue)
M_INLINE DRING * DRING_get_first (DRING *list)
M_INLINE DRING * DRING_get_last (DRING *list)
M_INLINE DRING * DRING_get_next (DRING *end, DRING *cur)
M_INLINE DRING * DRING_get_prev (DRING *end, DRING *cur)
M_INLINE size_t DRING_size (DRING *list)
M_INLINE DRING * DRING_get_nth (DRING *list, size_t nth)
M_INLINE DRING * DRING_get_nth_reverse (DRING *list, size_t nth)
void DRING_foreach (DRING *lst, DRING_VISITOR_V eval, void *context, int save_from_del)
 iterate over all elements of a list, callback is invoked for either element of the list. list is traversed forward from first element to the last element.
void DRING_foreach_reverse (DRING *lst, DRING_VISITOR_V eval, void *context, int save_from_delete)
 iterate over all elements of a list, callback is invoked for each element of the list. list is traversed backword from last element to the first element.
M_INLINE DRING * DRING_findif (DRING *lst, DRING_VISITOR eval, void *context, int32_t *retval, int save_from_del)
 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 DRING * DRING_find_reverse (DRING *lst, DRING_VISITOR eval, void *context, int32_t *retval, int save_from_delete)
 find an element within the linked list. callback is invoked for each element of the list, in reverse direction from last element to first element; when the callback returns non zero value the iteration stops as we have found what we searched for.
M_INLINE size_t DRING_deleteif (DRING *list, DRING_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 DRING_deleteall (DRING *list, DRING_VISITOR_V on_delete, void *context, int offset_of_link)
 iterate over all entries of the list and delete them.
M_INLINE void DRING_reverse (DRING *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 DRING_check (DRING *header)
 check consistency of list

Detailed Description

Double linked circular list data structure; where each list element can be of different length. Each element has a pointer to the next and previous 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.

Define Documentation

#define DRING_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 DRING *) pointer to the current element
list(type DRING *) pointer to the list that is traversed

Definition at line 204 of file dring.h.

#define DRING_FOREACH_REVERSE (   loopvarname,
  list 
)
Value:
for((loopvarname) = (list)->prev;\
      (loopvarname) != (list);\
      (loopvarname) = (loopvarname)->prev )

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

Definition at line 214 of file dring.h.

#define DRING_FOREACH_REVERSE_SAVE (   loopvarname,
  loopvarnext,
  list 
)
Value:
for((loopvarname) = (list)->prev, (loopvarnext) = (loopvarname)->prev;\
      (loopvarname) != (list);\
      (loopvarname) = (loopvarnext), (loopvarnext) = (loopvarname)->prev )

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 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 236 of file dring.h.

#define DRING_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 225 of file dring.h.

Typedef Documentation

typedef struct tagDRING DRING
typedef int32_t(* DRING_COMPARE)(DRING *, DRING *)

Definition at line 39 of file dring.h.

typedef int32_t(* DRING_VISITOR)(DRING *entry, void *context)

Definition at line 38 of file dring.h.

typedef void(* DRING_VISITOR_V)(DRING *entry, void *context)

Definition at line 37 of file dring.h.

Function Documentation

M_INLINE int DRING_check ( DRING *  header)

check consistency of list

Parameters:
lstlist header.
Returns:
zero if list contains errors.

Definition at line 487 of file dring.h.

{
        DRING *cur,*next;

        DRING_FOREACH( cur, header ) {

                next = cur->next;
                if (!next || next->prev != cur) {               
                        return 0;
                }
        }
        return 1;
}
M_INLINE void DRING_deleteall ( DRING *  list,
DRING_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_ctxallocation interface used to free data of entry.
offset_of_linkoffset of DRING in embedded structure.

Definition at line 436 of file dring.h.

{
    DRING *cur,*next,*del;

    DRING_FOREACH_SAVE(cur,next,list) {
                if (on_delete) {
                        on_delete( cur, context);
                }
                del = DRING_unlink( cur );
                if (offset_of_link != -1) {
                        free( _MEMBEROF(del,offset_of_link) );
                }
        }
}
M_INLINE size_t DRING_deleteif ( DRING *  list,
DRING_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 DRING in embedded structure.
Returns:
nunmber of elements deleted.

Definition at line 409 of file dring.h.

{
    DRING *cur,*next,*del;
        size_t  ret = 0;

    DRING_FOREACH_SAVE(cur,next,list) {
                if (!check_if || check_if( cur, context))  {
                        del = DRING_unlink( cur );
                        if (offset_of_link != -1) {
                                free( _MEMBEROF(del,offset_of_link) );
                        }
                        ret ++;
                }
        }
        return ret;
}
M_INLINE DRING* DRING_find_reverse ( DRING *  lst,
DRING_VISITOR  eval,
void *  context,
int32_t *  retval,
int  save_from_delete 
)

find an element within the linked list. callback is invoked for each element of the list, in reverse direction from last element to first 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.
lastpos(out) position in the list that has been found.
save_from_del(in) if non zero then callback can remove the current link from the list (a bit slower); if null then not; if zero then can't remove the current link from the list.
Returns:
the list element that has matched (i.e. element that has been found).

Definition at line 360 of file dring.h.

{
        int ret;
        DRING *cur, *next;

        if (retval) {
                *retval = 0;
        }

        if (!eval) {
          return 0;
        }

        if ( save_from_delete ) {
                DRING_FOREACH_REVERSE_SAVE( cur, next, lst ) {

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

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

        return 0;
}
M_INLINE DRING* DRING_findif ( DRING *  lst,
DRING_VISITOR  eval,
void *  context,
int32_t *  retval,
int  save_from_del 
)

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.
save_from_del(in) if non zero then callback can remove the current link from the list (a bit slower); if null then not; if zero then can't remove the current link from the list.
Returns:
the list element that has matched (i.e. element that has been found).

Definition at line 310 of file dring.h.

{
        int ret;
    DRING *cur, *next;

        if (retval) {
                *retval = 0;
        }

        if (!eval) {
                return 0;
        }

        if (save_from_del) {
                DRING_FOREACH_SAVE( cur, next, lst) {
                        ret = eval( cur, context );
                        if (ret) {
                                if (retval) {
                                        *retval = ret;
                                }
                                return cur;
                        }
                }
        } else {
                DRING_FOREACH(  cur, lst ) {
                        ret = eval( cur, context );
                        if (ret) {
                                if (retval) {
                                        *retval = ret;
                                }
                                return cur;
                        }
                }
        }
                

        return 0;
}
void DRING_foreach ( DRING *  lst,
DRING_VISITOR_V  eval,
void *  context,
int  save_from_del 
)

iterate over all elements of a list, callback is invoked for either element of the list. list is traversed forward from first element to the last element.

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.
save_from_del(in) if non zero then callback can remove the current link from the list (a bit slower); if null then not; if zero then can't remove the current link from the list.

Definition at line 7 of file dring.c.

{
    DRING *cur, *next;

        if (!eval) {
          return;
        }

        if (save_from_del) {
                DRING_FOREACH_SAVE( cur, next, lst) {
                        eval( cur, data );
                }
        } else {
                DRING_FOREACH(  cur, lst ) {
                        eval( cur, data );
                }
        }
                
}
void DRING_foreach_reverse ( DRING *  lst,
DRING_VISITOR_V  eval,
void *  context,
int  save_from_delete 
)

iterate over all elements of a list, callback is invoked for each element of the list. list is traversed backword from last element to the first element.

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.
save_from_del(in) if non zero then callback can remove the current link from the list (a bit slower); if null then not; if zero then can't remove the current link from the list.

Definition at line 28 of file dring.c.

{
        DRING *cur, *next;

        if (!eval) {
          return ;
        }

        if ( save_from_delete ) {
                DRING_FOREACH_REVERSE_SAVE( cur, next, lst ) {

                        eval( cur, data );
                }
        } else {
                DRING_FOREACH_REVERSE( cur, lst ) {

                        eval( cur, data );
                }
        }
}
M_INLINE DRING* DRING_get_first ( DRING *  list)

Definition at line 163 of file dring.h.

{
  if (DRING_isempty(list)) {
    return 0;
  }  
  return list->next;
}
M_INLINE DRING* DRING_get_last ( DRING *  list)

Definition at line 171 of file dring.h.

{
  if (DRING_isempty(list)) {
    return 0;
  }
  return list->prev;
}
M_INLINE DRING* DRING_get_next ( DRING *  end,
DRING *  cur 
)

Definition at line 180 of file dring.h.

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

}
M_INLINE DRING* DRING_get_nth ( DRING *  list,
size_t  nth 
)

Definition at line 261 of file dring.h.

{

        DRING *elm;

        for(elm = DRING_get_first(list); elm != 0 && nth > 0; nth -= 1, elm = DRING_get_next(list, elm)); 

        return elm;
}
M_INLINE DRING* DRING_get_nth_reverse ( DRING *  list,
size_t  nth 
)

Definition at line 277 of file dring.h.

{       
        return DRING_get_nth( list, DRING_size( list ) - nth );
}
M_INLINE DRING* DRING_get_prev ( DRING *  end,
DRING *  cur 
)

Definition at line 190 of file dring.h.

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

}
M_INLINE void DRING_init ( DRING *  head)

initialises an empty list head

Parameters:
headlist head

Definition at line 46 of file dring.h.

{ 
  head->next = head->prev = head; 
}
M_INLINE void DRING_insert_after ( DRING *  list,
DRING *  newentry 
)

insert new entry after a given entry.

Parameters:
newentrypointer to new list entry (to be inserted).
listcurrent posision (newentry inserted after this one).

Definition at line 83 of file dring.h.

{
   DRING_insert_before( list->next, newentry );
}
M_INLINE void DRING_insert_before ( DRING *  list,
DRING *  newentry 
)

insert new entry before a given entry.

Parameters:
newentrypointer to new list entry (to be inserted).
listcurrent position (newentry inserted before this one).

Definition at line 67 of file dring.h.

{
   DRING *prev = list->prev;

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

   newentry->prev = prev; 
   list->prev = newentry; 
}
void DRING_insert_sorted ( DRING *  list,
DRING_COMPARE  compare,
DRING *  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 52 of file dring.c.

{
        DRING *cur;
        
        DRING_FOREACH(  cur, list ) {
                if (compare(cur,newentry) > 0) {
                        DRING_insert_before(cur,newentry);
                        return;
                }
        }

        DRING_push_back( list, newentry );
}
M_INLINE int DRING_isempty ( DRING *  list)

checks if argument list is empty

Parameters:
listpointer to list.
Returns:
not zero for non empty list.

Definition at line 57 of file dring.h.

{
  return list->next == list;
}
M_INLINE DRING* DRING_pop_back ( DRING *  elem)

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

Parameters:
elem(in) list head.
Returns:
the last element of list, NULL if list empty

Definition at line 150 of file dring.h.

{ 
  DRING *ret;

  if (DRING_isempty( elem )) {
    return 0;
  }
  ret = elem->prev;
  DRING_unlink(elem->prev);
  return ret;
}
M_INLINE DRING* DRING_pop_front ( DRING *  elem)

remove 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 133 of file dring.h.

{
  DRING *ret;
  if (DRING_isempty( elem )) {
    return 0;
  }
  ret = elem->next;
  DRING_unlink(elem->next);
  return ret;  
}
M_INLINE void DRING_push_back ( DRING *  list,
DRING *  newentry 
)

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

Parameters:
listlist head.
newentryentry to be inserted into list

Definition at line 113 of file dring.h.

{
  DRING_insert_after( list->prev, newentry );
}
M_INLINE void DRING_push_front ( DRING *  list,
DRING *  newentry 
)

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

Parameters:
listlist head.s
newentryentry to be inserted into list

Definition at line 123 of file dring.h.

{
  DRING_insert_after( list, newentry );
}
M_INLINE void DRING_reverse ( DRING *  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 457 of file dring.h.

{
        DRING *cur = lst->prev, *next;
        DRING *tmp;

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

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

                        cur = next;
                        next = tmp;
                }

                tmp = lst->prev;
                lst->prev = lst->next;
                lst->next = tmp;
        }
}
M_INLINE size_t DRING_size ( DRING *  list)

Definition at line 245 of file dring.h.

{
        size_t sz;
        DRING * cur;
        
        DRING_FOREACH( cur, list ) {
                sz += 1;
        }
        return sz;
}
M_INLINE DRING* DRING_unlink ( DRING *  list)

delete an element from a list.

Parameters:
listdeletes this list element

Definition at line 101 of file dring.h.

{
   list->next->prev = list->prev;
   list->prev->next = list->next;
   return list;
}
Generated on Tue Oct 25 2011 01:17:10 for Simple data structures / objects in plain C by  doxygen 1.7.4