eblstrtab.c revision 441f72d43a9b550baa779fc82f70816da5f74f0e
1441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project/* ELF string table handling. 2441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project Copyright (C) 2000, 2001, 2002 Red Hat, Inc. 3441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project Written by Ulrich Drepper <drepper@redhat.com>, 2000. 4441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 5441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project This program is Open Source software; you can redistribute it and/or 6441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project modify it under the terms of the Open Software License version 1.0 as 7441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project published by the Open Source Initiative. 8441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 9441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project You should have received a copy of the Open Software License along 10441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project with this program; if not, you may obtain a copy of the Open Software 11441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project License version 1.0 from http://www.opensource.org/licenses/osl.php or 12441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project by writing the Open Source Initiative c/o Lawrence Rosen, Esq., 13441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 3001 King Ranch Road, Ukiah, CA 95482. */ 14441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 15441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#ifdef HAVE_CONFIG_H 16441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project# include <config.h> 17441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#endif 18441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 19441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#include <assert.h> 20441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#include <inttypes.h> 21441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#include <libelf.h> 22441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#include <stddef.h> 23441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#include <stdlib.h> 24441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#include <string.h> 25441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#include <unistd.h> 26441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#include <sys/param.h> 27441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 28441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#include "libebl.h" 29441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#include <system.h> 30441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 31441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#ifndef MIN 32441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project# define MIN(a, b) ((a) < (b) ? (a) : (b)) 33441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#endif 34441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 35441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 36441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectstruct Ebl_Strent 37441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 38441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project const char *string; 39441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project size_t len; 40441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct Ebl_Strent *next; 41441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct Ebl_Strent *left; 42441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct Ebl_Strent *right; 43441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project size_t offset; 44441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project char reverse[0]; 45441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project}; 46441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 47441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 48441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectstruct memoryblock 49441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 50441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct memoryblock *next; 51441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project char memory[0]; 52441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project}; 53441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 54441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 55441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectstruct Ebl_Strtab 56441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 57441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct Ebl_Strent *root; 58441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct memoryblock *memory; 59441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project char *backp; 60441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project size_t left; 61441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project size_t total; 62441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project bool nullstr; 63441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 64441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct Ebl_Strent null; 65441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project}; 66441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 67441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 68441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project/* Cache for the pagesize. We correct this value a bit so that `malloc' 69441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project is not allocating more than a page. */ 70441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectstatic size_t ps; 71441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 72441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 73441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectstruct Ebl_Strtab * 74441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectebl_strtabinit (bool nullstr) 75441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 76441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct Ebl_Strtab *ret; 77441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 78441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (ps == 0) 79441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 80441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project ps = sysconf (_SC_PAGESIZE) - 2 * sizeof (void *); 81441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project assert (sizeof (struct memoryblock) < ps); 82441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 83441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 84441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project ret = (struct Ebl_Strtab *) calloc (1, sizeof (struct Ebl_Strtab)); 85441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (ret != NULL) 86441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 87441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project ret->nullstr = nullstr; 88441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 89441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (nullstr) 90441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 91441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project ret->null.len = 1; 92441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project ret->null.string = ""; 93441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 94441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 95441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 96441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return ret; 97441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 98441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 99441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 100441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectstatic int 101441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectmorememory (struct Ebl_Strtab *st, size_t len) 102441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 103441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct memoryblock *newmem; 104441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 105441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (len < ps) 106441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project len = ps; 107441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newmem = (struct memoryblock *) malloc (len); 108441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (newmem == NULL) 109441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return 1; 110441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 111441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newmem->next = st->memory; 112441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->memory = newmem; 113441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->backp = newmem->memory; 114441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->left = len - offsetof (struct memoryblock, memory); 115441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 116441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return 0; 117441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 118441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 119441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 120441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectvoid 121441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectebl_strtabfree (struct Ebl_Strtab *st) 122441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 123441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct memoryblock *mb = st->memory; 124441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 125441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project while (mb != NULL) 126441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 127441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project void *old = mb; 128441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project mb = mb->next; 129441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project free (old); 130441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 131441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 132441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project free (st); 133441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 134441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 135441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 136441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectstatic struct Ebl_Strent * 137441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectnewstring (struct Ebl_Strtab *st, const char *str, size_t len) 138441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 139441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct Ebl_Strent *newstr; 140441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project size_t align; 141441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project int i; 142441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 143441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Compute the amount of padding needed to make the structure aligned. */ 144441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project align = ((__alignof__ (struct Ebl_Strent) 145441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project - (((uintptr_t) st->backp) 146441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project & (__alignof__ (struct Ebl_Strent) - 1))) 147441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project & (__alignof__ (struct Ebl_Strent) - 1)); 148441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 149441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Make sure there is enough room in the memory block. */ 150441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (st->left < align + sizeof (struct Ebl_Strent) + len) 151441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 152441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (morememory (st, sizeof (struct Ebl_Strent) + len)) 153441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return NULL; 154441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 155441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project align = 0; 156441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 157441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 158441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Create the reserved string. */ 159441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr = (struct Ebl_Strent *) (st->backp + align); 160441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->string = str; 161441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->len = len; 162441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->next = NULL; 163441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->left = NULL; 164441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->right = NULL; 165441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->offset = 0; 166441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project for (i = len - 2; i >= 0; --i) 167441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->reverse[i] = str[len - 2 - i]; 168441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->reverse[len - 1] = '\0'; 169441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->backp += align + sizeof (struct Ebl_Strent) + len; 170441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->left -= align + sizeof (struct Ebl_Strent) + len; 171441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 172441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return newstr; 173441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 174441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 175441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 176441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project/* XXX This function should definitely be rewritten to use a balancing 177441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project tree algorith (AVL, red-black trees). For now a simple, correct 178441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project implementation is enough. */ 179441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectstatic struct Ebl_Strent ** 180441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectsearchstring (struct Ebl_Strent **sep, struct Ebl_Strent *newstr) 181441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 182441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project int cmpres; 183441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 184441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* More strings? */ 185441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (*sep == NULL) 186441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 187441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project *sep = newstr; 188441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return sep; 189441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 190441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 191441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Compare the strings. */ 192441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project cmpres = memcmp ((*sep)->reverse, newstr->reverse, 193441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project MIN ((*sep)->len, newstr->len) - 1); 194441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (cmpres == 0) 195441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* We found a matching string. */ 196441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return sep; 197441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project else if (cmpres > 0) 198441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return searchstring (&(*sep)->left, newstr); 199441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project else 200441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return searchstring (&(*sep)->right, newstr); 201441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 202441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 203441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 204441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project/* Add new string. The actual string is assumed to be permanent. */ 205441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectstruct Ebl_Strent * 206441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectebl_strtabadd (struct Ebl_Strtab *st, const char *str, size_t len) 207441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 208441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct Ebl_Strent *newstr; 209441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct Ebl_Strent **sep; 210441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 211441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Compute the string length if the caller doesn't know it. */ 212441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (len == 0) 213441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project len = strlen (str) + 1; 214441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 215441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Make sure all "" strings get offset 0 but only if the table was 216441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project created with a special null entry in mind. */ 217441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (len == 1 && st->null.string != NULL) 218441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return &st->null; 219441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 220441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Allocate memory for the new string and its associated information. */ 221441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr = newstring (st, str, len); 222441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (newstr == NULL) 223441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return NULL; 224441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 225441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Search in the array for the place to insert the string. If there 226441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project is no string with matching prefix and no string with matching 227441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project leading substring, create a new entry. */ 228441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project sep = searchstring (&st->root, newstr); 229441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (*sep != newstr) 230441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 231441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* This is not the same entry. This means we have a prefix match. */ 232441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if ((*sep)->len > newstr->len) 233441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 234441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct Ebl_Strent *subs; 235441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 236441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Check whether we already know this string. */ 237441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project for (subs = (*sep)->next; subs != NULL; subs = subs->next) 238441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (subs->len == newstr->len) 239441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 240441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* We have an exact match with a substring. Free the memory 241441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project we allocated. */ 242441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->left += st->backp - (char *) newstr; 243441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->backp = (char *) newstr; 244441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 245441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return subs; 246441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 247441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 248441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* We have a new substring. This means we don't need the reverse 249441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project string of this entry anymore. */ 250441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->backp -= newstr->len; 251441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->left += newstr->len; 252441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 253441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->next = (*sep)->next; 254441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project (*sep)->next = newstr; 255441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 256441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project else if ((*sep)->len != newstr->len) 257441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 258441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* When we get here it means that the string we are about to 259441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project add has a common prefix with a string we already have but 260441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project it is longer. In this case we have to put it first. */ 261441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->total += newstr->len - (*sep)->len; 262441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->next = *sep; 263441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->left = (*sep)->left; 264441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr->right = (*sep)->right; 265441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project *sep = newstr; 266441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 267441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project else 268441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 269441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* We have an exact match. Free the memory we allocated. */ 270441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->left += st->backp - (char *) newstr; 271441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->backp = (char *) newstr; 272441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 273441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project newstr = *sep; 274441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 275441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 276441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project else 277441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project st->total += newstr->len; 278441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 279441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return newstr; 280441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 281441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 282441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 283441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectstatic void 284441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectcopystrings (struct Ebl_Strent *nodep, char **freep, size_t *offsetp) 285441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 286441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project struct Ebl_Strent *subs; 287441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 288441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (nodep->left != NULL) 289441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project copystrings (nodep->left, freep, offsetp); 290441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 291441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Process the current node. */ 292441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project nodep->offset = *offsetp; 293441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project *freep = (char *) mempcpy (*freep, nodep->string, nodep->len); 294441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project *offsetp += nodep->len; 295441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 296441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project for (subs = nodep->next; subs != NULL; subs = subs->next) 297441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 298441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project assert (subs->len < nodep->len); 299441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project subs->offset = nodep->offset + nodep->len - subs->len; 300441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project assert (subs->offset != 0 || subs->string[0] == '\0'); 301441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 302441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 303441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (nodep->right != NULL) 304441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project copystrings (nodep->right, freep, offsetp); 305441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 306441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 307441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 308441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectvoid 309441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectebl_strtabfinalize (struct Ebl_Strtab *st, Elf_Data *data) 310441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 311441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project size_t copylen; 312441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project char *endp; 313441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project size_t nulllen = st->nullstr ? 1 : 0; 314441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 315441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Fill in the information. */ 316441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project data->d_buf = malloc (st->total + nulllen); 317441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (data->d_buf == NULL) 318441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project abort (); 319441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 320441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* The first byte must always be zero if we created the table with a 321441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project null string. */ 322441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (st->nullstr) 323441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project *((char *) data->d_buf) = '\0'; 324441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 325441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project data->d_type = ELF_T_BYTE; 326441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project data->d_size = st->total + nulllen; 327441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project data->d_off = 0; 328441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project data->d_align = 1; 329441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project data->d_version = EV_CURRENT; 330441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 331441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Now run through the tree and add all the string while also updating 332441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project the offset members of the elfstrent records. */ 333441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project endp = (char *) data->d_buf + nulllen; 334441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project copylen = nulllen; 335441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project copystrings (st->root, &endp, ©len); 336441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project assert (copylen == st->total + nulllen); 337441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 338441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 339441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 340441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectsize_t 341441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectebl_strtaboffset (struct Ebl_Strent *se) 342441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 343441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return se->offset; 344441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 345441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 346441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 347441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectconst char * 348441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectebl_string (struct Ebl_Strent *se) 349441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 350441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project assert (se->string != NULL); 351441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 352441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return se->string; 353441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 354