fg_list.c File Reference

Generic doubly linked list implementation. More...

#include "config.h"
#include <stdlib.h>
#include "fg_list.h"

Go to the source code of this file.

Functions
static struct list_node *	create_node (void *const data, struct list_node *const previous, struct list_node *const next)
	Creates a new list element on the heap. More...
const struct list_node *	fg_list_back (struct linked_list *const list)
	Returns the last element of the list. More...
int	fg_list_clear (struct linked_list *const list)
	Removes and destroys all elements from the list, leaving it with a size of 0. More...
const struct list_node *	fg_list_front (struct linked_list *const list)
	Returns the first element of the list. More...
int	fg_list_init (struct linked_list *const list)
	Initializes the list by setting its head and tail to NULL and its size to 0. More...
void *	fg_list_pop_back (struct linked_list *const list)
	Removes the last element in the list, effectively reducing its size by one. More...
void *	fg_list_pop_front (struct linked_list *const list)
	Removes the first element in the list, effectively reducing its size by one. More...
int	fg_list_push_back (struct linked_list *const list, void *const data)
	Inserts a new element at the end of the list. More...
int	fg_list_push_front (struct linked_list *const list, void *const data)
	Inserts a new element at the beginning of the list. More...
int	fg_list_remove (struct linked_list *const list, const void *const data)
	Removes from the list the first element whose data points to data. More...
size_t	fg_list_size (struct linked_list *const list)
	Returns the number of elements in the list. More...

Detailed Description

Generic doubly linked list implementation.

Definition in file fg_list.c.

Function Documentation

create_node()

static struct list_node* create_node ( void *const  data, struct list_node *const  previous, struct list_node *const  next  )

static

Creates a new list element on the heap.

It prepares it for insertion into the list between elements pointed to by previous and next. The data of the newly created element will point to the same memory location as data.

Parameters

[in]	data	data of newly created element
[in]	previous	existing list element the new element will be inserted after
[in]	next	existing list element the new element will be inserted before

Returns

pointer to the newly created list element or NULL on failure

Definition at line 107 of file fg_list.c.

{
        struct list_node *new_node = (struct list_node*)malloc(sizeof(struct list_node));
 
        if (!new_node)
                return NULL;
 
        new_node->data = data;
        new_node->previous = previous;
        new_node->next = next;
 
        return new_node;
}

fg_list_back()

const struct list_node* fg_list_back

(

struct linked_list *const

list

)

Returns the last element of the list.

The element is not removed from the list.

Parameters

[in]

list

to operate on

Returns

a pointer to the last element in list

Definition at line 57 of file fg_list.c.

{
        if (!list)
                return NULL;
 
        return list->tail;
}

fg_list_clear()

int fg_list_clear

(

struct linked_list *const

list

)

Removes and destroys all elements from the list, leaving it with a size of 0.

Parameters

[in]

list

to operate on

Returns

zero on success, non-zero otherwise

Definition at line 219 of file fg_list.c.

{
        if (!list)
                return -1;
 
        while (fg_list_size(list)) {
                void * data = fg_list_pop_front(list);
                free(data);
        }
 
        return 0;
}

fg_list_front()

const struct list_node* fg_list_front

(

struct linked_list *const

list

)

Returns the first element of the list.

The element is not removed from the list.

Parameters

[in]

list

to operate on

Returns

a pointer to the first element in list

Definition at line 49 of file fg_list.c.

{
        if (!list)
                return NULL;
 
        return list->head;
}

fg_list_init()

int fg_list_init

(

struct linked_list *const

list

)

Initializes the list by setting its head and tail to NULL and its size to 0.

Parameters

[in]

list

list to initialize

Returns

zero on success, non-zero otherwise

Definition at line 34 of file fg_list.c.

{
        if (!list)
                return -1;
        if (list->head)
                if (!fg_list_clear(list))
                        return -2;
 
        list->head = NULL;
        list->tail = NULL;
        list->size = 0;
 
        return 0;
}

fg_list_pop_back()

void* fg_list_pop_back

(

struct linked_list *const

list

)

Removes the last element in the list, effectively reducing its size by one.

This destroys the removed element. The data contained in this element will not be modified.

Parameters

[in]

list

to operate on

Returns

pointer to the data that was contained in the removed element, NULL on failure

Definition at line 188 of file fg_list.c.

{
        if (!list)
                return NULL;
        if (!list->tail)
                return NULL;
 
        struct list_node *tail = list->tail;
        void *data = tail->data;
 
        if (tail->previous)
                tail->previous->next = NULL;
        if (list->tail == list->head)
                list->head = NULL;
 
        list->tail = tail->previous;
 
        free(tail);
        --list->size;
 
        return data;
}

fg_list_pop_front()

void* fg_list_pop_front

(

struct linked_list *const

list

)

Removes the first element in the list, effectively reducing its size by one.

This destroys the removed element. The data contained in this element will not be modified.

Parameters

[in]

list

to operate on

Returns

pointer to the data that was contained in the removed element, NULL on failure

Definition at line 144 of file fg_list.c.

{
        if (!list)
                return NULL;
        if (!list->head)
                return NULL;
 
        struct list_node *head = list->head;
 
        if (list->head == list->tail)
                list->tail = NULL;
        if (head->next)
                head->next->previous = NULL;
 
        list->head = head->next;
        void *data = head->data;
 
        free(head);
        --list->size;
 
        return data;
}

fg_list_push_back()

int fg_list_push_back	(	struct linked_list *const	list,
		void *const	data
	)

Inserts a new element at the end of the list.

The data of the new element will point to the same memory location as data. This effectively increases the list's size by one.

Parameters

[in]	list	to operate on
[in]	data	of inserted element

Returns

zero on success, non-zero otherwise

Definition at line 167 of file fg_list.c.

{
        if (!list)
                return -1;
 
        struct list_node *new_node = create_node(data, list->tail, NULL);
 
        if (!new_node)
                return -5;
 
        if (!list->head)
                list->head = new_node;
        if (list->tail)
                list->tail->next = new_node;
 
        list->tail = new_node;
        ++list->size;
 
        return 0;
}

fg_list_push_front()

int fg_list_push_front	(	struct linked_list *const	list,
		void *const	data
	)

Inserts a new element at the beginning of the list.

The data of the new element will point to the same memory location as data. This effectively increases the list's size by one.

Parameters

[in]	list	to operate on
[in]	data	of inserted element

Returns

zero on success, non-zero otherwise

Definition at line 123 of file fg_list.c.

{
        if (!list)
                return -1;
 
        struct list_node *new_node = create_node(data, NULL, list->head);
 
        if (!new_node)
                return -5;
 
        if (!list->head)
                list->tail = new_node;
        else
                list->head->previous = new_node;
 
        list->head = new_node;
        ++list->size;
 
        return 0;
}

fg_list_remove()

int fg_list_remove	(	struct linked_list *const	list,
		const void *const	data
	)

Removes from the list the first element whose data points to data.

It reduces the list size by one. The data contained in this element will not be modified.

Parameters

[in]	list	to operate on
[in]	data	of the element to be removed

Returns

zero on success, non-zero otherwise

Definition at line 65 of file fg_list.c.

{
        if (!list)
                return -1;
        if (!list->head)
                return -3;
 
        struct list_node *node = list->head;
 
        while (node->data != data) {
                node = node->next;
                if (!node)
                        return -4;
        }
 
        if (list->head == node)
                list->head = node->next;
        if (list->tail == node)
                list->tail = node->previous;
        if (node->previous)
                node->previous->next = node->next;
        if (node->next)
                node->next->previous = node->previous;
 
        free(node);
        --list->size;
 
        return 0;
}

fg_list_size()

size_t fg_list_size

(

struct linked_list *const

list

)

Returns the number of elements in the list.

Parameters

[in]

list

to operate on

Returns

the number of elements in the list

Definition at line 211 of file fg_list.c.

{
        if (!list)
                return -1;
 
        return list->size;
}