include/vlc_list.h

   1 /******************************************************************************
   2  * vlc_list.h
   3  ******************************************************************************
   4  * Copyright © 2018 Rémi Denis-Courmont
   5  *
   6  * This program is free software; you can redistribute it and/or modify it
   7  * under the terms of the GNU Lesser General Public License as published by
   8  * the Free Software Foundation; either version 2.1 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  14  * GNU Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public License
  17  * along with this program; if not, write to the Free Software Foundation,
  18  * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
  19  *****************************************************************************/
  20
  21 #ifndef VLC_LIST_H
  22 # define VLC_LIST_H 1
  23
  24 # include <stdalign.h>
  25 # include <stdbool.h>
  26
  27 /**
  28  * \defgroup list Linked lists
  29  * \ingroup cext
  30  * @{
  31  * \file
  32  * This provides convenience helpers for linked lists.
  33  */
  34
  35 /**
  36  * Doubly-linked list node.
  37  *
  38  * This data structure provides a doubly-linked list node.
  39  * It must be embedded in each member of a list as a node proper.
  40  * It also serves as a list head in the object containing the list.
  41  */
  42 struct vlc_list
  43 {
  44     struct vlc_list *prev;
  45     struct vlc_list *next;
  46 };
  47
  48 /**
  49  * Static initializer for a list head.
  50  */
  51 #define VLC_LIST_INITIALIZER(h) { h, h }
  52
  53 /**
  54  * Initializes an empty list head.
  55  */
  56 static inline void vlc_list_init(struct vlc_list *restrict head)
  57 {
  58     head->prev = head;
  59     head->next = head;
  60 }
  61
  62 /**
  63  * Inserts an element in a list.
  64  *
  65  * \param node Node pointer of the element to insert [OUT].
  66  * \param prev Node pointer of the previous element.
  67  * \param next Node pointer of the next element.
  68  */
  69 static inline void vlc_list_add_between(struct vlc_list *restrict node,
  70                                         struct vlc_list *prev,
  71                                         struct vlc_list *next)
  72 {
  73     node->prev = prev;
  74     node->next = next;
  75     prev->next = node;
  76     next->prev = node;
  77 }
  78
  79 /**
  80  * Inserts an element after another.
  81  *
  82  * \param node Node pointer of the element to insert [OUT].
  83  * \param prev Node pointer of the previous element.
  84  */
  85 static inline void vlc_list_add_after(struct vlc_list *restrict node,
  86                                       struct vlc_list *prev)
  87 {
  88     vlc_list_add_between(node, prev, prev->next);
  89 }
  90
  91 /**
  92  * Inserts an element before another.
  93  *
  94  * \param node Node pointer of the element to insert [OUT].
  95  * \param prev Node pointer of the next element.
  96  */
  97 static inline void vlc_list_add_before(struct vlc_list *restrict node,
  98                                        struct vlc_list *next)
  99 {
 100     vlc_list_add_between(node, next->prev, next);
 101 }
 102
 103 /**
 104  * Appends an element into a list.
 105  *
 106  * \param node Node pointer of the element to append to the list [OUT].
 107  * \param head Head pointer of the list to append the element to.
 108  */
 109 static inline void vlc_list_append(struct vlc_list *restrict node,
 110                                    struct vlc_list *head)
 111 {
 112     vlc_list_add_before(node, head);
 113 }
 114
 115 /**
 116  * Prepends an element into a list.
 117  *
 118  * \param node Node pointer of the element to prepend to the list [OUT].
 119  * \param head Head pointer of the list to prepend the element to.
 120  */
 121 static inline void vlc_list_prepend(struct vlc_list *restrict node,
 122                                     struct vlc_list *head)
 123 {
 124     vlc_list_add_after(node, head);
 125 }
 126
 127 /**
 128  * Removes an element from a list.
 129  *
 130  * \param node Node of the element to remove from a list.
 131  * \warning The element must be inside a list.
 132  * Otherwise the behaviour is undefined.
 133  */
 134 static inline void vlc_list_remove(struct vlc_list *restrict node)
 135 {
 136     struct vlc_list *prev = node->prev;
 137     struct vlc_list *next = node->next;
 138
 139     prev->next = next;
 140     next->prev = prev;
 141 }
 142
 143 /**
 144  * Replaces an element with another one.
 145  *
 146  * \param origin Node pointer of the element to remove from the list [IN].
 147  * \param substitute Node pointer of the replacement [OUT].
 148  */
 149 static inline void vlc_list_replace(const struct vlc_list *original,
 150                                     struct vlc_list *restrict substitute)
 151 {
 152     vlc_list_add_between(substitute, original->prev, original->next);
 153 }
 154
 155 /**
 156  * Checks if a list is empty.
 157  *
 158  * \param head Head of the list to be checked [IN].
 159  *
 160  * \retval false The list is not empty.
 161  * \retval true The list is empty.
 162  *
 163  * \note Obviously the list must have been initialized.
 164  * Otherwise, the behaviour is undefined.
 165  */
 166 static inline bool vlc_list_is_empty(const struct vlc_list *head)
 167 {
 168     return head->next == head;
 169 }
 170
 171 /**
 172  * Checks if an element is first in a list.
 173  *
 174  * \param node List node of the element [IN].
 175  * \param head Head of the list to be checked [IN].
 176  *
 177  * \retval false The element is not first (or is in another list).
 178  * \retval true The element is first.
 179  */
 180 static inline bool vlc_list_is_first(const struct vlc_list *node,
 181                                      const struct vlc_list *head)
 182 {
 183     return node->prev == head;
 184 }
 185
 186 /**
 187  * Checks if an element is last in a list.
 188  *
 189  * \param node List node of the element [IN].
 190  * \param head Head of the list to be checked [IN].
 191  *
 192  * \retval false The element is not last (or is in another list).
 193  * \retval true The element is last.
 194  */
 195 static inline bool vlc_list_is_last(const struct vlc_list *node,
 196                                     const struct vlc_list *head)
 197 {
 198     return node->next == head;
 199 }
 200
 201 /**
 202  * List iterator.
 203  */
 204 struct vlc_list_it
 205 {
 206     const struct vlc_list *head;
 207     struct vlc_list *current;
 208     struct vlc_list *next;
 209 };
 210
 211 static inline
 212 struct vlc_list_it vlc_list_it_start(const struct vlc_list *head)
 213 {
 214     struct vlc_list *first = head->next;
 215
 216     return (struct vlc_list_it){ head, first, first->next };
 217 }
 218
 219 static inline bool vlc_list_it_continue(const struct vlc_list_it *restrict it)
 220 {
 221     return it->current != it->head;
 222 }
 223
 224 static inline void vlc_list_it_next(struct vlc_list_it *restrict it)
 225 {
 226     struct vlc_list *next = it->next;
 227
 228     it->current = next;
 229     it->next = next->next;
 230 }
 231
 232 #define vlc_list_entry_aligned_size(p) \
 233     ((sizeof (*(p)) + sizeof (max_align_t) - 1) / sizeof (max_align_t))
 234
 235 #define vlc_list_entry_dummy(p) \
 236     (0 ? (p) : ((void *)(&(max_align_t[vlc_list_entry_aligned_size(p)]){})))
 237
 238 #define vlc_list_offset_p(p, member) \
 239     ((p) = vlc_list_entry_dummy(p), (char *)(&(p)->member) - (char *)(p))
 240
 241 #define vlc_list_entry_p(node, p, member) \
 242     (0 ? (p) : (void *)(((char *)(node)) - vlc_list_offset_p(p, member)))
 243
 244 /**
 245  * List iteration macro.
 246  *
 247  * This macro iterates over all elements (excluding the head) of a list,
 248  * in order from the first to the last.
 249  *
 250  * For each iteration, it sets the cursor variable to the current element.
 251  *
 252  * \param pos Cursor pointer variable identifier.
 253  * \param head Head pointer of the list to iterate [IN].
 254  * \param member Identifier of the member of the data type
 255  *               serving as list node.
 256  * \note It it safe to delete the current item while iterating.
 257  * It is however <b>not</b> safe to delete another item.
 258  */
 259 #define vlc_list_foreach(pos, head, member) \
 260     for (struct vlc_list_it vlc_list_it_##pos = vlc_list_it_start(head); \
 261          vlc_list_it_continue(&(vlc_list_it_##pos)) \
 262           && ((pos) = vlc_list_entry_p((vlc_list_it_##pos).current, \
 263                                        pos, member), true); \
 264          vlc_list_it_next(&(vlc_list_it_##pos)))
 265
 266 /**
 267  * Converts a list node pointer to an element pointer.
 268  *
 269  * \param ptr list node pointer
 270  * \param type list data element type name
 271  * \param member list node member within the data element compound type
 272  */
 273 #define vlc_list_entry(ptr, type, member) container_of(ptr, type, member)
 274
 275 static inline void *vlc_list_first_or_null(const struct vlc_list *head,
 276                                            size_t offset)
 277 {
 278     if (vlc_list_is_empty(head))
 279         return NULL;
 280     return ((char *)(head->next)) - offset;
 281 }
 282
 283 static inline void *vlc_list_last_or_null(const struct vlc_list *head,
 284                                           size_t offset)
 285 {
 286     if (vlc_list_is_empty(head))
 287         return NULL;
 288     return ((char *)(head->prev)) - offset;
 289 }
 290
 291 static inline void *vlc_list_prev_or_null(const struct vlc_list *head,
 292                                           struct vlc_list *node,
 293                                           size_t offset)
 294 {
 295     if (vlc_list_is_first(node, head))
 296         return NULL;
 297     return ((char *)(node->prev)) - offset;
 298 }
 299
 300 static inline void *vlc_list_next_or_null(const struct vlc_list *head,
 301                                           struct vlc_list *node,
 302                                           size_t offset)
 303 {
 304     if (vlc_list_is_last(node, head))
 305         return NULL;
 306     return ((char *)(node->next)) - offset;
 307 }
 308
 309 /**
 310  * Gets the first element.
 311  *
 312  * \param head Head of list whose last element to get [IN].
 313  *
 314  * \return the first entry in a list or NULL if empty.
 315  */
 316 #define vlc_list_first_entry_or_null(head, type, member) \
 317         ((type *)vlc_list_first_or_null(head, offsetof (type, member)))
 318
 319 /**
 320  * Gets the last element.
 321  *
 322  * \param head Head of list whose last element to get [IN].
 323  *
 324  * \return the last entry in a list or NULL if empty.
 325  */
 326 #define vlc_list_last_entry_or_null(head, type, member) \
 327         ((type *)vlc_list_last_or_null(head, offsetof (type, member)))
 328
 329 #define vlc_list_prev_entry_or_null(head, entry, type, member) \
 330         ((type *)vlc_list_prev_or_null(head, &(entry)->member, \
 331                                        offsetof (type, member)))
 332 #define vlc_list_next_entry_or_null(head, entry, type, member) \
 333         ((type *)vlc_list_next_or_null(head, &(entry)->member, \
 334                                        offsetof (type, member)))
 335
 336 /** \todo Merging lists, splitting lists. */
 337
 338 /** @} */
 339
 340 #endif /* VLC_LIST_H */