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) MONO_INTERNAL;
  52
  53 gboolean
  54 mono_lls_insert (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value) MONO_INTERNAL;
  55
  56 gboolean
  57 mono_lls_remove (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value) MONO_INTERNAL;
  58
  59 gpointer
  60 get_hazardous_pointer_with_mask (gpointer volatile *pp, MonoThreadHazardPointers *hp, int hazard_index) MONO_INTERNAL;
  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 #define MONO_LLS_END_FOREACH }}
  72
  73 static inline MonoLinkedListSetNode*
  74 mono_lls_info_step (MonoLinkedListSetNode *val, MonoThreadHazardPointers *hp)
  75 {
  76         val = mono_lls_pointer_unmask (val);
  77         mono_hazard_pointer_set (hp, 1, val);
  78         return val;
  79 }
  80
  81 /*
  82 Provides snapshot iteration
  83 */
  84 #define MONO_LLS_FOREACH_SAFE(list, element, type) {\
  85         MonoThreadHazardPointers *__hp = mono_hazard_pointer_get ();    \
  86         MonoLinkedListSetNode *__cur, *__next;  \
  87         for (__cur = mono_lls_pointer_unmask (get_hazardous_pointer ((gpointer volatile*)&(list)->head, __hp, 1)); \
  88                 __cur;  \
  89                 __cur = mono_lls_info_step (__next, __hp)) {    \
  90                 __next = get_hazardous_pointer_with_mask ((gpointer volatile*)&__cur->next, __hp, 0);   \
  91                 if (!mono_lls_pointer_get_mark (__next)) {      \
  92                         (element) = (type)__cur;
  93
  94 #define MONO_LLS_END_FOREACH_SAFE \
  95                 } \
  96         }       \
  97         mono_hazard_pointer_clear (__hp, 0); \
  98         mono_hazard_pointer_clear (__hp, 1); \
  99 }
 100
 101 #endif /* __MONO_SPLIT_ORDERED_LIST_H__ */