elf/tst-stringtable.c

   1 /* Unit test for ldconfig string tables.
   2    Copyright (C) 2020-2021 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4
   5    This program is free software; you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published
   7    by the Free Software Foundation; version 2 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program; if not, see <https://www.gnu.org/licenses/>.  */
  17
  18 #include <array_length.h>
  19 #include <stdlib.h>
  20 #include <string.h>
  21 #include <stringtable.h>
  22 #include <support/check.h>
  23 #include <support/support.h>
  24
  25 static int
  26 do_test (void)
  27 {
  28   /* Empty string table.  */
  29   {
  30     struct stringtable s = { 0, };
  31     struct stringtable_finalized f;
  32     stringtable_finalize (&s, &f);
  33     TEST_COMPARE_STRING (f.strings, "");
  34     TEST_COMPARE (f.size, 0);
  35     free (f.strings);
  36     stringtable_free (&s);
  37   }
  38
  39   /* String table with one empty string.  */
  40   {
  41     struct stringtable s = { 0, };
  42     struct stringtable_entry *e = stringtable_add (&s, "");
  43     TEST_COMPARE_STRING (e->string, "");
  44     TEST_COMPARE (e->length, 0);
  45     TEST_COMPARE (s.count, 1);
  46
  47     struct stringtable_finalized f;
  48     stringtable_finalize (&s, &f);
  49     TEST_COMPARE (e->offset, 0);
  50     TEST_COMPARE_STRING (f.strings, "");
  51     TEST_COMPARE (f.size, 1);
  52     free (f.strings);
  53     stringtable_free (&s);
  54   }
  55
  56   /* String table with one non-empty string.  */
  57   {
  58     struct stringtable s = { 0, };
  59     struct stringtable_entry *e = stringtable_add (&s, "name");
  60     TEST_COMPARE_STRING (e->string, "name");
  61     TEST_COMPARE (e->length, 4);
  62     TEST_COMPARE (s.count, 1);
  63
  64     struct stringtable_finalized f;
  65     stringtable_finalize (&s, &f);
  66     TEST_COMPARE (e->offset, 0);
  67     TEST_COMPARE_STRING (f.strings, "name");
  68     TEST_COMPARE (f.size, 5);
  69     free (f.strings);
  70     stringtable_free (&s);
  71   }
  72
  73   /* Two strings, one is a prefix of the other.  Tail-merging can only
  74      happen in one way in this case.  */
  75   {
  76     struct stringtable s = { 0, };
  77     struct stringtable_entry *suffix = stringtable_add (&s, "suffix");
  78     TEST_COMPARE_STRING (suffix->string, "suffix");
  79     TEST_COMPARE (suffix->length, 6);
  80     TEST_COMPARE (s.count, 1);
  81
  82     struct stringtable_entry *prefix
  83       = stringtable_add (&s, "prefix-suffix");
  84     TEST_COMPARE_STRING (prefix->string, "prefix-suffix");
  85     TEST_COMPARE (prefix->length, strlen ("prefix-suffix"));
  86     TEST_COMPARE (s.count, 2);
  87
  88     struct stringtable_finalized f;
  89     stringtable_finalize (&s, &f);
  90     TEST_COMPARE (prefix->offset, 0);
  91     TEST_COMPARE (suffix->offset, strlen ("prefix-"));
  92     TEST_COMPARE_STRING (f.strings, "prefix-suffix");
  93     TEST_COMPARE (f.size, sizeof ("prefix-suffix"));
  94     free (f.strings);
  95     stringtable_free (&s);
  96   }
  97
  98   /* String table with various shared prefixes.  Triggers hash
  99      resizing.  */
 100   {
 101     enum { count = 1500 };
 102     char *strings[2 * count];
 103     struct stringtable_entry *entries[2 * count];
 104     struct stringtable s = { 0, };
 105     for (int i = 0; i < count; ++i)
 106       {
 107         strings[i] = xasprintf ("%d", i);
 108         entries[i] = stringtable_add (&s, strings[i]);
 109         TEST_COMPARE (entries[i]->length, strlen (strings[i]));
 110         TEST_COMPARE_STRING (entries[i]->string, strings[i]);
 111         strings[i + count] = xasprintf ("prefix/%d", i);
 112         entries[i + count] = stringtable_add (&s, strings[i + count]);
 113         TEST_COMPARE (entries[i + count]->length, strlen (strings[i + count]));
 114         TEST_COMPARE_STRING (entries[i + count]->string, strings[i + count]);
 115       }
 116
 117     struct stringtable_finalized f;
 118     stringtable_finalize (&s, &f);
 119
 120     for (int i = 0; i < 2 * count; ++i)
 121       {
 122         TEST_COMPARE (entries[i]->length, strlen (strings[i]));
 123         TEST_COMPARE_STRING (entries[i]->string, strings[i]);
 124         TEST_COMPARE_STRING (f.strings + entries[i]->offset, strings[i]);
 125         free (strings[i]);
 126       }
 127
 128     free (f.strings);
 129     stringtable_free (&s);
 130   }
 131
 132   /* Verify that maximum tail merging happens.  */
 133   {
 134     struct stringtable s = { 0, };
 135     const char *strings[] = {
 136       "",
 137       "a",
 138       "b",
 139       "aa",
 140       "aaa",
 141       "aa",
 142       "bb",
 143       "b",
 144       "a",
 145       "ba",
 146       "baa",
 147     };
 148     struct stringtable_entry *entries[array_length (strings)];
 149     for (int i = 0; i < array_length (strings); ++i)
 150       entries[i] = stringtable_add (&s, strings[i]);
 151     for (int i = 0; i < array_length (strings); ++i)
 152       TEST_COMPARE_STRING (entries[i]->string, strings[i]);
 153
 154     struct stringtable_finalized f;
 155     stringtable_finalize (&s, &f);
 156
 157     /* There are only four different strings, "aaa", "ba", "baa",
 158        "bb".  The rest is shared in an unspecified fashion.  */
 159     TEST_COMPARE (f.size, 4 + 3 + 4 + 3);
 160
 161     for (int i = 0; i < array_length (strings); ++i)
 162       {
 163         TEST_COMPARE_STRING (entries[i]->string, strings[i]);
 164         TEST_COMPARE_STRING (f.strings + entries[i]->offset, strings[i]);
 165       }
 166
 167     free (f.strings);
 168     stringtable_free (&s);
 169   }
 170
 171   return 0;
 172 }
 173
 174 #include <support/test-driver.c>
 175
 176 /* Re-compile the string table implementation here.  It is not
 177    possible to link against the actual build because it was built for
 178    use in ldconfig.  */
 179 #define _(arg) arg
 180 #include "stringtable.c"
 181 #include "stringtable_free.c"