sl_list.h File Reference

Detailed Description

Single linked list. Each list must have a head (struct sl_list_head_t) that is initiliazed with sl_list_init() function. List items must contain struct sl_list_t as its first member.

Example:

list_head_t head;
 
struct my_item {
    sl_list_t list; // Reserved for sl_list use
    // Remaining of the struct can be used as required
    char my_data[MY_DATA_LEN];
};
 
struct my_item item;
 
sl_list_init(&head);
sl_list_push_back(&head, &item);

Single linked list allows fast adding to both back and front, and fast removing from front (see the table of operations and their execution time below). Thus, FIFO list should be implemented by pushing to back and popping from front.

Operation  | Time
-----------+--------
push back  | O(1)
push front | O(1)
pop        | O(n)
pop front  | O(1)
pop back   | O(n)
size       | O(1)
at         | O(n)
search     | O(n)

Definition in file sl_list.h.

Go to the source code of this file.

Functions
void	sl_list_init (sl_list_head_t *list_head)
sl_list_t *	sl_list_next (const sl_list_t *iter)
void	sl_list_push_before (sl_list_head_t *list_head, const sl_list_t *iter, sl_list_t *element)
void	sl_list_push_back (sl_list_head_t *list_head, sl_list_t *element)
void	sl_list_push_front (sl_list_head_t *list_head, sl_list_t *element)
sl_list_t *	sl_list_pop_front (sl_list_head_t *list_head)
sl_list_t *	sl_list_pop_back (sl_list_head_t *list_head)
sl_list_t *	sl_list_pop (sl_list_head_t *list_head, sl_list_t *element)
sl_list_t *	sl_list_remove (sl_list_head_t *list_head, sl_list_t *element)
sl_list_t *	sl_list_at (const sl_list_head_t *list_head, int idx)
unsigned char	sl_list_contains (const sl_list_head_t *list_head, const sl_list_t *element)
sl_list_t *	sl_list_search (const sl_list_t *start, int(*match)(const sl_list_t *, const void *), const void *match_param)
void	sl_list_swap (sl_list_head_t *list1, sl_list_head_t *list2)

Data Structures
struct	sl_list_head_t
struct	sl_list_t

Macros
#define	sl_list_empty(l)   ((l)->next == NULL)
#define	sl_list_begin(l)   sl_list_next((sl_list_t *) l)
#define	sl_list_end(l)   ((sl_list_t *) NULL)
#define	sl_list_front(l)   ((sl_list_t *)(l)->next)
#define	SL_LIST_ITER_NEXT(iter)   { (iter) = (((sl_list_t *)(iter))->next); }
#define	sl_list_size(l)   ((l)->size)

Function Documentation

sl_list_at()

sl_list_t * sl_list_at	(	const sl_list_head_t *	list_head,
		int	idx
	)

sl_list_contains()

unsigned char sl_list_contains	(	const sl_list_head_t *	list_head,
		const sl_list_t *	element
	)

Returns 1 if the named element is in the list.

sl_list_init()

void sl_list_init

(

sl_list_head_t *

list_head

)

sl_list_next()

sl_list_t * sl_list_next

(

const sl_list_t *

iter

)

Returns next element in the list.

Example

sl_list_t * item = sl_list_begin(list);
while (item != sl_list_end(list))
{
    // ...
    item = sl_list_next(item);
}

sl_list_pop()

sl_list_t * sl_list_pop	(	sl_list_head_t *	list_head,
		sl_list_t *	element
	)

Removes named element from the list.

sl_list_pop_back()

sl_list_t * sl_list_pop_back

(

sl_list_head_t *

list_head

)

sl_list_pop_front()

sl_list_t * sl_list_pop_front

(

sl_list_head_t *

list_head

)

sl_list_push_back()

void sl_list_push_back	(	sl_list_head_t *	list_head,
		sl_list_t *	element
	)

sl_list_push_before()

void sl_list_push_before	(	sl_list_head_t *	list_head,
		const sl_list_t *	iter,
		sl_list_t *	element
	)

sl_list_push_front()

void sl_list_push_front	(	sl_list_head_t *	list_head,
		sl_list_t *	element
	)

sl_list_remove()

sl_list_t * sl_list_remove	(	sl_list_head_t *	list_head,
		sl_list_t *	element
	)

Removes named element form the list and returns the previous element,

sl_list_search()

sl_list_t * sl_list_search	(	const sl_list_t *	start,
		int(*)(const sl_list_t *, const void *)	match,
		const void *	match_param
	)

sl_list_swap()

void sl_list_swap	(	sl_list_head_t *	list1,
		sl_list_head_t *	list2
	)

Swaps the contents of two lists.

---

Data Structure Documentation

sl_list_head_t

struct sl_list_head_t

Definition at line 55 of file sl_list.h.

Data Fields
struct sl_list_t *	last
struct sl_list_t *	next
uint32_t	size	Amount of items in the list

sl_list_t

struct sl_list_t

Definition at line 63 of file sl_list.h.

Data Fields
struct sl_list_t *	next

Macro Definition Documentation

sl_list_begin

#define sl_list_begin

(

l

)

sl_list_next((sl_list_t *) l)

Definition at line 75 of file sl_list.h.

sl_list_empty

#define sl_list_empty

(

l

)

((l)->next == NULL)

Definition at line 70 of file sl_list.h.

sl_list_end

#define sl_list_end

(

l

)

((sl_list_t *) NULL)

Definition at line 78 of file sl_list.h.

sl_list_front

#define sl_list_front

(

l

)

((sl_list_t *)(l)->next)

Definition at line 80 of file sl_list.h.

SL_LIST_ITER_NEXT

#define SL_LIST_ITER_NEXT

(

iter

)

{ (iter) = (((sl_list_t *)(iter))->next); }

Definition at line 83 of file sl_list.h.

sl_list_size

#define sl_list_size

(

l

)

((l)->size)

Definition at line 125 of file sl_list.h.