2 * Copyright 2010 Nexenta Systems, Inc. All rights reserved.
3 * Copyright 2015 John Marino <draco@marino.st>
5 * This source code is derived from the illumos localedef command, and
6 * provided under BSD-style license terms by Nexenta Systems, Inc.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
22 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28 * POSSIBILITY OF SUCH DAMAGE.
32 * LC_COLLATE database generation routines for localedef.
35 #include <sys/types.h>
46 #include "localedef.h"
53 * It will be extremely helpful to the reader if they have access to
54 * the localedef and locale file format specifications available.
55 * Latest versions of these are available from www.opengroup.org.
57 * The design for the collation code is a bit complex. The goal is a
58 * single collation database as described in collate.h (in
59 * libc/port/locale). However, there are some other tidbits:
61 * a) The substitution entries are now a directly indexable array. A
62 * priority elsewhere in the table is taken as an index into the
63 * substitution table if it has a high bit (COLLATE_SUBST_PRIORITY)
64 * set. (The bit is cleared and the result is the index into the
67 * b) We eliminate duplicate entries into the substitution table.
68 * This saves a lot of space.
70 * c) The priorities for each level are "compressed", so that each
71 * sorting level has consecutively numbered priorities starting at 1.
72 * (O is reserved for the ignore priority.) This means sort levels
73 * which only have a few distinct priorities can represent the
74 * priority level in fewer bits, which makes the strxfrm output
77 * d) We record the total number of priorities so that strxfrm can
78 * figure out how many bytes to expand a numeric priority into.
80 * e) For the UNDEFINED pass (the last pass), we record the maximum
81 * number of bits needed to uniquely prioritize these entries, so that
82 * the last pass can also use smaller strxfrm output when possible.
84 * f) Priorities with the sign bit set are verboten. This works out
85 * because no active character set needs that bit to carry significant
86 * information once the character is in wide form.
88 * To process the entire data to make the database, we actually run
89 * multiple passes over the data.
91 * The first pass, which is done at parse time, identifies elements,
92 * substitutions, and such, and records them in priority order. As
93 * some priorities can refer to other priorities, using forward
94 * references, we use a table of references indicating whether the
95 * priority's value has been resolved, or whether it is still a
98 * The second pass walks over all the items in priority order, noting
99 * that they are used directly, and not just an indirect reference.
100 * This is done by creating a "weight" structure for the item. The
101 * weights are stashed in an RB tree sorted by relative "priority".
103 * The third pass walks over all the weight structures, in priority
104 * order, and assigns a new monotonically increasing (per sort level)
105 * weight value to them. These are the values that will actually be
106 * written to the file.
108 * The fourth pass just writes the data out.
112 * In order to resolve the priorities, we create a table of priorities.
113 * Entries in the table can be in one of three states.
115 * UNKNOWN is for newly allocated entries, and indicates that nothing
116 * is known about the priority. (For example, when new entries are created
117 * for collating-symbols, this is the value assigned for them until the
118 * collating symbol's order has been determined.
120 * RESOLVED is used for an entry where the priority indicates the final
123 * REFER is used for entries that reference other entries. Typically
124 * this is used for forward references. A collating-symbol can never
127 * The "pass" field is used during final resolution to aid in detection
128 * of referencing loops. (For example <A> depends on <B>, but <B> has its
129 * priority dependent on <A>.)
132 UNKNOWN
, /* priority is totally unknown */
133 RESOLVED
, /* priority value fully resolved */
134 REFER
/* priority is a reference (index) */
137 typedef struct weight
{
140 RB_ENTRY(weight
) entry
;
143 typedef struct priority
{
150 #define NUM_WT collinfo.directive_count
153 * These are the abstract collating symbols, which are just a symbolic
154 * way to reference a priority.
159 RB_ENTRY(collsym
) entry
;
163 * These are also abstract collating symbols, but we allow them to have
164 * different priorities at different levels.
166 typedef struct collundef
{
168 int32_t ref
[COLL_WEIGHTS_MAX
];
169 RB_ENTRY(collundef
) entry
;
173 * These are called "chains" in libc. This records the fact that two
174 * more characters should be treated as a single collating entity when
175 * they appear together. For example, in Spanish <C><h> gets collated
176 * as a character between <C> and <D>.
181 int32_t ref
[COLL_WEIGHTS_MAX
];
182 RB_ENTRY(collelem
) rb_bysymbol
;
183 RB_ENTRY(collelem
) rb_byexpand
;
187 * Individual characters have a sequence of weights as well.
189 typedef struct collchar
{
191 int32_t ref
[COLL_WEIGHTS_MAX
];
192 RB_ENTRY(collchar
) entry
;
196 * Substitution entries. The key is itself a priority. Note that
197 * when we create one of these, we *automatically* wind up with a
198 * fully resolved priority for the key, because creation of
199 * substitutions creates a resolved priority at the same time.
201 typedef struct subst
{
203 int32_t ref
[COLLATE_STR_LEN
];
204 RB_ENTRY(subst
) entry
;
205 RB_ENTRY(subst
) entry_ref
;
208 static RB_HEAD(collsyms
, collsym
) collsyms
;
209 static RB_HEAD(collundefs
, collundef
) collundefs
;
210 static RB_HEAD(elem_by_symbol
, collelem
) elem_by_symbol
;
211 static RB_HEAD(elem_by_expand
, collelem
) elem_by_expand
;
212 static RB_HEAD(collchars
, collchar
) collchars
;
213 static RB_HEAD(substs
, subst
) substs
[COLL_WEIGHTS_MAX
];
214 static RB_HEAD(substs_ref
, subst
) substs_ref
[COLL_WEIGHTS_MAX
];
215 static RB_HEAD(weights
, weight
) weights
[COLL_WEIGHTS_MAX
];
216 static int32_t nweight
[COLL_WEIGHTS_MAX
];
219 * This is state tracking for the ellipsis token. Note that we start
220 * the initial values so that the ellipsis logic will think we got a
221 * magic starting value of NUL. It starts at minus one because the
222 * starting point is exclusive -- i.e. the starting point is not
223 * itself handled by the ellipsis code.
225 static int currorder
= EOF
;
226 static int lastorder
= EOF
;
227 static collelem_t
*currelem
;
228 static collchar_t
*currchar
;
229 static collundef_t
*currundef
;
230 static wchar_t ellipsis_start
= 0;
231 static int32_t ellipsis_weights
[COLL_WEIGHTS_MAX
];
234 * We keep a running tally of weights.
236 static int nextpri
= 1;
237 static int nextsubst
[COLL_WEIGHTS_MAX
] = { 0 };
240 * This array collects up the weights for each level.
242 static int32_t order_weights
[COLL_WEIGHTS_MAX
];
243 static int curr_weight
= 0;
244 static int32_t subst_weights
[COLLATE_STR_LEN
];
245 static int curr_subst
= 0;
248 * Some initial priority values.
250 static int32_t pri_undefined
[COLL_WEIGHTS_MAX
];
251 static int32_t pri_ignore
;
253 static collate_info_t collinfo
;
255 static collpri_t
*prilist
= NULL
;
256 static int numpri
= 0;
257 static int maxpri
= 0;
259 static void start_order(int);
266 if (numpri
>= maxpri
) {
267 maxpri
= maxpri
? maxpri
* 2 : 1024;
268 prilist
= realloc(prilist
, sizeof (collpri_t
) * maxpri
);
269 if (prilist
== NULL
) {
270 fprintf(stderr
,"out of memory");
273 for (i
= numpri
; i
< maxpri
; i
++) {
274 prilist
[i
].res
= UNKNOWN
;
285 if ((ref
< 0) || (ref
> numpri
)) {
289 return (&prilist
[ref
]);
293 set_pri(int32_t ref
, int32_t v
, res_t res
)
299 if ((res
== REFER
) && ((v
< 0) || (v
>= numpri
))) {
303 /* Resolve self references */
304 if ((res
== REFER
) && (ref
== v
)) {
309 if (pri
->res
!= UNKNOWN
) {
310 warn("repeated item in order list (first on %d)",
314 pri
->lineno
= lineno
;
320 resolve_pri(int32_t ref
)
323 static int32_t pass
= 0;
327 while (pri
->res
== REFER
) {
328 if (pri
->pass
== pass
) {
329 /* report a line with the circular symbol */
330 lineno
= pri
->lineno
;
331 fprintf(stderr
,"circular reference in order list");
334 if ((pri
->pri
< 0) || (pri
->pri
>= numpri
)) {
339 pri
= &prilist
[pri
->pri
];
342 if (pri
->res
== UNKNOWN
) {
345 if (pri
->res
!= RESOLVED
)
352 weight_compare(const void *n1
, const void *n2
)
354 int32_t k1
= ((const weight_t
*)n1
)->pri
;
355 int32_t k2
= ((const weight_t
*)n2
)->pri
;
357 return (k1
< k2
? -1 : k1
> k2
? 1 : 0);
360 RB_PROTOTYPE_STATIC(weights
, weight
, entry
, weight_compare
);
361 RB_GENERATE(weights
, weight
, entry
, weight_compare
);
364 collsym_compare(const void *n1
, const void *n2
)
366 const collsym_t
*c1
= n1
;
367 const collsym_t
*c2
= n2
;
370 rv
= strcmp(c1
->name
, c2
->name
);
371 return ((rv
< 0) ? -1 : (rv
> 0) ? 1 : 0);
374 RB_PROTOTYPE_STATIC(collsyms
, collsym
, entry
, collsym_compare
);
375 RB_GENERATE(collsyms
, collsym
, entry
, collsym_compare
);
378 collundef_compare(const void *n1
, const void *n2
)
380 const collundef_t
*c1
= n1
;
381 const collundef_t
*c2
= n2
;
384 rv
= strcmp(c1
->name
, c2
->name
);
385 return ((rv
< 0) ? -1 : (rv
> 0) ? 1 : 0);
388 RB_PROTOTYPE_STATIC(collundefs
, collundef
, entry
, collundef_compare
);
389 RB_GENERATE(collundefs
, collundef
, entry
, collundef_compare
);
392 element_compare_symbol(const void *n1
, const void *n2
)
394 const collelem_t
*c1
= n1
;
395 const collelem_t
*c2
= n2
;
398 rv
= strcmp(c1
->symbol
, c2
->symbol
);
399 return ((rv
< 0) ? -1 : (rv
> 0) ? 1 : 0);
402 RB_PROTOTYPE_STATIC(elem_by_symbol
, collelem
, rb_bysymbol
, element_compare_symbol
);
403 RB_GENERATE(elem_by_symbol
, collelem
, rb_bysymbol
, element_compare_symbol
);
406 element_compare_expand(const void *n1
, const void *n2
)
408 const collelem_t
*c1
= n1
;
409 const collelem_t
*c2
= n2
;
412 rv
= wcscmp(c1
->expand
, c2
->expand
);
413 return ((rv
< 0) ? -1 : (rv
> 0) ? 1 : 0);
416 RB_PROTOTYPE_STATIC(elem_by_expand
, collelem
, rb_byexpand
, element_compare_expand
);
417 RB_GENERATE(elem_by_expand
, collelem
, rb_byexpand
, element_compare_expand
);
420 collchar_compare(const void *n1
, const void *n2
)
422 wchar_t k1
= ((const collchar_t
*)n1
)->wc
;
423 wchar_t k2
= ((const collchar_t
*)n2
)->wc
;
425 return (k1
< k2
? -1 : k1
> k2
? 1 : 0);
428 RB_PROTOTYPE_STATIC(collchars
, collchar
, entry
, collchar_compare
);
429 RB_GENERATE(collchars
, collchar
, entry
, collchar_compare
);
432 subst_compare(const void *n1
, const void *n2
)
434 int32_t k1
= ((const subst_t
*)n1
)->key
;
435 int32_t k2
= ((const subst_t
*)n2
)->key
;
437 return (k1
< k2
? -1 : k1
> k2
? 1 : 0);
440 RB_PROTOTYPE_STATIC(substs
, subst
, entry
, subst_compare
);
441 RB_GENERATE(substs
, subst
, entry
, subst_compare
);
444 subst_compare_ref(const void *n1
, const void *n2
)
446 const wchar_t *c1
= ((const subst_t
*)n1
)->ref
;
447 const wchar_t *c2
= ((const subst_t
*)n2
)->ref
;
451 return ((rv
< 0) ? -1 : (rv
> 0) ? 1 : 0);
454 RB_PROTOTYPE_STATIC(substs_ref
, subst
, entry_ref
, subst_compare_ref
);
455 RB_GENERATE(substs_ref
, subst
, entry_ref
, subst_compare_ref
);
464 RB_INIT(&collundefs
);
466 RB_INIT(&elem_by_symbol
);
468 RB_INIT(&elem_by_expand
);
472 for (i
= 0; i
< COLL_WEIGHTS_MAX
; i
++) {
474 RB_INIT(&substs_ref
[i
]);
475 RB_INIT(&weights
[i
]);
479 (void) memset(&collinfo
, 0, sizeof (collinfo
));
481 /* allocate some initial priorities */
482 pri_ignore
= new_pri();
484 set_pri(pri_ignore
, 0, RESOLVED
);
486 for (i
= 0; i
< COLL_WEIGHTS_MAX
; i
++) {
487 pri_undefined
[i
] = new_pri();
489 /* we will override this later */
490 set_pri(pri_undefined
[i
], COLLATE_MAX_PRIORITY
, UNKNOWN
);
495 define_collsym(char *name
)
499 if ((sym
= calloc(sizeof (*sym
), 1)) == NULL
) {
500 fprintf(stderr
,"out of memory");
504 sym
->ref
= new_pri();
506 if (RB_FIND(collsyms
, &collsyms
, sym
) != NULL
) {
508 * This should never happen because we are only called
509 * for undefined symbols.
514 RB_INSERT(collsyms
, &collsyms
, sym
);
518 lookup_collsym(char *name
)
523 return (RB_FIND(collsyms
, &collsyms
, &srch
));
527 lookup_collelem(char *symbol
)
531 srch
.symbol
= symbol
;
532 return (RB_FIND(elem_by_symbol
, &elem_by_symbol
, &srch
));
536 get_collundef(char *name
)
543 if ((ud
= RB_FIND(collundefs
, &collundefs
, &srch
)) == NULL
) {
544 if (((ud
= calloc(sizeof (*ud
), 1)) == NULL
) ||
545 ((ud
->name
= strdup(name
)) == NULL
)) {
546 fprintf(stderr
,"out of memory");
549 for (i
= 0; i
< NUM_WT
; i
++) {
550 ud
->ref
[i
] = new_pri();
552 RB_INSERT(collundefs
, &collundefs
, ud
);
554 add_charmap_undefined(name
);
559 get_collchar(wchar_t wc
, int create
)
566 cc
= RB_FIND(collchars
, &collchars
, &srch
);
567 if ((cc
== NULL
) && create
) {
568 if ((cc
= calloc(sizeof (*cc
), 1)) == NULL
) {
569 fprintf(stderr
, "out of memory");
572 for (i
= 0; i
< NUM_WT
; i
++) {
573 cc
->ref
[i
] = new_pri();
576 RB_INSERT(collchars
, &collchars
, cc
);
582 end_order_collsym(collsym_t
*sym
)
584 start_order(T_COLLSYM
);
585 /* update the weight */
587 set_pri(sym
->ref
, nextpri
, RESOLVED
);
599 /* advance the priority/weight */
604 for (i
= 0; i
< NUM_WT
; i
++) {
605 if (((ref
= order_weights
[i
]) < 0) ||
606 ((p
= get_pri(ref
)) == NULL
) ||
608 /* unspecified weight is a self reference */
609 set_pri(currchar
->ref
[i
], pri
, RESOLVED
);
611 set_pri(currchar
->ref
[i
], ref
, REFER
);
613 order_weights
[i
] = -1;
616 /* leave a cookie trail in case next symbol is ellipsis */
617 ellipsis_start
= currchar
->wc
+ 1;
622 /* save off the weights were we can find them */
623 for (i
= 0; i
< NUM_WT
; i
++) {
624 ellipsis_weights
[i
] = order_weights
[i
];
625 order_weights
[i
] = -1;
630 if (currelem
== NULL
) {
633 for (i
= 0; i
< NUM_WT
; i
++) {
635 if (((ref
= order_weights
[i
]) < 0) ||
636 ((p
= get_pri(ref
)) == NULL
) ||
638 set_pri(currelem
->ref
[i
], pri
,
641 set_pri(currelem
->ref
[i
], ref
, REFER
);
643 order_weights
[i
] = -1;
649 for (i
= 0; i
< NUM_WT
; i
++) {
650 if (((ref
= order_weights
[i
]) < 0) ||
651 ((p
= get_pri(ref
)) == NULL
) ||
653 set_pri(pri_undefined
[i
], -1, RESOLVED
);
655 set_pri(pri_undefined
[i
], ref
, REFER
);
657 order_weights
[i
] = -1;
662 for (i
= 0; i
< NUM_WT
; i
++) {
663 if (((ref
= order_weights
[i
]) < 0) ||
664 ((p
= get_pri(ref
)) == NULL
) ||
666 set_pri(currundef
->ref
[i
], pri
, RESOLVED
);
668 set_pri(currundef
->ref
[i
], ref
, REFER
);
670 order_weights
[i
] = -1;
682 start_order(int type
)
686 lastorder
= currorder
;
689 /* this is used to protect ELLIPSIS processing */
690 if ((lastorder
== T_ELLIPSIS
) && (type
!= T_CHAR
)) {
691 fprintf(stderr
, "character value expected");
694 for (i
= 0; i
< COLL_WEIGHTS_MAX
; i
++) {
695 order_weights
[i
] = -1;
701 start_order_undefined(void)
703 start_order(T_UNDEFINED
);
707 start_order_symbol(char *name
)
709 currundef
= get_collundef(name
);
710 start_order(T_SYMBOL
);
714 start_order_char(wchar_t wc
)
722 * If we last saw an ellipsis, then we need to close the range.
723 * Handle that here. Note that we have to be careful because the
724 * items *inside* the range are treated exclusiveley to the items
725 * outside of the range. The ends of the range can have quite
726 * different weights than the range members.
728 if (lastorder
== T_ELLIPSIS
) {
731 if (wc
< ellipsis_start
) {
732 fprintf(stderr
, "malformed range!");
735 while (ellipsis_start
< wc
) {
737 * pick all of the saved weights for the
738 * ellipsis. note that -1 encodes for the
739 * ellipsis itself, which means to take the
740 * current relative priority.
742 if ((cc
= get_collchar(ellipsis_start
, 1)) == NULL
) {
746 for (i
= 0; i
< NUM_WT
; i
++) {
748 if (((ref
= ellipsis_weights
[i
]) == -1) ||
749 ((p
= get_pri(ref
)) == NULL
) ||
751 set_pri(cc
->ref
[i
], nextpri
, RESOLVED
);
753 set_pri(cc
->ref
[i
], ref
, REFER
);
755 ellipsis_weights
[i
] = 0;
762 currchar
= get_collchar(wc
, 1);
766 start_order_collelem(collelem_t
*e
)
768 start_order(T_COLLELEM
);
773 start_order_ellipsis(void)
777 start_order(T_ELLIPSIS
);
779 if (lastorder
!= T_CHAR
) {
780 fprintf(stderr
, "illegal starting point for range");
784 for (i
= 0; i
< NUM_WT
; i
++) {
785 ellipsis_weights
[i
] = order_weights
[i
];
790 define_collelem(char *name
, wchar_t *wcs
)
795 if (wcslen(wcs
) >= COLLATE_STR_LEN
) {
796 fprintf(stderr
,"expanded collation element too long");
800 if ((e
= calloc(sizeof (*e
), 1)) == NULL
) {
801 fprintf(stderr
, "out of memory");
808 * This is executed before the order statement, so we don't
809 * know how many priorities we *really* need. We allocate one
810 * for each possible weight. Not a big deal, as collating-elements
811 * prove to be quite rare.
813 for (i
= 0; i
< COLL_WEIGHTS_MAX
; i
++) {
814 e
->ref
[i
] = new_pri();
817 /* A character sequence can only reduce to one element. */
818 if ((RB_FIND(elem_by_symbol
, &elem_by_symbol
, e
) != NULL
) ||
819 (RB_FIND(elem_by_expand
, &elem_by_expand
, e
) != NULL
)) {
820 fprintf(stderr
, "duplicate collating element definition");
823 RB_INSERT(elem_by_symbol
, &elem_by_symbol
, e
);
824 RB_INSERT(elem_by_expand
, &elem_by_expand
, e
);
828 add_order_bit(int kw
)
830 uint8_t bit
= DIRECTIVE_UNDEF
;
834 bit
= DIRECTIVE_FORWARD
;
837 bit
= DIRECTIVE_BACKWARD
;
840 bit
= DIRECTIVE_POSITION
;
846 collinfo
.directive
[collinfo
.directive_count
] |= bit
;
850 add_order_directive(void)
852 if (collinfo
.directive_count
>= COLL_WEIGHTS_MAX
) {
853 fprintf(stderr
,"too many directives (max %d)", COLL_WEIGHTS_MAX
);
855 collinfo
.directive_count
++;
859 add_order_pri(int32_t ref
)
861 if (curr_weight
>= NUM_WT
) {
862 fprintf(stderr
,"too many weights (max %d)", NUM_WT
);
865 order_weights
[curr_weight
] = ref
;
870 add_order_collsym(collsym_t
*s
)
872 add_order_pri(s
->ref
);
876 add_order_char(wchar_t wc
)
880 if ((cc
= get_collchar(wc
, 1)) == NULL
) {
885 add_order_pri(cc
->ref
[curr_weight
]);
889 add_order_collelem(collelem_t
*e
)
891 add_order_pri(e
->ref
[curr_weight
]);
895 add_order_ignore(void)
897 add_order_pri(pri_ignore
);
901 add_order_symbol(char *sym
)
904 if ((c
= get_collundef(sym
)) == NULL
) {
908 add_order_pri(c
->ref
[curr_weight
]);
912 add_order_ellipsis(void)
914 /* special NULL value indicates self reference */
919 add_order_subst(void)
925 (void) memset(&srch
, 0, sizeof (srch
));
926 for (i
= 0; i
< curr_subst
; i
++) {
927 srch
.ref
[i
] = subst_weights
[i
];
928 subst_weights
[i
] = 0;
930 s
= RB_FIND(substs_ref
, &substs_ref
[curr_weight
], &srch
);
933 if ((s
= calloc(sizeof (*s
), 1)) == NULL
) {
934 fprintf(stderr
,"out of memory");
940 * We use a self reference for our key, but we set a
941 * high bit to indicate that this is a substitution
942 * reference. This will expedite table lookups later,
943 * and prevent table lookups for situations that don't
944 * require it. (In short, its a big win, because we
945 * can skip a lot of binary searching.)
948 (nextsubst
[curr_weight
] | COLLATE_SUBST_PRIORITY
),
950 nextsubst
[curr_weight
] += 1;
952 for (i
= 0; i
< curr_subst
; i
++) {
953 s
->ref
[i
] = srch
.ref
[i
];
956 RB_INSERT(substs_ref
, &substs_ref
[curr_weight
], s
);
958 if (RB_FIND(substs
, &substs
[curr_weight
], s
) != NULL
) {
962 RB_INSERT(substs
, &substs
[curr_weight
], s
);
968 * We are using the current (unique) priority as a search key
969 * in the substitution table.
971 add_order_pri(s
->key
);
975 add_subst_pri(int32_t ref
)
977 if (curr_subst
>= COLLATE_STR_LEN
) {
978 fprintf(stderr
,"substitution string is too long");
981 subst_weights
[curr_subst
] = ref
;
986 add_subst_char(wchar_t wc
)
991 if (((cc
= get_collchar(wc
, 1)) == NULL
) ||
996 /* we take the weight for the character at that position */
997 add_subst_pri(cc
->ref
[curr_weight
]);
1001 add_subst_collelem(collelem_t
*e
)
1003 add_subst_pri(e
->ref
[curr_weight
]);
1007 add_subst_collsym(collsym_t
*s
)
1009 add_subst_pri(s
->ref
);
1013 add_subst_symbol(char *ptr
)
1017 if ((cu
= get_collundef(ptr
)) != NULL
) {
1018 add_subst_pri(cu
->ref
[curr_weight
]);
1023 add_weight(int32_t ref
, int pass
)
1028 srch
.pri
= resolve_pri(ref
);
1030 /* No translation of ignores */
1034 /* Substitution priorities are not weights */
1035 if (srch
.pri
& COLLATE_SUBST_PRIORITY
)
1038 if (RB_FIND(weights
, &weights
[pass
], &srch
) != NULL
)
1041 if ((w
= calloc(sizeof (*w
), 1)) == NULL
) {
1042 fprintf(stderr
, "out of memory");
1046 RB_INSERT(weights
, &weights
[pass
], w
);
1050 add_weights(int32_t *refs
)
1053 for (i
= 0; i
< NUM_WT
; i
++) {
1054 add_weight(refs
[i
], i
);
1059 get_weight(int32_t ref
, int pass
)
1065 pri
= resolve_pri(ref
);
1066 if (pri
& COLLATE_SUBST_PRIORITY
) {
1073 if ((w
= RB_FIND(weights
, &weights
[pass
], &srch
)) == NULL
) {
1081 wsncpy(wchar_t *s1
, const wchar_t *s2
, size_t n
)
1086 while (--n
> 0 && (*s1
++ = *s2
++) != 0)
1094 #define RB_COUNT(x, name, head, cnt) do { \
1096 RB_FOREACH(x, name, (head)) { \
1101 #define RB_NUMNODES(type, name, head, cnt) do { \
1104 RB_FOREACH(t, name, head) { \
1119 char vers
[COLLATE_STR_LEN
];
1120 collate_char_t chars
[UCHAR_MAX
+ 1];
1121 collate_large_t
*large
;
1122 collate_subst_t
*subst
[COLL_WEIGHTS_MAX
];
1123 collate_chain_t
*chain
;
1126 * We have to run throught a preliminary pass to identify all the
1127 * weights that we use for each sorting level.
1129 for (i
= 0; i
< NUM_WT
; i
++) {
1130 add_weight(pri_ignore
, i
);
1132 for (i
= 0; i
< NUM_WT
; i
++) {
1133 RB_FOREACH(sb
, substs
, &substs
[i
]) {
1134 for (j
= 0; sb
->ref
[j
]; j
++) {
1135 add_weight(sb
->ref
[j
], i
);
1139 RB_FOREACH(ce
, elem_by_expand
, &elem_by_expand
) {
1140 add_weights(ce
->ref
);
1142 RB_FOREACH(cc
, collchars
, &collchars
) {
1143 add_weights(cc
->ref
);
1147 * Now we walk the entire set of weights, removing the gaps
1148 * in the weights. This gives us optimum usage. The walk
1149 * occurs in priority.
1151 for (i
= 0; i
< NUM_WT
; i
++) {
1153 RB_FOREACH(w
, weights
, &weights
[i
]) {
1154 w
->opt
= nweight
[i
];
1159 (void) memset(&chars
, 0, sizeof (chars
));
1160 (void) memset(vers
, 0, COLLATE_STR_LEN
);
1161 (void) strlcpy(vers
, COLLATE_VERSION
, sizeof (vers
));
1164 * We need to make sure we arrange for the UNDEFINED field
1165 * to show up. Also, set the total weight counts.
1167 for (i
= 0; i
< NUM_WT
; i
++) {
1168 if (resolve_pri(pri_undefined
[i
]) == -1) {
1169 set_pri(pri_undefined
[i
], -1, RESOLVED
);
1170 /* they collate at the end of everything else */
1171 collinfo
.undef_pri
[i
] = COLLATE_MAX_PRIORITY
;
1173 collinfo
.pri_count
[i
] = nweight
[i
];
1176 collinfo
.pri_count
[NUM_WT
] = max_wide();
1177 collinfo
.undef_pri
[NUM_WT
] = COLLATE_MAX_PRIORITY
;
1178 collinfo
.directive
[NUM_WT
] = DIRECTIVE_UNDEFINED
;
1181 * Ordinary character priorities
1183 for (i
= 0; i
<= UCHAR_MAX
; i
++) {
1184 if ((cc
= get_collchar(i
, 0)) != NULL
) {
1185 for (j
= 0; j
< NUM_WT
; j
++) {
1186 chars
[i
].pri
[j
] = get_weight(cc
->ref
[j
], j
);
1189 for (j
= 0; j
< NUM_WT
; j
++) {
1191 get_weight(pri_undefined
[j
], j
);
1194 * Per POSIX, for undefined characters, we
1195 * also have to add a last item, which is the
1198 chars
[i
].pri
[NUM_WT
] = i
;
1203 * Substitution tables
1205 for (i
= 0; i
< NUM_WT
; i
++) {
1206 collate_subst_t
*st
= NULL
;
1208 RB_COUNT(temp
, substs
, &substs
[i
], n
);
1209 collinfo
.subst_count
[i
] = n
;
1210 if ((st
= calloc(sizeof (collate_subst_t
) * n
, 1)) == NULL
) {
1211 fprintf(stderr
, "out of memory");
1215 RB_FOREACH(sb
, substs
, &substs
[i
]) {
1216 if ((st
[n
].key
= resolve_pri(sb
->key
)) < 0) {
1217 /* by definition these resolve! */
1220 if (st
[n
].key
!= (n
| COLLATE_SUBST_PRIORITY
)) {
1223 for (j
= 0; sb
->ref
[j
]; j
++) {
1224 st
[n
].pri
[j
] = get_weight(sb
->ref
[j
], i
);
1228 if (n
!= collinfo
.subst_count
[i
])
1235 * Chains, i.e. collating elements
1237 RB_NUMNODES(collelem_t
, elem_by_expand
, &elem_by_expand
,
1238 collinfo
.chain_count
);
1239 chain
= calloc(sizeof (collate_chain_t
), collinfo
.chain_count
);
1240 if (chain
== NULL
) {
1241 fprintf(stderr
, "out of memory");
1245 RB_FOREACH(ce
, elem_by_expand
, &elem_by_expand
) {
1246 (void) wsncpy(chain
[n
].str
, ce
->expand
, COLLATE_STR_LEN
);
1247 for (i
= 0; i
< NUM_WT
; i
++) {
1248 chain
[n
].pri
[i
] = get_weight(ce
->ref
[i
], i
);
1252 if (n
!= collinfo
.chain_count
)
1256 * Large (> UCHAR_MAX) character priorities
1258 RB_NUMNODES(collchar_t
, collchars
, &collchars
, n
);
1259 large
= calloc(n
, sizeof (collate_large_t
));
1260 if (large
== NULL
) {
1261 fprintf(stderr
, "out of memory");
1266 RB_FOREACH(cc
, collchars
, &collchars
) {
1268 /* we already gathered those */
1269 if (cc
->wc
<= UCHAR_MAX
)
1271 for (j
= 0; j
< NUM_WT
; j
++) {
1272 if ((pri
= get_weight(cc
->ref
[j
], j
)) < 0) {
1275 if (undef
&& (pri
>= 0)) {
1276 /* if undefined, then all priorities are */
1279 large
[i
].pri
.pri
[j
] = pri
;
1283 large
[i
].val
= cc
->wc
;
1284 collinfo
.large_count
= i
++;
1288 if ((f
= open_category()) == NULL
) {
1292 /* Time to write the entire data set out */
1294 if ((wr_category(vers
, COLLATE_STR_LEN
, f
) < 0) ||
1295 (wr_category(&collinfo
, sizeof (collinfo
), f
) < 0) ||
1296 (wr_category(&chars
, sizeof (chars
), f
) < 0)) {
1300 for (i
= 0; i
< NUM_WT
; i
++) {
1301 sz
= sizeof (collate_subst_t
) * collinfo
.subst_count
[i
];
1302 if (wr_category(subst
[i
], sz
, f
) < 0) {
1306 sz
= sizeof (collate_chain_t
) * collinfo
.chain_count
;
1307 if (wr_category(chain
, sz
, f
) < 0) {
1310 sz
= sizeof (collate_large_t
) * collinfo
.large_count
;
1311 if (wr_category(large
, sz
, f
) < 0) {