list.h : Linked List
[/general : General utility files & modules]

A doubly (forwards and backwards) linked list using pointers. More...

Data Structures
struct	list_item_t
	Link structure that must be at the head of each item in the list. More...
struct	list_t
	Linked list structure. More...
Functions
void	list_init (list_t *list, size_t max_nr_of_items)
	Initialises a linked list structure.
void	list_item_init (list_t *list, list_item_t *item)
	Initialises a list item.
bool_t	list_is_empty (list_t *list)
	See if the list is empty.
bool_t	list_is_full (list_t *list)
	See if the list is full.
size_t	list_nr_of_items (list_t *list)
	Get the number of items in the list.
list_item_t *	list_first_item (list_t *list)
	Get a pointer to the first item in the list.
list_item_t *	list_last_item (list_t *list)
	Get a pointer to the last item in the list.
list_item_t *	list_next_item (list_t *list, list_item_t *item)
	Get a pointer to the next item in the list (after the specified item).
list_item_t *	list_previous_item (list_t *list, list_item_t *item)
	Get a pointer to the previous item in the list (before the specified item).
bool_t	list_add_to_start (list_t *list, list_item_t *item)
	Insert item to the start of the list.
bool_t	list_add_to_end (list_t *list, list_item_t *item)
	Add item to the end of the list.
list_item_t *	list_remove_first_item (list_t *list)
	Remove first item from the list.
list_item_t *	list_remove_last_item (list_t *list)
	Remove last item from the list.
void	list_remove_item (list_t *list, list_item_t *item)
	Remove item from the list.
bool_t	list_item_in_list (list_t *list, list_item_t *item)
	See if item is in the list.

---

Detailed Description

Files: list.h & list.c

See also:

http://en.wikipedia.org/wiki/Linked_list

Graphical example:

  No items in list:
 
  [first = NULL] [last = NULL]
 
  One item in list:
 
  [first] -> [prev = NULL][next = NULL] <- [last]
 
  Two items in list:
 
  [first] -> [prev = NULL][next] <-> [prev][next = NULL]  <- [last]
 
  Three items in list:
 
  [first] -> [prev = NULL][next] <-> [prev][next] <-> [prev][next = NULL]  <- [last]

---

Function Documentation

void list_init	(	list_t *	list,
		size_t	max_nr_of_items
	)

Parameters:

	list	Pointer to the linked list
	max_nr_of_items	Maximum number of items allowed in list; 0 means no limit

Definition at line 58 of file list.c.

References list_t::first_item, list_t::last_item, list_t::max_nr_of_items, list_t::nr_of_items, and NULL.

{
    list->first_item      = NULL;
    list->last_item       = NULL;
    list->nr_of_items     = 0;
    list->max_nr_of_items = max_nr_of_items;
}

void list_item_init	(	list_t *	list,
		list_item_t *	item
	)

Initialises the item structure to indicate that it is not in the list.

See also:

list_item_in_list()

Parameters:

	list	Pointer to the linked list
	item	Pointer to specified item

Definition at line 67 of file list.c.

References NULL.

{
    item->previous_item = NULL;
    item->next_item     = NULL;
}

bool_t list_is_empty

(

list_t *

list

)

Parameters:

list

Pointer to the linked list

Returns:

TRUE List is empty

FALSE List contains one or more items

Definition at line 74 of file list.c.

References list_t::first_item, and NULL.

Referenced by list_add_to_end(), list_add_to_start(), list_remove_first_item(), list_remove_item(), and list_remove_last_item().

{
    if(list->first_item == NULL)
    {
        return TRUE;
    }
    else
    {
        return FALSE;
    }
}

bool_t list_is_full

(

list_t *

list

)

Parameters:

list

Pointer to the linked list

Return values:

	TRUE	The list is full
	FALSE	The list is not full, or there is no limit (max_nr_of_items = 0)

Definition at line 86 of file list.c.

References list_t::max_nr_of_items, and list_t::nr_of_items.

Referenced by list_add_to_end(), and list_add_to_start().

{
    if(list->max_nr_of_items == 0)
    {
        return FALSE;
    }

    if(list->nr_of_items < list->max_nr_of_items)
    {
        return FALSE;
    }
    else
    {
        return TRUE;
    }
}

size_t list_nr_of_items

(

list_t *

list

)

Parameters:

list

Pointer to the linked list

Returns:

size_t The number of items in the list

Definition at line 103 of file list.c.

References list_t::nr_of_items.

{
    // Return item count
    return (list->nr_of_items);
}

list_item_t* list_first_item

(

list_t *

list

)

Parameters:

list

Pointer to the linked list

Returns:

list_item_t* Pointer to the first item in the list; NULL will be returned if the list is empty.

Definition at line 109 of file list.c.

References list_t::first_item.

{
    return list->first_item;
}

list_item_t* list_last_item

(

list_t *

list

)

param list Pointer to the linked list

Returns:

list_item_t* Pointer to the last item in the list; NULL will be returned if the list is empty.

Definition at line 114 of file list.c.

References list_t::last_item.

{
    return list->last_item;
}

list_item_t* list_next_item	(	list_t *	list,
		list_item_t *	item
	)

param list Pointer to the linked list

Returns:

list_item_t* Pointer to the next item in the list; NULL will be returned if the specified item is the last one in the list.

Definition at line 119 of file list.c.

{
    return item->next_item;
}

list_item_t* list_previous_item	(	list_t *	list,
		list_item_t *	item
	)

* param list Pointer to the linked list

Returns:

list_item_t* Pointer to the next item in the list; NULL will be returned if the specified item is the first one in the list.

Definition at line 125 of file list.c.

{
    return item->previous_item;
}

bool_t list_add_to_start	(	list_t *	list,
		list_item_t *	item
	)

Parameters:

	list	Pointer to the linked list
	item	Item to be inserted

Return values:

	TRUE	Item has been inserted
	FALSE	List is full

Definition at line 131 of file list.c.

References list_t::first_item, list_t::last_item, list_is_empty(), list_is_full(), list_t::nr_of_items, and NULL.

{
    if(list_is_full(list))
    {
        return FALSE;
    }

    if(list_is_empty(list))
    {
        // Add first item
        list->first_item    = item;
        list->last_item     = item;
        item->next_item     = NULL;
        item->previous_item = NULL;
    }
    else
    {
        // Insert new item before first item
        item->previous_item             = NULL;
        item->next_item                 = list->first_item;
        list->first_item->previous_item = item;
        list->first_item                = item;
    }

    // Increment item count
    (list->nr_of_items)++;

    return TRUE;
}

bool_t list_add_to_end	(	list_t *	list,
		list_item_t *	item
	)

Parameters:

	list	Pointer to the linked list
	item	Item to be inserted

Return values:

	TRUE	Item has been inserted
	FALSE	List is full

Definition at line 162 of file list.c.

References list_t::first_item, list_t::last_item, list_is_empty(), list_is_full(), list_t::nr_of_items, and NULL.

{
    if(list_is_full(list))
    {
        return FALSE;
    }

    if(list_is_empty(list))
    {
        // Add first item
        list->first_item    = item;
        list->last_item     = item;
        item->next_item     = NULL;
        item->previous_item = NULL;
    }
    else
    {
        // Append new item to last item
        item->previous_item        = list->last_item;
        item->next_item            = NULL;
        list->last_item->next_item = item;
        list->last_item            = item;
    }

    // Increment item count
    (list->nr_of_items)++;

    return TRUE;
}

list_item_t* list_remove_first_item

(

list_t *

list

)

Parameters:

list

Pointer to the linked list

Returns:

list_item_t* Pointer to the (old) first item; NULL will be returned if the list is empty.

Definition at line 193 of file list.c.

References list_t::first_item, list_t::last_item, list_is_empty(), list_t::nr_of_items, and NULL.

Referenced by list_remove_item().

{
    list_item_t *item = list->first_item;

    // See if list is empty
    if(list_is_empty(list))
    {
        return NULL;
    }

    // See if there is only one item
    if(list->first_item == list->last_item)
    {
        list->first_item = NULL;
        list->last_item  = NULL;
    }
    else
    {
        // The next item become the first one in the list
        list->first_item          = item->next_item;
        item->next_item->previous_item = NULL;
    }

    // Clear links of removed item
    item->previous_item = NULL;
    item->next_item     = NULL;

    // Decrement item count
    (list->nr_of_items)--;

    return item;
}

list_item_t* list_remove_last_item

(

list_t *

list

)

Parameters:

list

Pointer to the linked list

Returns:

list_item_t* Pointer to the (old) last item; NULL will be returned if the list is empty.

Definition at line 226 of file list.c.

References list_t::first_item, list_t::last_item, list_is_empty(), list_t::nr_of_items, and NULL.

Referenced by list_remove_item().

{
    list_item_t *item = list->last_item;

    // See if list is empty
    if(list_is_empty(list))
    {
        return NULL;
    }

    // See if there is only one item
    if(list->first_item == list->last_item)
    {
        list->first_item = NULL;
        list->last_item  = NULL;
    }
    else
    {
        // The previous item become the last one in the list
        list->last_item                = item->previous_item;
        item->previous_item->next_item = NULL;        
    }

    // Clear links of removed item
    item->previous_item = NULL;
    item->next_item     = NULL;

    // Decrement item count
    (list->nr_of_items)--;

    return item;
}

void list_remove_item	(	list_t *	list,
		list_item_t *	item
	)

Parameters:

	list	Pointer to the linked list
	item	Item to be removed from the list

Definition at line 259 of file list.c.

References list_t::first_item, list_t::last_item, list_is_empty(), list_remove_first_item(), list_remove_last_item(), list_t::nr_of_items, and NULL.

{
    // Extra sanity check
    if(list_is_empty(list))
    {
        return;
    }

    // See if this is the first item in the list
    if(item == list->first_item)
    {
        list_remove_first_item(list);
        return;
    }

    // See if this is the last item in the list
    if(item == list->last_item)
    {
        list_remove_last_item(list);
        return;
    }

    // Link previous and next item to each other
    item->previous_item->next_item = item->next_item;
    item->next_item->previous_item = item->previous_item;
    
    // Clear links of item
    item->previous_item = NULL;
    item->next_item     = NULL;

    // Decrement item count
    (list->nr_of_items)--;
}

bool_t list_item_in_list	(	list_t *	list,
		list_item_t *	item
	)

Parameters:

	list	Pointer to the linked list
	item	Pointer to specified item

Return values:

	TRUE	Item is in the list
	FALSE	Item is not in the list

Definition at line 294 of file list.c.

References list_t::first_item, and NULL.

{
    // Start at first item in the list
    list_item_t *item_in_list = list->first_item;

    // Search all items in the list
    while(item_in_list != NULL)
    {
        if(item_in_list == item)
        {
            // Item is in the list
            return TRUE;
        }
        // Next item
        item_in_list = item_in_list->next_item;
    }
    // Item is not in the list
    return FALSE;
}