125b3c049e70834cf33790a28643ab058b507b35cBen Cheng/* ELF 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#include <system.h> 4525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 4625b3c049e70834cf33790a28643ab058b507b35cBen Cheng#ifndef MIN 4725b3c049e70834cf33790a28643ab058b507b35cBen Cheng# define MIN(a, b) ((a) < (b) ? (a) : (b)) 4825b3c049e70834cf33790a28643ab058b507b35cBen Cheng#endif 4925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 5025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 5125b3c049e70834cf33790a28643ab058b507b35cBen Chengstruct Ebl_Strent 5225b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 5325b3c049e70834cf33790a28643ab058b507b35cBen Cheng const char *string; 5425b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t len; 5525b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_Strent *next; 5625b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_Strent *left; 5725b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_Strent *right; 5825b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t offset; 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_Strtab 7125b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 7225b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_Strent *root; 7325b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct memoryblock *memory; 7425b3c049e70834cf33790a28643ab058b507b35cBen Cheng char *backp; 7525b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t left; 7625b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t total; 7725b3c049e70834cf33790a28643ab058b507b35cBen Cheng bool nullstr; 7825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 7925b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_Strent null; 8025b3c049e70834cf33790a28643ab058b507b35cBen Cheng}; 8125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 8225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 8325b3c049e70834cf33790a28643ab058b507b35cBen Cheng/* Cache for the pagesize. */ 8425b3c049e70834cf33790a28643ab058b507b35cBen Chengstatic size_t ps; 8525b3c049e70834cf33790a28643ab058b507b35cBen Cheng/* We correct this value a bit so that `malloc' is not allocating more 8625b3c049e70834cf33790a28643ab058b507b35cBen Cheng than a page. */ 8725b3c049e70834cf33790a28643ab058b507b35cBen Cheng#define MALLOC_OVERHEAD (2 * sizeof (void *)) 8825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 8925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 9025b3c049e70834cf33790a28643ab058b507b35cBen Chengstruct Ebl_Strtab * 9125b3c049e70834cf33790a28643ab058b507b35cBen Chengebl_strtabinit (bool nullstr) 9225b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 9325b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (ps == 0) 9425b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 9525b3c049e70834cf33790a28643ab058b507b35cBen Cheng ps = sysconf (_SC_PAGESIZE); 9625b3c049e70834cf33790a28643ab058b507b35cBen Cheng assert (sizeof (struct memoryblock) < ps - MALLOC_OVERHEAD); 9725b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 9825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 9925b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_Strtab *ret 10025b3c049e70834cf33790a28643ab058b507b35cBen Cheng = (struct Ebl_Strtab *) calloc (1, sizeof (struct Ebl_Strtab)); 10125b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (ret != NULL) 10225b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 10325b3c049e70834cf33790a28643ab058b507b35cBen Cheng ret->nullstr = nullstr; 10425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 10525b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (nullstr) 10625b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 10725b3c049e70834cf33790a28643ab058b507b35cBen Cheng ret->null.len = 1; 10825b3c049e70834cf33790a28643ab058b507b35cBen Cheng ret->null.string = ""; 10925b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 11025b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 11125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 11225b3c049e70834cf33790a28643ab058b507b35cBen Cheng return ret; 11325b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 11425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 11525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 11625b3c049e70834cf33790a28643ab058b507b35cBen Chengstatic int 11725b3c049e70834cf33790a28643ab058b507b35cBen Chengmorememory (struct Ebl_Strtab *st, size_t len) 11825b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 11925b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t overhead = offsetof (struct memoryblock, memory); 12025b3c049e70834cf33790a28643ab058b507b35cBen Cheng len += overhead + MALLOC_OVERHEAD; 12125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 12225b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Allocate nearest multiple of pagesize >= len. */ 12325b3c049e70834cf33790a28643ab058b507b35cBen Cheng len = ((len / ps) + (len % ps != 0)) * ps - MALLOC_OVERHEAD; 12425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 12525b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct memoryblock *newmem = (struct memoryblock *) malloc (len); 12625b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (newmem == NULL) 12725b3c049e70834cf33790a28643ab058b507b35cBen Cheng return 1; 12825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 12925b3c049e70834cf33790a28643ab058b507b35cBen Cheng newmem->next = st->memory; 13025b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->memory = newmem; 13125b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->backp = newmem->memory; 13225b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->left = len - overhead; 13325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 13425b3c049e70834cf33790a28643ab058b507b35cBen Cheng return 0; 13525b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 13625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 13725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 13825b3c049e70834cf33790a28643ab058b507b35cBen Chengvoid 13925b3c049e70834cf33790a28643ab058b507b35cBen Chengebl_strtabfree (struct Ebl_Strtab *st) 14025b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 14125b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct memoryblock *mb = st->memory; 14225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 14325b3c049e70834cf33790a28643ab058b507b35cBen Cheng while (mb != NULL) 14425b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 14525b3c049e70834cf33790a28643ab058b507b35cBen Cheng void *old = mb; 14625b3c049e70834cf33790a28643ab058b507b35cBen Cheng mb = mb->next; 14725b3c049e70834cf33790a28643ab058b507b35cBen Cheng free (old); 14825b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 14925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 15025b3c049e70834cf33790a28643ab058b507b35cBen Cheng free (st); 15125b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 15225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 15325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 15425b3c049e70834cf33790a28643ab058b507b35cBen Chengstatic struct Ebl_Strent * 15525b3c049e70834cf33790a28643ab058b507b35cBen Chengnewstring (struct Ebl_Strtab *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_Strent) 15925b3c049e70834cf33790a28643ab058b507b35cBen Cheng - (((uintptr_t) st->backp) 16025b3c049e70834cf33790a28643ab058b507b35cBen Cheng & (__alignof__ (struct Ebl_Strent) - 1))) 16125b3c049e70834cf33790a28643ab058b507b35cBen Cheng & (__alignof__ (struct Ebl_Strent) - 1)); 16225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 16325b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Make sure there is enough room in the memory block. */ 16425b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (st->left < align + sizeof (struct Ebl_Strent) + len) 16525b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 16625b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (morememory (st, sizeof (struct Ebl_Strent) + len)) 16725b3c049e70834cf33790a28643ab058b507b35cBen Cheng return NULL; 16825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 16925b3c049e70834cf33790a28643ab058b507b35cBen Cheng align = 0; 17025b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 17125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 17225b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Create the reserved string. */ 17325b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_Strent *newstr = (struct Ebl_Strent *) (st->backp + align); 17425b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->string = str; 17525b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->len = len; 17625b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->next = NULL; 17725b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->left = NULL; 17825b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->right = NULL; 17925b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->offset = 0; 18025b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (int i = len - 2; i >= 0; --i) 18125b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->reverse[i] = str[len - 2 - i]; 18225b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->reverse[len - 1] = '\0'; 18325b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->backp += align + sizeof (struct Ebl_Strent) + len; 18425b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->left -= align + sizeof (struct Ebl_Strent) + len; 18525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 18625b3c049e70834cf33790a28643ab058b507b35cBen Cheng return newstr; 18725b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 18825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 18925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 19025b3c049e70834cf33790a28643ab058b507b35cBen Cheng/* XXX This function should definitely be rewritten to use a balancing 19125b3c049e70834cf33790a28643ab058b507b35cBen Cheng tree algorith (AVL, red-black trees). For now a simple, correct 19225b3c049e70834cf33790a28643ab058b507b35cBen Cheng implementation is enough. */ 19325b3c049e70834cf33790a28643ab058b507b35cBen Chengstatic struct Ebl_Strent ** 19425b3c049e70834cf33790a28643ab058b507b35cBen Chengsearchstring (struct Ebl_Strent **sep, struct Ebl_Strent *newstr) 19525b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 19625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* More strings? */ 19725b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (*sep == NULL) 19825b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 19925b3c049e70834cf33790a28643ab058b507b35cBen Cheng *sep = newstr; 20025b3c049e70834cf33790a28643ab058b507b35cBen Cheng return sep; 20125b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 20225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 20325b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Compare the strings. */ 20425b3c049e70834cf33790a28643ab058b507b35cBen Cheng int cmpres = memcmp ((*sep)->reverse, newstr->reverse, 20525b3c049e70834cf33790a28643ab058b507b35cBen Cheng MIN ((*sep)->len, newstr->len) - 1); 20625b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (cmpres == 0) 20725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* We found a matching string. */ 20825b3c049e70834cf33790a28643ab058b507b35cBen Cheng return sep; 20925b3c049e70834cf33790a28643ab058b507b35cBen Cheng else if (cmpres > 0) 21025b3c049e70834cf33790a28643ab058b507b35cBen Cheng return searchstring (&(*sep)->left, newstr); 21125b3c049e70834cf33790a28643ab058b507b35cBen Cheng else 21225b3c049e70834cf33790a28643ab058b507b35cBen Cheng return searchstring (&(*sep)->right, newstr); 21325b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 21425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 21525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 21625b3c049e70834cf33790a28643ab058b507b35cBen Cheng/* Add new string. The actual string is assumed to be permanent. */ 21725b3c049e70834cf33790a28643ab058b507b35cBen Chengstruct Ebl_Strent * 21825b3c049e70834cf33790a28643ab058b507b35cBen Chengebl_strtabadd (struct Ebl_Strtab *st, const char *str, size_t len) 21925b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 22025b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Compute the string length if the caller doesn't know it. */ 22125b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (len == 0) 22225b3c049e70834cf33790a28643ab058b507b35cBen Cheng len = strlen (str) + 1; 22325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 22425b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Make sure all "" strings get offset 0 but only if the table was 22525b3c049e70834cf33790a28643ab058b507b35cBen Cheng created with a special null entry in mind. */ 22625b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (len == 1 && st->null.string != NULL) 22725b3c049e70834cf33790a28643ab058b507b35cBen Cheng return &st->null; 22825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 22925b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Allocate memory for the new string and its associated information. */ 23025b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_Strent *newstr = newstring (st, str, len); 23125b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (newstr == NULL) 23225b3c049e70834cf33790a28643ab058b507b35cBen Cheng return NULL; 23325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 23425b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Search in the array for the place to insert the string. If there 23525b3c049e70834cf33790a28643ab058b507b35cBen Cheng is no string with matching prefix and no string with matching 23625b3c049e70834cf33790a28643ab058b507b35cBen Cheng leading substring, create a new entry. */ 23725b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_Strent **sep = searchstring (&st->root, newstr); 23825b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (*sep != newstr) 23925b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 24025b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* This is not the same entry. This means we have a prefix match. */ 24125b3c049e70834cf33790a28643ab058b507b35cBen Cheng if ((*sep)->len > newstr->len) 24225b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 24325b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Check whether we already know this string. */ 24425b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (struct Ebl_Strent *subs = (*sep)->next; subs != NULL; 24525b3c049e70834cf33790a28643ab058b507b35cBen Cheng subs = subs->next) 24625b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (subs->len == newstr->len) 24725b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 24825b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* We have an exact match with a substring. Free the memory 24925b3c049e70834cf33790a28643ab058b507b35cBen Cheng we allocated. */ 25025b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->left += st->backp - (char *) newstr; 25125b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->backp = (char *) newstr; 25225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 25325b3c049e70834cf33790a28643ab058b507b35cBen Cheng return subs; 25425b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 25525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 25625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* We have a new substring. This means we don't need the reverse 25725b3c049e70834cf33790a28643ab058b507b35cBen Cheng string of this entry anymore. */ 25825b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->backp -= newstr->len; 25925b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->left += newstr->len; 26025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 26125b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->next = (*sep)->next; 26225b3c049e70834cf33790a28643ab058b507b35cBen Cheng (*sep)->next = newstr; 26325b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 26425b3c049e70834cf33790a28643ab058b507b35cBen Cheng else if ((*sep)->len != newstr->len) 26525b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 26625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* When we get here it means that the string we are about to 26725b3c049e70834cf33790a28643ab058b507b35cBen Cheng add has a common prefix with a string we already have but 26825b3c049e70834cf33790a28643ab058b507b35cBen Cheng it is longer. In this case we have to put it first. */ 26925b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->total += newstr->len - (*sep)->len; 27025b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->next = *sep; 27125b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->left = (*sep)->left; 27225b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->right = (*sep)->right; 27325b3c049e70834cf33790a28643ab058b507b35cBen Cheng *sep = newstr; 27425b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 27525b3c049e70834cf33790a28643ab058b507b35cBen Cheng else 27625b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 27725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* We have an exact match. Free the memory we allocated. */ 27825b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->left += st->backp - (char *) newstr; 27925b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->backp = (char *) newstr; 28025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 28125b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr = *sep; 28225b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 28325b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 28425b3c049e70834cf33790a28643ab058b507b35cBen Cheng else 28525b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->total += newstr->len; 28625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 28725b3c049e70834cf33790a28643ab058b507b35cBen Cheng return newstr; 28825b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 28925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 29025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 29125b3c049e70834cf33790a28643ab058b507b35cBen Chengstatic void 29225b3c049e70834cf33790a28643ab058b507b35cBen Chengcopystrings (struct Ebl_Strent *nodep, char **freep, size_t *offsetp) 29325b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 29425b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (nodep->left != NULL) 29525b3c049e70834cf33790a28643ab058b507b35cBen Cheng copystrings (nodep->left, freep, offsetp); 29625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 29725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Process the current node. */ 29825b3c049e70834cf33790a28643ab058b507b35cBen Cheng nodep->offset = *offsetp; 29925b3c049e70834cf33790a28643ab058b507b35cBen Cheng *freep = (char *) mempcpy (*freep, nodep->string, nodep->len); 30025b3c049e70834cf33790a28643ab058b507b35cBen Cheng *offsetp += nodep->len; 30125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 30225b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (struct Ebl_Strent *subs = nodep->next; subs != NULL; subs = subs->next) 30325b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 30425b3c049e70834cf33790a28643ab058b507b35cBen Cheng assert (subs->len < nodep->len); 30525b3c049e70834cf33790a28643ab058b507b35cBen Cheng subs->offset = nodep->offset + nodep->len - subs->len; 30625b3c049e70834cf33790a28643ab058b507b35cBen Cheng assert (subs->offset != 0 || subs->string[0] == '\0'); 30725b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 30825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 30925b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (nodep->right != NULL) 31025b3c049e70834cf33790a28643ab058b507b35cBen Cheng copystrings (nodep->right, freep, offsetp); 31125b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 31225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 31325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 31425b3c049e70834cf33790a28643ab058b507b35cBen Chengvoid 31525b3c049e70834cf33790a28643ab058b507b35cBen Chengebl_strtabfinalize (struct Ebl_Strtab *st, Elf_Data *data) 31625b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 31725b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t nulllen = st->nullstr ? 1 : 0; 31825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 31925b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Fill in the information. */ 32025b3c049e70834cf33790a28643ab058b507b35cBen Cheng data->d_buf = malloc (st->total + nulllen); 32125b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (data->d_buf == NULL) 32225b3c049e70834cf33790a28643ab058b507b35cBen Cheng abort (); 32325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 32425b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* The first byte must always be zero if we created the table with a 32525b3c049e70834cf33790a28643ab058b507b35cBen Cheng null string. */ 32625b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (st->nullstr) 32725b3c049e70834cf33790a28643ab058b507b35cBen Cheng *((char *) data->d_buf) = '\0'; 32825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 32925b3c049e70834cf33790a28643ab058b507b35cBen Cheng data->d_type = ELF_T_BYTE; 33025b3c049e70834cf33790a28643ab058b507b35cBen Cheng data->d_size = st->total + nulllen; 33125b3c049e70834cf33790a28643ab058b507b35cBen Cheng data->d_off = 0; 33225b3c049e70834cf33790a28643ab058b507b35cBen Cheng data->d_align = 1; 33325b3c049e70834cf33790a28643ab058b507b35cBen Cheng data->d_version = EV_CURRENT; 33425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 33525b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Now run through the tree and add all the string while also updating 33625b3c049e70834cf33790a28643ab058b507b35cBen Cheng the offset members of the elfstrent records. */ 33725b3c049e70834cf33790a28643ab058b507b35cBen Cheng char *endp = (char *) data->d_buf + nulllen; 33825b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t copylen = nulllen; 33925b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (st->root) 34025b3c049e70834cf33790a28643ab058b507b35cBen Cheng copystrings (st->root, &endp, ©len); 34125b3c049e70834cf33790a28643ab058b507b35cBen Cheng assert (copylen == st->total + nulllen); 34225b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 34325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 34425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 34525b3c049e70834cf33790a28643ab058b507b35cBen Chengsize_t 34625b3c049e70834cf33790a28643ab058b507b35cBen Chengebl_strtaboffset (struct Ebl_Strent *se) 34725b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 34825b3c049e70834cf33790a28643ab058b507b35cBen Cheng return se->offset; 34925b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 35025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 35125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 35225b3c049e70834cf33790a28643ab058b507b35cBen Chengconst char * 35325b3c049e70834cf33790a28643ab058b507b35cBen Chengebl_string (struct Ebl_Strent *se) 35425b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 35525b3c049e70834cf33790a28643ab058b507b35cBen Cheng assert (se->string != NULL); 35625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 35725b3c049e70834cf33790a28643ab058b507b35cBen Cheng return se->string; 35825b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 359