mono/utils/mono-linked-list-set.h

   1 /*
   2  * mono-linked-list-set.h: A lock-free split ordered list.
   3  *
   4  * Author:
   5  *      Rodrigo Kumpera (kumpera@gmail.com)
   6  *
   7  * (C) 2011 Novell, Inc
   8  */
   9
  10 #ifndef __MONO_SPLIT_ORDERED_LIST_H__
  11 #define __MONO_SPLIT_ORDERED_LIST_H__
  12
  13 #include <mono/utils/hazard-pointer.h>
  14 #include <mono/utils/mono-membar.h>
  15
  16 typedef struct _MonoLinkedListSetNode MonoLinkedListSetNode;
  17
  18 struct _MonoLinkedListSetNode {
  19         /* next must be the first element in this struct! */
  20         MonoLinkedListSetNode *next;
  21         uintptr_t key;
  22 };
  23
  24 typedef struct {
  25         MonoLinkedListSetNode *head;
  26         void (*free_node_func)(void *);
  27 } MonoLinkedListSet;
  28
  29
  30 static inline gpointer
  31 mono_lls_pointer_unmask (gpointer p)
  32 {
  33         return (gpointer)((uintptr_t)p & ~(uintptr_t)0x3);
  34 }
  35
  36 static inline uintptr_t
  37 mono_lls_pointer_get_mark (gpointer n)
  38 {
  39         return (uintptr_t)n & 0x1;
  40 }
  41
  42 /*
  43 Those are low level operations. prev, cur, next are returned in the hazard pointer table.
  44 You must manually clean the hazard pointer table after using them.
  45 */
  46
  47 void
  48 mono_lls_init (MonoLinkedListSet *list, void (*free_node_func)(void *));
  49
  50 gboolean
  51 mono_lls_find (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, uintptr_t key);
  52
  53 gboolean
  54 mono_lls_insert (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value);
  55
  56 gboolean
  57 mono_lls_remove (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value);
  58
  59 gpointer
  60 get_hazardous_pointer_with_mask (gpointer volatile *pp, MonoThreadHazardPointers *hp, int hazard_index);
  61
  62 /*
  63 Requires the world to be stoped
  64 */
  65 #define MONO_LLS_FOREACH(list, element, type) {\
  66         MonoLinkedListSetNode *__cur;   \
  67         for (__cur = (list)->head; __cur; __cur = mono_lls_pointer_unmask (__cur->next)) \
  68                 if (!mono_lls_pointer_get_mark (__cur->next)) { \
  69                         (element) = (type)__cur;
  70
  71
  72 #define MONO_LLS_FOREACH_FILTERED(list, element, filter_func, type) {\
  73         MonoLinkedListSetNode *__cur;   \
  74         for (__cur = (list)->head; __cur; __cur = mono_lls_pointer_unmask (__cur->next)) \
  75                 if (!mono_lls_pointer_get_mark (__cur->next)) { \
  76                         (element) = (type)__cur;                        \
  77                         if (!filter_func (element)) continue;
  78
  79 #define MONO_LLS_END_FOREACH }}
  80
  81 static inline MonoLinkedListSetNode*
  82 mono_lls_info_step (MonoLinkedListSetNode *val, MonoThreadHazardPointers *hp)
  83 {
  84         val = (MonoLinkedListSetNode *) mono_lls_pointer_unmask (val);
  85         mono_hazard_pointer_set (hp, 1, val);
  86         return val;
  87 }
  88
  89 /*
  90 Provides snapshot iteration
  91 */
  92 #define MONO_LLS_FOREACH_SAFE(list, element, type) {\
  93         MonoThreadHazardPointers *__hp = mono_hazard_pointer_get ();    \
  94         MonoLinkedListSetNode *__cur, *__next;  \
  95         for (__cur = (MonoLinkedListSetNode *) mono_lls_pointer_unmask (get_hazardous_pointer ((gpointer volatile*)&(list)->head, __hp, 1)); \
  96                 __cur;  \
  97                 __cur = (MonoLinkedListSetNode *) mono_lls_info_step (__next, __hp)) {  \
  98                 __next = (MonoLinkedListSetNode *) get_hazardous_pointer_with_mask ((gpointer volatile*)&__cur->next, __hp, 0); \
  99                 if (!mono_lls_pointer_get_mark (__next)) {      \
 100                         (element) = (type)__cur;
 101
 102 #define MONO_LLS_FOREACH_FILTERED_SAFE(list, element, filter_func, type) {\
 103         MonoThreadHazardPointers *__hp = mono_hazard_pointer_get ();    \
 104         MonoLinkedListSetNode *__cur, *__next;  \
 105         for (__cur = (MonoLinkedListSetNode *) mono_lls_pointer_unmask (get_hazardous_pointer ((gpointer volatile*)&(list)->head, __hp, 1)); \
 106                 __cur;  \
 107                 __cur = (MonoLinkedListSetNode *) mono_lls_info_step (__next, __hp)) {  \
 108                 __next = (MonoLinkedListSetNode *) get_hazardous_pointer_with_mask ((gpointer volatile*)&__cur->next, __hp, 0); \
 109                 if (!mono_lls_pointer_get_mark (__next)) {      \
 110                         (element) = (type)__cur;        \
 111                         if (!filter_func (element)) continue;
 112
 113
 114 #define MONO_LLS_END_FOREACH_SAFE \
 115                 } \
 116         }       \
 117         mono_hazard_pointer_clear (__hp, 0); \
 118         mono_hazard_pointer_clear (__hp, 1); \
 119 }
 120
 121 #endif /* __MONO_SPLIT_ORDERED_LIST_H__ */