souffle  2.0.2-371-g6315b36
Data Structures | Typedefs | Functions
souffle::test Namespace Reference

Data Structures

struct  reserver
 
struct  reserver< std::unordered_set< A, B, C, D > >
 

Typedefs

using Entry = std::tuple< int, int >
 
using EqRel = souffle::EquivalenceRelation< Tuple< RamDomain, 2 > >
 
using TestLambdaTree = souffle::LambdaBTreeSet< TestPair, std::function< TestPair::second_type(TestPair &)>, souffle::EqrelMapComparator< TestPair > >
 
typedef std::pair< size_t, size_t > TestPair
 
using time_point = std::chrono::high_resolution_clock::time_point
 

Functions

template<typename C >
int count (const C &c)
 
long duration (const time_point &start, const time_point &end)
 
std::vector< Entry > getData (unsigned numEntries)
 
time_point now ()
 
 TEST (BTreeMultiSet, Basic)
 
 TEST (BTreeMultiSet, BoundaryEmpty)
 
 TEST (BTreeMultiSet, BoundaryTest)
 
 TEST (BTreeMultiSet, Clear)
 
 TEST (BTreeMultiSet, Decremental)
 
 TEST (BTreeMultiSet, Duplicates)
 
 TEST (BTreeMultiSet, Incremental)
 
 TEST (BTreeMultiSet, IteratorBasic)
 
 TEST (BTreeMultiSet, IteratorEmpty)
 
 TEST (BTreeMultiSet, IteratorStress)
 
 TEST (BTreeMultiSet, Load)
 
 TEST (BTreeMultiSet, Shuffled)
 
 TEST (BTreeSet, Basic)
 
 TEST (BTreeSet, BoundaryEmpty)
 
 TEST (BTreeSet, BoundaryTest)
 
 TEST (BTreeSet, ChunkSplit)
 
 TEST (BTreeSet, ChunkSplitStress)
 
 TEST (BTreeSet, Clear)
 
 TEST (BTreeSet, Copy)
 
 TEST (BTreeSet, Decremental)
 
 TEST (BTreeSet, Duplicates)
 
 TEST (BTreeSet, Incremental)
 
 TEST (BTreeSet, IteratorBasic)
 
 TEST (BTreeSet, IteratorEmpty)
 
 TEST (BTreeSet, IteratorStress)
 
 TEST (BTreeSet, Load)
 
 TEST (BTreeSet, Merge)
 
 TEST (BTreeSet, Parallel)
 
 TEST (BTreeSet, Shuffled)
 
 TEST (DjTest, Clear)
 
 TEST (DjTest, MakeNode)
 
 TEST (DjTest, Scoping)
 The underlying Disjoint Set (essentially Anderson '91 Find-Union, but dynamic) More...
 
 TEST (DjTest, TestUnion)
 
 TEST (EqRelTest, Basic)
 
 TEST (EqRelTest, Clear)
 
 TEST (EqRelTest, Duplicates)
 
 TEST (EqRelTest, Extend)
 
 TEST (EqRelTest, IterBasic)
 
 TEST (EqRelTest, IterEmpty)
 
 TEST (EqRelTest, IterPartition)
 
 TEST (EqRelTest, IterRange)
 
 TEST (EqRelTest, Merge)
 
 TEST (EqRelTest, PairwiseDecremental)
 
 TEST (EqRelTest, PairwiseIncremental)
 
 TEST (EqRelTest, Scaling)
 
 TEST (EqRelTest, Scoping)
 
 TEST (EqRelTest, Shuffled)
 
 TEST (EqRelTest, TransitivityTest)
 
 TEST (Graph, Basic)
 
 TEST (LambdaBTreeTest, Insert)
 
 TEST (LambdaBTreeTest, Scoping)
 The LambdaBTree - essentially a ripoff to the Btree, but allows a function to be called on successful insert. More...
 
 TEST (Pack, Tuple)
 
 TEST (PackUnpack, Tuple)
 
 TEST (PackUnpack, Vector)
 
 TEST (ParallelUtils, OptimisticReadWriteLock)
 
 TEST (ParallelUtils, ReadWriteLock)
 
 TEST (ParallelUtils, SpinLock)
 
 TEST (Performance, Basic)
 
 TEST (Performance, Load)
 
 TEST (PiggyTest, Append)
 
 TEST (PiggyTest, CopyCtor)
 
 TEST (PiggyTest, DoubleClear)
 
 TEST (PiggyTest, ElementCreation)
 
 TEST (PiggyTest, Iteration)
 
 TEST (PiggyTest, Scoping)
 Regular Old Piggy List. More...
 
 TEST (RandomInsertPiggyTest, DoubleClear)
 
 TEST (RandomInsertPiggyTest, Insertion)
 
 TEST (RandomInsertPiggyTest, Scoping)
 Piggy List that allows creation at arbitrary elements. More...
 
 TEST (SparseDjTest, MakeNode)
 
 TEST (SparseDjTest, Scoping)
 The SparseDisjointSet that is used by the EquivalenceRelation. More...
 
 TEST (SparseDjTest, SignedData)
 
 TEST (SparseDjTest, TestUnion)
 
 TEST (SymbolTable, Assign)
 
 TEST (SymbolTable, Basics)
 
 TEST (SymbolTable, Copy)
 
 TEST (SymbolTable, Inserts)
 
 TEST (Table, Basic)
 
 TEST (Table, Stress)
 
template<typename Op >
long time (const std::string &name, const Op &operation)
 

Typedef Documentation

◆ Entry

typedef std::tuple< int, int > souffle::test::Entry

Definition at line 385 of file btree_multiset_test.cpp.

◆ EqRel

using souffle::test::EqRel = typedef souffle::EquivalenceRelation<Tuple<RamDomain, 2> >

Definition at line 56 of file binary_relation_test.cpp.

◆ TestLambdaTree

using souffle::test::TestLambdaTree = typedef souffle::LambdaBTreeSet<TestPair, std::function<TestPair::second_type(TestPair&)>, souffle::EqrelMapComparator<TestPair> >

Definition at line 513 of file eqrel_datastructure_test.cpp.

◆ TestPair

typedef std::pair<size_t, size_t> souffle::test::TestPair

Definition at line 511 of file eqrel_datastructure_test.cpp.

◆ time_point

typedef std::chrono::high_resolution_clock::time_point souffle::test::time_point

Definition at line 400 of file btree_multiset_test.cpp.

Function Documentation

◆ count()

template<typename C >
int souffle::test::count ( const C &  c)

Definition at line 40 of file table_test.cpp.

49  {

Referenced by TCB_SPAN_NAMESPACE_NAME::span< ElementType, Extent >::first(), souffle::profile::Tui::genJsonTop(), souffle::genJsonUsage(), souffle::ast::transform::MagicSetTransformer::LabelDatabaseTransformer::NegativeLabellingTransformer::getNegativeLabel(), souffle::ast::transform::MaterializeAggregationQueriesTransformer::instantiateUnnamedVariables(), TCB_SPAN_NAMESPACE_NAME::span< ElementType, Extent >::last(), rel(), rul(), TCB_SPAN_NAMESPACE_NAME::span< ElementType, Extent >::span(), TCB_SPAN_NAMESPACE_NAME::span< ElementType, Extent >::subspan(), TEST(), souffle::ast::transform::RemoveRedundantSumsTransformer::transform(), and usage().

◆ duration()

long souffle::test::duration ( const time_point &  start,
const time_point &  end 
)

Definition at line 406 of file btree_multiset_test.cpp.

406  {
407  return std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
408 }

Referenced by time().

◆ getData()

std::vector< Entry > souffle::test::getData ( unsigned  numEntries)

Definition at line 387 of file btree_multiset_test.cpp.

387  {
388  std::vector<Entry> res(numEntries);
389  int k = 0;
390  for (unsigned i = 0; i < numEntries; i++) {
391  res[k++] = Entry(i / 100, i % 100);
392  }
393  std::random_device rd;
394  std::mt19937 generator(rd());
395 
396  shuffle(res.begin(), res.end(), generator);
397  return res;
398 }

References i, and k.

Referenced by TEST().

◆ now()

time_point souffle::test::now ( )

Definition at line 402 of file btree_multiset_test.cpp.

402  {
403  return std::chrono::high_resolution_clock::now();
404 }

Referenced by time().

◆ TEST() [1/78]

souffle::test::TEST ( BTreeMultiSet  ,
Basic   
)

Definition at line 56 of file btree_multiset_test.cpp.

56  {
57  const bool DEBUG = false;
58 
59  using test_set = btree_multiset<int, detail::comparator<int>, std::allocator<int>, 16>;
60 
61  test_set t;
62 
63  EXPECT_EQ(3, test_set::max_keys_per_node);
64 
65  // check initial conditions
66  EXPECT_EQ(0u, t.size());
67  EXPECT_FALSE(t.contains(10));
68  EXPECT_FALSE(t.contains(12));
69  EXPECT_FALSE(t.contains(14));
70  EXPECT_EQ(0, t.getDepth());
71  EXPECT_EQ(0, t.getNumNodes());
72 
73  if (DEBUG) t.printTree();
74 
75  // add an element
76 
77  t.insert(12);
78  if (DEBUG) {
79  t.printTree();
80  std::cout << "\n";
81  }
82 
83  EXPECT_EQ(1u, t.size());
84  EXPECT_FALSE(t.contains(10));
85  EXPECT_TRUE(t.contains(12));
86  EXPECT_FALSE(t.contains(14));
87  EXPECT_EQ(1, t.getDepth());
88  EXPECT_EQ(1, t.getNumNodes());
89 
90  // add a larger element
91 
92  t.insert(14);
93  if (DEBUG) {
94  t.printTree();
95  std::cout << "\n";
96  }
97  EXPECT_EQ(2u, t.size());
98  EXPECT_FALSE(t.contains(10));
99  EXPECT_TRUE(t.contains(12));
100  EXPECT_TRUE(t.contains(14));
101  EXPECT_EQ(1, t.getDepth());
102  EXPECT_EQ(1, t.getNumNodes());
103 
104  // add a smaller element
105 
106  t.insert(10);
107  if (DEBUG) {
108  t.printTree();
109  std::cout << "\n";
110  }
111  EXPECT_EQ(3u, t.size());
112  EXPECT_TRUE(t.contains(10));
113  EXPECT_TRUE(t.contains(12));
114  EXPECT_TRUE(t.contains(14));
115  EXPECT_EQ(1, t.getDepth());
116  EXPECT_EQ(1, t.getNumNodes());
117 
118  // cause a split
119  t.insert(11);
120  if (DEBUG) {
121  t.printTree();
122  std::cout << "\n";
123  }
124  EXPECT_EQ(4u, t.size());
125  EXPECT_TRUE(t.contains(10));
126  EXPECT_TRUE(t.contains(11));
127  EXPECT_TRUE(t.contains(12));
128  EXPECT_TRUE(t.contains(14));
129 
130  if (DEBUG) {
131  t.printTree();
132  std::cout << "\n";
133  }
134 
135  t.insert(12);
136  EXPECT_EQ(5u, t.size());
137  t.insert(12);
138  EXPECT_EQ(6u, t.size());
139  if (DEBUG) {
140  t.printTree();
141  std::cout << "\n";
142  }
143 
144  t.insert(15);
145  if (DEBUG) {
146  t.printTree();
147  std::cout << "\n";
148  }
149 
150  t.insert(16);
151  if (DEBUG) {
152  t.printTree();
153  std::cout << "\n";
154  }
155 }

References DEBUG, EXPECT_EQ, EXPECT_FALSE, and EXPECT_TRUE.

◆ TEST() [2/78]

souffle::test::TEST ( BTreeMultiSet  ,
BoundaryEmpty   
)

Definition at line 323 of file btree_multiset_test.cpp.

323  {
324  using test_set = btree_multiset<int, detail::comparator<int>, std::allocator<int>, 16>;
325 
326  test_set t;
327 
328  EXPECT_EQ(t.end(), t.lower_bound(5));
329  EXPECT_EQ(t.end(), t.upper_bound(5));
330 
331  t.insert(4);
332 
333  EXPECT_EQ(t.lower_bound(3), t.upper_bound(3));
334  EXPECT_EQ(t.lower_bound(5), t.upper_bound(5));
335 
336  t.insert(6);
337  EXPECT_EQ(t.lower_bound(3), t.upper_bound(3));
338  EXPECT_EQ(t.lower_bound(5), t.upper_bound(5));
339 
340  t.insert(5);
341 
342  EXPECT_EQ(t.lower_bound(3), t.upper_bound(3));
343  EXPECT_NE(t.lower_bound(5), t.upper_bound(5));
344 }

References EXPECT_EQ, and EXPECT_NE.

◆ TEST() [3/78]

souffle::test::TEST ( BTreeMultiSet  ,
BoundaryTest   
)

Definition at line 279 of file btree_multiset_test.cpp.

279  {
280  using test_set = btree_multiset<int, detail::comparator<int>, std::allocator<int>, 16>;
281 
282  test_set t;
283 
284  for (int i = 0; i < 10; i++) {
285  t.insert(i);
286  }
287 
288  // t.printTree();
289 
290  auto a = t.lower_bound(5);
291  EXPECT_EQ(5, *a);
292 
293  auto b = t.upper_bound(5);
294  EXPECT_EQ(6, *b);
295 
296  // add duplicates
297 
298  t.insert(5);
299  t.insert(5);
300  t.insert(5);
301 
302  // t.printTree(); std::cout << "\n";
303 
304  // test again ..
305  a = t.lower_bound(5);
306  EXPECT_EQ(5, *a);
307 
308  b = t.upper_bound(5);
309  EXPECT_EQ(6, *b);
310 
311  // check the distance
312  EXPECT_EQ(5, *a);
313  ++a;
314  EXPECT_EQ(5, *a);
315  ++a;
316  EXPECT_EQ(5, *a);
317  ++a;
318  EXPECT_EQ(5, *a);
319  ++a;
320  EXPECT_EQ(6, *a);
321 }

References b, EXPECT_EQ, i, and souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::insert().

Here is the call graph for this function:

◆ TEST() [4/78]

souffle::test::TEST ( BTreeMultiSet  ,
Clear   
)

Definition at line 368 of file btree_multiset_test.cpp.

368  {
369  using test_set = btree_multiset<int, detail::comparator<int>, std::allocator<int>, 16>;
370 
371  test_set t;
372 
373  EXPECT_TRUE(t.empty());
374 
375  t.insert(5);
376 
377  EXPECT_FALSE(t.empty());
378  t.clear();
379  EXPECT_TRUE(t.empty());
380 
381  t.clear();
382  EXPECT_TRUE(t.empty());
383 }

References EXPECT_FALSE, and EXPECT_TRUE.

◆ TEST() [5/78]

souffle::test::TEST ( BTreeMultiSet  ,
Decremental   
)

Definition at line 183 of file btree_multiset_test.cpp.

183  {
184  using test_set = btree_multiset<int, detail::comparator<int>, std::allocator<int>, 16>;
185  test_set t;
186  int N = 1000;
187  for (int i = N; i >= 0; i--) {
188  t.insert(i);
189  for (int j = 0; j < N; j++) {
190  EXPECT_EQ(j >= i, t.contains(j)) << "i=" << i << ", j=" << j;
191  }
192  }
193 }

References EXPECT_EQ, i, souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::insert(), and j.

Here is the call graph for this function:

◆ TEST() [6/78]

souffle::test::TEST ( BTreeMultiSet  ,
Duplicates   
)

Definition at line 157 of file btree_multiset_test.cpp.

157  {
158  using test_set = btree_multiset<int, detail::comparator<int>, std::allocator<int>, 16>;
159  test_set t;
160  for (int i = 0; i < 10; i++) {
161  t.insert(0);
162  }
163  EXPECT_EQ(10, t.size());
164  std::vector<int> data(t.begin(), t.end());
165  EXPECT_EQ(10, data.size());
166  for (int i = 0; i < 10; i++) {
167  EXPECT_EQ(0, data[i]);
168  }
169 }

References TCB_SPAN_NAMESPACE_NAME::detail::data(), EXPECT_EQ, i, and souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::insert().

Here is the call graph for this function:

◆ TEST() [7/78]

souffle::test::TEST ( BTreeMultiSet  ,
Incremental   
)

Definition at line 171 of file btree_multiset_test.cpp.

171  {
172  using test_set = btree_multiset<int, detail::comparator<int>, std::allocator<int>, 16>;
173  test_set t;
174  int N = 1000;
175  for (int i = 0; i < N; i++) {
176  t.insert(i);
177  for (int j = 0; j < N; j++) {
178  EXPECT_EQ(j <= i, t.contains(j)) << "i=" << i << ", j=" << j;
179  }
180  }
181 }

References EXPECT_EQ, i, souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::insert(), and j.

Here is the call graph for this function:

◆ TEST() [8/78]

souffle::test::TEST ( BTreeMultiSet  ,
IteratorBasic   
)

Definition at line 227 of file btree_multiset_test.cpp.

227  {
228  using test_set = btree_multiset<int, detail::comparator<int>, std::allocator<int>, 16>;
229  test_set t;
230 
231  for (int i = 0; i < 10; i++) {
232  t.insert(i);
233  }
234 
235  // t.printTree();
236 
237  auto it = t.begin();
238  auto e = t.end();
239 
240  EXPECT_NE(it, e);
241 
242  int last = -1;
243  for (int i : t) {
244  EXPECT_EQ(last + 1, i);
245  last = i;
246  }
247  EXPECT_EQ(last, 9);
248 }

References e, EXPECT_EQ, EXPECT_NE, i, and souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::insert().

Here is the call graph for this function:

◆ TEST() [9/78]

souffle::test::TEST ( BTreeMultiSet  ,
IteratorEmpty   
)

Definition at line 220 of file btree_multiset_test.cpp.

220  {
221  using test_set = btree_multiset<int, detail::comparator<int>, std::allocator<int>, 16>;
222  test_set t;
223 
224  EXPECT_EQ(t.begin(), t.end());
225 }

References EXPECT_EQ.

◆ TEST() [10/78]

souffle::test::TEST ( BTreeMultiSet  ,
IteratorStress   
)

Definition at line 250 of file btree_multiset_test.cpp.

250  {
251  using test_set = btree_multiset<int, detail::comparator<int>, std::allocator<int>, 16>;
252 
253  test_set t;
254 
255  int N = 1000;
256 
257  std::vector<int> data;
258  for (int i = 0; i < N; i++) {
259  data.push_back(i);
260  }
261  std::random_device rd;
262  std::mt19937 generator(rd());
263 
264  shuffle(data.begin(), data.end(), generator);
265 
266  for (int i = 0; i < N; i++) {
267  EXPECT_EQ((size_t)i, t.size());
268 
269  int last = -1;
270  for (int i : t) {
271  EXPECT_LT(last, i);
272  last = i;
273  }
274 
275  t.insert(data[i]);
276  }
277 }

References TCB_SPAN_NAMESPACE_NAME::detail::data(), EXPECT_EQ, EXPECT_LT, and i.

Here is the call graph for this function:

◆ TEST() [11/78]

souffle::test::TEST ( BTreeMultiSet  ,
Load   
)

Definition at line 346 of file btree_multiset_test.cpp.

346  {
347  using test_set = btree_multiset<int, detail::comparator<int>, std::allocator<int>, 16>;
348 
349  for (int N = 0; N < 100; N++) {
350  // generate some ordered data
351  std::vector<int> data;
352 
353  for (int i = 0; i < N; i++) {
354  data.push_back(i);
355  }
356  auto t = test_set::load(data.begin(), data.end());
357  EXPECT_EQ(data.size(), t.size());
358  EXPECT_TRUE(t.check());
359  int last = -1;
360  for (int c : t) {
361  EXPECT_EQ(last + 1, c);
362  last = c;
363  }
364  EXPECT_EQ(last, N - 1);
365  }
366 }

References TCB_SPAN_NAMESPACE_NAME::detail::data(), EXPECT_EQ, EXPECT_TRUE, and i.

Here is the call graph for this function:

◆ TEST() [12/78]

souffle::test::TEST ( BTreeMultiSet  ,
Shuffled   
)

Definition at line 195 of file btree_multiset_test.cpp.

195  {
196  using test_set = btree_multiset<int, detail::comparator<int>, std::allocator<int>, 16>;
197 
198  test_set t;
199 
200  int N = 10000;
201 
202  std::vector<int> data;
203  for (int i = 0; i < N; i++) {
204  data.push_back(i);
205  }
206  std::random_device rd;
207  std::mt19937 generator(rd());
208 
209  shuffle(data.begin(), data.end(), generator);
210 
211  for (int i = 0; i < N; i++) {
212  t.insert(data[i]);
213  }
214 
215  for (int i = 0; i < N; i++) {
216  EXPECT_TRUE(t.contains(i)) << "i=" << i;
217  }
218 }

References TCB_SPAN_NAMESPACE_NAME::detail::data(), EXPECT_TRUE, and i.

Here is the call graph for this function:

◆ TEST() [13/78]

souffle::test::TEST ( BTreeSet  ,
Basic   
)

Definition at line 60 of file btree_set_test.cpp.

60  {
61  const bool DEBUG = false;
62 
63  using test_set = btree_set<int, detail::comparator<int>, std::allocator<int>, 16>;
64 
65  test_set t;
66 
67  EXPECT_EQ(3, test_set::max_keys_per_node);
68 
69  // check initial conditions
70  EXPECT_EQ(0u, t.size());
71  EXPECT_FALSE(t.contains(10));
72  EXPECT_FALSE(t.contains(12));
73  EXPECT_FALSE(t.contains(14));
74  EXPECT_EQ(0, t.getDepth());
75  EXPECT_EQ(0, t.getNumNodes());
76 
77  if (DEBUG) t.printTree();
78 
79  // add an element
80 
81  t.insert(12);
82  if (DEBUG) {
83  t.printTree();
84  std::cout << "\n";
85  }
86 
87  EXPECT_EQ(1u, t.size());
88  EXPECT_FALSE(t.contains(10));
89  EXPECT_TRUE(t.contains(12));
90  EXPECT_FALSE(t.contains(14));
91  EXPECT_EQ(1, t.getDepth());
92  EXPECT_EQ(1, t.getNumNodes());
93 
94  // add a larger element
95 
96  t.insert(14);
97  if (DEBUG) {
98  t.printTree();
99  std::cout << "\n";
100  }
101  EXPECT_EQ(2u, t.size());
102  EXPECT_FALSE(t.contains(10));
103  EXPECT_TRUE(t.contains(12));
104  EXPECT_TRUE(t.contains(14));
105  EXPECT_EQ(1, t.getDepth());
106  EXPECT_EQ(1, t.getNumNodes());
107 
108  // add a smaller element
109 
110  t.insert(10);
111  if (DEBUG) {
112  t.printTree();
113  std::cout << "\n";
114  }
115  EXPECT_EQ(3u, t.size());
116  EXPECT_TRUE(t.contains(10));
117  EXPECT_TRUE(t.contains(12));
118  EXPECT_TRUE(t.contains(14));
119  EXPECT_EQ(1, t.getDepth());
120  EXPECT_EQ(1, t.getNumNodes());
121 
122  // cause a split
123  t.insert(11);
124  if (DEBUG) {
125  t.printTree();
126  std::cout << "\n";
127  }
128  EXPECT_EQ(4u, t.size());
129  EXPECT_TRUE(t.contains(10));
130  EXPECT_TRUE(t.contains(11));
131  EXPECT_TRUE(t.contains(12));
132  EXPECT_TRUE(t.contains(14));
133 
134  if (DEBUG) {
135  t.printTree();
136  std::cout << "\n";
137  }
138 
139  EXPECT_EQ(4u, t.size());
140  t.insert(12);
141  EXPECT_EQ(4u, t.size());
142  t.insert(12);
143  EXPECT_EQ(4u, t.size());
144 
145  t.insert(10);
146  EXPECT_EQ(4u, t.size());
147 
148  if (DEBUG) {
149  t.printTree();
150  std::cout << "\n";
151  }
152 
153  t.insert(15);
154  EXPECT_EQ(5u, t.size());
155  EXPECT_EQ(2, t.getDepth());
156  EXPECT_EQ(3, t.getNumNodes());
157  if (DEBUG) {
158  t.printTree();
159  std::cout << "\n";
160  }
161 
162  t.insert(16);
163  EXPECT_EQ(6u, t.size());
164  if (DEBUG) {
165  t.printTree();
166  std::cout << "\n";
167  }
168 }

References DEBUG, EXPECT_EQ, EXPECT_FALSE, and EXPECT_TRUE.

◆ TEST() [14/78]

souffle::test::TEST ( BTreeSet  ,
BoundaryEmpty   
)

Definition at line 438 of file btree_set_test.cpp.

438  {
439  using test_set = btree_set<int, detail::comparator<int>, std::allocator<int>, 16>;
440 
441  test_set t;
442 
443  EXPECT_EQ(t.end(), t.lower_bound(5));
444  EXPECT_EQ(t.end(), t.upper_bound(5));
445 
446  t.insert(4);
447 
448  EXPECT_EQ(t.lower_bound(3), t.upper_bound(3));
449  EXPECT_EQ(t.lower_bound(5), t.upper_bound(5));
450 
451  t.insert(6);
452  EXPECT_EQ(t.lower_bound(3), t.upper_bound(3));
453  EXPECT_EQ(t.lower_bound(5), t.upper_bound(5));
454 
455  t.insert(5);
456 
457  EXPECT_EQ(t.lower_bound(3), t.upper_bound(3));
458  EXPECT_NE(t.lower_bound(5), t.upper_bound(5));
459 }

References EXPECT_EQ, and EXPECT_NE.

◆ TEST() [15/78]

souffle::test::TEST ( BTreeSet  ,
BoundaryTest   
)

Definition at line 402 of file btree_set_test.cpp.

402  {
403  using test_set = btree_set<int, detail::comparator<int>, std::allocator<int>, 16>;
404 
405  test_set t;
406 
407  for (int i = 0; i < 10; i++) {
408  t.insert(i);
409  }
410 
411  // t.printTree();
412 
413  auto a = t.lower_bound(5);
414  EXPECT_EQ(5, *a);
415 
416  auto b = t.upper_bound(5);
417  EXPECT_EQ(6, *b);
418 
419  // add duplicates
420 
421  t.insert(5);
422  t.insert(5);
423  t.insert(5);
424 
425  // t.printTree(); std::cout << "\n";
426 
427  // test again ..
428  a = t.lower_bound(5);
429  EXPECT_EQ(5, *a);
430 
431  b = t.upper_bound(5);
432  EXPECT_EQ(6, *b);
433 
434  // check the distance
435  EXPECT_EQ(++a, b);
436 }

References b, EXPECT_EQ, i, and souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::insert().

Here is the call graph for this function:

◆ TEST() [16/78]

souffle::test::TEST ( BTreeSet  ,
ChunkSplit   
)

Definition at line 504 of file btree_set_test.cpp.

504  {
505  using test_set = btree_set<int, detail::comparator<int>, std::allocator<int>, 16>;
506 
507  test_set t;
508 
509  // TODO: test for empty
510 
511  for (int i = 0; i < 100; i++) {
512  t.insert(i);
513  }
514 
515  // split chunks
516  auto chunks = t.getChunks(20);
517 
518  // EXPECT_EQ(20, chunks.size());
519 
520  for (const auto& cur : chunks) {
521  for (int i : cur) {
522  std::cout << i << ", ";
523  }
524  std::cout << "\n";
525  }
526 
527  int last = -1;
528  for (const auto& chunk : chunks) {
529  for (auto current : chunk) {
530  EXPECT_EQ(last + 1, current);
531  last = current;
532  }
533  }
534 }

References EXPECT_EQ, i, and souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::insert().

Here is the call graph for this function:

◆ TEST() [17/78]

souffle::test::TEST ( BTreeSet  ,
ChunkSplitStress   
)

Definition at line 536 of file btree_set_test.cpp.

536  {
537  using test_set = btree_set<int, detail::comparator<int>, std::allocator<int>, 16>;
538 
539  for (int i = 0; i < 1000; i++) {
540  // generate random sequence
541  std::vector<int> data;
542  for (int j = 0; j < i; j++) {
543  data.push_back(j);
544  }
545  std::random_device rd;
546  std::mt19937 generator(rd());
547 
548  shuffle(data.begin(), data.end(), generator);
549 
550  // fill tree
551  test_set t;
552 
553  for (int x : data) {
554  t.insert(x);
555  }
556 
557  for (int j = 1; j < 100; j++) {
558  auto chunks = t.getChunks(j);
559  // EXPECT_LT(chunks.size(), j * 2);
560 
561  if (chunks.empty()) continue;
562 
563  // check covered range
564  EXPECT_EQ(0, *chunks.front().begin());
565 
566  int last = -1;
567  for (const auto& chunk : chunks) {
568  for (auto current : chunk) {
569  EXPECT_EQ(last + 1, current);
570  last = current;
571  }
572  }
573 
574  EXPECT_EQ(i - 1, last);
575  }
576  }
577 }

References TCB_SPAN_NAMESPACE_NAME::detail::data(), EXPECT_EQ, i, and j.

Here is the call graph for this function:

◆ TEST() [18/78]

souffle::test::TEST ( BTreeSet  ,
Clear   
)

Definition at line 487 of file btree_set_test.cpp.

487  {
488  using test_set = btree_set<int, detail::comparator<int>, std::allocator<int>, 16>;
489 
490  test_set t;
491 
492  EXPECT_TRUE(t.empty());
493 
494  t.insert(5);
495 
496  EXPECT_FALSE(t.empty());
497  t.clear();
498  EXPECT_TRUE(t.empty());
499 
500  t.clear();
501  EXPECT_TRUE(t.empty());
502 }

References EXPECT_FALSE, and EXPECT_TRUE.

◆ TEST() [19/78]

souffle::test::TEST ( BTreeSet  ,
Copy   
)

Definition at line 262 of file btree_set_test.cpp.

262  {
263  using test_set = btree_set<int>;
264 
265  test_set t;
266 
267  int N = 100000;
268 
269  std::vector<int> data;
270  for (int i = 0; i < N; i++) {
271  data.push_back(i);
272  }
273  std::random_device rd;
274  std::mt19937 generator(rd());
275 
276  shuffle(data.begin(), data.end(), generator);
277 
278  for (int i = 0; i < N; i++) {
279  t.insert(data[i]);
280  }
281 
282  EXPECT_EQ((size_t)N, t.size());
283 
284  for (int i = 0; i < N; i++) {
285  EXPECT_TRUE(t.find(i) != t.end()) << "i=" << i;
286  }
287 
288  test_set t2;
289  EXPECT_EQ((size_t)N, t.size());
290  EXPECT_EQ(0, t2.size());
291 
292  t2 = t;
293 
294  EXPECT_EQ((size_t)N, t.size());
295  EXPECT_EQ((size_t)N, t2.size());
296 
297  for (int i = 0; i < N; i++) {
298  EXPECT_TRUE(t.find(i) != t.end()) << "i=" << i;
299  }
300  for (int i = 0; i < N; i++) {
301  EXPECT_TRUE(t2.find(i) != t2.end()) << "i=" << i;
302  }
303 
304  EXPECT_FALSE(t.find(N + 1) != t.end());
305  EXPECT_FALSE(t2.find(N + 1) != t2.end());
306  t2.insert(N + 1);
307  EXPECT_FALSE(t.find(N + 1) != t.end());
308  EXPECT_TRUE(t2.find(N + 1) != t2.end());
309 
310  for (int i = 0; i < N; i++) {
311  EXPECT_NE(&*t.find(i), &*t2.find(i)) << "i=" << i;
312  }
313 }

References TCB_SPAN_NAMESPACE_NAME::detail::data(), EXPECT_EQ, EXPECT_FALSE, EXPECT_NE, EXPECT_TRUE, and i.

Here is the call graph for this function:

◆ TEST() [20/78]

souffle::test::TEST ( BTreeSet  ,
Decremental   
)

Definition at line 212 of file btree_set_test.cpp.

212  {
213  using test_set = btree_set<int, detail::comparator<int>, std::allocator<int>, 16>;
214 
215  test_set t;
216 
217  int N = 1000;
218 
219  for (int i = N; i >= 0; i--) {
220  // std::cout << "\nBefore:\n";
221  // t.printTree();
222  // std::cout << "\n";
223  t.insert(i);
224  // std::cout << "\nAfter:\n";
225  // t.printTree();
226  // std::cout << "\n";
227  // std::cout << "\n\n";
228 
229  for (int j = 0; j < N; j++) {
230  EXPECT_EQ(j >= i, t.contains(j)) << "i=" << i << ", j=" << j;
231  }
232  }
233 }

References EXPECT_EQ, i, souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::insert(), and j.

Here is the call graph for this function:

◆ TEST() [21/78]

souffle::test::TEST ( BTreeSet  ,
Duplicates   
)

Definition at line 170 of file btree_set_test.cpp.

170  {
171  using test_set = btree_set<int, detail::comparator<int>, std::allocator<int>, 16>;
172 
173  test_set t;
174 
175  for (int i = 0; i < 10; i++) {
176  t.insert(0);
177  }
178 
179  EXPECT_EQ(1, t.size());
180 
181  EXPECT_EQ(0, *t.begin());
182 
183  // t.printTree();
184 }

References EXPECT_EQ, i, and souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::insert().

Here is the call graph for this function:

◆ TEST() [22/78]

souffle::test::TEST ( BTreeSet  ,
Incremental   
)

Definition at line 186 of file btree_set_test.cpp.

186  {
187  using test_set = btree_set<int, detail::comparator<int>, std::allocator<int>, 16>;
188 
189  test_set t;
190 
191  int N = 1000;
192 
193  for (int i = 0; i < N; i++) {
194  // std::cout << "\nBefore:\n";
195  // t.printTree();
196  // std::cout << "\n";
197  t.insert(i);
198  // std::cout << "\nAfter:\n";
199  // std::cout << "\n";
200  // t.printTree();
201  // std::cout << "\n";
202  // std::cout << "\n\n";
203 
204  for (int j = 0; j < N; j++) {
205  EXPECT_EQ(j <= i, t.contains(j)) << "i=" << i << ", j=" << j;
206  }
207  }
208 
209  t.printStats();
210 }

References EXPECT_EQ, i, souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::insert(), and j.

Here is the call graph for this function:

◆ TEST() [23/78]

souffle::test::TEST ( BTreeSet  ,
IteratorBasic   
)

Definition at line 345 of file btree_set_test.cpp.

345  {
346  using test_set = btree_set<int, detail::comparator<int>, std::allocator<int>, 16>;
347  test_set t;
348 
349  int N = 10;
350 
351  for (int i = 0; i <= N; i++) {
352  t.insert(i);
353  }
354 
355  // t.printTree();
356 
357  auto it = t.begin();
358  auto e = t.end();
359 
360  EXPECT_NE(it, e);
361 
362  int last = -1;
363  for (int i : t) {
364  EXPECT_EQ(last + 1, i);
365  last = i;
366  }
367  EXPECT_EQ(last, N);
368 }

References e, EXPECT_EQ, EXPECT_NE, i, and souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::insert().

Here is the call graph for this function:

◆ TEST() [24/78]

souffle::test::TEST ( BTreeSet  ,
IteratorEmpty   
)

Definition at line 338 of file btree_set_test.cpp.

338  {
339  using test_set = btree_set<int, detail::comparator<int>, std::allocator<int>, 16>;
340  test_set t;
341 
342  EXPECT_EQ(t.begin(), t.end());
343 }

References EXPECT_EQ.

◆ TEST() [25/78]

souffle::test::TEST ( BTreeSet  ,
IteratorStress   
)

Definition at line 370 of file btree_set_test.cpp.

370  {
371  using test_set = btree_set<int, detail::comparator<int>, std::allocator<int>, 16>;
372 
373  test_set t;
374 
375  int N = 1000;
376 
377  std::vector<int> data;
378  for (int i = 0; i < N; i++) {
379  data.push_back(i);
380  }
381  std::random_device rd;
382  std::mt19937 generator(rd());
383 
384  shuffle(data.begin(), data.end(), generator);
385 
386  int max = -1;
387  for (int i = 0; i < N; i++) {
388  EXPECT_EQ((size_t)i, t.size());
389 
390  int last = -1;
391  for (int i : t) {
392  EXPECT_LT(last, i);
393  last = i;
394  }
395  EXPECT_EQ(last, max);
396 
397  t.insert(data[i]);
398  max = (data[i] > max) ? data[i] : max;
399  }
400 }

References TCB_SPAN_NAMESPACE_NAME::detail::data(), EXPECT_EQ, EXPECT_LT, and i.

Here is the call graph for this function:

◆ TEST() [26/78]

souffle::test::TEST ( BTreeSet  ,
Load   
)

Definition at line 461 of file btree_set_test.cpp.

461  {
462  using test_set = btree_set<int, detail::comparator<int>, std::allocator<int>, 16>;
463 
464  for (int N = 0; N < 100; N++) {
465  // generate some ordered data
466  std::vector<int> data;
467 
468  for (int i = 0; i < N; i++) {
469  data.push_back(i);
470  }
471 
472  auto t = test_set::load(data.begin(), data.end());
473  // t.printTree();
474 
475  EXPECT_EQ(data.size(), t.size());
476  EXPECT_TRUE(t.check());
477 
478  int last = -1;
479  for (int c : t) {
480  EXPECT_EQ(last + 1, c);
481  last = c;
482  }
483  EXPECT_EQ(last, N - 1);
484  }
485 }

References TCB_SPAN_NAMESPACE_NAME::detail::data(), EXPECT_EQ, EXPECT_TRUE, and i.

Here is the call graph for this function:

◆ TEST() [27/78]

souffle::test::TEST ( BTreeSet  ,
Merge   
)

Definition at line 315 of file btree_set_test.cpp.

315  {
316  using test_set = btree_set<int>;
317 
318  test_set a;
319  test_set b;
320 
321  a.insert(1);
322  a.insert(2);
323  a.insert(3);
324  a.insert(4);
325 
326  b.insert(2);
327  b.insert(4);
328  b.insert(6);
329 
330  EXPECT_NE(a, b);
331 
332  test_set c = a;
333  test_set d = b;
334 
335  EXPECT_NE(c, d);
336 }

References b, d, and EXPECT_NE.

◆ TEST() [28/78]

souffle::test::TEST ( BTreeSet  ,
Parallel   
)

Definition at line 731 of file btree_set_test.cpp.

731  {
732  // const int N = 600000000;
733  // const int N = 100000;
734  // const int N = 10000;
735  const int N = 1000;
736  // const int N = 300;
737  // const int N = 100;
738 
739  // get a unordered list of test data
740  using entry_t = int;
741  std::vector<entry_t> list;
742  btree_set<entry_t> filter;
743 
744  for (int i = 0; i < N; i++) {
745  list.push_back(i);
746  }
747 
748  // the number of times duplicates show up in the input set
749  for (int dup = 1; dup < 4; dup++) {
750  // now duplicate this list
751  std::vector<entry_t> full;
752  for (int i = 0; i < dup; i++) {
753  for (const auto& cur : list) {
754  full.push_back(cur);
755  }
756  }
757 
758  // shuffle data
759  std::random_device rd;
760  std::mt19937 generator(rd());
761 
762  std::shuffle(full.begin(), full.end(), generator);
763 
764  // now insert all those values into a new set - in parallel
765  btree_set<entry_t> res;
766 #pragma omp parallel for // schedule(static,1)
767  for (auto it = full.begin(); it < full.end(); ++it) {
768  res.insert(*it);
769  }
770 
771  EXPECT_TRUE(res.check());
772 
773  // check resulting values
774  EXPECT_EQ(N, res.size());
775 
776  std::set<entry_t> should(full.begin(), full.end());
777  std::set<entry_t> is(res.begin(), res.end());
778 
779  for (const auto& cur : should) {
780  EXPECT_TRUE(res.contains(cur)) << "Missing: " << cur << "\n";
781  }
782 
783  for (const auto& cur : res) {
784  EXPECT_TRUE(should.find(cur) != should.end()) << "Additional: " << cur << "\n"
785  << "Contained: " << res.contains(cur) << "\n";
786  }
787 
788  std::vector<entry_t> extra;
789  for (const auto& cur : is) {
790  if (should.find(cur) == should.end()) extra.push_back(cur);
791  }
792  EXPECT_TRUE(extra.empty()) << "Extra elments: " << extra << "\n";
793 
794  std::vector<entry_t> missing;
795  for (const auto& cur : should) {
796  if (is.find(cur) == is.end()) missing.push_back(cur);
797  }
798  EXPECT_TRUE(missing.empty()) << "Missing elments: " << missing << "\n";
799  // << "All Elements: " << should << "\n";
800 
801  EXPECT_EQ(N, should.size());
802  EXPECT_EQ(N, is.size());
803  EXPECT_EQ(should, is);
804  }
805 }

References souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, 256, typename souffle::detail::default_strategy< Key >::type, true, detail::comparator< Key >, souffle::detail::updater< Key > >::begin(), souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, 256, typename souffle::detail::default_strategy< Key >::type, true, detail::comparator< Key >, souffle::detail::updater< Key > >::check(), souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, 256, typename souffle::detail::default_strategy< Key >::type, true, detail::comparator< Key >, souffle::detail::updater< Key > >::contains(), souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, 256, typename souffle::detail::default_strategy< Key >::type, true, detail::comparator< Key >, souffle::detail::updater< Key > >::end(), EXPECT_EQ, EXPECT_TRUE, souffle::filter(), i, souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, 256, typename souffle::detail::default_strategy< Key >::type, true, detail::comparator< Key >, souffle::detail::updater< Key > >::insert(), and souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, 256, typename souffle::detail::default_strategy< Key >::type, true, detail::comparator< Key >, souffle::detail::updater< Key > >::size().

Here is the call graph for this function:

◆ TEST() [29/78]

souffle::test::TEST ( BTreeSet  ,
Shuffled   
)

Definition at line 235 of file btree_set_test.cpp.

235  {
236  using test_set = btree_set<int, detail::comparator<int>, std::allocator<int>, 16>;
237 
238  test_set t;
239 
240  int N = 10000;
241 
242  std::vector<int> data;
243  for (int i = 0; i < N; i++) {
244  data.push_back(i);
245  }
246  std::random_device rd;
247  std::mt19937 generator(rd());
248 
249  shuffle(data.begin(), data.end(), generator);
250 
251  for (int i = 0; i < N; i++) {
252  t.insert(data[i]);
253  }
254 
255  // t.printTree();
256 
257  for (int i = 0; i < N; i++) {
258  EXPECT_TRUE(t.contains(i)) << "i=" << i;
259  }
260 }

References TCB_SPAN_NAMESPACE_NAME::detail::data(), EXPECT_TRUE, and i.

Here is the call graph for this function:

◆ TEST() [30/78]

souffle::test::TEST ( DjTest  ,
Clear   
)

Definition at line 329 of file eqrel_datastructure_test.cpp.

331  {
332  // insert, union, and stuff in parallel, then check things are in the valid sets
333 
334  souffle::DisjointSet ds;
335  constexpr size_t N = 10000;
336 
337 #pragma omp parallel for
338  for (size_t i = 0; i < N; ++i) {
339  ds.makeNode();
340  }
341  // check we didn't miss any
342  EXPECT_EQ(ds.size(), N);

References EXPECT_EQ, souffle::DisjointSet::findNode(), i, souffle::DisjointSet::makeNode(), souffle::DisjointSet::size(), and souffle::DisjointSet::unionNodes().

Here is the call graph for this function:

◆ TEST() [31/78]

souffle::test::TEST ( DjTest  ,
MakeNode   
)

Definition at line 277 of file eqrel_datastructure_test.cpp.

281  {
282  // check whether the unioning works to see if the elements are properly in the same set
283  souffle::DisjointSet ds;
284 
285  parent_t n1 = DisjointSet::b2p(ds.makeNode());
286  parent_t n2 = DisjointSet::b2p(ds.makeNode());
287  parent_t n3 = DisjointSet::b2p(ds.makeNode());
288  parent_t n4 = DisjointSet::b2p(ds.makeNode());
289  parent_t n5 = DisjointSet::b2p(ds.makeNode());
290  EXPECT_EQ(ds.size(), 5);
291 
292  // test running same set doesn't accidentally union them
293  EXPECT_FALSE(ds.sameSet(n1, n2));

◆ TEST() [32/78]

souffle::test::TEST ( DjTest  ,
Scoping   
)

The underlying Disjoint Set (essentially Anderson '91 Find-Union, but dynamic)

Definition at line 273 of file eqrel_datastructure_test.cpp.

◆ TEST() [33/78]

souffle::test::TEST ( DjTest  ,
TestUnion   
)

Definition at line 295 of file eqrel_datastructure_test.cpp.

315  {
316  souffle::DisjointSet ds;
317 
318  ds.clear();
319  EXPECT_EQ(ds.size(), 0);
320 
321  // get ready 2 double free y'all
322  for (size_t i = 0; i < 10000; ++i) {
323  ds.makeNode();
324  }
325  ds.unionNodes(1, 2);
326  ds.clear();
327  ds.clear();

◆ TEST() [34/78]

souffle::test::TEST ( EqRelTest  ,
Basic   
)

Definition at line 58 of file binary_relation_test.cpp.

68  : br) {
69  ++count;
70  testutil::ignore(x);
71  }
72  EXPECT_EQ(count, br.size());
73 }
74 
75 TEST(EqRelTest, Clear) {
76  EqRel br;
77  br.insert(0, 44);
78  br.insert(0, 1);
79 
80  EXPECT_EQ(9, br.size());
81  size_t count = 0;
82  for (auto x : br) {
83  ++count;
84  testutil::ignore(x);
85  }

◆ TEST() [35/78]

souffle::test::TEST ( EqRelTest  ,
Clear   
)

Definition at line 87 of file binary_relation_test.cpp.

90  : br) {
91  ++count;
92  testutil::ignore(x);
93  }
94  EXPECT_EQ(count, br.size());
95 }
96 
97 TEST(EqRelTest, Duplicates) {
98  EqRel br;
99  // test inserting same pair
100  for (int i = 0; i < 10; ++i) {
101  br.insert(0, 0);
102  }
103  EXPECT_EQ(br.size(), 1);
104 
105  for (int i = 0; i < 10; ++i) {
106  EXPECT_TRUE(br.contains(0, 0));
107  }

◆ TEST() [36/78]

souffle::test::TEST ( EqRelTest  ,
Duplicates   
)

Definition at line 109 of file binary_relation_test.cpp.

121  {
122  // test (a,b) && (b, c) => (a,c) etc
123  EqRel br;
124  br.insert(1, 2);
125  br.insert(2, 3);
126  EXPECT_EQ(br.size(), 9);
127  size_t count = 0;
128  for (auto x : br) {
129  ++count;
130  testutil::ignore(x);
131  }

◆ TEST() [37/78]

souffle::test::TEST ( EqRelTest  ,
Extend   
)

Definition at line 234 of file binary_relation_test.cpp.

281  {
282  // test insertAll isolates data
283  EqRel br;
284 
285  int N = 100;
286 
287  std::vector<int> data;
288  for (int i = 0; i < N; i++) {
289  data.push_back(i);
290  }
291  std::random_device rd;

◆ TEST() [38/78]

souffle::test::TEST ( EqRelTest  ,
IterBasic   
)

Definition at line 371 of file binary_relation_test.cpp.

375  : br) {
376  ++count;
377  testutil::ignore(x);
378  }
379 
380  EXPECT_EQ(count, br.size());
381 }
382 
383 TEST(EqRelTest, IterRange) {
384  // write some tests to use that templated range for different indexes too
385  EqRel br;
386  br.insert(0, 1);
387  br.insert(0, 2);
388  br.insert(0, 3);
389  br.insert(0, 4);
390  br.insert(0, 5);
391  br.insert(0, 6);
392 
393  br.insert(8, 9);

◆ TEST() [39/78]

souffle::test::TEST ( EqRelTest  ,
IterEmpty   
)

Definition at line 361 of file binary_relation_test.cpp.

366  : br) {
367  ++count;
368  testutil::ignore(x);
369  }

References count(), and testutil::ignore().

Here is the call graph for this function:

◆ TEST() [40/78]

souffle::test::TEST ( EqRelTest  ,
IterPartition   
)

Definition at line 494 of file binary_relation_test.cpp.

499  : chunks) {
500  for (auto x : chunk) {
501  values.push_back(std::make_pair(x[0], x[1]));
502  }
503  }
504 
505  EXPECT_EQ(br.size(), values.size());
506 
507  br.clear();
508  values.clear();
509  chunks.clear();
510 
511  // many disjoint sets (note, can't use N, because even & odd numbers don't work the same..)
512  for (RamDomain i = 0; i < 1000; i += 2) {
513  br.insert(i, i + 1);
514  }
515  EXPECT_EQ((size_t)4 * 1000 / 2, br.size());
516 
517  chunks = br.partition(400);
518  for (auto chunk : chunks) {
519  for (auto x : chunk) {
520  values.push_back(std::make_pair(x[0], x[1]));
521  }
522  }
523 
524  EXPECT_EQ(br.size(), values.size());
525 }
526 
527 TEST(EqRelTest, Scaling) {
528  const int N = 100;
529 
530  EqRel br;
531  for (int i = 0; i < N; ++i) {
532  br.insert(i, i);
533  }
534 
535  EXPECT_EQ(N, br.size());
536 }
537 

◆ TEST() [41/78]

souffle::test::TEST ( EqRelTest  ,
IterRange   
)

Definition at line 395 of file binary_relation_test.cpp.

397  {{3, 18293018}});
398 
399  std::vector<size_t> posteriorsCovered;
400  for (auto tup : rangeIt) {
401  posteriorsCovered.push_back(tup[1]);
402  }
403  EXPECT_EQ(posteriorsCovered.size(), 7);
404 
405  // this should be of everything, so doesn't matter the args
406  rangeIt = br.getBoundaries<0>({{332, 888}});
407  posteriorsCovered.clear();
408  for (auto tup : rangeIt) {
409  posteriorsCovered.push_back(tup[1]);
410  }
411  EXPECT_EQ(posteriorsCovered.size(), (7 * 7) + (3 * 3));
412 
413  // and now iterate over two levels (exactly one pretty much)
414  rangeIt = br.getBoundaries<2>({{2, 3}});
415  posteriorsCovered.clear();
416  for (auto tup : rangeIt) {
417  posteriorsCovered.push_back(tup[1]);
418  }
419  EXPECT_EQ(posteriorsCovered.size(), 1);
420  EXPECT_EQ(posteriorsCovered.front(), 3);
421 
422  // and now the same, but for levels 1 and two, stuff that doesn't exist
423  rangeIt = br.getBoundaries<1>({{99, 99}});
424  posteriorsCovered.clear();
425  for (auto tup : rangeIt) {
426  posteriorsCovered.push_back(tup[1]);
427  }
428  EXPECT_EQ(posteriorsCovered.size(), 0);
429 
430  rangeIt = br.getBoundaries<2>({{8, 1}});
431  posteriorsCovered.clear();
432  for (auto tup : rangeIt) {
433  posteriorsCovered.push_back(tup[1]);
434  }
435  EXPECT_EQ(posteriorsCovered.size(), 0);
436 
437  // and now the same for an empty binary relation
438  br.clear();
439  // repeat the same, but notice that we expect the size to be 0 always
440  {
441  auto rangeIt = br.getBoundaries<1>({{3, 18293018}});
442 
443  std::vector<size_t> posteriorsCovered;
444  for (auto tup : rangeIt) {
445  posteriorsCovered.push_back(tup[1]);
446  }
447  EXPECT_EQ(posteriorsCovered.size(), 0);
448 
449  // this should be of everything, so doesn't matter the args
450  rangeIt = br.getBoundaries<0>({{332, 888}});
451  posteriorsCovered.clear();
452  for (auto tup : rangeIt) {
453  posteriorsCovered.push_back(tup[1]);
454  }
455  EXPECT_EQ(posteriorsCovered.size(), 0);
456 
457  // and now iterate over two levels (exactly one pretty much)
458  rangeIt = br.getBoundaries<2>({{2, 3}});
459  posteriorsCovered.clear();
460  for (auto tup : rangeIt) {
461  posteriorsCovered.push_back(tup[1]);
462  }
463  EXPECT_EQ(posteriorsCovered.size(), 0);
464 
465  // and now the same, but for levels 1 and two, stuff that doesn't exist
466  rangeIt = br.getBoundaries<1>({{99, 99}});
467  posteriorsCovered.clear();
468  for (auto tup : rangeIt) {
469  posteriorsCovered.push_back(tup[1]);
470  }
471  EXPECT_EQ(posteriorsCovered.size(), 0);
472 
473  rangeIt = br.getBoundaries<2>({{8, 1}});
474  posteriorsCovered.clear();
475  for (auto tup : rangeIt) {
476  posteriorsCovered.push_back(tup[1]);
477  }
478  EXPECT_EQ(posteriorsCovered.size(), 0);
479  }
480 }
481 
482 TEST(EqRelTest, IterPartition) {
483  // test that the union equals the input
484 
485  // test single set binary rel
486  EqRel br;
487  std::vector<std::pair<RamDomain, RamDomain>> values;
488  RamDomain N = 1000;
489  for (RamDomain i = 0; i < N; ++i) {
490  br.insert(i, i + 1);
491  }
492 

◆ TEST() [42/78]

souffle::test::TEST ( EqRelTest  ,
Merge   
)

Definition at line 293 of file binary_relation_test.cpp.

296  {
297  br.insert(data[i], data[i]);
298  }
299 
300  // also insert a joint pair
301  br.insert(N - 1, N + 1);
302 
303  EXPECT_EQ((size_t)N + 3, br.size());
304 
305  EqRel br2;
306  EXPECT_EQ(0, br2.size());
307 
308  size_t count = 0;
309  for (auto x : br2) {
310  ++count;
311  testutil::ignore(x);
312  }
313  EXPECT_EQ(count, br2.size());
314 
315  br2.insertAll(br);
316  EXPECT_EQ((size_t)N + 3, br2.size());
317  EXPECT_EQ((size_t)N + 3, br.size());
318  count = 0;
319  for (auto x : br2) {
320  ++count;
321  testutil::ignore(x);
322  }
323  EXPECT_EQ(count, br2.size());
324 
325  br.clear();
326  EXPECT_EQ((size_t)N + 3, br2.size());
327  EXPECT_EQ(0, br.size());
328  EXPECT_FALSE(br.begin() != br.end());
329 
330  count = 0;
331  for (auto x : br) {
332  ++count;
333  testutil::ignore(x);
334  }
335  EXPECT_EQ(count, br.size());
336 
337  br2.clear();
338  EXPECT_EQ(0, br2.size());
339  EXPECT_EQ(0, br.size());
340 
341  count = 0;
342  for (auto x : br2) {
343  ++count;
344  testutil::ignore(x);
345  }
346  EXPECT_EQ(count, br2.size());
347 }
348 
349 TEST(EqRelTest, IterEmpty) {
350  // test iterating over an empty binrel fails
351  EqRel br;
352  for (auto x : br) {
353  EXPECT_FALSE(true);
354  testutil::ignore(x);
355  }
356  EXPECT_EQ(0, br.size());
357 }
358 
359 TEST(EqRelTest, IterBasic) {

◆ TEST() [43/78]

souffle::test::TEST ( EqRelTest  ,
PairwiseDecremental   
)

Definition at line 178 of file binary_relation_test.cpp.

182  : br) {
183  ++count;
184  testutil::ignore(x);
185  }
186  EXPECT_EQ(count, br.size());
187 }
188 
189 TEST(EqRelTest, Shuffled) {
190  EqRel br;
191 
192  size_t N = 100;
193  // test inserting data "out of order" keeps isolation
194  std::vector<int> data;
195  for (size_t i = 0; i < N; i++) {
196  data.push_back(i);
197  }
198  std::random_device rd;
199  std::mt19937 generator(rd());

◆ TEST() [44/78]

souffle::test::TEST ( EqRelTest  ,
PairwiseIncremental   
)

Definition at line 156 of file binary_relation_test.cpp.

159  : br) {
160  ++count;
161  testutil::ignore(x);
162  }
163  EXPECT_EQ(count, br.size());
164 }
165 
166 TEST(EqRelTest, PairwiseDecremental) {
167  EqRel br;
168 
169  const size_t N = 100;
170  // test inserting descending pairs still isolates them
171  for (size_t i = N; i > 1; --i) {
172  br.insert(i, i);
173  EXPECT_TRUE(br.contains(i, i));
174  br.insert(i + (N + 1), i);
175  EXPECT_TRUE(br.contains(i, i + (N + 1)));
176  EXPECT_TRUE(br.contains(i + (N + 1), i + (N + 1)));

◆ TEST() [45/78]

souffle::test::TEST ( EqRelTest  ,
Scaling   
)

Definition at line 539 of file binary_relation_test.cpp.

539  {
540  // use OpenMP this time
541 
542  // test with varying number of threads (100000 will likely catch a race condition)
543  const int N = 100000;
544  std::vector<int> data1;
545  std::vector<int> data2;
546  for (int i = 0; i < N; ++i)
547  data1.push_back(i);
548  for (int i = 0; i < N; ++i)

References EXPECT_EQ, i, souffle::EquivalenceRelation< TupleType >::insert(), and souffle::EquivalenceRelation< TupleType >::size().

Here is the call graph for this function:

◆ TEST() [46/78]

souffle::test::TEST ( EqRelTest  ,
Scoping   
)

Definition at line 51 of file binary_relation_test.cpp.

68  : br) {

◆ TEST() [47/78]

souffle::test::TEST ( EqRelTest  ,
Shuffled   
)

Definition at line 201 of file binary_relation_test.cpp.

203  : data) {
204  br.insert(x, x);
205  }
206 
207  for (size_t i = 0; i < N; ++i) {
208  EXPECT_TRUE(br.contains(i, i));
209  }
210 
211  EXPECT_EQ(br.size(), N);
212 
213  // always check the iterator for size too
214  size_t count = 0;
215  for (auto x : br) {
216  ++count;
217  testutil::ignore(x);
218  }
219  EXPECT_EQ(count, br.size());
220 }
221 
222 TEST(EqRelTest, Extend) {
223  // test running extend for a relation
224 
225  // br is {{0,1,2,3,4,5,6}, {8,9}, {44, 70}, {11}}
226  EqRel br;
227 
228  br.insert(0, 1);
229  br.insert(0, 2);
230  br.insert(0, 3);
231  br.insert(0, 4);
232  br.insert(0, 5);

◆ TEST() [48/78]

souffle::test::TEST ( EqRelTest  ,
TransitivityTest   
)

Definition at line 133 of file binary_relation_test.cpp.

144  {
145  EqRel br;
146 
147  const size_t N = 100;
148  // test inserting ascending pairs still isolates them
149  for (size_t i = 1; i < N; ++i) {
150  br.insert(i, i);
151  EXPECT_TRUE(br.contains(i, i));
152  br.insert(i + (N + 1), i);
153  EXPECT_TRUE(br.contains(i, i + (N + 1)));
154  EXPECT_TRUE(br.contains(i + (N + 1), i + (N + 1)));

◆ TEST() [49/78]

souffle::test::TEST ( Graph  ,
Basic   
)

Definition at line 42 of file graph_utils_test.cpp.

111  {1->2,2->3,3->1}", toString(g));
112 }
113 
114 } // end namespace test
115 } // end namespace souffle

◆ TEST() [50/78]

souffle::test::TEST ( LambdaBTreeTest  ,
Insert   
)

Definition at line 523 of file eqrel_datastructure_test.cpp.

524  {55, -1};
525  // inserting the ticketed value
526  EXPECT_EQ(t.insert(toInsert, update_fn), 0);
527 
528  EXPECT_EQ(t.size(), 1);
529 
530  // the second argument should be ignored because its unknown until you fetch it!
531  EXPECT_TRUE(t.contains({55, 1329139123}));
532 
533  // post increment of 0 is zero.
534  EXPECT_EQ(((*t.find({55, 3232})).second), 0);
535 
536  TestPair insert2 = {43, 22};
537  // insert should also return the value
538  EXPECT_EQ(t.insert(insert2, update_fn), 1);
539  EXPECT_TRUE(t.contains({43, 1329139123}));
540  // post increment now should equal 1
541  EXPECT_EQ(((*t.find({43, 3232})).second), 1);
542  EXPECT_EQ(t.size(), 2);
543 
544  // now lets insert something that already exists (the anterior is all that matters)
545  TestPair alreadyExistsPair = {55, 12313123};
546  EXPECT_EQ(t.insert(alreadyExistsPair,
547  [&](TestPair&) {
548  EXPECT_TRUE(false &&
549  "newly inserted function called for an element that already exists!");
550  // some dummy value
551  return 3223;
552  }),
553  0);
554 
555  EXPECT_EQ(t.size(), 2);
556 }
557 
558 #ifdef _OPENMP
559 TEST(LambdaBTreeTest, ParallelInsert) {
560  // check whether doing the above works, but in parallel
561  // we must ensure that duplicate elements inserted in parallel stiiilll should only result in singly
562  // elements inserted
563 
564  constexpr size_t N = 10000;
565  {
566  // the ticket machine that sets the second argument (for now our functor will just postincrent to
567  // assign)
568  std::atomic<size_t> assigner(0);
569  std::function<TestPair::second_type(TestPair&)> update_fn = [&](TestPair& tp) {
570  tp.second = assigner.fetch_add(1);

◆ TEST() [51/78]

souffle::test::TEST ( LambdaBTreeTest  ,
Scoping   
)

The LambdaBTree - essentially a ripoff to the Btree, but allows a function to be called on successful insert.

I just am gonna test a subset of it, because I can argue that BTree already tests the basic stuff

Definition at line 518 of file eqrel_datastructure_test.cpp.

519  {
520  tp.second = assigner.fetch_add(1);
521  return tp.second;

◆ TEST() [52/78]

souffle::test::TEST ( Pack  ,
Tuple   
)

Definition at line 40 of file record_table_test.cpp.

42  {
43  EXPECT_EQ(tuple[i], ptr[i]);
44  }
45 }
46 
47 // Generate random tuples
48 // pack them all
49 // unpack and test for equality
50 TEST(PackUnpack, Tuple) {
51  constexpr size_t tupleSize = 3;

References EXPECT_EQ, and i.

◆ TEST() [53/78]

souffle::test::TEST ( PackUnpack  ,
Tuple   
)

Definition at line 56 of file record_table_test.cpp.

70  {
71  toPack[i] = {{random(), random(), random()}};
72  tupleRef[i] = pack(recordTable, toPack[i]);
73  }
74 
75  // unpack and test
76  for (size_t i = 0; i < NUMBER_OF_TESTS; ++i) {
77  auto unpacked = recordTable.unpack(tupleRef[i], tupleSize);
78  tupleType cmp = {unpacked[0], unpacked[1], unpacked[2]};
79  EXPECT_EQ(toPack[i], cmp);
80  }
81 }
82 
83 // Generate random vectors
84 // pack them all
85 // unpack and test for equality
86 TEST(PackUnpack, Vector) {
87  constexpr size_t vectorSize = 10;

◆ TEST() [54/78]

souffle::test::TEST ( PackUnpack  ,
Vector   
)

Definition at line 92 of file record_table_test.cpp.

98  {
99  toPack[i] = testutil::generateRandomVector<RamDomain>(10);
100  tupleRef[i] = recordTable.pack(toPack[i].data(), vectorSize);
101  std::cerr << "Ref: " << tupleRef[i] << std::endl;
102  }
103 
104  // unpack and test
105  for (size_t i = 0; i < NUMBER_OF_TESTS; ++i) {
106  const RamDomain* unpacked{recordTable.unpack(tupleRef[i], vectorSize)};
107  for (size_t j = 0; j < vectorSize; ++j) {
108  EXPECT_EQ(toPack[i][j], unpacked[j]);
109  }
110  }
111 }
112 
113 } // namespace souffle::test

◆ TEST() [55/78]

souffle::test::TEST ( ParallelUtils  ,
OptimisticReadWriteLock   
)

Definition at line 79 of file parallel_utils_test.cpp.

82  {
83  bool succ = false;
84  do {
85  auto lease = lock.start_read();
86  // nothing to do here ..
87  int x = c;
88  succ = lock.end_read(lease);
89  EXPECT_TRUE((x % 2 == 0) || !succ);
90  } while (!succ);
91  }
92  }
93 
94  EXPECT_EQ(2 * (N / K), c);
95 }
96 } // namespace test
97 } // end namespace souffle

◆ TEST() [56/78]

souffle::test::TEST ( ParallelUtils  ,
ReadWriteLock   
)

Definition at line 55 of file parallel_utils_test.cpp.

57  {
58  lock.start_read();
59  // nothing to do here ..
60  lock.end_read();
61  }
62  }
63 
64  EXPECT_EQ(N / K, c);
65 }
66 
67 TEST(ParallelUtils, OptimisticReadWriteLock) {
68  const int N = 1000000;
69  const int K = 10;
70 
71  OptimisticReadWriteLock lock;
72 
73  volatile int c = 0;
74 
75 #pragma omp parallel for num_threads(4)
76  for (int i = 0; i < N; i++) {
77  if (i % K == 0) { // 10% write probability

◆ TEST() [57/78]

souffle::test::TEST ( ParallelUtils  ,
SpinLock   
)

Definition at line 38 of file parallel_utils_test.cpp.

43  {
44  const int N = 1000000;
45  const int K = 10;
46 
47  ReadWriteLock lock;
48 
49  volatile int c = 0;
50 
51 #pragma omp parallel for num_threads(4)
52  for (int i = 0; i < N; i++) {
53  if (i % K == 0) { // 10% write probability

◆ TEST() [58/78]

souffle::test::TEST ( Performance  ,
Basic   
)

Definition at line 494 of file btree_multiset_test.cpp.

494  {
495  int N = 1 << 18;
496 
497  // get list of tuples to be inserted
498  std::cout << "Generating Test-Data ...\n";
499  std::vector<Entry> in;
500  std::vector<Entry> out;
501  time("generating data", [&]() {
502  auto data = getData(2 * N);
503  for (std::size_t i = 0; i < data.size(); i += 2) {
504  in.push_back(data[i]);
505  out.push_back(data[i + 1]);
506  }
507  });
508 
509  using t1 = std::set<Entry>;
510  checkPerformance(t1, " -- warm up -- ", in, out);
511  using t2 = btree_multiset<Entry, detail::comparator<Entry>, std::allocator<Entry>, 256,
512  detail::linear_search>;
513  checkPerformance(t2, "souffle btree_multiset - 256 - linear", in, out);
514  using t3 = btree_multiset<Entry, detail::comparator<Entry>, std::allocator<Entry>, 256,
515  detail::binary_search>;
516  checkPerformance(t3, "souffle btree_multiset - 256 - binary", in, out);
517 }

References checkPerformance, TCB_SPAN_NAMESPACE_NAME::detail::data(), getData(), i, and time().

Here is the call graph for this function:

◆ TEST() [59/78]

souffle::test::TEST ( Performance  ,
Load   
)

Definition at line 519 of file btree_multiset_test.cpp.

519  {
520  int N = 1 << 20;
521 
522  std::vector<int> data;
523  for (int i = 0; i < N; i++) {
524  data.push_back(i);
525  }
526 
527  // take time for conventional load
528  time("conventional load", [&]() { btree_multiset<int> t(data.begin(), data.end()); });
529 
530  // take time for structured load
531  time("bulk-load", [&]() { auto t = btree_multiset<int>::load(data.begin(), data.end()); });
532 }

References TCB_SPAN_NAMESPACE_NAME::detail::data(), i, souffle::btree_multiset< Key, Comparator, Allocator, blockSize, SearchStrategy, WeakComparator, Updater >::load(), and time().

Here is the call graph for this function:

◆ TEST() [60/78]

souffle::test::TEST ( PiggyTest  ,
Append   
)

Definition at line 118 of file eqrel_datastructure_test.cpp.

119  {
120  pl.append(2);
121  }
122  EXPECT_EQ(pl.size(), N + 3);
123  // make sure that all of our inserties are exacties
124  for (size_t i = 3; i < N + 3; ++i) {
125  EXPECT_EQ(pl.get(i), 2);
126  }
127 }
128 
129 TEST(PiggyTest, ElementCreation) {
130  // test that we can use makeNode() and set the values properly
131  souffle::PiggyList<size_t> pl;
132  pl.get(pl.createNode()) = 99;
133  EXPECT_EQ(pl.size(), 1);
134  EXPECT_EQ(pl.get(0), 99);
135 }
136 
137 TEST(PiggyTest, Iteration) {
138  souffle::PiggyList<size_t> pl;
139  constexpr size_t N = 10000;
140  for (size_t i = 0; i < N; ++i) {
141  pl.append(i);

References souffle::PiggyList< T >::append().

Here is the call graph for this function:

◆ TEST() [61/78]

souffle::test::TEST ( PiggyTest  ,
CopyCtor   
)

Definition at line 163 of file eqrel_datastructure_test.cpp.

168  {
169  // yep, they both finished at the same time
170  if (pl1It == pl.end() && pl2It == pl2.end()) {
171  break;
172  }
173 
174  // uhoh, they didn't both finish at the same time
175  if (pl1It == pl.end() || pl2It == pl2.end()) {
176  EXPECT_FALSE(true && "whoops, looks like the iterators are broken");
177  }
178 
179  EXPECT_EQ(*pl1It, *pl2It);
180 
181  ++pl1It;
182  ++pl2It;
183  }
184 
185  // change contents of pl1 and makesure they don't change in pl2
186  pl.get(2) = 99;
187  EXPECT_EQ(pl.get(2), 99);
188  EXPECT_EQ(pl2.get(2), 2);
189 
190  // check clearing one doesn't invalidate the other
191  pl.clear();
192  EXPECT_EQ(pl.size(), 0);
193  EXPECT_EQ(pl2.size(), N);
194  pl2.clear();
195  EXPECT_EQ(pl.size(), 0);
196  EXPECT_EQ(pl2.size(), 0);
197 }
198 
199 TEST(PiggyTest, DoubleClear) {
200  // err.. prior versions have had the bug where clear caused double-free errors (as we don't set the
201  // container to null) This should *crash* the test-suite if this is the case, but I also try to check the
202  // contents here
203  souffle::PiggyList<size_t> pl;
204  pl.append(3213);
205  pl.append(3213);
206  pl.append(3213);
207  pl.append(3213);
208  EXPECT_EQ(pl.size(), 4);
209  pl.clear();
210  EXPECT_EQ(pl.size(), 0);
211  pl.clear();

◆ TEST() [62/78]

souffle::test::TEST ( PiggyTest  ,
DoubleClear   
)

Definition at line 213 of file eqrel_datastructure_test.cpp.

218  {
219  constexpr size_t N = 10000;
220  souffle::PiggyList<size_t> pl;
221 
222 #pragma omp parallel for
223  for (size_t i = 0; i < N; ++i) {
224  size_t pos = pl.createNode();
225  pl.get(pos) = pos;
226  }
227  EXPECT_EQ(N, pl.size());
228 
229  for (size_t i = 0; i < N; ++i) {

◆ TEST() [63/78]

souffle::test::TEST ( PiggyTest  ,
ElementCreation   
)

Definition at line 143 of file eqrel_datastructure_test.cpp.

144  : pl) {
145  EXPECT_EQ(e, counter++);
146  }
147 }
148 
149 TEST(PiggyTest, CopyCtor) {

References e, and EXPECT_EQ.

◆ TEST() [64/78]

souffle::test::TEST ( PiggyTest  ,
Iteration   
)

Definition at line 151 of file eqrel_datastructure_test.cpp.

152  {
153  pl.append(i);
154  }
155 
156  souffle::PiggyList<size_t> pl2(pl);
157  EXPECT_EQ(pl.size(), pl2.size());
158 
159  // check every element is equal and same order
160  for (size_t i = 0; i < N; ++i) {
161  EXPECT_EQ(pl.get(i), pl2.get(i));

References souffle::PiggyList< T >::append(), and i.

Here is the call graph for this function:

◆ TEST() [65/78]

souffle::test::TEST ( PiggyTest  ,
Scoping   
)

Regular Old Piggy List.

Definition at line 113 of file eqrel_datastructure_test.cpp.

119  {

◆ TEST() [66/78]

souffle::test::TEST ( RandomInsertPiggyTest  ,
DoubleClear   
)

Definition at line 76 of file eqrel_datastructure_test.cpp.

81  {
82  constexpr size_t limit = 10000;
83  souffle::RandomInsertPiggyList<size_t> pl;
84 
85 // insert in parallel (no element should be overridden, because this breaks the datastructure)
86 #pragma omp parallel for
87  for (size_t i = 0; i < limit; ++i) {
88  pl.insertAt(i, i);
89  }
90 
91  EXPECT_EQ(limit, pl.size());
92  for (size_t i = 0; i < limit; ++i) {

◆ TEST() [67/78]

souffle::test::TEST ( RandomInsertPiggyTest  ,
Insertion   
)

Definition at line 62 of file eqrel_datastructure_test.cpp.

62  {
63  // err.. prior versions have had the bug where clear caused double-free errors (as we don't set the
64  // container to null) This should *crash* the test-suite if this is the case, but I also try to check the
65  // contents here
66  souffle::RandomInsertPiggyList<size_t> pl;
67  pl.insertAt(0, 3213);
68  pl.insertAt(1, 3213);
69  pl.insertAt(2, 3213);
70  pl.insertAt(3, 3213);
71  EXPECT_EQ(pl.size(), 4);
72  pl.clear();
73  EXPECT_EQ(pl.size(), 0);
74  pl.clear();

References souffle::RandomInsertPiggyList< T >::clear(), EXPECT_EQ, souffle::RandomInsertPiggyList< T >::insertAt(), and souffle::RandomInsertPiggyList< T >::size().

Here is the call graph for this function:

◆ TEST() [68/78]

souffle::test::TEST ( RandomInsertPiggyTest  ,
Scoping   
)

Piggy List that allows creation at arbitrary elements.

Definition at line 57 of file eqrel_datastructure_test.cpp.

62  {

◆ TEST() [69/78]

souffle::test::TEST ( SparseDjTest  ,
MakeNode   
)

Definition at line 378 of file eqrel_datastructure_test.cpp.

383  {
384  // check whether the unioning works to see if the elements are properly in the same set
385  souffle::SparseDisjointSet<size_t> sds;
386 
387  sds.makeNode(20);
388  sds.makeNode(32);
389 
390  EXPECT_FALSE(sds.contains(20, 32));
391  sds.unionNodes(20, 32);
392  EXPECT_TRUE(sds.contains(20, 32));
393 
394  EXPECT_EQ(sds.size(), 2);
395 

◆ TEST() [70/78]

souffle::test::TEST ( SparseDjTest  ,
Scoping   
)

The SparseDisjointSet that is used by the EquivalenceRelation.

Definition at line 374 of file eqrel_datastructure_test.cpp.

376  {

References i, and souffle::SparseDisjointSet< SparseDomain >::makeNode().

Here is the call graph for this function:

◆ TEST() [71/78]

souffle::test::TEST ( SparseDjTest  ,
SignedData   
)

Definition at line 417 of file eqrel_datastructure_test.cpp.

421  {
422  data_source.push_back(i);
423  }
424  std::shuffle(data_source.begin(), data_source.end(), std::random_device());

References i.

◆ TEST() [72/78]

souffle::test::TEST ( SparseDjTest  ,
TestUnion   
)

Definition at line 397 of file eqrel_datastructure_test.cpp.

403  {
404  // test when the sparse dj set stores different signed-ness to the internally stored data
405  souffle::SparseDisjointSet<ssize_t> sds;
406 
407  EXPECT_EQ(sds.size(), 0);
408  sds.makeNode(9999);
409  EXPECT_EQ(sds.size(), 1);
410 }
411 
412 #ifdef _OPENMP
413 TEST(SparseDjTest, ParallelDense) {
414  souffle::SparseDisjointSet<size_t> sds;
415  // store the dense and sparse values

◆ TEST() [73/78]

souffle::test::TEST ( SymbolTable  ,
Assign   
)

Definition at line 75 of file symbol_table_test.cpp.

96  {
97  // whether to print the recorded times to stdout
98  // should be false unless developing
99  const bool ECHO_TIME = false;
100 

◆ TEST() [74/78]

souffle::test::TEST ( SymbolTable  ,
Basics   
)

Definition at line 35 of file symbol_table_test.cpp.

44  {
45  auto* a = new SymbolTable();
46  a->insert("Hello");
47 
48  auto* b = new SymbolTable(*a);

◆ TEST() [75/78]

souffle::test::TEST ( SymbolTable  ,
Copy   
)

Definition at line 50 of file symbol_table_test.cpp.

69  {
70  auto* a = new SymbolTable();
71  a->insert("Hello");
72 
73  SymbolTable b = *a;

◆ TEST() [76/78]

souffle::test::TEST ( SymbolTable  ,
Inserts   
)

Definition at line 102 of file symbol_table_test.cpp.

117  {
118  x = std::to_string(i) + "string";
119  A.push_back(x);
120  }
121  start = now();
122  for (T i = 0; i < N; ++i) {
123  X.insert(A[i]); // insert one at a time
124  }
125  end = now();
126  n = duration_in_ns(start, end); // record the time
127 
128  if (ECHO_TIME) {
129  std::cout << "Time to insert " << N << " new elements: " << n << " ns" << std::endl;
130  }
131 
132  // try inserting all the elements that were just inserted
133  start = now();
134  X.insert(A);
135  end = now();
136  n = duration_in_ns(start, end);
137 
138  if (ECHO_TIME) {
139  std::cout << "Time to insert " << N << " existing elements: " << n << " ns" << std::endl;
140  }
141 }
142 
143 } // namespace souffle::test

References i.

◆ TEST() [77/78]

souffle::test::TEST ( Table  ,
Basic   
)

Definition at line 48 of file table_test.cpp.

49  {
50  for (int i = 0; i < 10000; ++i) {
51  Table<int> table;
52 
53  for (int j = 0; j < i; ++j) {
54  table.insert(j);
55  }
56 
57  EXPECT_EQ((size_t)i, table.size());
58 
59  int last = -1;

References EXPECT_EQ, i, souffle::Table< T, blockSize >::insert(), j, and souffle::Table< T, blockSize >::size().

Here is the call graph for this function:

◆ TEST() [78/78]

souffle::test::TEST ( Table  ,
Stress   
)

Definition at line 61 of file table_test.cpp.

◆ time()

template<typename Op >
long souffle::test::time ( const std::string &  name,
const Op &  operation 
)

Definition at line 411 of file btree_multiset_test.cpp.

411  {
412  std::cout << "\t" << std::setw(30) << std::setiosflags(std::ios::left) << name
413  << std::resetiosflags(std::ios::left) << " ... " << std::flush;
414  auto a = now();
415  operation();
416  auto b = now();
417  auto time = duration(a, b);
418  std::cout << " done [" << std::setw(5) << time << "ms]\n";
419  return time;
420 }

References b, duration(), and now().

Referenced by souffle::ProfileEventSingleton::makeTimingEvent(), souffle::profile::RelationIOTimingProcessor::process(), souffle::profile::ProgramRun::setEndtime(), souffle::profile::Iteration::setEndtime(), souffle::profile::Rule::setEndtime(), souffle::profile::Relation::setEndtime(), souffle::profile::ProgramRun::setStarttime(), souffle::profile::Rule::setStarttime(), souffle::profile::Iteration::setStarttime(), souffle::profile::Relation::setStarttime(), TEST(), and TEST().

Here is the call graph for this function:
souffle::PiggyList::get
T & get(size_t index) const
Retrieve a reference to the stored value at index.
Definition: PiggyList.h:235
souffle::parent_t
uint64_t parent_t
Definition: UnionFind.h:41
DEBUG
#define DEBUG(Kind)
EXPECT_TRUE
#define EXPECT_TRUE(a)
Definition: test.h:189
souffle::PiggyList::size
size_t size() const
Well, returns the number of nodes exist within the list + number of nodes queued to be inserted The r...
Definition: PiggyList.h:181
souffle::SparseDisjointSet
Definition: UnionFind.h:258
souffle::DisjointSet::clear
void clear()
Clears the DisjointSet of all nodes Invalidates all iterators.
Definition: UnionFind.h:140
souffle::RamDomain
int32_t RamDomain
Definition: RamTypes.h:56
souffle::RandomInsertPiggyList::insertAt
void insertAt(size_t index, T value)
Definition: PiggyList.h:90
souffle::SparseDisjointSet::size
std::size_t size()
Definition: UnionFind.h:331
souffle::test::now
time_point now()
Definition: btree_multiset_test.cpp:402
souffle::DisjointSet::sameSet
bool sameSet(parent_t x, parent_t y)
Check whether the two indices are in the same set.
Definition: UnionFind.h:150
EXPECT_EQ
#define EXPECT_EQ(a, b)
Definition: test.h:191
e
l j a showGridBackground &&c b raw series this eventEmitter e
Definition: htmlJsChartistMin.h:15
souffle::SparseDisjointSet::unionNodes
void unionNodes(SparseDomain x, SparseDomain y)
Definition: UnionFind.h:327
souffle::PiggyList::append
size_t append(T element)
Definition: PiggyList.h:189
testutil::ignore
void ignore(const T &)
Definition: test.h:70
souffle::DisjointSet::makeNode
block_t makeNode()
Create a node with its parent as itself, rank 0.
Definition: UnionFind.h:198
souffle::PiggyList::createNode
size_t createNode()
Definition: PiggyList.h:210
n
var n
Definition: htmlJsChartistMin.h:15
j
var j
Definition: htmlJsChartistMin.h:15
souffle::test::TEST
TEST(LambdaBTreeTest, Insert)
Definition: eqrel_datastructure_test.cpp:523
souffle::SparseDisjointSet::contains
bool contains(SparseDomain v1, SparseDomain v2)
Definition: UnionFind.h:355
souffle::now
time_point now()
Definition: MiscUtil.h:89
NUMBER_OF_TESTS
#define NUMBER_OF_TESTS
Definition: record_table_test.cpp:38
souffle::test::EqRel
souffle::EquivalenceRelation< Tuple< RamDomain, 2 > > EqRel
Definition: binary_relation_test.cpp:56
i
size_t i
Definition: json11.h:663
souffle::filter
std::vector< A > filter(std::vector< A > xs, F &&f)
Filter a vector to include certain elements.
Definition: FunctionalUtil.h:155
souffle::PiggyList
Definition: PiggyList.h:143
souffle::PiggyList::clear
void clear()
Clear all elements from the PiggyList.
Definition: PiggyList.h:246
souffle::SparseDisjointSet::makeNode
void makeNode(SparseDomain val)
Definition: UnionFind.h:345
souffle::DisjointSet::unionNodes
void unionNodes(parent_t x, parent_t y)
Union the two specified index nodes.
Definition: UnionFind.h:165
souffle::test::count
int count(const C &c)
Definition: table_test.cpp:40
souffle::pack
RamDomain pack(RecordTable &recordTab, Tuple< RamDomain, Arity > const &tuple)
helper to convert tuple to record reference for the synthesiser
Definition: RecordTable.h:153
souffle::duration_in_ns
long duration_in_ns(const time_point &start, const time_point &end)
Definition: MiscUtil.h:99
EXPECT_LT
#define EXPECT_LT(a, b)
Definition: test.h:199
souffle::Tuple
std::array< A, N > Tuple
Definition: RamTypes.h:36
souffle::RandomInsertPiggyList::clear
void clear()
Definition: PiggyList.h:110
souffle::test::TEST
TEST(EqRelTest, Scaling)
Definition: binary_relation_test.cpp:539
k
var k
Definition: htmlJsChartistMin.h:15
EXPECT_NE
#define EXPECT_NE(a, b)
Definition: test.h:195
souffle::test::duration
long duration(const time_point &start, const time_point &end)
Definition: btree_multiset_test.cpp:406
souffle::test::getData
std::vector< Entry > getData(unsigned numEntries)
Definition: btree_multiset_test.cpp:387
souffle::test::time
long time(const std::string &name, const Op &operation)
Definition: btree_multiset_test.cpp:411
b
l j a showGridBackground &&c b raw series this eventEmitter b
Definition: htmlJsChartistMin.h:15
souffle::test::Entry
std::tuple< int, int > Entry
Definition: btree_multiset_test.cpp:385
souffle::RandomInsertPiggyList::size
size_t size() const
Definition: PiggyList.h:75
souffle::test::TEST
TEST(PackUnpack, Vector)
Definition: record_table_test.cpp:92
souffle::test::TestPair
std::pair< size_t, size_t > TestPair
Definition: eqrel_datastructure_test.cpp:511
d
else d
Definition: htmlJsChartistMin.h:15
souffle::RandomInsertPiggyList
A PiggyList that allows insertAt functionality.
Definition: PiggyList.h:37
souffle::DisjointSet
Structure that emulates a Disjoint Set, i.e.
Definition: UnionFind.h:54
TCB_SPAN_NAMESPACE_NAME::detail::data
constexpr auto data(C &c) -> decltype(c.data())
Definition: span.h:210
checkPerformance
#define checkPerformance(set_type, name, in, out)
Definition: btree_multiset_test.cpp:436
souffle::DisjointSet::size
size_t size()
Return the number of elements in this disjoint set (not the number of pairs)
Definition: UnionFind.h:76
EXPECT_FALSE
#define EXPECT_FALSE(a)
Definition: test.h:190
souffle::test::TEST
TEST(ParallelUtils, OptimisticReadWriteLock)
Definition: parallel_utils_test.cpp:79
Generated by   doxygen 1.8.17