libctf, dedup: add deduplicator

This adds the core deduplicator that the ctf_link machinery calls
(possibly repeatedly) to link the CTF sections: it takes an array
of input ctf_file_t's and another array that indicates which entries in
the input array are parents of which other entries, and returns an array
of outputs.  The first output is always the ctf_file_t on which
ctf_link/ctf_dedup/etc was called: the other outputs are child dicts
that have the first output as their parent.

include/
	* ctf-api.h (CTF_LINK_SHARE_DUPLICATED): No longer unimplemented.
libctf/
	* ctf-impl.h (ctf_type_id_key): New, the key in the
	cd_id_to_file_t.
	(ctf_dedup): New, core deduplicator state.
	(ctf_file_t) <ctf_dedup>: New.
	<ctf_dedup_atoms>: New.
	<ctf_dedup_atoms_alloc>: New.
	(ctf_hash_type_id_key): New prototype.
	(ctf_hash_eq_type_id_key): Likewise.
	(ctf_dedup_atoms_init): Likewise.
	* ctf-hash.c (ctf_hash_eq_type_id_key): New.
	(ctf_dedup_atoms_init): Likewise.
	* ctf-create.c (ctf_serialize): Adjusted.
	(ctf_add_encoded): No longer static.
	(ctf_add_reftype): Likewise.
	* ctf-open.c (ctf_file_close): Destroy the
	ctf_dedup_atoms_alloc.
	* ctf-dedup.c: New file.
        * ctf-decls.h [!HAVE_DECL_STPCPY]: Add prototype.
	* configure.ac: Check for stpcpy.
	* Makefile.am: Add it.
	* Makefile.in: Regenerate.
        * config.h.in: Regenerate.
        * configure: Regenerate.

1 files changed, 34 insertions, 18 deletions

diff --git a/libctf/Makefile.in b/libctf/Makefile.in
index bc385278e09..78de09ba10a 100644
--- a/libctf/Makefile.in
+++ b/libctf/Makefile.in
@@ -166,18 +166,18 @@ am__DEPENDENCIES_1 =
 libctf_nobfd_la_DEPENDENCIES = $(am__DEPENDENCIES_1)
 am__libctf_nobfd_la_SOURCES_DIST = ctf-archive.c ctf-dump.c \
 	ctf-create.c ctf-decl.c ctf-error.c ctf-hash.c ctf-labels.c \
-	ctf-link.c ctf-lookup.c ctf-open.c ctf-sha1.c ctf-string.c \
-	ctf-subr.c ctf-types.c ctf-util.c ctf-qsort_r.c
+	ctf-dedup.c ctf-link.c ctf-lookup.c ctf-open.c ctf-sha1.c \
+	ctf-string.c ctf-subr.c ctf-types.c ctf-util.c ctf-qsort_r.c
 @NEED_CTF_QSORT_R_TRUE@am__objects_1 = libctf_nobfd_la-ctf-qsort_r.lo
 am_libctf_nobfd_la_OBJECTS = libctf_nobfd_la-ctf-archive.lo \
 	libctf_nobfd_la-ctf-dump.lo libctf_nobfd_la-ctf-create.lo \
 	libctf_nobfd_la-ctf-decl.lo libctf_nobfd_la-ctf-error.lo \
 	libctf_nobfd_la-ctf-hash.lo libctf_nobfd_la-ctf-labels.lo \
-	libctf_nobfd_la-ctf-link.lo libctf_nobfd_la-ctf-lookup.lo \
-	libctf_nobfd_la-ctf-open.lo libctf_nobfd_la-ctf-sha1.lo \
-	libctf_nobfd_la-ctf-string.lo libctf_nobfd_la-ctf-subr.lo \
-	libctf_nobfd_la-ctf-types.lo libctf_nobfd_la-ctf-util.lo \
-	$(am__objects_1)
+	libctf_nobfd_la-ctf-dedup.lo libctf_nobfd_la-ctf-link.lo \
+	libctf_nobfd_la-ctf-lookup.lo libctf_nobfd_la-ctf-open.lo \
+	libctf_nobfd_la-ctf-sha1.lo libctf_nobfd_la-ctf-string.lo \
+	libctf_nobfd_la-ctf-subr.lo libctf_nobfd_la-ctf-types.lo \
+	libctf_nobfd_la-ctf-util.lo $(am__objects_1)
 libctf_nobfd_la_OBJECTS = $(am_libctf_nobfd_la_OBJECTS)
 AM_V_lt = $(am__v_lt_@AM_V@)
 am__v_lt_ = $(am__v_lt_@AM_DEFAULT_V@)
@@ -191,18 +191,18 @@ libctf_nobfd_la_LINK = $(LIBTOOL) $(AM_V_lt) --tag=CC \
 @INSTALL_LIBBFD_TRUE@am_libctf_nobfd_la_rpath = -rpath $(libdir)
 am__DEPENDENCIES_2 = $(am__DEPENDENCIES_1)
 am__libctf_la_SOURCES_DIST = ctf-archive.c ctf-dump.c ctf-create.c \
-	ctf-decl.c ctf-error.c ctf-hash.c ctf-labels.c ctf-link.c \
-	ctf-lookup.c ctf-open.c ctf-sha1.c ctf-string.c ctf-subr.c \
-	ctf-types.c ctf-util.c ctf-qsort_r.c ctf-open-bfd.c
+	ctf-decl.c ctf-error.c ctf-hash.c ctf-labels.c ctf-dedup.c \
+	ctf-link.c ctf-lookup.c ctf-open.c ctf-sha1.c ctf-string.c \
+	ctf-subr.c ctf-types.c ctf-util.c ctf-qsort_r.c ctf-open-bfd.c
 @NEED_CTF_QSORT_R_TRUE@am__objects_2 = libctf_la-ctf-qsort_r.lo
 am__objects_3 = libctf_la-ctf-archive.lo libctf_la-ctf-dump.lo \
 	libctf_la-ctf-create.lo libctf_la-ctf-decl.lo \
 	libctf_la-ctf-error.lo libctf_la-ctf-hash.lo \
-	libctf_la-ctf-labels.lo libctf_la-ctf-link.lo \
-	libctf_la-ctf-lookup.lo libctf_la-ctf-open.lo \
-	libctf_la-ctf-sha1.lo libctf_la-ctf-string.lo \
-	libctf_la-ctf-subr.lo libctf_la-ctf-types.lo \
-	libctf_la-ctf-util.lo $(am__objects_2)
+	libctf_la-ctf-labels.lo libctf_la-ctf-dedup.lo \
+	libctf_la-ctf-link.lo libctf_la-ctf-lookup.lo \
+	libctf_la-ctf-open.lo libctf_la-ctf-sha1.lo \
+	libctf_la-ctf-string.lo libctf_la-ctf-subr.lo \
+	libctf_la-ctf-types.lo libctf_la-ctf-util.lo $(am__objects_2)
 am_libctf_la_OBJECTS = $(am__objects_3) libctf_la-ctf-open-bfd.lo
 libctf_la_OBJECTS = $(am_libctf_la_OBJECTS)
 libctf_la_LINK = $(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) \
@@ -457,9 +457,9 @@ libctf_nobfd_la_LIBADD = @SHARED_LIBADD@ $(ZLIB)
 libctf_nobfd_la_LDFLAGS = -version-info 0:0:0 @SHARED_LDFLAGS@ @VERSION_FLAGS@
 libctf_nobfd_la_CPPFLAGS = $(AM_CPPFLAGS) -DNOBFD=1
 libctf_nobfd_la_SOURCES = ctf-archive.c ctf-dump.c ctf-create.c \
-	ctf-decl.c ctf-error.c ctf-hash.c ctf-labels.c ctf-link.c \
-	ctf-lookup.c ctf-open.c ctf-sha1.c ctf-string.c ctf-subr.c \
-	ctf-types.c ctf-util.c $(am__append_1)
+	ctf-decl.c ctf-error.c ctf-hash.c ctf-labels.c ctf-dedup.c \
+	ctf-link.c ctf-lookup.c ctf-open.c ctf-sha1.c ctf-string.c \
+	ctf-subr.c ctf-types.c ctf-util.c $(am__append_1)
 libctf_la_LIBADD = @BFD_LIBADD@ $(libctf_nobfd_la_LIBADD)
 libctf_la_CPPFLAGS = $(AM_CPPFLAGS) -DNOBFD=0
 libctf_la_DEPENDENCIES = @BFD_DEPENDENCIES@
@@ -581,6 +581,7 @@ distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libctf_la-ctf-archive.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libctf_la-ctf-create.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libctf_la-ctf-decl.Plo@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libctf_la-ctf-dedup.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libctf_la-ctf-dump.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libctf_la-ctf-error.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libctf_la-ctf-hash.Plo@am__quote@
@@ -598,6 +599,7 @@ distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libctf_nobfd_la-ctf-archive.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libctf_nobfd_la-ctf-create.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libctf_nobfd_la-ctf-decl.Plo@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libctf_nobfd_la-ctf-dedup.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libctf_nobfd_la-ctf-dump.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libctf_nobfd_la-ctf-error.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libctf_nobfd_la-ctf-hash.Plo@am__quote@
@@ -682,6 +684,13 @@ libctf_nobfd_la-ctf-labels.lo: ctf-labels.c
 @AMDEP_TRUE@@am__fastdepCC_FALSE@	DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
 @am__fastdepCC_FALSE@	$(AM_V_CC@am__nodep@)$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libctf_nobfd_la_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o libctf_nobfd_la-ctf-labels.lo `test -f 'ctf-labels.c' || echo '$(srcdir)/'`ctf-labels.c
 
+libctf_nobfd_la-ctf-dedup.lo: ctf-dedup.c
+@am__fastdepCC_TRUE@	$(AM_V_CC)$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libctf_nobfd_la_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT libctf_nobfd_la-ctf-dedup.lo -MD -MP -MF $(DEPDIR)/libctf_nobfd_la-ctf-dedup.Tpo -c -o libctf_nobfd_la-ctf-dedup.lo `test -f 'ctf-dedup.c' || echo '$(srcdir)/'`ctf-dedup.c
+@am__fastdepCC_TRUE@	$(AM_V_at)$(am__mv) $(DEPDIR)/libctf_nobfd_la-ctf-dedup.Tpo $(DEPDIR)/libctf_nobfd_la-ctf-dedup.Plo
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	$(AM_V_CC)source='ctf-dedup.c' object='libctf_nobfd_la-ctf-dedup.lo' libtool=yes @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
+@am__fastdepCC_FALSE@	$(AM_V_CC@am__nodep@)$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libctf_nobfd_la_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o libctf_nobfd_la-ctf-dedup.lo `test -f 'ctf-dedup.c' || echo '$(srcdir)/'`ctf-dedup.c
+
 libctf_nobfd_la-ctf-link.lo: ctf-link.c
 @am__fastdepCC_TRUE@	$(AM_V_CC)$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libctf_nobfd_la_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT libctf_nobfd_la-ctf-link.lo -MD -MP -MF $(DEPDIR)/libctf_nobfd_la-ctf-link.Tpo -c -o libctf_nobfd_la-ctf-link.lo `test -f 'ctf-link.c' || echo '$(srcdir)/'`ctf-link.c
 @am__fastdepCC_TRUE@	$(AM_V_at)$(am__mv) $(DEPDIR)/libctf_nobfd_la-ctf-link.Tpo $(DEPDIR)/libctf_nobfd_la-ctf-link.Plo
@@ -794,6 +803,13 @@ libctf_la-ctf-labels.lo: ctf-labels.c
 @AMDEP_TRUE@@am__fastdepCC_FALSE@	DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
 @am__fastdepCC_FALSE@	$(AM_V_CC@am__nodep@)$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libctf_la_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o libctf_la-ctf-labels.lo `test -f 'ctf-labels.c' || echo '$(srcdir)/'`ctf-labels.c
 
+libctf_la-ctf-dedup.lo: ctf-dedup.c
+@am__fastdepCC_TRUE@	$(AM_V_CC)$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libctf_la_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT libctf_la-ctf-dedup.lo -MD -MP -MF $(DEPDIR)/libctf_la-ctf-dedup.Tpo -c -o libctf_la-ctf-dedup.lo `test -f 'ctf-dedup.c' || echo '$(srcdir)/'`ctf-dedup.c
+@am__fastdepCC_TRUE@	$(AM_V_at)$(am__mv) $(DEPDIR)/libctf_la-ctf-dedup.Tpo $(DEPDIR)/libctf_la-ctf-dedup.Plo
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	$(AM_V_CC)source='ctf-dedup.c' object='libctf_la-ctf-dedup.lo' libtool=yes @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
+@am__fastdepCC_FALSE@	$(AM_V_CC@am__nodep@)$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libctf_la_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o libctf_la-ctf-dedup.lo `test -f 'ctf-dedup.c' || echo '$(srcdir)/'`ctf-dedup.c
+
 libctf_la-ctf-link.lo: ctf-link.c
 @am__fastdepCC_TRUE@	$(AM_V_CC)$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libctf_la_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT libctf_la-ctf-link.lo -MD -MP -MF $(DEPDIR)/libctf_la-ctf-link.Tpo -c -o libctf_la-ctf-link.lo `test -f 'ctf-link.c' || echo '$(srcdir)/'`ctf-link.c
 @am__fastdepCC_TRUE@	$(AM_V_at)$(am__mv) $(DEPDIR)/libctf_la-ctf-link.Tpo $(DEPDIR)/libctf_la-ctf-link.Plo