range_map_test.cc
Go to the documentation of this file.
1 // Copyright 2016 Google Inc. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
15 #include "bloaty.h"
16 
17 #include "gmock/gmock.h"
18 #include "gtest/gtest.h"
19 
20 #include <tuple>
21 
22 namespace bloaty {
23 
24 class RangeMapTest : public ::testing::Test {
25  protected:
26  void CheckConsistencyFor(const bloaty::RangeMap& map) {
27  uint64_t last_end = 0;
28  for (auto it = map.mappings_.begin(); it != map.mappings_.end(); ++it) {
29  ASSERT_GE(it->first, last_end);
30  last_end = map.RangeEnd(it);
31  }
32  }
33 
34  void CheckConsistency() {
35  CheckConsistencyFor(map_);
36  CheckConsistencyFor(map2_);
37  CheckConsistencyFor(map3_);
38  }
39 
40  struct Row {
41  std::vector<std::string> keys;
42  uint64_t start;
43  uint64_t end;
44  };
45 
46  void AssertRollupEquals(const std::vector<const RangeMap*> maps,
47  const std::vector<Row>& rows) {
48  int i = 0;
49  RangeMap::ComputeRollup(
50  maps, [&i, &rows](const std::vector<std::string>& keys, uint64_t start,
51  uint64_t end) {
52  ASSERT_LT(i, rows.size());
53  const auto& row = rows[i];
54  ASSERT_EQ(row.keys, keys);
55  ASSERT_EQ(row.start, start);
56  ASSERT_EQ(row.end, end);
57  i++;
58  });
59  ASSERT_EQ(rows.size(), i);
60  }
61 
62  struct Entry {
63  uint64_t addr;
64  uint64_t end;
65  uint64_t other_start;
66  std::string label;
67  };
68 
69  void AssertMapEquals(const bloaty::RangeMap& map,
70  const std::vector<Entry>& entries) {
71  auto iter = map.mappings_.begin();
72  size_t i = 0;
73  for (; i < entries.size() && iter != map.mappings_.end(); ++i, ++iter) {
74  const auto& entry = entries[i];
75  ASSERT_EQ(entry.addr, iter->first) << i;
76  ASSERT_EQ(entry.end, map.RangeEnd(iter)) << i;
77  ASSERT_EQ(entry.other_start, iter->second.other_start) << i;
78  ASSERT_EQ(entry.label, iter->second.label) << i;
79  }
80  ASSERT_EQ(i, entries.size());
81  ASSERT_EQ(iter, map.mappings_.end());
82 
83  // Also test that ComputeRollup yields the same thing.
84  i = 0;
85  RangeMap::ComputeRollup({&map},
86  [&i, &entries](const std::vector<std::string>& keys,
87  uint64_t start, uint64_t end) {
88  ASSERT_LT(i, entries.size());
89  const auto& entry = entries[i];
90  ASSERT_EQ(entry.addr, start);
91  ASSERT_EQ(entry.end, end);
92  ASSERT_EQ(entry.label, keys[0]);
93  i++;
94  });
95  ASSERT_EQ(entries.size(), i);
96  }
97 
98  void AssertMainMapEquals(const std::vector<Entry>& entries) {
99  AssertMapEquals(map_, entries);
100  }
101 
102  bloaty::RangeMap map_;
103  bloaty::RangeMap map2_;
104  bloaty::RangeMap map3_;
105 
106  const uint64_t kNoTranslation = RangeMap::kNoTranslation;
107  const uint64_t kUnknownSize = RangeMap::kUnknownSize;
108 };
109 
110 TEST_F(RangeMapTest, AddRange) {
111  CheckConsistency();
112  AssertMainMapEquals({});
113 
114  map_.AddRange(4, 3, "foo");
115  CheckConsistency();
116  AssertMainMapEquals({
117  {4, 7, kNoTranslation, "foo"}
118  });
119 
120  map_.AddRange(30, 5, "bar");
121  CheckConsistency();
122  AssertMainMapEquals({
123  {4, 7, kNoTranslation, "foo"},
124  {30, 35, kNoTranslation, "bar"}
125  });
126 
127  map_.AddRange(50, 0, "baz"); // No-op due to 0 size.
128  CheckConsistency();
129  AssertMainMapEquals({
130  {4, 7, kNoTranslation, "foo"},
131  {30, 35, kNoTranslation, "bar"}
132  });
133 
134  map_.AddRange(20, 5, "baz");
135  map_.AddRange(25, 5, "baz2");
136  map_.AddRange(40, 5, "quux");
137  CheckConsistency();
138  AssertMainMapEquals({
139  {4, 7, kNoTranslation, "foo"},
140  {20, 25, kNoTranslation, "baz"},
141  {25, 30, kNoTranslation, "baz2"},
142  {30, 35, kNoTranslation, "bar"},
143  {40, 45, kNoTranslation, "quux"}
144  });
145 
146  map_.AddRange(21, 25, "overlapping");
147  CheckConsistency();
148  AssertMainMapEquals({
149  {4, 7, kNoTranslation, "foo"},
150  {20, 25, kNoTranslation, "baz"},
151  {25, 30, kNoTranslation, "baz2"},
152  {30, 35, kNoTranslation, "bar"},
153  {35, 40, kNoTranslation, "overlapping"},
154  {40, 45, kNoTranslation, "quux"},
155  {45, 46, kNoTranslation, "overlapping"}
156  });
157 
158  map_.AddRange(21, 25, "overlapping no-op");
159  CheckConsistency();
160  AssertMainMapEquals({
161  {4, 7, kNoTranslation, "foo"},
162  {20, 25, kNoTranslation, "baz"},
163  {25, 30, kNoTranslation, "baz2"},
164  {30, 35, kNoTranslation, "bar"},
165  {35, 40, kNoTranslation, "overlapping"},
166  {40, 45, kNoTranslation, "quux"},
167  {45, 46, kNoTranslation, "overlapping"}
168  });
169 
170  map_.AddRange(0, 100, "overlap everything");
171  CheckConsistency();
172  AssertMainMapEquals({
173  {0, 4, kNoTranslation, "overlap everything"},
174  {4, 7, kNoTranslation, "foo"},
175  {7, 20, kNoTranslation, "overlap everything"},
176  {20, 25, kNoTranslation, "baz"},
177  {25, 30, kNoTranslation, "baz2"},
178  {30, 35, kNoTranslation, "bar"},
179  {35, 40, kNoTranslation, "overlapping"},
180  {40, 45, kNoTranslation, "quux"},
181  {45, 46, kNoTranslation, "overlapping"},
182  {46, 100, kNoTranslation, "overlap everything"},
183  });
184 }
185 
186 TEST_F(RangeMapTest, UnknownSize) {
187  map_.AddRange(5, kUnknownSize, "foo");
188  CheckConsistency();
189  AssertMainMapEquals({
190  {5, UINT64_MAX, kNoTranslation, "foo"}
191  });
192 
193  map_.AddRange(100, 15, "bar");
194  map_.AddRange(200, kUnknownSize, "baz");
195  CheckConsistency();
196  AssertMainMapEquals({
197  {5, 100, kNoTranslation, "foo"},
198  {100, 115, kNoTranslation, "bar"},
199  {200, UINT64_MAX, kNoTranslation, "baz"}
200  });
201 
202  map2_.AddRange(5, 110, "base0");
203  map2_.AddRange(200, 50, "base1");
204 
205  AssertRollupEquals({&map2_, &map_}, {
206  {{"base0", "foo"}, 5, 100},
207  {{"base0", "bar"}, 100, 115},
208  {{"base1", "baz"}, 200, 250},
209  });
210 }
211 
212 TEST_F(RangeMapTest, UnknownSize2) {
213  // This case is slightly weird, but we do consider the "100" below to be a
214  // hard fact even if the size is unknown, so the "[95, 105]: bar" range
215  // doesn't override it.
216  map_.AddRange(100, kUnknownSize, "foo");
217  map_.AddRange(95, 10, "bar");
218  AssertMainMapEquals({
219  {95, 100, kNoTranslation, "bar"},
220  {100, 105, kNoTranslation, "foo"},
221  });
222 }
223 
224 TEST_F(RangeMapTest, UnknownSize3) {
225  map_.AddRange(100, kUnknownSize, "foo");
226  map_.AddRange(150, kUnknownSize, "bar");
227  // This tells us the ultimate size of "foo", and we keep the "foo" label even
228  // though the new label is "baz".
229  map_.AddRange(100, 100, "baz");
230  AssertMainMapEquals({
231  {100, 150, kNoTranslation, "foo"},
232  {150, 200, kNoTranslation, "bar"},
233  });
234 }
235 
236 TEST_F(RangeMapTest, UnknownSize4) {
237  map_.AddRange(100, kUnknownSize, "foo");
238  map_.AddRange(150, 100, "bar");
239  // This tells us the ultimate size of "foo", and we keep the "foo" label even
240  // though the new label is "baz".
241  map_.AddRange(100, 100, "baz");
242  AssertMainMapEquals({
243  {100, 150, kNoTranslation, "foo"},
244  {150, 250, kNoTranslation, "bar"},
245  });
246 }
247 
248 TEST_F(RangeMapTest, Bug1) {
249  map_.AddRange(100, 20, "foo");
250  map_.AddRange(120, 20, "bar");
251  map_.AddRange(100, 15, "baz");
252  AssertMainMapEquals({
253  {100, 120, kNoTranslation, "foo"},
254  {120, 140, kNoTranslation, "bar"},
255  });
256 }
257 
258 TEST_F(RangeMapTest, Bug2) {
259  map_.AddRange(100, kUnknownSize, "foo");
260  map_.AddRange(200, 50, "bar");
261  map_.AddRange(150, 10, "baz");
262  AssertMainMapEquals({
263  {100, 150, kNoTranslation, "foo"},
264  {150, 160, kNoTranslation, "baz"},
265  {200, 250, kNoTranslation, "bar"},
266  });
267 }
268 
269 TEST_F(RangeMapTest, Bug3) {
270  map_.AddRange(100, kUnknownSize, "foo");
271  map_.AddRange(200, kUnknownSize, "bar");
272  map_.AddRange(150, 10, "baz");
273  AssertMainMapEquals({
274  {100, 150, kNoTranslation, "foo"},
275  {150, 160, kNoTranslation, "baz"},
276  {200, UINT64_MAX, kNoTranslation, "bar"},
277  });
278 }
279 
280 TEST_F(RangeMapTest, GetLabel) {
281  map_.AddRange(100, kUnknownSize, "foo");
282  map_.AddRange(200, 50, "bar");
283  map_.AddRange(150, 10, "baz");
284  AssertMainMapEquals({
285  {100, 150, kNoTranslation, "foo"},
286  {150, 160, kNoTranslation, "baz"},
287  {200, 250, kNoTranslation, "bar"},
288  });
289 
290  std::string label;
291 
292  ASSERT_TRUE(map_.TryGetLabel(100, &label));
293  ASSERT_EQ(label, "foo");
294  ASSERT_TRUE(map_.TryGetLabel(155, &label));
295  ASSERT_EQ(label, "baz");
296  ASSERT_TRUE(map_.TryGetLabel(249, &label));
297  ASSERT_EQ(label, "bar");
298  ASSERT_FALSE(map_.TryGetLabel(250, &label));
299 
300  ASSERT_TRUE(map_.TryGetLabelForRange(100, 10, &label));
301  ASSERT_EQ(label, "foo");
302  ASSERT_TRUE(map_.TryGetLabelForRange(155, 3, &label));
303  ASSERT_EQ(label, "baz");
304  ASSERT_TRUE(map_.TryGetLabelForRange(200, 50, &label));
305  ASSERT_EQ(label, "bar");
306  ASSERT_FALSE(map_.TryGetLabelForRange(200, 51, &label));
307 }
308 
309 TEST_F(RangeMapTest, Translation) {
310  map_.AddDualRange(20, 5, 120, "foo");
311  CheckConsistency();
312  AssertMainMapEquals({
313  {20, 25, 120, "foo"}
314  });
315 
316  ASSERT_TRUE(map2_.AddRangeWithTranslation(20, 5, "translate me", map_, false,
317  &map3_));
318 
319  CheckConsistency();
320  AssertMapEquals(map2_, {
321  {20, 25, kNoTranslation, "translate me"}
322  });
323  AssertMapEquals(map3_, {
324  {120, 125, kNoTranslation, "translate me"}
325  });
326 
327  map_.AddDualRange(1000, 30, 1100, "bar");
328  ASSERT_TRUE(map2_.AddRangeWithTranslation(1000, 5, "translate me2", map_,
329  false, &map3_));
330  AssertMapEquals(map2_, {
331  {20, 25, kNoTranslation, "translate me"},
332  {1000, 1005, kNoTranslation, "translate me2"}
333  });
334  AssertMapEquals(map3_, {
335  {120, 125, kNoTranslation, "translate me"},
336  {1100, 1105, kNoTranslation, "translate me2"}
337  });
338 
339  // Starts before base map.
340  ASSERT_FALSE(map2_.AddRangeWithTranslation(15, 8, "translate me", map_, false,
341  &map3_));
342 
343  // Extends past base map.
344  ASSERT_FALSE(map2_.AddRangeWithTranslation(22, 15, "translate me", map_,
345  false, &map3_));
346 
347  // Starts and ends in base map, but skips range in the middle.
348  ASSERT_FALSE(map2_.AddRangeWithTranslation(20, 1000, "translate me", map_,
349  false, &map3_));
350 }
351 
352 TEST_F(RangeMapTest, Translation2) {
353  map_.AddRange(5, 5, "foo");
354  map_.AddDualRange(20, 5, 120, "bar");
355  map_.AddRange(25, 5, "baz");
356  map_.AddDualRange(30, 5, 130, "quux");
357  CheckConsistency();
358  AssertMainMapEquals({
359  {5, 10, kNoTranslation, "foo"},
360  {20, 25, 120, "bar"},
361  {25, 30, kNoTranslation, "baz"},
362  {30, 35, 130, "quux"}
363  });
364 
365  ASSERT_TRUE(map2_.AddRangeWithTranslation(20, 15, "translate me", map_, false,
366  &map3_));
367  CheckConsistency();
368  AssertMapEquals(map2_, {
369  {20, 25, kNoTranslation, "translate me"},
370  {25, 30, kNoTranslation, "translate me"},
371  {30, 35, kNoTranslation, "translate me"}
372  });
373  AssertMapEquals(map3_, {
374  {120, 125, kNoTranslation, "translate me"},
375  {130, 135, kNoTranslation, "translate me"}
376  });
377 }
378 
379 TEST_F(RangeMapTest, UnknownTranslation) {
380  map_.AddDualRange(20, 10, 120, "foo");
381  CheckConsistency();
382  AssertMainMapEquals({
383  {20, 30, 120, "foo"}
384  });
385 
386  map2_.AddRangeWithTranslation(25, kUnknownSize, "translate me", map_, false,
387  &map3_);
388  CheckConsistency();
389  AssertMapEquals(map2_, {
390  {25, UINT64_MAX, kNoTranslation, "translate me"}
391  });
392  AssertMapEquals(map3_, {
393  {125, UINT64_MAX, kNoTranslation, "translate me"}
394  });
395 
396  map2_.AddRange(20, 10, "fallback");
397 
398  AssertRollupEquals({&map_, &map2_}, {
399  {{"foo", "fallback"}, 20, 25},
400  {{"foo", "translate me"}, 25, 30},
401  });
402 }
403 
404 } // namespace bloaty
bloaty::RangeMapTest::Entry::addr
uint64_t addr
Definition: range_map_test.cc:63
bloaty
Definition: bloaty.cc:69
bloaty::RangeMapTest::AssertMapEquals
void AssertMapEquals(const bloaty::RangeMap &map, const std::vector< Entry > &entries)
Definition: range_map_test.cc:69
regen-readme.it
it
Definition: regen-readme.py:15
bloaty::RangeMap::kNoTranslation
static const uint64_t kNoTranslation
Definition: range_map.h:158
bloaty::RangeMapTest::Entry::label
std::string label
Definition: range_map_test.cc:66
keys
const void * keys
Definition: abseil-cpp/absl/random/internal/randen.cc:49
bloaty::TEST_F
TEST_F(RangeMapTest, AddRange)
Definition: range_map_test.cc:110
bloaty::RangeMapTest::CheckConsistency
void CheckConsistency()
Definition: range_map_test.cc:34
bloaty::RangeMapTest::Row::end
uint64_t end
Definition: range_map_test.cc:43
bloaty::RangeMap::kUnknownSize
static constexpr uint64_t kUnknownSize
Definition: range_map.h:154
bloaty.h
testing::internal::string
::std::string string
Definition: bloaty/third_party/protobuf/third_party/googletest/googletest/include/gtest/internal/gtest-port.h:881
UINT64_MAX
#define UINT64_MAX
Definition: stdint-msvc2008.h:143
ASSERT_GE
#define ASSERT_GE(val1, val2)
Definition: bloaty/third_party/googletest/googletest/include/gtest/gtest.h:2072
bloaty::RangeMapTest
Definition: range_map_test.cc:24
bloaty::RangeMapTest::map3_
bloaty::RangeMap map3_
Definition: range_map_test.cc:104
map
zval * map
Definition: php/ext/google/protobuf/encode_decode.c:480
testing::Test
Definition: bloaty/third_party/googletest/googletest/include/gtest/gtest.h:402
bloaty::RangeMapTest::map_
bloaty::RangeMap map_
Definition: range_map_test.cc:102
bloaty::RangeMap
Definition: range_map.h:46
start
static uint64_t start
Definition: benchmark-pound.c:74
benchmark::internal::AddRange
void AddRange(std::vector< T > *dst, T lo, T hi, int mult)
Definition: benchmark_register.h:59
end
char * end
Definition: abseil-cpp/absl/strings/internal/str_format/float_conversion.cc:1008
ASSERT_LT
#define ASSERT_LT(val1, val2)
Definition: bloaty/third_party/googletest/googletest/include/gtest/gtest.h:2068
gen_synthetic_protos.label
label
Definition: gen_synthetic_protos.py:102
uint64_t
unsigned __int64 uint64_t
Definition: stdint-msvc2008.h:90
bloaty::RangeMapTest::Entry::end
uint64_t end
Definition: range_map_test.cc:64
google::protobuf::python::field_descriptor::GetLabel
static PyObject * GetLabel(PyBaseDescriptor *self, void *closure)
Definition: bloaty/third_party/protobuf/python/google/protobuf/pyext/descriptor.cc:773
bloaty::RangeMapTest::Row
Definition: range_map_test.cc:40
bloaty::RangeMapTest::Row::start
uint64_t start
Definition: range_map_test.cc:42
bloaty::RangeMapTest::Entry
Definition: range_map_test.cc:62
bloaty::RangeMapTest::Row::keys
std::vector< std::string > keys
Definition: range_map_test.cc:41
bloaty::RangeMapTest::kNoTranslation
const uint64_t kNoTranslation
Definition: range_map_test.cc:106
ASSERT_TRUE
#define ASSERT_TRUE(condition)
Definition: bloaty/third_party/googletest/googletest/include/gtest/gtest.h:1973
ASSERT_FALSE
#define ASSERT_FALSE(condition)
Definition: bloaty/third_party/googletest/googletest/include/gtest/gtest.h:1976
bloaty::RangeMapTest::map2_
bloaty::RangeMap map2_
Definition: range_map_test.cc:103
bloaty::RangeMapTest::AssertMainMapEquals
void AssertMainMapEquals(const std::vector< Entry > &entries)
Definition: range_map_test.cc:98
bloaty::RangeMapTest::CheckConsistencyFor
void CheckConsistencyFor(const bloaty::RangeMap &map)
Definition: range_map_test.cc:26
iter
Definition: test_winkernel.cpp:47
bloaty::RangeMapTest::kUnknownSize
const uint64_t kUnknownSize
Definition: range_map_test.cc:107
bloaty::RangeMapTest::AssertRollupEquals
void AssertRollupEquals(const std::vector< const RangeMap * > maps, const std::vector< Row > &rows)
Definition: range_map_test.cc:46
bloaty::RangeMap::ComputeRollup
static void ComputeRollup(const std::vector< const RangeMap * > &range_maps, Func func)
Definition: range_map.h:251
i
uint64_t i
Definition: abseil-cpp/absl/container/btree_benchmark.cc:230
ASSERT_EQ
#define ASSERT_EQ(val1, val2)
Definition: bloaty/third_party/googletest/googletest/include/gtest/gtest.h:2056
bloaty::RangeMapTest::Entry::other_start
uint64_t other_start
Definition: range_map_test.cc:65

grpc
Author(s):
autogenerated on Thu Mar 13 2025 03:00:59