string/strxfrm.c

   1 /* Copyright (C) 1995, 1996, 1997 Free Software Foundation, Inc.
   2    This file is part of the GNU C Library.
   3    Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1995.
   4
   5    The GNU C Library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Library General Public License as
   7    published by the Free Software Foundation; either version 2 of the
   8    License, or (at your option) any later version.
   9
  10    The GNU C Library is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    Library General Public License for more details.
  14
  15    You should have received a copy of the GNU Library General Public
  16    License along with the GNU C Library; see the file COPYING.LIB.  If not,
  17    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18    Boston, MA 02111-1307, USA.  */
  19
  20 #include <stddef.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23
  24 #ifndef WIDE_VERSION
  25 # define STRING_TYPE char
  26 # define USTRING_TYPE unsigned char
  27 # define L_(Ch) Ch
  28 # define STRXFRM strxfrm
  29 # define STRLEN strlen
  30 # define STPNCPY __stpncpy
  31 #endif
  32
  33 /* Include the shared helper functions.  `strxfrm'/`wcsxfrm' also use
  34    these functions.  */
  35 #include "../locale/weight.h"
  36
  37
  38 #ifndef WIDE_VERSION
  39 /* Write 32 bit value UTF-8 encoded but only if enough space is left.  */
  40 static __inline size_t
  41 print_val (u_int32_t value, char *dest, size_t max, size_t act)
  42 {
  43   char tmp[6];
  44   int idx = 0;
  45
  46   if (value < 0x80)
  47     tmp[idx++] = (char) value;
  48   else
  49     {
  50       tmp[idx++] = '\x80' + (char) (value & 0x3f);
  51       value >>= 6;
  52
  53       if (value < 0x20)
  54         tmp[idx++] = '\xc0' + (char) value;
  55       else
  56         {
  57           tmp[idx++] = '\x80' + (char) (value & 0x3f);
  58           value >>= 6;
  59
  60           if (value < 0x10)
  61             tmp[idx++] = '\xe0' + (char) value;
  62           else
  63             {
  64               tmp[idx++] = '\x80' + (char) (value & 0x3f);
  65               value >>= 6;
  66
  67               if (value < 0x08)
  68                 tmp[idx++] = '\xf0' + (char) value;
  69               else
  70                 {
  71                   tmp[idx++] = '\x80' + (char) (value & 0x3f);
  72                   value >>= 6;
  73
  74                   if (value < 0x04)
  75                     tmp[idx++] = '\xf8' + (char) value;
  76                   else
  77                     {
  78                       tmp[idx++] = '\x80' + (char) (value & 0x3f);
  79                       tmp[idx++] = '\xfc' + (char) (value >> 6);
  80                     }
  81                 }
  82             }
  83         }
  84     }
  85
  86   while (idx-- > 0)
  87     {
  88       if (act < max)
  89         dest[act] = tmp[idx];
  90       ++act;
  91     }
  92
  93   return act;
  94 }
  95 #else
  96 static __inline size_t
  97 print_val (u_int32_t value, wchar_t *dest, size_t max, size_t act)
  98 {
  99   /* We cannot really assume wchar_t is 32 bits wide.  But it is for
 100      GCC and so we don't do much optimization for the other case.  */
 101   if (sizeof (wchar_t) == 4)
 102     {
 103       if (act < max)
 104         dest[act] = (wchar_t) value;
 105       ++act;
 106     }
 107   else
 108     {
 109       wchar_t tmp[3];
 110       size_t idx = 0;
 111
 112       if (value < 0x8000)
 113         tmp[idx++] = (wchar_t) act;
 114       else
 115         {
 116           tmp[idx++] = (wchar_t) (0x8000 + (value & 0x3fff));
 117           value >>= 14;
 118           if (value < 0x2000)
 119             tmp[idx++] = (wchar_t) (0xc000 + value);
 120           else
 121             {
 122               tmp[idx++] = (wchar_t) (0x8000 + (value & 0x3fff));
 123               value >>= 14;
 124               tmp[idx++] = (wchar_t) (0xe000 + value);
 125             }
 126         }
 127       while (idx-- > 0)
 128         {
 129           if (act < max)
 130             dest[act] = tmp[idx];
 131           ++act;
 132         }
 133     }
 134   return act;
 135 }
 136 #endif
 137
 138
 139 /* Transform SRC into a form such that the result of strcmp
 140    on two strings that have been transformed by strxfrm is
 141    the same as the result of strcoll on the two strings before
 142    their transformation.  The transformed string is put in at
 143    most N characters of DEST and its length is returned.  */
 144 size_t
 145 STRXFRM (STRING_TYPE *dest, const STRING_TYPE *src, size_t n)
 146 {
 147   weight_t *forw = NULL;
 148   weight_t *backw = NULL;
 149   size_t pass;
 150   size_t written;
 151
 152   /* If the current locale does not specify locale data we use normal
 153      8-bit string comparison.  */
 154   if (collate_nrules == 0)
 155     {
 156       if (n != 0)
 157         STPNCPY (dest, src, n);
 158
 159       return STRLEN (src);
 160     }
 161
 162   /* Get full information about the string.  This means we get
 163      information for all passes in a special data structure.  */
 164   get_string (src, forw, backw);
 165
 166   /* Now we have all the information.  In at most the given number of
 167      passes we can finally decide about the order.  */
 168   written = 0;
 169   for (pass = 0; pass < collate_nrules; ++pass)
 170     {
 171       int forward = (collate_rules[pass] & sort_forward) != 0;
 172       const weight_t *run = forward ? forw : backw;
 173       int idx = forward ? 0 : run->data[pass].number - 1;
 174
 175       while (1)
 176         {
 177           int ignore = 0;
 178           u_int32_t w = 0;
 179
 180           /* Here we have to check for IGNORE entries.  If these are
 181              found we count them and go on with he next value.  */
 182           while (run != NULL
 183                  && ((w = run->data[pass].value[idx])
 184                      == (u_int32_t) IGNORE_CHAR))
 185             {
 186               ++ignore;
 187               if ((forward && ++idx >= run->data[pass].number)
 188                   || (!forward && --idx < 0))
 189                 {
 190                   weight_t *nextp = forward ? run->next : run->prev;
 191                   if (nextp == NULL)
 192                     {
 193                       w = 0;
 194                       /* No more non-INGOREd elements means lowest
 195                         possible value.  */
 196                       ignore = -1;
 197                     }
 198                   else
 199                     idx = forward ? 0 : nextp->data[pass].number - 1;
 200                   run = nextp;
 201                 }
 202             }
 203
 204           /* Stop if all characters are processed.  */
 205           if (run == NULL)
 206             break;
 207
 208           /* Now we have information of the number of ignored weights
 209              and the value of the next weight.  We have to add 2
 210              because 0 means EOS and 1 is the intermediate string end.  */
 211           if ((collate_rules[pass] & sort_position) != 0)
 212             written = print_val (ignore + 2, dest, n, written);
 213
 214           if (w != 0)
 215             written = print_val (w, dest, n, written);
 216
 217           /* We have to increment the index counters.  */
 218           if ((forward && ++idx >= run->data[pass].number)
 219               || (!forward && --idx < 0))
 220             if (forward)
 221               {
 222                 run = run->next;
 223                 idx = 0;
 224               }
 225             else
 226               {
 227                 run = run->prev;
 228                 if (run != NULL)
 229                   idx = run->data[pass].number - 1;
 230               }
 231         }
 232
 233       /* Write marker for end of word.  */
 234       if (pass + 1 < collate_nrules)
 235         written = print_val (1, dest, n, written);
 236     }
 237
 238   /* Terminate string.  */
 239   if (written < n)
 240     dest[written] = L_('\0');
 241
 242   /* Return length without counting the terminating '\0'.  */
 243   return written;
 244 }