2 * Copyright 2018 Nexenta Systems, Inc.
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.
34 #include <sys/cdefs.h>
35 __FBSDID("$FreeBSD$");
37 #include <sys/types.h>
48 #include "localedef.h"
52 _Static_assert(COLL_WEIGHTS_MAX == 10, "This code assumes a value of 10");
57 * It will be extremely helpful to the reader if they have access to
58 * the localedef and locale file format specifications available.
59 * Latest versions of these are available from www.opengroup.org.
61 * The design for the collation code is a bit complex. The goal is a
62 * single collation database as described in collate.h (in
63 * libc/port/locale). However, there are some other tidbits:
65 * a) The substitution entries are now a directly indexable array. A
66 * priority elsewhere in the table is taken as an index into the
67 * substitution table if it has a high bit (COLLATE_SUBST_PRIORITY)
68 * set. (The bit is cleared and the result is the index into the
71 * b) We eliminate duplicate entries into the substitution table.
72 * This saves a lot of space.
74 * c) The priorities for each level are "compressed", so that each
75 * sorting level has consecutively numbered priorities starting at 1.
76 * (O is reserved for the ignore priority.) This means sort levels
77 * which only have a few distinct priorities can represent the
78 * priority level in fewer bits, which makes the strxfrm output
81 * d) We record the total number of priorities so that strxfrm can
82 * figure out how many bytes to expand a numeric priority into.
84 * e) For the UNDEFINED pass (the last pass), we record the maximum
85 * number of bits needed to uniquely prioritize these entries, so that
86 * the last pass can also use smaller strxfrm output when possible.
88 * f) Priorities with the sign bit set are verboten. This works out
89 * because no active character set needs that bit to carry significant
90 * information once the character is in wide form.
92 * To process the entire data to make the database, we actually run
93 * multiple passes over the data.
95 * The first pass, which is done at parse time, identifies elements,
96 * substitutions, and such, and records them in priority order. As
97 * some priorities can refer to other priorities, using forward
98 * references, we use a table of references indicating whether the
99 * priority's value has been resolved, or whether it is still a
102 * The second pass walks over all the items in priority order, noting
103 * that they are used directly, and not just an indirect reference.
104 * This is done by creating a "weight" structure for the item. The
105 * weights are stashed in an RB tree sorted by relative "priority".
107 * The third pass walks over all the weight structures, in priority
108 * order, and assigns a new monotonically increasing (per sort level)
109 * weight value to them. These are the values that will actually be
110 * written to the file.
112 * The fourth pass just writes the data out.
116 * In order to resolve the priorities, we create a table of priorities.
117 * Entries in the table can be in one of three states.
119 * UNKNOWN is for newly allocated entries, and indicates that nothing
120 * is known about the priority. (For example, when new entries are created
121 * for collating-symbols, this is the value assigned for them until the
122 * collating symbol's order has been determined.
124 * RESOLVED is used for an entry where the priority indicates the final
127 * REFER is used for entries that reference other entries. Typically
128 * this is used for forward references. A collating-symbol can never
131 * The "pass" field is used during final resolution to aid in detection
132 * of referencing loops. (For example <A> depends on <B>, but <B> has its
133 * priority dependent on <A>.)
136 UNKNOWN, /* priority is totally unknown */
137 RESOLVED, /* priority value fully resolved */
138 REFER /* priority is a reference (index) */
141 typedef struct weight {
144 RB_ENTRY(weight) entry;
147 typedef struct priority {
154 #define NUM_WT collinfo.directive_count
157 * These are the abstract collating symbols, which are just a symbolic
158 * way to reference a priority.
163 RB_ENTRY(collsym) entry;
167 * These are also abstract collating symbols, but we allow them to have
168 * different priorities at different levels.
170 typedef struct collundef {
172 int32_t ref[COLL_WEIGHTS_MAX];
173 RB_ENTRY(collundef) entry;
177 * These are called "chains" in libc. This records the fact that two
178 * more characters should be treated as a single collating entity when
179 * they appear together. For example, in Spanish <C><h> gets collated
180 * as a character between <C> and <D>.
185 int32_t ref[COLL_WEIGHTS_MAX];
186 RB_ENTRY(collelem) rb_bysymbol;
187 RB_ENTRY(collelem) rb_byexpand;
191 * Individual characters have a sequence of weights as well.
193 typedef struct collchar {
195 int32_t ref[COLL_WEIGHTS_MAX];
196 RB_ENTRY(collchar) entry;
200 * Substitution entries. The key is itself a priority. Note that
201 * when we create one of these, we *automatically* wind up with a
202 * fully resolved priority for the key, because creation of
203 * substitutions creates a resolved priority at the same time.
205 typedef struct subst{
207 int32_t ref[COLLATE_STR_LEN];
208 RB_ENTRY(subst) entry;
209 RB_ENTRY(subst) entry_ref;
212 static RB_HEAD(collsyms, collsym) collsyms;
213 static RB_HEAD(collundefs, collundef) collundefs;
214 static RB_HEAD(elem_by_symbol, collelem) elem_by_symbol;
215 static RB_HEAD(elem_by_expand, collelem) elem_by_expand;
216 static RB_HEAD(collchars, collchar) collchars;
217 static RB_HEAD(substs, subst) substs[COLL_WEIGHTS_MAX];
218 static RB_HEAD(substs_ref, subst) substs_ref[COLL_WEIGHTS_MAX];
219 static RB_HEAD(weights, weight) weights[COLL_WEIGHTS_MAX];
220 static int32_t nweight[COLL_WEIGHTS_MAX];
223 * This is state tracking for the ellipsis token. Note that we start
224 * the initial values so that the ellipsis logic will think we got a
225 * magic starting value of NUL. It starts at minus one because the
226 * starting point is exclusive -- i.e. the starting point is not
227 * itself handled by the ellipsis code.
229 static int currorder = EOF;
230 static int lastorder = EOF;
231 static collelem_t *currelem;
232 static collchar_t *currchar;
233 static collundef_t *currundef;
234 static wchar_t ellipsis_start = 0;
235 static int32_t ellipsis_weights[COLL_WEIGHTS_MAX];
238 * We keep a running tally of weights.
240 static int nextpri = 1;
241 static int nextsubst[COLL_WEIGHTS_MAX] = { 0 };
244 * This array collects up the weights for each level.
246 static int32_t order_weights[COLL_WEIGHTS_MAX];
247 static int curr_weight = 0;
248 static int32_t subst_weights[COLLATE_STR_LEN];
249 static int curr_subst = 0;
252 * Some initial priority values.
254 static int32_t pri_undefined[COLL_WEIGHTS_MAX];
255 static int32_t pri_ignore;
257 static collate_info_t collinfo;
258 static int32_t subst_count[COLL_WEIGHTS_MAX];
259 static int32_t chain_count;
260 static int32_t large_count;
262 static collpri_t *prilist = NULL;
263 static int numpri = 0;
264 static int maxpri = 0;
266 static void start_order(int);
273 if (numpri >= maxpri) {
274 maxpri = maxpri ? maxpri * 2 : 1024;
275 prilist = realloc(prilist, sizeof (collpri_t) * maxpri);
276 if (prilist == NULL) {
277 fprintf(stderr,"out of memory");
280 for (i = numpri; i < maxpri; i++) {
281 prilist[i].res = UNKNOWN;
292 if ((ref < 0) || (ref > numpri)) {
296 return (&prilist[ref]);
300 set_pri(int32_t ref, int32_t v, res_t res)
306 if ((res == REFER) && ((v < 0) || (v >= numpri))) {
310 /* Resolve self references */
311 if ((res == REFER) && (ref == v)) {
316 if (pri->res != UNKNOWN) {
317 warn("repeated item in order list (first on %d)",
321 pri->lineno = lineno;
327 resolve_pri(int32_t ref)
330 static int32_t pass = 0;
334 while (pri->res == REFER) {
335 if (pri->pass == pass) {
336 /* report a line with the circular symbol */
337 lineno = pri->lineno;
338 fprintf(stderr,"circular reference in order list");
341 if ((pri->pri < 0) || (pri->pri >= numpri)) {
346 pri = &prilist[pri->pri];
349 if (pri->res == UNKNOWN) {
352 if (pri->res != RESOLVED)
359 weight_compare(const void *n1, const void *n2)
361 int32_t k1 = ((const weight_t *)n1)->pri;
362 int32_t k2 = ((const weight_t *)n2)->pri;
364 return (k1 < k2 ? -1 : k1 > k2 ? 1 : 0);
367 RB_GENERATE_STATIC(weights, weight, entry, weight_compare);
370 collsym_compare(const void *n1, const void *n2)
372 const collsym_t *c1 = n1;
373 const collsym_t *c2 = n2;
376 rv = strcmp(c1->name, c2->name);
377 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
380 RB_GENERATE_STATIC(collsyms, collsym, entry, collsym_compare);
383 collundef_compare(const void *n1, const void *n2)
385 const collundef_t *c1 = n1;
386 const collundef_t *c2 = n2;
389 rv = strcmp(c1->name, c2->name);
390 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
393 RB_GENERATE_STATIC(collundefs, collundef, entry, collundef_compare);
396 element_compare_symbol(const void *n1, const void *n2)
398 const collelem_t *c1 = n1;
399 const collelem_t *c2 = n2;
402 rv = strcmp(c1->symbol, c2->symbol);
403 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
406 RB_GENERATE_STATIC(elem_by_symbol, collelem, rb_bysymbol, element_compare_symbol);
409 element_compare_expand(const void *n1, const void *n2)
411 const collelem_t *c1 = n1;
412 const collelem_t *c2 = n2;
415 rv = wcscmp(c1->expand, c2->expand);
416 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
419 RB_GENERATE_STATIC(elem_by_expand, collelem, rb_byexpand, element_compare_expand);
422 collchar_compare(const void *n1, const void *n2)
424 wchar_t k1 = ((const collchar_t *)n1)->wc;
425 wchar_t k2 = ((const collchar_t *)n2)->wc;
427 return (k1 < k2 ? -1 : k1 > k2 ? 1 : 0);
430 RB_GENERATE_STATIC(collchars, collchar, entry, collchar_compare);
433 subst_compare(const void *n1, const void *n2)
435 int32_t k1 = ((const subst_t *)n1)->key;
436 int32_t k2 = ((const subst_t *)n2)->key;
438 return (k1 < k2 ? -1 : k1 > k2 ? 1 : 0);
441 RB_GENERATE_STATIC(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_GENERATE_STATIC(substs_ref, subst, entry_ref, subst_compare_ref);
463 RB_INIT(&collundefs);
465 RB_INIT(&elem_by_symbol);
467 RB_INIT(&elem_by_expand);
471 for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
473 RB_INIT(&substs_ref[i]);
474 RB_INIT(&weights[i]);
478 (void) memset(&collinfo, 0, sizeof (collinfo));
480 /* allocate some initial priorities */
481 pri_ignore = new_pri();
483 set_pri(pri_ignore, 0, RESOLVED);
485 for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
486 pri_undefined[i] = new_pri();
488 /* we will override this later */
489 set_pri(pri_undefined[i], COLLATE_MAX_PRIORITY, UNKNOWN);
494 define_collsym(char *name)
498 if ((sym = calloc(1, sizeof(*sym))) == NULL) {
499 fprintf(stderr,"out of memory");
503 sym->ref = new_pri();
505 if (RB_FIND(collsyms, &collsyms, sym) != NULL) {
507 * This should never happen because we are only called
508 * 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(1, sizeof(*ud))) == NULL) ||
545 ((ud->name = strdup(name)) == NULL)) {
546 fprintf(stderr,"out of memory");
550 for (i = 0; i < NUM_WT; i++) {
551 ud->ref[i] = new_pri();
553 RB_INSERT(collundefs, &collundefs, ud);
555 add_charmap_undefined(name);
560 get_collchar(wchar_t wc, int create)
567 cc = RB_FIND(collchars, &collchars, &srch);
568 if ((cc == NULL) && create) {
569 if ((cc = calloc(1, sizeof(*cc))) == NULL) {
570 fprintf(stderr, "out of memory");
573 for (i = 0; i < NUM_WT; i++) {
574 cc->ref[i] = new_pri();
577 RB_INSERT(collchars, &collchars, cc);
583 end_order_collsym(collsym_t *sym)
585 start_order(T_COLLSYM);
586 /* update the weight */
588 set_pri(sym->ref, nextpri, RESOLVED);
600 /* advance the priority/weight */
605 for (i = 0; i < NUM_WT; i++) {
606 if (((ref = order_weights[i]) < 0) ||
607 ((p = get_pri(ref)) == NULL) ||
609 /* unspecified weight is a self reference */
610 set_pri(currchar->ref[i], pri, RESOLVED);
612 set_pri(currchar->ref[i], ref, REFER);
614 order_weights[i] = -1;
617 /* leave a cookie trail in case next symbol is ellipsis */
618 ellipsis_start = currchar->wc + 1;
623 /* save off the weights were we can find them */
624 for (i = 0; i < NUM_WT; i++) {
625 ellipsis_weights[i] = order_weights[i];
626 order_weights[i] = -1;
631 if (currelem == NULL) {
634 for (i = 0; i < NUM_WT; i++) {
636 if (((ref = order_weights[i]) < 0) ||
637 ((p = get_pri(ref)) == NULL) ||
639 set_pri(currelem->ref[i], pri,
642 set_pri(currelem->ref[i], ref, REFER);
644 order_weights[i] = -1;
650 for (i = 0; i < NUM_WT; i++) {
651 if (((ref = order_weights[i]) < 0) ||
652 ((p = get_pri(ref)) == NULL) ||
654 set_pri(pri_undefined[i], -1, RESOLVED);
656 set_pri(pri_undefined[i], ref, REFER);
658 order_weights[i] = -1;
663 for (i = 0; i < NUM_WT; i++) {
664 if (((ref = order_weights[i]) < 0) ||
665 ((p = get_pri(ref)) == NULL) ||
667 set_pri(currundef->ref[i], pri, RESOLVED);
669 set_pri(currundef->ref[i], ref, REFER);
671 order_weights[i] = -1;
683 start_order(int type)
687 lastorder = currorder;
690 /* this is used to protect ELLIPSIS processing */
691 if ((lastorder == T_ELLIPSIS) && (type != T_CHAR)) {
692 fprintf(stderr, "character value expected");
695 for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
696 order_weights[i] = -1;
702 start_order_undefined(void)
704 start_order(T_UNDEFINED);
708 start_order_symbol(char *name)
710 currundef = get_collundef(name);
711 start_order(T_SYMBOL);
715 start_order_char(wchar_t wc)
723 * If we last saw an ellipsis, then we need to close the range.
724 * Handle that here. Note that we have to be careful because the
725 * items *inside* the range are treated exclusiveley to the items
726 * outside of the range. The ends of the range can have quite
727 * different weights than the range members.
729 if (lastorder == T_ELLIPSIS) {
732 if (wc < ellipsis_start) {
733 fprintf(stderr, "malformed range!");
736 while (ellipsis_start < wc) {
738 * pick all of the saved weights for the
739 * ellipsis. note that -1 encodes for the
740 * ellipsis itself, which means to take the
741 * current relative priority.
743 if ((cc = get_collchar(ellipsis_start, 1)) == NULL) {
747 for (i = 0; i < NUM_WT; i++) {
749 if (((ref = ellipsis_weights[i]) == -1) ||
750 ((p = get_pri(ref)) == NULL) ||
752 set_pri(cc->ref[i], nextpri, RESOLVED);
754 set_pri(cc->ref[i], ref, REFER);
756 ellipsis_weights[i] = 0;
763 currchar = get_collchar(wc, 1);
767 start_order_collelem(collelem_t *e)
769 start_order(T_COLLELEM);
774 start_order_ellipsis(void)
778 start_order(T_ELLIPSIS);
780 if (lastorder != T_CHAR) {
781 fprintf(stderr, "illegal starting point for range");
785 for (i = 0; i < NUM_WT; i++) {
786 ellipsis_weights[i] = order_weights[i];
791 define_collelem(char *name, wchar_t *wcs)
796 if (wcslen(wcs) >= COLLATE_STR_LEN) {
797 fprintf(stderr,"expanded collation element too long");
801 if ((e = calloc(1, sizeof(*e))) == NULL) {
802 fprintf(stderr, "out of memory");
809 * This is executed before the order statement, so we don't
810 * know how many priorities we *really* need. We allocate one
811 * for each possible weight. Not a big deal, as collating-elements
812 * prove to be quite rare.
814 for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
815 e->ref[i] = new_pri();
818 /* A character sequence can only reduce to one element. */
819 if ((RB_FIND(elem_by_symbol, &elem_by_symbol, e) != NULL) ||
820 (RB_FIND(elem_by_expand, &elem_by_expand, e) != NULL)) {
821 fprintf(stderr, "duplicate collating element definition");
825 RB_INSERT(elem_by_symbol, &elem_by_symbol, e);
826 RB_INSERT(elem_by_expand, &elem_by_expand, e);
830 add_order_bit(int kw)
832 uint8_t bit = DIRECTIVE_UNDEF;
836 bit = DIRECTIVE_FORWARD;
839 bit = DIRECTIVE_BACKWARD;
842 bit = DIRECTIVE_POSITION;
848 collinfo.directive[collinfo.directive_count] |= bit;
852 add_order_directive(void)
854 if (collinfo.directive_count >= COLL_WEIGHTS_MAX) {
855 fprintf(stderr, "too many directives (max %d)\n", COLL_WEIGHTS_MAX);
858 collinfo.directive_count++;
862 add_order_pri(int32_t ref)
864 if (curr_weight >= NUM_WT) {
865 fprintf(stderr, "too many weights (max %d)\n", NUM_WT);
868 order_weights[curr_weight] = ref;
873 add_order_collsym(collsym_t *s)
875 add_order_pri(s->ref);
879 add_order_char(wchar_t wc)
883 if ((cc = get_collchar(wc, 1)) == NULL) {
888 add_order_pri(cc->ref[curr_weight]);
892 add_order_collelem(collelem_t *e)
894 add_order_pri(e->ref[curr_weight]);
898 add_order_ignore(void)
900 add_order_pri(pri_ignore);
904 add_order_symbol(char *sym)
907 if ((c = get_collundef(sym)) == NULL) {
911 add_order_pri(c->ref[curr_weight]);
915 add_order_ellipsis(void)
917 /* special NULL value indicates self reference */
922 add_order_subst(void)
928 (void) memset(&srch, 0, sizeof (srch));
929 for (i = 0; i < curr_subst; i++) {
930 srch.ref[i] = subst_weights[i];
931 subst_weights[i] = 0;
933 s = RB_FIND(substs_ref, &substs_ref[curr_weight], &srch);
936 if ((s = calloc(1, sizeof(*s))) == NULL) {
937 fprintf(stderr,"out of memory");
943 * We use a self reference for our key, but we set a
944 * high bit to indicate that this is a substitution
945 * reference. This will expedite table lookups later,
946 * and prevent table lookups for situations that don't
947 * require it. (In short, its a big win, because we
948 * can skip a lot of binary searching.)
951 (nextsubst[curr_weight] | COLLATE_SUBST_PRIORITY),
953 nextsubst[curr_weight] += 1;
955 for (i = 0; i < curr_subst; i++) {
956 s->ref[i] = srch.ref[i];
959 RB_INSERT(substs_ref, &substs_ref[curr_weight], s);
961 if (RB_FIND(substs, &substs[curr_weight], s) != NULL) {
965 RB_INSERT(substs, &substs[curr_weight], s);
971 * We are using the current (unique) priority as a search key
972 * in the substitution table.
974 add_order_pri(s->key);
978 add_subst_pri(int32_t ref)
980 if (curr_subst >= COLLATE_STR_LEN) {
981 fprintf(stderr,"substitution string is too long");
984 subst_weights[curr_subst] = ref;
989 add_subst_char(wchar_t wc)
994 if (((cc = get_collchar(wc, 1)) == NULL) ||
999 /* we take the weight for the character at that position */
1000 add_subst_pri(cc->ref[curr_weight]);
1004 add_subst_collelem(collelem_t *e)
1006 add_subst_pri(e->ref[curr_weight]);
1010 add_subst_collsym(collsym_t *s)
1012 add_subst_pri(s->ref);
1016 add_subst_symbol(char *ptr)
1020 if ((cu = get_collundef(ptr)) != NULL) {
1021 add_subst_pri(cu->ref[curr_weight]);
1026 add_weight(int32_t ref, int pass)
1031 srch.pri = resolve_pri(ref);
1033 /* No translation of ignores */
1037 /* Substitution priorities are not weights */
1038 if (srch.pri & COLLATE_SUBST_PRIORITY)
1041 if (RB_FIND(weights, &weights[pass], &srch) != NULL)
1044 if ((w = calloc(1, sizeof(*w))) == NULL) {
1045 fprintf(stderr, "out of memory");
1049 RB_INSERT(weights, &weights[pass], w);
1053 add_weights(int32_t *refs)
1056 for (i = 0; i < NUM_WT; i++) {
1057 add_weight(refs[i], i);
1062 get_weight(int32_t ref, int pass)
1068 pri = resolve_pri(ref);
1069 if (pri & COLLATE_SUBST_PRIORITY) {
1076 if ((w = RB_FIND(weights, &weights[pass], &srch)) == NULL) {
1084 wsncpy(wchar_t *s1, const wchar_t *s2, size_t n)
1089 while (--n > 0 && (*s1++ = htote(*s2++)) != 0)
1097 #define RB_COUNT(x, name, head, cnt) do { \
1099 RB_FOREACH(x, name, (head)) { \
1104 #define RB_NUMNODES(type, name, head, cnt) do { \
1107 RB_FOREACH(t, name, head) { \
1122 char vers[COLLATE_STR_LEN];
1123 collate_char_t chars[UCHAR_MAX + 1];
1124 collate_large_t *large;
1125 collate_subst_t *subst[COLL_WEIGHTS_MAX];
1126 collate_chain_t *chain;
1129 * We have to run through a preliminary pass to identify all the
1130 * weights that we use for each sorting level.
1132 for (i = 0; i < NUM_WT; i++) {
1133 add_weight(pri_ignore, i);
1135 for (i = 0; i < NUM_WT; i++) {
1136 RB_FOREACH(sb, substs, &substs[i]) {
1137 for (j = 0; sb->ref[j]; j++) {
1138 add_weight(sb->ref[j], i);
1142 RB_FOREACH(ce, elem_by_expand, &elem_by_expand) {
1143 add_weights(ce->ref);
1145 RB_FOREACH(cc, collchars, &collchars) {
1146 add_weights(cc->ref);
1150 * Now we walk the entire set of weights, removing the gaps
1151 * in the weights. This gives us optimum usage. The walk
1152 * occurs in priority.
1154 for (i = 0; i < NUM_WT; i++) {
1156 RB_FOREACH(w, weights, &weights[i]) {
1157 w->opt = nweight[i];
1162 (void) memset(&chars, 0, sizeof (chars));
1163 (void) memset(vers, 0, COLLATE_STR_LEN);
1164 (void) strlcpy(vers, COLLATE_VERSION, sizeof (vers));
1167 * We need to make sure we arrange for the UNDEFINED field
1168 * to show up. Also, set the total weight counts.
1170 for (i = 0; i < NUM_WT; i++) {
1171 if (resolve_pri(pri_undefined[i]) == -1) {
1172 set_pri(pri_undefined[i], -1, RESOLVED);
1173 /* they collate at the end of everything else */
1174 collinfo.undef_pri[i] = htote(COLLATE_MAX_PRIORITY);
1176 collinfo.pri_count[i] = htote(nweight[i]);
1179 collinfo.pri_count[NUM_WT] = htote(max_wide());
1180 collinfo.undef_pri[NUM_WT] = htote(COLLATE_MAX_PRIORITY);
1181 collinfo.directive[NUM_WT] = DIRECTIVE_UNDEFINED;
1184 * Ordinary character priorities
1186 for (i = 0; i <= UCHAR_MAX; i++) {
1187 if ((cc = get_collchar(i, 0)) != NULL) {
1188 for (j = 0; j < NUM_WT; j++) {
1190 htote(get_weight(cc->ref[j], j));
1193 for (j = 0; j < NUM_WT; j++) {
1195 htote(get_weight(pri_undefined[j], j));
1198 * Per POSIX, for undefined characters, we
1199 * also have to add a last item, which is the
1202 chars[i].pri[NUM_WT] = htote(i);
1207 * Substitution tables
1209 for (i = 0; i < NUM_WT; i++) {
1210 collate_subst_t *st = NULL;
1212 RB_COUNT(temp, substs, &substs[i], n);
1214 if ((st = calloc(n, sizeof(collate_subst_t))) == NULL) {
1215 fprintf(stderr, "out of memory");
1219 RB_FOREACH(sb, substs, &substs[i]) {
1220 if ((st[n].key = resolve_pri(sb->key)) < 0) {
1221 /* by definition these resolve! */
1224 if (st[n].key != (n | COLLATE_SUBST_PRIORITY)) {
1227 st[n].key = htote(st[n].key);
1228 for (j = 0; sb->ref[j]; j++) {
1229 st[n].pri[j] = htote(get_weight(sb->ref[j],
1234 if (n != subst_count[i])
1241 * Chains, i.e. collating elements
1243 RB_NUMNODES(collelem_t, elem_by_expand, &elem_by_expand, chain_count);
1244 chain = calloc(chain_count, sizeof(collate_chain_t));
1245 if (chain == NULL) {
1246 fprintf(stderr, "out of memory");
1250 RB_FOREACH(ce, elem_by_expand, &elem_by_expand) {
1251 (void) wsncpy(chain[n].str, ce->expand, COLLATE_STR_LEN);
1252 for (i = 0; i < NUM_WT; i++) {
1253 chain[n].pri[i] = htote(get_weight(ce->ref[i], i));
1257 if (n != chain_count)
1261 * Large (> UCHAR_MAX) character priorities
1263 RB_NUMNODES(collchar_t, collchars, &collchars, n);
1264 large = calloc(n, sizeof(collate_large_t));
1265 if (large == NULL) {
1266 fprintf(stderr, "out of memory");
1271 RB_FOREACH(cc, collchars, &collchars) {
1273 /* we already gathered those */
1274 if (cc->wc <= UCHAR_MAX)
1276 for (j = 0; j < NUM_WT; j++) {
1277 if ((pri = get_weight(cc->ref[j], j)) < 0) {
1280 if (undef && (pri >= 0)) {
1281 /* if undefined, then all priorities are */
1284 large[i].pri.pri[j] = htote(pri);
1288 large[i].val = htote(cc->wc);
1293 if ((f = open_category()) == NULL) {
1297 /* Time to write the entire data set out */
1299 for (i = 0; i < NUM_WT; i++)
1300 collinfo.subst_count[i] = htote(subst_count[i]);
1301 collinfo.chain_count = htote(chain_count);
1302 collinfo.large_count = htote(large_count);
1304 if ((wr_category(vers, COLLATE_STR_LEN, f) < 0) ||
1305 (wr_category(&collinfo, sizeof (collinfo), f) < 0) ||
1306 (wr_category(&chars, sizeof (chars), f) < 0)) {
1310 for (i = 0; i < NUM_WT; i++) {
1311 sz = sizeof (collate_subst_t) * subst_count[i];
1312 if (wr_category(subst[i], sz, f) < 0) {
1316 sz = sizeof (collate_chain_t) * chain_count;
1317 if (wr_category(chain, sz, f) < 0) {
1320 sz = sizeof (collate_large_t) * large_count;
1321 if (wr_category(large, sz, f) < 0) {