[PATCH 07/41] Add ordered_hash_map

[David Malcolm]

On Fri, 2020-01-10 at 09:22 -0700, Jeff Law wrote:
> On Wed, 2020-01-08 at 04:02 -0500, David Malcolm wrote:
> > Needs review.  This is used in many places in the analyzer.
> > msebor made some comments about the v1 version of this patch here:
> >   https://gcc.gnu.org/ml/gcc-patches/2019-12/msg00231.html
> > 
> > Changed in v5:
> > - updated copyright years to include 2020
> > 
> > This patch adds an ordered_hash_map template, which is similar to
> > hash_map, but preserves insertion order.
> > 
> > gcc/ChangeLog:
> > 	* Makefile.in (OBJS): Add ordered-hash-map-tests.o.
> > 	* ordered-hash-map-tests.cc: New file.
> > 	* ordered-hash-map.h: New file.
> > 	* selftest-run-tests.c (selftest::run_tests): Call
> > 	selftest::ordered_hash_map_tests_cc_tests.
> > 	* selftest.h (selftest::ordered_hash_map_tests_cc_tests): New
> > 	decl.
> There's nothing inherent in the data that would preclude us from
> using
> a standard container (ie, nothing with embedded GC based on our
> meeting
> Tuesday).

Correct: this doesn't support our GC, but doesn't need to for the uses
I'm making of it.

>   But there isn't an existing standard container with the
> right properties (based on email between you and Jon).  Right?

Correct; std::map uses Key ordering to build a red-black tree; I'm
using insertion ordering (not Key ordering), to get more deterministic
results in the face of ptr values that can change from under me.  It's
analogous to Python's OrderedDict, fwiw.

> Do you need a private assignment operator?

I added that in:
  https://gcc.gnu.org/ml/gcc-patches/2020-01/msg00518.html
to ensure that we don't erroneously use the compiler-generated one;
that's the latest version of this patch.

Dave