125b3c049e70834cf33790a28643ab058b507b35cBen Cheng/* Generic string table handling. 225b3c049e70834cf33790a28643ab058b507b35cBen Cheng Copyright (C) 2000, 2001, 2002, 2005 Red Hat, Inc. 303333823c75a1c1887e923828113a1b0fd12020cElliott Hughes This file is part of elfutils. 425b3c049e70834cf33790a28643ab058b507b35cBen Cheng Written by Ulrich Drepper <drepper@redhat.com>, 2000. 525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 603333823c75a1c1887e923828113a1b0fd12020cElliott Hughes This file is free software; you can redistribute it and/or modify 703333823c75a1c1887e923828113a1b0fd12020cElliott Hughes it under the terms of either 825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 903333823c75a1c1887e923828113a1b0fd12020cElliott Hughes * the GNU Lesser General Public License as published by the Free 1003333823c75a1c1887e923828113a1b0fd12020cElliott Hughes Software Foundation; either version 3 of the License, or (at 1103333823c75a1c1887e923828113a1b0fd12020cElliott Hughes your option) any later version 1203333823c75a1c1887e923828113a1b0fd12020cElliott Hughes 1303333823c75a1c1887e923828113a1b0fd12020cElliott Hughes or 1403333823c75a1c1887e923828113a1b0fd12020cElliott Hughes 1503333823c75a1c1887e923828113a1b0fd12020cElliott Hughes * the GNU General Public License as published by the Free 1603333823c75a1c1887e923828113a1b0fd12020cElliott Hughes Software Foundation; either version 2 of the License, or (at 1703333823c75a1c1887e923828113a1b0fd12020cElliott Hughes your option) any later version 1803333823c75a1c1887e923828113a1b0fd12020cElliott Hughes 1903333823c75a1c1887e923828113a1b0fd12020cElliott Hughes or both in parallel, as here. 2003333823c75a1c1887e923828113a1b0fd12020cElliott Hughes 2103333823c75a1c1887e923828113a1b0fd12020cElliott Hughes elfutils is distributed in the hope that it will be useful, but 2225b3c049e70834cf33790a28643ab058b507b35cBen Cheng WITHOUT ANY WARRANTY; without even the implied warranty of 2325b3c049e70834cf33790a28643ab058b507b35cBen Cheng MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 2425b3c049e70834cf33790a28643ab058b507b35cBen Cheng General Public License for more details. 2525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 2603333823c75a1c1887e923828113a1b0fd12020cElliott Hughes You should have received copies of the GNU General Public License and 2703333823c75a1c1887e923828113a1b0fd12020cElliott Hughes the GNU Lesser General Public License along with this program. If 2803333823c75a1c1887e923828113a1b0fd12020cElliott Hughes not, see <http://www.gnu.org/licenses/>. */ 2925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 3025b3c049e70834cf33790a28643ab058b507b35cBen Cheng#ifdef HAVE_CONFIG_H 3125b3c049e70834cf33790a28643ab058b507b35cBen Cheng# include <config.h> 3225b3c049e70834cf33790a28643ab058b507b35cBen Cheng#endif 3325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 3425b3c049e70834cf33790a28643ab058b507b35cBen Cheng#include <assert.h> 3525b3c049e70834cf33790a28643ab058b507b35cBen Cheng#include <inttypes.h> 3625b3c049e70834cf33790a28643ab058b507b35cBen Cheng#include <libelf.h> 3725b3c049e70834cf33790a28643ab058b507b35cBen Cheng#include <stddef.h> 3825b3c049e70834cf33790a28643ab058b507b35cBen Cheng#include <stdlib.h> 3925b3c049e70834cf33790a28643ab058b507b35cBen Cheng#include <string.h> 4025b3c049e70834cf33790a28643ab058b507b35cBen Cheng#include <unistd.h> 4125b3c049e70834cf33790a28643ab058b507b35cBen Cheng#include <sys/param.h> 4225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 4325b3c049e70834cf33790a28643ab058b507b35cBen Cheng#include "libebl.h" 4425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 4525b3c049e70834cf33790a28643ab058b507b35cBen Cheng#ifndef MIN 4625b3c049e70834cf33790a28643ab058b507b35cBen Cheng# define MIN(a, b) ((a) < (b) ? (a) : (b)) 4725b3c049e70834cf33790a28643ab058b507b35cBen Cheng#endif 4825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 4925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 5025b3c049e70834cf33790a28643ab058b507b35cBen Chengstruct Ebl_GStrent 5125b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 5225b3c049e70834cf33790a28643ab058b507b35cBen Cheng const char *string; 5325b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t len; 5425b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_GStrent *next; 5525b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_GStrent *left; 5625b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_GStrent *right; 5725b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t offset; 5825b3c049e70834cf33790a28643ab058b507b35cBen Cheng unsigned int width; 5925b3c049e70834cf33790a28643ab058b507b35cBen Cheng char reverse[0]; 6025b3c049e70834cf33790a28643ab058b507b35cBen Cheng}; 6125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 6225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 6325b3c049e70834cf33790a28643ab058b507b35cBen Chengstruct memoryblock 6425b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 6525b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct memoryblock *next; 6625b3c049e70834cf33790a28643ab058b507b35cBen Cheng char memory[0]; 6725b3c049e70834cf33790a28643ab058b507b35cBen Cheng}; 6825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 6925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 7025b3c049e70834cf33790a28643ab058b507b35cBen Chengstruct Ebl_GStrtab 7125b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 7225b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_GStrent *root; 7325b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct memoryblock *memory; 7425b3c049e70834cf33790a28643ab058b507b35cBen Cheng char *backp; 7525b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t left; 7625b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t total; 7725b3c049e70834cf33790a28643ab058b507b35cBen Cheng unsigned int width; 7825b3c049e70834cf33790a28643ab058b507b35cBen Cheng bool nullstr; 7925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 8025b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_GStrent null; 8125b3c049e70834cf33790a28643ab058b507b35cBen Cheng}; 8225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 8325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 8425b3c049e70834cf33790a28643ab058b507b35cBen Cheng/* Cache for the pagesize. We correct this value a bit so that `malloc' 8525b3c049e70834cf33790a28643ab058b507b35cBen Cheng is not allocating more than a page. */ 8625b3c049e70834cf33790a28643ab058b507b35cBen Chengstatic size_t ps; 8725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 8825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 8925b3c049e70834cf33790a28643ab058b507b35cBen Chengstruct Ebl_GStrtab * 9025b3c049e70834cf33790a28643ab058b507b35cBen Chengebl_gstrtabinit (unsigned int width, bool nullstr) 9125b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 9225b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_GStrtab *ret; 9325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 9425b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (ps == 0) 9525b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 9625b3c049e70834cf33790a28643ab058b507b35cBen Cheng ps = sysconf (_SC_PAGESIZE) - 2 * sizeof (void *); 9725b3c049e70834cf33790a28643ab058b507b35cBen Cheng assert (sizeof (struct memoryblock) < ps); 9825b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 9925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 10025b3c049e70834cf33790a28643ab058b507b35cBen Cheng ret = (struct Ebl_GStrtab *) calloc (1, sizeof (struct Ebl_GStrtab)); 10125b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (ret != NULL) 10225b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 10325b3c049e70834cf33790a28643ab058b507b35cBen Cheng ret->width = width; 10425b3c049e70834cf33790a28643ab058b507b35cBen Cheng ret->nullstr = nullstr; 10525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 10625b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (nullstr) 10725b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 10825b3c049e70834cf33790a28643ab058b507b35cBen Cheng ret->null.len = 1; 10925b3c049e70834cf33790a28643ab058b507b35cBen Cheng ret->null.string = (char *) calloc (1, width); 11025b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 11125b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 11225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 11325b3c049e70834cf33790a28643ab058b507b35cBen Cheng return ret; 11425b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 11525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 11625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 11725b3c049e70834cf33790a28643ab058b507b35cBen Chengstatic void 11825b3c049e70834cf33790a28643ab058b507b35cBen Chengmorememory (struct Ebl_GStrtab *st, size_t len) 11925b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 12025b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct memoryblock *newmem; 12125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 12225b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (len < ps) 12325b3c049e70834cf33790a28643ab058b507b35cBen Cheng len = ps; 12425b3c049e70834cf33790a28643ab058b507b35cBen Cheng newmem = (struct memoryblock *) malloc (len); 12525b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (newmem == NULL) 12625b3c049e70834cf33790a28643ab058b507b35cBen Cheng abort (); 12725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 12825b3c049e70834cf33790a28643ab058b507b35cBen Cheng newmem->next = st->memory; 12925b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->memory = newmem; 13025b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->backp = newmem->memory; 13125b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->left = len - offsetof (struct memoryblock, memory); 13225b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 13325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 13425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 13525b3c049e70834cf33790a28643ab058b507b35cBen Chengvoid 13625b3c049e70834cf33790a28643ab058b507b35cBen Chengebl_gstrtabfree (struct Ebl_GStrtab *st) 13725b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 13825b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct memoryblock *mb = st->memory; 13925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 14025b3c049e70834cf33790a28643ab058b507b35cBen Cheng while (mb != NULL) 14125b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 14225b3c049e70834cf33790a28643ab058b507b35cBen Cheng void *old = mb; 14325b3c049e70834cf33790a28643ab058b507b35cBen Cheng mb = mb->next; 14425b3c049e70834cf33790a28643ab058b507b35cBen Cheng free (old); 14525b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 14625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 14725b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (st->null.string != NULL) 14825b3c049e70834cf33790a28643ab058b507b35cBen Cheng free ((char *) st->null.string); 14925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 15025b3c049e70834cf33790a28643ab058b507b35cBen Cheng free (st); 15125b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 15225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 15325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 15425b3c049e70834cf33790a28643ab058b507b35cBen Chengstatic struct Ebl_GStrent * 15525b3c049e70834cf33790a28643ab058b507b35cBen Chengnewstring (struct Ebl_GStrtab *st, const char *str, size_t len) 15625b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 15725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Compute the amount of padding needed to make the structure aligned. */ 15825b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t align = ((__alignof__ (struct Ebl_GStrent) 15925b3c049e70834cf33790a28643ab058b507b35cBen Cheng - (((uintptr_t) st->backp) 16025b3c049e70834cf33790a28643ab058b507b35cBen Cheng & (__alignof__ (struct Ebl_GStrent) - 1))) 16125b3c049e70834cf33790a28643ab058b507b35cBen Cheng & (__alignof__ (struct Ebl_GStrent) - 1)); 16225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 16325b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Make sure there is enough room in the memory block. */ 16425b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (st->left < align + sizeof (struct Ebl_GStrent) + len * st->width) 16525b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 16625b3c049e70834cf33790a28643ab058b507b35cBen Cheng morememory (st, sizeof (struct Ebl_GStrent) + len * st->width); 16725b3c049e70834cf33790a28643ab058b507b35cBen Cheng align = 0; 16825b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 16925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 17025b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Create the reserved string. */ 17125b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_GStrent *newstr = (struct Ebl_GStrent *) (st->backp + align); 17225b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->string = str; 17325b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->len = len; 17425b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->width = st->width; 17525b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->next = NULL; 17625b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->left = NULL; 17725b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->right = NULL; 17825b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->offset = 0; 17925b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (int i = len - 2; i >= 0; --i) 18025b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (int j = st->width - 1; j >= 0; --j) 18125b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->reverse[i * st->width + j] = str[(len - 2 - i) * st->width + j]; 18225b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (size_t j = 0; j < st->width; ++j) 18325b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->reverse[(len - 1) * st->width + j] = '\0'; 18425b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->backp += align + sizeof (struct Ebl_GStrent) + len * st->width; 18525b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->left -= align + sizeof (struct Ebl_GStrent) + len * st->width; 18625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 18725b3c049e70834cf33790a28643ab058b507b35cBen Cheng return newstr; 18825b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 18925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 19025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 19125b3c049e70834cf33790a28643ab058b507b35cBen Cheng/* XXX This function should definitely be rewritten to use a balancing 19225b3c049e70834cf33790a28643ab058b507b35cBen Cheng tree algorith (AVL, red-black trees). For now a simple, correct 19325b3c049e70834cf33790a28643ab058b507b35cBen Cheng implementation is enough. */ 19425b3c049e70834cf33790a28643ab058b507b35cBen Chengstatic struct Ebl_GStrent ** 19525b3c049e70834cf33790a28643ab058b507b35cBen Chengsearchstring (struct Ebl_GStrent **sep, struct Ebl_GStrent *newstr) 19625b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 19725b3c049e70834cf33790a28643ab058b507b35cBen Cheng int cmpres; 19825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 19925b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* More strings? */ 20025b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (*sep == NULL) 20125b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 20225b3c049e70834cf33790a28643ab058b507b35cBen Cheng *sep = newstr; 20325b3c049e70834cf33790a28643ab058b507b35cBen Cheng return sep; 20425b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 20525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 20625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Compare the strings. */ 20725b3c049e70834cf33790a28643ab058b507b35cBen Cheng cmpres = memcmp ((*sep)->reverse, newstr->reverse, 20825b3c049e70834cf33790a28643ab058b507b35cBen Cheng (MIN ((*sep)->len, newstr->len) - 1) * (*sep)->width); 20925b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (cmpres == 0) 21025b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* We found a matching string. */ 21125b3c049e70834cf33790a28643ab058b507b35cBen Cheng return sep; 21225b3c049e70834cf33790a28643ab058b507b35cBen Cheng else if (cmpres > 0) 21325b3c049e70834cf33790a28643ab058b507b35cBen Cheng return searchstring (&(*sep)->left, newstr); 21425b3c049e70834cf33790a28643ab058b507b35cBen Cheng else 21525b3c049e70834cf33790a28643ab058b507b35cBen Cheng return searchstring (&(*sep)->right, newstr); 21625b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 21725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 21825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 21925b3c049e70834cf33790a28643ab058b507b35cBen Cheng/* Add new string. The actual string is assumed to be permanent. */ 22025b3c049e70834cf33790a28643ab058b507b35cBen Chengstruct Ebl_GStrent * 22125b3c049e70834cf33790a28643ab058b507b35cBen Chengebl_gstrtabadd (struct Ebl_GStrtab *st, const char *str, size_t len) 22225b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 22325b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_GStrent *newstr; 22425b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_GStrent **sep; 22525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 22625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Compute the string length if the caller doesn't know it. */ 22725b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (len == 0) 22825b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 22925b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t j; 23025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 23125b3c049e70834cf33790a28643ab058b507b35cBen Cheng do 23225b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (j = 0; j < st->width; ++j) 23325b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (str[len * st->width + j] != '\0') 23425b3c049e70834cf33790a28643ab058b507b35cBen Cheng break; 23525b3c049e70834cf33790a28643ab058b507b35cBen Cheng while (j == st->width && ++len); 23625b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 23725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 23825b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Make sure all "" strings get offset 0 but only if the table was 23925b3c049e70834cf33790a28643ab058b507b35cBen Cheng created with a special null entry in mind. */ 24025b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (len == 1 && st->null.string != NULL) 24125b3c049e70834cf33790a28643ab058b507b35cBen Cheng return &st->null; 24225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 24325b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Allocate memory for the new string and its associated information. */ 24425b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr = newstring (st, str, len); 24525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 24625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Search in the array for the place to insert the string. If there 24725b3c049e70834cf33790a28643ab058b507b35cBen Cheng is no string with matching prefix and no string with matching 24825b3c049e70834cf33790a28643ab058b507b35cBen Cheng leading substring, create a new entry. */ 24925b3c049e70834cf33790a28643ab058b507b35cBen Cheng sep = searchstring (&st->root, newstr); 25025b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (*sep != newstr) 25125b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 25225b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* This is not the same entry. This means we have a prefix match. */ 25325b3c049e70834cf33790a28643ab058b507b35cBen Cheng if ((*sep)->len > newstr->len) 25425b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 25525b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_GStrent *subs; 25625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 25725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Check whether we already know this string. */ 25825b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (subs = (*sep)->next; subs != NULL; subs = subs->next) 25925b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (subs->len == newstr->len) 26025b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 26125b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* We have an exact match with a substring. Free the memory 26225b3c049e70834cf33790a28643ab058b507b35cBen Cheng we allocated. */ 26325b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->left += (st->backp - (char *) newstr) * st->width; 26425b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->backp = (char *) newstr; 26525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 26625b3c049e70834cf33790a28643ab058b507b35cBen Cheng return subs; 26725b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 26825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 26925b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* We have a new substring. This means we don't need the reverse 27025b3c049e70834cf33790a28643ab058b507b35cBen Cheng string of this entry anymore. */ 27125b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->backp -= newstr->len; 27225b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->left += newstr->len; 27325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 27425b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->next = (*sep)->next; 27525b3c049e70834cf33790a28643ab058b507b35cBen Cheng (*sep)->next = newstr; 27625b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 27725b3c049e70834cf33790a28643ab058b507b35cBen Cheng else if ((*sep)->len != newstr->len) 27825b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 27925b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* When we get here it means that the string we are about to 28025b3c049e70834cf33790a28643ab058b507b35cBen Cheng add has a common prefix with a string we already have but 28125b3c049e70834cf33790a28643ab058b507b35cBen Cheng it is longer. In this case we have to put it first. */ 28225b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->total += newstr->len - (*sep)->len; 28325b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->next = *sep; 28425b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->left = (*sep)->left; 28525b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->right = (*sep)->right; 28625b3c049e70834cf33790a28643ab058b507b35cBen Cheng *sep = newstr; 28725b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 28825b3c049e70834cf33790a28643ab058b507b35cBen Cheng else 28925b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 29025b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* We have an exact match. Free the memory we allocated. */ 29125b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->left += (st->backp - (char *) newstr) * st->width; 29225b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->backp = (char *) newstr; 29325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 29425b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr = *sep; 29525b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 29625b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 29725b3c049e70834cf33790a28643ab058b507b35cBen Cheng else 29825b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->total += newstr->len; 29925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 30025b3c049e70834cf33790a28643ab058b507b35cBen Cheng return newstr; 30125b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 30225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 30325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 30425b3c049e70834cf33790a28643ab058b507b35cBen Chengstatic void 30525b3c049e70834cf33790a28643ab058b507b35cBen Chengcopystrings (struct Ebl_GStrent *nodep, char **freep, size_t *offsetp) 30625b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 30725b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_GStrent *subs; 30825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 30925b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (nodep->left != NULL) 31025b3c049e70834cf33790a28643ab058b507b35cBen Cheng copystrings (nodep->left, freep, offsetp); 31125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 31225b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Process the current node. */ 31325b3c049e70834cf33790a28643ab058b507b35cBen Cheng nodep->offset = *offsetp; 31425b3c049e70834cf33790a28643ab058b507b35cBen Cheng *freep = (char *) mempcpy (*freep, nodep->string, nodep->len * nodep->width); 31525b3c049e70834cf33790a28643ab058b507b35cBen Cheng *offsetp += nodep->len * nodep->width; 31625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 31725b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (subs = nodep->next; subs != NULL; subs = subs->next) 31825b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 31925b3c049e70834cf33790a28643ab058b507b35cBen Cheng assert (subs->len < nodep->len); 32025b3c049e70834cf33790a28643ab058b507b35cBen Cheng subs->offset = nodep->offset + (nodep->len - subs->len) * nodep->width; 32125b3c049e70834cf33790a28643ab058b507b35cBen Cheng assert (subs->offset != 0 || subs->string[0] == '\0'); 32225b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 32325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 32425b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (nodep->right != NULL) 32525b3c049e70834cf33790a28643ab058b507b35cBen Cheng copystrings (nodep->right, freep, offsetp); 32625b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 32725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 32825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 32925b3c049e70834cf33790a28643ab058b507b35cBen Chengvoid 33025b3c049e70834cf33790a28643ab058b507b35cBen Chengebl_gstrtabfinalize (struct Ebl_GStrtab *st, Elf_Data *data) 33125b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 33225b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t copylen; 33325b3c049e70834cf33790a28643ab058b507b35cBen Cheng char *endp; 33425b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t nulllen = st->nullstr ? st->width : 0; 33525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 33625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Fill in the information. */ 33725b3c049e70834cf33790a28643ab058b507b35cBen Cheng data->d_buf = malloc (st->total + nulllen); 33825b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (data->d_buf == NULL) 33925b3c049e70834cf33790a28643ab058b507b35cBen Cheng abort (); 34025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 34125b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* The first byte must always be zero if we created the table with a 34225b3c049e70834cf33790a28643ab058b507b35cBen Cheng null string. */ 34325b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (st->nullstr) 34425b3c049e70834cf33790a28643ab058b507b35cBen Cheng memset (data->d_buf, '\0', st->width); 34525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 34625b3c049e70834cf33790a28643ab058b507b35cBen Cheng data->d_type = ELF_T_BYTE; 34725b3c049e70834cf33790a28643ab058b507b35cBen Cheng data->d_size = st->total + nulllen; 34825b3c049e70834cf33790a28643ab058b507b35cBen Cheng data->d_off = 0; 34925b3c049e70834cf33790a28643ab058b507b35cBen Cheng data->d_align = 1; 35025b3c049e70834cf33790a28643ab058b507b35cBen Cheng data->d_version = EV_CURRENT; 35125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 35225b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Now run through the tree and add all the string while also updating 35325b3c049e70834cf33790a28643ab058b507b35cBen Cheng the offset members of the elfstrent records. */ 35425b3c049e70834cf33790a28643ab058b507b35cBen Cheng endp = (char *) data->d_buf + nulllen; 35525b3c049e70834cf33790a28643ab058b507b35cBen Cheng copylen = nulllen; 35625b3c049e70834cf33790a28643ab058b507b35cBen Cheng copystrings (st->root, &endp, ©len); 35725b3c049e70834cf33790a28643ab058b507b35cBen Cheng assert (copylen == st->total * st->width + nulllen); 35825b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 35925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 36025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 36125b3c049e70834cf33790a28643ab058b507b35cBen Chengsize_t 36225b3c049e70834cf33790a28643ab058b507b35cBen Chengebl_gstrtaboffset (struct Ebl_GStrent *se) 36325b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 36425b3c049e70834cf33790a28643ab058b507b35cBen Cheng return se->offset; 36525b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 366