Sat Mar 23 17:52:49 1996 Ulrich Drepper <drepper@gnu.ai.mit.edu>
authorroland <roland>
Thu, 28 Mar 1996 07:42:05 +0000 (07:42 +0000)
committerroland <roland>
Thu, 28 Mar 1996 07:42:05 +0000 (07:42 +0000)
* string/strcoll.c, string/strxfrm.c: Real implementation of
        string collation according to ISO C.

string/strcoll.c
string/strxfrm.c

index 9dee89f..13e9f0d 100644 (file)
@@ -1,5 +1,6 @@
-/* Copyright (C) 1995 Free Software Foundation, Inc.
+/* Copyright (C) 1995, 1996 Free Software Foundation, Inc.
 This file is part of the GNU C Library.
+Written by Ulrich Drepper, <drepper@gnu.ai.mit.edu>.
 
 The GNU C Library is free software; you can redistribute it and/or
 modify it under the terms of the GNU Library General Public License as
@@ -13,22 +14,145 @@ Library General Public License for more details.
 
 You should have received a copy of the GNU Library General Public
 License along with the GNU C Library; see the file COPYING.LIB.  If
-not, write to the Free Software Foundation, Inc., 675 Mass Ave,
-Cambridge, MA 02139, USA.  */
+not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA.  */
 
 #include <stddef.h>
 #include <stdlib.h>
 #include <string.h>
+#include "localeinfo.h"
+
+#ifndef STRING_TYPE
+# define STRING_TYPE char
+# define USTRING_TYPE unsigned char
+# define STRCOLL strcoll
+#endif
+
+/* Include the shared helper functions.  `strxfrm'/`wcsxfrm' also use
+   these functions.  */
+#include "weight.h"
 
 
 /* Compare S1 and S2, returning less than, equal to or
-   greater than zero if the collated form of S1 is lexiographically
+   greater than zero if the collated form of S1 is lexicographically
    less than, equal to or greater than the collated form of S2.  */
 int
-strcoll (s1, s2)
-     const char *s1;
-     const char *s2;
+STRCOLL (s1, s2)
+     const STRING_TYPE *s1;
+     const STRING_TYPE *s2;
 {
-  /* XXX LC_COLLATE not implemented yet.  */
-  return strcmp (s1, s2);
+  weight_t *s1forw = NULL;
+  weight_t *s1backw = NULL;
+  weight_t *s2forw = NULL;
+  weight_t *s2backw = NULL;
+  size_t pass;
+
+  /* If the current locale does not specify locale data we use normal
+     8-bit string comparison.  */
+  if (collate_nrules == 0)
+    return strcmp (s1, s2);
+
+  /* Get full information about the strings.  This means we get
+     information for all passes in a special data structure.  */
+  get_string (s1, s1forw, s1backw);
+  get_string (s2, s2forw, s2backw);
+
+  /* Now we have all the information.  In at most the given number of
+     passes we can finally decide about the order.  */
+  for (pass = 0; pass < collate_nrules; ++pass)
+    {
+      int forward = (collate_rules[pass] & sort_forward) != 0;
+      const weight_t *s1run = forward ? s1forw : s1backw;
+      const weight_t *s2run = forward ? s2forw : s2backw;
+      int s1idx = forward ? 0 : s1run->data[pass].number - 1;
+      int s2idx = forward ? 0 : s2run->data[pass].number - 1;
+
+      do
+       {
+         int s1ignore = 0;
+         int s2ignore = 0;
+         u32_t w1, w2;
+
+         /* Here we have to check for IGNORE entries.  If these are
+            found we count them and go on witht he next value.  */
+         while ((w1 = s1run->data[pass].value[s1idx]) == IGNORE_CHAR)
+           {
+             ++s1ignore;
+             if ((forward && ++s1idx >= s1run->data[pass].number)
+                 || (!forward && --s1idx < 0))
+               {
+                 weight_t *nextp = forward ? s1run->next : s1run->prev;
+                 if (nextp == NULL)
+                   {
+                     w1 = 0;
+                     break;
+                   }
+                 s1run = nextp;
+                 s1idx = forward ? 0 : s1run->data[pass].number - 1;
+               }
+           }
+
+         while ((w2 = s2run->data[pass].value[s2idx]) == IGNORE_CHAR)
+           {
+             ++s2ignore;
+             if ((forward && ++s2idx >= s2run->data[pass].number)
+                 || (!forward && --s2idx < 0))
+               {
+                 weight_t *nextp = forward ? s2run->next : s2run->prev;
+                 if (nextp == NULL)
+                   {
+                     w2 = 0;
+                     break;
+                   }
+                 s2run = nextp;
+                 s2idx = forward ? 0 : s2run->data[pass].number - 1;
+               }
+           }
+
+         /* Now we have information of the number of ignored
+            weights and the value of the next weight.  */
+         if ((collate_rules[pass] & sort_position) != 0
+             && s1ignore != s2ignore && (w1 != 0 || w2 != 0))
+           return s1ignore < s2ignore ? -1 : 1;
+
+         if (w1 != w2)
+           return w1 < w2 ? -1 : 1;
+
+         /* We have to increment the index counters.  */
+         if ((forward && ++s1idx >= s1run->data[pass].number)
+             || (!forward && --s1idx < 0))
+           if (forward)
+             {
+               s1run = s1run->next;
+               s1idx = 0;
+             }
+           else
+             {
+               s1run = s1run->prev;
+               if (s1run != NULL)
+                 s1idx = s1run->data[pass].number - 1;
+             }
+
+         if ((forward && ++s2idx >= s2run->data[pass].number)
+             || (!forward && --s2idx < 0))
+           if (forward)
+             {
+               s2run = s2run->next;
+               s2idx = 0;
+             }
+           else
+             {
+               s2run = s2run->prev;
+               if (s2run != NULL)
+                 s2idx = s2run->data[pass].number - 1;
+             }
+
+       }
+      while (s1run != NULL && s2run != NULL);
+
+      if (s1run != s2run)
+       return s1run != NULL ? 1 : -1;
+    }
+
+  return 0;
 }
index e40ae1c..7dce9c1 100644 (file)
@@ -1,5 +1,6 @@
-/* Copyright (C) 1995 Free Software Foundation, Inc.
+/* Copyright (C) 1995, 1996 Free Software Foundation, Inc.
 This file is part of the GNU C Library.
+Written by Ulrich Drepper, <drepper@gnu.ai.mit.edu>.
 
 The GNU C Library is free software; you can redistribute it and/or
 modify it under the terms of the GNU Library General Public License as
@@ -13,12 +14,87 @@ Library General Public License for more details.
 
 You should have received a copy of the GNU Library General Public
 License along with the GNU C Library; see the file COPYING.LIB.  If
-not, write to the Free Software Foundation, Inc., 675 Mass Ave,
-Cambridge, MA 02139, USA.  */
+not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA.  */
 
 #include <stddef.h>
 #include <stdlib.h>
 #include <string.h>
+#include "localeinfo.h"
+
+#ifndef STRING_TYPE
+# define STRING_TYPE char
+# define USTRING_TYPE unsigned char
+# define STRXFRM strxfrm
+# define STRLEN strlen
+# define STPNCPY __stpncpy
+#endif
+
+/* Include the shared helper functions.  `strxfrm'/`wcsxfrm' also use
+   these functions.  */
+#include "weight.h"
+
+
+/* Write 32 bit value UTF-8 encoded but only if enough space is left.  */
+static __inline size_t
+print_val (value, dest, max, act)
+     u32_t value;
+     STRING_TYPE *dest;
+     size_t max;
+     size_t act;
+{
+  char tmp[6];
+  int idx = 0;
+
+  if (value < 0x80)
+    tmp[idx++] = (char) value;
+  else
+    {
+      tmp[idx++] = '\x80' + (char) (value & 0x3f);
+      value >>= 6;
+
+      if (value < 0x20)
+       tmp[idx++] = '\xc0' + (char) value;
+      else
+       {
+         tmp[idx++] = '\x80' + (char) (value & 0x3f);
+         value >>= 6;
+
+         if (value < 0x10)
+           tmp[idx++] = '\xe0' + (char) value;
+         else
+           {
+             tmp[idx++] = '\x80' + (char) (value & 0x3f);
+             value >>= 6;
+
+             if (value < 0x08)
+               tmp[idx++] = '\xf0' + (char) value;
+             else
+               {
+                 tmp[idx++] = '\x80' + (char) (value & 0x3f);
+                 value >>= 6;
+
+                 if (value < 0x04)
+                   tmp[idx++] = '\xf8' + (char) value;
+                 else
+                   {
+                     tmp[idx++] = '\x80' + (char) (value & 0x3f);
+                     tmp[idx++] = '\xfc' + (char) (value >> 6);
+                   }
+               }
+           }
+       }
+    }
+
+  while (idx-- > 0)
+    {
+      if (act < max)
+       dest[act] = tmp[idx];
+      ++act;
+    }
+
+  return act;
+}
 
 
 /* Transform SRC into a form such that the result of strcmp
@@ -27,13 +103,94 @@ Cambridge, MA 02139, USA.  */
    their transformation.  The transformed string is put in at
    most N characters of DEST and its length is returned.  */
 size_t
-strxfrm (dest, src, n)
-     char *dest;
-     const char *src;
+STRXFRM (dest, src, n)
+     STRING_TYPE *dest;
+     const STRING_TYPE *src;
      size_t n;
 {
-  if (n == 0)
-    return strlen (src);
+  weight_t *forw = NULL;
+  weight_t *backw = NULL;
+  size_t pass;
+  size_t written;
+
+  /* If the current locale does not specify locale data we use normal
+     8-bit string comparison.  */
+  if (collate_nrules == 0)
+    {
+      if (n != 0)
+       STPNCPY (dest, src, n);
+
+      return STRLEN (src);
+    }
+
+  /* Get full information about the string.  This means we get
+     information for all passes in a special data structure.  */
+  get_string (src, forw, backw);
+
+  /* Now we have all the information.  In at most the given number of
+     passes we can finally decide about the order.  */
+  written = 0;
+  for (pass = 0; pass < collate_nrules; ++pass)
+    {
+      int forward = (collate_rules[pass] & sort_forward) != 0;
+      const weight_t *run = forward ? forw : backw;
+      int idx = forward ? 0 : run->data[pass].number - 1;
+
+      do
+       {
+         int ignore = 0;
+         u32_t w;
+
+         /* Here we have to check for IGNORE entries.  If these are
+            found we count them and go on witht he next value.  */
+         while ((w = run->data[pass].value[idx]) == IGNORE_CHAR)
+           {
+             ++ignore;
+             if ((forward && ++idx >= run->data[pass].number)
+                 || (!forward && --idx < 0))
+               {
+                 weight_t *nextp = forward ? run->next : run->prev;
+                 if (nextp == NULL)
+                   {
+                     w = 0;
+                     break;
+                   }
+                 run = nextp;
+                 idx = forward ? 0 : run->data[pass].number - 1;
+               }
+           }
+
+         /* Now we have information of the number of ignored weights
+            and the value of the next weight.  We have to add 2
+            because 0 means EOS and 1 is the intermediate string end.  */
+         if ((collate_rules[pass] & sort_position) != 0)
+           written = print_val (ignore + 2, dest, n, written);
+
+         if (w != 0)
+           written = print_val (w, dest, n, written);
+
+         /* We have to increment the index counters.  */
+         if ((forward && ++idx >= run->data[pass].number)
+             || (!forward && --idx < 0))
+           if (forward)
+             {
+               run = run->next;
+               idx = 0;
+             }
+           else
+             {
+               run = run->prev;
+               if (run != NULL)
+                 idx = run->data[pass].number - 1;
+             }
+       }
+      while (run != NULL);
+
+      /* Write marker for end of word.  */
+      if (pass + 1 < collate_nrules)
+       written = print_val (1, dest, n, written);
+    }
 
-  return __stpncpy (dest, src, n) - dest;
+  /* Terminate string.  */
+  return print_val (0, dest, n, written);
 }