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 /**
 138  * plist_requeue - Requeue @node at end of same-prio entries.
 139  *
 140  * This is essentially an optimized plist_del() followed by
 141  * plist_add().  It moves an entry already in the plist to
 142  * after any other same-priority entries.
 143  *
 144  * @node:       &struct plist_node pointer - entry to be moved
 145  * @head:       &struct plist_head pointer - list head
 146  */
 147 void plist_requeue(struct plist_node *node, struct plist_head *head)
 148 {
 149         struct plist_node *iter;
 150         struct list_head *node_next = &head->node_list;
 151
 152         plist_check_head(head);
 153         BUG_ON(plist_head_empty(head));
 154         BUG_ON(plist_node_empty(node));
 155
 156         if (node == plist_last(head))
 157                 return;
 158
 159         iter = plist_next(node);
 160
 161         if (node->prio != iter->prio)
 162                 return;
 163
 164         plist_del(node, head);
 165
 166         plist_for_each_continue(iter, head) {
 167                 if (node->prio != iter->prio) {
 168                         node_next = &iter->node_list;
 169                         break;
 170                 }
 171         }
 172         list_add_tail(&node->node_list, node_next);
 173
 174         plist_check_head(head);
 175 }
 176
 177 #ifdef CONFIG_DEBUG_PI_LIST
 178 #include <linux/sched.h>
 179 #include <linux/module.h>
 180 #include <linux/init.h>
 181
 182 static struct plist_node __initdata test_node[241];
 183
 184 static void __init plist_test_check(int nr_expect)
 185 {
 186         struct plist_node *first, *prio_pos, *node_pos;
 187
 188         if (plist_head_empty(&test_head)) {
 189                 BUG_ON(nr_expect != 0);
 190                 return;
 191         }
 192
 193         prio_pos = first = plist_first(&test_head);
 194         plist_for_each(node_pos, &test_head) {
 195                 if (nr_expect-- < 0)
 196                         break;
 197                 if (node_pos == first)
 198                         continue;
 199                 if (node_pos->prio == prio_pos->prio) {
 200                         BUG_ON(!list_empty(&node_pos->prio_list));
 201                         continue;
 202                 }
 203
 204                 BUG_ON(prio_pos->prio > node_pos->prio);
 205                 BUG_ON(prio_pos->prio_list.next != &node_pos->prio_list);
 206                 prio_pos = node_pos;
 207         }
 208
 209         BUG_ON(nr_expect != 0);
 210         BUG_ON(prio_pos->prio_list.next != &first->prio_list);
 211 }
 212
 213 static void __init plist_test_requeue(struct plist_node *node)
 214 {
 215         plist_requeue(node, &test_head);
 216
 217         if (node != plist_last(&test_head))
 218                 BUG_ON(node->prio == plist_next(node)->prio);
 219 }
 220
 221 static int  __init plist_test(void)
 222 {
 223         int nr_expect = 0, i, loop;
 224         unsigned int r = local_clock();
 225
 226         printk(KERN_DEBUG "start plist test\n");
 227         plist_head_init(&test_head);
 228         for (i = 0; i < ARRAY_SIZE(test_node); i++)
 229                 plist_node_init(test_node + i, 0);
 230
 231         for (loop = 0; loop < 1000; loop++) {
 232                 r = r * 193939 % 47629;
 233                 i = r % ARRAY_SIZE(test_node);
 234                 if (plist_node_empty(test_node + i)) {
 235                         r = r * 193939 % 47629;
 236                         test_node[i].prio = r % 99;
 237                         plist_add(test_node + i, &test_head);
 238                         nr_expect++;
 239                 } else {
 240                         plist_del(test_node + i, &test_head);
 241                         nr_expect--;
 242                 }
 243                 plist_test_check(nr_expect);
 244                 if (!plist_node_empty(test_node + i)) {
 245                         plist_test_requeue(test_node + i);
 246                         plist_test_check(nr_expect);
 247                 }
 248         }
 249
 250         for (i = 0; i < ARRAY_SIZE(test_node); i++) {
 251                 if (plist_node_empty(test_node + i))
 252                         continue;
 253                 plist_del(test_node + i, &test_head);
 254                 nr_expect--;
 255                 plist_test_check(nr_expect);
 256         }
 257
 258         printk(KERN_DEBUG "end plist test\n");
 259         return 0;
 260 }
 261
 262 module_init(plist_test);
 263
 264 #endif