Branch data     Line data    Source code

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