-
Notifications
You must be signed in to change notification settings - Fork 1
/
paxtypes.h
executable file
·109 lines (97 loc) · 3.45 KB
/
paxtypes.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
106
107
108
109
// Definitions for some basic types used in Paxos
#pragma once
#include <set>
#include <iostream>
// Request type, viewid, viewstamp, view
// Declarations mostly come from and only lightly modified from
// Mazieres, "Paxos Made Practical"
// Group identifier (id_t in Mazieres) eliminated
// cid (cohort identifier) and net_address_t are a tuple in
// Mazieres that identifies a Paxos participant and allows
// network communication. Our node_id_t (node.h)
// serves both those functions.
typedef int64_t rid_t; // Request identifier, 0 is illegal
struct viewid_t {
uint64_t counter;
node_id_t manager; // node_id_t instead of cid
bool operator ==(const viewid_t& vid) const {
return (counter == vid.counter) && (manager == vid.manager);
}
bool operator !=(const viewid_t& vid) const {
return (counter != vid.counter) || (manager != vid.manager);
}
};
bool operator <(const viewid_t& x, const viewid_t& y);
bool operator <=(const viewid_t& x, const viewid_t& y);
bool operator >(const viewid_t& x, const viewid_t& y);
bool operator >=(const viewid_t& x, const viewid_t& y);
std::ostream& operator<<(std::ostream& os, const viewid_t&);
namespace std {
template<>
struct hash<viewid_t> {
typedef viewid_t argument_type;
typedef std::size_t value_type;
value_type operator()(const argument_type& s) const {
value_type const h1 ( std::hash<uint64_t>()(s.counter) );
value_type const h2 ( std::hash<node_id_t>()(s.manager) );
return h1 ^ (h2 << 12);
}
};
}
struct viewstamp_t {
viewid_t vid;
uint64_t ts;
bool operator==(const viewstamp_t& vs) const {
return (vid == vs.vid) && (ts == vs.ts);
}
bool operator!=(const viewstamp_t& vs) const {
return !(*this == vs);
}
bool sucessor(const viewstamp_t& vs) const {
// Within a view, timestamps increase by 1
if(vid == vs.vid) return (ts == (vs.ts+1));
// Across views, timestamps begin with 1
return (vid > vs.vid) && (ts == 1ULL);
}
};
std::ostream& operator<<(std::ostream& os, const viewstamp_t& vs);
bool operator <(const viewstamp_t& x, const viewstamp_t& y);
bool operator <=(const viewstamp_t& x, const viewstamp_t& y);
bool operator >(const viewstamp_t& x, const viewstamp_t& y);
bool operator >=(const viewstamp_t& x, const viewstamp_t& y);
namespace std {
template<>
struct hash<viewstamp_t> {
typedef viewstamp_t argument_type;
typedef std::size_t value_type;
value_type operator()(const argument_type& s) const {
value_type const h1 ( std::hash<viewid_t>()(s.vid) );
value_type const h2 ( std::hash<uint64_t>()(s.ts) );
return (h1<<12) ^ (h2);
}
};
}
struct view_t {
viewid_t vid;
node_id_t primary;
// Not really sure if this should be a set, it is for set_difference
std::set<node_id_t> backups;
bool elt_in(node_id_t node) const {
if(node == primary) return true;
for(const auto& backup : backups ) {
if( backup == node ) return true;
}
return false;
}
std::set<node_id_t> get_servers() const {
std::set<node_id_t> s = backups;
s.insert(primary);
return s;
}
bool operator==(const view_t& v) {
return (vid == v.vid)
&& (primary == v.primary)
&& (backups == v.backups);
}
};
std::ostream& operator<<(std::ostream& os, const view_t& vid);