~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/include/linux/plist.h

Version: ~ [ linux-5.2-rc1 ] ~ [ linux-5.1.2 ] ~ [ linux-5.0.16 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.43 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.119 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.176 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.179 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.139 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.67 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.39.4 ] ~ [ linux-2.6.38.8 ] ~ [ linux-2.6.37.6 ] ~ [ linux-2.6.36.4 ] ~ [ linux-2.6.35.14 ] ~ [ linux-2.6.34.15 ] ~ [ linux-2.6.33.20 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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_HEAD - declare and init plist_head
102  * @head:       name for struct plist_head variable
103  */
104 #define PLIST_HEAD(head) \
105         struct plist_head head = PLIST_HEAD_INIT(head)
106 
107 /**
108  * PLIST_NODE_INIT - static struct plist_node initializer
109  * @node:       struct plist_node variable name
110  * @__prio:     initial node priority
111  */
112 #define PLIST_NODE_INIT(node, __prio)                   \
113 {                                                       \
114         .prio  = (__prio),                              \
115         .prio_list = LIST_HEAD_INIT((node).prio_list),  \
116         .node_list = LIST_HEAD_INIT((node).node_list),  \
117 }
118 
119 /**
120  * plist_head_init - dynamic struct plist_head initializer
121  * @head:       &struct plist_head pointer
122  */
123 static inline void
124 plist_head_init(struct plist_head *head)
125 {
126         INIT_LIST_HEAD(&head->node_list);
127 }
128 
129 /**
130  * plist_node_init - Dynamic struct plist_node initializer
131  * @node:       &struct plist_node pointer
132  * @prio:       initial node priority
133  */
134 static inline void plist_node_init(struct plist_node *node, int prio)
135 {
136         node->prio = prio;
137         INIT_LIST_HEAD(&node->prio_list);
138         INIT_LIST_HEAD(&node->node_list);
139 }
140 
141 extern void plist_add(struct plist_node *node, struct plist_head *head);
142 extern void plist_del(struct plist_node *node, struct plist_head *head);
143 
144 extern void plist_requeue(struct plist_node *node, struct plist_head *head);
145 
146 /**
147  * plist_for_each - iterate over the plist
148  * @pos:        the type * to use as a loop counter
149  * @head:       the head for your list
150  */
151 #define plist_for_each(pos, head)       \
152          list_for_each_entry(pos, &(head)->node_list, node_list)
153 
154 /**
155  * plist_for_each_continue - continue iteration over the plist
156  * @pos:        the type * to use as a loop cursor
157  * @head:       the head for your list
158  *
159  * Continue to iterate over plist, continuing after the current position.
160  */
161 #define plist_for_each_continue(pos, head)      \
162          list_for_each_entry_continue(pos, &(head)->node_list, node_list)
163 
164 /**
165  * plist_for_each_safe - iterate safely over a plist of given type
166  * @pos:        the type * to use as a loop counter
167  * @n:  another type * to use as temporary storage
168  * @head:       the head for your list
169  *
170  * Iterate over a plist of given type, safe against removal of list entry.
171  */
172 #define plist_for_each_safe(pos, n, head)       \
173          list_for_each_entry_safe(pos, n, &(head)->node_list, node_list)
174 
175 /**
176  * plist_for_each_entry - iterate over list of given type
177  * @pos:        the type * to use as a loop counter
178  * @head:       the head for your list
179  * @mem:        the name of the list_head within the struct
180  */
181 #define plist_for_each_entry(pos, head, mem)    \
182          list_for_each_entry(pos, &(head)->node_list, mem.node_list)
183 
184 /**
185  * plist_for_each_entry_continue - continue iteration over list of given type
186  * @pos:        the type * to use as a loop cursor
187  * @head:       the head for your list
188  * @m:          the name of the list_head within the struct
189  *
190  * Continue to iterate over list of given type, continuing after
191  * the current position.
192  */
193 #define plist_for_each_entry_continue(pos, head, m)     \
194         list_for_each_entry_continue(pos, &(head)->node_list, m.node_list)
195 
196 /**
197  * plist_for_each_entry_safe - iterate safely over list of given type
198  * @pos:        the type * to use as a loop counter
199  * @n:          another type * to use as temporary storage
200  * @head:       the head for your list
201  * @m:          the name of the list_head within the struct
202  *
203  * Iterate over list of given type, safe against removal of list entry.
204  */
205 #define plist_for_each_entry_safe(pos, n, head, m)      \
206         list_for_each_entry_safe(pos, n, &(head)->node_list, m.node_list)
207 
208 /**
209  * plist_head_empty - return !0 if a plist_head is empty
210  * @head:       &struct plist_head pointer
211  */
212 static inline int plist_head_empty(const struct plist_head *head)
213 {
214         return list_empty(&head->node_list);
215 }
216 
217 /**
218  * plist_node_empty - return !0 if plist_node is not on a list
219  * @node:       &struct plist_node pointer
220  */
221 static inline int plist_node_empty(const struct plist_node *node)
222 {
223         return list_empty(&node->node_list);
224 }
225 
226 /* All functions below assume the plist_head is not empty. */
227 
228 /**
229  * plist_first_entry - get the struct for the first entry
230  * @head:       the &struct plist_head pointer
231  * @type:       the type of the struct this is embedded in
232  * @member:     the name of the list_head within the struct
233  */
234 #ifdef CONFIG_DEBUG_PI_LIST
235 # define plist_first_entry(head, type, member)  \
236 ({ \
237         WARN_ON(plist_head_empty(head)); \
238         container_of(plist_first(head), type, member); \
239 })
240 #else
241 # define plist_first_entry(head, type, member)  \
242         container_of(plist_first(head), type, member)
243 #endif
244 
245 /**
246  * plist_last_entry - get the struct for the last entry
247  * @head:       the &struct plist_head pointer
248  * @type:       the type of the struct this is embedded in
249  * @member:     the name of the list_head within the struct
250  */
251 #ifdef CONFIG_DEBUG_PI_LIST
252 # define plist_last_entry(head, type, member)   \
253 ({ \
254         WARN_ON(plist_head_empty(head)); \
255         container_of(plist_last(head), type, member); \
256 })
257 #else
258 # define plist_last_entry(head, type, member)   \
259         container_of(plist_last(head), type, member)
260 #endif
261 
262 /**
263  * plist_next - get the next entry in list
264  * @pos:        the type * to cursor
265  */
266 #define plist_next(pos) \
267         list_next_entry(pos, node_list)
268 
269 /**
270  * plist_prev - get the prev entry in list
271  * @pos:        the type * to cursor
272  */
273 #define plist_prev(pos) \
274         list_prev_entry(pos, node_list)
275 
276 /**
277  * plist_first - return the first node (and thus, highest priority)
278  * @head:       the &struct plist_head pointer
279  *
280  * Assumes the plist is _not_ empty.
281  */
282 static inline struct plist_node *plist_first(const struct plist_head *head)
283 {
284         return list_entry(head->node_list.next,
285                           struct plist_node, node_list);
286 }
287 
288 /**
289  * plist_last - return the last node (and thus, lowest priority)
290  * @head:       the &struct plist_head pointer
291  *
292  * Assumes the plist is _not_ empty.
293  */
294 static inline struct plist_node *plist_last(const struct plist_head *head)
295 {
296         return list_entry(head->node_list.prev,
297                           struct plist_node, node_list);
298 }
299 
300 #endif
301 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp