GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 92.0% 23 / 0 / 25
Functions: 100.0% 8 / 0 / 8
Branches: 55.6% 10 / 0 / 18
storage/index/dram/extendible_hash.h
Line Branch Exec Source
1 #pragma once
2
3 #include <cstdlib>
4 #include <cstring>
5 #include <new>
6 #include "../index.h"
7 #include "base/factory.h"
8 #include "storage/kv_engine/base_kv.h"
9 #include "../utils/util.h"
10 #define LSB
11
12 const size_t kMask = 256 - 1;
13 const size_t kShift = 8;
14
15 struct Block {
16 static const size_t kBlockSize = 256; // 4 - 1
17 // static const size_t kBlockSize = 1024; // 16 - 1
18 // static const size_t kBlockSize = 4*1024; // 64 - 1
19 // static const size_t kBlockSize = 16*1024; // 256 - 1
20 // static const size_t kBlockSize = 64*1024; // 1024 - 1
21 // static const size_t kBlockSize = 256 * 1024; // 4096 - 1
22 static const size_t kNumSlot = kBlockSize / sizeof(Pair);
23
24 Block(void) : local_depth{0} {}
25
26
2/2
✓ Branch 1 taken 158624 times.
✓ Branch 2 taken 9914 times.
 168538 Block(size_t depth) : local_depth{depth} {}
27
28 ~Block(void) {}
29
30 9914 void* operator new(size_t size) {
31 9914 void* ret = nullptr;
32
3/6
✓ Branch 0 taken 9914 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 9914 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 9914 times.
 9914 if (posix_memalign(&ret, 64, size) != 0 || ret == nullptr)
33 ✗ throw std::bad_alloc();
34 9914 return ret;
35 }
36
37 void* operator new[](size_t size) {
38 void* ret = nullptr;
39 if (posix_memalign(&ret, 64, size) != 0 || ret == nullptr)
40 throw std::bad_alloc();
41 return ret;
42 }
43
44 int Insert(Key_t&, Value_t, size_t, Value_t* old_value = nullptr);
45 void Insert4split(Key_t&, Value_t);
46 bool Put(Key_t&, Value_t, size_t);
47 Block** Split(void);
48 bool Delete(Key_t&);
49
50 void operator delete[](void* p) noexcept { std::free(p); }
51 void operator delete[](void* p, std::size_t) noexcept { std::free(p); }
52 void operator delete(void* p) noexcept { std::free(p); }
53 void operator delete(void* p, std::size_t) noexcept { std::free(p); }
54
55 Pair _[kNumSlot];
56 size_t local_depth;
57 int64_t sema = 0;
58 size_t pattern = 0;
59 size_t numElem(void);
60 };
61
62 struct Directory {
63 static const size_t kDefaultDirectorySize = 1024;
64 Block** _;
65 size_t capacity;
66 bool lock;
67 int sema = 0;
68
69 Directory(void) {
70 capacity = kDefaultDirectorySize;
71 _ = new Block*[capacity];
72 lock = false;
73 sema = 0;
74 }
75
76 364 Directory(size_t size) {
77 364 capacity = size;
78
1/2
✓ Branch 0 taken 364 times.
✗ Branch 1 not taken.
 364 _ = new Block*[capacity];
79 364 lock = false;
80 364 sema = 0;
81 364 }
82
83
1/2
✓ Branch 0 taken 364 times.
✗ Branch 1 not taken.
 364 ~Directory(void) { delete[] _; }
84
85 5944 bool Acquire(void) {
86 5944 bool unlocked = false;
87 5944 return CAS(&lock, &unlocked, true);
88 }
89
90 4550 bool Release(void) {
91 4550 bool locked = true;
92 4550 return CAS(&lock, &locked, false);
93 }
94
95 void SanityCheck(void*);
96 void LSBUpdate(int, int, int, int, Block**);
97 };
98
99 class ExtendibleHash : public Index {
100 public:
101 ExtendibleHash(const BaseKVConfig& config);
102 ~ExtendibleHash();
103 bool Delete(Key_t&) override;
104 double Utilization(void) override;
105 size_t Capacity(void) override;
106 void Get(Key_t key, Value_t& value, unsigned tid) override;
107 Value_t Put(Key_t key, Value_t value, unsigned tid) override;
108 void BatchGet(base::ConstArray<Key_t> keys,
109 Value_t* pointers,
110 unsigned tid) override;
111 void BatchPut(base::ConstArray<Key_t> keys,
112 Value_t* pointers,
113 unsigned tid) override;
114
115 364 void operator delete(void* p) noexcept { std::free(p); }
116 void operator delete(void* p, std::size_t) noexcept { std::free(p); }
117 364 void* operator new(size_t size) {
118 364 void* ret = nullptr;
119
3/6
✓ Branch 0 taken 364 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 364 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 364 times.
 364 if (posix_memalign(&ret, 64, size) != 0 || ret == nullptr)
120 ✗ throw std::bad_alloc();
121 364 return ret;
122 }
123
124 private:
125 Directory dir;
126 size_t global_depth;
127
128 size_t DirectoryIndex(size_t key_hash) const;
129 void HintPrefetch(size_t key_hash) const;
130 Value_t ExtractWithHash(Key_t& key, size_t key_hash);
131 Value_t Extract(Key_t& key);
132 Value_t Insert(Key_t& key, Value_t value);
133 bool InsertOnly(Key_t& key, Value_t value);
134 Value_t FindAnyway(Key_t&);
135 };
136