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->lock); 58 if (head->lock) 59 WARN_ON_SMP(!spin_is_locked(head->lock)); 60 plist_check_list(&head->prio_list); 61 plist_check_list(&head->node_list); 62 } 63 64 #else 65 # define plist_check_head(h) do { } while (0) 66 #endif 67 68 /** 69 * plist_add - add @node to @head 70 * 71 * @node: &struct plist_node pointer 72 * @head: &struct plist_head pointer 73 */ 74 void plist_add(struct plist_node *node, struct plist_head *head) 75 { 76 struct plist_node *iter; 77 78 plist_check_head(head); 79 WARN_ON(!plist_node_empty(node)); 80 81 list_for_each_entry(iter, &head->prio_list, plist.prio_list) { 82 if (node->prio < iter->prio) 83 goto lt_prio; 84 else if (node->prio == iter->prio) { 85 iter = list_entry(iter->plist.prio_list.next, 86 struct plist_node, plist.prio_list); 87 goto eq_prio; 88 } 89 } 90 91 lt_prio: 92 list_add_tail(&node->plist.prio_list, &iter->plist.prio_list); 93 eq_prio: 94 list_add_tail(&node->plist.node_list, &iter->plist.node_list); 95 96 plist_check_head(head); 97 } 98 99 /** 100 * plist_del - Remove a @node from plist. 101 * 102 * @node: &struct plist_node pointer - entry to be removed 103 * @head: &struct plist_head pointer - list head 104 */ 105 void plist_del(struct plist_node *node, struct plist_head *head) 106 { 107 plist_check_head(head); 108 109 if (!list_empty(&node->plist.prio_list)) { 110 struct plist_node *next = plist_first(&node->plist); 111 112 list_move_tail(&next->plist.prio_list, &node->plist.prio_list); 113 list_del_init(&node->plist.prio_list); 114 } 115 116 list_del_init(&node->plist.node_list); 117 118 plist_check_head(head); 119 } 120