# include/slist.h File Reference

Singly linked list implementation. More...

`#include <assert.h>`
`#include <types.h>`

Include dependency graph for slist.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

## Data Structures
struct | slist_node
| A node in a singly linked list. More...
struct | slist
| A singly linked list. More...
## Defines
#define | slist_entry(node, type, member) container_of(node, type, member)
| Access the containing structure of node.
#define | slist_peek_head(list, type, member) slist_entry(slist_peek_head_node(list), type, member)
| Return the first item in list.
#define | slist_peek_tail(list, type, member) slist_entry(slist_peek_tail_node(list), type, member)
| Return the last item in list.
#define | slist_peek_next(node, type, member) slist_entry(slist_peek_next_node(node), type, member)
| Return the node following node in list.
#define | slist_pop_head(list, type, member) container_of(slist_pop_head_node(list), type, member)
| Return the first item in list and remove it.
#define | slist_for_each_node(list, node)
| Iterate over each node in list.
#define | slist_for_each_node_safe(list, node, tmp)
| Iterate over each node in list, allowing removal of the current node.
#define | slist_for_each(list, item, member)
| Iterate over each item in list.
#define | slist_for_each_safe(list, item, tmp, member)
| Iterate over each item in list, allowing removal of the current item.
## Functions
static void | slist_init (struct slist *list)
| Initialize a singly linked list.
static bool | slist_is_empty (struct slist *list)
| Determine if list is empty.
static bool | slist_node_is_last (struct slist *list, struct slist_node *node)
| Determine if node is the last node in list.
static bool | slist_node_is_valid (struct slist *list, struct slist_node *node)
| Determine if node represents an item in list (i.e. is not the sentinel node).
static void | slist_insert_head (struct slist *list, struct slist_node *node)
| Insert node as the first node in list.
static void | slist_insert_tail (struct slist *list, struct slist_node *node)
| Insert node as the last node in list.
static void | slist_borrow_to_tail (struct slist *to, struct slist *from)
| Borrow the list from appending it to the tail of to.
static void | slist_give_back_head (struct slist *to, struct slist *from)
| Give back nodes borrowed from to currently at the head of from.
static void | slist_move_to_tail (struct slist *to, struct slist *from)
| Move all the nodes in from to the list to.
static struct slist_node * | slist_peek_head_node (struct slist *list)
| Return the first node in list.
static struct slist_node * | slist_peek_tail_node (struct slist *list)
| Return the last node in list.
static struct slist_node * | slist_peek_next_node (struct slist_node *node)
| Return the node following node in the list.
static struct slist_node * | slist_pop_head_node (struct slist *list)
| Return the first node in list and remove it.

## Detailed Description

Singly linked list implementation.

This is a generic implementation of singly linked lists. Each list is represented by a struct slist, which is typically embedded in another struct. Each list item is represented by a struct slist_node, which is also typically embedded in another struct.

- Compiler: IAR EWAVR32 and GNU GCC for AVR32
- Supported devices: All devices
- AppNote:

Author:
  Atmel Corporation: http://www.atmel.com
  Support and FAQ: http://support.atmel.no/

Definition in file slist.h.

## Define Documentation

#define slist_entry | ( | node,
|  | type,
|  | member |  | ) | container_of(node, type, member)

Access the containing structure of node.

Parameters:

  | node | A singly-linked list node
  | type | The type of the containing structure
  | member | The member of the containing struct that holds node

Returns:
  A pointer to the containing structure

Definition at line 127 of file slist.h.

#define slist_for_each | ( | list,
|  | item,
|  | member |  | ) |

Value:

    for (item = slist_peek_head(list, typeof(*item), member);       \
                            &item->node != &(list)->first;                  \
                            item = slist_peek_next(&item->member,           \
                                    typeof(*item), member))

Iterate over each item in list.

Parameters:

  | list | The list
  | item | Variable holding each item
  | member | The member of the item struct holding the list node

Definition at line 315 of file slist.h.

Referenced by aes_duplicate_buffer_refs(), and gpio_priv_irq_group_interrupt().

#define slist_for_each_node | ( | list,
|  | node |  | ) |

Value:

    for (node = (list)->first.next; node != &(list)->first;         \
                            node = node->next)

Iterate over each node in list.

Definition at line 293 of file slist.h.

#define slist_for_each_node_safe | ( | list,
|  | node,
|  | tmp |  | ) |

Value:

    for (node = (list)->first.next, tmp = node->next;               \
                            node != &(list)->first;                         \
                            node = tmp, tmp = node->next)

Iterate over each node in list, allowing removal of the current node.

Parameters:

  | list | The list
  | node | Variable holding each node
  | tmp | Variable holding the node following node

Definition at line 304 of file slist.h.

#define slist_for_each_safe | ( | list,
|  | item,
|  | tmp,
|  | member |  | ) |

Value:

    for (item = slist_peek_head(list, typeof(*item), member),       \
                            tmp = slist_peek_next(&item->member,            \
                                            typeof(*item), member);         \
                            &item->node != &(list)->first;                  \
                            item = tmp,                                     \
                            tmp = slist_peek_next(&item->member,            \
                                            typeof(*item), member))         \

Iterate over each item in list, allowing removal of the current item.

Parameters:

  | list | The list
  | item | Variable holding each item
  | tmp | Variable holding the item following item
  | member | The member of the item struct holding the list node

Definition at line 329 of file slist.h.

Referenced by usbb_udc_submit_in_queue(), and usbb_udc_submit_out_queue().

#define slist_peek_head | ( | list,
|  | type,
|  | member |  | ) | slist_entry(slist_peek_head_node(list), type, member)

Return the first item in list.

Parameters:

  | list | The list
  | type | The type of the item stored in list
  | member | The member of the item struct holding the list node

Definition at line 222 of file slist.h.

Referenced by usb_req_get_first_buffer(), usbb_udc_dma_interrupt(), usbb_udc_submit_in_queue(), and usbb_udc_submit_out_queue().

#define slist_peek_next | ( | node,
|  | type,
|  | member |  | ) | slist_entry(slist_peek_next_node(node), type, member)

Return the node following node in list.

Parameters:

  | node | A list node
  | type | The type of the item stored in list
  | member | The member of the item struct holding the list node

Definition at line 258 of file slist.h.

Referenced by usbb_udc_submit_in_queue(), and usbb_udc_submit_out_queue().

#define slist_peek_tail | ( | list,
|  | type,
|  | member |  | ) | slist_entry(slist_peek_tail_node(list), type, member)

Return the last item in list.

Parameters:

  | list | The list
  | type | The type of the item stored in list
  | member | The member of the item struct holding the list node

Definition at line 240 of file slist.h.

#define slist_pop_head | ( | list,
|  | type,
|  | member |  | ) | container_of(slist_pop_head_node(list), type, member)

Return the first item in list and remove it.

Parameters:

  | list | The list
  | type | The type of the item stored in list
  | member | The member of the item struct holding the list node

Precondition:
  list is not empty

Definition at line 287 of file slist.h.

Referenced by aes_free_duplicate_buffers(), block_copy_free(), usbb_udc_dma_interrupt(), and workqueue_remove_item().

## Function Documentation

static void slist_borrow_to_tail | ( | struct slist * | to,
|  | struct slist * | from |
| ) |  |  | `[inline, static]`

Borrow the list from appending it to the tail of to.

This appends all the nodes in from to the end of the list to. The nodes are still reachable from from, but there may be additional nodes at the end. The list from must not be modified or iterated over until the nodes are handed back using slist_give_back_head().

Precondition:
  from must contain at least one node

Postcondition:
  The last node in from does not point to from's sentinel node.

  The tail of from points to the last element in from

Definition at line 167 of file slist.h.

References assert, slist::first, slist::last, slist_node::next, and slist_is_empty().

Referenced by slist_move_to_tail(), udc_ep0_submit_in_req(), udc_ep0_submit_out_req(), udc_ep_submit_in_req(), and udc_ep_submit_out_req().

Here is the call graph for this function:

static void slist_give_back_head | ( | struct slist * | to,
|  | struct slist * | from |
| ) |  |  | `[inline, static]`

Give back nodes borrowed from to currently at the head of from.

This restores the state of the list to as it was before from borrowed nodes from it. After this, from will contain any nodes following the ones borrowed from to.

Precondition:
  The head of from must point to any of the nodes that were borrowed from to.

Postcondition:
  The last node in to points to to's sentinel node

Definition at line 188 of file slist.h.

References slist::first, slist::last, and slist_node::next.

static void slist_init | ( | struct slist * | list | ) | `[inline, static]`

Initialize a singly linked list.

Definition at line 78 of file slist.h.

References slist::first, slist::last, and slist_node::next.

Referenced by aes_prepare_request(), aesblk_prepare_req(), block_copy_alloc(), dmac_req_init(), msc_submit_read_buffers(), sdmmc_mcihost_init(), sdmmc_mcihost_load_data(), sdmmc_req_init(), slist_move_to_tail(), udc_ep_create(), usb_req_init(), usbb_udc_init(), and workqueue_init().

static void slist_insert_head | ( | struct slist * | list,
|  | struct slist_node * | node |
| ) |  |  | `[inline, static]`

Insert node as the first node in list.

Definition at line 133 of file slist.h.

References slist::first, slist::last, and slist_node::next.

Referenced by usbb_udc_dma_interrupt().

static void slist_insert_tail | ( | struct slist * | list,
|  | struct slist_node * | node |
| ) |  |  | `[inline, static]`

Insert node as the last node in list.

Definition at line 145 of file slist.h.

References slist::first, slist::last, and slist_node::next.

Referenced by aes_duplicate_buffer_refs(), blk_req_add_buffer(), block_copy_alloc(), dmac_req_add_buffer(), gpio_register_irq_handler(), sdmmc_req_prep_data(), udc_ep0_submit_in_req(), udc_ep0_submit_out_req(), udc_ep_submit_in_req(), udc_ep_submit_out_req(), usb_req_add_buffer(), workqueue_add_item(), and workqueue_add_item_safe().

static bool slist_is_empty | ( | struct slist * | list | ) | `[inline, static]`

Determine if list is empty.

Return values:

  | true | list is empty
  | false | list contains at least one node besides the sentinel node.

Definition at line 90 of file slist.h.

References slist::first, and slist_node::next.

Referenced by aes_free_duplicate_buffers(), aes_free_request(), aes_prepare_request(), aes_submit_request(), block_copy_free(), sdmmc_mcihost_load_data(), slist_borrow_to_tail(), udc_ep0_submit_in_req(), udc_ep0_submit_out_req(), usbb_udc_dma_interrupt(), usbb_udc_submit_in_queue(), usbb_udc_submit_out_queue(), and workqueue_is_empty().

static void slist_move_to_tail | ( | struct slist * | to,
|  | struct slist * | from |
| ) |  |  | `[inline, static]`

Move all the nodes in from to the list to.

Precondition:
  from must contain at least one node

Postcondition:
  from is empty

Definition at line 201 of file slist.h.

References slist_borrow_to_tail(), and slist_init().

Referenced by aes_prepare_request(), aes_submit_request(), blk_req_add_buffer_list(), and sdmmc_mcihost_load_data().

Here is the call graph for this function:

static bool slist_node_is_last | ( | struct slist * | list,
|  | struct slist_node * | node |
| ) |  |  | `[inline, static]`

Determine if node is the last node in list.

Return values:

  | true | node is the last node in list
  | false | node is not the last node in list

Definition at line 100 of file slist.h.

References slist::last.

Referenced by usbb_udc_submit_in_queue(), and usbb_udc_submit_out_queue().

static bool slist_node_is_valid | ( | struct slist * | list,
|  | struct slist_node * | node |
| ) |  |  | `[inline, static]`

Determine if node represents an item in list (i.e. is not the sentinel node).

Return values:

  | true | node represents an actual item
  | false | node is the sentinel node (i.e. one past the end of the list)

Definition at line 113 of file slist.h.

References slist::first.

static struct slist_node* slist_peek_head_node | ( | struct slist * | list | ) | `[static, read]`

Return the first node in list.

Definition at line 210 of file slist.h.

References assert, slist::first, and slist_node::next.

Referenced by usbb_udc_submit_in_queue(), and usbb_udc_submit_out_queue().

static struct slist_node* slist_peek_next_node | ( | struct slist_node * | node | ) | `[static, read]`

Return the node following node in the list.

Definition at line 246 of file slist.h.

References assert, and slist_node::next.

static struct slist_node* slist_peek_tail_node | ( | struct slist * | list | ) | `[static, read]`

Return the last node in list.

Definition at line 228 of file slist.h.

References assert, and slist::last.

static struct slist_node* slist_pop_head_node | ( | struct slist * | list | ) | `[static, read]`

Return the first node in list and remove it.

Precondition:
  list is not empty

Definition at line 265 of file slist.h.

References assert, slist::first, slist::last, and slist_node::next.