1 files changed, 294 insertions, 0 deletions
diff --git a/iconv/strtab.c b/iconv/strtab.c
new file mode 100644
index 0000000000..5b3e3283e9
--- /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;
+}