Sat Mar 23 17:52:49 1996 Ulrich Drepper <drepper@gnu.ai.mit.edu>
[kopensolaris-gnu/glibc.git] / locale / programs / ld-collate.c
1 /* Copyright (C) 1995, 1996 Free Software Foundation, Inc.
2 This file is part of the GNU C Library.
3 Contributed by Ulrich Drepper, <drepper@gnu.ai.mit.edu>.
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
17 not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.  */
19
20 #ifdef HAVE_CONFIG_H
21 # include <config.h>
22 #endif
23
24 #include <endian.h>
25 #include <errno.h>
26 #include <limits.h>
27 #include <locale.h>
28 #include <obstack.h>
29 #include <stdlib.h>
30 #include <string.h>
31 #include <wcstr.h>
32
33 #include "localeinfo.h"
34 #include "locales.h"
35 #include "simple-hash.h"
36 #include "stringtrans.h"
37
38 /* Uncomment the following line in the production version.  */
39 /* define NDEBUG 1 */
40 #include <assert.h>
41
42
43 #define MAX(a, b) ((a) > (b) ? (a) : (b))
44
45 #define SWAPU32(w) \
46   (((w) << 24) | (((w) & 0xff00) << 8) | (((w) >> 8) & 0xff00) | ((w) >> 24))
47
48
49 /* What kind of symbols get defined?  */
50 enum coll_symbol
51 {
52   undefined,
53   ellipsis,
54   character,
55   element,
56   symbol
57 };
58
59
60 typedef struct patch_t
61 {
62   const char *fname;
63   size_t lineno;
64   const char *token;
65   union
66   {
67     unsigned int *pos;
68     size_t idx;
69   } where;
70   struct patch_t *next;
71 } patch_t;
72
73
74 typedef struct element_t
75 {
76   const wchar_t *name;
77   unsigned int this_weight;
78
79   struct element_t *next;
80
81   unsigned int *ordering;
82   size_t ordering_len;
83 } element_t;
84
85
86 /* The real definition of the struct for the LC_CTYPE locale.  */
87 struct locale_collate_t
88 {
89   /* Collate symbol table.  Simple mapping to number.  */
90   hash_table symbols;
91
92   /* The collation elements.  */
93   hash_table elements;
94   struct obstack element_mem;
95
96   /* The result table.  */
97   hash_table result;
98
99   /* Sorting rules given in order_start line.  */
100   int nrules;
101   int nrules_max;
102   enum coll_sort_rule *rules;
103
104   /* Used while recognizing symbol composed of multiple tokens
105      (collating-element).  */
106   const char *combine_token;
107   size_t combine_token_len;
108
109   /* How many sorting order specifications so far.  */
110   unsigned int order_cnt;
111
112   /* Was lastline ellipsis?  */
113   int was_ellipsis;
114   /* Value of last entry if was character.  */
115   wchar_t last_char;
116   /* Current element.  */
117   element_t *current_element;
118   /* What kind of symbol is current element.  */
119   enum coll_symbol kind;
120
121   /* While collecting the weigths we need some temporary space.  */
122   unsigned int current_order;
123   int *weight_cnt;
124   int weight_idx;
125   unsigned int *weight;
126   int nweight;
127   int nweight_max;
128
129   /* Patch lists.  */
130   patch_t *current_patch;
131   patch_t *all_patches;
132
133   /* Room for the UNDEFINED information.  */
134   element_t undefined;
135   unsigned int undefined_len;
136 };
137
138
139 /* Be verbose?  Defined in localedef.c.  */
140 extern int verbose;
141
142
143 void *xmalloc (size_t __n);
144 void *xrealloc (void *__p, size_t __n);
145
146
147 #define obstack_chunk_alloc xmalloc
148 #define obstack_chunk_free free
149
150
151 void
152 collate_startup (struct linereader *lr, struct localedef_t *locale,
153                  struct charset_t *charset)
154 {
155   struct locale_collate_t *collate;
156
157   /* It is important that we always use UCS4 encoding for strings now.  */
158   encoding_method = ENC_UCS4;
159
160   /* Allocate the needed room.  */
161   locale->categories[LC_COLLATE].collate = collate =
162     (struct locale_collate_t *) xmalloc (sizeof (struct locale_collate_t));
163
164   /* Allocate hash table for collating elements.  */
165   if (init_hash (&collate->elements, 512))
166     error (4, 0, _("memory exhausted"));
167   collate->combine_token = NULL;
168   obstack_init (&collate->element_mem);
169
170   /* Allocate hash table for collating elements.  */
171   if (init_hash (&collate->symbols, 64))
172     error (4, 0, _("memory exhausted"));
173
174   /* Allocate hash table for result.  */
175   if (init_hash (&collate->result, 512))
176     error (4, 0, _("memory exhausted"));
177
178   collate->nrules = 0;
179   collate->nrules_max = 10;
180   collate->rules
181     = (enum coll_sort_rule *) xmalloc (collate->nrules_max
182                                        * sizeof (enum coll_sort_rule));
183
184   collate->order_cnt = 1;       /* The smallest weight is 2.  */
185
186   collate->was_ellipsis = 0;
187   collate->last_char = L'\0';   /* 0 because leading ellipsis is allowed.  */
188
189   collate->all_patches = NULL;
190
191   /* This tells us no UNDEFINED entry was found until now.  */
192   collate->undefined.this_weight = 0;
193
194   lr->translate_strings = 0;
195 }
196
197
198 void
199 collate_finish (struct localedef_t *locale, struct charset_t *charset)
200 {
201   struct locale_collate_t *collate = locale->categories[LC_COLLATE].collate;
202   patch_t *patch;
203   size_t cnt;
204
205   /* Patch the constructed table so that forward references are
206      correctly filled.  */
207   for (patch = collate->all_patches; patch != NULL; patch = patch->next)
208     {
209       wchar_t wch;
210       size_t toklen = strlen (patch->token);
211       void *ptmp;
212       unsigned int value = 0;
213
214       wch = charset_find_value (charset, patch->token, toklen);
215       if (wch != ILLEGAL_CHAR_VALUE)
216         {
217           element_t *runp;
218
219           if (find_entry (&collate->result, &wch, sizeof (wchar_t),
220                           (void *) &runp) < 0)
221             runp = NULL;
222           for (; runp != NULL; runp = runp->next)
223             if (runp->name[0] == wch && runp->name[1] == L'\0')
224               break;
225
226           value = runp == NULL ? 0 : runp->this_weight;
227         }
228       else if (find_entry (&collate->elements, patch->token, toklen, &ptmp)
229                >= 0)
230         {
231           value = ((element_t *) ptmp)->this_weight;
232         }
233       else if (find_entry (&collate->symbols, patch->token, toklen, &ptmp)
234                >= 0)
235         {
236           value = (unsigned int) ptmp;
237         }
238       else
239         value = 0;
240
241       if (value == 0)
242         error_with_loc (0, 0, patch->fname, patch->lineno,
243                         _("no weight defined for symbol `%s'"), patch->token);
244       else
245         *patch->where.pos = value;
246     }
247
248   /* If no definition for UNDEFINED is given, all characters in the
249      given charset must be specified.  */
250   if (collate->undefined.ordering == NULL)
251     {
252       /**************************************************************\
253       |* XXX We should test whether really an unspecified character *|
254       |* exists before giving the message.                          *|
255       \**************************************************************/
256       u32_t weight;
257
258       error (0, 0, _("no definition of `UNDEFINED'"));
259
260       collate->undefined.ordering_len = collate->nrules;
261       weight = ++collate->order_cnt;
262
263       for (cnt = 0; cnt < collate->nrules; ++cnt)
264         {
265           u32_t one = 1;
266           obstack_grow (&collate->element_mem, &one, sizeof (one));
267         }
268
269       for (cnt = 0; cnt < collate->nrules; ++cnt)
270         obstack_grow (&collate->element_mem, &weight, sizeof (weight));
271
272       collate->undefined.ordering = obstack_finish (&collate->element_mem);
273     }
274
275   collate->undefined_len = 2;   /* For the name: 1 x wchar_t + L'\0'.  */
276   for (cnt = 0; cnt < collate->nrules; ++cnt)
277     collate->undefined_len += 1 + collate->undefined.ordering[cnt];
278
279   /* Collating symbols are not used anymore.  */
280   (void) delete_hash (&collate->symbols);
281 }
282
283
284
285 void
286 collate_output (struct localedef_t *locale, const char *output_path)
287 {
288   struct locale_collate_t *collate = locale->categories[LC_COLLATE].collate;
289   u32_t table_size, table_best, level_best, sum_best;
290   void *last;
291   element_t *pelem;
292   wchar_t *name;
293   size_t len;
294   const size_t nelems = _NL_ITEM_INDEX (_NL_NUM_LC_COLLATE);
295   struct iovec iov[2 + nelems];
296   struct locale_file data;
297   u32_t idx[nelems];
298   struct obstack non_simple;
299   size_t cnt, entry_size;
300   u32_t undefined_offset = UINT_MAX;
301   u32_t *table, *extra, *table2, *extra2;
302   size_t extra_len;
303
304   sum_best = UINT_MAX;
305   table_best = 0xffff;
306   level_best = 0xffff;
307
308   /* Compute table size.  */
309   fputs (_("\
310 Computing table size for collation information might take a while..."),
311          stderr);
312   for (table_size = 256; table_size < sum_best; ++table_size)
313     {
314       size_t hits[table_size];
315       unsigned int worst = 1;
316       size_t cnt;
317
318       last = NULL;
319
320       for (cnt = 0; cnt < 256; ++cnt)
321         hits[cnt] = 1;
322       memset (&hits[256], '\0', sizeof (hits) - 256 * sizeof (size_t));
323
324       while (iterate_table (&collate->result, &last, (const void **) &name,
325                             &len, (void **) &pelem) >= 0)
326         if (pelem->ordering != NULL && pelem->name[0] > 0xff)
327           if (++hits[(unsigned int) pelem->name[0] % table_size] > worst)
328             {
329               worst = hits[(unsigned int) pelem->name[0] % table_size];
330               if (table_size * worst > sum_best)
331                 break;
332             }
333
334       if (table_size * worst < sum_best)
335         {
336           sum_best = table_size * worst;
337           table_best = table_size;
338           level_best = worst;
339         }
340     }
341   assert (table_best != 0xffff || level_best != 0xffff);
342   fputs (_(" done\n"), stderr);
343
344   obstack_init (&non_simple);
345
346   data.magic = LIMAGIC (LC_COLLATE);
347   data.n = nelems;
348   iov[0].iov_base = (void *) &data;
349   iov[0].iov_len = sizeof (data);
350
351   iov[1].iov_base = (void *) idx;
352   iov[1].iov_len = sizeof (idx);
353
354   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_NRULES)].iov_base = &collate->nrules;
355   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_NRULES)].iov_len = sizeof (u32_t);
356
357   table = (u32_t *) alloca (collate->nrules * sizeof (u32_t));
358   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_RULES)].iov_base = table;
359   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_RULES)].iov_len
360     = collate->nrules * sizeof (u32_t);
361   /* Another trick here.  Describing the collation method needs only a
362      few bits (3, to be exact).  But the binary file should be
363      accessible by maschines with both endianesses and so we store both
364      information in the same word.  */
365   for (cnt = 0; cnt < collate->nrules; ++cnt)
366     table[cnt] = collate->rules[cnt] | SWAPU32 (collate->rules[cnt]);
367
368   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_HASH_SIZE)].iov_base = &table_best;
369   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_HASH_SIZE)].iov_len = sizeof (u32_t);
370
371   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_HASH_LAYERS)].iov_base = &level_best;
372   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_HASH_LAYERS)].iov_len = sizeof (u32_t);
373
374   entry_size = 1 + MAX (collate->nrules, 2);
375
376   table = (u32_t *) alloca (table_best * level_best * entry_size
377                             * sizeof (table[0]));
378   memset (table, '\0', table_best * level_best * entry_size
379           * sizeof (table[0]));
380
381
382   /* Macros for inserting in output table.  */
383 #define ADD_VALUE(expr)                                                       \
384   do {                                                                        \
385     u32_t to_write = (u32_t) expr;                                            \
386     obstack_grow (&non_simple, &to_write, sizeof (to_write));                 \
387   } while (0)
388
389 #define ADD_ELEMENT(pelem, len)                                               \
390   do {                                                                        \
391     size_t cnt, idx;                                                          \
392                                                                               \
393     ADD_VALUE (len);                                                          \
394                                                                               \
395     wlen = wcslen (pelem->name);                                              \
396     obstack_grow (&non_simple, pelem->name, (wlen + 1) * sizeof (u32_t));     \
397                                                                               \
398     idx = collate->nrules;                                                    \
399     for (cnt = 0; cnt < collate->nrules; ++cnt)                               \
400       {                                                                       \
401         size_t disp;                                                          \
402                                                                               \
403         ADD_VALUE (pelem->ordering[cnt]);                                     \
404         for (disp = 0; disp < pelem->ordering[cnt]; ++disp)                   \
405           ADD_VALUE (pelem->ordering[idx++]);                                 \
406       }                                                                       \
407   } while (0)
408
409 #define ADD_FORWARD(pelem)                                                    \
410   do {                                                                        \
411     /* We leave a reference in the main table and put all                     \
412        information in the table for the extended entries.  */                 \
413     element_t *runp;                                                          \
414     element_t *has_simple = NULL;                                             \
415     size_t wlen;                                                              \
416                                                                               \
417     table[(level * table_best + slot) * entry_size + 1]                       \
418       = FORWARD_CHAR;                                                         \
419     table[(level * table_best + slot) * entry_size + 2]                       \
420       = obstack_object_size (&non_simple) / sizeof (u32_t);                   \
421                                                                               \
422     /* Here we have to construct the non-simple table entry.  First           \
423        compute the total length of this entry.  */                            \
424     for (runp = (pelem); runp != NULL; runp = runp->next)                     \
425       if (runp->ordering != NULL)                                             \
426         {                                                                     \
427           u32_t value;                                                        \
428           size_t cnt;                                                         \
429                                                                               \
430           value = 1 + wcslen (runp->name) + 1;                                \
431                                                                               \
432           for (cnt = 0; cnt < collate->nrules; ++cnt)                         \
433             /* We have to take care for entries without ordering              \
434                information.  While reading them they get inserted in the      \
435                table and later not removed when something goes wrong with     \
436                reading its weights.  */                                       \
437             {                                                                 \
438               value += 1 + runp->ordering[cnt];                               \
439                                                                               \
440               if (runp->name[1] == L'\0')                                     \
441                 has_simple = runp;                                            \
442             }                                                                 \
443                                                                               \
444           ADD_ELEMENT (runp, value);                                          \
445         }                                                                     \
446                                                                               \
447     if (has_simple == NULL)                                                   \
448       {                                                                       \
449         size_t idx, cnt;                                                      \
450                                                                               \
451         ADD_VALUE (collate->undefined_len + 1);                               \
452                                                                               \
453         /* Add the name.  */                                                  \
454         ADD_VALUE ((pelem)->name[0]);                                         \
455         ADD_VALUE (0);                                                        \
456                                                                               \
457         idx = collate->nrules;                                                \
458         for (cnt = 0; cnt < collate->nrules; ++cnt)                           \
459           {                                                                   \
460             size_t disp;                                                      \
461                                                                               \
462             ADD_VALUE (collate->undefined.ordering[cnt]);                     \
463             for (disp = 0; disp < collate->undefined.ordering[cnt]; ++disp)   \
464               {                                                               \
465                 if (collate->undefined.ordering[idx] == ELLIPSIS_CHAR)        \
466                   ADD_VALUE ((pelem)->name[0]);                               \
467                 else                                                          \
468                   ADD_VALUE (collate->undefined.ordering[idx++]);             \
469                 ++idx;                                                        \
470               }                                                               \
471           }                                                                   \
472       }                                                                       \
473   } while (0)
474
475
476
477   /* Fill the table now.  First we look for all the characters which
478      fit into one single byte.  This speeds up the 8-bit string
479      functions.  */
480   last = NULL;
481   while (iterate_table (&collate->result, &last, (const void **) &name,
482                         &len, (void **) &pelem) >= 0)
483     if (pelem->name[0] <= 0xff)
484       {
485         /* We have a single byte name.  Now we must distinguish
486            between entries in simple form (i.e., only one value per
487            weight and no collation element starting with the same
488            character) and those which are not.  */
489         size_t slot = ((size_t) pelem->name[0]);
490         const size_t level = 0;
491
492         table[slot * entry_size] = pelem->name[0];
493
494         if (pelem->name[1] == L'\0' && pelem->next == NULL
495             && pelem->ordering_len == collate->nrules)
496           {
497             /* Yes, we have a simple one.  Lucky us.  */
498             size_t cnt;
499
500             for (cnt = 0; cnt < collate->nrules; ++cnt)
501               table[slot * entry_size + 1 + cnt]
502                 = pelem->ordering[collate->nrules + cnt];
503           }
504         else
505           ADD_FORWARD (pelem);
506       }
507
508   /* Now check for missing single byte entries.  If one exist we fill
509      with the UNDEFINED entry.  */
510   for (cnt = 0; cnt < 256; ++cnt)
511     /* The first weight is never 0 for existing entries.  */
512     if (table[cnt * entry_size + 1] == 0)
513       {
514         /* We have to fill in the information from the UNDEFINED
515            entry.  */
516         table[cnt * entry_size] = (u32_t) cnt;
517
518         if (collate->undefined.ordering_len == collate->nrules)
519           {
520             size_t inner;
521
522             for (inner = 0; inner < collate->nrules; ++inner)
523               if (collate->undefined.ordering[collate->nrules + inner]
524                   == ELLIPSIS_CHAR)
525                 table[cnt * entry_size + 1 + inner] = cnt;
526               else
527                 table[cnt * entry_size + 1 + inner]
528                   = collate->undefined.ordering[collate->nrules + inner];
529           }
530         else
531           {
532             if (undefined_offset != UINT_MAX)
533               {
534                 table[cnt * entry_size + 1] = FORWARD_CHAR;
535                 table[cnt * entry_size + 2] = undefined_offset;
536               }
537             else
538               {
539                 const size_t slot = cnt;
540                 const size_t level = 0;
541
542                 ADD_FORWARD (&collate->undefined);
543                 undefined_offset = table[cnt * entry_size + 2];
544               }
545           }
546       }
547
548   /* Now we are ready for inserting the whole rest.   */
549   last = NULL;
550   while (iterate_table (&collate->result, &last, (const void **) &name,
551                         &len, (void **) &pelem) >= 0)
552     if (pelem->name[0] > 0xff)
553       {
554         /* Find the position.  */
555         size_t slot = ((size_t) pelem->name[0]) % table_best;
556         size_t level = 0;
557
558         while (table[(level * table_best + slot) * entry_size + 1] != 0)
559           ++level;
560         assert (level < level_best);
561
562         if (pelem->name[1] == L'\0' && pelem->next == NULL
563             && pelem->ordering_len == collate->nrules)
564           {
565             /* Again a simple entry.  */
566             size_t inner;
567
568             for (inner = 0; inner < collate->nrules; ++inner)
569               table[(level * table_best + slot) * entry_size + 1 + inner]
570                 = pelem->ordering[collate->nrules + inner];
571           }
572         else
573           ADD_FORWARD (pelem);
574       }
575
576   /* Add the UNDEFINED entry.  */
577   {
578     /* Here we have to construct the non-simple table entry.  */
579     size_t idx, cnt;
580
581     undefined_offset = obstack_object_size (&non_simple);
582
583     idx = collate->nrules;
584     for (cnt = 0; cnt < collate->nrules; ++cnt)
585       {
586         size_t disp;
587
588         ADD_VALUE (collate->undefined.ordering[cnt]);
589         for (disp = 0; disp < collate->undefined.ordering[cnt]; ++disp)
590           ADD_VALUE (collate->undefined.ordering[idx++]);
591       }
592   }
593
594   /* Finish the extra block.  */
595   extra_len = obstack_object_size (&non_simple);
596   extra = (u32_t *) obstack_finish (&non_simple);
597   assert ((extra_len % sizeof (u32_t)) == 0);
598
599   /* Now we have to build the two array for the other byte ordering.  */
600   table2 = (u32_t *) alloca (table_best * level_best * entry_size
601                              * sizeof (table[0]));
602   extra2 = (u32_t *) alloca (extra_len);
603
604   for (cnt = 0; cnt < table_best * level_best * entry_size; ++cnt)
605     table2[cnt] = SWAPU32 (table[cnt]);
606
607   for (cnt = 0; cnt < extra_len / sizeof (u32_t); ++cnt)
608     extra2[cnt] = SWAPU32 (extra2[cnt]);
609
610   /* Store table adresses and lengths.   */
611 #if __BYTE_ORDER == __BIG_ENDIAN
612   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_TABLE_EB)].iov_base = table;
613   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_TABLE_EB)].iov_len
614     = table_best * level_best * entry_size * sizeof (table[0]);
615
616   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_TABLE_EL)].iov_base = table2;
617   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_TABLE_EL)].iov_len
618     = table_best * level_best * entry_size * sizeof (table[0]);
619
620   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_EXTRA_EB)].iov_base = extra;
621   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_EXTRA_EB)].iov_len = extra_len;
622
623   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_EXTRA_EL)].iov_base = extra2;
624   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_EXTRA_EL)].iov_len = extra_len;
625 #else
626   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_TABLE_EB)].iov_base = table2;
627   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_TABLE_EB)].iov_len
628     = table_best * level_best * entry_size * sizeof (table[0]);
629
630   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_TABLE_EL)].iov_base = table;
631   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_TABLE_EL)].iov_len
632     = table_best * level_best * entry_size * sizeof (table[0]);
633
634   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_EXTRA_EB)].iov_base = extra2;
635   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_EXTRA_EB)].iov_len = extra_len;
636
637   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_EXTRA_EL)].iov_base = extra;
638   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_EXTRA_EL)].iov_len = extra_len;
639 #endif
640
641   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_UNDEFINED)].iov_base = &undefined_offset;
642   iov[2 + _NL_ITEM_INDEX (_NL_COLLATE_UNDEFINED)].iov_len = sizeof (u32_t);
643
644   /* Update idx array.  */
645   idx[0] = iov[0].iov_len + iov[1].iov_len;
646   for (cnt = 1; cnt < nelems; ++cnt)
647     idx[cnt] = idx[cnt - 1] + iov[1 + cnt].iov_len;
648
649   write_locale_data (output_path, "LC_COLLATE", 2 + nelems, iov);
650 }
651
652
653 void
654 collate_element_to (struct linereader *lr, struct localedef_t *locale,
655                     struct token *code, struct charset_t *charset)
656 {
657   struct locale_collate_t *collate = locale->categories[LC_COLLATE].collate;
658   unsigned int value;
659   void *not_used;
660
661   if (collate->combine_token != NULL)
662     {
663       free ((void *) collate->combine_token);
664       collate->combine_token = NULL;
665     }
666
667   value = charset_find_value (charset, code->val.str.start, code->val.str.len);
668   if (value != ILLEGAL_CHAR_VALUE)
669     {
670       lr_error (lr, _("symbol for multicharacter collating element "
671                       "`%.*s' duplicates symbolic name in charset"),
672                 code->val.str.len, code->val.str.start);
673       return;
674     }
675
676   if (find_entry (&collate->elements, code->val.str.start, code->val.str.len,
677                   &not_used) >= 0)
678     {
679       lr_error (lr, _("symbol for multicharacter collating element "
680                       "`%.*s' duplicates other element definition"),
681                 code->val.str.len, code->val.str.start);
682       return;
683     }
684
685   if (find_entry (&collate->elements, code->val.str.start, code->val.str.len,
686                   &not_used) >= 0)
687     {
688       lr_error (lr, _("symbol for multicharacter collating element "
689                       "`%.*s' duplicates symbol definition"),
690                 code->val.str.len, code->val.str.start);
691       return;
692     }
693
694   collate->combine_token = code->val.str.start;
695   collate->combine_token_len = code->val.str.len;
696 }
697
698
699 void
700 collate_element_from (struct linereader *lr, struct localedef_t *locale,
701                       struct token *code, struct charset_t *charset)
702 {
703   struct locale_collate_t *collate = locale->categories[LC_COLLATE].collate;
704   element_t *elemp, *runp;
705
706   /* CODE is a string.  */
707   elemp = (element_t *) obstack_alloc (&collate->element_mem,
708                                        sizeof (element_t));
709
710   /* We have to translate the string.  It may contain <...> character
711      names.  */
712   elemp->name = (wchar_t *) translate_string (code->val.str.start, charset);
713   elemp->this_weight = 0;
714   elemp->ordering = NULL;
715   elemp->ordering_len = 0;
716
717   free (code->val.str.start);
718
719   if (elemp->name == NULL)
720     {
721       /* At least one character in the string is not defined.  We simply
722          do nothing.  */
723       if (verbose)
724         lr_error (lr, _("\
725 `from' string in collation element declaration contains unknown character"));
726       return;
727     }
728
729   if (elemp->name[0] == L'\0' || elemp->name[1] == L'\0')
730     {
731       lr_error (lr, _("illegal colltion element"));
732       return;
733     }
734
735   /* The entries in the linked lists of RESULT are sorting in
736      descending order.  The order is important for the `strcoll' and
737      `wcscoll' functions.  */
738   if (find_entry (&collate->result, elemp->name, sizeof (wchar_t),
739                   (void *) &runp) >= 0)
740     {
741       /* We already have an entry with this key.  Check whether it is
742          identical.  */
743       element_t *prevp = NULL;
744       int cmpres;
745
746       do
747         {
748           cmpres = wcscmp (elemp->name, runp->name);
749           if (cmpres <= 0)
750             break;
751           prevp = runp;
752         }
753       while ((runp = runp->next) != NULL);
754
755       if (cmpres == 0)
756         lr_error (lr, _("duplicate collating element definition"));
757       else
758         {
759           elemp->next = runp;
760           if (prevp == NULL)
761             {
762               if (set_entry (&collate->result, elemp->name, sizeof (wchar_t),
763                              elemp) < 0)
764                 error (EXIT_FAILURE, 0,
765                        _("\
766 error while inserting collation element into hash table"));
767             }
768           else
769             prevp->next = elemp;
770         }
771     }
772   else
773     {
774       elemp->next = NULL;
775       if (insert_entry (&collate->result, elemp->name, sizeof (wchar_t), elemp)
776           < 0)
777         error (EXIT_FAILURE, errno, _("error while inserting to hash table"));
778     }
779
780   if (insert_entry (&collate->elements, collate->combine_token,
781                     collate->combine_token_len, (void *) elemp) < 0)
782     lr_error (lr, _("cannot insert new collating symbol definition: %s"),
783               strerror (errno));
784 }
785
786
787 void
788 collate_symbol (struct linereader *lr, struct localedef_t *locale,
789                 struct token *code, struct charset_t *charset)
790 {
791   struct locale_collate_t *collate = locale->categories[LC_COLLATE].collate;
792   wchar_t value;
793   void *not_used;
794
795   value = charset_find_value (charset, code->val.str.start, code->val.str.len);
796   if (value != ILLEGAL_CHAR_VALUE)
797     {
798       lr_error (lr, _("symbol for multicharacter collating element "
799                       "`%.*s' duplicates symbolic name in charset"),
800                 code->val.str.len, code->val.str.start);
801       return;
802     }
803
804   if (find_entry (&collate->elements, code->val.str.start, code->val.str.len,
805                   &not_used) >= 0)
806     {
807       lr_error (lr, _("symbol for multicharacter collating element "
808                       "`%.*s' duplicates element definition"),
809                 code->val.str.len, code->val.str.start);
810       return;
811     }
812
813   if (find_entry (&collate->symbols, code->val.str.start, code->val.str.len,
814                   &not_used) >= 0)
815     {
816       lr_error (lr, _("symbol for multicharacter collating element "
817                       "`%.*s' duplicates other symbol definition"),
818                 code->val.str.len, code->val.str.start);
819       return;
820     }
821
822   if (insert_entry (&collate->symbols, code->val.str.start, code->val.str.len,
823                     (void *) 0) < 0)
824     lr_error (lr, _("cannot insert new collating symbol definition: %s"),
825               strerror (errno));
826 }
827
828
829 void
830 collate_new_order (struct linereader *lr, struct localedef_t *locale,
831                    enum coll_sort_rule sort_rule)
832 {
833   struct locale_collate_t *collate = locale->categories[LC_COLLATE].collate;
834
835   if (collate->nrules >= collate->nrules_max)
836     {
837       collate->nrules_max *= 2;
838       collate->rules
839         = (enum coll_sort_rule *) xrealloc (collate->rules,
840                                             collate->nrules_max
841                                             * sizeof (enum coll_sort_rule));
842     }
843
844   collate->rules[collate->nrules++] = sort_rule;
845 }
846
847
848 void
849 collate_build_arrays (struct linereader *lr, struct localedef_t *locale)
850 {
851   struct locale_collate_t *collate = locale->categories[LC_COLLATE].collate;
852
853   collate->rules
854     = (enum coll_sort_rule *) xrealloc (collate->rules,
855                                         collate->nrules
856                                         * sizeof (enum coll_sort_rule));
857
858   /* Allocate arrays for temporary weights.  */
859   collate->weight_cnt = (int *) xmalloc (collate->nrules * sizeof (int));
860
861   /* Choose arbitrary start value for table size.  */
862   collate->nweight_max = 5 * collate->nrules;
863   collate->weight = (int *) xmalloc (collate->nweight_max * sizeof (int));
864 }
865
866
867 int
868 collate_order_elem (struct linereader *lr, struct localedef_t *locale,
869                     struct token *code, struct charset_t *charset)
870 {
871   const wchar_t zero = L'\0';
872   struct locale_collate_t *collate = locale->categories[LC_COLLATE].collate;
873   int result = 0;
874   wchar_t value;
875   void *tmp;
876   int i;
877
878   switch (code->tok)
879     {
880     case tok_bsymbol:
881       /* We have a string to find in one of the three hashing tables.  */
882       value = charset_find_value (charset, code->val.str.start,
883                                   code->val.str.len);
884       if (value != ILLEGAL_CHAR_VALUE)
885         {
886           element_t *lastp, *firstp;
887
888           collate->kind = character;
889
890           if (find_entry (&collate->result, &value, sizeof (wchar_t),
891                           (void *) &firstp) < 0)
892             firstp = lastp = NULL;
893           else
894             {
895               /* The entry for the simple character is always found at
896                  the end.  */
897               lastp = firstp;
898               while (lastp->next != NULL)
899                 lastp = lastp->next;
900
901               if (lastp->name[0] == value && lastp->name[1] == L'\0')
902                 {
903                   lr_error (lr, _("duplicate definition for character `%.*s'"),
904                             code->val.str.len, code->val.str.start);
905                   lr_ignore_rest (lr, 0);
906                   result = -1;
907                   break;
908                 }
909             }
910
911           collate->current_element
912             = (element_t *) obstack_alloc (&collate->element_mem,
913                                            sizeof (element_t));
914
915           obstack_grow (&collate->element_mem, &value, sizeof (value));
916           obstack_grow (&collate->element_mem, &zero, sizeof (zero));
917
918           collate->current_element->name =
919             (const wchar_t *) obstack_finish (&collate->element_mem);
920
921           collate->current_element->this_weight = ++collate->order_cnt;
922
923           collate->current_element->next = NULL;
924
925           if (firstp == NULL)
926             {
927               if (insert_entry (&collate->result, &value, sizeof (wchar_t),
928                                 (void *) collate->current_element) < 0)
929                 {
930                   lr_error (lr, _("cannot insert collation element `%.*s'"),
931                             code->val.str.len, code->val.str.start);
932                   exit (4);
933                 }
934             }
935           else
936             lastp->next = collate->current_element;
937         }
938       else if (find_entry (&collate->elements, code->val.str.start,
939                            code->val.str.len, &tmp) >= 0)
940         {
941           collate->current_element = (element_t *) tmp;
942
943           if (collate->current_element->this_weight != 0)
944             {
945               lr_error (lr, _("\
946 collation element `%.*s' appears more than once: ignore line"),
947                         code->val.str.len, code->val.str.start);
948               lr_ignore_rest (lr, 0);
949               result = -1;
950               break;
951             }
952
953           collate->kind = element;
954           collate->current_element->this_weight = ++collate->order_cnt;
955         }
956       else if (find_entry (&collate->symbols, code->val.str.start,
957                            code->val.str.len, &tmp) >= 0)
958         {
959           unsigned int order = ++collate->order_cnt;
960
961           if ((unsigned int) tmp != 0)
962             {
963               lr_error (lr, _("\
964 collation symbol `.*s' appears more than once: ignore line"),
965                         code->val.str.len, code->val.str.start);
966               lr_ignore_rest (lr, 0);
967               result = -1;
968               break;
969             }
970
971           collate->kind = symbol;
972
973           if (set_entry (&collate->symbols, code->val.str.start,
974                          code->val.str.len, (void *) order) < 0)
975             {
976               lr_error (lr, _("cannot process order specification"));
977               exit (4);
978             }
979         }
980       else
981         {
982           if (verbose)
983             lr_error (lr, _("unknown symbol `%.*s': line ignored"),
984                       code->val.str.len, code->val.str.start);
985           lr_ignore_rest (lr, 0);
986
987           result = -1;
988         }
989       break;
990
991     case tok_undefined:
992       collate->kind = undefined;
993       collate->current_element = &collate->undefined;
994       break;
995
996     case tok_ellipsis:
997       if (collate->was_ellipsis)
998         {
999           lr_error (lr, _("\
1000 two lines in a row containing `...' are not allowed"));
1001           result = -1;
1002         }
1003       else if (collate->kind != character)
1004         {
1005           /* An ellipsis requires the previous line to be an
1006              character definition.  */
1007           lr_error (lr, _("\
1008 line before ellipsis does not contain definition for character constant"));
1009           lr_ignore_rest (lr, 0);
1010           result = -1;
1011         }
1012       else
1013         collate->kind = ellipsis;
1014       break;
1015
1016     default:
1017       assert (! "illegal token in `collate_order_elem'");
1018     }
1019
1020   /* Now it's time to handle the ellipsis in the previous line.  We do
1021      this only when the last line contained an definition for an
1022      character, the current line also defines an character, the
1023      character code for the later is bigger than the former.  */
1024   if (collate->was_ellipsis)
1025     {
1026       if (collate->kind != character)
1027         {
1028           lr_error (lr, _("\
1029 line after ellipsis must contain character definition"));
1030           lr_ignore_rest (lr, 0);
1031           result = -1;
1032         }
1033       else if (collate->last_char > value)
1034         {
1035           lr_error (lr, _("end point of ellipsis range is bigger then start"));
1036           lr_ignore_rest (lr, 0);
1037           result = -1;
1038         }
1039       else
1040         {
1041           /* We can fill the arrays with the information we need.  */
1042           wchar_t name[2];
1043           unsigned int *data;
1044           size_t *ptr;
1045           size_t cnt;
1046
1047           name[0] = collate->last_char + 1;
1048           name[1] = L'\0';
1049
1050           data = (unsigned int *) alloca ((collate->nrules + collate->nweight)
1051                                           * sizeof (unsigned int));
1052           ptr = (size_t *) alloca (collate->nrules * sizeof (size_t));
1053
1054           if (data == NULL || ptr == NULL)
1055             error (4, 0, _("memory exhausted"));
1056
1057           /* Prepare data.  Because the characters covered by an
1058              ellipsis all have equal values we prepare the data once
1059              and only change the variable number (if there are any).
1060              PTR[...] will point to the entries which will have to be
1061              fixed during the output loop.  */
1062           for (cnt = 0; cnt < collate->nrules; ++cnt)
1063             {
1064               data[cnt] = collate->weight_cnt[cnt];
1065               ptr[cnt] = (cnt == 0
1066                           ? collate->nweight
1067                           : ptr[cnt - 1] + collate->weight_cnt[cnt - 1]);
1068             }
1069
1070           for (cnt = 0; cnt < collate->nweight; ++cnt)
1071             data[collate->nrules + cnt] = collate->weight[cnt];
1072
1073           for (cnt = 0; cnt < collate->nrules; ++cnt)
1074             if (data[ptr[cnt]] != ELLIPSIS_CHAR)
1075               ptr[cnt] = 0;
1076
1077           while (name[0] <= value)
1078             {
1079               element_t *pelem;
1080
1081               pelem = (element_t *) obstack_alloc (&collate->element_mem,
1082                                                    sizeof (element_t));
1083               if (pelem == NULL)
1084                 error (4, 0, _("memory exhausted"));
1085
1086               pelem->name
1087                 = (const wchar_t *) obstack_copy (&collate->element_mem,
1088                                                   name, 2 * sizeof (wchar_t));
1089               pelem->this_weight = ++collate->order_cnt;
1090
1091               pelem->ordering_len = collate->nweight;
1092               pelem->ordering
1093                 = (unsigned int *) obstack_copy (&collate->element_mem, data,
1094                                                  (collate->nrules
1095                                                   * pelem->ordering_len)
1096                                                  * sizeof (unsigned int));
1097
1098               /* `...' weights need to be adjusted.  */
1099               for (cnt = 0; cnt < collate->nrules; ++cnt)
1100                 if (ptr[cnt] != 0)
1101                   pelem->ordering[ptr[cnt]] = pelem->this_weight;
1102
1103               /* Insert new entry into result table.  */
1104               if (find_entry (&collate->result, name, sizeof (wchar_t),
1105                               (void *) &pelem->next) >= 0)
1106                 {
1107                   if (set_entry (&collate->result, name, sizeof (wchar_t),
1108                                  (void *) pelem->next) < 0)
1109                     error (4, 0, _("cannot insert into result table"));
1110                 }
1111               else
1112                 if (insert_entry (&collate->result, name, sizeof (wchar_t),
1113                                   (void *) pelem->next) < 0)
1114                   error (4, 0, _("cannot insert into result table"));
1115
1116               /* Increment counter.  */
1117               ++name[0];
1118             }
1119         }
1120     }
1121
1122   /* Reset counters for weights.  */
1123   collate->weight_idx = 0;
1124   collate->nweight = 0;
1125   for (i = 0; i < collate->nrules; ++i)
1126     collate->weight_cnt[i] = 0;
1127   collate->current_patch = NULL;
1128
1129   return result;
1130 }
1131
1132
1133 int
1134 collate_weight_bsymbol (struct linereader *lr, struct localedef_t *locale,
1135                         struct token *code, struct charset_t *charset)
1136 {
1137   struct locale_collate_t *collate = locale->categories[LC_COLLATE].collate;
1138   unsigned int here_weight;
1139   wchar_t value;
1140   void *tmp;
1141
1142   assert (code->tok == tok_bsymbol);
1143
1144   value = charset_find_value (charset, code->val.str.start, code->val.str.len);
1145   if (value != ILLEGAL_CHAR_VALUE)
1146     {
1147       element_t *runp;
1148
1149       if (find_entry (&collate->result, &value, sizeof (wchar_t),
1150                       (void *)&runp) < 0)
1151         runp = NULL;
1152
1153       while (runp != NULL
1154              && (runp->name[0] != value || runp->name[1] != L'\0'))
1155         runp = runp->next;
1156
1157       here_weight = runp == NULL ? 0 : runp->this_weight;
1158     }
1159   else if (find_entry (&collate->elements, code->val.str.start,
1160                        code->val.str.len, &tmp) >= 0)
1161     {
1162       element_t *runp = (element_t *) tmp;
1163
1164       here_weight = runp->this_weight;
1165     }
1166   else if (find_entry (&collate->symbols, code->val.str.start,
1167                        code->val.str.len, &tmp) >= 0)
1168     {
1169       here_weight = (unsigned int) tmp;
1170     }
1171   else
1172     {
1173       if (verbose)
1174         lr_error (lr, _("unknown symbol `%.*s': line ignored"),
1175                   code->val.str.len, code->val.str.start);
1176       lr_ignore_rest (lr, 0);
1177       return -1;
1178     }
1179
1180   /* When we currently work on a collation symbol we do not expect any
1181      weight.  */
1182   if (collate->kind == symbol)
1183     {
1184       lr_error (lr, _("\
1185 specification of sorting weight for collation symbol does not make sense"));
1186       lr_ignore_rest (lr, 0);
1187       return -1;
1188     }
1189
1190   /* Add to the current collection of weights.  */
1191   if (collate->nweight >= collate->nweight_max)
1192     {
1193       collate->nweight_max *= 2;
1194       collate->weight = (unsigned int *) xrealloc (collate->weight,
1195                                                    collate->nweight_max);
1196     }
1197
1198   /* If the weight is currently not known, we remember to patch the
1199      resulting tables.  */
1200   if (here_weight == 0)
1201     {
1202       patch_t *newp;
1203
1204       newp = (patch_t *) obstack_alloc (&collate->element_mem,
1205                                         sizeof (patch_t));
1206       newp->fname = lr->fname;
1207       newp->lineno = lr->lineno;
1208       newp->token = (const char *) obstack_copy0 (&collate->element_mem,
1209                                                   code->val.str.start,
1210                                                   code->val.str.len);
1211       newp->where.idx = collate->nweight++;
1212       newp->next = collate->current_patch;
1213       collate->current_patch = newp;
1214     }
1215   else
1216     collate->weight[collate->nweight++] = here_weight;
1217   ++collate->weight_cnt[collate->weight_idx];
1218
1219   return 0;
1220 }
1221
1222
1223 int
1224 collate_next_weight (struct linereader *lr, struct localedef_t *locale)
1225 {
1226   struct locale_collate_t *collate = locale->categories[LC_COLLATE].collate;
1227
1228   if (collate->kind == symbol)
1229     {
1230       lr_error (lr, _("\
1231 specification of sorting weight for collation symbol does not make sense"));
1232       lr_ignore_rest (lr, 0);
1233       return -1;
1234     }
1235
1236   ++collate->weight_idx;
1237   if (collate->weight_idx >= collate->nrules)
1238     {
1239       lr_error (lr, _("too many weights"));
1240       lr_ignore_rest (lr, 0);
1241       return -1;
1242     }
1243
1244   return 0;
1245 }
1246
1247
1248 int
1249 collate_simple_weight (struct linereader *lr, struct localedef_t *locale,
1250                        struct token *code, struct charset_t *charset)
1251 {
1252   struct locale_collate_t *collate = locale->categories[LC_COLLATE].collate;
1253   unsigned int value = 0;
1254
1255   /* There current tokens can be `IGNORE', `...', or a string.  */
1256   switch (code->tok)
1257     {
1258     case tok_ignore:
1259       /* This token is allowed in all situations.  */
1260       value = IGNORE_CHAR;
1261       break;
1262
1263     case tok_ellipsis:
1264       /* The ellipsis is only allowed for the `...' or `UNDEFINED'
1265          entry.  */
1266       if (collate->kind != ellipsis && collate->kind != undefined)
1267         {
1268           lr_error (lr, _("\
1269 `...' must only be used in `...' and `UNDEFINED' entries"));
1270           lr_ignore_rest (lr, 0);
1271           return -1;
1272         }
1273       value = ELLIPSIS_CHAR;
1274       break;
1275
1276     case tok_string:
1277       /* This can become difficult.  We have to get the weights which
1278          correspind the the single wide chars in the string.  But some
1279          of the `chars' might not be real characters, but collation
1280          elements or symbols.  And so the string decoder might have
1281          signaled errors.  The string at this point is not translated.
1282          I.e., all <...> sequences are still there.  */
1283       {
1284         char *runp = code->val.str.start;
1285         void *tmp;
1286
1287         while (*runp != '\0')
1288           {
1289             char *startp = (char *) runp;
1290             char *putp = (char *) runp;
1291             wchar_t wch;
1292
1293             /* Lookup weight for char and store it.  */
1294             if (*runp == '<')
1295               {
1296                 while (*++runp != '\0' && *runp != '>')
1297                   {
1298                     if (*runp == lr->escape_char)
1299                       if (*++runp == '\0')
1300                         {
1301                           lr_error (lr, _("unterminated weight name"));
1302                           lr_ignore_rest (lr, 0);
1303                           return -1;
1304                         }
1305                     *putp++ = *runp;
1306                   }
1307                 if (*runp == '>')
1308                   ++runp;
1309
1310                 if (putp == startp)
1311                   {
1312                     lr_error (lr, _("empty weight name: line ignored"));
1313                     lr_ignore_rest (lr, 0);
1314                     return -1;
1315                   }
1316
1317                 wch = charset_find_value (charset, startp, putp - startp);
1318                 if (wch != ILLEGAL_CHAR_VALUE)
1319                   {
1320                     element_t *pelem;
1321
1322                     if (find_entry (&collate->result, &wch, sizeof (wchar_t),
1323                                     (void *)&pelem) < 0)
1324                       pelem = NULL;
1325
1326                     while (pelem != NULL
1327                            && (pelem->name[0] != wch
1328                                || pelem->name[1] != L'\0'))
1329                       pelem = pelem->next;
1330
1331                     value = pelem == NULL ? 0 : pelem->this_weight;
1332                   }
1333                 else if (find_entry (&collate->elements, startp, putp - startp,
1334                                      &tmp) >= 0)
1335                   {
1336                     element_t *pelem = (element_t *) tmp;
1337
1338                     value = pelem->this_weight;
1339                   }
1340                 else if (find_entry (&collate->symbols, startp, putp - startp,
1341                                      &tmp) >= 0)
1342                   {
1343                     value = (unsigned int) tmp;
1344                   }
1345                 else
1346                   {
1347                     if (verbose)
1348                       lr_error (lr, _("unknown symbol `%.*s': line ignored"),
1349                                 putp - startp, startp);
1350                     lr_ignore_rest (lr, 0);
1351                     return -1;
1352                   }
1353               }
1354             else
1355               {
1356                 element_t *wp;
1357                 wchar_t wch;
1358
1359                 if (*runp == lr->escape_char)
1360                   {
1361                     static char digits[] = "0123456789abcdef";
1362                     char *dp;
1363                     int base;
1364
1365                     ++runp;
1366                     if (tolower (*runp) == 'x')
1367                       {
1368                         ++runp;
1369                         base = 16;
1370                       }
1371                     else if (tolower (*runp) == 'd')
1372                       {
1373                         ++runp;
1374                         base = 10;
1375                       }
1376                     else
1377                       base = 8;
1378
1379                     dp = strchr (digits, tolower (*runp));
1380                     if (dp == NULL || (dp - digits) >= base)
1381                       {
1382                       illegal_char:
1383                         lr_error (lr, _("\
1384 illegal character constant in string"));
1385                         lr_ignore_rest (lr, 0);
1386                         return -1;
1387                       }
1388                     wch = dp - digits;
1389                     ++runp;
1390
1391                     dp = strchr (digits, tolower (*runp));
1392                     if (dp == NULL || (dp - digits) >= base)
1393                       goto illegal_char;
1394                     wch *= base;
1395                     wch += dp - digits;
1396                     ++runp;
1397
1398                     if (base != 16)
1399                       {
1400                         dp = strchr (digits, tolower (*runp));
1401                         if (dp != NULL && (dp - digits < base))
1402                           {
1403                             wch *= base;
1404                             wch += dp - digits;
1405                             ++runp;
1406                           }
1407                       }
1408                   }
1409                 else
1410                   wch = (wchar_t) *runp++;
1411
1412                 /* Lookup the weight for WCH.  */
1413                 if (find_entry (&collate->result, &wch, sizeof (wch),
1414                                 (void *)&wp) < 0)
1415                   wp = NULL;
1416
1417                 while (wp != NULL
1418                        && (wp->name[0] != wch || wp->name[1] != L'\0'))
1419                   wp = wp->next;
1420
1421                 value = wp == NULL ? 0 : wp->this_weight;
1422
1423                 /* To get the correct name for the error message.  */
1424                 putp = runp;
1425
1426                 /**************************************************\
1427                 |* I know here is something wrong.  Characters in *|
1428                 |* the string which are not in the <...> form     *|
1429                 |* cannot be declared forward for now!!!          *|
1430                 \**************************************************/
1431               }
1432
1433             /* Store in weight array.  */
1434             if (collate->nweight >= collate->nweight_max)
1435               {
1436                 collate->nweight_max *= 2;
1437                 collate->weight
1438                   = (unsigned int *) xrealloc (collate->weight,
1439                                                collate->nweight_max);
1440               }
1441
1442             if (value == 0)
1443               {
1444                 patch_t *newp;
1445
1446                 newp = (patch_t *) obstack_alloc (&collate->element_mem,
1447                                                   sizeof (patch_t));
1448                 newp->fname = lr->fname;
1449                 newp->lineno = lr->lineno;
1450                 newp->token
1451                   = (const char *) obstack_copy0 (&collate->element_mem,
1452                                                   startp, putp - startp);
1453                 newp->where.idx = collate->nweight++;
1454                 newp->next = collate->current_patch;
1455                 collate->current_patch = newp;
1456               }
1457             else
1458               collate->weight[collate->nweight++] = value;
1459             ++collate->weight_cnt[collate->weight_idx];
1460           }
1461       }
1462       return 0;
1463
1464     default:
1465       assert (! "should not happen");
1466     }
1467
1468
1469   if (collate->nweight >= collate->nweight_max)
1470     {
1471       collate->nweight_max *= 2;
1472       collate->weight = (unsigned int *) xrealloc (collate->weight,
1473                                                    collate->nweight_max);
1474     }
1475
1476   collate->weight[collate->nweight++] = value;
1477   ++collate->weight_cnt[collate->weight_idx];
1478
1479   return 0;
1480 }
1481
1482
1483 void
1484 collate_end_weight (struct linereader *lr, struct localedef_t *locale)
1485 {
1486   struct locale_collate_t *collate = locale->categories[LC_COLLATE].collate;
1487   element_t *pelem = collate->current_element;
1488
1489   if (collate->kind == symbol)
1490     {
1491       /* We don't have to do anything.  */
1492       collate->was_ellipsis = 0;
1493       return;
1494     }
1495
1496   if (collate->kind == ellipsis)
1497     {
1498       /* Before the next line is processed the ellipsis is handled.  */
1499       collate->was_ellipsis = 1;
1500       return;
1501     }
1502
1503   assert (collate->kind == character || collate->kind == element
1504           || collate->kind == undefined);
1505
1506   /* Fill in the missing weights.  */
1507   while (++collate->weight_idx < collate->nrules)
1508     {
1509       collate->weight[collate->nweight++] = pelem->this_weight;
1510       ++collate->weight_cnt[collate->weight_idx];
1511     }
1512
1513   /* Now we know how many ordering weights the current
1514      character/element has.  Allocate room in the element structure
1515      and copy information.  */
1516   pelem->ordering_len = collate->nweight;
1517
1518   /* First we write an array with the number of values for each
1519      weight.  */
1520   obstack_grow (&collate->element_mem, collate->weight_cnt,
1521                 collate->nrules * sizeof (unsigned int));
1522
1523   /* Now the weights itselves.  */
1524   obstack_grow (&collate->element_mem, collate->weight,
1525                 collate->nweight * sizeof (unsigned int));
1526
1527   /* Get result.  */
1528   pelem->ordering = obstack_finish (&collate->element_mem);
1529
1530   /* Now we handle the "patches".  */
1531   while (collate->current_patch != NULL)
1532     {
1533       patch_t *this_patch;
1534
1535       this_patch = collate->current_patch;
1536
1537       this_patch->where.pos = &pelem->ordering[collate->nrules
1538                                               + this_patch->where.idx];
1539
1540       collate->current_patch = this_patch->next;
1541       this_patch->next = collate->all_patches;
1542       collate->all_patches = this_patch;
1543     }
1544
1545   /* Set information for next round.  */
1546   collate->was_ellipsis = 0;
1547   if (collate->kind != undefined)
1548     collate->last_char = pelem->name[0];
1549 }