-
Notifications
You must be signed in to change notification settings - Fork 0
/
lf_set.h
105 lines (90 loc) · 2.71 KB
/
lf_set.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#ifndef CDC7572F_E1AD_4B7D_B182_4CA81AA68BB4
#define CDC7572F_E1AD_4B7D_B182_4CA81AA68BB4
#include <mutex>
#include <thread>
#include <iostream>
#include <chrono>
#include <vector>
#include <mutex>
#include <memory>
#include <atomic>
#include <climits>
#include <algorithm>
#include <optional>
using namespace std;
constexpr unsigned MAX_THREAD = 128;
constexpr uintptr_t WITH_MARK = -1;
constexpr uintptr_t POINTER_ONLY = -2;
class LFNODE
{
public:
unsigned long key;
unsigned long value;
bool is_new; // dummy node일 경우에만 의미가 있음.
LFNODE *next;
LFNODE(unsigned long key, unsigned long value) : key{ key }, next{ nullptr }, value{ value }, is_new{ true } {}
LFNODE *GetNext()
{
return reinterpret_cast<LFNODE *>((uintptr_t)next & POINTER_ONLY);
}
void SetNext(LFNODE *ptr)
{
next = ptr;
}
LFNODE *GetNextWithMark(bool *mark)
{
uintptr_t temp = (uintptr_t)next;
*mark = temp & 1;
return reinterpret_cast<LFNODE *>(temp & POINTER_ONLY);
}
bool CAS(uintptr_t old_value, uintptr_t new_value)
{
return atomic_compare_exchange_strong(
reinterpret_cast<atomic_uintptr_t *>(&next),
&old_value, new_value);
}
bool CAS(LFNODE *old_next, LFNODE *new_next, bool old_mark, bool new_mark)
{
uintptr_t old_value = reinterpret_cast<uintptr_t>(old_next);
if (old_mark)
old_value = old_value | 0x1;
else
old_value = old_value & POINTER_ONLY;
uintptr_t new_value = reinterpret_cast<uintptr_t>(new_next);
if (new_mark)
new_value = new_value | 0x1;
else
new_value = new_value & POINTER_ONLY;
return CAS(old_value, new_value);
}
bool TryMark(LFNODE *ptr)
{
uintptr_t old_value = reinterpret_cast<uintptr_t>(ptr) & POINTER_ONLY;
uintptr_t new_value = old_value | 1;
return CAS(old_value, new_value);
}
bool IsMarked()
{
return (0 != ((uintptr_t)next & 1));
}
};
class LFSET
{
LFNODE head;
public:
LFSET();
~LFSET();
void Init();
void Dump();
bool Find(LFNODE &from, unsigned long x, LFNODE **pred, LFNODE **curr);
// 성공하면 삽입된 노드 pointer 반환, 실패하면 이미 삽입된 노드의 pointer 반환
LFNODE *Add(LFNODE &from, unsigned long x, unsigned long value = 0);
bool Add(LFNODE &from, LFNODE &node);
bool Remove(LFNODE &from, unsigned long x);
optional<unsigned long> Contains(unsigned long x);
optional<unsigned long> Contains(LFNODE &from, unsigned long x);
LFNODE& get_head() {return head;}
};
void start_op();
void end_op();
#endif /* CDC7572F_E1AD_4B7D_B182_4CA81AA68BB4 */