[PATCH] Fix iconv strtab.c

[Jakub Jelinek]

Hi!

Since the actual enabling of prefix merging in strtab, iconvconfig does not
work.
Here is a fix.
Actually, the fix is just the last hunk (say if A// was a node, now adding
BA//, the code used kill all nodes in A//'s left and right subtrees, so
they'd get offset 0), the rest are optimizations:
a) ensure that "" string gives always offset 0
b) I noticed that the substring chains (chained through ->next) contained
   a lot of duplicates, so this patch avoid them

Possible other optimizations:
c) don't make reverse zero terminated, save 1 byte for each string
d) remove the ->string field, it is only needed during finalize
   and at that time can be cheaply reconstructed from its reverse.
   The advantage would be that callers wouldn't have to make sure
   strings passed as arguments to strtabadd are kept until strtabfinalize
   (and as strtabadd may return a different string, this means they
    have to keep the copy in some other structure somewhere).

2001-09-04  Jakub Jelinek  <jakub@redhat.com>

	* iconv/strtab.c (strtabinit): Initialize null Strent.
	(newstring): Move len == 0 handling...
	(strtabadd): ...here.
	If len == 1, return null Strent.
	When inserting a suffix of an existing string, check if
	it is not equal to some suffix already recorded.
	Copy left and right members over if adding longer string.

--- iconv/strtab.c.jj	Sat Sep  1 05:15:22 2001
+++ iconv/strtab.c	Tue Sep  4 14:33:18 2001
@@ -90,13 +90,21 @@ extern size_t strtaboffset (struct Stren
 struct Strtab *
 strtabinit (void)
 {
+  struct Strtab *ret;
+
   if (ps == 0)
     {
       ps = sysconf (_SC_PAGESIZE) - 2 * sizeof (void *);
       assert (sizeof (struct memoryblock) < ps);
     }
 
-  return (struct Strtab *) calloc (1, sizeof (struct Strtab));
+  ret = (struct Strtab *) calloc (1, sizeof (struct Strtab));
+  if (ret != NULL)
+    {
+      ret->null.len = 1;
+      ret->null.string = "";
+    }
+  return ret;
 }
 
 
@@ -141,10 +149,6 @@ newstring (struct Strtab *st, const char
   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)
@@ -211,6 +215,14 @@ strtabadd (struct Strtab *st, const char
   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);
 
@@ -223,6 +235,19 @@ strtabadd (struct Strtab *st, const char
       /* 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;
@@ -238,6 +263,8 @@ strtabadd (struct Strtab *st, const char
 	     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

	Jakub