lib/libpmcstat/pmu-events/list.h

   1 /*-
   2  * Copyright (c) 2010 Isilon Systems, Inc.
   3  * Copyright (c) 2010 iX Systems, Inc.
   4  * Copyright (c) 2010 Panasas, Inc.
   5  * Copyright (c) 2013-2016 Mellanox Technologies, Ltd.
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice unmodified, this list of conditions, and the following
  13  *    disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in the
  16  *    documentation and/or other materials provided with the distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  19  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  20  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  21  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  22  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  23  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  27  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  *
  29  * $FreeBSD$
  30  */
  31 #ifndef _LINUX_LIST_H_
  32 #define _LINUX_LIST_H_
  33
  34 #define container_of(ptr, type, member)                         \
  35 ({                                                              \
  36         const __typeof(((type *)0)->member) *__p = (ptr);       \
  37         (type *)((uintptr_t)__p - offsetof(type, member));      \
  38 })
  39
  40 #define LINUX_LIST_HEAD_INIT(name) { &(name), &(name) }
  41
  42 #define LINUX_LIST_HEAD(name) \
  43         struct list_head name = LINUX_LIST_HEAD_INIT(name)
  44
  45 #ifndef LIST_HEAD_DEF
  46 #define LIST_HEAD_DEF
  47 struct list_head {
  48         struct list_head *next;
  49         struct list_head *prev;
  50 };
  51 #endif
  52
  53 #define barrier()                       __asm__ __volatile__("": : :"memory")
  54
  55
  56 #define ACCESS_ONCE(x)                  (*(volatile __typeof(x) *)&(x))
  57
  58 #define WRITE_ONCE(x,v) do {            \
  59         barrier();                      \
  60         ACCESS_ONCE(x) = (v);           \
  61         barrier();                      \
  62 } while (0)
  63
  64 #define READ_ONCE(x) ({                 \
  65         __typeof(x) __var = ({          \
  66                 barrier();              \
  67                 ACCESS_ONCE(x);         \
  68         });                             \
  69         barrier();                      \
  70         __var;                          \
  71 })
  72
  73 static inline void
  74 INIT_LIST_HEAD(struct list_head *list)
  75 {
  76
  77         list->next = list->prev = list;
  78 }
  79
  80 static inline int
  81 list_empty(const struct list_head *head)
  82 {
  83
  84         return (head->next == head);
  85 }
  86
  87 static inline int
  88 list_empty_careful(const struct list_head *head)
  89 {
  90         struct list_head *next = head->next;
  91
  92         return ((next == head) && (next == head->prev));
  93 }
  94
  95 static inline void
  96 __list_del(struct list_head *prev, struct list_head *next)
  97 {
  98         next->prev = prev;
  99         WRITE_ONCE(prev->next, next);
 100 }
 101
 102 static inline void
 103 __list_del_entry(struct list_head *entry)
 104 {
 105
 106         __list_del(entry->prev, entry->next);
 107 }
 108
 109 static inline void
 110 list_del(struct list_head *entry)
 111 {
 112
 113         __list_del(entry->prev, entry->next);
 114 }
 115
 116 static inline void
 117 list_replace(struct list_head *old, struct list_head *new)
 118 {
 119         new->next = old->next;
 120         new->next->prev = new;
 121         new->prev = old->prev;
 122         new->prev->next = new;
 123 }
 124
 125 static inline void
 126 list_replace_init(struct list_head *old, struct list_head *new)
 127 {
 128         list_replace(old, new);
 129         INIT_LIST_HEAD(old);
 130 }
 131
 132 static inline void
 133 linux_list_add(struct list_head *new, struct list_head *prev,
 134     struct list_head *next)
 135 {
 136
 137         next->prev = new;
 138         new->next = next;
 139         new->prev = prev;
 140         prev->next = new;
 141 }
 142
 143 static inline void
 144 list_del_init(struct list_head *entry)
 145 {
 146
 147         list_del(entry);
 148         INIT_LIST_HEAD(entry);
 149 }
 150
 151 #define list_entry(ptr, type, field)    container_of(ptr, type, field)
 152
 153 #define list_first_entry(ptr, type, member) \
 154         list_entry((ptr)->next, type, member)
 155
 156 #define list_last_entry(ptr, type, member)      \
 157         list_entry((ptr)->prev, type, member)
 158
 159 #define list_first_entry_or_null(ptr, type, member) \
 160         (!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL)
 161
 162 #define list_next_entry(ptr, member)                                    \
 163         list_entry(((ptr)->member.next), typeof(*(ptr)), member)
 164
 165 #define list_safe_reset_next(ptr, n, member) \
 166         (n) = list_next_entry(ptr, member)
 167
 168 #define list_prev_entry(ptr, member)                                    \
 169         list_entry(((ptr)->member.prev), typeof(*(ptr)), member)
 170
 171 #define list_for_each(p, head)                                          \
 172         for (p = (head)->next; p != (head); p = (p)->next)
 173
 174 #define list_for_each_safe(p, n, head)                                  \
 175         for (p = (head)->next, n = (p)->next; p != (head); p = n, n = (p)->next)
 176
 177 #define list_for_each_entry(p, h, field)                                \
 178         for (p = list_entry((h)->next, typeof(*p), field); &(p)->field != (h); \
 179             p = list_entry((p)->field.next, typeof(*p), field))
 180
 181 #define list_for_each_entry_safe(p, n, h, field)                        \
 182         for (p = list_entry((h)->next, typeof(*p), field),              \
 183             n = list_entry((p)->field.next, typeof(*p), field); &(p)->field != (h);\
 184             p = n, n = list_entry(n->field.next, typeof(*n), field))
 185
 186 #define list_for_each_entry_from(p, h, field) \
 187         for ( ; &(p)->field != (h); \
 188             p = list_entry((p)->field.next, typeof(*p), field))
 189
 190 #define list_for_each_entry_continue(p, h, field)                       \
 191         for (p = list_next_entry((p), field); &(p)->field != (h);       \
 192             p = list_next_entry((p), field))
 193
 194 #define list_for_each_entry_safe_from(pos, n, head, member)                     \
 195         for (n = list_entry((pos)->member.next, typeof(*pos), member);          \
 196              &(pos)->member != (head);                                          \
 197              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 198
 199 #define list_for_each_entry_reverse(p, h, field)                        \
 200         for (p = list_entry((h)->prev, typeof(*p), field); &(p)->field != (h); \
 201             p = list_entry((p)->field.prev, typeof(*p), field))
 202
 203 #define list_for_each_entry_safe_reverse(p, n, h, field)                \
 204         for (p = list_entry((h)->prev, typeof(*p), field),              \
 205             n = list_entry((p)->field.prev, typeof(*p), field); &(p)->field != (h); \
 206             p = n, n = list_entry(n->field.prev, typeof(*n), field))
 207
 208 #define list_for_each_entry_continue_reverse(p, h, field) \
 209         for (p = list_entry((p)->field.prev, typeof(*p), field); &(p)->field != (h); \
 210             p = list_entry((p)->field.prev, typeof(*p), field))
 211
 212 #define list_for_each_prev(p, h) for (p = (h)->prev; p != (h); p = (p)->prev)
 213
 214 static inline void
 215 list_add(struct list_head *new, struct list_head *head)
 216 {
 217
 218         linux_list_add(new, head, head->next);
 219 }
 220
 221 static inline void
 222 list_add_tail(struct list_head *new, struct list_head *head)
 223 {
 224
 225         linux_list_add(new, head->prev, head);
 226 }
 227
 228 static inline void
 229 list_move(struct list_head *list, struct list_head *head)
 230 {
 231
 232         list_del(list);
 233         list_add(list, head);
 234 }
 235
 236 static inline void
 237 list_move_tail(struct list_head *entry, struct list_head *head)
 238 {
 239
 240         list_del(entry);
 241         list_add_tail(entry, head);
 242 }
 243
 244 static inline void
 245 linux_list_splice(const struct list_head *list, struct list_head *prev,
 246     struct list_head *next)
 247 {
 248         struct list_head *first;
 249         struct list_head *last;
 250
 251         if (list_empty(list))
 252                 return;
 253         first = list->next;
 254         last = list->prev;
 255         first->prev = prev;
 256         prev->next = first;
 257         last->next = next;
 258         next->prev = last;
 259 }
 260
 261 static inline void
 262 list_splice(const struct list_head *list, struct list_head *head)
 263 {
 264
 265         linux_list_splice(list, head, head->next);
 266 }
 267
 268 static inline void
 269 list_splice_tail(struct list_head *list, struct list_head *head)
 270 {
 271
 272         linux_list_splice(list, head->prev, head);
 273 }
 274
 275 static inline void
 276 list_splice_init(struct list_head *list, struct list_head *head)
 277 {
 278
 279         linux_list_splice(list, head, head->next);
 280         INIT_LIST_HEAD(list);
 281 }
 282
 283 static inline void
 284 list_splice_tail_init(struct list_head *list, struct list_head *head)
 285 {
 286
 287         linux_list_splice(list, head->prev, head);
 288         INIT_LIST_HEAD(list);
 289 }
 290
 291 #undef LIST_HEAD
 292 #define LIST_HEAD(name) struct list_head name = { &(name), &(name) }
 293
 294
 295 struct hlist_head {
 296         struct hlist_node *first;
 297 };
 298
 299 struct hlist_node {
 300         struct hlist_node *next, **pprev;
 301 };
 302
 303 #define HLIST_HEAD_INIT { }
 304 #define HLIST_HEAD(name) struct hlist_head name = HLIST_HEAD_INIT
 305 #define INIT_HLIST_HEAD(head) (head)->first = NULL
 306 #define INIT_HLIST_NODE(node)                                           \
 307 do {                                                                    \
 308         (node)->next = NULL;                                            \
 309         (node)->pprev = NULL;                                           \
 310 } while (0)
 311
 312 static inline int
 313 hlist_unhashed(const struct hlist_node *h)
 314 {
 315
 316         return !h->pprev;
 317 }
 318
 319 static inline int
 320 hlist_empty(const struct hlist_head *h)
 321 {
 322
 323         return !h->first;
 324 }
 325
 326 static inline void
 327 hlist_del(struct hlist_node *n)
 328 {
 329
 330         if (n->next)
 331                 n->next->pprev = n->pprev;
 332         *n->pprev = n->next;
 333 }
 334
 335 static inline void
 336 hlist_del_init(struct hlist_node *n)
 337 {
 338
 339         if (hlist_unhashed(n))
 340                 return;
 341         hlist_del(n);
 342         INIT_HLIST_NODE(n);
 343 }
 344
 345 static inline void
 346 hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 347 {
 348
 349         n->next = h->first;
 350         if (h->first)
 351                 h->first->pprev = &n->next;
 352         h->first = n;
 353         n->pprev = &h->first;
 354 }
 355
 356 static inline void
 357 hlist_add_before(struct hlist_node *n, struct hlist_node *next)
 358 {
 359
 360         n->pprev = next->pprev;
 361         n->next = next;
 362         next->pprev = &n->next;
 363         *(n->pprev) = n;
 364 }
 365
 366 static inline void
 367 hlist_add_after(struct hlist_node *n, struct hlist_node *next)
 368 {
 369
 370         next->next = n->next;
 371         n->next = next;
 372         next->pprev = &n->next;
 373         if (next->next)
 374                 next->next->pprev = &next->next;
 375 }
 376
 377 static inline void
 378 hlist_move_list(struct hlist_head *old, struct hlist_head *new)
 379 {
 380
 381         new->first = old->first;
 382         if (new->first)
 383                 new->first->pprev = &new->first;
 384         old->first = NULL;
 385 }
 386
 387 static inline int list_is_singular(const struct list_head *head)
 388 {
 389         return !list_empty(head) && (head->next == head->prev);
 390 }
 391
 392 static inline void __list_cut_position(struct list_head *list,
 393                 struct list_head *head, struct list_head *entry)
 394 {
 395         struct list_head *new_first = entry->next;
 396         list->next = head->next;
 397         list->next->prev = list;
 398         list->prev = entry;
 399         entry->next = list;
 400         head->next = new_first;
 401         new_first->prev = head;
 402 }
 403
 404 static inline void list_cut_position(struct list_head *list,
 405                 struct list_head *head, struct list_head *entry)
 406 {
 407         if (list_empty(head))
 408                 return;
 409         if (list_is_singular(head) &&
 410                 (head->next != entry && head != entry))
 411                 return;
 412         if (entry == head)
 413                 INIT_LIST_HEAD(list);
 414         else
 415                 __list_cut_position(list, head, entry);
 416 }
 417
 418 static inline int list_is_last(const struct list_head *list,
 419                                 const struct list_head *head)
 420 {
 421         return list->next == head;
 422 }
 423
 424 #define hlist_entry(ptr, type, field)   container_of(ptr, type, field)
 425
 426 #define hlist_for_each(p, head)                                         \
 427         for (p = (head)->first; p; p = (p)->next)
 428
 429 #define hlist_for_each_safe(p, n, head)                                 \
 430         for (p = (head)->first; p && ({ n = (p)->next; 1; }); p = n)
 431
 432 #define hlist_entry_safe(ptr, type, member) \
 433         ((ptr) ? hlist_entry(ptr, type, member) : NULL)
 434
 435 #define hlist_for_each_entry(pos, head, member)                         \
 436         for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
 437              pos;                                                       \
 438              pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
 439
 440 #define hlist_for_each_entry_continue(pos, member)                      \
 441         for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member); \
 442              (pos);                                                     \
 443              pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
 444
 445 #define hlist_for_each_entry_from(pos, member)                          \
 446         for (; (pos);                                                           \
 447              pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
 448
 449 #define hlist_for_each_entry_safe(pos, n, head, member)                 \
 450         for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member); \
 451              (pos) && ({ n = (pos)->member.next; 1; });                 \
 452              pos = hlist_entry_safe(n, typeof(*(pos)), member))
 453
 454 extern void list_sort(void *priv, struct list_head *head, int (*cmp)(void *priv,
 455     struct list_head *a, struct list_head *b));
 456
 457 #endif /* _LINUX_LIST_H_ */