aboutsummaryrefslogtreecommitdiff
path: root/iconv/strtab.c
diff options
context:
space:
mode:
authorUlrich Drepper <drepper@redhat.com>2001-07-22 17:47:08 +0000
committerUlrich Drepper <drepper@redhat.com>2001-07-22 17:47:08 +0000
commit6b98979fc9e48f7627068426c49780f74f482750 (patch)
treed268769299237c3e7a3daa824289f1063b9a4fd1 /iconv/strtab.c
parent2c4223669598910462717212b583ef0be08dc2bb (diff)
downloadglibc-6b98979fc9e48f7627068426c49780f74f482750.zip
glibc-6b98979fc9e48f7627068426c49780f74f482750.tar.gz
glibc-6b98979fc9e48f7627068426c49780f74f482750.tar.bz2
Update.
2001-07-22 Ulrich Drepper <drepper@redhat.com> * iconv/gconv_builtin.c (struct builtin_map): Remove init and end elements. (BUILTIN_TRANSFORMATION): Remove Init and End parameters. (__gconv_get_builtin_trans): Initialize __init_fct and __end_fct to NULL. * iconv/gconv_builtin.h: Remove NULL parameters for Init and End in all BUILTIN_TRANSFORMATION calls. * iconv/gconv_conf.c (BUILTIN_TRANSFORMATION): Remove Init and End parameters. * iconv/gconv_simple.c: Likewise. * iconv/gconv_db.c (gen_steps): Internal converters don't have initializers, move the code accordingly. * iconv/gconv_conf.c (__gconv_read_conf): Don't read configuration file if STATIC_GCONV is defined. * iconv/gconv_conf.c (__gconv_path_envvar): New global variable. (__gconv_get_path): Use it instead of call getenv. (__gconv_read_conf): First see whether cache can be used. If yes, don't do any work here. * iconv/gconv_db.c (__gconv_release_step): Renamed from release_step and exported. Change callers. (__gconv_find_transform): First call __gconv_lookup_cache and only continue if it signals no cache available. Remove some unnecessary tests. * iconv/gconv_int.h: Declare __gconv_path_envvar, __gconv_lookup_cache, __gconv_release_step, and __gconv_loaded_cache. * iconv/gconv_cache.c: New file. * iconv/iconvconfig.c: New file. * iconv/iconvconfig.h: New file. * iconv/strtab.c: New file. * iconv/Makefile: Add rules to build new files and programs.
Diffstat (limited to 'iconv/strtab.c')
-rw-r--r--iconv/strtab.c294
1 files changed, 294 insertions, 0 deletions
diff --git a/iconv/strtab.c b/iconv/strtab.c
new file mode 100644
index 0000000..5b3e328
--- /dev/null
+++ b/iconv/strtab.c
@@ -0,0 +1,294 @@
+/* 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 <stdlib.h>
+#include <string.h>
+#include <unistd.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__));
+
+
+struct Strtab *
+strtabinit (void)
+{
+ if (ps == 0)
+ {
+ ps = sysconf (_SC_PAGESIZE) - 2 * sizeof (void);
+ assert (sizeof (struct memoryblock) < ps);
+ }
+
+ return (struct Strtab *) calloc (1, sizeof (struct Strtab));
+}
+
+
+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;
+}
+
+
+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 string length if the caller doesn't know it. */
+ if (len == 0)
+ len = strlen (str) + 1;
+
+ /* 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));
+ 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;
+
+ /* 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)
+ {
+ /* 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. */
+ newstr->next = *sep;
+ *sep = newstr;
+
+ st->total += newstr->len - (*sep)->len;
+ }
+ 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 *) mempcpy (*freep, nodep->string, 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, &copylen);
+ assert (copylen == st->total + 1);
+ assert (endp = retval + st->total + 1);
+ *size = copylen;
+
+ return retval;
+}
+
+
+size_t
+strtaboffset (struct Strent *se)
+{
+ return se->offset;
+}