plist: add new implementation
PATCH 2/3 plist: add new implementation
New implementation. It is smaller, and in my opinion cleaner. User-space test: http://www.tv-sign.ru/oleg/plist.tgz
Like hlist, it has different types for head and node: pl_head/pl_node.
pl_head does not have ->prio field. This saves sizeof(int), and we don't need to have it in plist_del's parameter list. This is also good for typechecking.
Like list_add(), plist_add() does not require initialization on pl_node, except ->prio.
Signed-off-by Oleg Nesterov <[email protected]>
include/linux/plist.h new file +75 -0
@@ -0,0 +1,75 @@ +#ifndef _LINUX_PLIST_H_ +#define _LINUX_PLIST_H_ + +#include <linux/list.h> + +struct pl_head { +struct list_head prio_list; +struct list_head node_list; +}; + +struct pl_node { +int prio; +struct pl_head plist; +}; + +#define PL_HEAD_INIT (head) \ +{ \ + .prio_list = LIST_HEAD_INIT((head).prio_list), \ + .node_list = LIST_HEAD_INIT((head).node_list), \ +} + +#define PL_NODE_INIT (node, __prio) \ +{ \ + .prio = (__prio), \ + .plist = PL_HEAD_INIT((node).plist), \ +} + +static inline void pl_head_init (struct pl_head *head) +{ +INIT_LIST_HEAD (&head->prio_list); +INIT_LIST_HEAD (&head->node_list); +} + +static inline void pl_node_init (struct pl_node *node,int prio) +{ + node->prio = prio; +pl_head_init (&node->plist); +} + +extern void plist_add (struct pl_node *node,struct pl_head *head); +extern void plist_del (struct pl_node *node); + +#define plist_for_each (pos, head) \ + list_for_each_entry(pos, &(head)->node_list, plist.node_list) + +#define plist_for_each_safe (pos, n, head) \ + list_for_each_entry_safe(pos, n, &(head)->node_list, plist.node_list) + +#define plist_for_each_entry (pos, head, mem) \ + list_for_each_entry(pos, &(head)->node_list, mem.plist.node_list) + +#define plist_for_each_entry_safe (pos, n, head, mem) \ + list_for_each_entry_safe(pos, n, &(head)->node_list, mem.plist.node_list) + +static inline int plist_empty (const struct pl_head *head) +{ +return list_empty (&head->node_list); +} + +static inline int plist_unhashed (const struct pl_node *node) +{ +return list_empty (&node->plist.node_list); +} + +/* All functions below assume the pl_head is not empty. */ + +#define plist_first_entry (head, type, member) \ + container_of(plist_first(head), type, member) + +static inline struct pl_node *plist_first (const struct pl_head *head) +{ + return list_entry((head)->node_list.next, struct pl_node, plist.node_list); +} + +#endif
lib/plist.c new file +36 -0
@@ -0,0 +1,36 @@ +/* +* lib/plist.c - Priority List implementation. +*/ + +#include <linux/plist.h> + +void plist_add (struct pl_node *node,struct pl_head *head) +{ +struct pl_node *iter; + +INIT_LIST_HEAD (&node->plist.prio_list); + +list_for_each_entry (iter, &head->prio_list, plist.prio_list) +if (node->prio < iter->prio) + goto lt_prio; +else if (node->prio == iter->prio) { + iter =plist_prio_next (&iter->plist); + goto eq_prio; + } + +lt_prio: +list_add_tail (&node->plist.prio_list, &iter->plist.prio_list); +eq_prio: +list_add_tail (&node->plist.node_list, &iter->plist.node_list); +} + +void plist_del (struct pl_node *node) +{ +if (!list_empty (&node->plist.prio_list)) { +struct pl_node *next =plist_next (&node->plist); +list_move_tail (&next->plist.prio_list, &node->plist.prio_list); +list_del_init (&node->plist.prio_list); + } + +list_del_init (&node->plist.node_list); +}