Data Structures | Functions

Doubly linked list functions
[Miscellaneous functions]

Basic operations on doubly-linked lists. More...

Data Structures

struct  DLLINK
 Member of a doubly linked list. More...
struct  DLLIST
 Doubly linked list. More...

Functions

void DL_Append (DLLIST *list1, DLLIST *list2)
 Appends a list to an other one.
void DL_Cut (DLLIST *list1, DLLIST *list2, DLLINK *refp)
 Cuts a list into two.
DLLINK * DL_GetHead (DLLIST *list)
 Remove and return the object at the head of the doubly linked list.
DLLINK * DL_GetTail (DLLIST *list)
 Remove and return the object at the tail of the doubly linked list.
void DL_Init (DLLIST *list)
 Initialise a doubly linked list.
void DL_InsertAfter (DLLIST *list, DLLINK *refp, DLLINK *link)
 Insert an object after an other object already on the list.
void DL_InsertBefore (DLLIST *list, DLLINK *refp, DLLINK *link)
 Insert an object before an other object already on the list.
DLLINK * DL_Next (DLLINK *link)
 Returns the next element of the list.
DLLINK * DL_Prev (DLLINK *link)
 Returns the previous element of the list.
void DL_PutHead (DLLIST *list, DLLINK *link)
 Insert an object to the head of the doubly linked list.
void DL_PutTail (DLLIST *list, DLLINK *link)
 Insert an object to the tail of the doubly linked list.
void DL_Remove (DLLIST *list, DLLINK *link)
 Removes a link from the list.
DLLINK * DL_SeeHead (DLLIST *list)
 Returns the head of the list without removing it.
DLLINK * DL_SeeTail (DLLIST *list)
 Returns the tail of the list without removing it.

Detailed Description

Basic operations on doubly-linked lists.

Linked lists and doubly linked lists are pretty often used objects. These functions provide the basic operations on doubly linked lists.
Two structures are defined, one represents the list and the other represents a list member (a link in the chain). Both structures contain two pointers and nothing else. The functions can be used to add and remove elements, cut and append lists and traverse the elements of a list.

To use these functions you need to include misc/dlink.h.
Since the functions are very simple, they are a good candidate for inlining. If you define BLC_DLINK_INLINE before you include misc/dlink.h, then the functions will be inlined.

Of course, you want to build a list of your own structures. One possibility would be if the list members contained a pointer to your structure. However, that approach separates the memory needed for the list pointers from the object to which they belong (your structure). That can lead to all sorts of complications. The other possibility is to put the link structure inside your own data: 

#include <misc/dlink.h>

typedef struct {

    DLLINK  link;       // Doubly-linked list pointers, must be first!
    ...                 // Rest of your data
} MYDATA;

Since the link is the first element of the structure, its address is the same as that of the structure itself. Therefore, you can simply cast the structure pointer to a DLLINK pointer when you pass it to the list handling functions and cast it to your type when you receive it: 

MYDATA *data;
DLLIST some_list;

    // Remove the head of the list and put it to the tail

    data = (MYDATA *) DL_GetHead( &some_list );
    DL_AddTail( &some_list, (DLLINK *) data );

While this works, there are cases when you can not guarantee that the link is the first member, for example if you want your objects to be on two lists in the same time: 

#include <misc/dlink.h>

typedef struct {

    DLLINK  link1;      // Doubly-linked list pointers for the first list
    DLLINK  link2;      // Doubly-linked list pointers for the second list
    ...                 // Rest of your data
} MYDATA;

Deriving the address of a DLLINK object from the structure pointer is trivial, of course: 

MYDATA *data;
DLLIST list1;
DLLIST list2;

    DL_AddTail( &list1, &data->link1 );
    DL_AddTail( &list2, &data->link2 );

It's a bit trickier to get the address of the structure from the address of the link. However, you can easily write a macro to do that for you: 

// Returns a pointer to a structure of type 'type' of which the
// member 'member' has the address of 'addr'.

#define BASE( type, member, addr )  \
    ((type *)((char *)(addr) - offsetof( type, member )))


// If you use gcc, you can use the built-in offsetof:

#define offsetof( type, member ) __builtin_offsetof( type, member )


// Alternatively, you can define your own (although this solution works
// only for structures while gcc's builtin works with arrays as well):

#define offsetof( type, member ) (&((type *)0)->member)

Using the BASE macro you can get your objects back: 

MYDATA *data;
DLLINK *temp;

    temp = DL_GetHead( &list2 );

    if ( link != NULL ) {

        data = BASE( MYDATA, link2, temp );
        ...

Function Documentation

void DL_Append ( DLLIST *  list1,
DLLIST *  list2 
)

Appends a list to an other one.

The content of list2 is appended to list1 and list2 is made empty.

Parameters:
list1 Pointer to the list to which the other one will be appended
list2 Pointer to the list that should be appended
void DL_Cut ( DLLIST *  list1,
DLLIST *  list2,
DLLINK *  refp 
)

Cuts a list into two.

The list will be cut at the given element in such a way that the second list will start with the given element and the first will end with the element before the given one.

Parameters:
list1 Pointer to the list to cut
list2 Pointer to the second list (should be empty)
refp Pointer to the element that will start the second list
DLLINK* DL_GetHead ( DLLIST *  list  ) 

Remove and return the object at the head of the doubly linked list.

Parameters:
list Pointer to the list
Returns:
Pointer to the object that was at the head of the list. (void *) 0 is returned is the list was empty.
DLLINK* DL_GetTail ( DLLIST *  list  ) 

Remove and return the object at the tail of the doubly linked list.

Parameters:
list Pointer to the list
Returns:
Pointer to the object that was at the tail of the list. (void *) 0 is returned is the list was empty.
void DL_Init ( DLLIST *  list  ) 

Initialise a doubly linked list.

The list will be initialised to be empty.

Parameters:
list Pointer to the list
void DL_InsertAfter ( DLLIST *  list,
DLLINK *  refp,
DLLINK *  link 
)

Insert an object after an other object already on the list.

Parameters:
list Pointer to the list
refp Pointer to the list member after which the new object should be inserted
link Pointer to the object to add to the list
void DL_InsertBefore ( DLLIST *  list,
DLLINK *  refp,
DLLINK *  link 
)

Insert an object before an other object already on the list.

Parameters:
list Pointer to the list
refp Pointer to the list member before which the new object should be inserted
link Pointer to the object to add to the list
DLLINK* DL_Next ( DLLINK *  link  ) 

Returns the next element of the list.

Parameters:
link Pointer to a list member
Returns:
Pointer to the next list member or NULL if the argument was the last link.
DLLINK* DL_Prev ( DLLINK *  link  ) 

Returns the previous element of the list.

Parameters:
link Pointer to a list member
Returns:
Pointer to the prior list member or NULL if the argument was the first link.
void DL_PutHead ( DLLIST *  list,
DLLINK *  link 
)

Insert an object to the head of the doubly linked list.

Parameters:
list Pointer to the list
link Pointer to the object to add to the list
void DL_PutTail ( DLLIST *  list,
DLLINK *  link 
)

Insert an object to the tail of the doubly linked list.

Parameters:
list Pointer to the list
link Pointer to the object to add to the list
void DL_Remove ( DLLIST *  list,
DLLINK *  link 
)

Removes a link from the list.

The link, which must be a member of the list, will be removed from the list.

Parameters:
list Pointer to the list
link Pointer to the member to be removed
DLLINK* DL_SeeHead ( DLLIST *  list  ) 

Returns the head of the list without removing it.

Parameters:
list Pointer to the list
Returns:
Pointer to the head of the list or NULL if the list is empty
DLLINK* DL_SeeTail ( DLLIST *  list  ) 

Returns the tail of the list without removing it.

Parameters:
list Pointer to the list
Returns:
Pointer to the tail of the list or NULL if the list is empty
Generated on Fri Jan 14 2011 09:52:10 by  doxygen 1.7.1