Adjust for additional parameter to lr_token.
[kopensolaris-gnu/glibc.git] / locale / programs / ld-collate.c
1 /* Copyright (C) 1995-1999, 2000, 2001 Free Software Foundation, Inc.
2    This file is part of the GNU C Library.
3    Contributed by Ulrich Drepper <drepper@gnu.org>, 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 Lesser General Public
7    License as published by the Free Software Foundation; either
8    version 2.1 of the 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    Lesser General Public License for more details.
14
15    You should have received a copy of the GNU Lesser General Public
16    License along with the GNU C Library; if not, write to the Free
17    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
18    02111-1307 USA.  */
19
20 #ifdef HAVE_CONFIG_H
21 # include <config.h>
22 #endif
23
24 #include <errno.h>
25 #include <error.h>
26 #include <stdlib.h>
27 #include <wchar.h>
28 #include <sys/param.h>
29
30 #include "charmap.h"
31 #include "localeinfo.h"
32 #include "linereader.h"
33 #include "locfile.h"
34 #include "localedef.h"
35 #include "elem-hash.h"
36
37 /* Uncomment the following line in the production version.  */
38 /* #define NDEBUG 1 */
39 #include <assert.h>
40
41 #define obstack_chunk_alloc malloc
42 #define obstack_chunk_free free
43
44 static inline void
45 obstack_int32_grow (struct obstack *obstack, int32_t data)
46 {
47   if (sizeof (int32_t) == sizeof (int))
48     obstack_int_grow (obstack, data);
49   else
50     obstack_grow (obstack, &data, sizeof (int32_t));
51 }
52
53 static inline void
54 obstack_int32_grow_fast (struct obstack *obstack, int32_t data)
55 {
56   if (sizeof (int32_t) == sizeof (int))
57     obstack_int_grow_fast (obstack, data);
58   else
59     obstack_grow (obstack, &data, sizeof (int32_t));
60 }
61
62 /* Forward declaration.  */
63 struct element_t;
64
65 /* Data type for list of strings.  */
66 struct section_list
67 {
68   /* Successor in the known_sections list.  */
69   struct section_list *def_next;
70   /* Successor in the sections list.  */
71   struct section_list *next;
72   /* Name of the section.  */
73   const char *name;
74   /* First element of this section.  */
75   struct element_t *first;
76   /* Last element of this section.  */
77   struct element_t *last;
78   /* These are the rules for this section.  */
79   enum coll_sort_rule *rules;
80   /* Index of the rule set in the appropriate section of the output file.  */
81   int ruleidx;
82 };
83
84 struct element_t;
85
86 struct element_list_t
87 {
88   /* Number of elements.  */
89   int cnt;
90
91   struct element_t **w;
92 };
93
94 /* Data type for collating element.  */
95 struct element_t
96 {
97   const char *name;
98
99   const char *mbs;
100   size_t nmbs;
101   const uint32_t *wcs;
102   size_t nwcs;
103   int *mborder;
104   int wcorder;
105
106   /* The following is a bit mask which bits are set if this element is
107      used in the appropriate level.  Interesting for the singlebyte
108      weight computation.
109
110      XXX The type here restricts the number of levels to 32.  It could
111      be changed if necessary but I doubt this is necessary.  */
112   unsigned int used_in_level;
113
114   struct element_list_t *weights;
115
116   /* Nonzero if this is a real character definition.  */
117   int is_character;
118
119   /* Order of the character in the sequence.  This information will
120      be used in range expressions.  */
121   int mbseqorder;
122   int wcseqorder;
123
124   /* Where does the definition come from.  */
125   const char *file;
126   size_t line;
127
128   /* Which section does this belong to.  */
129   struct section_list *section;
130
131   /* Predecessor and successor in the order list.  */
132   struct element_t *last;
133   struct element_t *next;
134
135   /* Next element in multibyte output list.  */
136   struct element_t *mbnext;
137   struct element_t *mblast;
138
139   /* Next element in wide character output list.  */
140   struct element_t *wcnext;
141   struct element_t *wclast;
142 };
143
144 /* Special element value.  */
145 #define ELEMENT_ELLIPSIS2       ((struct element_t *) 1)
146 #define ELEMENT_ELLIPSIS3       ((struct element_t *) 2)
147 #define ELEMENT_ELLIPSIS4       ((struct element_t *) 3)
148
149 /* Data type for collating symbol.  */
150 struct symbol_t
151 {
152   const char *name;
153
154   /* Point to place in the order list.  */
155   struct element_t *order;
156
157   /* Where does the definition come from.  */
158   const char *file;
159   size_t line;
160 };
161
162 /* Sparse table of struct element_t *.  */
163 #define TABLE wchead_table
164 #define ELEMENT struct element_t *
165 #define DEFAULT NULL
166 #define ITERATE
167 #define NO_FINALIZE
168 #include "3level.h"
169
170 /* Sparse table of int32_t.  */
171 #define TABLE collidx_table
172 #define ELEMENT int32_t
173 #define DEFAULT 0
174 #include "3level.h"
175
176 /* Sparse table of uint32_t.  */
177 #define TABLE collseq_table
178 #define ELEMENT uint32_t
179 #define DEFAULT ~((uint32_t) 0)
180 #include "3level.h"
181
182
183 /* The real definition of the struct for the LC_COLLATE locale.  */
184 struct locale_collate_t
185 {
186   int col_weight_max;
187   int cur_weight_max;
188
189   /* List of known scripts.  */
190   struct section_list *known_sections;
191   /* List of used sections.  */
192   struct section_list *sections;
193   /* Current section using definition.  */
194   struct section_list *current_section;
195   /* There always can be an unnamed section.  */
196   struct section_list unnamed_section;
197   /* To make handling of errors easier we have another section.  */
198   struct section_list error_section;
199   /* Sometimes we are defining the values for collating symbols before
200      the first actual section.  */
201   struct section_list symbol_section;
202
203   /* Start of the order list.  */
204   struct element_t *start;
205
206   /* The undefined element.  */
207   struct element_t undefined;
208
209   /* This is the cursor for `reorder_after' insertions.  */
210   struct element_t *cursor;
211
212   /* This value is used when handling ellipsis.  */
213   struct element_t ellipsis_weight;
214
215   /* Known collating elements.  */
216   hash_table elem_table;
217
218   /* Known collating symbols.  */
219   hash_table sym_table;
220
221   /* Known collation sequences.  */
222   hash_table seq_table;
223
224   struct obstack mempool;
225
226   /* The LC_COLLATE category is a bit special as it is sometimes possible
227      that the definitions from more than one input file contains information.
228      Therefore we keep all relevant input in a list.  */
229   struct locale_collate_t *next;
230
231   /* Arrays with heads of the list for each of the leading bytes in
232      the multibyte sequences.  */
233   struct element_t *mbheads[256];
234
235   /* Arrays with heads of the list for each of the leading bytes in
236      the multibyte sequences.  */
237   struct wchead_table wcheads;
238
239   /* The arrays with the collation sequence order.  */
240   unsigned char mbseqorder[256];
241   struct collseq_table wcseqorder;
242 };
243
244
245 /* We have a few global variables which are used for reading all
246    LC_COLLATE category descriptions in all files.  */
247 static uint32_t nrules;
248
249
250 /* We need UTF-8 encoding of numbers.  */
251 static inline int
252 utf8_encode (char *buf, int val)
253 {
254   int retval;
255
256   if (val < 0x80)
257     {
258       *buf++ = (char) val;
259       retval = 1;
260     }
261   else
262     {
263       int step;
264
265       for (step = 2; step < 6; ++step)
266         if ((val & (~(uint32_t)0 << (5 * step + 1))) == 0)
267           break;
268       retval = step;
269
270       *buf = (unsigned char) (~0xff >> step);
271       --step;
272       do
273         {
274           buf[step] = 0x80 | (val & 0x3f);
275           val >>= 6;
276         }
277       while (--step > 0);
278       *buf |= val;
279     }
280
281   return retval;
282 }
283
284
285 static struct section_list *
286 make_seclist_elem (struct locale_collate_t *collate, const char *string,
287                    struct section_list *next)
288 {
289   struct section_list *newp;
290
291   newp = (struct section_list *) obstack_alloc (&collate->mempool,
292                                                 sizeof (*newp));
293   newp->next = next;
294   newp->name = string;
295   newp->first = NULL;
296   newp->last = NULL;
297
298   return newp;
299 }
300
301
302 static struct element_t *
303 new_element (struct locale_collate_t *collate, const char *mbs, size_t mbslen,
304              const uint32_t *wcs, const char *name, size_t namelen,
305              int is_character)
306 {
307   struct element_t *newp;
308
309   newp = (struct element_t *) obstack_alloc (&collate->mempool,
310                                              sizeof (*newp));
311   newp->name = name == NULL ? NULL : obstack_copy0 (&collate->mempool,
312                                                     name, namelen);
313   if (mbs != NULL)
314     {
315       newp->mbs = obstack_copy0 (&collate->mempool, mbs, mbslen);
316       newp->nmbs = mbslen;
317     }
318   else
319     {
320       newp->mbs = NULL;
321       newp->nmbs = 0;
322     }
323   if (wcs != NULL)
324     {
325       size_t nwcs = wcslen ((wchar_t *) wcs);
326       uint32_t zero = 0;
327       obstack_grow (&collate->mempool, wcs, nwcs * sizeof (uint32_t));
328       obstack_grow (&collate->mempool, &zero, sizeof (uint32_t));
329       newp->wcs = (uint32_t *) obstack_finish (&collate->mempool);
330       newp->nwcs = nwcs;
331     }
332   else
333     {
334       newp->wcs = NULL;
335       newp->nwcs = 0;
336     }
337   newp->mborder = NULL;
338   newp->wcorder = 0;
339   newp->used_in_level = 0;
340   newp->is_character = is_character;
341
342   /* Will be assigned later.  XXX  */
343   newp->mbseqorder = 0;
344   newp->wcseqorder = 0;
345
346   /* Will be allocated later.  */
347   newp->weights = NULL;
348
349   newp->file = NULL;
350   newp->line = 0;
351
352   newp->section = collate->current_section;
353
354   newp->last = NULL;
355   newp->next = NULL;
356
357   newp->mbnext = NULL;
358   newp->mblast = NULL;
359
360   newp->wcnext = NULL;
361   newp->wclast = NULL;
362
363   return newp;
364 }
365
366
367 static struct symbol_t *
368 new_symbol (struct locale_collate_t *collate, const char *name, size_t len)
369 {
370   struct symbol_t *newp;
371
372   newp = (struct symbol_t *) obstack_alloc (&collate->mempool, sizeof (*newp));
373
374   newp->name = obstack_copy0 (&collate->mempool, name, len);
375   newp->order = NULL;
376
377   newp->file = NULL;
378   newp->line = 0;
379
380   return newp;
381 }
382
383
384 /* Test whether this name is already defined somewhere.  */
385 static int
386 check_duplicate (struct linereader *ldfile, struct locale_collate_t *collate,
387                  const struct charmap_t *charmap,
388                  struct repertoire_t *repertoire, const char *symbol,
389                  size_t symbol_len)
390 {
391   void *ignore = NULL;
392
393   if (find_entry (&charmap->char_table, symbol, symbol_len, &ignore) == 0)
394     {
395       lr_error (ldfile, _("`%.*s' already defined in charmap"),
396                 (int) symbol_len, symbol);
397       return 1;
398     }
399
400   if (repertoire != NULL
401       && (find_entry (&repertoire->char_table, symbol, symbol_len, &ignore)
402           == 0))
403     {
404       lr_error (ldfile, _("`%.*s' already defined in repertoire"),
405                 (int) symbol_len, symbol);
406       return 1;
407     }
408
409   if (find_entry (&collate->sym_table, symbol, symbol_len, &ignore) == 0)
410     {
411       lr_error (ldfile, _("`%.*s' already defined as collating symbol"),
412                 (int) symbol_len, symbol);
413       return 1;
414     }
415
416   if (find_entry (&collate->elem_table, symbol, symbol_len, &ignore) == 0)
417     {
418       lr_error (ldfile, _("`%.*s' already defined as collating element"),
419                 (int) symbol_len, symbol);
420       return 1;
421     }
422
423   return 0;
424 }
425
426
427 /* Read the direction specification.  */
428 static void
429 read_directions (struct linereader *ldfile, struct token *arg,
430                  const struct charmap_t *charmap,
431                  struct repertoire_t *repertoire, struct localedef_t *result)
432 {
433   int cnt = 0;
434   int max = nrules ?: 10;
435   enum coll_sort_rule *rules = calloc (max, sizeof (*rules));
436   int warned = 0;
437   struct locale_collate_t *collate = result->categories[LC_COLLATE].collate;
438
439   while (1)
440     {
441       int valid = 0;
442
443       if (arg->tok == tok_forward)
444         {
445           if (rules[cnt] & sort_backward)
446             {
447               if (! warned)
448                 {
449                   lr_error (ldfile, _("\
450 %s: `forward' and `backward' are mutually excluding each other"),
451                             "LC_COLLATE");
452                   warned = 1;
453                 }
454             }
455           else if (rules[cnt] & sort_forward)
456             {
457               if (! warned)
458                 {
459                   lr_error (ldfile, _("\
460 %s: `%s' mentioned more than once in definition of weight %d"),
461                             "LC_COLLATE", "forward", cnt + 1);
462                 }
463             }
464           else
465             rules[cnt] |= sort_forward;
466
467           valid = 1;
468         }
469       else if (arg->tok == tok_backward)
470         {
471           if (rules[cnt] & sort_forward)
472             {
473               if (! warned)
474                 {
475                   lr_error (ldfile, _("\
476 %s: `forward' and `backward' are mutually excluding each other"),
477                             "LC_COLLATE");
478                   warned = 1;
479                 }
480             }
481           else if (rules[cnt] & sort_backward)
482             {
483               if (! warned)
484                 {
485                   lr_error (ldfile, _("\
486 %s: `%s' mentioned more than once in definition of weight %d"),
487                             "LC_COLLATE", "backward", cnt + 1);
488                 }
489             }
490           else
491             rules[cnt] |= sort_backward;
492
493           valid = 1;
494         }
495       else if (arg->tok == tok_position)
496         {
497           if (rules[cnt] & sort_position)
498             {
499               if (! warned)
500                 {
501                   lr_error (ldfile, _("\
502 %s: `%s' mentioned more than once in definition of weight %d"),
503                             "LC_COLLATE", "position", cnt + 1);
504                 }
505             }
506           else
507             rules[cnt] |= sort_position;
508
509           valid = 1;
510         }
511
512       if (valid)
513         arg = lr_token (ldfile, charmap, result, repertoire, verbose);
514
515       if (arg->tok == tok_eof || arg->tok == tok_eol || arg->tok == tok_comma
516           || arg->tok == tok_semicolon)
517         {
518           if (! valid && ! warned)
519             {
520               lr_error (ldfile, _("%s: syntax error"), "LC_COLLATE");
521               warned = 1;
522             }
523
524           /* See whether we have to increment the counter.  */
525           if (arg->tok != tok_comma && rules[cnt] != 0)
526             {
527               /* Add the default `forward' if we have seen only `position'.  */
528               if (rules[cnt] == sort_position)
529                 rules[cnt] = sort_position | sort_forward;
530
531               ++cnt;
532             }
533
534           if (arg->tok == tok_eof || arg->tok == tok_eol)
535             /* End of line or file, so we exit the loop.  */
536             break;
537
538           if (nrules == 0)
539             {
540               /* See whether we have enough room in the array.  */
541               if (cnt == max)
542                 {
543                   max += 10;
544                   rules = (enum coll_sort_rule *) xrealloc (rules,
545                                                             max
546                                                             * sizeof (*rules));
547                   memset (&rules[cnt], '\0', (max - cnt) * sizeof (*rules));
548                 }
549             }
550           else
551             {
552               if (cnt == nrules)
553                 {
554                   /* There must not be any more rule.  */
555                   if (! warned)
556                     {
557                       lr_error (ldfile, _("\
558 %s: too many rules; first entry only had %d"),
559                                 "LC_COLLATE", nrules);
560                       warned = 1;
561                     }
562
563                   lr_ignore_rest (ldfile, 0);
564                   break;
565                 }
566             }
567         }
568       else
569         {
570           if (! warned)
571             {
572               lr_error (ldfile, _("%s: syntax error"), "LC_COLLATE");
573               warned = 1;
574             }
575         }
576
577       arg = lr_token (ldfile, charmap, result, repertoire, verbose);
578     }
579
580   if (nrules == 0)
581     {
582       /* Now we know how many rules we have.  */
583       nrules = cnt;
584       rules = (enum coll_sort_rule *) xrealloc (rules,
585                                                 nrules * sizeof (*rules));
586     }
587   else
588     {
589       if (cnt < nrules)
590         {
591           /* Not enough rules in this specification.  */
592           if (! warned)
593             lr_error (ldfile, _("%s: not enough sorting rules"), "LC_COLLATE");
594
595           do
596             rules[cnt] = sort_forward;
597           while (++cnt < nrules);
598         }
599     }
600
601   collate->current_section->rules = rules;
602 }
603
604
605 static struct element_t *
606 find_element (struct linereader *ldfile, struct locale_collate_t *collate,
607               const char *str, size_t len)
608 {
609   struct element_t *result = NULL;
610
611   /* Search for the entries among the collation sequences already define.  */
612   if (find_entry (&collate->seq_table, str, len, (void **) &result) != 0)
613     {
614       /* Nope, not define yet.  So we see whether it is a
615          collation symbol.  */
616       void *ptr;
617
618       if (find_entry (&collate->sym_table, str, len, &ptr) == 0)
619         {
620           /* It's a collation symbol.  */
621           struct symbol_t *sym = (struct symbol_t *) ptr;
622           result = sym->order;
623
624           if (result == NULL)
625             result = sym->order = new_element (collate, NULL, 0, NULL,
626                                                NULL, 0, 0);
627         }
628       else if (find_entry (&collate->elem_table, str, len,
629                            (void **) &result) != 0)
630         {
631           /* It's also no collation element.  So it is a character
632              element defined later.  */
633           result = new_element (collate, NULL, 0, NULL, str, len, 1);
634           /* Insert it into the sequence table.  */
635           insert_entry (&collate->seq_table, str, len, result);
636         }
637     }
638
639   return result;
640 }
641
642
643 static void
644 unlink_element (struct locale_collate_t *collate)
645 {
646   if (collate->cursor == collate->start)
647     {
648       assert (collate->cursor->next == NULL);
649       assert (collate->cursor->last == NULL);
650       collate->cursor = NULL;
651     }
652   else
653     {
654       if (collate->cursor->next != NULL)
655         collate->cursor->next->last = collate->cursor->last;
656       if (collate->cursor->last != NULL)
657         collate->cursor->last->next = collate->cursor->next;
658       collate->cursor = collate->cursor->last;
659     }
660 }
661
662
663 static void
664 insert_weights (struct linereader *ldfile, struct element_t *elem,
665                 const struct charmap_t *charmap,
666                 struct repertoire_t *repertoire, struct localedef_t *result,
667                 enum token_t ellipsis)
668 {
669   int weight_cnt;
670   struct token *arg;
671   struct locale_collate_t *collate = result->categories[LC_COLLATE].collate;
672
673   /* Initialize all the fields.  */
674   elem->file = ldfile->fname;
675   elem->line = ldfile->lineno;
676
677   elem->last = collate->cursor;
678   elem->next = collate->cursor ? collate->cursor->next : NULL;
679   if (collate->cursor != NULL && collate->cursor->next != NULL)
680     collate->cursor->next->last = elem;
681   if (collate->cursor != NULL)
682     collate->cursor->next = elem;
683   if (collate->start == NULL)
684     {
685       assert (collate->cursor == NULL);
686       collate->start = elem;
687     }
688
689   elem->section = collate->current_section;
690
691   if (collate->current_section->first == NULL)
692     collate->current_section->first = elem;
693   if (collate->current_section->last == collate->cursor)
694     collate->current_section->last = elem;
695
696   collate->cursor = elem;
697
698   elem->weights = (struct element_list_t *)
699     obstack_alloc (&collate->mempool, nrules * sizeof (struct element_list_t));
700   memset (elem->weights, '\0', nrules * sizeof (struct element_list_t));
701
702   weight_cnt = 0;
703
704   arg = lr_token (ldfile, charmap, result, repertoire, verbose);
705   do
706     {
707       if (arg->tok == tok_eof || arg->tok == tok_eol)
708         break;
709
710       if (arg->tok == tok_ignore)
711         {
712           /* The weight for this level has to be ignored.  We use the
713              null pointer to indicate this.  */
714           elem->weights[weight_cnt].w = (struct element_t **)
715             obstack_alloc (&collate->mempool, sizeof (struct element_t *));
716           elem->weights[weight_cnt].w[0] = NULL;
717           elem->weights[weight_cnt].cnt = 1;
718         }
719       else if (arg->tok == tok_bsymbol || arg->tok == tok_ucs4)
720         {
721           char ucs4str[10];
722           struct element_t *val;
723           char *symstr;
724           size_t symlen;
725
726           if (arg->tok == tok_bsymbol)
727             {
728               symstr = arg->val.str.startmb;
729               symlen = arg->val.str.lenmb;
730             }
731           else
732             {
733               snprintf (ucs4str, sizeof (ucs4str), "U%08X", arg->val.ucs4);
734               symstr = ucs4str;
735               symlen = 9;
736             }
737
738           val = find_element (ldfile, collate, symstr, symlen);
739           if (val == NULL)
740             break;
741
742           elem->weights[weight_cnt].w = (struct element_t **)
743             obstack_alloc (&collate->mempool, sizeof (struct element_t *));
744           elem->weights[weight_cnt].w[0] = val;
745           elem->weights[weight_cnt].cnt = 1;
746         }
747       else if (arg->tok == tok_string)
748         {
749           /* Split the string up in the individual characters and put
750              the element definitions in the list.  */
751           const char *cp = arg->val.str.startmb;
752           int cnt = 0;
753           struct element_t *charelem;
754           struct element_t **weights = NULL;
755           int max = 0;
756
757           if (*cp == '\0')
758             {
759               lr_error (ldfile, _("%s: empty weight string not allowed"),
760                         "LC_COLLATE");
761               lr_ignore_rest (ldfile, 0);
762               break;
763             }
764
765           do
766             {
767               if (*cp == '<')
768                 {
769                   /* Ahh, it's a bsymbol or an UCS4 value.  If it's
770                      the latter we have to unify the name.  */
771                   const char *startp = ++cp;
772                   size_t len;
773
774                   while (*cp != '>')
775                     {
776                       if (*cp == ldfile->escape_char)
777                         ++cp;
778                       if (*cp == '\0')
779                         /* It's a syntax error.  */
780                         goto syntax;
781
782                       ++cp;
783                     }
784
785                   if (cp - startp == 5 && startp[0] == 'U'
786                       && isxdigit (startp[1]) && isxdigit (startp[2])
787                       && isxdigit (startp[3]) && isxdigit (startp[4]))
788                     {
789                       unsigned int ucs4 = strtoul (startp + 1, NULL, 16);
790                       char *newstr;
791
792                       newstr = (char *) xmalloc (10);
793                       snprintf (newstr, 10, "U%08X", ucs4);
794                       startp = newstr;
795
796                       len = 9;
797                     }
798                   else
799                     len = cp - startp;
800
801                   charelem = find_element (ldfile, collate, startp, len);
802                   ++cp;
803                 }
804               else
805                 {
806                   /* People really shouldn't use characters directly in
807                      the string.  Especially since it's not really clear
808                      what this means.  We interpret all characters in the
809                      string as if that would be bsymbols.  Otherwise we
810                      would have to match back to bsymbols somehow and this
811                      is normally not what people normally expect.  */
812                   charelem = find_element (ldfile, collate, cp++, 1);
813                 }
814
815               if (charelem == NULL)
816                 {
817                   /* We ignore the rest of the line.  */
818                   lr_ignore_rest (ldfile, 0);
819                   break;
820                 }
821
822               /* Add the pointer.  */
823               if (cnt >= max)
824                 {
825                   struct element_t **newp;
826                   max += 10;
827                   newp = (struct element_t **)
828                     alloca (max * sizeof (struct element_t *));
829                   memcpy (newp, weights, cnt * sizeof (struct element_t *));
830                   weights = newp;
831                 }
832               weights[cnt++] = charelem;
833             }
834           while (*cp != '\0');
835
836           /* Now store the information.  */
837           elem->weights[weight_cnt].w = (struct element_t **)
838             obstack_alloc (&collate->mempool,
839                            cnt * sizeof (struct element_t *));
840           memcpy (elem->weights[weight_cnt].w, weights,
841                   cnt * sizeof (struct element_t *));
842           elem->weights[weight_cnt].cnt = cnt;
843
844           /* We don't need the string anymore.  */
845           free (arg->val.str.startmb);
846         }
847       else if (ellipsis != tok_none
848                && (arg->tok == tok_ellipsis2
849                    || arg->tok == tok_ellipsis3
850                    || arg->tok == tok_ellipsis4))
851         {
852           /* It must be the same ellipsis as used in the initial column.  */
853           if (arg->tok != ellipsis)
854             lr_error (ldfile, _("\
855 %s: weights must use the same ellipsis symbol as the name"),
856                       "LC_COLLATE");
857
858           /* The weight for this level will depend on the element
859              iterating over the range.  Put a placeholder.  */
860           elem->weights[weight_cnt].w = (struct element_t **)
861             obstack_alloc (&collate->mempool, sizeof (struct element_t *));
862           elem->weights[weight_cnt].w[0] = ELEMENT_ELLIPSIS2;
863           elem->weights[weight_cnt].cnt = 1;
864         }
865       else
866         {
867         syntax:
868           /* It's a syntax error.  */
869           lr_error (ldfile, _("%s: syntax error"), "LC_COLLATE");
870           lr_ignore_rest (ldfile, 0);
871           break;
872         }
873
874       arg = lr_token (ldfile, charmap, result, repertoire, verbose);
875       /* This better should be the end of the line or a semicolon.  */
876       if (arg->tok == tok_semicolon)
877         /* OK, ignore this and read the next token.  */
878         arg = lr_token (ldfile, charmap, result, repertoire, verbose);
879       else if (arg->tok != tok_eof && arg->tok != tok_eol)
880         {
881           /* It's a syntax error.  */
882           lr_error (ldfile, _("%s: syntax error"), "LC_COLLATE");
883           lr_ignore_rest (ldfile, 0);
884           break;
885         }
886     }
887   while (++weight_cnt < nrules);
888
889   if (weight_cnt < nrules)
890     {
891       /* This means the rest of the line uses the current element as
892          the weight.  */
893       do
894         {
895           elem->weights[weight_cnt].w = (struct element_t **)
896             obstack_alloc (&collate->mempool, sizeof (struct element_t *));
897           if (ellipsis == tok_none)
898             elem->weights[weight_cnt].w[0] = elem;
899           else
900             elem->weights[weight_cnt].w[0] = ELEMENT_ELLIPSIS2;
901           elem->weights[weight_cnt].cnt = 1;
902         }
903       while (++weight_cnt < nrules);
904     }
905   else
906     {
907       if (arg->tok == tok_ignore || arg->tok == tok_bsymbol)
908         {
909           /* Too many rule values.  */
910           lr_error (ldfile, _("%s: too many values"), "LC_COLLATE");
911           lr_ignore_rest (ldfile, 0);
912         }
913       else
914         lr_ignore_rest (ldfile, arg->tok != tok_eol && arg->tok != tok_eof);
915     }
916 }
917
918
919 static int
920 insert_value (struct linereader *ldfile, const char *symstr, size_t symlen,
921               const struct charmap_t *charmap, struct repertoire_t *repertoire,
922               struct localedef_t *result)
923 {
924   /* First find out what kind of symbol this is.  */
925   struct charseq *seq;
926   uint32_t wc;
927   struct element_t *elem = NULL;
928   struct locale_collate_t *collate = result->categories[LC_COLLATE].collate;
929
930   /* Try to find the character in the charmap.  */
931   seq = charmap_find_value (charmap, symstr, symlen);
932
933   /* Determine the wide character.  */
934   if (seq == NULL || seq->ucs4 == UNINITIALIZED_CHAR_VALUE)
935     {
936       wc = repertoire_find_value (repertoire, symstr, symlen);
937       if (seq != NULL)
938         seq->ucs4 = wc;
939     }
940   else
941     wc = seq->ucs4;
942
943   if (wc == ILLEGAL_CHAR_VALUE && seq == NULL)
944     {
945       /* It's no character, so look through the collation elements and
946          symbol list.  */
947       if (find_entry (&collate->elem_table, symstr, symlen,
948                            (void **) &elem) != 0)
949         {
950           void *result;
951           struct symbol_t *sym = NULL;
952
953           /* It's also collation element.  Therefore it's either a
954              collating symbol or it's a character which is not
955              supported by the character set.  In the later case we
956              simply create a dummy entry.  */
957           if (find_entry (&collate->sym_table, symstr, symlen, &result) == 0)
958             {
959               /* It's a collation symbol.  */
960               sym = (struct symbol_t *) result;
961
962               elem = sym->order;
963             }
964
965           if (elem == NULL)
966             {
967               elem = new_element (collate, NULL, 0, NULL, symstr, symlen, 0);
968
969               if (sym != NULL)
970                 sym->order = elem;
971               else
972                 /* Enter a fake element in the sequence table.  This
973                    won't cause anything in the output since there is
974                    no multibyte or wide character associated with
975                    it.  */
976                 insert_entry (&collate->seq_table, symstr, symlen, elem);
977             }
978         }
979     }
980   else
981     {
982       /* Otherwise the symbols stands for a character.  */
983       if (find_entry (&collate->seq_table, symstr, symlen,
984                       (void **) &elem) != 0)
985         {
986           uint32_t wcs[2] = { wc, 0 };
987
988           /* We have to allocate an entry.  */
989           elem = new_element (collate, seq != NULL ? seq->bytes : NULL,
990                               seq != NULL ? seq->nbytes : 0,
991                               wc == ILLEGAL_CHAR_VALUE ? NULL : wcs,
992                               symstr, symlen, 1);
993
994           /* And add it to the table.  */
995           if (insert_entry (&collate->seq_table, symstr, symlen, elem) != 0)
996             /* This cannot happen.  */
997             assert (! "Internal error");
998         }
999       else
1000         {
1001           /* Maybe the character was used before the definition.  In this case
1002              we have to insert the byte sequences now.  */
1003           if (elem->mbs == NULL && seq != NULL)
1004             {
1005               elem->mbs = obstack_copy0 (&collate->mempool,
1006                                          seq->bytes, seq->nbytes);
1007               elem->nmbs = seq->nbytes;
1008             }
1009
1010           if (elem->wcs == NULL && wc != ILLEGAL_CHAR_VALUE)
1011             {
1012               uint32_t wcs[2] = { wc, 0 };
1013
1014               elem->wcs = obstack_copy (&collate->mempool, wcs, sizeof (wcs));
1015               elem->nwcs = 1;
1016             }
1017         }
1018     }
1019
1020   /* Test whether this element is not already in the list.  */
1021   if (elem->next != NULL || elem == collate->cursor)
1022     {
1023       lr_error (ldfile, _("order for `%.*s' already defined at %s:%Zu"),
1024                 (int) symlen, symstr, elem->file, elem->line);
1025       lr_ignore_rest (ldfile, 0);
1026       return 1;
1027     }
1028
1029   insert_weights (ldfile, elem, charmap, repertoire, result, tok_none);
1030
1031   return 0;
1032 }
1033
1034
1035 static void
1036 handle_ellipsis (struct linereader *ldfile, const char *symstr, size_t symlen,
1037                  enum token_t ellipsis, const struct charmap_t *charmap,
1038                  struct repertoire_t *repertoire,
1039                  struct localedef_t *result)
1040 {
1041   struct element_t *startp;
1042   struct element_t *endp;
1043   struct locale_collate_t *collate = result->categories[LC_COLLATE].collate;
1044
1045   /* Unlink the entry added for the ellipsis.  */
1046   unlink_element (collate);
1047   startp = collate->cursor;
1048
1049   /* Process and add the end-entry.  */
1050   if (symstr != NULL
1051       && insert_value (ldfile, symstr, symlen, charmap, repertoire, result))
1052     /* Something went wrong with inserting the to-value.  This means
1053        we cannot process the ellipsis.  */
1054     return;
1055
1056   /* Reset the cursor.  */
1057   collate->cursor = startp;
1058
1059   /* Now we have to handle many different situations:
1060      - we have to distinguish between the three different ellipsis forms
1061      - the is the ellipsis at the beginning, in the middle, or at the end.
1062   */
1063   endp = collate->cursor->next;
1064   assert (symstr == NULL || endp != NULL);
1065
1066   /* XXX The following is probably very wrong since also collating symbols
1067      can appear in ranges.  But do we want/can refine the test for that?  */
1068 #if 0
1069   /* Both, the start and the end symbol, must stand for characters.  */
1070   if ((startp != NULL && (startp->name == NULL || ! startp->is_character))
1071       || (endp != NULL && (endp->name == NULL|| ! endp->is_character)))
1072     {
1073       lr_error (ldfile, _("\
1074 %s: the start and the end symbol of a range must stand for characters"),
1075                 "LC_COLLATE");
1076       return;
1077     }
1078 #endif
1079
1080   if (ellipsis == tok_ellipsis3)
1081     {
1082       /* One requirement we make here: the length of the byte
1083          sequences for the first and end character must be the same.
1084          This is mainly to prevent unwanted effects and this is often
1085          not what is wanted.  */
1086       size_t len = (startp->mbs != NULL ? startp->nmbs
1087                     : (endp->mbs != NULL ? endp->nmbs : 0));
1088       char mbcnt[len + 1];
1089       char mbend[len + 1];
1090
1091       /* Well, this should be caught somewhere else already.  Just to
1092          make sure.  */
1093       assert (startp == NULL || startp->wcs == NULL || startp->wcs[1] == 0);
1094       assert (endp == NULL || endp->wcs == NULL || endp->wcs[1] == 0);
1095
1096       if (startp != NULL && endp != NULL
1097           && startp->mbs != NULL && endp->mbs != NULL
1098           && startp->nmbs != endp->nmbs)
1099         {
1100           lr_error (ldfile, _("\
1101 %s: byte sequences of first and last character must have the same length"),
1102                     "LC_COLLATE");
1103           return;
1104         }
1105
1106       /* Determine whether we have to generate multibyte sequences.  */
1107       if ((startp == NULL || startp->mbs != NULL)
1108           && (endp == NULL || endp->mbs != NULL))
1109         {
1110           int cnt;
1111           int ret;
1112
1113           /* Prepare the beginning byte sequence.  This is either from the
1114              beginning byte sequence or it is all nulls if it was an
1115              initial ellipsis.  */
1116           if (startp == NULL || startp->mbs == NULL)
1117             memset (mbcnt, '\0', len);
1118           else
1119             {
1120               memcpy (mbcnt, startp->mbs, len);
1121
1122               /* And increment it so that the value is the first one we will
1123                  try to insert.  */
1124               for (cnt = len - 1; cnt >= 0; --cnt)
1125                 if (++mbcnt[cnt] != '\0')
1126                   break;
1127             }
1128           mbcnt[len] = '\0';
1129
1130           /* And the end sequence.  */
1131           if (endp == NULL || endp->mbs == NULL)
1132             memset (mbend, '\0', len);
1133           else
1134             memcpy (mbend, endp->mbs, len);
1135           mbend[len] = '\0';
1136
1137           /* Test whether we have a correct range.  */
1138           ret = memcmp (mbcnt, mbend, len);
1139           if (ret >= 0)
1140             {
1141               if (ret > 0)
1142                 lr_error (ldfile, _("%s: byte sequence of first character of \
1143 sequence is not lower than that of the last character"), "LC_COLLATE");
1144               return;
1145             }
1146
1147           /* Generate the byte sequences data.  */
1148           while (1)
1149             {
1150               struct charseq *seq;
1151
1152               /* Quite a bit of work ahead.  We have to find the character
1153                  definition for the byte sequence and then determine the
1154                  wide character belonging to it.  */
1155               seq = charmap_find_symbol (charmap, mbcnt, len);
1156               if (seq != NULL)
1157                 {
1158                   struct element_t *elem;
1159                   size_t namelen;
1160
1161                   /* I don't this this can ever happen.  */
1162                   assert (seq->name != NULL);
1163                   namelen = strlen (seq->name);
1164
1165                   if (seq->ucs4 == UNINITIALIZED_CHAR_VALUE)
1166                     seq->ucs4 = repertoire_find_value (repertoire, seq->name,
1167                                                        namelen);
1168
1169                   /* Now we are ready to insert the new value in the
1170                      sequence.  Find out whether the element is
1171                      already known.  */
1172                   if (find_entry (&collate->seq_table, seq->name, namelen,
1173                                   (void **) &elem) != 0)
1174                     {
1175                       uint32_t wcs[2] = { seq->ucs4, 0 };
1176
1177                       /* We have to allocate an entry.  */
1178                       elem = new_element (collate, mbcnt, len,
1179                                           seq->ucs4 == ILLEGAL_CHAR_VALUE
1180                                           ? NULL : wcs, seq->name,
1181                                           namelen, 1);
1182
1183                       /* And add it to the table.  */
1184                       if (insert_entry (&collate->seq_table, seq->name,
1185                                         namelen, elem) != 0)
1186                         /* This cannot happen.  */
1187                         assert (! "Internal error");
1188                     }
1189
1190                   /* Test whether this element is not already in the list.  */
1191                   if (elem->next != NULL || (collate->cursor != NULL
1192                                              && elem->next == collate->cursor))
1193                     {
1194                       lr_error (ldfile, _("\
1195 order for `%.*s' already defined at %s:%Zu"),
1196                                 (int) namelen, seq->name,
1197                                 elem->file, elem->line);
1198                       goto increment;
1199                     }
1200
1201                   /* Enqueue the new element.  */
1202                   elem->last = collate->cursor;
1203                   if (collate->cursor == NULL)
1204                     elem->next = NULL;
1205                   else
1206                     {
1207                       elem->next = collate->cursor->next;
1208                       elem->last->next = elem;
1209                       if (elem->next != NULL)
1210                         elem->next->last = elem;
1211                     }
1212                   if (collate->start == NULL)
1213                     {
1214                       assert (collate->cursor == NULL);
1215                       collate->start = elem;
1216                     }
1217                   collate->cursor = elem;
1218
1219                  /* Add the weight value.  We take them from the
1220                     `ellipsis_weights' member of `collate'.  */
1221                   elem->weights = (struct element_list_t *)
1222                     obstack_alloc (&collate->mempool,
1223                                    nrules * sizeof (struct element_list_t));
1224                   for (cnt = 0; cnt < nrules; ++cnt)
1225                     if (collate->ellipsis_weight.weights[cnt].cnt == 1
1226                         && (collate->ellipsis_weight.weights[cnt].w[0]
1227                             == ELEMENT_ELLIPSIS2))
1228                       {
1229                         elem->weights[cnt].w = (struct element_t **)
1230                           obstack_alloc (&collate->mempool,
1231                                          sizeof (struct element_t *));
1232                         elem->weights[cnt].w[0] = elem;
1233                         elem->weights[cnt].cnt = 1;
1234                       }
1235                     else
1236                       {
1237                         /* Simply use the weight from `ellipsis_weight'.  */
1238                         elem->weights[cnt].w =
1239                           collate->ellipsis_weight.weights[cnt].w;
1240                         elem->weights[cnt].cnt =
1241                           collate->ellipsis_weight.weights[cnt].cnt;
1242                       }
1243                 }
1244
1245               /* Increment for the next round.  */
1246             increment:
1247               for (cnt = len - 1; cnt >= 0; --cnt)
1248                 if (++mbcnt[cnt] != '\0')
1249                   break;
1250
1251               /* Find out whether this was all.  */
1252               if (cnt < 0 || memcmp (mbcnt, mbend, len) >= 0)
1253                 /* Yep, that's all.  */
1254                 break;
1255             }
1256         }
1257     }
1258   else
1259     {
1260       /* For symbolic range we naturally must have a beginning and an
1261          end specified by the user.  */
1262       if (startp == NULL)
1263         lr_error (ldfile, _("\
1264 %s: symbolic range ellipsis must not directly follow `order_start'"),
1265                   "LC_COLLATE");
1266       else if (endp == NULL)
1267         lr_error (ldfile, _("\
1268 %s: symbolic range ellipsis must not be directly followed by `order_end'"),
1269                   "LC_COLLATE");
1270       else
1271         {
1272           /* Determine the range.  To do so we have to determine the
1273              common prefix of the both names and then the numeric
1274              values of both ends.  */
1275           size_t lenfrom = strlen (startp->name);
1276           size_t lento = strlen (endp->name);
1277           char buf[lento + 1];
1278           int preflen = 0;
1279           long int from;
1280           long int to;
1281           char *cp;
1282           int base = ellipsis == tok_ellipsis2 ? 16 : 10;
1283
1284           if (lenfrom != lento)
1285             {
1286             invalid_range:
1287               lr_error (ldfile, _("\
1288 `%s' and `%.*s' are no valid names for symbolic range"),
1289                         startp->name, (int) lento, endp->name);
1290               return;
1291             }
1292
1293           while (startp->name[preflen] == endp->name[preflen])
1294             if (startp->name[preflen] == '\0')
1295               /* Nothing to be done.  The start and end point are identical
1296                  and while inserting the end point we have already given
1297                  the user an error message.  */
1298               return;
1299             else
1300               ++preflen;
1301
1302           errno = 0;
1303           from = strtol (startp->name + preflen, &cp, base);
1304           if ((from == UINT_MAX && errno == ERANGE) || *cp != '\0')
1305             goto invalid_range;
1306
1307           errno = 0;
1308           to = strtol (endp->name + preflen, &cp, base);
1309           if ((to == UINT_MAX && errno == ERANGE) || *cp != '\0')
1310             goto invalid_range;
1311
1312           /* Copy the prefix.  */
1313           memcpy (buf, startp->name, preflen);
1314
1315           /* Loop over all values.  */
1316           for (++from; from < to; ++from)
1317             {
1318               struct element_t *elem = NULL;
1319               struct charseq *seq;
1320               uint32_t wc;
1321               int cnt;
1322
1323               /* Generate the the name.  */
1324               sprintf (buf + preflen, base == 10 ? "%ld" : "%lX", from);
1325
1326               /* Look whether this name is already defined.  */
1327               if (find_entry (&collate->seq_table, buf, symlen,
1328                               (void **) &elem) == 0)
1329                 {
1330                   if (elem->next != NULL || (collate->cursor != NULL
1331                                              && elem->next == collate->cursor))
1332                     {
1333                       lr_error (ldfile, _("\
1334 %s: order for `%.*s' already defined at %s:%Zu"),
1335                                 "LC_COLLATE", (int) lenfrom, buf,
1336                                 elem->file, elem->line);
1337                       continue;
1338                     }
1339
1340                   if (elem->name == NULL)
1341                     {
1342                       lr_error (ldfile, _("%s: `%s' must be a character"),
1343                                 "LC_COLLATE", buf);
1344                       continue;
1345                     }
1346                 }
1347
1348               if (elem == NULL || (elem->mbs == NULL && elem->wcs == NULL))
1349                 {
1350                   /* Search for a character of this name.  */
1351                   seq = charmap_find_value (charmap, buf, lenfrom);
1352                   if (seq == NULL || seq->ucs4 == UNINITIALIZED_CHAR_VALUE)
1353                     {
1354                       wc = repertoire_find_value (repertoire, buf, lenfrom);
1355
1356                       if (seq != NULL)
1357                         seq->ucs4 = wc;
1358                     }
1359                   else
1360                     wc = seq->ucs4;
1361
1362                   if (wc == ILLEGAL_CHAR_VALUE && seq == NULL)
1363                     /* We don't know anything about a character with this
1364                        name.  XXX Should we warn?  */
1365                     continue;
1366
1367                   if (elem == NULL)
1368                     {
1369                       uint32_t wcs[2] = { wc, 0 };
1370
1371                       /* We have to allocate an entry.  */
1372                       elem = new_element (collate,
1373                                           seq != NULL ? seq->bytes : NULL,
1374                                           seq != NULL ? seq->nbytes : 0,
1375                                           wc == ILLEGAL_CHAR_VALUE
1376                                           ? NULL : wcs, buf, lenfrom, 1);
1377                     }
1378                   else
1379                     {
1380                       /* Update the element.  */
1381                       if (seq != NULL)
1382                         {
1383                           elem->mbs = obstack_copy0 (&collate->mempool,
1384                                                      seq->bytes, seq->nbytes);
1385                           elem->nmbs = seq->nbytes;
1386                         }
1387
1388                       if (wc != ILLEGAL_CHAR_VALUE)
1389                         {
1390                           uint32_t zero = 0;
1391
1392                           obstack_grow (&collate->mempool,
1393                                         &wc, sizeof (uint32_t));
1394                           obstack_grow (&collate->mempool,
1395                                         &zero, sizeof (uint32_t));
1396                           elem->wcs = obstack_finish (&collate->mempool);
1397                           elem->nwcs = 1;
1398                         }
1399                     }
1400
1401                   elem->file = ldfile->fname;
1402                   elem->line = ldfile->lineno;
1403                   elem->section = collate->current_section;
1404                 }
1405
1406               /* Enqueue the new element.  */
1407               elem->last = collate->cursor;
1408               elem->next = collate->cursor->next;
1409               elem->last->next = elem;
1410               if (elem->next != NULL)
1411                 elem->next->last = elem;
1412               collate->cursor = elem;
1413
1414               /* Now add the weights.  They come from the `ellipsis_weights'
1415                  member of `collate'.  */
1416               elem->weights = (struct element_list_t *)
1417                 obstack_alloc (&collate->mempool,
1418                                nrules * sizeof (struct element_list_t));
1419               for (cnt = 0; cnt < nrules; ++cnt)
1420                 if (collate->ellipsis_weight.weights[cnt].cnt == 1
1421                     && (collate->ellipsis_weight.weights[cnt].w[0]
1422                         == ELEMENT_ELLIPSIS2))
1423                   {
1424                     elem->weights[cnt].w = (struct element_t **)
1425                       obstack_alloc (&collate->mempool,
1426                                      sizeof (struct element_t *));
1427                     elem->weights[cnt].w[0] = elem;
1428                     elem->weights[cnt].cnt = 1;
1429                   }
1430                 else
1431                   {
1432                     /* Simly use the weight from `ellipsis_weight'.  */
1433                     elem->weights[cnt].w =
1434                       collate->ellipsis_weight.weights[cnt].w;
1435                     elem->weights[cnt].cnt =
1436                       collate->ellipsis_weight.weights[cnt].cnt;
1437                   }
1438             }
1439         }
1440     }
1441 }
1442
1443
1444 static void
1445 collate_startup (struct linereader *ldfile, struct localedef_t *locale,
1446                  struct localedef_t *copy_locale, int ignore_content)
1447 {
1448   if (!ignore_content && locale->categories[LC_COLLATE].collate == NULL)
1449     {
1450       struct locale_collate_t *collate;
1451
1452       if (copy_locale == NULL)
1453         {
1454           collate = locale->categories[LC_COLLATE].collate =
1455             (struct locale_collate_t *)
1456             xcalloc (1, sizeof (struct locale_collate_t));
1457
1458           /* Init the various data structures.  */
1459           init_hash (&collate->elem_table, 100);
1460           init_hash (&collate->sym_table, 100);
1461           init_hash (&collate->seq_table, 500);
1462           obstack_init (&collate->mempool);
1463
1464           collate->col_weight_max = -1;
1465         }
1466       else
1467         /* Reuse the copy_locale's data structures.  */
1468         collate = locale->categories[LC_COLLATE].collate =
1469           copy_locale->categories[LC_COLLATE].collate;
1470     }
1471
1472   ldfile->translate_strings = 0;
1473   ldfile->return_widestr = 0;
1474 }
1475
1476
1477 void
1478 collate_finish (struct localedef_t *locale, const struct charmap_t *charmap)
1479 {
1480   /* Now is the time when we can assign the individual collation
1481      values for all the symbols.  We have possibly different values
1482      for the wide- and the multibyte-character symbols.  This is done
1483      since it might make a difference in the encoding if there is in
1484      some cases no multibyte-character but there are wide-characters.
1485      (The other way around it is not important since theencoded
1486      collation value in the wide-character case is 32 bits wide and
1487      therefore requires no encoding).
1488
1489      The lowest collation value assigned is 2.  Zero is reserved for
1490      the NUL byte terminating the strings in the `strxfrm'/`wcsxfrm'
1491      functions and 1 is used to separate the individual passes for the
1492      different rules.
1493
1494      We also have to construct is list with all the bytes/words which
1495      can come first in a sequence, followed by all the elements which
1496      also start with this byte/word.  The order is reverse which has
1497      among others the important effect that longer strings are located
1498      first in the list.  This is required for the output data since
1499      the algorithm used in `strcoll' etc depends on this.
1500
1501      The multibyte case is easy.  We simply sort into an array with
1502      256 elements.  */
1503   struct locale_collate_t *collate = locale->categories[LC_COLLATE].collate;
1504   int mbact[nrules];
1505   int wcact;
1506   int mbseqact;
1507   int wcseqact;
1508   struct element_t *runp;
1509   int i;
1510   int need_undefined = 0;
1511   struct section_list *sect;
1512   int ruleidx;
1513   int nr_wide_elems = 0;
1514
1515   if (collate == NULL)
1516     {
1517       /* No data, no check.  */
1518       if (! be_quiet)
1519         error (0, 0, _("No definition for %s category found"), "LC_COLLATE");
1520       return;
1521     }
1522
1523   /* If this assertion is hit change the type in `element_t'.  */
1524   assert (nrules <= sizeof (runp->used_in_level) * 8);
1525
1526   /* Make sure that the `position' rule is used either in all sections
1527      or in none.  */
1528   for (i = 0; i < nrules; ++i)
1529     for (sect = collate->sections; sect != NULL; sect = sect->next)
1530       if (sect->rules != NULL
1531           && ((sect->rules[i] & sort_position)
1532               != (collate->sections->rules[i] & sort_position)))
1533         {
1534           error (0, 0, _("\
1535 %s: `position' must be used for a specific level in all sections or none"),
1536                  "LC_COLLATE");
1537           break;
1538         }
1539
1540   /* Find out which elements are used at which level.  At the same
1541      time we find out whether we have any undefined symbols.  */
1542   runp = collate->start;
1543   while (runp != NULL)
1544     {
1545       if (runp->mbs != NULL)
1546         {
1547           for (i = 0; i < nrules; ++i)
1548             {
1549               int j;
1550
1551               for (j = 0; j < runp->weights[i].cnt; ++j)
1552                 /* A NULL pointer as the weight means IGNORE.  */
1553                 if (runp->weights[i].w[j] != NULL)
1554                   {
1555                     if (runp->weights[i].w[j]->weights == NULL)
1556                       {
1557                         error_at_line (0, 0, runp->file, runp->line,
1558                                        _("symbol `%s' not defined"),
1559                                        runp->weights[i].w[j]->name);
1560
1561                         need_undefined = 1;
1562                         runp->weights[i].w[j] = &collate->undefined;
1563                       }
1564                     else
1565                       /* Set the bit for the level.  */
1566                       runp->weights[i].w[j]->used_in_level |= 1 << i;
1567                   }
1568             }
1569         }
1570
1571       /* Up to the next entry.  */
1572       runp = runp->next;
1573     }
1574
1575   /* Walk through the list of defined sequences and assign weights.  Also
1576      create the data structure which will allow generating the single byte
1577      character based tables.
1578
1579      Since at each time only the weights for each of the rules are
1580      only compared to other weights for this rule it is possible to
1581      assign more compact weight values than simply counting all
1582      weights in sequence.  We can assign weights from 3, one for each
1583      rule individually and only for those elements, which are actually
1584      used for this rule.
1585
1586      Why is this important?  It is not for the wide char table.  But
1587      it is for the singlebyte output since here larger numbers have to
1588      be encoded to make it possible to emit the value as a byte
1589      string.  */
1590   for (i = 0; i < nrules; ++i)
1591     mbact[i] = 2;
1592   wcact = 2;
1593   mbseqact = 0;
1594   wcseqact = 0;
1595   runp = collate->start;
1596   while (runp != NULL)
1597     {
1598       /* Determine the order.  */
1599       if (runp->used_in_level != 0)
1600         {
1601           runp->mborder = (int *) obstack_alloc (&collate->mempool,
1602                                                  nrules * sizeof (int));
1603
1604           for (i = 0; i < nrules; ++i)
1605             if ((runp->used_in_level & (1 << i)) != 0)
1606               runp->mborder[i] = mbact[i]++;
1607             else
1608               runp->mborder[i] = 0;
1609         }
1610
1611       if (runp->mbs != NULL)
1612         {
1613           struct element_t **eptr;
1614           struct element_t *lastp = NULL;
1615
1616           /* Find the point where to insert in the list.  */
1617           eptr = &collate->mbheads[((unsigned char *) runp->mbs)[0]];
1618           while (*eptr != NULL)
1619             {
1620               if ((*eptr)->nmbs < runp->nmbs)
1621                 break;
1622
1623               if ((*eptr)->nmbs == runp->nmbs)
1624                 {
1625                   int c = memcmp ((*eptr)->mbs, runp->mbs, runp->nmbs);
1626
1627                   if (c == 0)
1628                     {
1629                       /* This should not happen.  It means that we have
1630                          to symbols with the same byte sequence.  It is
1631                          of course an error.  */
1632                       error_at_line (0, 0, (*eptr)->file, (*eptr)->line,
1633                                      _("symbol `%s' has the same encoding as"),
1634                                      (*eptr)->name);
1635                       error_at_line (0, 0, runp->file, runp->line,
1636                                      _("symbol `%s'"), runp->name);
1637                       goto dont_insert;
1638                     }
1639                   else if (c < 0)
1640                     /* Insert it here.  */
1641                     break;
1642                 }
1643
1644               /* To the next entry.  */
1645               lastp = *eptr;
1646               eptr = &(*eptr)->mbnext;
1647             }
1648
1649           /* Set the pointers.  */
1650           runp->mbnext = *eptr;
1651           runp->mblast = lastp;
1652           if (*eptr != NULL)
1653             (*eptr)->mblast = runp;
1654           *eptr = runp;
1655         dont_insert:
1656           ;
1657         }
1658
1659       if (runp->used_in_level)
1660         {
1661           runp->wcorder = wcact++;
1662
1663           /* We take the opportunity to count the elements which have
1664              wide characters.  */
1665           ++nr_wide_elems;
1666         }
1667
1668       if (runp->is_character)
1669         {
1670           if (runp->nmbs == 1)
1671             collate->mbseqorder[((unsigned char *) runp->mbs)[0]] = mbseqact++;
1672
1673           runp->wcseqorder = wcseqact++;
1674         }
1675
1676       /* Up to the next entry.  */
1677       runp = runp->next;
1678     }
1679
1680   /* Find out whether any of the `mbheads' entries is unset.  In this
1681      case we use the UNDEFINED entry.  */
1682   for (i = 1; i < 256; ++i)
1683     if (collate->mbheads[i] == NULL)
1684       {
1685         need_undefined = 1;
1686         collate->mbheads[i] = &collate->undefined;
1687       }
1688
1689   /* Now to the wide character case.  */
1690   collate->wcheads.p = 6;
1691   collate->wcheads.q = 10;
1692   wchead_table_init (&collate->wcheads);
1693
1694   collate->wcseqorder.p = 6;
1695   collate->wcseqorder.q = 10;
1696   collseq_table_init (&collate->wcseqorder);
1697
1698   /* Start adding.  */
1699   runp = collate->start;
1700   while (runp != NULL)
1701     {
1702       if (runp->wcs != NULL)
1703         {
1704           struct element_t *e;
1705           struct element_t **eptr;
1706           struct element_t *lastp;
1707
1708           /* Insert the collation sequence value.  */
1709           collseq_table_add (&collate->wcseqorder, runp->wcs[0],
1710                              runp->wcseqorder);
1711
1712           /* Find the point where to insert in the list.  */
1713           e = wchead_table_get (&collate->wcheads, runp->wcs[0]);
1714           eptr = &e;
1715           lastp = NULL;
1716           while (*eptr != NULL)
1717             {
1718               if ((*eptr)->nwcs < runp->nwcs)
1719                 break;
1720
1721               if ((*eptr)->nwcs == runp->nwcs)
1722                 {
1723                   int c = wmemcmp ((wchar_t *) (*eptr)->wcs,
1724                                    (wchar_t *) runp->wcs, runp->nwcs);
1725
1726                   if (c == 0)
1727                     {
1728                       /* This should not happen.  It means that we have
1729                          two symbols with the same byte sequence.  It is
1730                          of course an error.  */
1731                       error_at_line (0, 0, (*eptr)->file, (*eptr)->line,
1732                                      _("symbol `%s' has the same encoding as"),
1733                                      (*eptr)->name);
1734                       error_at_line (0, 0, runp->file, runp->line,
1735                                      _("symbol `%s'"), runp->name);
1736                       goto dont_insertwc;
1737                     }
1738                   else if (c < 0)
1739                     /* Insert it here.  */
1740                     break;
1741                 }
1742
1743               /* To the next entry.  */
1744               lastp = *eptr;
1745               eptr = &(*eptr)->wcnext;
1746             }
1747
1748           /* Set the pointers.  */
1749           runp->wcnext = *eptr;
1750           runp->wclast = lastp;
1751           if (*eptr != NULL)
1752             (*eptr)->wclast = runp;
1753           *eptr = runp;
1754           if (eptr == &e)
1755             wchead_table_add (&collate->wcheads, runp->wcs[0], e);
1756         dont_insertwc:
1757           ;
1758         }
1759
1760       /* Up to the next entry.  */
1761       runp = runp->next;
1762     }
1763
1764   collseq_table_finalize (&collate->wcseqorder);
1765
1766   /* Now determine whether the UNDEFINED entry is needed and if yes,
1767      whether it was defined.  */
1768   collate->undefined.used_in_level = need_undefined ? ~0ul : 0;
1769   if (collate->undefined.file == NULL)
1770     {
1771       if (need_undefined)
1772         {
1773           /* This seems not to be enforced by recent standards.  Don't
1774              emit an error, simply append UNDEFINED at the end.  */
1775           if (0)
1776             error (0, 0, _("no definition of `UNDEFINED'"));
1777
1778           /* Add UNDEFINED at the end.  */
1779           collate->undefined.mborder =
1780             (int *) obstack_alloc (&collate->mempool, nrules * sizeof (int));
1781
1782           for (i = 0; i < nrules; ++i)
1783             collate->undefined.mborder[i] = mbact[i]++;
1784         }
1785
1786       /* In any case we will need the definition for the wide character
1787          case.  But we will not complain that it is missing since the
1788          specification strangely enough does not seem to account for
1789          this.  */
1790       collate->undefined.wcorder = wcact++;
1791     }
1792
1793   /* Finally, try to unify the rules for the sections.  Whenever the rules
1794      for a section are the same as those for another section give the
1795      ruleset the same index.  Since there are never many section we can
1796      use an O(n^2) algorithm here.  */
1797   sect = collate->sections;
1798   while (sect != NULL && sect->rules == NULL)
1799     sect = sect->next;
1800   assert (sect != NULL);
1801   ruleidx = 0;
1802   do
1803     {
1804       struct section_list *osect = collate->sections;
1805
1806       while (osect != sect)
1807         if (osect->rules != NULL
1808             && memcmp (osect->rules, sect->rules, nrules) == 0)
1809           break;
1810         else
1811           osect = osect->next;
1812
1813       if (osect == sect)
1814         sect->ruleidx = ruleidx++;
1815       else
1816         sect->ruleidx = osect->ruleidx;
1817
1818       /* Next section.  */
1819       do
1820         sect = sect->next;
1821       while (sect != NULL && sect->rules == NULL);
1822     }
1823   while (sect != NULL);
1824   /* We are currently not prepared for more than 128 rulesets.  But this
1825      should never really be a problem.  */
1826   assert (ruleidx <= 128);
1827 }
1828
1829
1830 static int32_t
1831 output_weight (struct obstack *pool, struct locale_collate_t *collate,
1832                struct element_t *elem)
1833 {
1834   size_t cnt;
1835   int32_t retval;
1836
1837   /* Optimize the use of UNDEFINED.  */
1838   if (elem == &collate->undefined)
1839     /* The weights are already inserted.  */
1840     return 0;
1841
1842   /* This byte can start exactly one collation element and this is
1843      a single byte.  We can directly give the index to the weights.  */
1844   retval = obstack_object_size (pool);
1845
1846   /* Construct the weight.  */
1847   for (cnt = 0; cnt < nrules; ++cnt)
1848     {
1849       char buf[elem->weights[cnt].cnt * 7];
1850       int len = 0;
1851       int i;
1852
1853       for (i = 0; i < elem->weights[cnt].cnt; ++i)
1854         /* Encode the weight value.  We do nothing for IGNORE entries.  */
1855         if (elem->weights[cnt].w[i] != NULL)
1856           len += utf8_encode (&buf[len],
1857                               elem->weights[cnt].w[i]->mborder[cnt]);
1858
1859       /* And add the buffer content.  */
1860       obstack_1grow (pool, len);
1861       obstack_grow (pool, buf, len);
1862     }
1863
1864   return retval | ((elem->section->ruleidx & 0x7f) << 24);
1865 }
1866
1867
1868 static int32_t
1869 output_weightwc (struct obstack *pool, struct locale_collate_t *collate,
1870                  struct element_t *elem)
1871 {
1872   size_t cnt;
1873   int32_t retval;
1874
1875   /* Optimize the use of UNDEFINED.  */
1876   if (elem == &collate->undefined)
1877     /* The weights are already inserted.  */
1878     return 0;
1879
1880   /* This byte can start exactly one collation element and this is
1881      a single byte.  We can directly give the index to the weights.  */
1882   retval = obstack_object_size (pool) / sizeof (int32_t);
1883
1884   /* Construct the weight.  */
1885   for (cnt = 0; cnt < nrules; ++cnt)
1886     {
1887       int32_t buf[elem->weights[cnt].cnt];
1888       int i;
1889       int32_t j;
1890
1891       for (i = 0, j = 0; i < elem->weights[cnt].cnt; ++i)
1892         if (elem->weights[cnt].w[i] != NULL)
1893           buf[j++] = elem->weights[cnt].w[i]->wcorder;
1894
1895       /* And add the buffer content.  */
1896       obstack_int32_grow (pool, j);
1897
1898       obstack_grow (pool, buf, j * sizeof (int32_t));
1899     }
1900
1901   return retval | ((elem->section->ruleidx & 0x7f) << 24);
1902 }
1903
1904
1905 void
1906 collate_output (struct localedef_t *locale, const struct charmap_t *charmap,
1907                 const char *output_path)
1908 {
1909   struct locale_collate_t *collate = locale->categories[LC_COLLATE].collate;
1910   const size_t nelems = _NL_ITEM_INDEX (_NL_NUM_LC_COLLATE);
1911   struct iovec iov[2 + nelems];
1912   struct locale_file data;
1913   uint32_t idx[nelems];
1914   size_t cnt;
1915   size_t ch;
1916   int32_t tablemb[256];
1917   struct obstack weightpool;
1918   struct obstack extrapool;
1919   struct obstack indirectpool;
1920   struct section_list *sect;
1921   struct collidx_table tablewc;
1922   uint32_t elem_size;
1923   uint32_t *elem_table;
1924   int i;
1925   struct element_t *runp;
1926
1927   data.magic = LIMAGIC (LC_COLLATE);
1928   data.n = nelems;
1929   iov[0].iov_base = (void *) &data;
1930   iov[0].iov_len = sizeof (data);
1931
1932   iov[1].iov_base = (void *) idx;
1933   iov[1].iov_len = sizeof (idx);
1934
1935   idx[0] = iov[0].iov_len + iov[1].iov_len;
1936   cnt = 0;
1937
1938   assert (cnt == _NL_ITEM_INDEX (_NL_COLLATE_NRULES));
1939   iov[2 + cnt].iov_base = &nrules;
1940   iov[2 + cnt].iov_len = sizeof (uint32_t);
1941   idx[1 + cnt] = idx[cnt] + iov[2 + cnt].iov_len;
1942   ++cnt;
1943
1944   /* If we have no LC_COLLATE data emit only the number of rules as zero.  */
1945   if (collate == NULL)
1946     {
1947       int32_t dummy = 0;
1948
1949       while (cnt < _NL_ITEM_INDEX (_NL_NUM_LC_COLLATE))
1950         {
1951           /* The words have to be handled specially.  */
1952           if (cnt == _NL_ITEM_INDEX (_NL_COLLATE_SYMB_HASH_SIZEMB))
1953             {
1954               iov[2 + cnt].iov_base = &dummy;
1955               iov[2 + cnt].iov_len = sizeof (int32_t);
1956             }
1957           else
1958             {
1959               iov[2 + cnt].iov_base = NULL;
1960               iov[2 + cnt].iov_len = 0;
1961             }
1962
1963           if (cnt + 1 < _NL_ITEM_INDEX (_NL_NUM_LC_COLLATE))
1964             idx[1 + cnt] = idx[cnt] + iov[2 + cnt].iov_len;
1965           ++cnt;
1966         }
1967
1968       assert (cnt == _NL_ITEM_INDEX (_NL_NUM_LC_COLLATE));
1969
1970       write_locale_data (output_path, "LC_COLLATE", 2 + cnt, iov);
1971
1972       return;
1973     }
1974
1975   obstack_init (&weightpool);
1976   obstack_init (&extrapool);
1977   obstack_init (&indirectpool);
1978
1979   /* Since we are using the sign of an integer to mark indirection the
1980      offsets in the arrays we are indirectly referring to must not be
1981      zero since -0 == 0.  Therefore we add a bit of dummy content.  */
1982   obstack_int32_grow (&extrapool, 0);
1983   obstack_int32_grow (&indirectpool, 0);
1984
1985   /* Prepare the ruleset table.  */
1986   for (sect = collate->sections, i = 0; sect != NULL; sect = sect->next)
1987     if (sect->rules != NULL && sect->ruleidx == i)
1988       {
1989         int j;
1990
1991         obstack_make_room (&weightpool, nrules);
1992
1993         for (j = 0; j < nrules; ++j)
1994           obstack_1grow_fast (&weightpool, sect->rules[j]);
1995         ++i;
1996       }
1997   /* And align the output.  */
1998   i = (nrules * i) % __alignof__ (int32_t);
1999   if (i > 0)
2000     do
2001       obstack_1grow (&weightpool, '\0');
2002     while (++i < __alignof__ (int32_t));
2003
2004   assert (cnt == _NL_ITEM_INDEX (_NL_COLLATE_RULESETS));
2005   iov[2 + cnt].iov_len = obstack_object_size (&weightpool);
2006   iov[2 + cnt].iov_base = obstack_finish (&weightpool);
2007   idx[1 + cnt] = idx[cnt] + iov[2 + cnt].iov_len;
2008   ++cnt;
2009
2010   /* Generate the 8-bit table.  Walk through the lists of sequences
2011      starting with the same byte and add them one after the other to
2012      the table.  In case we have more than one sequence starting with
2013      the same byte we have to use extra indirection.
2014
2015      First add a record for the NUL byte.  This entry will never be used
2016      so it does not matter.  */
2017   tablemb[0] = 0;
2018
2019   /* Now insert the `UNDEFINED' value if it is used.  Since this value
2020      will probably be used more than once it is good to store the
2021      weights only once.  */
2022   if (collate->undefined.used_in_level != 0)
2023     output_weight (&weightpool, collate, &collate->undefined);
2024
2025   for (ch = 1; ch < 256; ++ch)
2026     if (collate->mbheads[ch]->mbnext == NULL
2027         && collate->mbheads[ch]->nmbs <= 1)
2028       {
2029         tablemb[ch] = output_weight (&weightpool, collate,
2030                                      collate->mbheads[ch]);
2031       }
2032     else
2033       {
2034         /* The entries in the list are sorted by length and then
2035            alphabetically.  This is the order in which we will add the
2036            elements to the collation table.  This allows simply walking
2037            the table in sequence and stopping at the first matching
2038            entry.  Since the longer sequences are coming first in the
2039            list they have the possibility to match first, just as it
2040            has to be.  In the worst case we are walking to the end of
2041            the list where we put, if no singlebyte sequence is defined
2042            in the locale definition, the weights for UNDEFINED.
2043
2044            To reduce the length of the search list we compress them a bit.
2045            This happens by collecting sequences of consecutive byte
2046            sequences in one entry (having and begin and end byte sequence)
2047            and add only one index into the weight table.  We can find the
2048            consecutive entries since they are also consecutive in the list.  */
2049         struct element_t *runp = collate->mbheads[ch];
2050         struct element_t *lastp;
2051
2052         assert ((obstack_object_size (&extrapool)
2053                  & (__alignof__ (int32_t) - 1)) == 0);
2054
2055         tablemb[ch] = -obstack_object_size (&extrapool);
2056
2057         do
2058           {
2059             /* Store the current index in the weight table.  We know that
2060                the current position in the `extrapool' is aligned on a
2061                32-bit address.  */
2062             int32_t weightidx;
2063             int added;
2064
2065             /* Find out wether this is a single entry or we have more than
2066                one consecutive entry.  */
2067             if (runp->mbnext != NULL
2068                 && runp->nmbs == runp->mbnext->nmbs
2069                 && memcmp (runp->mbs, runp->mbnext->mbs, runp->nmbs - 1) == 0
2070                 && (runp->mbs[runp->nmbs - 1]
2071                     == runp->mbnext->mbs[runp->nmbs - 1] + 1))
2072               {
2073                 int i;
2074                 struct element_t *series_startp = runp;
2075                 struct element_t *curp;
2076
2077                 /* Compute how much space we will need.  */
2078                 added = ((sizeof (int32_t) + 1 + 2 * (runp->nmbs - 1)
2079                           + __alignof__ (int32_t) - 1)
2080                          & ~(__alignof__ (int32_t) - 1));
2081                 assert ((obstack_object_size (&extrapool)
2082                          & (__alignof__ (int32_t) - 1)) == 0);
2083                 obstack_make_room (&extrapool, added);
2084
2085                 /* More than one consecutive entry.  We mark this by having
2086                    a negative index into the indirect table.  */
2087                 obstack_int32_grow_fast (&extrapool,
2088                                          -(obstack_object_size (&indirectpool)
2089                                            / sizeof (int32_t)));
2090
2091                 /* Now search first the end of the series.  */
2092                 do
2093                   runp = runp->mbnext;
2094                 while (runp->mbnext != NULL
2095                        && runp->nmbs == runp->mbnext->nmbs
2096                        && memcmp (runp->mbs, runp->mbnext->mbs,
2097                                   runp->nmbs - 1) == 0
2098                        && (runp->mbs[runp->nmbs - 1]
2099                            == runp->mbnext->mbs[runp->nmbs - 1] + 1));
2100
2101                 /* Now walk backward from here to the beginning.  */
2102                 curp = runp;
2103
2104                 assert (runp->nmbs <= 256);
2105                 obstack_1grow_fast (&extrapool, curp->nmbs - 1);
2106                 for (i = 1; i < curp->nmbs; ++i)
2107                   obstack_1grow_fast (&extrapool, curp->mbs[i]);
2108
2109                 /* Now find the end of the consecutive sequence and
2110                    add all the indeces in the indirect pool.  */
2111                 do
2112                   {
2113                     weightidx = output_weight (&weightpool, collate, curp);
2114                     obstack_int32_grow (&indirectpool, weightidx);
2115
2116                     curp = curp->mblast;
2117                   }
2118                 while (curp != series_startp);
2119
2120                 /* Add the final weight.  */
2121                 weightidx = output_weight (&weightpool, collate, curp);
2122                 obstack_int32_grow (&indirectpool, weightidx);
2123
2124                 /* And add the end byte sequence.  Without length this
2125                    time.  */
2126                 for (i = 1; i < curp->nmbs; ++i)
2127                   obstack_1grow_fast (&extrapool, curp->mbs[i]);
2128               }
2129             else
2130               {
2131                 /* A single entry.  Simply add the index and the length and
2132                    string (except for the first character which is already
2133                    tested for).  */
2134                 int i;
2135
2136                 /* Output the weight info.  */
2137                 weightidx = output_weight (&weightpool, collate, runp);
2138
2139                 added = ((sizeof (int32_t) + 1 + runp->nmbs - 1
2140                           + __alignof__ (int32_t) - 1)
2141                          & ~(__alignof__ (int32_t) - 1));
2142                 assert ((obstack_object_size (&extrapool)
2143                          & (__alignof__ (int32_t) - 1)) == 0);
2144                 obstack_make_room (&extrapool, added);
2145
2146                 obstack_int32_grow_fast (&extrapool, weightidx);
2147                 assert (runp->nmbs <= 256);
2148                 obstack_1grow_fast (&extrapool, runp->nmbs - 1);
2149
2150                 for (i = 1; i < runp->nmbs; ++i)
2151                   obstack_1grow_fast (&extrapool, runp->mbs[i]);
2152               }
2153
2154             /* Add alignment bytes if necessary.  */
2155             while ((obstack_object_size (&extrapool)
2156                     & (__alignof__ (int32_t) - 1)) != 0)
2157               obstack_1grow_fast (&extrapool, '\0');
2158
2159             /* Next entry.  */
2160             lastp = runp;
2161             runp = runp->mbnext;
2162           }
2163         while (runp != NULL);
2164
2165         assert ((obstack_object_size (&extrapool)
2166                  & (__alignof__ (int32_t) - 1)) == 0);
2167
2168         /* If the final entry in the list is not a single character we
2169            add an UNDEFINED entry here.  */
2170         if (lastp->nmbs != 1)
2171           {
2172             int added = ((sizeof (int32_t) + 1 + 1 + __alignof__ (int32_t) - 1)
2173                          & ~(__alignof__ (int32_t) - 1));
2174             obstack_make_room (&extrapool, added);
2175
2176             obstack_int32_grow_fast (&extrapool, 0);
2177             /* XXX What rule? We just pick the first.  */
2178             obstack_1grow_fast (&extrapool, 0);
2179             /* Length is zero.  */
2180             obstack_1grow_fast (&extrapool, 0);
2181
2182             /* Add alignment bytes if necessary.  */
2183             while ((obstack_object_size (&extrapool)
2184                     & (__alignof__ (int32_t) - 1)) != 0)
2185               obstack_1grow_fast (&extrapool, '\0');
2186           }
2187       }
2188
2189   /* Add padding to the tables if necessary.  */
2190   while ((obstack_object_size (&weightpool) & (__alignof__ (int32_t) - 1))
2191          != 0)
2192     obstack_1grow (&weightpool, 0);
2193
2194   /* Now add the four tables.  */
2195   assert (cnt == _NL_ITEM_INDEX (_NL_COLLATE_TABLEMB));
2196   iov[2 + cnt].iov_base = tablemb;
2197   iov[2 + cnt].iov_len = sizeof (tablemb);
2198   idx[1 + cnt] = idx[cnt] + iov[2 + cnt].iov_len;
2199   assert ((iov[2 + cnt].iov_len & (__alignof__ (int32_t) - 1)) == 0);
2200   ++cnt;
2201
2202   assert (cnt == _NL_ITEM_INDEX (_NL_COLLATE_WEIGHTMB));
2203   iov[2 + cnt].iov_len = obstack_object_size (&weightpool);
2204   iov[2 + cnt].iov_base = obstack_finish (&weightpool);
2205   idx[1 + cnt] = idx[cnt] + iov[2 + cnt].iov_len;
2206   ++cnt;
2207
2208   assert (cnt == _NL_ITEM_INDEX (_NL_COLLATE_EXTRAMB));
2209   iov[2 + cnt].iov_len = obstack_object_size (&extrapool);
2210   iov[2 + cnt].iov_base = obstack_finish (&extrapool);
2211   idx[1 + cnt] = idx[cnt] + iov[2 + cnt].iov_len;
2212   ++cnt;
2213
2214   assert (cnt == _NL_ITEM_INDEX (_NL_COLLATE_INDIRECTMB));
2215   iov[2 + cnt].iov_len = obstack_object_size (&indirectpool);
2216   iov[2 + cnt].iov_base = obstack_finish (&indirectpool);
2217   idx[1 + cnt] = idx[cnt] + iov[2 + cnt].iov_len;
2218   assert ((iov[2 + cnt].iov_len & (__alignof__ (int32_t) - 1)) == 0);
2219   ++cnt;
2220
2221
2222   /* Now the same for the wide character table.  We need to store some
2223      more information here.  */
2224   assert (cnt == _NL_ITEM_INDEX (_NL_COLLATE_GAP1));
2225   iov[2 + cnt].iov_base = NULL;
2226   iov[2 + cnt].iov_len = 0;
2227   idx[1 + cnt] = idx[cnt] + iov[2 + cnt].iov_len;
2228   assert (idx[cnt] % __alignof__ (int32_t) == 0);
2229   ++cnt;
2230
2231   assert (cnt == _NL_ITEM_INDEX (_NL_COLLATE_GAP2));
2232   iov[2 + cnt].iov_base = NULL;
2233   iov[2 + cnt].iov_len = 0;
2234   idx[1 + cnt] = idx[cnt] + iov[2 + cnt].iov_len;
2235   assert (idx[cnt] % __alignof__ (int32_t) == 0);
2236   ++cnt;
2237
2238   assert (cnt == _NL_ITEM_INDEX (_NL_COLLATE_GAP3));
2239   iov[2 + cnt].iov_base = NULL;
2240   iov[2 + cnt].iov_len = 0;
2241   idx[1 + cnt] = idx[cnt] + iov[2 + cnt].iov_len;
2242   assert (idx[cnt] % __alignof__ (int32_t) == 0);
2243   ++cnt;
2244
2245   /* Since we are using the sign of an integer to mark indirection the
2246      offsets in the arrays we are indirectly referring to must not be
2247      zero since -0 == 0.  Therefore we add a bit of dummy content.  */
2248   obstack_int32_grow (&extrapool, 0);
2249   obstack_int32_grow (&indirectpool, 0);
2250
2251   /* Now insert the `UNDEFINED' value if it is used.  Since this value
2252      will probably be used more than once it is good to store the
2253      weights only once.  */
2254   if (output_weightwc (&weightpool, collate, &collate->undefined) != 0)
2255     abort ();
2256
2257   /* Generate the table.  Walk through the lists of sequences starting
2258      with the same wide character and add them one after the other to
2259      the table.  In case we have more than one sequence starting with
2260      the same byte we have to use extra indirection.  */
2261   {
2262     auto void add_to_tablewc (uint32_t ch, struct element_t *runp);
2263
2264     void add_to_tablewc (uint32_t ch, struct element_t *runp)
2265       {
2266         if (runp->wcnext == NULL && runp->nwcs == 1)
2267           {
2268             int32_t weigthidx = output_weightwc (&weightpool, collate, runp);
2269             collidx_table_add (&tablewc, ch, weigthidx);
2270           }
2271         else
2272           {
2273             /* As for the singlebyte table, we recognize sequences and
2274                compress them.  */
2275             struct element_t *lastp;
2276
2277             collidx_table_add (&tablewc, ch,
2278                                -(obstack_object_size (&extrapool) / sizeof (uint32_t)));
2279
2280             do
2281               {
2282                 /* Store the current index in the weight table.  We know that
2283                    the current position in the `extrapool' is aligned on a
2284                    32-bit address.  */
2285                 int32_t weightidx;
2286                 int added;
2287
2288                 /* Find out wether this is a single entry or we have more than
2289                    one consecutive entry.  */
2290                 if (runp->wcnext != NULL
2291                     && runp->nwcs == runp->wcnext->nwcs
2292                     && wmemcmp ((wchar_t *) runp->wcs,
2293                                 (wchar_t *)runp->wcnext->wcs,
2294                                 runp->nwcs - 1) == 0
2295                     && (runp->wcs[runp->nwcs - 1]
2296                         == runp->wcnext->wcs[runp->nwcs - 1] + 1))
2297                   {
2298                     int i;
2299                     struct element_t *series_startp = runp;
2300                     struct element_t *curp;
2301
2302                     /* Now add first the initial byte sequence.  */
2303                     added = (1 + 1 + 2 * (runp->nwcs - 1)) * sizeof (int32_t);
2304                     if (sizeof (int32_t) == sizeof (int))
2305                       obstack_make_room (&extrapool, added);
2306
2307                     /* More than one consecutive entry.  We mark this by having
2308                        a negative index into the indirect table.  */
2309                     obstack_int32_grow_fast (&extrapool,
2310                                              -(obstack_object_size (&indirectpool)
2311                                                / sizeof (int32_t)));
2312                     obstack_int32_grow_fast (&extrapool, runp->nwcs - 1);
2313
2314                     do
2315                       runp = runp->wcnext;
2316                     while (runp->wcnext != NULL
2317                            && runp->nwcs == runp->wcnext->nwcs
2318                            && wmemcmp ((wchar_t *) runp->wcs,
2319                                        (wchar_t *)runp->wcnext->wcs,
2320                                        runp->nwcs - 1) == 0
2321                            && (runp->wcs[runp->nwcs - 1]
2322                                == runp->wcnext->wcs[runp->nwcs - 1] + 1));
2323
2324                     /* Now walk backward from here to the beginning.  */
2325                     curp = runp;
2326
2327                     for (i = 1; i < runp->nwcs; ++i)
2328                       obstack_int32_grow_fast (&extrapool, curp->wcs[i]);
2329
2330                     /* Now find the end of the consecutive sequence and
2331                        add all the indeces in the indirect pool.  */
2332                     do
2333                       {
2334                         weightidx = output_weightwc (&weightpool, collate,
2335                                                      curp);
2336                         obstack_int32_grow (&indirectpool, weightidx);
2337
2338                         curp = curp->wclast;
2339                       }
2340                     while (curp != series_startp);
2341
2342                     /* Add the final weight.  */
2343                     weightidx = output_weightwc (&weightpool, collate, curp);
2344                     obstack_int32_grow (&indirectpool, weightidx);
2345
2346                     /* And add the end byte sequence.  Without length this
2347                        time.  */
2348                     for (i = 1; i < curp->nwcs; ++i)
2349                       obstack_int32_grow (&extrapool, curp->wcs[i]);
2350                   }
2351                 else
2352                   {
2353                     /* A single entry.  Simply add the index and the length and
2354                        string (except for the first character which is already
2355                        tested for).  */
2356                     int i;
2357
2358                     /* Output the weight info.  */
2359                     weightidx = output_weightwc (&weightpool, collate, runp);
2360
2361                     added = (1 + 1 + runp->nwcs - 1) * sizeof (int32_t);
2362                     if (sizeof (int) == sizeof (int32_t))
2363                       obstack_make_room (&extrapool, added);
2364
2365                     obstack_int32_grow_fast (&extrapool, weightidx);
2366                     obstack_int32_grow_fast (&extrapool, runp->nwcs - 1);
2367                     for (i = 1; i < runp->nwcs; ++i)
2368                       obstack_int32_grow_fast (&extrapool, runp->wcs[i]);
2369                   }
2370
2371                 /* Next entry.  */
2372                 lastp = runp;
2373                 runp = runp->wcnext;
2374               }
2375             while (runp != NULL);
2376           }
2377       }
2378
2379     tablewc.p = 6;
2380     tablewc.q = 10;
2381     collidx_table_init (&tablewc);
2382
2383     wchead_table_iterate (&collate->wcheads, add_to_tablewc);
2384
2385     collidx_table_finalize (&tablewc);
2386   }
2387
2388   /* Now add the four tables.  */
2389   assert (cnt == _NL_ITEM_INDEX (_NL_COLLATE_TABLEWC));
2390   iov[2 + cnt].iov_base = tablewc.result;
2391   iov[2 + cnt].iov_len = tablewc.result_size;
2392   idx[1 + cnt] = idx[cnt] + iov[2 + cnt].iov_len;
2393   assert (iov[2 + cnt].iov_len % sizeof (int32_t) == 0);
2394   assert (idx[cnt] % __alignof__ (int32_t) == 0);
2395   ++cnt;
2396
2397   assert (cnt == _NL_ITEM_INDEX (_NL_COLLATE_WEIGHTWC));
2398   iov[2 + cnt].iov_len = obstack_object_size (&weightpool);
2399   iov[2 + cnt].iov_base = obstack_finish (&weightpool);
2400   idx[1 + cnt] = idx[cnt] + iov[2 + cnt].iov_len;
2401   assert (iov[2 + cnt].iov_len % sizeof (int32_t) == 0);
2402   assert (idx[cnt] % __alignof__ (int32_t) == 0);
2403   ++cnt;
2404
2405   assert (cnt == _NL_ITEM_INDEX (_NL_COLLATE_EXTRAWC));
2406   iov[2 + cnt].iov_len = obstack_object_size (&extrapool);
2407   iov[2 + cnt].iov_base = obstack_finish (&extrapool);
2408   idx[1 + cnt] = idx[cnt] + iov[2 + cnt].iov_len;
2409   assert (iov[2 + cnt].iov_len % sizeof (int32_t) == 0);
2410   assert (idx[cnt] % __alignof__ (int32_t) == 0);
2411   ++cnt;
2412
2413   assert (cnt == _NL_ITEM_INDEX (_NL_COLLATE_INDIRECTWC));
2414   iov[2 + cnt].iov_len = obstack_object_size (&indirectpool);
2415   iov[2 + cnt].iov_base = obstack_finish (&indirectpool);
2416   idx[1 + cnt] = idx[cnt] + iov[2 + cnt].iov_len;
2417   assert (iov[2 + cnt].iov_len % sizeof (int32_t) == 0);
2418   assert (idx[cnt] % __alignof__ (int32_t) == 0);
2419   ++cnt;
2420
2421
2422   /* Finally write the table with collation element names out.  It is
2423      a hash table with a simple function which gets the name of the
2424      character as the input.  One character might have many names.  The
2425      value associated with the name is an index into the weight table
2426      where we are then interested in the first-level weight value.
2427
2428      To determine how large the table should be we are counting the
2429      elements have to put in.  Since we are using internal chaining
2430      using a secondary hash function we have to make the table a bit
2431      larger to avoid extremely long search times.  We can achieve
2432      good results with a 40% larger table than there are entries.  */
2433   elem_size = 0;
2434   runp = collate->start;
2435   while (runp != NULL)
2436     {
2437       if (runp->mbs != NULL && runp->weights != NULL)
2438         /* Yep, the element really counts.  */
2439         ++elem_size;
2440
2441       runp = runp->next;
2442     }
2443   /* Add 40% and find the next prime number.  */
2444   elem_size = MIN (next_prime (elem_size * 1.4), 257);
2445
2446   /* Allocate the table.  Each entry consists of two words: the hash
2447      value and an index in a secondary table which provides the index
2448      into the weight table and the string itself (so that a match can
2449      be determined).  */
2450   elem_table = (uint32_t *) obstack_alloc (&extrapool,
2451                                            elem_size * 2 * sizeof (uint32_t));
2452   memset (elem_table, '\0', elem_size * 2 * sizeof (uint32_t));
2453
2454   /* Now add the elements.  */
2455   runp = collate->start;
2456   while (runp != NULL)
2457     {
2458       if (runp->mbs != NULL && runp->weights != NULL && !runp->is_character)
2459         {
2460           /* Compute the hash value of the name.  */
2461           uint32_t namelen = strlen (runp->name);
2462           uint32_t hash = elem_hash (runp->name, namelen);
2463           size_t idx = hash % elem_size;
2464
2465           if (elem_table[idx * 2] != 0)
2466             {
2467               /* The spot is already take.  Try iterating using the value
2468                  from the secondary hashing function.  */
2469               size_t iter = hash % (elem_size - 2);
2470
2471               do
2472                 {
2473                   idx += iter;
2474                   if (idx >= elem_size)
2475                     idx -= elem_size;
2476                 }
2477               while (elem_table[idx * 2] != 0);
2478             }
2479           /* This is the spot where we will insert the value.  */
2480           elem_table[idx * 2] = hash;
2481           elem_table[idx * 2 + 1] = obstack_object_size (&extrapool);
2482
2483           /* The the string itself including length.  */
2484           obstack_1grow (&extrapool, namelen);
2485           obstack_grow (&extrapool, runp->name, namelen);
2486
2487           /* And the multibyte representation.  */
2488           obstack_1grow (&extrapool, runp->nmbs);
2489           obstack_grow (&extrapool, runp->mbs, runp->nmbs);
2490
2491           /* And align again to 32 bits.  */
2492           if ((1 + namelen + 1 + runp->nmbs) % sizeof (int32_t) != 0)
2493             obstack_grow (&extrapool, "\0\0",
2494                           (sizeof (int32_t)
2495                            - ((1 + namelen + 1 + runp->nmbs)
2496                               % sizeof (int32_t))));
2497
2498           /* Now some 32-bit values: multibyte collation sequence,
2499              wide char string (including length), and wide char
2500              collation sequence.  */
2501           obstack_int32_grow (&extrapool, runp->mbseqorder);
2502
2503           obstack_int32_grow (&extrapool, runp->nwcs);
2504           obstack_grow (&extrapool, runp->wcs,
2505                         runp->nwcs * sizeof (uint32_t));
2506
2507           obstack_int32_grow (&extrapool, runp->wcseqorder);
2508         }
2509
2510       runp = runp->next;
2511     }
2512
2513   /* Prepare to write out this data.  */
2514   assert (cnt == _NL_ITEM_INDEX (_NL_COLLATE_SYMB_HASH_SIZEMB));
2515   iov[2 + cnt].iov_base = &elem_size;
2516   iov[2 + cnt].iov_len = sizeof (int32_t);
2517   idx[1 + cnt] = idx[cnt] + iov[2 + cnt].iov_len;
2518   assert (idx[cnt] % __alignof__ (int32_t) == 0);
2519   ++cnt;
2520
2521   assert (cnt == _NL_ITEM_INDEX (_NL_COLLATE_SYMB_TABLEMB));
2522   iov[2 + cnt].iov_base = elem_table;
2523   iov[2 + cnt].iov_len = elem_size * 2 * sizeof (int32_t);
2524   idx[1 + cnt] = idx[cnt] + iov[2 + cnt].iov_len;
2525   assert (idx[cnt] % __alignof__ (int32_t) == 0);
2526   ++cnt;
2527
2528   assert (cnt == _NL_ITEM_INDEX (_NL_COLLATE_SYMB_EXTRAMB));
2529   iov[2 + cnt].iov_len = obstack_object_size (&extrapool);
2530   iov[2 + cnt].iov_base = obstack_finish (&extrapool);
2531   idx[1 + cnt] = idx[cnt] + iov[2 + cnt].iov_len;
2532   ++cnt;
2533
2534   assert (cnt == _NL_ITEM_INDEX (_NL_COLLATE_COLLSEQMB));
2535   iov[2 + cnt].iov_base = collate->mbseqorder;
2536   iov[2 + cnt].iov_len = 256;
2537   idx[1 + cnt] = idx[cnt] + iov[2 + cnt].iov_len;
2538   ++cnt;
2539
2540   assert (cnt == _NL_ITEM_INDEX (_NL_COLLATE_COLLSEQWC));
2541   iov[2 + cnt].iov_base = collate->wcseqorder.result;
2542   iov[2 + cnt].iov_len = collate->wcseqorder.result_size;
2543   idx[1 + cnt] = idx[cnt] + iov[2 + cnt].iov_len;
2544   assert (idx[cnt] % __alignof__ (int32_t) == 0);
2545   ++cnt;
2546
2547   assert (cnt == _NL_ITEM_INDEX (_NL_COLLATE_CODESET));
2548   iov[2 + cnt].iov_base = (void *) charmap->code_set_name;
2549   iov[2 + cnt].iov_len = strlen (iov[2 + cnt].iov_base) + 1;
2550   ++cnt;
2551
2552   assert (cnt == _NL_ITEM_INDEX (_NL_NUM_LC_COLLATE));
2553
2554   write_locale_data (output_path, "LC_COLLATE", 2 + cnt, iov);
2555
2556   obstack_free (&weightpool, NULL);
2557   obstack_free (&extrapool, NULL);
2558   obstack_free (&indirectpool, NULL);
2559 }
2560
2561
2562 void
2563 collate_read (struct linereader *ldfile, struct localedef_t *result,
2564               const struct charmap_t *charmap, const char *repertoire_name,
2565               int ignore_content)
2566 {
2567   struct repertoire_t *repertoire = NULL;
2568   struct locale_collate_t *collate;
2569   struct token *now;
2570   struct token *arg = NULL;
2571   enum token_t nowtok;
2572   enum token_t was_ellipsis = tok_none;
2573   struct localedef_t *copy_locale = NULL;
2574   /* Parsing state:
2575      0 - start
2576      1 - between `order-start' and `order-end'
2577      2 - after `order-end'
2578      3 - after `reorder-after', waiting for `reorder-end'
2579      4 - after `reorder-end'
2580      5 - after `reorder-sections-after', waiting for `reorder-sections-end'
2581      6 - after `reorder-sections-end'
2582   */
2583   int state = 0;
2584
2585   /* Get the repertoire we have to use.  */
2586   if (repertoire_name != NULL)
2587     repertoire = repertoire_read (repertoire_name);
2588
2589   /* The rest of the line containing `LC_COLLATE' must be free.  */
2590   lr_ignore_rest (ldfile, 1);
2591
2592   do
2593     {
2594       now = lr_token (ldfile, charmap, result, NULL, verbose);
2595       nowtok = now->tok;
2596     }
2597   while (nowtok == tok_eol);
2598
2599   if (nowtok == tok_copy)
2600     {
2601       state = 2;
2602       now = lr_token (ldfile, charmap, result, NULL, verbose);
2603       if (now->tok != tok_string)
2604         {
2605           SYNTAX_ERROR (_("%s: syntax error"), "LC_COLLATE");
2606
2607         skip_category:
2608           do
2609             now = lr_token (ldfile, charmap, result, NULL, verbose);
2610           while (now->tok != tok_eof && now->tok != tok_end);
2611
2612           if (now->tok != tok_eof
2613               || (now = lr_token (ldfile, charmap, result, NULL, verbose),
2614                   now->tok == tok_eof))
2615             lr_error (ldfile, _("%s: premature end of file"), "LC_COLLATE");
2616           else if (now->tok != tok_lc_collate)
2617             {
2618               lr_error (ldfile, _("\
2619 %1$s: definition does not end with `END %1$s'"), "LC_COLLATE");
2620               lr_ignore_rest (ldfile, 0);
2621             }
2622           else
2623             lr_ignore_rest (ldfile, 1);
2624
2625           return;
2626         }
2627
2628       if (! ignore_content)
2629         {
2630           /* Get the locale definition.  */
2631           copy_locale = load_locale (LC_COLLATE, now->val.str.startmb,
2632                                      repertoire_name, charmap, NULL);
2633           if ((copy_locale->avail & COLLATE_LOCALE) == 0)
2634             {
2635               /* Not yet loaded.  So do it now.  */
2636               if (locfile_read (copy_locale, charmap) != 0)
2637                 goto skip_category;
2638             }
2639         }
2640
2641       lr_ignore_rest (ldfile, 1);
2642
2643       now = lr_token (ldfile, charmap, result, NULL, verbose);
2644       nowtok = now->tok;
2645     }
2646
2647   /* Prepare the data structures.  */
2648   collate_startup (ldfile, result, copy_locale, ignore_content);
2649   collate = result->categories[LC_COLLATE].collate;
2650
2651   while (1)
2652     {
2653       char ucs4buf[10];
2654       char *symstr;
2655       size_t symlen;
2656
2657       /* Of course we don't proceed beyond the end of file.  */
2658       if (nowtok == tok_eof)
2659         break;
2660
2661       /* Ingore empty lines.  */
2662       if (nowtok == tok_eol)
2663         {
2664           now = lr_token (ldfile, charmap, result, NULL, verbose);
2665           nowtok = now->tok;
2666           continue;
2667         }
2668
2669       switch (nowtok)
2670         {
2671         case tok_copy:
2672           /* Allow copying other locales.  */
2673           now = lr_token (ldfile, charmap, result, NULL, verbose);
2674           if (now->tok != tok_string)
2675             goto err_label;
2676
2677           if (! ignore_content)
2678             load_locale (LC_COLLATE, now->val.str.startmb, repertoire_name,
2679                          charmap, result);
2680
2681           lr_ignore_rest (ldfile, 1);
2682           break;
2683
2684         case tok_coll_weight_max:
2685           /* Ignore the rest of the line if we don't need the input of
2686              this line.  */
2687           if (ignore_content)
2688             {
2689               lr_ignore_rest (ldfile, 0);
2690               break;
2691             }
2692
2693           if (state != 0)
2694             goto err_label;
2695
2696           arg = lr_token (ldfile, charmap, result, NULL, verbose);
2697           if (arg->tok != tok_number)
2698             goto err_label;
2699           if (collate->col_weight_max != -1)
2700             lr_error (ldfile, _("%s: duplicate definition of `%s'"),
2701                       "LC_COLLATE", "col_weight_max");
2702           else
2703             collate->col_weight_max = arg->val.num;
2704           lr_ignore_rest (ldfile, 1);
2705           break;
2706
2707         case tok_section_symbol:
2708           /* Ignore the rest of the line if we don't need the input of
2709              this line.  */
2710           if (ignore_content)
2711             {
2712               lr_ignore_rest (ldfile, 0);
2713               break;
2714             }
2715
2716           if (state != 0)
2717             goto err_label;
2718
2719           arg = lr_token (ldfile, charmap, result, repertoire, verbose);
2720           if (arg->tok != tok_bsymbol)
2721             goto err_label;
2722           else if (!ignore_content)
2723             {
2724               /* Check whether this section is already known.  */
2725               struct section_list *known = collate->sections;
2726               while (known != NULL)
2727                 {
2728                   if (strcmp (known->name, arg->val.str.startmb) == 0)
2729                     break;
2730                   known = known->next;
2731                 }
2732
2733               if (known != NULL)
2734                 {
2735                   lr_error (ldfile,
2736                             _("%s: duplicate declaration of section `%s'"),
2737                             "LC_COLLATE", arg->val.str.startmb);
2738                   free (arg->val.str.startmb);
2739                 }
2740               else
2741                 collate->sections = make_seclist_elem (collate,
2742                                                        arg->val.str.startmb,
2743                                                        collate->sections);
2744
2745               lr_ignore_rest (ldfile, known == NULL);
2746             }
2747           else
2748             {
2749               free (arg->val.str.startmb);
2750               lr_ignore_rest (ldfile, 0);
2751             }
2752           break;
2753
2754         case tok_collating_element:
2755           /* Ignore the rest of the line if we don't need the input of
2756              this line.  */
2757           if (ignore_content)
2758             {
2759               lr_ignore_rest (ldfile, 0);
2760               break;
2761             }
2762
2763           if (state != 0 && state != 2)
2764             goto err_label;
2765
2766           arg = lr_token (ldfile, charmap, result, repertoire, verbose);
2767           if (arg->tok != tok_bsymbol)
2768             goto err_label;
2769           else
2770             {
2771               const char *symbol = arg->val.str.startmb;
2772               size_t symbol_len = arg->val.str.lenmb;
2773
2774               /* Next the `from' keyword.  */
2775               arg = lr_token (ldfile, charmap, result, repertoire, verbose);
2776               if (arg->tok != tok_from)
2777                 {
2778                   free ((char *) symbol);
2779                   goto err_label;
2780                 }
2781
2782               ldfile->return_widestr = 1;
2783               ldfile->translate_strings = 1;
2784
2785               /* Finally the string with the replacement.  */
2786               arg = lr_token (ldfile, charmap, result, repertoire, verbose);
2787
2788               ldfile->return_widestr = 0;
2789               ldfile->translate_strings = 0;
2790
2791               if (arg->tok != tok_string)
2792                 goto err_label;
2793
2794               if (!ignore_content && symbol != NULL)
2795                 {
2796                   /* The name is already defined.  */
2797                   if (check_duplicate (ldfile, collate, charmap,
2798                                        repertoire, symbol, symbol_len))
2799                     goto col_elem_free;
2800
2801                   if (arg->val.str.startmb != NULL)
2802                     insert_entry (&collate->elem_table, symbol, symbol_len,
2803                                   new_element (collate,
2804                                                arg->val.str.startmb,
2805                                                arg->val.str.lenmb - 1,
2806                                                arg->val.str.startwc,
2807                                                symbol, symbol_len, 0));
2808                 }
2809               else
2810                 {
2811                 col_elem_free:
2812                   if (symbol != NULL)
2813                     free ((char *) symbol);
2814                   if (arg->val.str.startmb != NULL)
2815                     free (arg->val.str.startmb);
2816                   if (arg->val.str.startwc != NULL)
2817                     free (arg->val.str.startwc);
2818                 }
2819               lr_ignore_rest (ldfile, 1);
2820             }
2821           break;
2822
2823         case tok_collating_symbol:
2824           /* Ignore the rest of the line if we don't need the input of
2825              this line.  */
2826           if (ignore_content)
2827             {
2828               lr_ignore_rest (ldfile, 0);
2829               break;
2830             }
2831
2832           if (state != 0 && state != 2)
2833             goto err_label;
2834
2835           arg = lr_token (ldfile, charmap, result, repertoire, verbose);
2836           if (arg->tok != tok_bsymbol)
2837             goto err_label;
2838           else
2839             {
2840               char *symbol = arg->val.str.startmb;
2841               size_t symbol_len = arg->val.str.lenmb;
2842               char *endsymbol = NULL;
2843               size_t endsymbol_len = 0;
2844               enum token_t ellipsis = tok_none;
2845
2846               arg = lr_token (ldfile, charmap, result, repertoire, verbose);
2847               if (arg->tok == tok_ellipsis2 || arg->tok == tok_ellipsis4)
2848                 {
2849                   ellipsis = arg->tok;
2850
2851                   arg = lr_token (ldfile, charmap, result, repertoire,
2852                                   verbose);
2853                   if (arg->tok != tok_bsymbol)
2854                     {
2855                       free (symbol);
2856                       goto err_label;
2857                     }
2858
2859                   endsymbol = arg->val.str.startmb;
2860                   endsymbol_len = arg->val.str.lenmb;
2861
2862                   lr_ignore_rest (ldfile, 1);
2863                 }
2864               else if (arg->tok != tok_eol)
2865                 {
2866                   free (symbol);
2867                   goto err_label;
2868                 }
2869
2870               if (!ignore_content)
2871                 {
2872                   if (symbol == NULL
2873                       || (ellipsis != tok_none && endsymbol == NULL))
2874                     {
2875                       lr_error (ldfile, _("\
2876 %s: unknown character in collating symbol name"),
2877                                 "LC_COLLATE");
2878                       goto col_sym_free;
2879                     }
2880                   else if (ellipsis == tok_none)
2881                     {
2882                       /* A single symbol, no ellipsis.  */
2883                       if (check_duplicate (ldfile, collate, charmap,
2884                                            repertoire, symbol, symbol_len))
2885                         /* The name is already defined.  */
2886                         goto col_sym_free;
2887
2888                       insert_entry (&collate->sym_table, symbol, symbol_len,
2889                                     new_symbol (collate, symbol, symbol_len));
2890                     }
2891                   else if (symbol_len != endsymbol_len)
2892                     {
2893                     col_sym_inv_range:
2894                       lr_error (ldfile,
2895                                 _("invalid names for character range"));
2896                       goto col_sym_free;
2897                     }
2898                   else
2899                     {
2900                       /* Oh my, we have to handle an ellipsis.  First, as
2901                          usual, determine the common prefix and then
2902                          convert the rest into a range.  */
2903                       size_t prefixlen;
2904                       unsigned long int from;
2905                       unsigned long int to;
2906                       char *endp;
2907
2908                       for (prefixlen = 0; prefixlen < symbol_len; ++prefixlen)
2909                         if (symbol[prefixlen] != endsymbol[prefixlen])
2910                           break;
2911
2912                       /* Convert the rest into numbers.  */
2913                       symbol[symbol_len] = '\0';
2914                       from = strtoul (&symbol[prefixlen], &endp,
2915                                       ellipsis == tok_ellipsis2 ? 16 : 10);
2916                       if (*endp != '\0')
2917                         goto col_sym_inv_range;
2918
2919                       endsymbol[symbol_len] = '\0';
2920                       to = strtoul (&endsymbol[prefixlen], &endp,
2921                                     ellipsis == tok_ellipsis2 ? 16 : 10);
2922                       if (*endp != '\0')
2923                         goto col_sym_inv_range;
2924
2925                       if (from > to)
2926                         goto col_sym_inv_range;
2927
2928                       /* Now loop over all entries.  */
2929                       while (from <= to)
2930                         {
2931                           char *symbuf;
2932
2933                           symbuf = (char *) obstack_alloc (&collate->mempool,
2934                                                            symbol_len + 1);
2935
2936                           /* Create the name.  */
2937                           sprintf (symbuf,
2938                                    ellipsis == tok_ellipsis2
2939                                    ? "%.*s%.*lX" : "%.*s%.*lu",
2940                                    (int) prefixlen, symbol,
2941                                    (int) (symbol_len - prefixlen), from);
2942
2943                           if (check_duplicate (ldfile, collate, charmap,
2944                                                repertoire, symbuf, symbol_len))
2945                             /* The name is already defined.  */
2946                             goto col_sym_free;
2947
2948                           insert_entry (&collate->sym_table, symbuf,
2949                                         symbol_len,
2950                                         new_symbol (collate, symbuf,
2951                                                     symbol_len));
2952
2953                           /* Increment the counter.  */
2954                           ++from;
2955                         }
2956
2957                       goto col_sym_free;
2958                     }
2959                 }
2960               else
2961                 {
2962                 col_sym_free:
2963                   if (symbol != NULL)
2964                     free (symbol);
2965                   if (endsymbol != NULL)
2966                     free (endsymbol);
2967                 }
2968             }
2969           break;
2970
2971         case tok_symbol_equivalence:
2972           /* Ignore the rest of the line if we don't need the input of
2973              this line.  */
2974           if (ignore_content)
2975             {
2976               lr_ignore_rest (ldfile, 0);
2977               break;
2978             }
2979
2980           if (state != 0)
2981             goto err_label;
2982
2983           arg = lr_token (ldfile, charmap, result, repertoire, verbose);
2984           if (arg->tok != tok_bsymbol)
2985             goto err_label;
2986           else
2987             {
2988               const char *newname = arg->val.str.startmb;
2989               size_t newname_len = arg->val.str.lenmb;
2990               const char *symname;
2991               size_t symname_len;
2992               struct symbol_t *symval;
2993
2994               arg = lr_token (ldfile, charmap, result, repertoire, verbose);
2995               if (arg->tok != tok_bsymbol)
2996                 {
2997                   if (newname != NULL)
2998                     free ((char *) newname);
2999                   goto err_label;
3000                 }
3001
3002               symname = arg->val.str.startmb;
3003               symname_len = arg->val.str.lenmb;
3004
3005               if (newname == NULL)
3006                 {
3007                   lr_error (ldfile, _("\
3008 %s: unknown character in equivalent definition name"),
3009                             "LC_COLLATE");
3010
3011                 sym_equiv_free:
3012                   if (newname != NULL)
3013                     free ((char *) newname);
3014                   if (symname != NULL)
3015                     free ((char *) symname);
3016                   break;
3017                 }
3018               if (symname == NULL)
3019                 {
3020                   lr_error (ldfile, _("\
3021 %s: unknown character in equivalent definition value"),
3022                             "LC_COLLATE");
3023                   goto sym_equiv_free;
3024                 }
3025
3026               /* See whether the symbol name is already defined.  */
3027               if (find_entry (&collate->sym_table, symname, symname_len,
3028                               (void **) &symval) != 0)
3029                 {
3030                   lr_error (ldfile, _("\
3031 %s: unknown symbol `%s' in equivalent definition"),
3032                             "LC_COLLATE", symname);
3033                   goto col_sym_free;
3034                 }
3035
3036               if (insert_entry (&collate->sym_table,
3037                                 newname, newname_len, symval) < 0)
3038                 {
3039                   lr_error (ldfile, _("\
3040 error while adding equivalent collating symbol"));
3041                   goto sym_equiv_free;
3042                 }
3043
3044               free ((char *) symname);
3045             }
3046           lr_ignore_rest (ldfile, 1);
3047           break;
3048
3049         case tok_script:
3050           /* We get told about the scripts we know.  */
3051           arg = lr_token (ldfile, charmap, result, repertoire, verbose);
3052           if (arg->tok != tok_bsymbol)
3053             goto err_label;
3054           else
3055             {
3056               struct section_list *runp = collate->known_sections;
3057               char *name;
3058
3059               while (runp != NULL)
3060                 if (strncmp (runp->name, arg->val.str.startmb,
3061                              arg->val.str.lenmb) == 0
3062                     && runp->name[arg->val.str.lenmb] == '\0')
3063                   break;
3064                 else
3065                   runp = runp->def_next;
3066
3067               if (runp != NULL)
3068                 {
3069                   lr_error (ldfile, _("duplicate definition of script `%s'"),
3070                             runp->name);
3071                   lr_ignore_rest (ldfile, 0);
3072                   break;
3073                 }
3074
3075               runp = (struct section_list *) xcalloc (1, sizeof (*runp));
3076               name = (char *) xmalloc (arg->val.str.lenmb + 1);
3077               memcpy (name, arg->val.str.startmb, arg->val.str.lenmb);
3078               name[arg->val.str.lenmb] = '\0';
3079               runp->name = name;
3080
3081               runp->def_next = collate->known_sections;
3082               collate->known_sections = runp;
3083             }
3084           lr_ignore_rest (ldfile, 1);
3085           break;
3086
3087         case tok_order_start:
3088           /* Ignore the rest of the line if we don't need the input of
3089              this line.  */
3090           if (ignore_content)
3091             {
3092               lr_ignore_rest (ldfile, 0);
3093               break;
3094             }
3095
3096           if (state != 0 && state != 1)
3097             goto err_label;
3098           state = 1;
3099
3100           /* The 14652 draft does not specify whether all `order_start' lines
3101              must contain the same number of sort-rules, but 14651 does.  So
3102              we require this here as well.  */
3103           arg = lr_token (ldfile, charmap, result, repertoire, verbose);
3104           if (arg->tok == tok_bsymbol)
3105             {
3106               /* This better should be a section name.  */
3107               struct section_list *sp = collate->known_sections;
3108               while (sp != NULL
3109                      && (sp->name == NULL
3110                          || strncmp (sp->name, arg->val.str.startmb,
3111                                      arg->val.str.lenmb) != 0
3112                          || sp->name[arg->val.str.lenmb] != '\0'))
3113                 sp = sp->def_next;
3114
3115               if (sp == NULL)
3116                 {
3117                   lr_error (ldfile, _("\
3118 %s: unknown section name `%s'"),
3119                             "LC_COLLATE", arg->val.str.startmb);
3120                   /* We use the error section.  */
3121                   collate->current_section = &collate->error_section;
3122
3123                   if (collate->error_section.first == NULL)
3124                     {
3125                       /* Insert &collate->error_section at the end of
3126                          the collate->sections list.  */
3127                       if (collate->sections == NULL)
3128                         collate->sections = &collate->error_section;
3129                       else
3130                         {
3131                           sp = collate->sections;
3132                           while (sp->next != NULL)
3133                             sp = sp->next;
3134
3135                           sp->next = &collate->error_section;
3136                         }
3137                       collate->error_section.next = NULL;
3138                     }
3139                 }
3140               else
3141                 {
3142                   /* One should not be allowed to open the same
3143                      section twice.  */
3144                   if (sp->first != NULL)
3145                     lr_error (ldfile, _("\
3146 %s: multiple order definitions for section `%s'"),
3147                               "LC_COLLATE", sp->name);
3148                   else
3149                     {
3150                       /* Insert sp in the collate->sections list,
3151                          right after collate->current_section.  */
3152                       if (collate->current_section == NULL)
3153                         collate->current_section = sp;
3154                       else
3155                         {
3156                           sp->next = collate->current_section->next;
3157                           collate->current_section->next = sp;
3158                         }
3159                     }
3160
3161                   /* Next should come the end of the line or a semicolon.  */
3162                   arg = lr_token (ldfile, charmap, result, repertoire,
3163                                   verbose);
3164                   if (arg->tok == tok_eol)
3165                     {
3166                       uint32_t cnt;
3167
3168                       /* This means we have exactly one rule: `forward'.  */
3169                       if (nrules > 1)
3170                         lr_error (ldfile, _("\
3171 %s: invalid number of sorting rules"),
3172                                   "LC_COLLATE");
3173                       else
3174                         nrules = 1;
3175                       sp->rules = obstack_alloc (&collate->mempool,
3176                                                  (sizeof (enum coll_sort_rule)
3177                                                   * nrules));
3178                       for (cnt = 0; cnt < nrules; ++cnt)
3179                         sp->rules[cnt] = sort_forward;
3180
3181                       /* Next line.  */
3182                       break;
3183                     }
3184