]>
git.proxmox.com Git - mirror_ubuntu-jammy-kernel.git/blob - lib/plist.c
4 * Descending-priority-sorted double-linked list
6 * (C) 2002-2003 Intel Corp
7 * Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>.
9 * 2001-2005 (c) MontaVista Software, Inc.
10 * Daniel Walker <dwalker@mvista.com>
12 * (C) 2005 Thomas Gleixner <tglx@linutronix.de>
14 * Simplifications of the original code by
15 * Oleg Nesterov <oleg@tv-sign.ru>
17 * Licensed under the FSF's GNU Public License v2 or later.
19 * Based on simple lists (include/linux/list.h).
21 * This file contains the add / del functions which are considered to
22 * be too large to inline. See include/linux/plist.h for further
26 #include <linux/plist.h>
27 #include <linux/spinlock.h>
29 #ifdef CONFIG_DEBUG_PI_LIST
31 static void plist_check_prev_next(struct list_head
*t
, struct list_head
*p
,
34 if (n
->prev
!= p
|| p
->next
!= n
) {
35 printk("top: %p, n: %p, p: %p\n", t
, t
->next
, t
->prev
);
36 printk("prev: %p, n: %p, p: %p\n", p
, p
->next
, p
->prev
);
37 printk("next: %p, n: %p, p: %p\n", n
, n
->next
, n
->prev
);
42 static void plist_check_list(struct list_head
*top
)
44 struct list_head
*prev
= top
, *next
= top
->next
;
46 plist_check_prev_next(top
, prev
, next
);
50 plist_check_prev_next(top
, prev
, next
);
54 static void plist_check_head(struct plist_head
*head
)
58 WARN_ON_SMP(!spin_is_locked(head
->lock
));
59 plist_check_list(&head
->prio_list
);
60 plist_check_list(&head
->node_list
);
64 # define plist_check_head(h) do { } while (0)
68 * plist_add - add @node to @head
70 * @node: &struct plist_node pointer
71 * @head: &struct plist_head pointer
73 void plist_add(struct plist_node
*node
, struct plist_head
*head
)
75 struct plist_node
*iter
;
77 plist_check_head(head
);
78 WARN_ON(!plist_node_empty(node
));
80 list_for_each_entry(iter
, &head
->prio_list
, plist
.prio_list
) {
81 if (node
->prio
< iter
->prio
)
83 else if (node
->prio
== iter
->prio
) {
84 iter
= list_entry(iter
->plist
.prio_list
.next
,
85 struct plist_node
, plist
.prio_list
);
91 list_add_tail(&node
->plist
.prio_list
, &iter
->plist
.prio_list
);
93 list_add_tail(&node
->plist
.node_list
, &iter
->plist
.node_list
);
95 plist_check_head(head
);
99 * plist_del - Remove a @node from plist.
101 * @node: &struct plist_node pointer - entry to be removed
102 * @head: &struct plist_head pointer - list head
104 void plist_del(struct plist_node
*node
, struct plist_head
*head
)
106 plist_check_head(head
);
108 if (!list_empty(&node
->plist
.prio_list
)) {
109 struct plist_node
*next
= plist_first(&node
->plist
);
111 list_move_tail(&next
->plist
.prio_list
, &node
->plist
.prio_list
);
112 list_del_init(&node
->plist
.prio_list
);
115 list_del_init(&node
->plist
.node_list
);
117 plist_check_head(head
);