1441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project/* Generic string table handling. 2cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng Copyright (C) 2000, 2001, 2002, 2005 Red Hat, Inc. 3cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng This file is part of Red Hat elfutils. 4441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project Written by Ulrich Drepper <drepper@redhat.com>, 2000. 5441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 6cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng Red Hat elfutils is free software; you can redistribute it and/or modify 7cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng it under the terms of the GNU General Public License as published by the 8cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng Free Software Foundation; version 2 of the License. 9cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng 10cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng Red Hat elfutils is distributed in the hope that it will be useful, but 11cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng WITHOUT ANY WARRANTY; without even the implied warranty of 12cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng General Public License for more details. 14cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng 15cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng You should have received a copy of the GNU General Public License along 16cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng with Red Hat elfutils; if not, write to the Free Software Foundation, 17cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301 USA. 18cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng 19cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng In addition, as a special exception, Red Hat, Inc. gives You the 20cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng additional right to link the code of Red Hat elfutils with code licensed 21cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng under any Open Source Initiative certified open source license 22cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng (http://www.opensource.org/licenses/index.php) which requires the 23cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng distribution of source code with any binary distribution and to 24cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng distribute linked combinations of the two. Non-GPL Code permitted under 25cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng this exception must only link to the code of Red Hat elfutils through 26cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng those well defined interfaces identified in the file named EXCEPTION 27cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng found in the source code files (the "Approved Interfaces"). The files 28cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng of Non-GPL Code may instantiate templates or use macros or inline 29cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng functions from the Approved Interfaces without causing the resulting 30cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng work to be covered by the GNU General Public License. Only Red Hat, 31cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng Inc. may make changes or additions to the list of Approved Interfaces. 32cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng Red Hat's grant of this exception is conditioned upon your not adding 33cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng any new exceptions. If you wish to add a new Approved Interface or 34cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng exception, please contact Red Hat. You must obey the GNU General Public 35cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng License in all respects for all of the Red Hat elfutils code and other 36cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng code used in conjunction with Red Hat elfutils except the Non-GPL Code 37cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng covered by this exception. If you modify this file, you may extend this 38cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng exception to your version of the file, but you are not obligated to do 39cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng so. If you do not wish to provide this exception without modification, 40cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng you must delete this exception statement from your version and license 41cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng this file solely under the GPL without exception. 42cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng 43cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng Red Hat elfutils is an included package of the Open Invention Network. 44cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng An included package of the Open Invention Network is a package for which 45cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng Open Invention Network licensees cross-license their patents. No patent 46cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng license is granted, either expressly or impliedly, by designation as an 47cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng included package. Should you wish to participate in the Open Invention 48cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng Network licensing program, please visit www.openinventionnetwork.com 49cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng <http://www.openinventionnetwork.com>. */ 50441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 51441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#ifdef HAVE_CONFIG_H 52441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project# include <config.h> 53441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#endif 54441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 55441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#include <assert.h> 56441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#include <inttypes.h> 57441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#include <libelf.h> 58441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#include <stddef.h> 59441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#include <stdlib.h> 60441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#include <string.h> 61441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#include <unistd.h> 62441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#include <sys/param.h> 63441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 64441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#include "libebl.h" 65441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 66441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#ifndef MIN 67441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project# define MIN(a, b) ((a) < (b) ? (a) : (b)) 68441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#endif 69441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 70441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 71441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectstruct Ebl_GStrent 72441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 73441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project const char *string; 74441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project size_t len; 75441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct Ebl_GStrent *next; 76441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct Ebl_GStrent *left; 77441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct Ebl_GStrent *right; 78441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project size_t offset; 79441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project unsigned int width; 80441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project char reverse[0]; 81441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project}; 82441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 83441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 84441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectstruct memoryblock 85441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 86441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct memoryblock *next; 87441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project char memory[0]; 88441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project}; 89441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 90441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 91441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectstruct Ebl_GStrtab 92441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 93441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct Ebl_GStrent *root; 94441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct memoryblock *memory; 95441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project char *backp; 96441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project size_t left; 97441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project size_t total; 98441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project unsigned int width; 99441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project bool nullstr; 100441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 101441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct Ebl_GStrent null; 102441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project}; 103441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 104441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 105441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project/* Cache for the pagesize. We correct this value a bit so that `malloc' 106441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project is not allocating more than a page. */ 107441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectstatic size_t ps; 108441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 109441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 110441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectstruct Ebl_GStrtab * 111441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectebl_gstrtabinit (unsigned int width, bool nullstr) 112441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 113441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct Ebl_GStrtab *ret; 114441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 115441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (ps == 0) 116441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 117441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project ps = sysconf (_SC_PAGESIZE) - 2 * sizeof (void *); 118441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project assert (sizeof (struct memoryblock) < ps); 119441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 120441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 121441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project ret = (struct Ebl_GStrtab *) calloc (1, sizeof (struct Ebl_GStrtab)); 122441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (ret != NULL) 123441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 124441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project ret->width = width; 125441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project ret->nullstr = nullstr; 126441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 127441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (nullstr) 128441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 129441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project ret->null.len = 1; 130441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project ret->null.string = (char *) calloc (1, width); 131441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 132441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 133441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 134441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return ret; 135441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 136441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 137441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 138441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectstatic void 139441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectmorememory (struct Ebl_GStrtab *st, size_t len) 140441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 141441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct memoryblock *newmem; 142441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 143441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (len < ps) 144441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project len = ps; 145441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newmem = (struct memoryblock *) malloc (len); 146441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (newmem == NULL) 147441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project abort (); 148441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 149441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newmem->next = st->memory; 150441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->memory = newmem; 151441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->backp = newmem->memory; 152441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->left = len - offsetof (struct memoryblock, memory); 153441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 154441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 155441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 156441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectvoid 157441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectebl_gstrtabfree (struct Ebl_GStrtab *st) 158441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 159441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct memoryblock *mb = st->memory; 160441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 161441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project while (mb != NULL) 162441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 163441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project void *old = mb; 164441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project mb = mb->next; 165441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project free (old); 166441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 167441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 168441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (st->null.string != NULL) 169441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project free ((char *) st->null.string); 170441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 171441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project free (st); 172441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 173441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 174441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 175441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectstatic struct Ebl_GStrent * 176441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectnewstring (struct Ebl_GStrtab *st, const char *str, size_t len) 177441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 178441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Compute the amount of padding needed to make the structure aligned. */ 179cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng size_t align = ((__alignof__ (struct Ebl_GStrent) 180cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng - (((uintptr_t) st->backp) 181cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng & (__alignof__ (struct Ebl_GStrent) - 1))) 182cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng & (__alignof__ (struct Ebl_GStrent) - 1)); 183441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 184441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Make sure there is enough room in the memory block. */ 185441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (st->left < align + sizeof (struct Ebl_GStrent) + len * st->width) 186441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 187441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project morememory (st, sizeof (struct Ebl_GStrent) + len * st->width); 188441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project align = 0; 189441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 190441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 191441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Create the reserved string. */ 192cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng struct Ebl_GStrent *newstr = (struct Ebl_GStrent *) (st->backp + align); 193441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->string = str; 194441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->len = len; 195441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->width = st->width; 196441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->next = NULL; 197441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->left = NULL; 198441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->right = NULL; 199441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->offset = 0; 200cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng for (int i = len - 2; i >= 0; --i) 201cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng for (int j = st->width - 1; j >= 0; --j) 202441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->reverse[i * st->width + j] = str[(len - 2 - i) * st->width + j]; 203cc6695e2684ce93cdf8bd2da63d55d2cf49ff076Ben Cheng for (size_t j = 0; j < st->width; ++j) 204441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->reverse[(len - 1) * st->width + j] = '\0'; 205441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->backp += align + sizeof (struct Ebl_GStrent) + len * st->width; 206441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->left -= align + sizeof (struct Ebl_GStrent) + len * st->width; 207441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 208441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return newstr; 209441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 210441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 211441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 212441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project/* XXX This function should definitely be rewritten to use a balancing 213441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project tree algorith (AVL, red-black trees). For now a simple, correct 214441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project implementation is enough. */ 215441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectstatic struct Ebl_GStrent ** 216441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectsearchstring (struct Ebl_GStrent **sep, struct Ebl_GStrent *newstr) 217441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 218441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project int cmpres; 219441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 220441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* More strings? */ 221441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (*sep == NULL) 222441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 223441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project *sep = newstr; 224441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return sep; 225441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 226441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 227441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Compare the strings. */ 228441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project cmpres = memcmp ((*sep)->reverse, newstr->reverse, 229441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project (MIN ((*sep)->len, newstr->len) - 1) * (*sep)->width); 230441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (cmpres == 0) 231441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* We found a matching string. */ 232441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return sep; 233441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project else if (cmpres > 0) 234441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return searchstring (&(*sep)->left, newstr); 235441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project else 236441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return searchstring (&(*sep)->right, newstr); 237441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 238441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 239441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 240441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project/* Add new string. The actual string is assumed to be permanent. */ 241441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectstruct Ebl_GStrent * 242441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectebl_gstrtabadd (struct Ebl_GStrtab *st, const char *str, size_t len) 243441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 244441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct Ebl_GStrent *newstr; 245441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct Ebl_GStrent **sep; 246441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 247441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Compute the string length if the caller doesn't know it. */ 248441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (len == 0) 249441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 250441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project size_t j; 251441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 252441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project do 253441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project for (j = 0; j < st->width; ++j) 254441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (str[len * st->width + j] != '\0') 255441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project break; 256441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project while (j == st->width && ++len); 257441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 258441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 259441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Make sure all "" strings get offset 0 but only if the table was 260441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project created with a special null entry in mind. */ 261441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (len == 1 && st->null.string != NULL) 262441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return &st->null; 263441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 264441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Allocate memory for the new string and its associated information. */ 265441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr = newstring (st, str, len); 266441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 267441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Search in the array for the place to insert the string. If there 268441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project is no string with matching prefix and no string with matching 269441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project leading substring, create a new entry. */ 270441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project sep = searchstring (&st->root, newstr); 271441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (*sep != newstr) 272441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 273441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* This is not the same entry. This means we have a prefix match. */ 274441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if ((*sep)->len > newstr->len) 275441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 276441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct Ebl_GStrent *subs; 277441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 278441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Check whether we already know this string. */ 279441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project for (subs = (*sep)->next; subs != NULL; subs = subs->next) 280441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (subs->len == newstr->len) 281441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 282441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* We have an exact match with a substring. Free the memory 283441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project we allocated. */ 284441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->left += (st->backp - (char *) newstr) * st->width; 285441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->backp = (char *) newstr; 286441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 287441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return subs; 288441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 289441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 290441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* We have a new substring. This means we don't need the reverse 291441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project string of this entry anymore. */ 292441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->backp -= newstr->len; 293441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->left += newstr->len; 294441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 295441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->next = (*sep)->next; 296441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project (*sep)->next = newstr; 297441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 298441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project else if ((*sep)->len != newstr->len) 299441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 300441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* When we get here it means that the string we are about to 301441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project add has a common prefix with a string we already have but 302441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project it is longer. In this case we have to put it first. */ 303441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->total += newstr->len - (*sep)->len; 304441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->next = *sep; 305441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->left = (*sep)->left; 306441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->right = (*sep)->right; 307441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project *sep = newstr; 308441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 309441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project else 310441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 311441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* We have an exact match. Free the memory we allocated. */ 312441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->left += (st->backp - (char *) newstr) * st->width; 313441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->backp = (char *) newstr; 314441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 315441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr = *sep; 316441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 317441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 318441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project else 319441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->total += newstr->len; 320441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 321441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return newstr; 322441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 323441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 324441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 325441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectstatic void 326441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectcopystrings (struct Ebl_GStrent *nodep, char **freep, size_t *offsetp) 327441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 328441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct Ebl_GStrent *subs; 329441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 330441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (nodep->left != NULL) 331441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project copystrings (nodep->left, freep, offsetp); 332441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 333441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Process the current node. */ 334441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project nodep->offset = *offsetp; 335441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project *freep = (char *) mempcpy (*freep, nodep->string, nodep->len * nodep->width); 336441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project *offsetp += nodep->len * nodep->width; 337441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 338441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project for (subs = nodep->next; subs != NULL; subs = subs->next) 339441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 340441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project assert (subs->len < nodep->len); 341441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project subs->offset = nodep->offset + (nodep->len - subs->len) * nodep->width; 342441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project assert (subs->offset != 0 || subs->string[0] == '\0'); 343441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 344441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 345441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (nodep->right != NULL) 346441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project copystrings (nodep->right, freep, offsetp); 347441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 348441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 349441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 350441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectvoid 351441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectebl_gstrtabfinalize (struct Ebl_GStrtab *st, Elf_Data *data) 352441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 353441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project size_t copylen; 354441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project char *endp; 355441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project size_t nulllen = st->nullstr ? st->width : 0; 356441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 357441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Fill in the information. */ 358441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project data->d_buf = malloc (st->total + nulllen); 359441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (data->d_buf == NULL) 360441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project abort (); 361441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 362441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* The first byte must always be zero if we created the table with a 363441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project null string. */ 364441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (st->nullstr) 365441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project memset (data->d_buf, '\0', st->width); 366441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 367441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project data->d_type = ELF_T_BYTE; 368441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project data->d_size = st->total + nulllen; 369441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project data->d_off = 0; 370441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project data->d_align = 1; 371441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project data->d_version = EV_CURRENT; 372441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 373441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Now run through the tree and add all the string while also updating 374441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project the offset members of the elfstrent records. */ 375441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project endp = (char *) data->d_buf + nulllen; 376441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project copylen = nulllen; 377441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project copystrings (st->root, &endp, ©len); 378441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project assert (copylen == st->total * st->width + nulllen); 379441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 380441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 381441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 382441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectsize_t 383441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectebl_gstrtaboffset (struct Ebl_GStrent *se) 384441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 385441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return se->offset; 386441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 387