include/slist.h File Reference

Singly linked list implementation. More...

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

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.

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 tail of the list to.
static void slist_move_to_head (struct slist *to, struct slist *from)
 Move all the nodes in from to the head of 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.

Copyright (C) 2009 Atmel Corporation. All rights reserved.

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 124 of file slist.h.

#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 235 of file slist.h.

Referenced by at90usb_ep0_tx_complete(), at90usb_udc_ep0_worker(), at90usb_udc_ep_flush(), at90usb_udc_submit_in_queue(), at90usb_udc_submit_out_queue(), and usb_req_get_first_buffer().

#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 271 of file slist.h.

Referenced by at90usb_udc_ep0_worker(), at90usb_udc_ep_flush(), at90usb_udc_submit_in_queue(), and at90usb_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 253 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 300 of file slist.h.

Referenced by at90usb_ep0_tx_flush(), at90usb_udc_ep_flush(), at90usb_udc_submit_in_queue(), at90usb_udc_submit_out_queue(), and workqueue_pop_task().

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 164 of file slist.h.

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

Referenced by slist_move_to_tail().

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 185 of file slist.h.

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

Referenced by at90usb_ep0_tx_complete().

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

Initialize a singly linked list.

Definition at line 75 of file slist.h.

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

Referenced by at90usb_ep0_tx_complete(), at90usb_ep0_tx_flush(), at90usb_ep_alloc(), at90usb_udc_ep0_worker(), at90usb_udc_init(), dataflash_alloc_req(), msc_submit_read_buffers(), slist_move_to_head(), slist_move_to_tail(), usb_req_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 130 of file slist.h.

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

Referenced by udc_fifo_read_data(), and udc_fifo_write_data().

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 142 of file slist.h.

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

Referenced by blk_req_add_buffer(), udc_fifo_read_data(), udc_fifo_write_data(), and usb_req_add_buffer().

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 87 of file slist.h.

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

Referenced by at90usb_ep0_tx_complete(), at90usb_ep0_tx_flush(), at90usb_udc_ep0_worker(), at90usb_udc_ep_flush(), at90usb_udc_submit_in_queue(), at90usb_udc_submit_out_queue(), slist_borrow_to_tail(), slist_move_to_head(), udc_fifo_read_data(), udc_fifo_write_data(), and workqueue_is_empty().

static void slist_move_to_head ( struct slist *  to,
struct slist *  from 
) [inline, static]

Move all the nodes in from to the head of the list to.

Precondition:
from must contain at least one node
Postcondition:
from is empty

Definition at line 209 of file slist.h.

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

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

Move all the nodes in from to the tail of the list to.

Precondition:
from must contain at least one node
Postcondition:
from is empty

Definition at line 198 of file slist.h.

References slist_borrow_to_tail(), and slist_init().

Referenced by blk_req_add_buffer_list(), and dataflash_submit_buf_list().

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 97 of file slist.h.

References slist::last.

Referenced by at90usb_udc_ep0_worker().

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 110 of file slist.h.

References slist::first.

Referenced by at90usb_udc_ep_flush(), at90usb_udc_submit_in_queue(), and at90usb_udc_submit_out_queue().

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

Return the first node in list.

Definition at line 223 of file slist.h.

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

Referenced by at90usb_udc_submit_in_queue(), and at90usb_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 259 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 241 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 278 of file slist.h.

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

Referenced by at90usb_ep0_tx_complete(), and at90usb_udc_ep0_worker().

Generated on Thu Apr 29 14:10:34 2010 for xplain-bc by  doxygen 1.6.3