| 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 | #endif
|
|---|
