From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qt1-x844.google.com (mail-qt1-x844.google.com [IPv6:2607:f8b0:4864:20::844]) by sourceware.org (Postfix) with ESMTPS id 0229D3857008 for ; Tue, 20 Oct 2020 14:26:02 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 0229D3857008 Received: by mail-qt1-x844.google.com with SMTP id p88so1294121qtd.12 for ; Tue, 20 Oct 2020 07:26:02 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:references:autocrypt:subject:message-id :date:user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=CJjdb8fFMph4uT/U5HZP0WMvC5PIrvEyIwfKociQbrA=; b=hMGbK51VaFNtDen6EeKfUu5sqj2rvGH+Qeh2TrRr3Rmcu5RYpI+sAuKK6hoAQR+BxW M6uOuYpRt1pDNYBn6tEubuzrtzYNbyItIGSD8D2foOplEAXSma7giQTsgGvS8eTQ8GKL U1ia9dAGH+xxQMF5cBrMWCNid3mRe5X9I7uO98+0xoHcARsKhdrXF/4sUlPwS9uZPrkP /jLNvnMHvedAM416cGCMG5Xg5OMswT5StY8DyJHpGPG0+dBdanhywqJQGC31nTg1NL00 llyztpx+Zax5M5auwuNxW0/ah19uqIEjjlWQ1l5ruzv4INCMCj4iwTkSDzpUnDQ5yu2t iKlg== X-Gm-Message-State: AOAM530dQ/wgcL2oV9C7SW9Kb4tWGR0tuIqIXgDLvpSwOZ2MUnaYP2YF pzRonOSNd9gUr3V8clNt/9vyuw== X-Google-Smtp-Source: ABdhPJz/Q79PaC78AgwOoIKgS44sbP6jtXwQnsrg5QFzKD4zOgWTuPVRx4Rk8ZqXFDccQXmS5AXK9Q== X-Received: by 2002:ac8:1c1b:: with SMTP id a27mr2712682qtk.157.1603203962168; Tue, 20 Oct 2020 07:26:02 -0700 (PDT) Received: from [192.168.1.4] ([177.194.48.209]) by smtp.googlemail.com with ESMTPSA id r17sm838053qtc.22.2020.10.20.07.26.00 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 20 Oct 2020 07:26:01 -0700 (PDT) From: Adhemerval Zanella To: libc-alpha@sourceware.org, Florian Weimer References: Autocrypt: addr=adhemerval.zanella@linaro.org; prefer-encrypt=mutual; keydata= mQINBFcVGkoBEADiQU2x/cBBmAVf5C2d1xgz6zCnlCefbqaflUBw4hB/bEME40QsrVzWZ5Nq 8kxkEczZzAOKkkvv4pRVLlLn/zDtFXhlcvQRJ3yFMGqzBjofucOrmdYkOGo0uCaoJKPT186L NWp53SACXguFJpnw4ODI64ziInzXQs/rUJqrFoVIlrPDmNv/LUv1OVPKz20ETjgfpg8MNwG6 iMizMefCl+RbtXbIEZ3TE/IaDT/jcOirjv96lBKrc/pAL0h/O71Kwbbp43fimW80GhjiaN2y WGByepnkAVP7FyNarhdDpJhoDmUk9yfwNuIuESaCQtfd3vgKKuo6grcKZ8bHy7IXX1XJj2X/ BgRVhVgMHAnDPFIkXtP+SiarkUaLjGzCz7XkUn4XAGDskBNfbizFqYUQCaL2FdbW3DeZqNIa nSzKAZK7Dm9+0VVSRZXP89w71Y7JUV56xL/PlOE+YKKFdEw+gQjQi0e+DZILAtFjJLoCrkEX w4LluMhYX/X8XP6/C3xW0yOZhvHYyn72sV4yJ1uyc/qz3OY32CRy+bwPzAMAkhdwcORA3JPb kPTlimhQqVgvca8m+MQ/JFZ6D+K7QPyvEv7bQ7M+IzFmTkOCwCJ3xqOD6GjX3aphk8Sr0dq3 4Awlf5xFDAG8dn8Uuutb7naGBd/fEv6t8dfkNyzj6yvc4jpVxwARAQABtElBZGhlbWVydmFs IFphbmVsbGEgTmV0dG8gKExpbmFybyBWUE4gS2V5KSA8YWRoZW1lcnZhbC56YW5lbGxhQGxp bmFyby5vcmc+iQI3BBMBCAAhBQJXFRpKAhsDBQsJCAcDBRUKCQgLBRYCAwEAAh4BAheAAAoJ EKqx7BSnlIjv0e8P/1YOYoNkvJ+AJcNUaM5a2SA9oAKjSJ/M/EN4Id5Ow41ZJS4lUA0apSXW NjQg3VeVc2RiHab2LIB4MxdJhaWTuzfLkYnBeoy4u6njYcaoSwf3g9dSsvsl3mhtuzm6aXFH /Qsauav77enJh99tI4T+58rp0EuLhDsQbnBic/ukYNv7sQV8dy9KxA54yLnYUFqH6pfH8Lly sTVAMyi5Fg5O5/hVV+Z0Kpr+ZocC1YFJkTsNLAW5EIYSP9ftniqaVsim7MNmodv/zqK0IyDB GLLH1kjhvb5+6ySGlWbMTomt/or/uvMgulz0bRS+LUyOmlfXDdT+t38VPKBBVwFMarNuREU2 69M3a3jdTfScboDd2ck1u7l+QbaGoHZQ8ZNUrzgObltjohiIsazqkgYDQzXIMrD9H19E+8fw kCNUlXxjEgH/Kg8DlpoYJXSJCX0fjMWfXywL6ZXc2xyG/hbl5hvsLNmqDpLpc1CfKcA0BkK+ k8R57fr91mTCppSwwKJYO9T+8J+o4ho/CJnK/jBy1pWKMYJPvvrpdBCWq3MfzVpXYdahRKHI ypk8m4QlRlbOXWJ3TDd/SKNfSSrWgwRSg7XCjSlR7PNzNFXTULLB34sZhjrN6Q8NQZsZnMNs TX8nlGOVrKolnQPjKCLwCyu8PhllU8OwbSMKskcD1PSkG6h3r0AquQINBFcVGkoBEACgAdbR Ck+fsfOVwT8zowMiL3l9a2DP3Eeak23ifdZG+8Avb/SImpv0UMSbRfnw/N81IWwlbjkjbGTu oT37iZHLRwYUFmA8fZX0wNDNKQUUTjN6XalJmvhdz9l71H3WnE0wneEM5ahu5V1L1utUWTyh VUwzX1lwJeV3vyrNgI1kYOaeuNVvq7npNR6t6XxEpqPsNc6O77I12XELic2+36YibyqlTJIQ V1SZEbIy26AbC2zH9WqaKyGyQnr/IPbTJ2Lv0dM3RaXoVf+CeK7gB2B+w1hZummD21c1Laua +VIMPCUQ+EM8W9EtX+0iJXxI+wsztLT6vltQcm+5Q7tY+HFUucizJkAOAz98YFucwKefbkTp eKvCfCwiM1bGatZEFFKIlvJ2QNMQNiUrqJBlW9nZp/k7pbG3oStOjvawD9ZbP9e0fnlWJIsj 6c7pX354Yi7kxIk/6gREidHLLqEb/otuwt1aoMPg97iUgDV5mlNef77lWE8vxmlY0FBWIXuZ yv0XYxf1WF6dRizwFFbxvUZzIJp3spAao7jLsQj1DbD2s5+S1BW09A0mI/1DjB6EhNN+4bDB SJCOv/ReK3tFJXuj/HbyDrOdoMt8aIFbe7YFLEExHpSk+HgN05Lg5TyTro8oW7TSMTk+8a5M kzaH4UGXTTBDP/g5cfL3RFPl79ubXwARAQABiQIfBBgBCAAJBQJXFRpKAhsMAAoJEKqx7BSn lIjvI/8P/jg0jl4Tbvg3B5kT6PxJOXHYu9OoyaHLcay6Cd+ZrOd1VQQCbOcgLFbf4Yr+rE9l mYsY67AUgq2QKmVVbn9pjvGsEaz8UmfDnz5epUhDxC6yRRvY4hreMXZhPZ1pbMa6A0a/WOSt AgFj5V6Z4dXGTM/lNManr0HjXxbUYv2WfbNt3/07Db9T+GZkpUotC6iknsTA4rJi6u2ls0W9 1UIvW4o01vb4nZRCj4rni0g6eWoQCGoVDk/xFfy7ZliR5B+3Z3EWRJcQskip/QAHjbLa3pml xAZ484fVxgeESOoaeC9TiBIp0NfH8akWOI0HpBCiBD5xaCTvR7ujUWMvhsX2n881r/hNlR9g fcE6q00qHSPAEgGr1bnFv74/1vbKtjeXLCcRKk3Ulw0bY1OoDxWQr86T2fZGJ/HIZuVVBf3+ gaYJF92GXFynHnea14nFFuFgOni0Mi1zDxYH/8yGGBXvo14KWd8JOW0NJPaCDFJkdS5hu0VY 7vJwKcyHJGxsCLU+Et0mryX8qZwqibJIzu7kUJQdQDljbRPDFd/xmGUFCQiQAncSilYOcxNU EMVCXPAQTteqkvA+gNqSaK1NM9tY0eQ4iJpo+aoX8HAcn4sZzt2pfUB9vQMTBJ2d4+m/qO6+ cFTAceXmIoFsN8+gFN3i8Is3u12u8xGudcBPvpoy4OoG Subject: Re: [PATCH 24/28] elf: Implement a string table for ldconfig, with tail merging Message-ID: <2fa948f4-4cc9-750d-3282-7df1d4dd4498@linaro.org> Date: Tue, 20 Oct 2020 11:25:59 -0300 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.10.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-14.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 20 Oct 2020 14:26:06 -0000 On 01/10/2020 13:34, Florian Weimer via Libc-alpha wrote: > This will be used in ldconfig to reduce the ld.so.cache size slightly. Could you extend the commit message to explain why the 32-bit FNV-1a hash is used and how the hash table is organized (how collisions are handled, expected memory usage, strategy used to increase/decrease the bucket size)? It could help also to explain the usercase a bit more, the 'tail merging' is not straightforward to understand without dig deep in the code. Also why kind of cache size decrease do you expect by using strategy? > --- > elf/Makefile | 2 +- > elf/stringtable.c | 201 +++++++++++++++++++++++++++++++++++++++++ > elf/stringtable.h | 61 +++++++++++++ > elf/stringtable_free.c | 32 +++++++ > elf/tst-stringtable.c | 140 ++++++++++++++++++++++++++++ > 5 files changed, 435 insertions(+), 1 deletion(-) > create mode 100644 elf/stringtable.c > create mode 100644 elf/stringtable.h > create mode 100644 elf/stringtable_free.c > create mode 100644 elf/tst-stringtable.c > > diff --git a/elf/Makefile b/elf/Makefile > index 2c36b08c73..ad50a3e16e 100644 > --- a/elf/Makefile > +++ b/elf/Makefile > @@ -172,7 +172,7 @@ tests-container := \ > > tests := tst-tls9 tst-leaks1 \ > tst-array1 tst-array2 tst-array3 tst-array4 tst-array5 \ > - tst-auxv > + tst-auxv tst-stringtable > tests-internal := tst-tls1 tst-tls2 $(tests-static-internal) > tests-static := $(tests-static-normal) $(tests-static-internal) > > diff --git a/elf/stringtable.c b/elf/stringtable.c > new file mode 100644 > index 0000000000..f9ade50249 > --- /dev/null > +++ b/elf/stringtable.c > @@ -0,0 +1,201 @@ > +/* String tables for ld.so.cache construction. Implementation. This file misses the Copyright year. > + 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 . */ > + > +#include > +#include > +#include > +#include > +#include > +#include > +#include > + > +static void > +stringtable_init (struct stringtable *table) > +{ > + table->count = 0; > + table->allocated = 16; > + table->entries = xcalloc (table->allocated, sizeof (table->entries[0])); > +} > + Why 16 elements as initial size? > +/* 32-bit FNV-1a hash function. */ > +static uint32_t > +fnv1a (const char *string, size_t length) > +{ > + const unsigned char *p = (const unsigned char *) string; > + uint32_t hash = 2166136261U; > + for (size_t i = 0; i < length; ++i) > + { > + hash ^= p[i]; > + hash *= 16777619U; > + } > + return hash; > +} Why fnv1a was chosen? > + > +/* Double the capacity of the hash table. */ > +static void > +stringtable_rehash (struct stringtable *table) > +{ > + /* Cannot overflow because the old allocation size (in bytes) is > + larger. */ > + uint32_t new_allocated = table->allocated * 2; > + struct stringtable_entry **new_entries > + = xcalloc (new_allocated, sizeof (table->entries[0])); > + > + uint32_t mask = new_allocated - 1; > + 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; > + uint32_t hash = fnv1a (e->string, e->length); > + uint32_t new_index = hash & mask; > + e->next = new_entries[new_index]; > + new_entries[new_index] = e; > + e = next; > + } > + > + free (table->entries); > + table->entries = new_entries; > + table->allocated = new_allocated; > +} > + > +struct stringtable_entry * > +stringtable_intern (struct stringtable *table, const char *string) > +{ > + if (table->allocated == 0) > + stringtable_init (table); How this could happen? Is it expect the caller to set 'allocated' explicitly? > + > + size_t length = strlen (string); > + if (length > (1U << 30)) > + error (EXIT_FAILURE, 0, _("String table string is too long")); > + uint32_t hash = fnv1a (string, length); > + > + /* Return a previously-existing entry. */ > + for (struct stringtable_entry *e > + = table->entries[hash & (table->allocated - 1)]; > + e != NULL; e = e->next) > + if (e->length == length && memcmp (e->string, string, length) == 0) > + return e; > + > + /* Increase the size of the table if necessary. Keep utilization > + below two thirds. */ > + if (table->count >= (1U << 30)) > + error (EXIT_FAILURE, 0, _("String table has too many entries")); > + if (table->count * 3 > table->allocated * 2) > + stringtable_rehash (table); > + > + /* Add the new table entry. */ > + ++table->count; > + struct stringtable_entry *e > + = xmalloc (offsetof (struct stringtable_entry, string) + length + 1); > + uint32_t index = hash & (table->allocated - 1); > + e->next = table->entries[index]; > + table->entries[index] = e; > + e->length = length; > + e->offset = 0; > + memcpy (e->string, string, length + 1); > + return e; > +} > + > +/* Sort reversed strings in lexicographic order. This is used for tail > + merging. */ > +static int > +finalize_compare (const void *l, const void *r) > +{ > + struct stringtable_entry *left = *(struct stringtable_entry **) l; > + struct stringtable_entry *right = *(struct stringtable_entry **) r; > + size_t to_compare; > + if (left->length < right->length) > + to_compare = left->length; > + else > + to_compare = right->length; > + for (ssize_t i = to_compare - 1; i >= 0; --i) > + { > + unsigned char lch = left->string[i]; > + unsigned char rch = right->string[i]; > + if (lch != rch) > + return lch - rch; > + } > + if (left->length == right->length) > + return 0; > + else if (left->length < right->length) > + /* Longer strings should come first. */ > + return 1; > + else > + return -1; > +} Ok. > + > +void > +stringtable_finalize (struct stringtable *table, > + struct stringtable_finalized *result) > +{ > + if (table->count == 0) > + { > + result->strings = xstrdup (""); > + result->size = 0; > + return; > + } > + > + /* Optimize the order of the strings. */ > + struct stringtable_entry **array = xcalloc (table->count, sizeof (*array)); > + { > + size_t j = 0; > + for (uint32_t i = 0; i < table->allocated; ++i) > + for (struct stringtable_entry *e = table->entries[i]; e != NULL; > + e = e->next) > + { > + array[j] = e; > + ++j; > + } > + assert (j == table->count); > + } > + qsort (array, table->count, sizeof (*array), finalize_compare); > + > + /* Assign offsets, using table sharing if possible. */ > + array[0]->offset = 0; > + for (uint32_t j = 1; j < table->count; ++j) > + { > + struct stringtable_entry *previous = array[j - 1]; > + struct stringtable_entry *current = array[j]; > + if (previous->length >= current->length > + && memcmp (&previous->string[previous->length - current->length], > + current->string, current->length) == 0) > + current->offset = (previous->offset + previous->length > + - current->length); > + else if (__builtin_add_overflow (previous->offset, > + previous->length + 1, > + ¤t->offset)) > + error (EXIT_FAILURE, 0, _("String table is too large")); > + } > + > + /* Allocate the result string. */ > + { > + struct stringtable_entry *last = array[table->count - 1]; > + if (__builtin_add_overflow (last->offset, last->length + 1, > + &result->size)) > + error (EXIT_FAILURE, 0, _("String table is too large")); > + } > + /* The strings are copied from the hash table, so the array is no > + longer needed. */ > + free (array); > + result->strings = xcalloc (result->size, 1); > + > + /* Copy the strings. */ > + for (uint32_t i = 0; i < table->allocated; ++i) > + for (struct stringtable_entry *e = table->entries[i]; e != NULL; > + e = e->next) > + if (result->strings[e->offset] == '\0') > + memcpy (&result->strings[e->offset], e->string, e->length + 1); > +} Ok, I guess allocating a new stringtable_finalized should be simpler than operating the table itself. > diff --git a/elf/stringtable.h b/elf/stringtable.h > new file mode 100644 > index 0000000000..e35b6c67fd > --- /dev/null > +++ b/elf/stringtable.h > @@ -0,0 +1,61 @@ > +/* String tables for ld.so.cache construction. > + 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 . */ > + > +#ifndef _STRINGTABLE_H > +#define _STRINGTABLE_H > + > +#include > +#include > + > +/* An entry in the string table. Only the length and string fields are > + expected to be used outside the string table code. */ > +struct stringtable_entry > +{ > + struct stringtable_entry *next; /* For collision resolution. */ > + uint32_t length; /* Length of then string. */ > + uint32_t offset; /* From start of finalized table. */ > + char string[]; /* Null-terminated string. */ > +}; > + > +/* A string table. Zero-initialization produces a valid atable. */ > +struct stringtable > +{ > + struct stringtable_entry **entries; > + uint32_t count; /* Number of elements in the table. */ > + uint32_t allocated; /* Length of the entries array. */ > +}; > + > +/* Adds STRING to TABLE. May return the address of an existing entry. */ > +struct stringtable_entry *stringtable_intern (struct stringtable *table, > + const char *string); I think this name is confusing, why not just 'stringtable_add' or 'stringtable_add_element'? > + > +/* Result of stringtable_finalize. SIZE bytes at STRINGS should be > + written to the file. */ > +struct stringtable_finalized > +{ > + char *strings; > + size_t size; > +}; > + > +/* Assigns offsets to string table entries and computes the serialized > + form of the string table. */ > +void stringtable_finalize (struct stringtable *table, > + struct stringtable_finalized *result); > + > +/* Deallocate the string table (but not the TABLE pointer itself). */ > +void stringtable_free (struct stringtable *table); > + > +#endif /* _STRINGTABLE_H */ > diff --git a/elf/stringtable_free.c b/elf/stringtable_free.c > new file mode 100644 > index 0000000000..0e5296e429 > --- /dev/null > +++ b/elf/stringtable_free.c > @@ -0,0 +1,32 @@ > +/* String tables for ld.so.cache construction. Deallocation (for tests only). > + 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 . */ > + > +#include > +#include > + > +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, }; > +} Ok. > diff --git a/elf/tst-stringtable.c b/elf/tst-stringtable.c > new file mode 100644 > index 0000000000..78ca5434df > --- /dev/null > +++ b/elf/tst-stringtable.c > @@ -0,0 +1,140 @@ > +/* Unit test for ldconfig string tables. > + 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 . */ > + > +#include > +#include > +#include > +#include > +#include > + > +static int > +do_test (void) > +{ > + /* Empty string table. */ > + { > + struct stringtable s = { 0, }; > + struct stringtable_finalized f; > + stringtable_finalize (&s, &f); > + TEST_COMPARE_STRING (f.strings, ""); > + TEST_COMPARE (f.size, 0); > + free (f.strings); > + stringtable_free (&s); > + } > + > + /* String table with one empty string. */ > + { > + struct stringtable s = { 0, }; > + struct stringtable_entry *e = stringtable_intern (&s, ""); > + TEST_COMPARE_STRING (e->string, ""); > + TEST_COMPARE (e->length, 0); > + TEST_COMPARE (s.count, 1); > + > + struct stringtable_finalized f; > + stringtable_finalize (&s, &f); > + TEST_COMPARE (e->offset, 0); > + TEST_COMPARE_STRING (f.strings, ""); > + TEST_COMPARE (f.size, 1); > + free (f.strings); > + stringtable_free (&s); > + } > + > + /* String table with one non-empty string. */ > + { > + struct stringtable s = { 0, }; > + struct stringtable_entry *e = stringtable_intern (&s, "name"); > + TEST_COMPARE_STRING (e->string, "name"); > + TEST_COMPARE (e->length, 4); > + TEST_COMPARE (s.count, 1); > + > + struct stringtable_finalized f; > + stringtable_finalize (&s, &f); > + TEST_COMPARE (e->offset, 0); > + TEST_COMPARE_STRING (f.strings, "name"); > + TEST_COMPARE (f.size, 5); > + free (f.strings); > + stringtable_free (&s); > + } > + > + /* Two strings, one is a prefix of the other. Tail-merging can only > + happen in one way in this case. */ > + { > + struct stringtable s = { 0, }; > + struct stringtable_entry *suffix = stringtable_intern (&s, "suffix"); > + TEST_COMPARE_STRING (suffix->string, "suffix"); > + TEST_COMPARE (suffix->length, 6); > + TEST_COMPARE (s.count, 1); > + > + struct stringtable_entry *prefix > + = stringtable_intern (&s, "prefix-suffix"); > + TEST_COMPARE_STRING (prefix->string, "prefix-suffix"); > + TEST_COMPARE (prefix->length, strlen ("prefix-suffix")); > + TEST_COMPARE (s.count, 2); > + > + struct stringtable_finalized f; > + stringtable_finalize (&s, &f); > + TEST_COMPARE (prefix->offset, 0); > + TEST_COMPARE (suffix->offset, strlen ("prefix-")); > + TEST_COMPARE_STRING (f.strings, "prefix-suffix"); > + TEST_COMPARE (f.size, sizeof ("prefix-suffix")); > + free (f.strings); > + stringtable_free (&s); > + } > + > + /* String table with various shared prefixes. Triggers hash > + resizing. */ > + { > + enum { count = 1500 }; > + char *strings[2 * count]; > + struct stringtable_entry *entries[2 * count]; > + struct stringtable s = { 0, }; > + for (int i = 0; i < count; ++i) > + { > + strings[i] = xasprintf ("%d", i); > + entries[i] = stringtable_intern (&s, strings[i]); > + TEST_COMPARE (entries[i]->length, strlen (strings[i])); > + TEST_COMPARE_STRING (entries[i]->string, strings[i]); > + strings[i + count] = xasprintf ("prefix/%d", i); > + entries[i + count] = stringtable_intern (&s, strings[i + count]); > + TEST_COMPARE (entries[i + count]->length, strlen (strings[i + count])); > + TEST_COMPARE_STRING (entries[i + count]->string, strings[i + count]); > + } > + > + struct stringtable_finalized f; > + stringtable_finalize (&s, &f); > + > + for (int i = 0; i < 2 * count; ++i) > + { > + TEST_COMPARE (entries[i]->length, strlen (strings[i])); > + TEST_COMPARE_STRING (entries[i]->string, strings[i]); > + TEST_COMPARE_STRING (f.strings + entries[i]->offset, strings[i]); > + free (strings[i]); > + } > + > + free (f.strings); > + stringtable_free (&s); > + } > + > + return 0; > +} > + > +#include > + > +/* Re-compile the string table implementation here. It is not > + possible to link against the actual build because it was built for > + use in ldconfig. */ > +#define _(arg) arg > +#include "stringtable.c" > +#include "stringtable_free.c" > Ok.