Adding support for overlapping ranges to RangeMap.

src/processor/range_map_unittest.cc

 // Copyright (c) 2010 Google Inc.
 // All rights reserved.
 //
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 // notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
@@ skipping 86 matching lines @@
   // The number of tests in the set
   unsigned int range_test_count;
 };
 
 
 // StoreTest uses the data in a RangeTest and calls StoreRange on the
 // test RangeMap.  It returns true if the expected result occurred, and
 // false if something else happened.
 static bool StoreTest(TestMap *range_map, const RangeTest *range_test) {
   linked_ptr<CountedObject> object(new CountedObject(range_test->id));
-  bool stored = range_map->StoreRange(range_test->address,
-                                      range_test->size,
-                                      object);
+  bool stored = range_map->StoreRange(range_test->address, 0 /* delta */,
+                                      range_test->size, object);
 
   if (stored != range_test->expect_storable) {
     fprintf(stderr, "FAILED: "
             "StoreRange id %d, expected %s, observed %s\n",
             range_test->id,
             range_test->expect_storable ? "storable" : "not storable",
             stored ? "stored" : "not stored");
     return false;
   }
 
@@ skipping 39 matching lines @@
           expected_result = true;    // test should always succeed.
         else if (offset == -1)       // When checking one below the target,
           expected_result = side;    // should fail low and succeed high.
         else                         // When checking one above the target,
           expected_result = !side;   // should succeed low and fail high.
       }
 
       linked_ptr<CountedObject> object;
       AddressType retrieved_base = AddressType();
       AddressType retrieved_size = AddressType();
+      AddressType retrieved_delta = AddressType();
       bool retrieved = range_map->RetrieveRange(address, &object,
                                                 &retrieved_base,
+                                                &retrieved_delta,
                                                 &retrieved_size);
 
       bool observed_result = retrieved && object->id() == range_test->id;
 
       if (observed_result != expected_result) {
         fprintf(stderr, "FAILED: "
                         "RetrieveRange id %d, side %d, offset %d, "
                         "expected %s, observed %s\n",
                         range_test->id,
                         side,
@@ skipping 21 matching lines @@
 
       // Now, check RetrieveNearestRange.  The nearest range is always
       // expected to be different from the test range when checking one
       // less than the low side.
       bool expected_nearest = range_test->expect_storable;
       if (!side && offset < 0)
         expected_nearest = false;
 
       linked_ptr<CountedObject> nearest_object;
       AddressType nearest_base = AddressType();
+      AddressType nearest_delta = AddressType();
       AddressType nearest_size = AddressType();
       bool retrieved_nearest = range_map->RetrieveNearestRange(address,
                                                                &nearest_object,
                                                                &nearest_base,
+                                                               &nearest_delta,
                                                                &nearest_size);
 
       // When checking one greater than the high side, RetrieveNearestRange
       // should usually return the test range.  When a different range begins
       // at that address, though, then RetrieveNearestRange should return the
       // range at the address instead of the test range.
       if (side && offset > 0 && nearest_base == address) {
         expected_nearest = false;
       }
 
@@ skipping 41 matching lines @@
 // call, and that ranges are returned with increasing base addresses.  Returns
 // false if the test fails.
 static bool RetrieveIndexTest(TestMap *range_map, int set) {
   linked_ptr<CountedObject> object;
   CountedObject *last_object = NULL;
   AddressType last_base = 0;
 
   int object_count = range_map->GetCount();
   for (int object_index = 0; object_index < object_count; ++object_index) {
     AddressType base;
-    if (!range_map->RetrieveRangeAtIndex(object_index, &object, &base, NULL)) {
+    if (!range_map->RetrieveRangeAtIndex(object_index, &object, &base,
+                                         NULL, NULL)) {
       fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, "
               "expected success, observed failure\n",
               set, object_index);
       return false;
     }
 
     if (!object.get()) {
       fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, "
               "expected object, observed NULL\n",
               set, object_index);
@@ skipping 19 matching lines @@
         return false;
       }
     }
 
     last_object = object.get();
     last_base = base;
   }
 
   // Make sure that RetrieveRangeAtIndex doesn't allow lookups at indices that
   // are too high.
-  if (range_map->RetrieveRangeAtIndex(object_count, &object, NULL, NULL)) {
+  if (range_map->RetrieveRangeAtIndex(object_count, &object, NULL, NULL,
+                                      NULL)) {
     fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d (too large), "
             "expected failure, observed success\n",
             set, object_count);
     return false;
   }
 
   return true;
 }
 
 // Additional RetriveAtIndex test to expose the bug in RetrieveRangeAtIndex().
 // Bug info: RetrieveRangeAtIndex() previously retrieves the high address of
 // entry, however, it is supposed to retrieve the base address of entry as
 // stated in the comment in range_map.h.
 static bool RetriveAtIndexTest2() {
   scoped_ptr<TestMap> range_map(new TestMap());
 
   // Store ranges with base address = 2 * object_id:
   const int range_size = 2;
   for (int object_id = 0; object_id < 100; ++object_id) {
     linked_ptr<CountedObject> object(new CountedObject(object_id));
     int base_address = 2 * object_id;
-    range_map->StoreRange(base_address, range_size, object);
+    range_map->StoreRange(base_address, 0 /* delta */, range_size, object);
   }
 
   linked_ptr<CountedObject> object;
   int object_count = range_map->GetCount();
   for (int object_index = 0; object_index < object_count; ++object_index) {
     AddressType base;
-    if (!range_map->RetrieveRangeAtIndex(object_index, &object, &base, NULL)) {
+    if (!range_map->RetrieveRangeAtIndex(object_index, &object, &base, NULL,
+                                         NULL)) {
       fprintf(stderr, "FAILED: RetrieveAtIndexTest2 index %d, "
               "expected success, observed failure\n", object_index);
       return false;
     }
 
     int expected_base = 2 * object->id();
     if (base != expected_base) {
       fprintf(stderr, "FAILED: RetriveAtIndexTest2 index %d, "
               "expected base %d, observed base %d",
               object_index, expected_base, base);
@@ skipping 186 matching lines @@
 
 
 }  // namespace
 
 
 int main(int argc, char **argv) {
   BPLOG_INIT(&argc, &argv);
 
   return RunTests() ? 0 : 1;
 }
+