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. | |
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 slist_entry | ( | node, | |||
| type, | |||||
| member | ) | container_of(node, type, member) |
| #define slist_peek_head | ( | list, | |||
| type, | |||||
| member | ) | slist_entry(slist_peek_head_node(list), type, member) |
| #define slist_peek_next | ( | node, | |||
| type, | |||||
| member | ) | slist_entry(slist_peek_next_node(node), type, member) |
| #define slist_peek_tail | ( | list, | |||
| type, | |||||
| member | ) | slist_entry(slist_peek_tail_node(list), type, member) |
| #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.
| 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 300 of file slist.h.
Referenced by workqueue_pop_task().
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().
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().
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.
Definition at line 185 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 75 of file slist.h.
References slist::first, slist::last, and slist_node::next.
Referenced by dataflash_alloc_req(), slist_move_to_head(), slist_move_to_tail(), 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.
| 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().
| static bool slist_is_empty | ( | struct slist * | list | ) | [inline, static] |
Determine if list is empty.
| 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 slist_borrow_to_tail(), slist_move_to_head(), and workqueue_is_empty().
Move all the nodes in from to the head of the list to.
Definition at line 209 of file slist.h.
References assert, slist::first, slist::last, slist_node::next, slist_init(), and slist_is_empty().
Move all the nodes in from to the tail of the list to.
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.
| 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.
| 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).
| 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.
| 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.
| 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.
Definition at line 278 of file slist.h.
References assert, slist::first, slist::last, and slist_node::next.
1.6.3