plist.c 2.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118
  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. #include <linux/plist.h>
  26. #include <linux/spinlock.h>
  27. #ifdef CONFIG_DEBUG_PI_LIST
  28. static void plist_check_prev_next(struct list_head *t, struct list_head *p,
  29. struct list_head *n)
  30. {
  31. if (n->prev != p || p->next != n) {
  32. printk("top: %p, n: %p, p: %p\n", t, t->next, t->prev);
  33. printk("prev: %p, n: %p, p: %p\n", p, p->next, p->prev);
  34. printk("next: %p, n: %p, p: %p\n", n, n->next, n->prev);
  35. WARN_ON(1);
  36. }
  37. }
  38. static void plist_check_list(struct list_head *top)
  39. {
  40. struct list_head *prev = top, *next = top->next;
  41. plist_check_prev_next(top, prev, next);
  42. while (next != top) {
  43. prev = next;
  44. next = prev->next;
  45. plist_check_prev_next(top, prev, next);
  46. }
  47. }
  48. static void plist_check_head(struct plist_head *head)
  49. {
  50. WARN_ON(!head->lock);
  51. if (head->lock)
  52. WARN_ON_SMP(!spin_is_locked(head->lock));
  53. plist_check_list(&head->prio_list);
  54. plist_check_list(&head->node_list);
  55. }
  56. #else
  57. # define plist_check_head(h) do { } while (0)
  58. #endif
  59. /**
  60. * plist_add - add @node to @head
  61. *
  62. * @node: &struct plist_node pointer
  63. * @head: &struct plist_head pointer
  64. */
  65. void plist_add(struct plist_node *node, struct plist_head *head)
  66. {
  67. struct plist_node *iter;
  68. plist_check_head(head);
  69. WARN_ON(!plist_node_empty(node));
  70. list_for_each_entry(iter, &head->prio_list, plist.prio_list) {
  71. if (node->prio < iter->prio)
  72. goto lt_prio;
  73. else if (node->prio == iter->prio) {
  74. iter = list_entry(iter->plist.prio_list.next,
  75. struct plist_node, plist.prio_list);
  76. goto eq_prio;
  77. }
  78. }
  79. lt_prio:
  80. list_add_tail(&node->plist.prio_list, &iter->plist.prio_list);
  81. eq_prio:
  82. list_add_tail(&node->plist.node_list, &iter->plist.node_list);
  83. plist_check_head(head);
  84. }
  85. /**
  86. * plist_del - Remove a @node from plist.
  87. *
  88. * @node: &struct plist_node pointer - entry to be removed
  89. * @head: &struct plist_head pointer - list head
  90. */
  91. void plist_del(struct plist_node *node, struct plist_head *head)
  92. {
  93. plist_check_head(head);
  94. if (!list_empty(&node->plist.prio_list)) {
  95. struct plist_node *next = plist_first(&node->plist);
  96. list_move_tail(&next->plist.prio_list, &node->plist.prio_list);
  97. list_del_init(&node->plist.prio_list);
  98. }
  99. list_del_init(&node->plist.node_list);
  100. plist_check_head(head);
  101. }