2 * This file and its contents are supplied under the terms of the
3 * Common Development and Distribution License ("CDDL"), version 1.0.
4 * You may only use this file in accordance with the terms of version
7 * A full copy of the text of the CDDL should have accompanied this
8 * source. A copy of the CDDL is also available via the Internet at
9 * http://www.illumos.org/license/CDDL.
13 * Copyright 2010 Nexenta Systems, Inc. All rights reserved.
14 * Copyright 2015 John Marino <draco@marino.st>
18 * LC_COLLATE database generation routines for localedef.
26 #include <sys/types.h>
31 #include "localedef.h"
37 * Work around buildworld bootstrapping from older systems whos limits.h
38 * sets COLL_WEIGHTS_MAX to 0.
40 #if COLL_WEIGHTS_MAX == 0
41 #undef COLL_WEIGHTS_MAX
42 #define COLL_WEIGHTS_MAX 10
48 * It will be extremely helpful to the reader if they have access to
49 * the localedef and locale file format specifications available.
50 * Latest versions of these are available from www.opengroup.org.
52 * The design for the collation code is a bit complex. The goal is a
53 * single collation database as described in collate.h (in
54 * libc/port/locale). However, there are some other tidbits:
56 * a) The substitution entries are now a directly indexable array. A
57 * priority elsewhere in the table is taken as an index into the
58 * substitution table if it has a high bit (COLLATE_SUBST_PRIORITY)
59 * set. (The bit is cleared and the result is the index into the
62 * b) We eliminate duplicate entries into the substitution table.
63 * This saves a lot of space.
65 * c) The priorities for each level are "compressed", so that each
66 * sorting level has consecutively numbered priorities starting at 1.
67 * (O is reserved for the ignore priority.) This means sort levels
68 * which only have a few distinct priorities can represent the
69 * priority level in fewer bits, which makes the strxfrm output
72 * d) We record the total number of priorities so that strxfrm can
73 * figure out how many bytes to expand a numeric priority into.
75 * e) For the UNDEFINED pass (the last pass), we record the maximum
76 * number of bits needed to uniquely prioritize these entries, so that
77 * the last pass can also use smaller strxfrm output when possible.
79 * f) Priorities with the sign bit set are verboten. This works out
80 * because no active character set needs that bit to carry significant
81 * information once the character is in wide form.
83 * To process the entire data to make the database, we actually run
84 * multiple passes over the data.
86 * The first pass, which is done at parse time, identifies elements,
87 * substitutions, and such, and records them in priority order. As
88 * some priorities can refer to other priorities, using forward
89 * references, we use a table of references indicating whether the
90 * priority's value has been resolved, or whether it is still a
93 * The second pass walks over all the items in priority order, noting
94 * that they are used directly, and not just an indirect reference.
95 * This is done by creating a "weight" structure for the item. The
96 * weights are stashed in an AVL tree sorted by relative "priority".
98 * The third pass walks over all the weight structures, in priority
99 * order, and assigns a new monotonically increasing (per sort level)
100 * weight value to them. These are the values that will actually be
101 * written to the file.
103 * The fourth pass just writes the data out.
107 * In order to resolve the priorities, we create a table of priorities.
108 * Entries in the table can be in one of three states.
110 * UNKNOWN is for newly allocated entries, and indicates that nothing
111 * is known about the priority. (For example, when new entries are created
112 * for collating-symbols, this is the value assigned for them until the
113 * collating symbol's order has been determined.
115 * RESOLVED is used for an entry where the priority indicates the final
118 * REFER is used for entries that reference other entries. Typically
119 * this is used for forward references. A collating-symbol can never
122 * The "pass" field is used during final resolution to aid in detection
123 * of referencing loops. (For example <A> depends on <B>, but <B> has its
124 * priority dependent on <A>.)
127 UNKNOWN, /* priority is totally unknown */
128 RESOLVED, /* priority value fully resolved */
129 REFER /* priority is a reference (index) */
132 typedef struct weight {
138 typedef struct priority {
145 #define NUM_WT collinfo.directive_count
148 * These are the abstract collating symbols, which are just a symbolic
149 * way to reference a priority.
158 * These are also abstract collating symbols, but we allow them to have
159 * different priorities at different levels.
161 typedef struct collundef {
163 int32_t ref[COLL_WEIGHTS_MAX];
168 * These are called "chains" in libc. This records the fact that two
169 * more characters should be treated as a single collating entity when
170 * they appear together. For example, in Spanish <C><h> gets collated
171 * as a character between <C> and <D>.
176 int32_t ref[COLL_WEIGHTS_MAX];
177 avl_node_t avl_bysymbol;
178 avl_node_t avl_byexpand;
182 * Individual characters have a sequence of weights as well.
184 typedef struct collchar {
186 int32_t ref[COLL_WEIGHTS_MAX];
191 * Substitution entries. The key is itself a priority. Note that
192 * when we create one of these, we *automatically* wind up with a
193 * fully resolved priority for the key, because creation of
194 * substitutions creates a resolved priority at the same time.
198 int32_t ref[COLLATE_STR_LEN];
203 static avl_tree_t collsyms;
204 static avl_tree_t collundefs;
205 static avl_tree_t elem_by_symbol;
206 static avl_tree_t elem_by_expand;
207 static avl_tree_t collchars;
208 static avl_tree_t substs[COLL_WEIGHTS_MAX];
209 static avl_tree_t substs_ref[COLL_WEIGHTS_MAX];
210 static avl_tree_t weights[COLL_WEIGHTS_MAX];
211 static int32_t nweight[COLL_WEIGHTS_MAX];
214 * This is state tracking for the ellipsis token. Note that we start
215 * the initial values so that the ellipsis logic will think we got a
216 * magic starting value of NUL. It starts at minus one because the
217 * starting point is exclusive -- i.e. the starting point is not
218 * itself handled by the ellipsis code.
220 static int currorder = EOF;
221 static int lastorder = EOF;
222 static collelem_t *currelem;
223 static collchar_t *currchar;
224 static collundef_t *currundef;
225 static wchar_t ellipsis_start = 0;
226 static int32_t ellipsis_weights[COLL_WEIGHTS_MAX];
229 * We keep a running tally of weights.
231 static int nextpri = 1;
232 static int nextsubst[COLL_WEIGHTS_MAX] = { 0 };
235 * This array collects up the weights for each level.
237 static int32_t order_weights[COLL_WEIGHTS_MAX];
238 static int curr_weight = 0;
239 static int32_t subst_weights[COLLATE_STR_LEN];
240 static int curr_subst = 0;
243 * Some initial priority values.
245 static int32_t pri_undefined[COLL_WEIGHTS_MAX];
246 static int32_t pri_ignore;
248 static collate_info_t collinfo;
250 static collpri_t *prilist = NULL;
251 static int numpri = 0;
252 static int maxpri = 0;
254 static void start_order(int);
261 if (numpri >= maxpri) {
262 maxpri = maxpri ? maxpri * 2 : 1024;
263 prilist = realloc(prilist, sizeof (collpri_t) * maxpri);
264 if (prilist == NULL) {
265 fprintf(stderr,"out of memory");
268 for (i = numpri; i < maxpri; i++) {
269 prilist[i].res = UNKNOWN;
280 if ((ref < 0) || (ref > numpri)) {
284 return (&prilist[ref]);
288 set_pri(int32_t ref, int32_t v, res_t res)
294 if ((res == REFER) && ((v < 0) || (v >= numpri))) {
298 /* Resolve self references */
299 if ((res == REFER) && (ref == v)) {
304 if (pri->res != UNKNOWN) {
305 warn("repeated item in order list (first on %d)",
309 pri->lineno = lineno;
315 resolve_pri(int32_t ref)
318 static int32_t pass = 0;
322 while (pri->res == REFER) {
323 if (pri->pass == pass) {
324 /* report a line with the circular symbol */
325 lineno = pri->lineno;
326 fprintf(stderr,"circular reference in order list");
329 if ((pri->pri < 0) || (pri->pri >= numpri)) {
334 pri = &prilist[pri->pri];
337 if (pri->res == UNKNOWN) {
340 if (pri->res != RESOLVED)
347 weight_compare(const void *n1, const void *n2)
349 int32_t k1 = ((const weight_t *)n1)->pri;
350 int32_t k2 = ((const weight_t *)n2)->pri;
352 return (k1 < k2 ? -1 : k1 > k2 ? 1 : 0);
356 collsym_compare(const void *n1, const void *n2)
358 const collsym_t *c1 = n1;
359 const collsym_t *c2 = n2;
362 rv = strcmp(c1->name, c2->name);
363 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
367 collundef_compare(const void *n1, const void *n2)
369 const collundef_t *c1 = n1;
370 const collundef_t *c2 = n2;
373 rv = strcmp(c1->name, c2->name);
374 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
378 element_compare_symbol(const void *n1, const void *n2)
380 const collelem_t *c1 = n1;
381 const collelem_t *c2 = n2;
384 rv = strcmp(c1->symbol, c2->symbol);
385 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
389 element_compare_expand(const void *n1, const void *n2)
391 const collelem_t *c1 = n1;
392 const collelem_t *c2 = n2;
395 rv = wcscmp(c1->expand, c2->expand);
396 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
400 collchar_compare(const void *n1, const void *n2)
402 wchar_t k1 = ((const collchar_t *)n1)->wc;
403 wchar_t k2 = ((const collchar_t *)n2)->wc;
405 return (k1 < k2 ? -1 : k1 > k2 ? 1 : 0);
409 subst_compare(const void *n1, const void *n2)
411 int32_t k1 = ((const subst_t *)n1)->key;
412 int32_t k2 = ((const subst_t *)n2)->key;
414 return (k1 < k2 ? -1 : k1 > k2 ? 1 : 0);
417 #pragma GCC diagnostic push
418 #pragma GCC diagnostic ignored "-Wcast-qual"
421 subst_compare_ref(const void *n1, const void *n2)
423 int32_t *c1 = ((subst_t *)n1)->ref;
424 int32_t *c2 = ((subst_t *)n2)->ref;
427 rv = wcscmp((wchar_t *)c1, (wchar_t *)c2);
428 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
431 #pragma GCC diagnostic pop
438 avl_create(&collsyms, collsym_compare, sizeof (collsym_t),
439 offsetof(collsym_t, avl));
441 avl_create(&collundefs, collundef_compare, sizeof (collsym_t),
442 offsetof(collundef_t, avl));
444 avl_create(&elem_by_symbol, element_compare_symbol, sizeof (collelem_t),
445 offsetof(collelem_t, avl_bysymbol));
446 avl_create(&elem_by_expand, element_compare_expand, sizeof (collelem_t),
447 offsetof(collelem_t, avl_byexpand));
449 avl_create(&collchars, collchar_compare, sizeof (collchar_t),
450 offsetof(collchar_t, avl));
452 for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
453 avl_create(&substs[i], subst_compare, sizeof (subst_t),
454 offsetof(subst_t, avl));
455 avl_create(&substs_ref[i], subst_compare_ref,
456 sizeof (subst_t), offsetof(subst_t, avl_ref));
457 avl_create(&weights[i], weight_compare, sizeof (weight_t),
458 offsetof(weight_t, avl));
462 (void) memset(&collinfo, 0, sizeof (collinfo));
464 /* allocate some initial priorities */
465 pri_ignore = new_pri();
467 set_pri(pri_ignore, 0, RESOLVED);
469 for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
470 pri_undefined[i] = new_pri();
472 /* we will override this later */
473 set_pri(pri_undefined[i], COLLATE_MAX_PRIORITY, UNKNOWN);
478 define_collsym(char *name)
483 if ((sym = calloc(sizeof (*sym), 1)) == NULL) {
484 fprintf(stderr,"out of memory");
488 sym->ref = new_pri();
490 if (avl_find(&collsyms, sym, &where) != NULL) {
492 * This should never happen because we are only called
493 * for undefined symbols.
498 avl_insert(&collsyms, sym, where);
502 lookup_collsym(char *name)
507 return (avl_find(&collsyms, &srch, NULL));
511 lookup_collelem(char *symbol)
515 srch.symbol = symbol;
516 return (avl_find(&elem_by_symbol, &srch, NULL));
520 get_collundef(char *name)
528 if ((ud = avl_find(&collundefs, &srch, &where)) == NULL) {
529 if (((ud = calloc(sizeof (*ud), 1)) == NULL) ||
530 ((ud->name = strdup(name)) == NULL)) {
531 fprintf(stderr,"out of memory");
534 for (i = 0; i < NUM_WT; i++) {
535 ud->ref[i] = new_pri();
537 avl_insert(&collundefs, ud, where);
539 add_charmap_undefined(name);
544 get_collchar(wchar_t wc, int create)
552 cc = avl_find(&collchars, &srch, &where);
553 if ((cc == NULL) && create) {
554 if ((cc = calloc(sizeof (*cc), 1)) == NULL) {
555 fprintf(stderr, "out of memory");
558 for (i = 0; i < NUM_WT; i++) {
559 cc->ref[i] = new_pri();
562 avl_insert(&collchars, cc, where);
568 end_order_collsym(collsym_t *sym)
570 start_order(T_COLLSYM);
571 /* update the weight */
573 set_pri(sym->ref, nextpri, RESOLVED);
585 /* advance the priority/weight */
590 for (i = 0; i < NUM_WT; i++) {
591 if (((ref = order_weights[i]) < 0) ||
592 ((p = get_pri(ref)) == NULL) ||
594 /* unspecified weight is a self reference */
595 set_pri(currchar->ref[i], pri, RESOLVED);
597 set_pri(currchar->ref[i], ref, REFER);
599 order_weights[i] = -1;
602 /* leave a cookie trail in case next symbol is ellipsis */
603 ellipsis_start = currchar->wc + 1;
608 /* save off the weights were we can find them */
609 for (i = 0; i < NUM_WT; i++) {
610 ellipsis_weights[i] = order_weights[i];
611 order_weights[i] = -1;
616 if (currelem == NULL) {
619 for (i = 0; i < NUM_WT; i++) {
621 if (((ref = order_weights[i]) < 0) ||
622 ((p = get_pri(ref)) == NULL) ||
624 set_pri(currelem->ref[i], pri,
627 set_pri(currelem->ref[i], ref, REFER);
629 order_weights[i] = -1;
635 for (i = 0; i < NUM_WT; i++) {
636 if (((ref = order_weights[i]) < 0) ||
637 ((p = get_pri(ref)) == NULL) ||
639 set_pri(pri_undefined[i], -1, RESOLVED);
641 set_pri(pri_undefined[i], ref, REFER);
643 order_weights[i] = -1;
648 for (i = 0; i < NUM_WT; i++) {
649 if (((ref = order_weights[i]) < 0) ||
650 ((p = get_pri(ref)) == NULL) ||
652 set_pri(currundef->ref[i], pri, RESOLVED);
654 set_pri(currundef->ref[i], ref, REFER);
656 order_weights[i] = -1;
668 start_order(int type)
672 lastorder = currorder;
675 /* this is used to protect ELLIPSIS processing */
676 if ((lastorder == T_ELLIPSIS) && (type != T_CHAR)) {
677 fprintf(stderr, "character value expected");
680 for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
681 order_weights[i] = -1;
687 start_order_undefined(void)
689 start_order(T_UNDEFINED);
693 start_order_symbol(char *name)
695 currundef = get_collundef(name);
696 start_order(T_SYMBOL);
700 start_order_char(wchar_t wc)
708 * If we last saw an ellipsis, then we need to close the range.
709 * Handle that here. Note that we have to be careful because the
710 * items *inside* the range are treated exclusiveley to the items
711 * outside of the range. The ends of the range can have quite
712 * different weights than the range members.
714 if (lastorder == T_ELLIPSIS) {
717 if (wc < ellipsis_start) {
718 fprintf(stderr, "malformed range!");
721 while (ellipsis_start < wc) {
723 * pick all of the saved weights for the
724 * ellipsis. note that -1 encodes for the
725 * ellipsis itself, which means to take the
726 * current relative priority.
728 if ((cc = get_collchar(ellipsis_start, 1)) == NULL) {
732 for (i = 0; i < NUM_WT; i++) {
734 if (((ref = ellipsis_weights[i]) == -1) ||
735 ((p = get_pri(ref)) == NULL) ||
737 set_pri(cc->ref[i], nextpri, RESOLVED);
739 set_pri(cc->ref[i], ref, REFER);
741 ellipsis_weights[i] = 0;
748 currchar = get_collchar(wc, 1);
752 start_order_collelem(collelem_t *e)
754 start_order(T_COLLELEM);
759 start_order_ellipsis(void)
763 start_order(T_ELLIPSIS);
765 if (lastorder != T_CHAR) {
766 fprintf(stderr, "illegal starting point for range");
770 for (i = 0; i < NUM_WT; i++) {
771 ellipsis_weights[i] = order_weights[i];
776 define_collelem(char *name, wchar_t *wcs)
783 if (wcslen(wcs) >= COLLATE_STR_LEN) {
784 fprintf(stderr,"expanded collation element too long");
788 if ((e = calloc(sizeof (*e), 1)) == NULL) {
789 fprintf(stderr, "out of memory");
796 * This is executed before the order statement, so we don't
797 * know how many priorities we *really* need. We allocate one
798 * for each possible weight. Not a big deal, as collating-elements
799 * prove to be quite rare.
801 for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
802 e->ref[i] = new_pri();
805 /* A character sequence can only reduce to one element. */
806 if ((avl_find(&elem_by_symbol, e, &where1) != NULL) ||
807 (avl_find(&elem_by_expand, e, &where2) != NULL)) {
808 fprintf(stderr, "duplicate collating element definition");
811 avl_insert(&elem_by_symbol, e, where1);
812 avl_insert(&elem_by_expand, e, where2);
816 add_order_bit(int kw)
818 uint8_t bit = DIRECTIVE_UNDEF;
822 bit = DIRECTIVE_FORWARD;
825 bit = DIRECTIVE_BACKWARD;
828 bit = DIRECTIVE_POSITION;
834 collinfo.directive[collinfo.directive_count] |= bit;
838 add_order_directive(void)
840 if (collinfo.directive_count >= COLL_WEIGHTS_MAX) {
841 fprintf(stderr,"too many directives (max %d)", COLL_WEIGHTS_MAX);
843 collinfo.directive_count++;
847 add_order_pri(int32_t ref)
849 if (curr_weight >= NUM_WT) {
850 fprintf(stderr,"too many weights (max %d)", NUM_WT);
853 order_weights[curr_weight] = ref;
858 add_order_collsym(collsym_t *s)
860 add_order_pri(s->ref);
864 add_order_char(wchar_t wc)
868 if ((cc = get_collchar(wc, 1)) == NULL) {
873 add_order_pri(cc->ref[curr_weight]);
877 add_order_collelem(collelem_t *e)
879 add_order_pri(e->ref[curr_weight]);
883 add_order_ignore(void)
885 add_order_pri(pri_ignore);
889 add_order_symbol(char *sym)
892 if ((c = get_collundef(sym)) == NULL) {
896 add_order_pri(c->ref[curr_weight]);
900 add_order_ellipsis(void)
902 /* special NULL value indicates self reference */
907 add_order_subst(void)
914 (void) memset(&srch, 0, sizeof (srch));
915 for (i = 0; i < curr_subst; i++) {
916 srch.ref[i] = subst_weights[i];
917 subst_weights[i] = 0;
919 s = avl_find(&substs_ref[curr_weight], &srch, &where);
922 if ((s = calloc(sizeof (*s), 1)) == NULL) {
923 fprintf(stderr,"out of memory");
929 * We use a self reference for our key, but we set a
930 * high bit to indicate that this is a substitution
931 * reference. This will expedite table lookups later,
932 * and prevent table lookups for situations that don't
933 * require it. (In short, its a big win, because we
934 * can skip a lot of binary searching.)
937 (nextsubst[curr_weight] | COLLATE_SUBST_PRIORITY),
939 nextsubst[curr_weight] += 1;
941 for (i = 0; i < curr_subst; i++) {
942 s->ref[i] = srch.ref[i];
945 avl_insert(&substs_ref[curr_weight], s, where);
947 if (avl_find(&substs[curr_weight], s, &where) != NULL) {
951 avl_insert(&substs[curr_weight], s, where);
957 * We are using the current (unique) priority as a search key
958 * in the substitution table.
960 add_order_pri(s->key);
964 add_subst_pri(int32_t ref)
966 if (curr_subst >= COLLATE_STR_LEN) {
967 fprintf(stderr,"substitution string is too long");
970 subst_weights[curr_subst] = ref;
975 add_subst_char(wchar_t wc)
980 if (((cc = get_collchar(wc, 1)) == NULL) ||
985 /* we take the weight for the character at that position */
986 add_subst_pri(cc->ref[curr_weight]);
990 add_subst_collelem(collelem_t *e)
992 add_subst_pri(e->ref[curr_weight]);
996 add_subst_collsym(collsym_t *s)
998 add_subst_pri(s->ref);
1002 add_subst_symbol(char *ptr)
1006 if ((cu = get_collundef(ptr)) != NULL) {
1007 add_subst_pri(cu->ref[curr_weight]);
1012 add_weight(int32_t ref, int pass)
1018 srch.pri = resolve_pri(ref);
1020 /* No translation of ignores */
1024 /* Substitution priorities are not weights */
1025 if (srch.pri & COLLATE_SUBST_PRIORITY)
1028 if (avl_find(&weights[pass], &srch, &where) != NULL)
1031 if ((w = calloc(sizeof (*w), 1)) == NULL) {
1032 fprintf(stderr, "out of memory");
1036 avl_insert(&weights[pass], w, where);
1040 add_weights(int32_t *refs)
1043 for (i = 0; i < NUM_WT; i++) {
1044 add_weight(refs[i], i);
1049 get_weight(int32_t ref, int pass)
1055 pri = resolve_pri(ref);
1056 if (pri & COLLATE_SUBST_PRIORITY) {
1063 if ((w = avl_find(&weights[pass], &srch, NULL)) == NULL) {
1071 wsncpy(wchar_t *s1, const wchar_t *s2, size_t n)
1076 while (--n > 0 && (*s1++ = *s2++) != 0)
1094 char vers[COLLATE_STR_LEN];
1095 collate_char_t chars[UCHAR_MAX + 1];
1096 collate_large_t *large;
1097 collate_subst_t *subst[COLL_WEIGHTS_MAX];
1098 collate_chain_t *chain;
1101 * We have to run throught a preliminary pass to identify all the
1102 * weights that we use for each sorting level.
1104 for (i = 0; i < NUM_WT; i++) {
1105 add_weight(pri_ignore, i);
1107 for (i = 0; i < NUM_WT; i++) {
1108 for (sb = avl_first(&substs[i]); sb;
1109 sb = AVL_NEXT(&substs[i], sb)) {
1110 for (j = 0; sb->ref[j]; j++) {
1111 add_weight(sb->ref[j], i);
1115 for (ce = avl_first(&elem_by_expand);
1117 ce = AVL_NEXT(&elem_by_expand, ce)) {
1118 add_weights(ce->ref);
1120 for (cc = avl_first(&collchars); cc; cc = AVL_NEXT(&collchars, cc)) {
1121 add_weights(cc->ref);
1125 * Now we walk the entire set of weights, removing the gaps
1126 * in the weights. This gives us optimum usage. The walk
1127 * occurs in priority.
1129 for (i = 0; i < NUM_WT; i++) {
1131 for (w = avl_first(&weights[i]); w;
1132 w = AVL_NEXT(&weights[i], w)) {
1133 w->opt = nweight[i];
1138 (void) memset(&chars, 0, sizeof (chars));
1139 (void) memset(vers, 0, COLLATE_STR_LEN);
1140 (void) strlcpy(vers, COLLATE_VERSION, sizeof (vers));
1143 * We need to make sure we arrange for the UNDEFINED field
1144 * to show up. Also, set the total weight counts.
1146 for (i = 0; i < NUM_WT; i++) {
1147 if (resolve_pri(pri_undefined[i]) == -1) {
1148 set_pri(pri_undefined[i], -1, RESOLVED);
1149 /* they collate at the end of everything else */
1150 collinfo.undef_pri[i] = COLLATE_MAX_PRIORITY;
1152 collinfo.pri_count[i] = nweight[i];
1155 collinfo.pri_count[NUM_WT] = max_wide();
1156 collinfo.undef_pri[NUM_WT] = COLLATE_MAX_PRIORITY;
1157 collinfo.directive[NUM_WT] = DIRECTIVE_UNDEFINED;
1160 * Ordinary character priorities
1162 for (i = 0; i <= UCHAR_MAX; i++) {
1163 if ((cc = get_collchar(i, 0)) != NULL) {
1164 for (j = 0; j < NUM_WT; j++) {
1165 chars[i].pri[j] = get_weight(cc->ref[j], j);
1168 for (j = 0; j < NUM_WT; j++) {
1170 get_weight(pri_undefined[j], j);
1173 * Per POSIX, for undefined characters, we
1174 * also have to add a last item, which is the
1177 chars[i].pri[NUM_WT] = i;
1182 * Substitution tables
1184 for (i = 0; i < NUM_WT; i++) {
1185 collate_subst_t *st = NULL;
1186 n = collinfo.subst_count[i] = avl_numnodes(&substs[i]);
1187 if ((st = calloc(sizeof (collate_subst_t) * n, 1)) == NULL) {
1188 fprintf(stderr, "out of memory");
1192 for (sb = avl_first(&substs[i]); sb;
1193 sb = AVL_NEXT(&substs[i], sb)) {
1194 if ((st[n].key = resolve_pri(sb->key)) < 0) {
1195 /* by definition these resolve! */
1198 if (st[n].key != (n | COLLATE_SUBST_PRIORITY)) {
1201 for (j = 0; sb->ref[j]; j++) {
1202 st[n].pri[j] = get_weight(sb->ref[j], i);
1206 if (n != collinfo.subst_count[i])
1213 * Chains, i.e. collating elements
1215 collinfo.chain_count = avl_numnodes(&elem_by_expand);
1216 chain = calloc(sizeof (collate_chain_t), collinfo.chain_count);
1217 if (chain == NULL) {
1218 fprintf(stderr, "out of memory");
1221 for (n = 0, ce = avl_first(&elem_by_expand);
1223 ce = AVL_NEXT(&elem_by_expand, ce), n++) {
1224 (void) wsncpy(chain[n].str, ce->expand, COLLATE_STR_LEN);
1225 for (i = 0; i < NUM_WT; i++) {
1226 chain[n].pri[i] = get_weight(ce->ref[i], i);
1229 if (n != collinfo.chain_count)
1233 * Large (> UCHAR_MAX) character priorities
1235 large = calloc(sizeof (collate_large_t) * avl_numnodes(&collchars), 1);
1236 if (large == NULL) {
1237 fprintf(stderr, "out of memory");
1242 for (cc = avl_first(&collchars); cc; cc = AVL_NEXT(&collchars, cc)) {
1244 /* we already gathered those */
1245 if (cc->wc <= UCHAR_MAX)
1247 for (j = 0; j < NUM_WT; j++) {
1248 if ((pri = get_weight(cc->ref[j], j)) < 0) {
1251 if (undef && (pri >= 0)) {
1252 /* if undefined, then all priorities are */
1255 large[i].pri.pri[j] = pri;
1259 large[i].val = cc->wc;
1260 collinfo.large_count = i++;
1264 if ((f = open_category()) == NULL) {
1268 /* Time to write the entire data set out */
1270 if ((wr_category(vers, COLLATE_STR_LEN, f) < 0) ||
1271 (wr_category(&collinfo, sizeof (collinfo), f) < 0) ||
1272 (wr_category(&chars, sizeof (chars), f) < 0)) {
1276 for (i = 0; i < NUM_WT; i++) {
1277 sz = sizeof (collate_subst_t) * collinfo.subst_count[i];
1278 if (wr_category(subst[i], sz, f) < 0) {
1282 sz = sizeof (collate_chain_t) * collinfo.chain_count;
1283 if (wr_category(chain, sz, f) < 0) {
1286 sz = sizeof (collate_large_t) * collinfo.large_count;
1287 if (wr_category(large, sz, f) < 0) {