Linked List

The Ambiorix Linked List is a doubly linked list. More...

Collaboration diagram for Linked List:

Modules
	Linked List Iterator

Data Structures
struct	_amxc_llist
	The linked list structure. More...

Macros
#define	amxc_llist_for_each(it, list)
	Loops over the list from head to tail. More...
#define	amxc_llist_iterate(it, list)
	Loops over the list from head to tail. More...
#define	amxc_llist_for_each_reverse(it, list)
	Loops over the list from tail to head. More...
#define	amxc_llist_iterate_reverse(it, list)
	Loops over the list from tail to head. More...

Typedefs
typedef struct _amxc_llist	amxc_llist_t
	The linked list structure. More...
typedef void(*	amxc_llist_it_delete_t) (amxc_llist_it_t *it)
	Definition of the linked list item delete function. More...

Functions
int	amxc_llist_new (amxc_llist_t **llist)
	Allocates a linked list. More...
void	amxc_llist_delete (amxc_llist_t **llist, amxc_llist_it_delete_t func)
	Frees the previously allocated linked list. More...
int	amxc_llist_init (amxc_llist_t *const llist)
	Initializes a linked list. More...
void	amxc_llist_clean (amxc_llist_t *const llist, amxc_llist_it_delete_t func)
	Removes all items from the linked list. More...
int	amxc_llist_move (amxc_llist_t *const dest, amxc_llist_t *const src)
	Moves all items from one linked list to another linked list. More...
bool	amxc_llist_is_empty (const amxc_llist_t *const llist)
	Checks that the linked list is empty. More...
size_t	amxc_llist_size (const amxc_llist_t *const llist)
	Calculates the size of the linked list. More...
int	amxc_llist_append (amxc_llist_t *const llist, amxc_llist_it_t *const it)
	Adds an item to the end of the linked list. More...
int	amxc_llist_prepend (amxc_llist_t *const llist, amxc_llist_it_t *const it)
	Adds an item to the beginning of the linked list. More...
amxc_llist_it_t *	amxc_llist_get_at (const amxc_llist_t *const llist, const unsigned int index)
	Gets an item at a certain position of the linked list. More...
int	amxc_llist_set_at (amxc_llist_t *llist, const unsigned int index, amxc_llist_it_t *const it)
	Inserts an item at a certain position. More...
int	amxc_llist_sort (amxc_llist_t *const llist, amxc_llist_it_cmp_t cmp)
	Sorts a linked list. More...
AMXC_INLINE amxc_llist_it_t *	amxc_llist_get_first (const amxc_llist_t *const llist)
	Gets the first item of the linked list. More...
AMXC_INLINE amxc_llist_it_t *	amxc_llist_get_last (const amxc_llist_t *const llist)
	Gets the last item of the linked list. More...
AMXC_INLINE amxc_llist_it_t *	amxc_llist_take_first (amxc_llist_t *const llist)
	Removes the first item from the linked list. More...
AMXC_INLINE amxc_llist_it_t *	amxc_llist_take_last (amxc_llist_t *const llist)
	Removes the last item from the linked list. More...
AMXC_INLINE amxc_llist_it_t *	amxc_llist_take_at (const amxc_llist_t *llist, const unsigned int index)
	Removes an item at a certain position of the linked list. More...

Detailed Description

The Ambiorix Linked List is a doubly linked list.

A doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields: a reference to the previous and to the next node in the sequence of nodes. The beginning and ending nodes' previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list.

The linked list itself contains two fields: a reference to the first node and a reference to the last node

The nodes of an Ambiorix linked list are defined using the amxc_llist_it_t structure (the iterator). To create a linked list of a C structure, put an linked list iterator as member of that structure.

typedef struct person {
   char* first_name;
   char* last_name;
   uint32_t age;
   amxc_llist_it_t it;
} person_t;

Creating A Linked List

A linked list can be declared on the stack or allocated in the heap. When declaring a linked list on the stack it must be correctly initialized.

• amxc_llist_init - initializes a linked list declared on the stack
• amxc_llist_new - allocates a linked list in the heap.

Adding items

Items can be added:

• at the start of the linked list - amxc_llist_prepend
• at the end of the linked list - amxc_llist_append
• before another node (iterator) - amxc_llist_it_insert_before
• after another node (iterator) - amxc_llist_it_insert_after
• at a specific index - amxc_llist_set_at

Looping Over A Linked List

Looping over a linked list can be done using the defined macros:

• amxc_llist_for_each - allows deletion of the current item
• amxc_llist_iterate

You can implement your own loop and use the linked list navigation functions:

• amxc_llist_get_first
• amxc_llist_get_last
• amxc_llist_it_get_next
• amxc_llist_it_get_previous

Convert An Linked List Iterator To Data Struct

Using the macro amxc_container_of (or amxc_llist_it_get_data) the address of the containing data structure is calculated:

(data address) = (iterator address) - (offsetof(<type>, <member>))

Removing An Item

Any item can be removed from the linked list without deleting the item itself.

• amxc_llist_it_take - removes a node (iterator) from the linked list
• amxc_llist_take_first - removes the first node (iterator) from the linked list
• amxc_llist_take_last - removes the last node (iterator) from the linked list

Deleting An Item

Most of the time items in the linked list are allocated on the heap. The linked list implementation can not by itself delete the allocated memory for the item, but a callback function can be provided to achieve this.

Deleting an item can be done using:

• amxc_llist_it_clean - deletes a single node (iterator)
• amxc_llist_clean - removes all nodes (iterators)
• amxc_llist_delete - removes all nodes (iterators)

Example

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
 
#include <amxc/amxc.h>
 
  typedef struct person {
     char first_name[64];
     char last_name[64];
     uint32_t age;
     amxc_llist_it_t it;
  } person_t;
 
  static void delete_person(amxc_llist_it_t* it) {
     person_t *person = amxc_container_of(it, person_t, it);
     free(person);
  }
 
  int main(int argc, char** argv) {
      amxc_llist_t contacts;
      person_t *person = NULL;
 
      amxc_llist_init(&contacts)
 
      for(uint32_t i = 0; i < 10; i++) {
        person = (person_t *)calloc(1, sizeof(person_t));
        snprintf(person->first_name, 64, "first_name %d", i);
        snprintf(person->last_name, 64, "last_name %d", i);
        person->age = i;
        amxc_llist_append(&contacts, &person->it);
      }
 
      amxc_llist_for_each(it, (&contacts)) {
         person = amxc_container_of(it, person_t, it);
         printf("%s %s %d\n". person->first_name, person->last_name, person->age);
      }
 
      amxc_llist_clean(&contacts, delete_person);
      return 0;
  }

Macro Definition Documentation

amxc_llist_for_each

#define amxc_llist_for_each	(		it,
			list
	)

Value:

    for(amxc_llist_it_t* it = amxc_llist_get_first(list), \
        * it ## _next = amxc_llist_it_get_next(it); \
        it; \
        it = it ## _next, \
        it ## _next = amxc_llist_it_get_next(it))

Loops over the list from head to tail.

Iterates over the list and updates the iterator each time.

Warning

Do not modify the list itself while using this macro. It is possible to nest this macro It is allowed to delete or remove the current iterator from the list.

Definition at line 253 of file amxc_llist.h.

amxc_llist_for_each_reverse

#define amxc_llist_for_each_reverse	(		it,
			list
	)

Value:

    for(amxc_llist_it_t* it = amxc_llist_get_last(list), \
        * it ## _prev = amxc_llist_it_get_previous(it); \
        it; \
        it = it ## _prev, \
        it ## _prev = amxc_llist_it_get_previous(it))

Loops over the list from tail to head.

Iterates over the list and updates the iterator each time.

Warning

Do not modify the list itself while using this macro. It is possible to nest this macro It is allowed to delete or remove the current iterator from the list.

Definition at line 287 of file amxc_llist.h.

amxc_llist_iterate

#define amxc_llist_iterate	(		it,
			list
	)

Value:

    for(amxc_llist_it_t* it = amxc_llist_get_first(list); \
        it; \
        it = amxc_llist_it_get_next(it))

Loops over the list from head to tail.

Iterates over the list and updates the iterator each time.

Warning

Do not modify the list itself while using this macro.

Definition at line 270 of file amxc_llist.h.

amxc_llist_iterate_reverse

#define amxc_llist_iterate_reverse	(		it,
			list
	)

Value:

    for(amxc_llist_it_t* it = amxc_llist_get_last(list); \
        it; \
        it = amxc_llist_it_get_previous(it))

Loops over the list from tail to head.

Iterates over the list and updates the iterator each time.

Warning

Do not modify the list itself while using this macro.

Definition at line 304 of file amxc_llist.h.

Typedef Documentation

amxc_llist_it_delete_t

typedef void(* amxc_llist_it_delete_t) (amxc_llist_it_t *it)

Definition of the linked list item delete function.

A pointer to a delete function is used in the following functions amxc_llist_delete, amxc_llist_clean, amxc_llist_it_clean.

Definition at line 317 of file amxc_llist.h.

amxc_llist_t

typedef struct _amxc_llist amxc_llist_t

The linked list structure.

Function Documentation

amxc_llist_append()

int amxc_llist_append	(	amxc_llist_t *const	llist,
		amxc_llist_it_t *const	it
	)

Adds an item to the end of the linked list.

If the item is already in a list, it is removed from that list.

Note

Make sure that the iterator of the item is at least initialized when it is first used. Initializing an iterator can be done using amxc_llist_it_init. An iterator that is already used in a linked list is considered initialized.

Parameters

llist	a pointer to the linked list structure
it	a pointer to the linked list item iterator

Returns

returns 0 when the item is added, -1 when there was an error

Definition at line 169 of file amxc_llist.c.

                                                                            {
    int retval = -1;
    when_null(llist, exit);
    when_null(it, exit);
 
    if(it->llist != NULL) {
        amxc_llist_it_take(it);
    }
 
    it->llist = llist;
    it->prev = llist->tail;
    it->next = NULL;
 
    if(llist->tail != NULL) {
        llist->tail->next = it;
        llist->tail = it;
    } else {
        llist->tail = it;
        llist->head = it;
    }
 
    retval = 0;
 
exit:
    return retval;
}

amxc_llist_clean()

void amxc_llist_clean	(	amxc_llist_t *const	llist,
		amxc_llist_it_delete_t	func
	)

Removes all items from the linked list.

Removes all items from the linked list, if a delete function is provided, it is called for each item after it was removed from the list.

Parameters

llist	a pointer to the linked list structure
func	a pointer to a function that is called to free each item in the linked list

Definition at line 124 of file amxc_llist.c.

                                                                              {
    amxc_llist_it_t* it = llist != NULL ? llist->head : NULL;
    while(it != NULL) {
        amxc_llist_it_take(it);
        if(func != NULL) {
            func(it);
        }
        it = llist->head;
    }
}

amxc_llist_delete()

void amxc_llist_delete	(	amxc_llist_t **	llist,
		amxc_llist_it_delete_t	func
	)

Frees the previously allocated linked list.

Removes all items from the linked list, if a delete function is provided, it is called for each item after it was removed from the list.

Frees the allocated memory and sets the pointer to NULL.

Note

Only call this function for linked lists that are allocated on the heap using amxc_llist_new

Parameters

llist	a pointer to the location where the pointer to the linked list is stored
func	a pointer to a function that is called to free each item in the linked list

Definition at line 101 of file amxc_llist.c.

                                                                          {
    when_null(llist, exit);
 
    amxc_llist_clean(*llist, func);
    free(*llist);
    *llist = NULL;
exit:
    return;
}

amxc_llist_get_at()

amxc_llist_it_t* amxc_llist_get_at	(	const amxc_llist_t *const	llist,
		const unsigned int	index
	)

Gets an item at a certain position of the linked list.

This function is not removing the item from the linked list. To remove the item from the linked list use amxc_llist_take_at.

Note

This function loops over the linked list, counting each item until the desired index is reached. Avoid to use this function for big linked lists, it can have a huge impact on performance. Use amxc_llist_get_last to get the last item in the list and not this function.

Parameters

llist	a pointer to the linked list structure
index	the position of the item to get

Returns

Returns the iterator of the linked list item at the requested index, or NULL when there is no such item.

Definition at line 222 of file amxc_llist.c.

                                                             {
    amxc_llist_it_t* it = NULL;
    size_t count = 0;
 
    for(it = llist != NULL ? llist->head : NULL; it; it = it->next) {
        if(count == index) {
            break;
        }
        count++;
    }
 
    return it;
}

amxc_llist_get_first()

AMXC_INLINE amxc_llist_it_t* amxc_llist_get_first

(

const amxc_llist_t *const

llist

)

Gets the first item of the linked list.

This function does not remove the item from the linked list. To remove the item, use amxc_llist_take_first.

Parameters

llist

a pointer to the linked list structure

Returns

Returns the first iterator of the linked list, or NULL when the linked list is empty.

Definition at line 713 of file amxc_llist.h.

                                                                       {
    return llist != NULL ? llist->head : NULL;
}

amxc_llist_get_last()

AMXC_INLINE amxc_llist_it_t* amxc_llist_get_last

(

const amxc_llist_t *const

llist

)

Gets the last item of the linked list.

This function does not remove the item from the linked list. To remove the item, use amxc_llist_take_last.

Parameters

llist

a pointer to the linked list structure

Returns

Returns the last iterator of the linked list, or NULL when the linked list is empty.

Definition at line 732 of file amxc_llist.h.

                                                                      {
    return llist != NULL ? llist->tail : NULL;
}

amxc_llist_init()

int amxc_llist_init

(

amxc_llist_t *const

llist

)

Initializes a linked list.

Initializes the linked list structure. All pointers are reset to NULL. This function is typically called for linked lists that are on the stack. Allocating and initializing a linked list on the heap can be done using amxc_llist_new

Note

When calling this function on an already initialized linked list, that contains items, the linked list is reset and all items in the list are lost. Use amxc_llist_clean to remove all items from the list.

Parameters

llist

a pointer to the linked list structure.

Returns

0 on success. -1 if a NULL pointer is given.

Definition at line 111 of file amxc_llist.c.

                                               {
    int retval = -1;
    when_null(llist, exit);
 
    llist->head = NULL;
    llist->tail = NULL;
 
    retval = 0;
 
exit:
    return retval;
}

amxc_llist_is_empty()

bool amxc_llist_is_empty

(

const amxc_llist_t *const

llist

)

Checks that the linked list is empty.

Parameters

llist

a pointer to the linked list structure

Returns

returns true when the linked list contains no items, false when there is at least one item in the list.

Definition at line 165 of file amxc_llist.c.

                                                          {
    return llist != NULL ? (llist->head == NULL) : true;
}

amxc_llist_move()

int amxc_llist_move	(	amxc_llist_t *const	dest,
		amxc_llist_t *const	src
	)

Moves all items from one linked list to another linked list.

After the move the source linked list will be empty.

If the destination linked list already contains items, the items of the source are appended to the destination linked list.

Note

Moving items from one linked list to another linked list can not fail.

Parameters

dest	a pointer to the destination linked list
src	a pointer to the source linked list

Returns

Always 0.

Definition at line 135 of file amxc_llist.c.

                                                                       {
    int retval = -1;
 
    when_null(dest, exit);
    when_null(src, exit);
 
    amxc_llist_for_each(it, src) {
        amxc_llist_append(dest, it);
    }
 
    retval = 0;
 
exit:
    return retval;
}

amxc_llist_new()

int amxc_llist_new

(

amxc_llist_t **

llist

)

Allocates a linked list.

Allocates and initializes memory to store a linked list. This function allocates memory from the heap, if a linked list is on the stack, it can be initialized using function amxc_llist_init

Note

The allocated memory must be freed when not used anymore, use amxc_llist_delete to free the memory

Parameters

llist

a pointer to the location where the pointer to the new linked list can be stored

Returns

-1 if an error occured. 0 on success

Definition at line 88 of file amxc_llist.c.

                                         {
    int retval = -1;
    when_null(llist, exit);
 
    *llist = (amxc_llist_t*) calloc(1, sizeof(amxc_llist_t));
    when_null(*llist, exit);
 
    retval = 0;
 
exit:
    return retval;
}

amxc_llist_prepend()

int amxc_llist_prepend	(	amxc_llist_t *const	llist,
		amxc_llist_it_t *const	it
	)

Adds an item to the beginning of the linked list.

If the item is already in a list, it is removed from that list.

Note

Make sure that the iterator of the item is at least initialized when it is first used. Initializing an iterator can be done using amxc_llist_it_init. An iterator that is already used in a linked list is considered initialized.

Parameters

llist	a pointer to the linked list structure
it	a pointer to the linked list item iterator

Returns

returns 0 when the item is added, -1 when there was an error

Definition at line 196 of file amxc_llist.c.

                                                                             {
    int retval = -1;
    when_null(llist, exit);
    when_null(it, exit);
 
    if(it->llist != NULL) {
        amxc_llist_it_take(it);
    }
 
    it->llist = llist;
    it->next = llist->head;
    it->prev = NULL;
 
    if(llist->head != NULL) {
        llist->head->prev = it;
        llist->head = it;
    } else {
        llist->tail = it;
        llist->head = it;
    }
 
    retval = 0;
exit:
    return retval;
}

amxc_llist_set_at()

int amxc_llist_set_at	(	amxc_llist_t *	llist,
		const unsigned int	index,
		amxc_llist_it_t *const	it
	)

Inserts an item at a certain position.

If the item is already in a list, it is removed from that list. If the index is out of range (higher then number of items in the linked list) the item is not added.

Note

This function loops over the linked list, counting each item until the desired index is reached. The item is inserted before the found item. Avoid to use this function for big linked lists, it can have a huge impact on performance. Use amxc_llist_append to add an item at the end of the list and not this function.

Parameters

llist	a pointer to the linked list structure
index	the position where the item must be inserted
it	a pointer to the linked list item iterator

Returns

returns 0 when the item is added, -1 when there was an error

Definition at line 237 of file amxc_llist.c.

                                                 {
    int retval = -1;
    amxc_llist_it_t* reference = NULL;
 
    size_t count = 0;
 
    for(reference = llist != NULL ? llist->head : NULL;
        reference;
        reference = reference->next) {
        if(count == index) {
            break;
        }
        count++;
    }
 
    if(!reference && (index == count)) {
        retval = amxc_llist_append(llist, it);
    } else {
        retval = amxc_llist_it_insert_before(reference, it);
    }
    return retval;
}

amxc_llist_size()

size_t amxc_llist_size

(

const amxc_llist_t *const

llist

)

Calculates the size of the linked list.

Loops over all items in the linked list and counts them. The size of the linked list is expressed in items.

Note

Use amxc_llist_is_empty to check if a list is empty, do not use this function to check if the list is empty

Parameters

llist

a pointer to the linked list structure

Returns

returns the number of items in linked list

Definition at line 151 of file amxc_llist.c.

                                                        {
    size_t count = 0;
 
    // no check on null pointer is needed here.
    // amxc_llist_first will return null anyway.
    for(amxc_llist_it_t* it = llist != NULL ? llist->head : NULL;
        it != NULL;
        it = it->next) {
        count++;
    }
 
    return count;
}

amxc_llist_sort()

int amxc_llist_sort	(	amxc_llist_t *const	llist,
		amxc_llist_it_cmp_t	cmp
	)

Sorts a linked list.

Using a callback compare function, the items in the linked list are sorted. The callback function must match amxc_llist_it_cmp_t signature.

Parameters

llist	a pointer to the linked list
cmp	the sort compare callback function

Returns

0 when sort is done successful, any other value when sorting fails.

Definition at line 262 of file amxc_llist.c.

                                                                        {
    int retval = -1;
    when_null(llist, exit);
    when_null(cmp, exit);
 
    if(amxc_llist_is_empty(llist)) {
        retval = 0;
        goto exit;
    }
 
    retval = amxc_llist_sort_internal(llist, cmp);
 
exit:
    return retval;
}

amxc_llist_take_at()

AMXC_INLINE amxc_llist_it_t* amxc_llist_take_at	(	const amxc_llist_t *	llist,
		const unsigned int	index
	)

Removes an item at a certain position of the linked list.

This function removes the item from the linked list. To get a pointer to the item, without removing it, use amxc_llist_get_at.

Note

This function loops over the linked list, counting each item until the desired index is reached. Avoid to use this function for big linked lists, it can have a huge impact on performance. Use amxc_llist_take_last to remove the last item from the list and not this function.

Parameters

llist	a pointer to the linked list structure
index	the position of the item to get

Returns

Returns the iterator of the linked list item at the requested index, or NULL when there is no such item.

Definition at line 803 of file amxc_llist.h.

                                                              {
    amxc_llist_it_t* it = amxc_llist_get_at(llist, index);
    amxc_llist_it_take(it);
    return it;
}

amxc_llist_take_first()

AMXC_INLINE amxc_llist_it_t* amxc_llist_take_first

(

amxc_llist_t *const

llist

)

Removes the first item from the linked list.

This function removes the item from the linked list. To get the item without removing it from the list use amxc_llist_get_first.

Parameters

llist

a pointer to the linked list structure

Returns

Returns the first iterator of the linked list, or NULL when the linked list is empty.

Definition at line 752 of file amxc_llist.h.

                                                                  {
    amxc_llist_it_t* it = amxc_llist_get_first(llist);
    amxc_llist_it_take(it);
    return it;
}

amxc_llist_take_last()

AMXC_INLINE amxc_llist_it_t* amxc_llist_take_last

(

amxc_llist_t *const

llist

)

Removes the last item from the linked list.

This function removes the item from the linked list. To get the item without removing it from the list use amxc_llist_get_last.

Parameters

llist

a pointer to the linked list structure

Returns

Returns the last iterator of the linked list, or NULL when the linked list is empty.

Definition at line 774 of file amxc_llist.h.

                                                                 {
    amxc_llist_it_t* it = amxc_llist_get_last(llist);
    amxc_llist_it_take(it);
    return it;
}