Adding support for overlapping ranges to RangeMap.

When enabled, adding of a new range that overlaps with an existing one can be a successful operation.  The range which ends at the higher address will be shrunk down by moving its start position to a higher address so that it does not overlap anymore.

This change is required to fix http://crbug/611824.  The actual fix will come in a separate CL.

R=mmandlis@chromium.org

Review URL: https://codereview.chromium.org/2029953003 .

1 files changed, 56 insertions, 0 deletions

diff --git a/Makefile.in b/Makefile.in
index d9c91332..06a112d5 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -194,6 +194,7 @@ EXTRA_PROGRAMS = $(am__EXEEXT_1)
 @DISABLE_PROCESSOR_FALSE@	src/processor/pathname_stripper_unittest \
 @DISABLE_PROCESSOR_FALSE@	src/processor/postfix_evaluator_unittest \
 @DISABLE_PROCESSOR_FALSE@	src/processor/proc_maps_linux_unittest \
+@DISABLE_PROCESSOR_FALSE@	src/processor/range_map_shrink_down_unittest \
 @DISABLE_PROCESSOR_FALSE@	src/processor/range_map_unittest \
 @DISABLE_PROCESSOR_FALSE@	src/processor/stackwalker_amd64_unittest \
 @DISABLE_PROCESSOR_FALSE@	src/processor/stackwalker_arm_unittest \
@@ -580,6 +581,7 @@ src_third_party_libdisasm_libdisasm_a_OBJECTS =  \
 @DISABLE_PROCESSOR_FALSE@	src/processor/pathname_stripper_unittest$(EXEEXT) \
 @DISABLE_PROCESSOR_FALSE@	src/processor/postfix_evaluator_unittest$(EXEEXT) \
 @DISABLE_PROCESSOR_FALSE@	src/processor/proc_maps_linux_unittest$(EXEEXT) \
+@DISABLE_PROCESSOR_FALSE@	src/processor/range_map_shrink_down_unittest$(EXEEXT) \
 @DISABLE_PROCESSOR_FALSE@	src/processor/range_map_unittest$(EXEEXT) \
 @DISABLE_PROCESSOR_FALSE@	src/processor/stackwalker_amd64_unittest$(EXEEXT) \
 @DISABLE_PROCESSOR_FALSE@	src/processor/stackwalker_arm_unittest$(EXEEXT) \
@@ -1170,6 +1172,17 @@ src_processor_proc_maps_linux_unittest_OBJECTS =  \
 @DISABLE_PROCESSOR_FALSE@	$(am__DEPENDENCIES_2) \
 @DISABLE_PROCESSOR_FALSE@	$(am__DEPENDENCIES_1) \
 @DISABLE_PROCESSOR_FALSE@	$(am__DEPENDENCIES_1)
+am__src_processor_range_map_shrink_down_unittest_SOURCES_DIST =  \
+	src/processor/range_map_shrink_down_unittest.cc
+@DISABLE_PROCESSOR_FALSE@am_src_processor_range_map_shrink_down_unittest_OBJECTS = src/processor/src_processor_range_map_shrink_down_unittest-range_map_shrink_down_unittest.$(OBJEXT)
+src_processor_range_map_shrink_down_unittest_OBJECTS =  \
+	$(am_src_processor_range_map_shrink_down_unittest_OBJECTS)
+@DISABLE_PROCESSOR_FALSE@src_processor_range_map_shrink_down_unittest_DEPENDENCIES =  \
+@DISABLE_PROCESSOR_FALSE@	src/processor/logging.o \
+@DISABLE_PROCESSOR_FALSE@	src/processor/pathname_stripper.o \
+@DISABLE_PROCESSOR_FALSE@	$(am__DEPENDENCIES_2) \
+@DISABLE_PROCESSOR_FALSE@	$(am__DEPENDENCIES_1) \
+@DISABLE_PROCESSOR_FALSE@	$(am__DEPENDENCIES_1)
 am__src_processor_range_map_unittest_SOURCES_DIST =  \
 	src/processor/range_map_unittest.cc
 @DISABLE_PROCESSOR_FALSE@am_src_processor_range_map_unittest_OBJECTS = src/processor/range_map_unittest.$(OBJEXT)
@@ -1559,6 +1572,7 @@ SOURCES = $(src_client_linux_libbreakpad_client_a_SOURCES) \
 	$(src_processor_pathname_stripper_unittest_SOURCES) \
 	$(src_processor_postfix_evaluator_unittest_SOURCES) \
 	$(src_processor_proc_maps_linux_unittest_SOURCES) \
+	$(src_processor_range_map_shrink_down_unittest_SOURCES) \
 	$(src_processor_range_map_unittest_SOURCES) \
 	$(src_processor_stackwalker_address_list_unittest_SOURCES) \
 	$(src_processor_stackwalker_amd64_unittest_SOURCES) \
@@ -1608,6 +1622,7 @@ DIST_SOURCES =  \
 	$(am__src_processor_pathname_stripper_unittest_SOURCES_DIST) \
 	$(am__src_processor_postfix_evaluator_unittest_SOURCES_DIST) \
 	$(am__src_processor_proc_maps_linux_unittest_SOURCES_DIST) \
+	$(am__src_processor_range_map_shrink_down_unittest_SOURCES_DIST) \
 	$(am__src_processor_range_map_unittest_SOURCES_DIST) \
 	$(am__src_processor_stackwalker_address_list_unittest_SOURCES_DIST) \
 	$(am__src_processor_stackwalker_amd64_unittest_SOURCES_DIST) \
@@ -2827,6 +2842,18 @@ TESTS = $(check_PROGRAMS) $(check_SCRIPTS)
 @DISABLE_PROCESSOR_FALSE@	src/processor/pathname_stripper.o \
 @DISABLE_PROCESSOR_FALSE@	$(PTHREAD_CFLAGS) $(PTHREAD_LIBS)
 
+@DISABLE_PROCESSOR_FALSE@src_processor_range_map_shrink_down_unittest_SOURCES = \
+@DISABLE_PROCESSOR_FALSE@	src/processor/range_map_shrink_down_unittest.cc
+
+@DISABLE_PROCESSOR_FALSE@src_processor_range_map_shrink_down_unittest_LDADD = \
+@DISABLE_PROCESSOR_FALSE@  src/processor/logging.o \
+@DISABLE_PROCESSOR_FALSE@	src/processor/pathname_stripper.o \
+@DISABLE_PROCESSOR_FALSE@	$(TEST_LIBS) \
+@DISABLE_PROCESSOR_FALSE@	$(PTHREAD_CFLAGS) $(PTHREAD_LIBS)
+
+@DISABLE_PROCESSOR_FALSE@src_processor_range_map_shrink_down_unittest_CPPFLAGS = \
+@DISABLE_PROCESSOR_FALSE@	$(AM_CPPFLAGS) $(TEST_CFLAGS)
+
 @DISABLE_PROCESSOR_FALSE@src_processor_range_map_unittest_SOURCES = \
 @DISABLE_PROCESSOR_FALSE@	src/processor/range_map_unittest.cc
 
@@ -4256,6 +4283,13 @@ src/processor/src_processor_proc_maps_linux_unittest-proc_maps_linux_unittest.$(
 src/processor/proc_maps_linux_unittest$(EXEEXT): $(src_processor_proc_maps_linux_unittest_OBJECTS) $(src_processor_proc_maps_linux_unittest_DEPENDENCIES) $(EXTRA_src_processor_proc_maps_linux_unittest_DEPENDENCIES) src/processor/$(am__dirstamp)
 	@rm -f src/processor/proc_maps_linux_unittest$(EXEEXT)
 	$(AM_V_CXXLD)$(CXXLINK) $(src_processor_proc_maps_linux_unittest_OBJECTS) $(src_processor_proc_maps_linux_unittest_LDADD) $(LIBS)
+src/processor/src_processor_range_map_shrink_down_unittest-range_map_shrink_down_unittest.$(OBJEXT):  \
+	src/processor/$(am__dirstamp) \
+	src/processor/$(DEPDIR)/$(am__dirstamp)
+
+src/processor/range_map_shrink_down_unittest$(EXEEXT): $(src_processor_range_map_shrink_down_unittest_OBJECTS) $(src_processor_range_map_shrink_down_unittest_DEPENDENCIES) $(EXTRA_src_processor_range_map_shrink_down_unittest_DEPENDENCIES) src/processor/$(am__dirstamp)
+	@rm -f src/processor/range_map_shrink_down_unittest$(EXEEXT)
+	$(AM_V_CXXLD)$(CXXLINK) $(src_processor_range_map_shrink_down_unittest_OBJECTS) $(src_processor_range_map_shrink_down_unittest_LDADD) $(LIBS)
 src/processor/range_map_unittest.$(OBJEXT):  \
 	src/processor/$(am__dirstamp) \
 	src/processor/$(DEPDIR)/$(am__dirstamp)
@@ -4792,6 +4826,7 @@ distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote@src/processor/$(DEPDIR)/src_processor_minidump_unittest-synth_minidump.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@src/processor/$(DEPDIR)/src_processor_proc_maps_linux_unittest-proc_maps_linux.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@src/processor/$(DEPDIR)/src_processor_proc_maps_linux_unittest-proc_maps_linux_unittest.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@src/processor/$(DEPDIR)/src_processor_range_map_shrink_down_unittest-range_map_shrink_down_unittest.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@src/processor/$(DEPDIR)/src_processor_stackwalker_address_list_unittest-stackwalker_address_list_unittest.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@src/processor/$(DEPDIR)/src_processor_stackwalker_amd64_unittest-stackwalker_amd64_unittest.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@src/processor/$(DEPDIR)/src_processor_stackwalker_arm64_unittest-stackwalker_arm64_unittest.Po@am__quote@
@@ -6478,6 +6513,20 @@ src/processor/src_processor_proc_maps_linux_unittest-proc_maps_linux_unittest.ob
 @AMDEP_TRUE@@am__fastdepCXX_FALSE@	DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@
 @am__fastdepCXX_FALSE@	$(AM_V_CXX@am__nodep@)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(src_processor_proc_maps_linux_unittest_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -c -o src/processor/src_processor_proc_maps_linux_unittest-proc_maps_linux_unittest.obj `if test -f 'src/processor/proc_maps_linux_unittest.cc'; then $(CYGPATH_W) 'src/processor/proc_maps_linux_unittest.cc'; else $(CYGPATH_W) '$(srcdir)/src/processor/proc_maps_linux_unittest.cc'; fi`
 
+src/processor/src_processor_range_map_shrink_down_unittest-range_map_shrink_down_unittest.o: src/processor/range_map_shrink_down_unittest.cc
+@am__fastdepCXX_TRUE@	$(AM_V_CXX)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(src_processor_range_map_shrink_down_unittest_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -MT src/processor/src_processor_range_map_shrink_down_unittest-range_map_shrink_down_unittest.o -MD -MP -MF src/processor/$(DEPDIR)/src_processor_range_map_shrink_down_unittest-range_map_shrink_down_unittest.Tpo -c -o src/processor/src_processor_range_map_shrink_down_unittest-range_map_shrink_down_unittest.o `test -f 'src/processor/range_map_shrink_down_unittest.cc' || echo '$(srcdir)/'`src/processor/range_map_shrink_down_unittest.cc
+@am__fastdepCXX_TRUE@	$(AM_V_at)$(am__mv) src/processor/$(DEPDIR)/src_processor_range_map_shrink_down_unittest-range_map_shrink_down_unittest.Tpo src/processor/$(DEPDIR)/src_processor_range_map_shrink_down_unittest-range_map_shrink_down_unittest.Po
+@AMDEP_TRUE@@am__fastdepCXX_FALSE@	$(AM_V_CXX)source='src/processor/range_map_shrink_down_unittest.cc' object='src/processor/src_processor_range_map_shrink_down_unittest-range_map_shrink_down_unittest.o' libtool=no @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCXX_FALSE@	DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@
+@am__fastdepCXX_FALSE@	$(AM_V_CXX@am__nodep@)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(src_processor_range_map_shrink_down_unittest_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -c -o src/processor/src_processor_range_map_shrink_down_unittest-range_map_shrink_down_unittest.o `test -f 'src/processor/range_map_shrink_down_unittest.cc' || echo '$(srcdir)/'`src/processor/range_map_shrink_down_unittest.cc
+
+src/processor/src_processor_range_map_shrink_down_unittest-range_map_shrink_down_unittest.obj: src/processor/range_map_shrink_down_unittest.cc
+@am__fastdepCXX_TRUE@	$(AM_V_CXX)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(src_processor_range_map_shrink_down_unittest_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -MT src/processor/src_processor_range_map_shrink_down_unittest-range_map_shrink_down_unittest.obj -MD -MP -MF src/processor/$(DEPDIR)/src_processor_range_map_shrink_down_unittest-range_map_shrink_down_unittest.Tpo -c -o src/processor/src_processor_range_map_shrink_down_unittest-range_map_shrink_down_unittest.obj `if test -f 'src/processor/range_map_shrink_down_unittest.cc'; then $(CYGPATH_W) 'src/processor/range_map_shrink_down_unittest.cc'; else $(CYGPATH_W) '$(srcdir)/src/processor/range_map_shrink_down_unittest.cc'; fi`
+@am__fastdepCXX_TRUE@	$(AM_V_at)$(am__mv) src/processor/$(DEPDIR)/src_processor_range_map_shrink_down_unittest-range_map_shrink_down_unittest.Tpo src/processor/$(DEPDIR)/src_processor_range_map_shrink_down_unittest-range_map_shrink_down_unittest.Po
+@AMDEP_TRUE@@am__fastdepCXX_FALSE@	$(AM_V_CXX)source='src/processor/range_map_shrink_down_unittest.cc' object='src/processor/src_processor_range_map_shrink_down_unittest-range_map_shrink_down_unittest.obj' libtool=no @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCXX_FALSE@	DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@
+@am__fastdepCXX_FALSE@	$(AM_V_CXX@am__nodep@)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(src_processor_range_map_shrink_down_unittest_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -c -o src/processor/src_processor_range_map_shrink_down_unittest-range_map_shrink_down_unittest.obj `if test -f 'src/processor/range_map_shrink_down_unittest.cc'; then $(CYGPATH_W) 'src/processor/range_map_shrink_down_unittest.cc'; else $(CYGPATH_W) '$(srcdir)/src/processor/range_map_shrink_down_unittest.cc'; fi`
+
 src/common/src_processor_stackwalker_address_list_unittest-test_assembler.o: src/common/test_assembler.cc
 @am__fastdepCXX_TRUE@	$(AM_V_CXX)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(src_processor_stackwalker_address_list_unittest_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -MT src/common/src_processor_stackwalker_address_list_unittest-test_assembler.o -MD -MP -MF src/common/$(DEPDIR)/src_processor_stackwalker_address_list_unittest-test_assembler.Tpo -c -o src/common/src_processor_stackwalker_address_list_unittest-test_assembler.o `test -f 'src/common/test_assembler.cc' || echo '$(srcdir)/'`src/common/test_assembler.cc
 @am__fastdepCXX_TRUE@	$(AM_V_at)$(am__mv) src/common/$(DEPDIR)/src_processor_stackwalker_address_list_unittest-test_assembler.Tpo src/common/$(DEPDIR)/src_processor_stackwalker_address_list_unittest-test_assembler.Po
@@ -7630,6 +7679,13 @@ src/processor/proc_maps_linux_unittest.log: src/processor/proc_maps_linux_unitte
 	--log-file $$b.log --trs-file $$b.trs \
 	$(am__common_driver_flags) $(AM_LOG_DRIVER_FLAGS) $(LOG_DRIVER_FLAGS) -- $(LOG_COMPILE) \
 	"$$tst" $(AM_TESTS_FD_REDIRECT)
+src/processor/range_map_shrink_down_unittest.log: src/processor/range_map_shrink_down_unittest$(EXEEXT)
+	@p='src/processor/range_map_shrink_down_unittest$(EXEEXT)'; \
+	b='src/processor/range_map_shrink_down_unittest'; \
+	$(am__check_pre) $(LOG_DRIVER) --test-name "$$f" \
+	--log-file $$b.log --trs-file $$b.trs \
+	$(am__common_driver_flags) $(AM_LOG_DRIVER_FLAGS) $(LOG_DRIVER_FLAGS) -- $(LOG_COMPILE) \
+	"$$tst" $(AM_TESTS_FD_REDIRECT)
 src/processor/range_map_unittest.log: src/processor/range_map_unittest$(EXEEXT)
 	@p='src/processor/range_map_unittest$(EXEEXT)'; \
 	b='src/processor/range_map_unittest'; \