lib/plist.c

   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/bug.h>
  27 #include <linux/plist.h>
  28 #include <linux/spinlock.h>
  29
  30 #ifdef CONFIG_DEBUG_PI_LIST
  31
  32 static struct plist_head test_head;
  33
  34 static void plist_check_prev_next(struct list_head *t, struct list_head *p,
  35                                   struct list_head *n)
  36 {
  37         WARN(n->prev != p || p->next != n,
  38                         "top: %p, n: %p, p: %p\n"
  39                         "prev: %p, n: %p, p: %p\n"
  40                         "next: %p, n: %p, p: %p\n",
  41                          t, t->next, t->prev,
  42                         p, p->next, p->prev,
  43                         n, n->next, n->prev);
  44 }
  45
  46 static void plist_check_list(struct list_head *top)
  47 {
  48         struct list_head *prev = top, *next = top->next;
  49
  50         plist_check_prev_next(top, prev, next);
  51         while (next != top) {
  52                 prev = next;
  53                 next = prev->next;
  54                 plist_check_prev_next(top, prev, next);
  55         }
  56 }
  57
  58 static void plist_check_head(struct plist_head *head)
  59 {
  60         if (!plist_head_empty(head))
  61                 plist_check_list(&plist_first(head)->prio_list);
  62         plist_check_list(&head->node_list);
  63 }
  64
  65 #else
  66 # define plist_check_head(h)    do { } while (0)
  67 #endif
  68
  69 /**
  70  * plist_add - add @node to @head
  71  *
  72  * @node:       &struct plist_node pointer
  73  * @head:       &struct plist_head pointer
  74  */
  75 void plist_add(struct plist_node *node, struct plist_head *head)
  76 {
  77         struct plist_node *first, *iter, *prev = NULL;
  78         struct list_head *node_next = &head->node_list;
  79
  80         plist_check_head(head);
  81         WARN_ON(!plist_node_empty(node));
  82         WARN_ON(!list_empty(&node->prio_list));
  83
  84         if (plist_head_empty(head))
  85                 goto ins_node;
  86
  87         first = iter = plist_first(head);
  88
  89         do {
  90                 if (node->prio < iter->prio) {
  91                         node_next = &iter->node_list;
  92                         break;
  93                 }
  94
  95                 prev = iter;
  96                 iter = list_entry(iter->prio_list.next,
  97                                 struct plist_node, prio_list);
  98         } while (iter != first);
  99
 100         if (!prev || prev->prio != node->prio)
 101                 list_add_tail(&node->prio_list, &iter->prio_list);
 102 ins_node:
 103         list_add_tail(&node->node_list, node_next);
 104
 105         plist_check_head(head);
 106 }
 107
 108 /**
 109  * plist_del - Remove a @node from plist.
 110  *
 111  * @node:       &struct plist_node pointer - entry to be removed
 112  * @head:       &struct plist_head pointer - list head
 113  */
 114 void plist_del(struct plist_node *node, struct plist_head *head)
 115 {
 116         plist_check_head(head);
 117
 118         if (!list_empty(&node->prio_list)) {
 119                 if (node->node_list.next != &head->node_list) {
 120                         struct plist_node *next;
 121
 122                         next = list_entry(node->node_list.next,
 123                                         struct plist_node, node_list);
 124
 125                         /* add the next plist_node into prio_list */
 126                         if (list_empty(&next->prio_list))
 127                                 list_add(&next->prio_list, &node->prio_list);
 128                 }
 129                 list_del_init(&node->prio_list);
 130         }
 131
 132         list_del_init(&node->node_list);
 133
 134         plist_check_head(head);
 135 }
 136
 137 #ifdef CONFIG_DEBUG_PI_LIST
 138 #include <linux/sched.h>
 139 #include <linux/module.h>
 140 #include <linux/init.h>
 141
 142 static struct plist_node __initdata test_node[241];
 143
 144 static void __init plist_test_check(int nr_expect)
 145 {
 146         struct plist_node *first, *prio_pos, *node_pos;
 147
 148         if (plist_head_empty(&test_head)) {
 149                 BUG_ON(nr_expect != 0);
 150                 return;
 151         }
 152
 153         prio_pos = first = plist_first(&test_head);
 154         plist_for_each(node_pos, &test_head) {
 155                 if (nr_expect-- < 0)
 156                         break;
 157                 if (node_pos == first)
 158                         continue;
 159                 if (node_pos->prio == prio_pos->prio) {
 160                         BUG_ON(!list_empty(&node_pos->prio_list));
 161                         continue;
 162                 }
 163
 164                 BUG_ON(prio_pos->prio > node_pos->prio);
 165                 BUG_ON(prio_pos->prio_list.next != &node_pos->prio_list);
 166                 prio_pos = node_pos;
 167         }
 168
 169         BUG_ON(nr_expect != 0);
 170         BUG_ON(prio_pos->prio_list.next != &first->prio_list);
 171 }
 172
 173 static int  __init plist_test(void)
 174 {
 175         int nr_expect = 0, i, loop;
 176         unsigned int r = local_clock();
 177
 178         pr_debug("start plist test\n");
 179         plist_head_init(&test_head);
 180         for (i = 0; i < ARRAY_SIZE(test_node); i++)
 181                 plist_node_init(test_node + i, 0);
 182
 183         for (loop = 0; loop < 1000; loop++) {
 184                 r = r * 193939 % 47629;
 185                 i = r % ARRAY_SIZE(test_node);
 186                 if (plist_node_empty(test_node + i)) {
 187                         r = r * 193939 % 47629;
 188                         test_node[i].prio = r % 99;
 189                         plist_add(test_node + i, &test_head);
 190                         nr_expect++;
 191                 } else {
 192                         plist_del(test_node + i, &test_head);
 193                         nr_expect--;
 194                 }
 195                 plist_test_check(nr_expect);
 196         }
 197
 198         for (i = 0; i < ARRAY_SIZE(test_node); i++) {
 199                 if (plist_node_empty(test_node + i))
 200                         continue;
 201                 plist_del(test_node + i, &test_head);
 202                 nr_expect--;
 203                 plist_test_check(nr_expect);
 204         }
 205
 206         pr_debug("end plist test\n");
 207         return 0;
 208 }
 209
 210 module_init(plist_test);
 211
 212 #endif