elf: Implement a string table for ldconfig, with tail merging

This will be used in ldconfig to reduce the ld.so.cache size slightly.

Tail merging is an optimization where a pointer points into another
string if the first string is a suffix of the second string.

The hash function FNV-1a was chosen because it is simple and achieves
good dispersion even for short strings (so that the hash table bucket
count can be a power of two).  It is clearly superior to the hsearch
hash and the ELF hash in this regard.

The hash table uses chaining for collision resolution.

Reviewed-by: Adhemerval Zanella  <adhemerval.zanella@linaro.org>

1 files changed, 33 insertions, 0 deletions

diff --git a/elf/stringtable_free.c b/elf/stringtable_free.c
new file mode 100644
index 0000000000..8588a25470
--- /dev/null
+++ b/elf/stringtable_free.c
@@ -0,0 +1,33 @@
+/* String tables for ld.so.cache construction.  Deallocation (for tests only).
+   Copyright (C) 2020 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published
+   by the Free Software Foundation; version 2 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, see <https://www.gnu.org/licenses/>.  */
+
+#include <stdlib.h>
+#include <stringtable.h>
+
+void
+stringtable_free (struct stringtable *table)
+{
+  for (uint32_t i = 0; i < table->allocated; ++i)
+    for (struct stringtable_entry *e = table->entries[i]; e != NULL; )
+      {
+        struct stringtable_entry *next = e->next;
+        free (e);
+        e = next;
+      }
+  free (table->entries);
+  *table = (struct stringtable) { 0, };
+}