1 /* 2 * lib/plist.c 3 * 4 * Descending-priority-sorted double-linked list 5 * 6 * (C) 2002-2003 Intel Corp 7 * Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>. 8 * 9 * 2001-2005 (c) MontaVista Software, Inc. 10 * Daniel Walker <dwalker@mvista.com> 11 * 12 * (C) 2005 Thomas Gleixner <tglx@linutronix.de> 13 * 14 * Simplifications of the original code by 15 * Oleg Nesterov <oleg@tv-sign.ru> 16 * 17 * Licensed under the FSF's GNU Public License v2 or later. 18 * 19 * Based on simple lists (include/linux/list.h). 20 * 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 23 * information. 24 */ 25 26 #include <linux/plist.h> 27 #include <linux/spinlock.h> 28 29 #ifdef CONFIG_DEBUG_PI_LIST 30 31 static void plist_check_prev_next(struct list_head *t, struct list_head *p, 32 struct list_head *n) 33 { 34 WARN(n->prev != p || p->next != n, 35 "top: %p, n: %p, p: %p\n" 36 "prev: %p, n: %p, p: %p\n" 37 "next: %p, n: %p, p: %p\n", 38 t, t->next, t->prev, 39 p, p->next, p->prev, 40 n, n->next, n->prev); 41 } 42 43 static void plist_check_list(struct list_head *top) 44 { 45 struct list_head *prev = top, *next = top->next; 46 47 plist_check_prev_next(top, prev, next); 48 while (next != top) { 49 prev = next; 50 next = prev->next; 51 plist_check_prev_next(top, prev, next); 52 } 53 } 54 55 static void plist_check_head(struct plist_head *head) 56 { 57 WARN_ON(!head->rawlock && !head->spinlock); 58 if (head->rawlock) 59 WARN_ON_SMP(!raw_spin_is_locked(head->rawlock)); 60 if (head->spinlock) 61 WARN_ON_SMP(!spin_is_locked(head->spinlock)); 62 plist_check_list(&head->prio_list); 63 plist_check_list(&head->node_list); 64 } 65 66 #else 67 # define plist_check_head(h) do { } while (0) 68 #endif 69 70 /** 71 * plist_add - add @node to @head 72 * 73 * @node: &struct plist_node pointer 74 * @head: &struct plist_head pointer 75 */ 76 void plist_add(struct plist_node *node, struct plist_head *head) 77 { 78 struct plist_node *iter; 79 80 plist_check_head(head); 81 WARN_ON(!plist_node_empty(node)); 82 83 list_for_each_entry(iter, &head->prio_list, plist.prio_list) { 84 if (node->prio < iter->prio) 85 goto lt_prio; 86 else if (node->prio == iter->prio) { 87 iter = list_entry(iter->plist.prio_list.next, 88 struct plist_node, plist.prio_list); 89 goto eq_prio; 90 } 91 } 92 93 lt_prio: 94 list_add_tail(&node->plist.prio_list, &iter->plist.prio_list); 95 eq_prio: 96 list_add_tail(&node->plist.node_list, &iter->plist.node_list); 97 98 plist_check_head(head); 99 } 100 101 /** 102 * plist_del - Remove a @node from plist. 103 * 104 * @node: &struct plist_node pointer - entry to be removed 105 * @head: &struct plist_head pointer - list head 106 */ 107 void plist_del(struct plist_node *node, struct plist_head *head) 108 { 109 plist_check_head(head); 110 111 if (!list_empty(&node->plist.prio_list)) { 112 struct plist_node *next = plist_first(&node->plist); 113 114 list_move_tail(&next->plist.prio_list, &node->plist.prio_list); 115 list_del_init(&node->plist.prio_list); 116 } 117 118 list_del_init(&node->plist.node_list); 119 120 plist_check_head(head); 121 } 122