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 next 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 original 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     struct vlc_list_it it = { head, first, first->next };
 217     return it;
 218 }
 219
 220 static inline bool vlc_list_it_continue(const struct vlc_list_it *restrict it)
 221 {
 222     return it->current != it->head;
 223 }
 224
 225 static inline void vlc_list_it_next(struct vlc_list_it *restrict it)
 226 {
 227     struct vlc_list *next = it->next;
 228
 229     it->current = next;
 230     it->next = next->next;
 231 }
 232
 233 #define vlc_list_entry_aligned_size(p) \
 234     ((sizeof (*(p)) + sizeof (max_align_t) - 1) / sizeof (max_align_t))
 235
 236 #define vlc_list_entry_dummy(p) \
 237     (0 ? (p) : ((void *)(&(max_align_t[vlc_list_entry_aligned_size(p)]){0})))
 238
 239 #define vlc_list_offset_p(p, member) \
 240     ((p) = vlc_list_entry_dummy(p), (char *)(&(p)->member) - (char *)(p))
 241
 242 #define vlc_list_entry_p(node, p, member) \
 243     (0 ? (p) : (void *)(((char *)(node)) - vlc_list_offset_p(p, member)))
 244
 245 /**
 246  * List iteration macro.
 247  *
 248  * This macro iterates over all elements (excluding the head) of a list,
 249  * in order from the first to the last.
 250  *
 251  * For each iteration, it sets the cursor variable to the current element.
 252  *
 253  * \param pos Cursor pointer variable identifier.
 254  * \param head Head pointer of the list to iterate [IN].
 255  * \param member Identifier of the member of the data type
 256  *               serving as list node.
 257  * \note It it safe to delete the current item while iterating.
 258  * It is however <b>not</b> safe to delete another item.
 259  */
 260 #define vlc_list_foreach(pos, head, member) \
 261     for (struct vlc_list_it vlc_list_it__##pos = vlc_list_it_start(head); \
 262          vlc_list_it_continue(&(vlc_list_it__##pos)) \
 263           && ((pos) = vlc_list_entry_p((vlc_list_it__##pos).current, \
 264                                        pos, member), true); \
 265          vlc_list_it_next(&(vlc_list_it__##pos)))
 266
 267 /**
 268  * Converts a list node pointer to an element pointer.
 269  *
 270  * \param ptr list node pointer
 271  * \param type list data element type name
 272  * \param member list node member within the data element compound type
 273  */
 274 #define vlc_list_entry(ptr, type, member) container_of(ptr, type, member)
 275
 276 static inline void *vlc_list_first_or_null(const struct vlc_list *head,
 277                                            size_t offset)
 278 {
 279     if (vlc_list_is_empty(head))
 280         return NULL;
 281     return ((char *)(head->next)) - offset;
 282 }
 283
 284 static inline void *vlc_list_last_or_null(const struct vlc_list *head,
 285                                           size_t offset)
 286 {
 287     if (vlc_list_is_empty(head))
 288         return NULL;
 289     return ((char *)(head->prev)) - offset;
 290 }
 291
 292 static inline void *vlc_list_prev_or_null(const struct vlc_list *head,
 293                                           struct vlc_list *node,
 294                                           size_t offset)
 295 {
 296     if (vlc_list_is_first(node, head))
 297         return NULL;
 298     return ((char *)(node->prev)) - offset;
 299 }
 300
 301 static inline void *vlc_list_next_or_null(const struct vlc_list *head,
 302                                           struct vlc_list *node,
 303                                           size_t offset)
 304 {
 305     if (vlc_list_is_last(node, head))
 306         return NULL;
 307     return ((char *)(node->next)) - offset;
 308 }
 309
 310 /**
 311  * Gets the first element.
 312  *
 313  * \param head Head of list whose last element to get [IN].
 314  *
 315  * \return the first entry in a list or NULL if empty.
 316  */
 317 #define vlc_list_first_entry_or_null(head, type, member) \
 318         ((type *)vlc_list_first_or_null(head, offsetof (type, member)))
 319
 320 /**
 321  * Gets the last element.
 322  *
 323  * \param head Head of list whose last element to get [IN].
 324  *
 325  * \return the last entry in a list or NULL if empty.
 326  */
 327 #define vlc_list_last_entry_or_null(head, type, member) \
 328         ((type *)vlc_list_last_or_null(head, offsetof (type, member)))
 329
 330 #define vlc_list_prev_entry_or_null(head, entry, type, member) \
 331         ((type *)vlc_list_prev_or_null(head, &(entry)->member, \
 332                                        offsetof (type, member)))
 333 #define vlc_list_next_entry_or_null(head, entry, type, member) \
 334         ((type *)vlc_list_next_or_null(head, &(entry)->member, \
 335                                        offsetof (type, member)))
 336
 337 /** \todo Merging lists, splitting lists. */
 338
 339 /** @} */
 340
 341 #endif /* VLC_LIST_H */