File: /Users/paulross/dev/linux/linux-3.13/include/linux/plist.h

Green shading in the line number column means the source is part of the translation unit, red means it is conditionally excluded. Highlighted line numbers link to the translation unit page. Highlighted macros link to the macro page.

       1: /*
       2:  * Descending-priority-sorted double-linked list
       3:  *
       4:  * (C) 2002-2003 Intel Corp
       5:  * Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>.
       6:  *
       7:  * 2001-2005 (c) MontaVista Software, Inc.
       8:  * Daniel Walker <dwalker@mvista.com>
       9:  *
      10:  * (C) 2005 Thomas Gleixner <tglx@linutronix.de>
      11:  *
      12:  * Simplifications of the original code by
      13:  * Oleg Nesterov <oleg@tv-sign.ru>
      14:  *
      15:  * Licensed under the FSF's GNU Public License v2 or later.
      16:  *
      17:  * Based on simple lists (include/linux/list.h).
      18:  *
      19:  * This is a priority-sorted list of nodes; each node has a
      20:  * priority from INT_MIN (highest) to INT_MAX (lowest).
      21:  *
      22:  * Addition is O(K), removal is O(1), change of priority of a node is
      23:  * O(K) and K is the number of RT priority levels used in the system.
      24:  * (1 <= K <= 99)
      25:  *
      26:  * This list is really a list of lists:
      27:  *
      28:  *  - The tier 1 list is the prio_list, different priority nodes.
      29:  *
      30:  *  - The tier 2 list is the node_list, serialized nodes.
      31:  *
      32:  * Simple ASCII art explanation:
      33:  *
      34:  * pl:prio_list (only for plist_node)
      35:  * nl:node_list
      36:  *   HEAD|             NODE(S)
      37:  *       |
      38:  *       ||------------------------------------|
      39:  *       ||->|pl|<->|pl|<--------------->|pl|<-|
      40:  *       |   |10|   |21|   |21|   |21|   |40|   (prio)
      41:  *       |   |  |   |  |   |  |   |  |   |  |
      42:  *       |   |  |   |  |   |  |   |  |   |  |
      43:  * |->|nl|<->|nl|<->|nl|<->|nl|<->|nl|<->|nl|<-|
      44:  * |-------------------------------------------|
      45:  *
      46:  * The nodes on the prio_list list are sorted by priority to simplify
      47:  * the insertion of new nodes. There are no nodes with duplicate
      48:  * priorites on the list.
      49:  *
      50:  * The nodes on the node_list are ordered by priority and can contain
      51:  * entries which have the same priority. Those entries are ordered
      52:  * FIFO
      53:  *
      54:  * Addition means: look for the prio_list node in the prio_list
      55:  * for the priority of the node and insert it before the node_list
      56:  * entry of the next prio_list node. If it is the first node of
      57:  * that priority, add it to the prio_list in the right position and
      58:  * insert it into the serialized node_list list
      59:  *
      60:  * Removal means remove it from the node_list and remove it from
      61:  * the prio_list if the node_list list_head is non empty. In case
      62:  * of removal from the prio_list it must be checked whether other
      63:  * entries of the same priority are on the list or not. If there
      64:  * is another entry of the same priority then this entry has to
      65:  * replace the removed entry on the prio_list. If the entry which
      66:  * is removed is the only entry of this priority then a simple
      67:  * remove from both list is sufficient.
      68:  *
      69:  * INT_MIN is the highest priority, 0 is the medium highest, INT_MAX
      70:  * is lowest priority.
      71:  *
      72:  * No locking is done, up to the caller.
      73:  *
      74:  */
      75: #ifndef _LINUX_PLIST_H_
      76: #define _LINUX_PLIST_H_
      77: 
      78: #include <linux/kernel.h>
      79: #include <linux/list.h>
      80: 
      81: struct plist_head {
      82:     struct list_head node_list;
      83: };
      84: 
      85: struct plist_node {
      86:     int            prio;
      87:     struct list_head    prio_list;
      88:     struct list_head    node_list;
      89: };
      90: 
      91: /**
      92:  * PLIST_HEAD_INIT - static struct plist_head initializer
      93:  * @head:    struct plist_head variable name
      94:  */
      95: #define PLIST_HEAD_INIT(head)                \
      96: {                            \
      97:     .node_list = LIST_HEAD_INIT((head).node_list)    \
      98: }
      99: 
     100: /**
     101:  * PLIST_NODE_INIT - static struct plist_node initializer
     102:  * @node:    struct plist_node variable name
     103:  * @__prio:    initial node priority
     104:  */
     105: #define PLIST_NODE_INIT(node, __prio)            \
     106: {                            \
     107:     .prio  = (__prio),                \
     108:     .prio_list = LIST_HEAD_INIT((node).prio_list),    \
     109:     .node_list = LIST_HEAD_INIT((node).node_list),    \
     110: }
     111: 
     112: /**
     113:  * plist_head_init - dynamic struct plist_head initializer
     114:  * @head:    &struct plist_head pointer
     115:  */
     116: static inline void
     117: plist_head_init(struct plist_head *head)
     118: {
     119:     INIT_LIST_HEAD(&head->node_list);
     120: }
     121: 
     122: /**
     123:  * plist_node_init - Dynamic struct plist_node initializer
     124:  * @node:    &struct plist_node pointer
     125:  * @prio:    initial node priority
     126:  */
     127: static inline void plist_node_init(struct plist_node *node, int prio)
     128: {
     129:     node->prio = prio;
     130:     INIT_LIST_HEAD(&node->prio_list);
     131:     INIT_LIST_HEAD(&node->node_list);
     132: }
     133: 
     134: extern void plist_add(struct plist_node *node, struct plist_head *head);
     135: extern void plist_del(struct plist_node *node, struct plist_head *head);
     136: 
     137: /**
     138:  * plist_for_each - iterate over the plist
     139:  * @pos:    the type * to use as a loop counter
     140:  * @head:    the head for your list
     141:  */
     142: #define plist_for_each(pos, head)    \
     143:      list_for_each_entry(pos, &(head)->node_list, node_list)
     144: 
     145: /**
     146:  * plist_for_each_safe - iterate safely over a plist of given type
     147:  * @pos:    the type * to use as a loop counter
     148:  * @n:    another type * to use as temporary storage
     149:  * @head:    the head for your list
     150:  *
     151:  * Iterate over a plist of given type, safe against removal of list entry.
     152:  */
     153: #define plist_for_each_safe(pos, n, head)    \
     154:      list_for_each_entry_safe(pos, n, &(head)->node_list, node_list)
     155: 
     156: /**
     157:  * plist_for_each_entry    - iterate over list of given type
     158:  * @pos:    the type * to use as a loop counter
     159:  * @head:    the head for your list
     160:  * @mem:    the name of the list_struct within the struct
     161:  */
     162: #define plist_for_each_entry(pos, head, mem)    \
     163:      list_for_each_entry(pos, &(head)->node_list, mem.node_list)
     164: 
     165: /**
     166:  * plist_for_each_entry_safe - iterate safely over list of given type
     167:  * @pos:    the type * to use as a loop counter
     168:  * @n:        another type * to use as temporary storage
     169:  * @head:    the head for your list
     170:  * @m:        the name of the list_struct within the struct
     171:  *
     172:  * Iterate over list of given type, safe against removal of list entry.
     173:  */
     174: #define plist_for_each_entry_safe(pos, n, head, m)    \
     175:     list_for_each_entry_safe(pos, n, &(head)->node_list, m.node_list)
     176: 
     177: /**
     178:  * plist_head_empty - return !0 if a plist_head is empty
     179:  * @head:    &struct plist_head pointer
     180:  */
     181: static inline int plist_head_empty(const struct plist_head *head)
     182: {
     183:     return list_empty(&head->node_list);
     184: }
     185: 
     186: /**
     187:  * plist_node_empty - return !0 if plist_node is not on a list
     188:  * @node:    &struct plist_node pointer
     189:  */
     190: static inline int plist_node_empty(const struct plist_node *node)
     191: {
     192:     return list_empty(&node->node_list);
     193: }
     194: 
     195: /* All functions below assume the plist_head is not empty. */
     196: 
     197: /**
     198:  * plist_first_entry - get the struct for the first entry
     199:  * @head:    the &struct plist_head pointer
     200:  * @type:    the type of the struct this is embedded in
     201:  * @member:    the name of the list_struct within the struct
     202:  */
     203: #ifdef CONFIG_DEBUG_PI_LIST
     204: # define plist_first_entry(head, type, member)    \
     205: ({ \
     206:     WARN_ON(plist_head_empty(head)); \
     207:     container_of(plist_first(head), type, member); \
     208: })
     209: #else
     210: # define plist_first_entry(head, type, member)    \
     211:     container_of(plist_first(head), type, member)
     212: #endif
     213: 
     214: /**
     215:  * plist_last_entry - get the struct for the last entry
     216:  * @head:    the &struct plist_head pointer
     217:  * @type:    the type of the struct this is embedded in
     218:  * @member:    the name of the list_struct within the struct
     219:  */
     220: #ifdef CONFIG_DEBUG_PI_LIST
     221: # define plist_last_entry(head, type, member)    \
     222: ({ \
     223:     WARN_ON(plist_head_empty(head)); \
     224:     container_of(plist_last(head), type, member); \
     225: })
     226: #else
     227: # define plist_last_entry(head, type, member)    \
     228:     container_of(plist_last(head), type, member)
     229: #endif
     230: 
     231: /**
     232:  * plist_first - return the first node (and thus, highest priority)
     233:  * @head:    the &struct plist_head pointer
     234:  *
     235:  * Assumes the plist is _not_ empty.
     236:  */
     237: static inline struct plist_node *plist_first(const struct plist_head *head)
     238: {
     239:     return list_entry(head->node_list.next,
     240:               struct plist_node, node_list);
     241: }
     242: 
     243: /**
     244:  * plist_last - return the last node (and thus, lowest priority)
     245:  * @head:    the &struct plist_head pointer
     246:  *
     247:  * Assumes the plist is _not_ empty.
     248:  */
     249: static inline struct plist_node *plist_last(const struct plist_head *head)
     250: {
     251:     return list_entry(head->node_list.prev,
     252:               struct plist_node, node_list);
     253: }
     254: 
     255: #endif
     256: