diff options
Diffstat (limited to 'newlib/libc/sys/linux/iconv/strtab.c')
| -rw-r--r-- | newlib/libc/sys/linux/iconv/strtab.c | 341 |
1 files changed, 0 insertions, 341 deletions
diff --git a/newlib/libc/sys/linux/iconv/strtab.c b/newlib/libc/sys/linux/iconv/strtab.c deleted file mode 100644 index 0f5e2b632..000000000 --- a/newlib/libc/sys/linux/iconv/strtab.c +++ /dev/null @@ -1,341 +0,0 @@ -/* C string table handling. - Copyright (C) 2000, 2001 Free Software Foundation, Inc. - Written by Ulrich Drepper <drepper@redhat.com>, 2000. - - This program is free software; you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2, or (at your option) - any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software Foundation, - Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ - -#ifdef HAVE_CONFIG_H -# include <config.h> -#endif - -#include <assert.h> -#include <inttypes.h> -#include <stddef.h> -#include <stdlib.h> -#include <string.h> -#include <unistd.h> -#include <sys/cdefs.h> -#include <sys/param.h> - - -struct Strent -{ - const char *string; - size_t len; - struct Strent *next; - struct Strent *left; - struct Strent *right; - size_t offset; - char reverse[0]; -}; - - -struct memoryblock -{ - struct memoryblock *next; - char memory[0]; -}; - - -struct Strtab -{ - struct Strent *root; - struct memoryblock *memory; - char *backp; - size_t left; - size_t total; - - struct Strent null; -}; - - -/* Cache for the pagesize. We correct this value a bit so that `malloc' - is not allocating more than a page. */ -static size_t ps; - - -extern void *xmalloc (size_t n) __attribute_malloc__; - -/* Prototypes for our functions that are used from iconvconfig.c. If - you change these, change also iconvconfig.c. */ -/* Create new C string table object in memory. */ -extern struct Strtab *strtabinit (void); - -/* Free resources allocated for C string table ST. */ -extern void strtabfree (struct Strtab *st); - -/* Add string STR (length LEN is != 0) to C string table ST. */ -extern struct Strent *strtabadd (struct Strtab *st, const char *str, - size_t len); - -/* Finalize string table ST and store size in *SIZE and return a pointer. */ -extern void *strtabfinalize (struct Strtab *st, size_t *size); - -/* Get offset in string table for string associated with SE. */ -extern size_t strtaboffset (struct Strent *se); - - -struct Strtab * -strtabinit (void) -{ - struct Strtab *ret; - - if (ps == 0) - { - ps = sysconf (_SC_PAGESIZE) - 2 * sizeof (void *); - assert (sizeof (struct memoryblock) < ps); - } - - ret = (struct Strtab *) calloc (1, sizeof (struct Strtab)); - if (ret != NULL) - { - ret->null.len = 1; - ret->null.string = ""; - } - return ret; -} - - -static void -morememory (struct Strtab *st, size_t len) -{ - struct memoryblock *newmem; - - if (len < ps) - len = ps; - newmem = (struct memoryblock *) malloc (len); - if (newmem == NULL) - abort (); - - newmem->next = st->memory; - st->memory = newmem; - st->backp = newmem->memory; - st->left = len - offsetof (struct memoryblock, memory); -} - - -void -strtabfree (struct Strtab *st) -{ - struct memoryblock *mb = st->memory; - - while (mb != NULL) - { - void *old = mb; - mb = mb->next; - free (old); - } - - free (st); -} - - -static struct Strent * -newstring (struct Strtab *st, const char *str, size_t len) -{ - struct Strent *newstr; - size_t align; - int i; - - /* Compute the amount of padding needed to make the structure aligned. */ - align = ((__alignof__ (struct Strent) - - (((uintptr_t) st->backp) - & (__alignof__ (struct Strent) - 1))) - & (__alignof__ (struct Strent) - 1)); - - /* Make sure there is enough room in the memory block. */ - if (st->left < align + sizeof (struct Strent) + len) - { - morememory (st, sizeof (struct Strent) + len); - align = 0; - } - - /* Create the reserved string. */ - newstr = (struct Strent *) (st->backp + align); - newstr->string = str; - newstr->len = len; - newstr->next = NULL; - newstr->left = NULL; - newstr->right = NULL; - newstr->offset = 0; - for (i = len - 2; i >= 0; --i) - newstr->reverse[i] = str[len - 2 - i]; - newstr->reverse[len - 1] = '\0'; - st->backp += align + sizeof (struct Strent) + len; - st->left -= align + sizeof (struct Strent) + len; - - return newstr; -} - - -/* XXX This function should definitely be rewritten to use a balancing - tree algorith (AVL, red-black trees). For now a simple, correct - implementation is enough. */ -static struct Strent ** -searchstring (struct Strent **sep, struct Strent *newstr) -{ - int cmpres; - - /* More strings? */ - if (*sep == NULL) - { - *sep = newstr; - return sep; - } - - /* Compare the strings. */ - cmpres = memcmp ((*sep)->reverse, newstr->reverse, - MIN ((*sep)->len, newstr->len) - 1); - if (cmpres == 0) - /* We found a matching string. */ - return sep; - else if (cmpres > 0) - return searchstring (&(*sep)->left, newstr); - else - return searchstring (&(*sep)->right, newstr); -} - - -/* Add new string. The actual string is assumed to be permanent. */ -struct Strent * -strtabadd (struct Strtab *st, const char *str, size_t len) -{ - struct Strent *newstr; - struct Strent **sep; - - /* Compute the string length if the caller doesn't know it. */ - if (len == 0) - len = strlen (str) + 1; - - /* Make sure all "" strings get offset 0. */ - if (len == 1) - return &st->null; - - /* Allocate memory for the new string and its associated information. */ - newstr = newstring (st, str, len); - - /* Search in the array for the place to insert the string. If there - is no string with matching prefix and no string with matching - leading substring, create a new entry. */ - sep = searchstring (&st->root, newstr); - if (*sep != newstr) - { - /* This is not the same entry. This means we have a prefix match. */ - if ((*sep)->len > newstr->len) - { - struct Strent *subs; - - for (subs = (*sep)->next; subs; subs = subs->next) - if (subs->len == newstr->len) - { - /* We have an exact match with a substring. Free the memory - we allocated. */ - st->left += st->backp - (char *) newstr; - st->backp = (char *) newstr; - - return subs; - } - - /* We have a new substring. This means we don't need the reverse - string of this entry anymore. */ - st->backp -= newstr->len; - st->left += newstr->len; - - newstr->next = (*sep)->next; - (*sep)->next = newstr; - } - else if ((*sep)->len != newstr->len) - { - /* When we get here it means that the string we are about to - add has a common prefix with a string we already have but - it is longer. In this case we have to put it first. */ - st->total += newstr->len - (*sep)->len; - newstr->next = *sep; - newstr->left = (*sep)->left; - newstr->right = (*sep)->right; - *sep = newstr; - } - else - { - /* We have an exact match. Free the memory we allocated. */ - st->left += st->backp - (char *) newstr; - st->backp = (char *) newstr; - - newstr = *sep; - } - } - else - st->total += newstr->len; - - return newstr; -} - - -static void -copystrings (struct Strent *nodep, char **freep, size_t *offsetp) -{ - struct Strent *subs; - - if (nodep->left != NULL) - copystrings (nodep->left, freep, offsetp); - - /* Process the current node. */ - nodep->offset = *offsetp; - *freep = (char *) memcpy (*freep, nodep->string, nodep->len); - *freep += nodep->len; - *offsetp += nodep->len; - - for (subs = nodep->next; subs != NULL; subs = subs->next) - { - assert (subs->len < nodep->len); - subs->offset = nodep->offset + nodep->len - subs->len; - } - - if (nodep->right != NULL) - copystrings (nodep->right, freep, offsetp); -} - - -void * -strtabfinalize (struct Strtab *st, size_t *size) -{ - size_t copylen; - char *endp; - char *retval; - - /* Fill in the information. */ - endp = retval = (char *) xmalloc (st->total + 1); - - /* Always put an empty string at the beginning so that a zero offset - can mean error. */ - *endp++ = '\0'; - - /* Now run through the tree and add all the string while also updating - the offset members of the elfstrent records. */ - copylen = 1; - copystrings (st->root, &endp, ©len); - assert (copylen == st->total + 1); - assert (endp = retval + st->total + 1); - *size = copylen; - - return retval; -} - - -size_t -strtaboffset (struct Strent *se) -{ - return se->offset; -} |