src/helper/list.h

   1 /* SPDX-License-Identifier: BSD-2-Clause */
   2
   3 /*
   4  * Copyright (c) 2010 Isilon Systems, Inc.
   5  * Copyright (c) 2010 iX Systems, Inc.
   6  * Copyright (c) 2010 Panasas, Inc.
   7  * Copyright (c) 2013-2016 Mellanox Technologies, Ltd.
   8  * Copyright (c) 2021-2024 by Antonio Borneo <borneo.antonio@gmail.com>
   9  * All rights reserved.
  10  */
  11
  12 /*
  13  * Circular doubly linked list implementation.
  14  *
  15  * The content of this file is mainly copied/inspired from FreeBSD code in:
  16  * https://cgit.freebsd.org/src/tree/
  17  * files:
  18  * sys/compat/linuxkpi/common/include/linux/list.h
  19  * sys/compat/linuxkpi/common/include/linux/types.h
  20  *
  21  * Last aligned with release/13.3.0:
  22  *
  23  * - Skip 'hlist_*' double linked lists with a single pointer list head.
  24  * - Expand WRITE_ONCE().
  25  * - Use TAB for indentation.
  26  * - Put macro arguments within parenthesis.
  27  * - Remove blank lines after an open brace '{'.
  28  * - Remove multiple assignment.
  29  *
  30  * There is an example of using this file in contrib/list_example.c.
  31  */
  32
  33 #ifndef OPENOCD_HELPER_LIST_H
  34 #define OPENOCD_HELPER_LIST_H
  35
  36 /* begin OpenOCD changes */
  37
  38 #include <stddef.h>
  39
  40 struct list_head {
  41         struct list_head *next;
  42         struct list_head *prev;
  43 };
  44
  45 /* end OpenOCD changes */
  46
  47 #define LIST_HEAD_INIT(name) { &(name), &(name) }
  48
  49 #define LIST_HEAD(name) \
  50         struct list_head name = LIST_HEAD_INIT(name)
  51
  52 static inline void
  53 INIT_LIST_HEAD(struct list_head *list)
  54 {
  55         list->next = list;
  56         list->prev = list;
  57 }
  58
  59 static inline int
  60 list_empty(const struct list_head *head)
  61 {
  62         return (head->next == head);
  63 }
  64
  65 static inline int
  66 list_empty_careful(const struct list_head *head)
  67 {
  68         struct list_head *next = head->next;
  69
  70         return ((next == head) && (next == head->prev));
  71 }
  72
  73 static inline void
  74 __list_del(struct list_head *prev, struct list_head *next)
  75 {
  76         next->prev = prev;
  77         prev->next = next;
  78 }
  79
  80 static inline void
  81 __list_del_entry(struct list_head *entry)
  82 {
  83         __list_del(entry->prev, entry->next);
  84 }
  85
  86 static inline void
  87 list_del(struct list_head *entry)
  88 {
  89         __list_del(entry->prev, entry->next);
  90 }
  91
  92 static inline void
  93 list_replace(struct list_head *old, struct list_head *new)
  94 {
  95         new->next = old->next;
  96         new->next->prev = new;
  97         new->prev = old->prev;
  98         new->prev->next = new;
  99 }
 100
 101 static inline void
 102 list_replace_init(struct list_head *old, struct list_head *new)
 103 {
 104         list_replace(old, new);
 105         INIT_LIST_HEAD(old);
 106 }
 107
 108 static inline void
 109 linux_list_add(struct list_head *new, struct list_head *prev,
 110         struct list_head *next)
 111 {
 112         next->prev = new;
 113         new->next = next;
 114         new->prev = prev;
 115         prev->next = new;
 116 }
 117
 118 static inline void
 119 list_del_init(struct list_head *entry)
 120 {
 121         list_del(entry);
 122         INIT_LIST_HEAD(entry);
 123 }
 124
 125 #define list_entry(ptr, type, field)    container_of(ptr, type, field)
 126
 127 #define list_first_entry(ptr, type, member) \
 128         list_entry((ptr)->next, type, member)
 129
 130 #define list_last_entry(ptr, type, member)      \
 131         list_entry((ptr)->prev, type, member)
 132
 133 #define list_first_entry_or_null(ptr, type, member) \
 134         (!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL)
 135
 136 #define list_next_entry(ptr, member)                                    \
 137         list_entry(((ptr)->member.next), typeof(*(ptr)), member)
 138
 139 #define list_safe_reset_next(ptr, n, member) \
 140         (n) = list_next_entry(ptr, member)
 141
 142 #define list_prev_entry(ptr, member)                                    \
 143         list_entry(((ptr)->member.prev), typeof(*(ptr)), member)
 144
 145 #define list_for_each(p, head)                                          \
 146         for (p = (head)->next; p != (head); p = (p)->next)
 147
 148 #define list_for_each_safe(p, n, head)                                  \
 149         for (p = (head)->next, n = (p)->next; p != (head); p = n, n = (p)->next)
 150
 151 #define list_for_each_entry(p, h, field)                                \
 152         for (p = list_entry((h)->next, typeof(*p), field); &(p)->field != (h); \
 153             p = list_entry((p)->field.next, typeof(*p), field))
 154
 155 #define list_for_each_entry_safe(p, n, h, field)                        \
 156         for (p = list_entry((h)->next, typeof(*p), field),              \
 157             n = list_entry((p)->field.next, typeof(*p), field); &(p)->field != (h);\
 158             p = n, n = list_entry(n->field.next, typeof(*n), field))
 159
 160 #define list_for_each_entry_from(p, h, field) \
 161         for ( ; &(p)->field != (h); \
 162             p = list_entry((p)->field.next, typeof(*p), field))
 163
 164 #define list_for_each_entry_continue(p, h, field)                       \
 165         for (p = list_next_entry((p), field); &(p)->field != (h);       \
 166             p = list_next_entry((p), field))
 167
 168 #define list_for_each_entry_safe_from(pos, n, head, member)                     \
 169         for (n = list_entry((pos)->member.next, typeof(*pos), member);          \
 170              &(pos)->member != (head);                                          \
 171              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 172
 173 #define list_for_each_entry_reverse(p, h, field)                        \
 174         for (p = list_entry((h)->prev, typeof(*p), field); &(p)->field != (h); \
 175             p = list_entry((p)->field.prev, typeof(*p), field))
 176
 177 #define list_for_each_entry_safe_reverse(p, n, h, field)                \
 178         for (p = list_entry((h)->prev, typeof(*p), field),              \
 179             n = list_entry((p)->field.prev, typeof(*p), field); &(p)->field != (h); \
 180             p = n, n = list_entry(n->field.prev, typeof(*n), field))
 181
 182 #define list_for_each_entry_continue_reverse(p, h, field) \
 183         for (p = list_entry((p)->field.prev, typeof(*p), field); &(p)->field != (h); \
 184             p = list_entry((p)->field.prev, typeof(*p), field))
 185
 186 #define list_for_each_prev(p, h) for (p = (h)->prev; p != (h); p = (p)->prev)
 187
 188 #define list_for_each_entry_from_reverse(p, h, field)   \
 189         for (; &p->field != (h);                        \
 190              p = list_prev_entry(p, field))
 191
 192 static inline void
 193 list_add(struct list_head *new, struct list_head *head)
 194 {
 195         linux_list_add(new, head, head->next);
 196 }
 197
 198 static inline void
 199 list_add_tail(struct list_head *new, struct list_head *head)
 200 {
 201         linux_list_add(new, head->prev, head);
 202 }
 203
 204 static inline void
 205 list_move(struct list_head *list, struct list_head *head)
 206 {
 207         list_del(list);
 208         list_add(list, head);
 209 }
 210
 211 static inline void
 212 list_move_tail(struct list_head *entry, struct list_head *head)
 213 {
 214         list_del(entry);
 215         list_add_tail(entry, head);
 216 }
 217
 218 static inline void
 219 list_rotate_to_front(struct list_head *entry, struct list_head *head)
 220 {
 221         list_move_tail(entry, head);
 222 }
 223
 224 static inline void
 225 list_bulk_move_tail(struct list_head *head, struct list_head *first,
 226         struct list_head *last)
 227 {
 228         first->prev->next = last->next;
 229         last->next->prev = first->prev;
 230         head->prev->next = first;
 231         first->prev = head->prev;
 232         last->next = head;
 233         head->prev = last;
 234 }
 235
 236 static inline void
 237 linux_list_splice(const struct list_head *list, struct list_head *prev,
 238         struct list_head *next)
 239 {
 240         struct list_head *first;
 241         struct list_head *last;
 242
 243         if (list_empty(list))
 244                 return;
 245         first = list->next;
 246         last = list->prev;
 247         first->prev = prev;
 248         prev->next = first;
 249         last->next = next;
 250         next->prev = last;
 251 }
 252
 253 static inline void
 254 list_splice(const struct list_head *list, struct list_head *head)
 255 {
 256         linux_list_splice(list, head, head->next);
 257 }
 258
 259 static inline void
 260 list_splice_tail(struct list_head *list, struct list_head *head)
 261 {
 262         linux_list_splice(list, head->prev, head);
 263 }
 264
 265 static inline void
 266 list_splice_init(struct list_head *list, struct list_head *head)
 267 {
 268         linux_list_splice(list, head, head->next);
 269         INIT_LIST_HEAD(list);
 270 }
 271
 272 static inline void
 273 list_splice_tail_init(struct list_head *list, struct list_head *head)
 274 {
 275         linux_list_splice(list, head->prev, head);
 276         INIT_LIST_HEAD(list);
 277 }
 278
 279 /*
 280  * Double linked lists with a single pointer list head.
 281  * IGNORED
 282  */
 283
 284 static inline int list_is_singular(const struct list_head *head)
 285 {
 286         return !list_empty(head) && (head->next == head->prev);
 287 }
 288
 289 static inline void __list_cut_position(struct list_head *list,
 290                 struct list_head *head, struct list_head *entry)
 291 {
 292         struct list_head *new_first = entry->next;
 293         list->next = head->next;
 294         list->next->prev = list;
 295         list->prev = entry;
 296         entry->next = list;
 297         head->next = new_first;
 298         new_first->prev = head;
 299 }
 300
 301 static inline void list_cut_position(struct list_head *list,
 302                 struct list_head *head, struct list_head *entry)
 303 {
 304         if (list_empty(head))
 305                 return;
 306         if (list_is_singular(head) &&
 307                 (head->next != entry && head != entry))
 308                 return;
 309         if (entry == head)
 310                 INIT_LIST_HEAD(list);
 311         else
 312                 __list_cut_position(list, head, entry);
 313 }
 314
 315 static inline int list_is_first(const struct list_head *list,
 316                                 const struct list_head *head)
 317 {
 318         return (list->prev == head);
 319 }
 320
 321 static inline int list_is_last(const struct list_head *list,
 322                                 const struct list_head *head)
 323 {
 324         return list->next == head;
 325 }
 326
 327 static inline size_t
 328 list_count_nodes(const struct list_head *list)
 329 {
 330         const struct list_head *lh;
 331         size_t count;
 332
 333         count = 0;
 334         list_for_each(lh, list) {
 335                 count++;
 336         }
 337
 338         return (count);
 339 }
 340
 341 /*
 342  * Double linked lists with a single pointer list head.
 343  * IGNORED
 344  */
 345
 346 /* begin OpenOCD extensions */
 347
 348 /**
 349  * list_for_each_entry_direction - iterate forward/backward over list of given type
 350  * @param is_fwd the iterate direction, true for forward, false for backward.
 351  * @param p      the type * to use as a loop cursor.
 352  * @param h      the head of the list.
 353  * @param field  the name of the list_head within the struct.
 354  */
 355 #define list_for_each_entry_direction(is_fwd, p, h, field)                                      \
 356         for (p = list_entry(is_fwd ? (h)->next : (h)->prev, typeof(*p), field); \
 357                 &(p)->field != (h);                                                                                                     \
 358                 p = list_entry(is_fwd ? (p)->field.next : (p)->field.prev, typeof(*p), field))
 359
 360 /**
 361  * list_rotate_left - rotate the list to the left
 362  * @param h the head of the list
 363  */
 364 static inline void list_rotate_left(struct list_head *h)
 365 {
 366         struct list_head *first;
 367
 368         if (!list_empty(h)) {
 369                 first = h->next;
 370                 list_move_tail(first, h);
 371         }
 372 }
 373
 374 /* end OpenOCD extensions */
 375
 376 #endif /* OPENOCD_HELPER_LIST_H */