125b3c049e70834cf33790a28643ab058b507b35cBen Cheng/* Generic string table handling. 225b3c049e70834cf33790a28643ab058b507b35cBen Cheng Copyright (C) 2000, 2001, 2002, 2005 Red Hat, Inc. 325b3c049e70834cf33790a28643ab058b507b35cBen Cheng This file is part of Red Hat elfutils. 425b3c049e70834cf33790a28643ab058b507b35cBen Cheng Written by Ulrich Drepper <drepper@redhat.com>, 2000. 525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 625b3c049e70834cf33790a28643ab058b507b35cBen Cheng Red Hat elfutils is free software; you can redistribute it and/or modify 725b3c049e70834cf33790a28643ab058b507b35cBen Cheng it under the terms of the GNU General Public License as published by the 825b3c049e70834cf33790a28643ab058b507b35cBen Cheng Free Software Foundation; version 2 of the License. 925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 1025b3c049e70834cf33790a28643ab058b507b35cBen Cheng Red Hat elfutils is distributed in the hope that it will be useful, but 1125b3c049e70834cf33790a28643ab058b507b35cBen Cheng WITHOUT ANY WARRANTY; without even the implied warranty of 1225b3c049e70834cf33790a28643ab058b507b35cBen Cheng MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1325b3c049e70834cf33790a28643ab058b507b35cBen Cheng General Public License for more details. 1425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 1525b3c049e70834cf33790a28643ab058b507b35cBen Cheng You should have received a copy of the GNU General Public License along 1625b3c049e70834cf33790a28643ab058b507b35cBen Cheng with Red Hat elfutils; if not, write to the Free Software Foundation, 1725b3c049e70834cf33790a28643ab058b507b35cBen Cheng Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301 USA. 1825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 1925b3c049e70834cf33790a28643ab058b507b35cBen Cheng In addition, as a special exception, Red Hat, Inc. gives You the 2025b3c049e70834cf33790a28643ab058b507b35cBen Cheng additional right to link the code of Red Hat elfutils with code licensed 2125b3c049e70834cf33790a28643ab058b507b35cBen Cheng under any Open Source Initiative certified open source license 2225b3c049e70834cf33790a28643ab058b507b35cBen Cheng (http://www.opensource.org/licenses/index.php) which requires the 2325b3c049e70834cf33790a28643ab058b507b35cBen Cheng distribution of source code with any binary distribution and to 2425b3c049e70834cf33790a28643ab058b507b35cBen Cheng distribute linked combinations of the two. Non-GPL Code permitted under 2525b3c049e70834cf33790a28643ab058b507b35cBen Cheng this exception must only link to the code of Red Hat elfutils through 2625b3c049e70834cf33790a28643ab058b507b35cBen Cheng those well defined interfaces identified in the file named EXCEPTION 2725b3c049e70834cf33790a28643ab058b507b35cBen Cheng found in the source code files (the "Approved Interfaces"). The files 2825b3c049e70834cf33790a28643ab058b507b35cBen Cheng of Non-GPL Code may instantiate templates or use macros or inline 2925b3c049e70834cf33790a28643ab058b507b35cBen Cheng functions from the Approved Interfaces without causing the resulting 3025b3c049e70834cf33790a28643ab058b507b35cBen Cheng work to be covered by the GNU General Public License. Only Red Hat, 3125b3c049e70834cf33790a28643ab058b507b35cBen Cheng Inc. may make changes or additions to the list of Approved Interfaces. 3225b3c049e70834cf33790a28643ab058b507b35cBen Cheng Red Hat's grant of this exception is conditioned upon your not adding 3325b3c049e70834cf33790a28643ab058b507b35cBen Cheng any new exceptions. If you wish to add a new Approved Interface or 3425b3c049e70834cf33790a28643ab058b507b35cBen Cheng exception, please contact Red Hat. You must obey the GNU General Public 3525b3c049e70834cf33790a28643ab058b507b35cBen Cheng License in all respects for all of the Red Hat elfutils code and other 3625b3c049e70834cf33790a28643ab058b507b35cBen Cheng code used in conjunction with Red Hat elfutils except the Non-GPL Code 3725b3c049e70834cf33790a28643ab058b507b35cBen Cheng covered by this exception. If you modify this file, you may extend this 3825b3c049e70834cf33790a28643ab058b507b35cBen Cheng exception to your version of the file, but you are not obligated to do 3925b3c049e70834cf33790a28643ab058b507b35cBen Cheng so. If you do not wish to provide this exception without modification, 4025b3c049e70834cf33790a28643ab058b507b35cBen Cheng you must delete this exception statement from your version and license 4125b3c049e70834cf33790a28643ab058b507b35cBen Cheng this file solely under the GPL without exception. 4225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 4325b3c049e70834cf33790a28643ab058b507b35cBen Cheng Red Hat elfutils is an included package of the Open Invention Network. 4425b3c049e70834cf33790a28643ab058b507b35cBen Cheng An included package of the Open Invention Network is a package for which 4525b3c049e70834cf33790a28643ab058b507b35cBen Cheng Open Invention Network licensees cross-license their patents. No patent 4625b3c049e70834cf33790a28643ab058b507b35cBen Cheng license is granted, either expressly or impliedly, by designation as an 4725b3c049e70834cf33790a28643ab058b507b35cBen Cheng included package. Should you wish to participate in the Open Invention 4825b3c049e70834cf33790a28643ab058b507b35cBen Cheng Network licensing program, please visit www.openinventionnetwork.com 4925b3c049e70834cf33790a28643ab058b507b35cBen Cheng <http://www.openinventionnetwork.com>. */ 5025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 5125b3c049e70834cf33790a28643ab058b507b35cBen Cheng#ifdef HAVE_CONFIG_H 5225b3c049e70834cf33790a28643ab058b507b35cBen Cheng# include <config.h> 5325b3c049e70834cf33790a28643ab058b507b35cBen Cheng#endif 5425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 5525b3c049e70834cf33790a28643ab058b507b35cBen Cheng#include <assert.h> 5625b3c049e70834cf33790a28643ab058b507b35cBen Cheng#include <inttypes.h> 5725b3c049e70834cf33790a28643ab058b507b35cBen Cheng#include <libelf.h> 5825b3c049e70834cf33790a28643ab058b507b35cBen Cheng#include <stddef.h> 5925b3c049e70834cf33790a28643ab058b507b35cBen Cheng#include <stdlib.h> 6025b3c049e70834cf33790a28643ab058b507b35cBen Cheng#include <string.h> 6125b3c049e70834cf33790a28643ab058b507b35cBen Cheng#include <unistd.h> 6225b3c049e70834cf33790a28643ab058b507b35cBen Cheng#include <sys/param.h> 6325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 6425b3c049e70834cf33790a28643ab058b507b35cBen Cheng#include "libebl.h" 6525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 6625b3c049e70834cf33790a28643ab058b507b35cBen Cheng#ifndef MIN 6725b3c049e70834cf33790a28643ab058b507b35cBen Cheng# define MIN(a, b) ((a) < (b) ? (a) : (b)) 6825b3c049e70834cf33790a28643ab058b507b35cBen Cheng#endif 6925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 7025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 7125b3c049e70834cf33790a28643ab058b507b35cBen Chengstruct Ebl_GStrent 7225b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 7325b3c049e70834cf33790a28643ab058b507b35cBen Cheng const char *string; 7425b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t len; 7525b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_GStrent *next; 7625b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_GStrent *left; 7725b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_GStrent *right; 7825b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t offset; 7925b3c049e70834cf33790a28643ab058b507b35cBen Cheng unsigned int width; 8025b3c049e70834cf33790a28643ab058b507b35cBen Cheng char reverse[0]; 8125b3c049e70834cf33790a28643ab058b507b35cBen Cheng}; 8225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 8325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 8425b3c049e70834cf33790a28643ab058b507b35cBen Chengstruct memoryblock 8525b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 8625b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct memoryblock *next; 8725b3c049e70834cf33790a28643ab058b507b35cBen Cheng char memory[0]; 8825b3c049e70834cf33790a28643ab058b507b35cBen Cheng}; 8925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 9025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 9125b3c049e70834cf33790a28643ab058b507b35cBen Chengstruct Ebl_GStrtab 9225b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 9325b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_GStrent *root; 9425b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct memoryblock *memory; 9525b3c049e70834cf33790a28643ab058b507b35cBen Cheng char *backp; 9625b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t left; 9725b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t total; 9825b3c049e70834cf33790a28643ab058b507b35cBen Cheng unsigned int width; 9925b3c049e70834cf33790a28643ab058b507b35cBen Cheng bool nullstr; 10025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 10125b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_GStrent null; 10225b3c049e70834cf33790a28643ab058b507b35cBen Cheng}; 10325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 10425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 10525b3c049e70834cf33790a28643ab058b507b35cBen Cheng/* Cache for the pagesize. We correct this value a bit so that `malloc' 10625b3c049e70834cf33790a28643ab058b507b35cBen Cheng is not allocating more than a page. */ 10725b3c049e70834cf33790a28643ab058b507b35cBen Chengstatic size_t ps; 10825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 10925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 11025b3c049e70834cf33790a28643ab058b507b35cBen Chengstruct Ebl_GStrtab * 11125b3c049e70834cf33790a28643ab058b507b35cBen Chengebl_gstrtabinit (unsigned int width, bool nullstr) 11225b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 11325b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_GStrtab *ret; 11425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 11525b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (ps == 0) 11625b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 11725b3c049e70834cf33790a28643ab058b507b35cBen Cheng ps = sysconf (_SC_PAGESIZE) - 2 * sizeof (void *); 11825b3c049e70834cf33790a28643ab058b507b35cBen Cheng assert (sizeof (struct memoryblock) < ps); 11925b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 12025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 12125b3c049e70834cf33790a28643ab058b507b35cBen Cheng ret = (struct Ebl_GStrtab *) calloc (1, sizeof (struct Ebl_GStrtab)); 12225b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (ret != NULL) 12325b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 12425b3c049e70834cf33790a28643ab058b507b35cBen Cheng ret->width = width; 12525b3c049e70834cf33790a28643ab058b507b35cBen Cheng ret->nullstr = nullstr; 12625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 12725b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (nullstr) 12825b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 12925b3c049e70834cf33790a28643ab058b507b35cBen Cheng ret->null.len = 1; 13025b3c049e70834cf33790a28643ab058b507b35cBen Cheng ret->null.string = (char *) calloc (1, width); 13125b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 13225b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 13325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 13425b3c049e70834cf33790a28643ab058b507b35cBen Cheng return ret; 13525b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 13625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 13725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 13825b3c049e70834cf33790a28643ab058b507b35cBen Chengstatic void 13925b3c049e70834cf33790a28643ab058b507b35cBen Chengmorememory (struct Ebl_GStrtab *st, size_t len) 14025b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 14125b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct memoryblock *newmem; 14225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 14325b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (len < ps) 14425b3c049e70834cf33790a28643ab058b507b35cBen Cheng len = ps; 14525b3c049e70834cf33790a28643ab058b507b35cBen Cheng newmem = (struct memoryblock *) malloc (len); 14625b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (newmem == NULL) 14725b3c049e70834cf33790a28643ab058b507b35cBen Cheng abort (); 14825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 14925b3c049e70834cf33790a28643ab058b507b35cBen Cheng newmem->next = st->memory; 15025b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->memory = newmem; 15125b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->backp = newmem->memory; 15225b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->left = len - offsetof (struct memoryblock, memory); 15325b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 15425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 15525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 15625b3c049e70834cf33790a28643ab058b507b35cBen Chengvoid 15725b3c049e70834cf33790a28643ab058b507b35cBen Chengebl_gstrtabfree (struct Ebl_GStrtab *st) 15825b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 15925b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct memoryblock *mb = st->memory; 16025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 16125b3c049e70834cf33790a28643ab058b507b35cBen Cheng while (mb != NULL) 16225b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 16325b3c049e70834cf33790a28643ab058b507b35cBen Cheng void *old = mb; 16425b3c049e70834cf33790a28643ab058b507b35cBen Cheng mb = mb->next; 16525b3c049e70834cf33790a28643ab058b507b35cBen Cheng free (old); 16625b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 16725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 16825b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (st->null.string != NULL) 16925b3c049e70834cf33790a28643ab058b507b35cBen Cheng free ((char *) st->null.string); 17025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 17125b3c049e70834cf33790a28643ab058b507b35cBen Cheng free (st); 17225b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 17325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 17425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 17525b3c049e70834cf33790a28643ab058b507b35cBen Chengstatic struct Ebl_GStrent * 17625b3c049e70834cf33790a28643ab058b507b35cBen Chengnewstring (struct Ebl_GStrtab *st, const char *str, size_t len) 17725b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 17825b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Compute the amount of padding needed to make the structure aligned. */ 17925b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t align = ((__alignof__ (struct Ebl_GStrent) 18025b3c049e70834cf33790a28643ab058b507b35cBen Cheng - (((uintptr_t) st->backp) 18125b3c049e70834cf33790a28643ab058b507b35cBen Cheng & (__alignof__ (struct Ebl_GStrent) - 1))) 18225b3c049e70834cf33790a28643ab058b507b35cBen Cheng & (__alignof__ (struct Ebl_GStrent) - 1)); 18325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 18425b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Make sure there is enough room in the memory block. */ 18525b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (st->left < align + sizeof (struct Ebl_GStrent) + len * st->width) 18625b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 18725b3c049e70834cf33790a28643ab058b507b35cBen Cheng morememory (st, sizeof (struct Ebl_GStrent) + len * st->width); 18825b3c049e70834cf33790a28643ab058b507b35cBen Cheng align = 0; 18925b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 19025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 19125b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Create the reserved string. */ 19225b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_GStrent *newstr = (struct Ebl_GStrent *) (st->backp + align); 19325b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->string = str; 19425b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->len = len; 19525b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->width = st->width; 19625b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->next = NULL; 19725b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->left = NULL; 19825b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->right = NULL; 19925b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->offset = 0; 20025b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (int i = len - 2; i >= 0; --i) 20125b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (int j = st->width - 1; j >= 0; --j) 20225b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->reverse[i * st->width + j] = str[(len - 2 - i) * st->width + j]; 20325b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (size_t j = 0; j < st->width; ++j) 20425b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->reverse[(len - 1) * st->width + j] = '\0'; 20525b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->backp += align + sizeof (struct Ebl_GStrent) + len * st->width; 20625b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->left -= align + sizeof (struct Ebl_GStrent) + len * st->width; 20725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 20825b3c049e70834cf33790a28643ab058b507b35cBen Cheng return newstr; 20925b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 21025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 21125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 21225b3c049e70834cf33790a28643ab058b507b35cBen Cheng/* XXX This function should definitely be rewritten to use a balancing 21325b3c049e70834cf33790a28643ab058b507b35cBen Cheng tree algorith (AVL, red-black trees). For now a simple, correct 21425b3c049e70834cf33790a28643ab058b507b35cBen Cheng implementation is enough. */ 21525b3c049e70834cf33790a28643ab058b507b35cBen Chengstatic struct Ebl_GStrent ** 21625b3c049e70834cf33790a28643ab058b507b35cBen Chengsearchstring (struct Ebl_GStrent **sep, struct Ebl_GStrent *newstr) 21725b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 21825b3c049e70834cf33790a28643ab058b507b35cBen Cheng int cmpres; 21925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 22025b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* More strings? */ 22125b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (*sep == NULL) 22225b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 22325b3c049e70834cf33790a28643ab058b507b35cBen Cheng *sep = newstr; 22425b3c049e70834cf33790a28643ab058b507b35cBen Cheng return sep; 22525b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 22625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 22725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Compare the strings. */ 22825b3c049e70834cf33790a28643ab058b507b35cBen Cheng cmpres = memcmp ((*sep)->reverse, newstr->reverse, 22925b3c049e70834cf33790a28643ab058b507b35cBen Cheng (MIN ((*sep)->len, newstr->len) - 1) * (*sep)->width); 23025b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (cmpres == 0) 23125b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* We found a matching string. */ 23225b3c049e70834cf33790a28643ab058b507b35cBen Cheng return sep; 23325b3c049e70834cf33790a28643ab058b507b35cBen Cheng else if (cmpres > 0) 23425b3c049e70834cf33790a28643ab058b507b35cBen Cheng return searchstring (&(*sep)->left, newstr); 23525b3c049e70834cf33790a28643ab058b507b35cBen Cheng else 23625b3c049e70834cf33790a28643ab058b507b35cBen Cheng return searchstring (&(*sep)->right, newstr); 23725b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 23825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 23925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 24025b3c049e70834cf33790a28643ab058b507b35cBen Cheng/* Add new string. The actual string is assumed to be permanent. */ 24125b3c049e70834cf33790a28643ab058b507b35cBen Chengstruct Ebl_GStrent * 24225b3c049e70834cf33790a28643ab058b507b35cBen Chengebl_gstrtabadd (struct Ebl_GStrtab *st, const char *str, size_t len) 24325b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 24425b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_GStrent *newstr; 24525b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_GStrent **sep; 24625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 24725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Compute the string length if the caller doesn't know it. */ 24825b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (len == 0) 24925b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 25025b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t j; 25125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 25225b3c049e70834cf33790a28643ab058b507b35cBen Cheng do 25325b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (j = 0; j < st->width; ++j) 25425b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (str[len * st->width + j] != '\0') 25525b3c049e70834cf33790a28643ab058b507b35cBen Cheng break; 25625b3c049e70834cf33790a28643ab058b507b35cBen Cheng while (j == st->width && ++len); 25725b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 25825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 25925b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Make sure all "" strings get offset 0 but only if the table was 26025b3c049e70834cf33790a28643ab058b507b35cBen Cheng created with a special null entry in mind. */ 26125b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (len == 1 && st->null.string != NULL) 26225b3c049e70834cf33790a28643ab058b507b35cBen Cheng return &st->null; 26325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 26425b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Allocate memory for the new string and its associated information. */ 26525b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr = newstring (st, str, len); 26625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 26725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Search in the array for the place to insert the string. If there 26825b3c049e70834cf33790a28643ab058b507b35cBen Cheng is no string with matching prefix and no string with matching 26925b3c049e70834cf33790a28643ab058b507b35cBen Cheng leading substring, create a new entry. */ 27025b3c049e70834cf33790a28643ab058b507b35cBen Cheng sep = searchstring (&st->root, newstr); 27125b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (*sep != newstr) 27225b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 27325b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* This is not the same entry. This means we have a prefix match. */ 27425b3c049e70834cf33790a28643ab058b507b35cBen Cheng if ((*sep)->len > newstr->len) 27525b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 27625b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_GStrent *subs; 27725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 27825b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Check whether we already know this string. */ 27925b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (subs = (*sep)->next; subs != NULL; subs = subs->next) 28025b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (subs->len == newstr->len) 28125b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 28225b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* We have an exact match with a substring. Free the memory 28325b3c049e70834cf33790a28643ab058b507b35cBen Cheng we allocated. */ 28425b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->left += (st->backp - (char *) newstr) * st->width; 28525b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->backp = (char *) newstr; 28625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 28725b3c049e70834cf33790a28643ab058b507b35cBen Cheng return subs; 28825b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 28925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 29025b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* We have a new substring. This means we don't need the reverse 29125b3c049e70834cf33790a28643ab058b507b35cBen Cheng string of this entry anymore. */ 29225b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->backp -= newstr->len; 29325b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->left += newstr->len; 29425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 29525b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->next = (*sep)->next; 29625b3c049e70834cf33790a28643ab058b507b35cBen Cheng (*sep)->next = newstr; 29725b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 29825b3c049e70834cf33790a28643ab058b507b35cBen Cheng else if ((*sep)->len != newstr->len) 29925b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 30025b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* When we get here it means that the string we are about to 30125b3c049e70834cf33790a28643ab058b507b35cBen Cheng add has a common prefix with a string we already have but 30225b3c049e70834cf33790a28643ab058b507b35cBen Cheng it is longer. In this case we have to put it first. */ 30325b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->total += newstr->len - (*sep)->len; 30425b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->next = *sep; 30525b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->left = (*sep)->left; 30625b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr->right = (*sep)->right; 30725b3c049e70834cf33790a28643ab058b507b35cBen Cheng *sep = newstr; 30825b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 30925b3c049e70834cf33790a28643ab058b507b35cBen Cheng else 31025b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 31125b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* We have an exact match. Free the memory we allocated. */ 31225b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->left += (st->backp - (char *) newstr) * st->width; 31325b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->backp = (char *) newstr; 31425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 31525b3c049e70834cf33790a28643ab058b507b35cBen Cheng newstr = *sep; 31625b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 31725b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 31825b3c049e70834cf33790a28643ab058b507b35cBen Cheng else 31925b3c049e70834cf33790a28643ab058b507b35cBen Cheng st->total += newstr->len; 32025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 32125b3c049e70834cf33790a28643ab058b507b35cBen Cheng return newstr; 32225b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 32325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 32425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 32525b3c049e70834cf33790a28643ab058b507b35cBen Chengstatic void 32625b3c049e70834cf33790a28643ab058b507b35cBen Chengcopystrings (struct Ebl_GStrent *nodep, char **freep, size_t *offsetp) 32725b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 32825b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct Ebl_GStrent *subs; 32925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 33025b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (nodep->left != NULL) 33125b3c049e70834cf33790a28643ab058b507b35cBen Cheng copystrings (nodep->left, freep, offsetp); 33225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 33325b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Process the current node. */ 33425b3c049e70834cf33790a28643ab058b507b35cBen Cheng nodep->offset = *offsetp; 33525b3c049e70834cf33790a28643ab058b507b35cBen Cheng *freep = (char *) mempcpy (*freep, nodep->string, nodep->len * nodep->width); 33625b3c049e70834cf33790a28643ab058b507b35cBen Cheng *offsetp += nodep->len * nodep->width; 33725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 33825b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (subs = nodep->next; subs != NULL; subs = subs->next) 33925b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 34025b3c049e70834cf33790a28643ab058b507b35cBen Cheng assert (subs->len < nodep->len); 34125b3c049e70834cf33790a28643ab058b507b35cBen Cheng subs->offset = nodep->offset + (nodep->len - subs->len) * nodep->width; 34225b3c049e70834cf33790a28643ab058b507b35cBen Cheng assert (subs->offset != 0 || subs->string[0] == '\0'); 34325b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 34425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 34525b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (nodep->right != NULL) 34625b3c049e70834cf33790a28643ab058b507b35cBen Cheng copystrings (nodep->right, freep, offsetp); 34725b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 34825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 34925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 35025b3c049e70834cf33790a28643ab058b507b35cBen Chengvoid 35125b3c049e70834cf33790a28643ab058b507b35cBen Chengebl_gstrtabfinalize (struct Ebl_GStrtab *st, Elf_Data *data) 35225b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 35325b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t copylen; 35425b3c049e70834cf33790a28643ab058b507b35cBen Cheng char *endp; 35525b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t nulllen = st->nullstr ? st->width : 0; 35625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 35725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Fill in the information. */ 35825b3c049e70834cf33790a28643ab058b507b35cBen Cheng data->d_buf = malloc (st->total + nulllen); 35925b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (data->d_buf == NULL) 36025b3c049e70834cf33790a28643ab058b507b35cBen Cheng abort (); 36125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 36225b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* The first byte must always be zero if we created the table with a 36325b3c049e70834cf33790a28643ab058b507b35cBen Cheng null string. */ 36425b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (st->nullstr) 36525b3c049e70834cf33790a28643ab058b507b35cBen Cheng memset (data->d_buf, '\0', st->width); 36625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 36725b3c049e70834cf33790a28643ab058b507b35cBen Cheng data->d_type = ELF_T_BYTE; 36825b3c049e70834cf33790a28643ab058b507b35cBen Cheng data->d_size = st->total + nulllen; 36925b3c049e70834cf33790a28643ab058b507b35cBen Cheng data->d_off = 0; 37025b3c049e70834cf33790a28643ab058b507b35cBen Cheng data->d_align = 1; 37125b3c049e70834cf33790a28643ab058b507b35cBen Cheng data->d_version = EV_CURRENT; 37225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 37325b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Now run through the tree and add all the string while also updating 37425b3c049e70834cf33790a28643ab058b507b35cBen Cheng the offset members of the elfstrent records. */ 37525b3c049e70834cf33790a28643ab058b507b35cBen Cheng endp = (char *) data->d_buf + nulllen; 37625b3c049e70834cf33790a28643ab058b507b35cBen Cheng copylen = nulllen; 37725b3c049e70834cf33790a28643ab058b507b35cBen Cheng copystrings (st->root, &endp, ©len); 37825b3c049e70834cf33790a28643ab058b507b35cBen Cheng assert (copylen == st->total * st->width + nulllen); 37925b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 38025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 38125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 38225b3c049e70834cf33790a28643ab058b507b35cBen Chengsize_t 38325b3c049e70834cf33790a28643ab058b507b35cBen Chengebl_gstrtaboffset (struct Ebl_GStrent *se) 38425b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 38525b3c049e70834cf33790a28643ab058b507b35cBen Cheng return se->offset; 38625b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 387