2 * mono-linked-list-set.h: A lock-free split ordered list.
5 * Rodrigo Kumpera (kumpera@gmail.com)
10 #ifndef __MONO_SPLIT_ORDERED_LIST_H__
11 #define __MONO_SPLIT_ORDERED_LIST_H__
13 #include <mono/utils/hazard-pointer.h>
14 #include <mono/utils/mono-membar.h>
16 typedef struct _MonoLinkedListSetNode MonoLinkedListSetNode;
18 struct _MonoLinkedListSetNode {
19 /* next must be the first element in this struct! */
20 MonoLinkedListSetNode *next;
25 MonoLinkedListSetNode *head;
26 void (*free_node_func)(void *);
30 static inline gpointer
31 mono_lls_pointer_unmask (gpointer p)
33 return (gpointer)((uintptr_t)p & ~(uintptr_t)0x3);
36 static inline uintptr_t
37 mono_lls_pointer_get_mark (gpointer n)
39 return (uintptr_t)n & 0x1;
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.
48 mono_lls_init (MonoLinkedListSet *list, void (*free_node_func)(void *));
51 mono_lls_find (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, uintptr_t key) MONO_INTERNAL;
54 mono_lls_insert (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value) MONO_INTERNAL;
57 mono_lls_remove (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value) MONO_INTERNAL;
60 get_hazardous_pointer_with_mask (gpointer volatile *pp, MonoThreadHazardPointers *hp, int hazard_index) MONO_INTERNAL;
63 Requires the world to be stoped
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; \
71 #define MONO_LLS_END_FOREACH }}
73 static inline MonoLinkedListSetNode*
74 mono_lls_info_step (MonoLinkedListSetNode *val, MonoThreadHazardPointers *hp)
76 val = mono_lls_pointer_unmask (val);
77 mono_hazard_pointer_set (hp, 1, val);
82 Provides snapshot iteration
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)); \
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;
94 #define MONO_LLS_END_FOREACH_SAFE \
97 mono_hazard_pointer_clear (__hp, 0); \
98 mono_hazard_pointer_clear (__hp, 1); \
101 #endif /* __MONO_SPLIT_ORDERED_LIST_H__ */