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