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: