-
Notifications
You must be signed in to change notification settings - Fork 0
/
skiplist.h
77 lines (57 loc) · 1.18 KB
/
skiplist.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
#ifndef SKIPLIST_H
#define SKIPLIST_H
#include <cstdint>
// #include <optional>
// #include <vector>
#include <string>
#include <map>
using key_type = uint64_t;
using value_type = std::string;
class SkipList;
class Node
{
friend SkipList;
key_type key;
value_type value;
Node** forward;
public:
explicit Node(int lvl, key_type k, value_type v);
~Node(){
delete[] forward;
}
};
class SkipList
{
std::string DFLAG = "~DELETED~";
int level;
int maxLevel;
Node* header;
Node* tailer;
double p;
uint64_t number;
uint64_t MAX_SIZE = 408;
int random_level();
public:
explicit SkipList(double pr = 0.5);
bool put(key_type key, const value_type &val);
std::string get(key_type key) const;
void scan(key_type key1, key_type key2, std::map<uint64_t, std::string> &res);
void getAll(std::map<uint64_t, std::string> &res);
uint64_t size() {
return number;
}
key_type getMinKey() {
return header->forward[0]->key;
}
key_type getMaxKey(){
Node* x = header;
while (x->forward[0] != tailer){
x = x->forward[0];
}
return x->key;
}
bool areaNotCross(uint64_t min, uint64_t max) {
return getMinKey() >= max || getMaxKey() <= min;
}
};
#endif // SKIPLIST_H