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.
40 #include <sys/types.h>
45 #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 AVL 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 {
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.
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];
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 avl_node_t avl_bysymbol;
183 avl_node_t avl_byexpand;
187 * Individual characters have a sequence of weights as well.
189 typedef struct collchar {
191 int32_t ref[COLL_WEIGHTS_MAX];
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.
203 int32_t ref[COLLATE_STR_LEN];
208 static avl_tree_t collsyms;
209 static avl_tree_t collundefs;
210 static avl_tree_t elem_by_symbol;
211 static avl_tree_t elem_by_expand;
212 static avl_tree_t collchars;
213 static avl_tree_t substs[COLL_WEIGHTS_MAX];
214 static avl_tree_t substs_ref[COLL_WEIGHTS_MAX];
215 static avl_tree_t 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);
361 collsym_compare(const void *n1, const void *n2)
363 const collsym_t *c1 = n1;
364 const collsym_t *c2 = n2;
367 rv = strcmp(c1->name, c2->name);
368 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
372 collundef_compare(const void *n1, const void *n2)
374 const collundef_t *c1 = n1;
375 const collundef_t *c2 = n2;
378 rv = strcmp(c1->name, c2->name);
379 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
383 element_compare_symbol(const void *n1, const void *n2)
385 const collelem_t *c1 = n1;
386 const collelem_t *c2 = n2;
389 rv = strcmp(c1->symbol, c2->symbol);
390 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
394 element_compare_expand(const void *n1, const void *n2)
396 const collelem_t *c1 = n1;
397 const collelem_t *c2 = n2;
400 rv = wcscmp(c1->expand, c2->expand);
401 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
405 collchar_compare(const void *n1, const void *n2)
407 wchar_t k1 = ((const collchar_t *)n1)->wc;
408 wchar_t k2 = ((const collchar_t *)n2)->wc;
410 return (k1 < k2 ? -1 : k1 > k2 ? 1 : 0);
414 subst_compare(const void *n1, const void *n2)
416 int32_t k1 = ((const subst_t *)n1)->key;
417 int32_t k2 = ((const subst_t *)n2)->key;
419 return (k1 < k2 ? -1 : k1 > k2 ? 1 : 0);
422 #pragma GCC diagnostic push
423 #pragma GCC diagnostic ignored "-Wcast-qual"
426 subst_compare_ref(const void *n1, const void *n2)
428 int32_t *c1 = ((subst_t *)n1)->ref;
429 int32_t *c2 = ((subst_t *)n2)->ref;
432 rv = wcscmp((wchar_t *)c1, (wchar_t *)c2);
433 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
436 #pragma GCC diagnostic pop
443 avl_create(&collsyms, collsym_compare, sizeof (collsym_t),
444 offsetof(collsym_t, avl));
446 avl_create(&collundefs, collundef_compare, sizeof (collsym_t),
447 offsetof(collundef_t, avl));
449 avl_create(&elem_by_symbol, element_compare_symbol, sizeof (collelem_t),
450 offsetof(collelem_t, avl_bysymbol));
451 avl_create(&elem_by_expand, element_compare_expand, sizeof (collelem_t),
452 offsetof(collelem_t, avl_byexpand));
454 avl_create(&collchars, collchar_compare, sizeof (collchar_t),
455 offsetof(collchar_t, avl));
457 for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
458 avl_create(&substs[i], subst_compare, sizeof (subst_t),
459 offsetof(subst_t, avl));
460 avl_create(&substs_ref[i], subst_compare_ref,
461 sizeof (subst_t), offsetof(subst_t, avl_ref));
462 avl_create(&weights[i], weight_compare, sizeof (weight_t),
463 offsetof(weight_t, avl));
467 (void) memset(&collinfo, 0, sizeof (collinfo));
469 /* allocate some initial priorities */
470 pri_ignore = new_pri();
472 set_pri(pri_ignore, 0, RESOLVED);
474 for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
475 pri_undefined[i] = new_pri();
477 /* we will override this later */
478 set_pri(pri_undefined[i], COLLATE_MAX_PRIORITY, UNKNOWN);
483 define_collsym(char *name)
488 if ((sym = calloc(sizeof (*sym), 1)) == NULL) {
489 fprintf(stderr,"out of memory");
493 sym->ref = new_pri();
495 if (avl_find(&collsyms, sym, &where) != NULL) {
497 * This should never happen because we are only called
498 * for undefined symbols.
503 avl_insert(&collsyms, sym, where);
507 lookup_collsym(char *name)
512 return (avl_find(&collsyms, &srch, NULL));
516 lookup_collelem(char *symbol)
520 srch.symbol = symbol;
521 return (avl_find(&elem_by_symbol, &srch, NULL));
525 get_collundef(char *name)
533 if ((ud = avl_find(&collundefs, &srch, &where)) == NULL) {
534 if (((ud = calloc(sizeof (*ud), 1)) == NULL) ||
535 ((ud->name = strdup(name)) == NULL)) {
536 fprintf(stderr,"out of memory");
539 for (i = 0; i < NUM_WT; i++) {
540 ud->ref[i] = new_pri();
542 avl_insert(&collundefs, ud, where);
544 add_charmap_undefined(name);
549 get_collchar(wchar_t wc, int create)
557 cc = avl_find(&collchars, &srch, &where);
558 if ((cc == NULL) && create) {
559 if ((cc = calloc(sizeof (*cc), 1)) == NULL) {
560 fprintf(stderr, "out of memory");
563 for (i = 0; i < NUM_WT; i++) {
564 cc->ref[i] = new_pri();
567 avl_insert(&collchars, cc, where);
573 end_order_collsym(collsym_t *sym)
575 start_order(T_COLLSYM);
576 /* update the weight */
578 set_pri(sym->ref, nextpri, RESOLVED);
590 /* advance the priority/weight */
595 for (i = 0; i < NUM_WT; i++) {
596 if (((ref = order_weights[i]) < 0) ||
597 ((p = get_pri(ref)) == NULL) ||
599 /* unspecified weight is a self reference */
600 set_pri(currchar->ref[i], pri, RESOLVED);
602 set_pri(currchar->ref[i], ref, REFER);
604 order_weights[i] = -1;
607 /* leave a cookie trail in case next symbol is ellipsis */
608 ellipsis_start = currchar->wc + 1;
613 /* save off the weights were we can find them */
614 for (i = 0; i < NUM_WT; i++) {
615 ellipsis_weights[i] = order_weights[i];
616 order_weights[i] = -1;
621 if (currelem == NULL) {
624 for (i = 0; i < NUM_WT; i++) {
626 if (((ref = order_weights[i]) < 0) ||
627 ((p = get_pri(ref)) == NULL) ||
629 set_pri(currelem->ref[i], pri,
632 set_pri(currelem->ref[i], ref, REFER);
634 order_weights[i] = -1;
640 for (i = 0; i < NUM_WT; i++) {
641 if (((ref = order_weights[i]) < 0) ||
642 ((p = get_pri(ref)) == NULL) ||
644 set_pri(pri_undefined[i], -1, RESOLVED);
646 set_pri(pri_undefined[i], ref, REFER);
648 order_weights[i] = -1;
653 for (i = 0; i < NUM_WT; i++) {
654 if (((ref = order_weights[i]) < 0) ||
655 ((p = get_pri(ref)) == NULL) ||
657 set_pri(currundef->ref[i], pri, RESOLVED);
659 set_pri(currundef->ref[i], ref, REFER);
661 order_weights[i] = -1;
673 start_order(int type)
677 lastorder = currorder;
680 /* this is used to protect ELLIPSIS processing */
681 if ((lastorder == T_ELLIPSIS) && (type != T_CHAR)) {
682 fprintf(stderr, "character value expected");
685 for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
686 order_weights[i] = -1;
692 start_order_undefined(void)
694 start_order(T_UNDEFINED);
698 start_order_symbol(char *name)
700 currundef = get_collundef(name);
701 start_order(T_SYMBOL);
705 start_order_char(wchar_t wc)
713 * If we last saw an ellipsis, then we need to close the range.
714 * Handle that here. Note that we have to be careful because the
715 * items *inside* the range are treated exclusiveley to the items
716 * outside of the range. The ends of the range can have quite
717 * different weights than the range members.
719 if (lastorder == T_ELLIPSIS) {
722 if (wc < ellipsis_start) {
723 fprintf(stderr, "malformed range!");
726 while (ellipsis_start < wc) {
728 * pick all of the saved weights for the
729 * ellipsis. note that -1 encodes for the
730 * ellipsis itself, which means to take the
731 * current relative priority.
733 if ((cc = get_collchar(ellipsis_start, 1)) == NULL) {
737 for (i = 0; i < NUM_WT; i++) {
739 if (((ref = ellipsis_weights[i]) == -1) ||
740 ((p = get_pri(ref)) == NULL) ||
742 set_pri(cc->ref[i], nextpri, RESOLVED);
744 set_pri(cc->ref[i], ref, REFER);
746 ellipsis_weights[i] = 0;
753 currchar = get_collchar(wc, 1);
757 start_order_collelem(collelem_t *e)
759 start_order(T_COLLELEM);
764 start_order_ellipsis(void)
768 start_order(T_ELLIPSIS);
770 if (lastorder != T_CHAR) {
771 fprintf(stderr, "illegal starting point for range");
775 for (i = 0; i < NUM_WT; i++) {
776 ellipsis_weights[i] = order_weights[i];
781 define_collelem(char *name, wchar_t *wcs)
788 if (wcslen(wcs) >= COLLATE_STR_LEN) {
789 fprintf(stderr,"expanded collation element too long");
793 if ((e = calloc(sizeof (*e), 1)) == NULL) {
794 fprintf(stderr, "out of memory");
801 * This is executed before the order statement, so we don't
802 * know how many priorities we *really* need. We allocate one
803 * for each possible weight. Not a big deal, as collating-elements
804 * prove to be quite rare.
806 for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
807 e->ref[i] = new_pri();
810 /* A character sequence can only reduce to one element. */
811 if ((avl_find(&elem_by_symbol, e, &where1) != NULL) ||
812 (avl_find(&elem_by_expand, e, &where2) != NULL)) {
813 fprintf(stderr, "duplicate collating element definition");
816 avl_insert(&elem_by_symbol, e, where1);
817 avl_insert(&elem_by_expand, e, where2);
821 add_order_bit(int kw)
823 uint8_t bit = DIRECTIVE_UNDEF;
827 bit = DIRECTIVE_FORWARD;
830 bit = DIRECTIVE_BACKWARD;
833 bit = DIRECTIVE_POSITION;
839 collinfo.directive[collinfo.directive_count] |= bit;
843 add_order_directive(void)
845 if (collinfo.directive_count >= COLL_WEIGHTS_MAX) {
846 fprintf(stderr,"too many directives (max %d)", COLL_WEIGHTS_MAX);
848 collinfo.directive_count++;
852 add_order_pri(int32_t ref)
854 if (curr_weight >= NUM_WT) {
855 fprintf(stderr,"too many weights (max %d)", NUM_WT);
858 order_weights[curr_weight] = ref;
863 add_order_collsym(collsym_t *s)
865 add_order_pri(s->ref);
869 add_order_char(wchar_t wc)
873 if ((cc = get_collchar(wc, 1)) == NULL) {
878 add_order_pri(cc->ref[curr_weight]);
882 add_order_collelem(collelem_t *e)
884 add_order_pri(e->ref[curr_weight]);
888 add_order_ignore(void)
890 add_order_pri(pri_ignore);
894 add_order_symbol(char *sym)
897 if ((c = get_collundef(sym)) == NULL) {
901 add_order_pri(c->ref[curr_weight]);
905 add_order_ellipsis(void)
907 /* special NULL value indicates self reference */
912 add_order_subst(void)
919 (void) memset(&srch, 0, sizeof (srch));
920 for (i = 0; i < curr_subst; i++) {
921 srch.ref[i] = subst_weights[i];
922 subst_weights[i] = 0;
924 s = avl_find(&substs_ref[curr_weight], &srch, &where);
927 if ((s = calloc(sizeof (*s), 1)) == NULL) {
928 fprintf(stderr,"out of memory");
934 * We use a self reference for our key, but we set a
935 * high bit to indicate that this is a substitution
936 * reference. This will expedite table lookups later,
937 * and prevent table lookups for situations that don't
938 * require it. (In short, its a big win, because we
939 * can skip a lot of binary searching.)
942 (nextsubst[curr_weight] | COLLATE_SUBST_PRIORITY),
944 nextsubst[curr_weight] += 1;
946 for (i = 0; i < curr_subst; i++) {
947 s->ref[i] = srch.ref[i];
950 avl_insert(&substs_ref[curr_weight], s, where);
952 if (avl_find(&substs[curr_weight], s, &where) != NULL) {
956 avl_insert(&substs[curr_weight], s, where);
962 * We are using the current (unique) priority as a search key
963 * in the substitution table.
965 add_order_pri(s->key);
969 add_subst_pri(int32_t ref)
971 if (curr_subst >= COLLATE_STR_LEN) {
972 fprintf(stderr,"substitution string is too long");
975 subst_weights[curr_subst] = ref;
980 add_subst_char(wchar_t wc)
985 if (((cc = get_collchar(wc, 1)) == NULL) ||
990 /* we take the weight for the character at that position */
991 add_subst_pri(cc->ref[curr_weight]);
995 add_subst_collelem(collelem_t *e)
997 add_subst_pri(e->ref[curr_weight]);
1001 add_subst_collsym(collsym_t *s)
1003 add_subst_pri(s->ref);
1007 add_subst_symbol(char *ptr)
1011 if ((cu = get_collundef(ptr)) != NULL) {
1012 add_subst_pri(cu->ref[curr_weight]);
1017 add_weight(int32_t ref, int pass)
1023 srch.pri = resolve_pri(ref);
1025 /* No translation of ignores */
1029 /* Substitution priorities are not weights */
1030 if (srch.pri & COLLATE_SUBST_PRIORITY)
1033 if (avl_find(&weights[pass], &srch, &where) != NULL)
1036 if ((w = calloc(sizeof (*w), 1)) == NULL) {
1037 fprintf(stderr, "out of memory");
1041 avl_insert(&weights[pass], w, where);
1045 add_weights(int32_t *refs)
1048 for (i = 0; i < NUM_WT; i++) {
1049 add_weight(refs[i], i);
1054 get_weight(int32_t ref, int pass)
1060 pri = resolve_pri(ref);
1061 if (pri & COLLATE_SUBST_PRIORITY) {
1068 if ((w = avl_find(&weights[pass], &srch, NULL)) == NULL) {
1076 wsncpy(wchar_t *s1, const wchar_t *s2, size_t n)
1081 while (--n > 0 && (*s1++ = *s2++) != 0)
1099 char vers[COLLATE_STR_LEN];
1100 collate_char_t chars[UCHAR_MAX + 1];
1101 collate_large_t *large;
1102 collate_subst_t *subst[COLL_WEIGHTS_MAX];
1103 collate_chain_t *chain;
1106 * We have to run throught a preliminary pass to identify all the
1107 * weights that we use for each sorting level.
1109 for (i = 0; i < NUM_WT; i++) {
1110 add_weight(pri_ignore, i);
1112 for (i = 0; i < NUM_WT; i++) {
1113 for (sb = avl_first(&substs[i]); sb;
1114 sb = AVL_NEXT(&substs[i], sb)) {
1115 for (j = 0; sb->ref[j]; j++) {
1116 add_weight(sb->ref[j], i);
1120 for (ce = avl_first(&elem_by_expand);
1122 ce = AVL_NEXT(&elem_by_expand, ce)) {
1123 add_weights(ce->ref);
1125 for (cc = avl_first(&collchars); cc; cc = AVL_NEXT(&collchars, cc)) {
1126 add_weights(cc->ref);
1130 * Now we walk the entire set of weights, removing the gaps
1131 * in the weights. This gives us optimum usage. The walk
1132 * occurs in priority.
1134 for (i = 0; i < NUM_WT; i++) {
1136 for (w = avl_first(&weights[i]); w;
1137 w = AVL_NEXT(&weights[i], w)) {
1138 w->opt = nweight[i];
1143 (void) memset(&chars, 0, sizeof (chars));
1144 (void) memset(vers, 0, COLLATE_STR_LEN);
1145 (void) strlcpy(vers, COLLATE_VERSION, sizeof (vers));
1148 * We need to make sure we arrange for the UNDEFINED field
1149 * to show up. Also, set the total weight counts.
1151 for (i = 0; i < NUM_WT; i++) {
1152 if (resolve_pri(pri_undefined[i]) == -1) {
1153 set_pri(pri_undefined[i], -1, RESOLVED);
1154 /* they collate at the end of everything else */
1155 collinfo.undef_pri[i] = COLLATE_MAX_PRIORITY;
1157 collinfo.pri_count[i] = nweight[i];
1160 collinfo.pri_count[NUM_WT] = max_wide();
1161 collinfo.undef_pri[NUM_WT] = COLLATE_MAX_PRIORITY;
1162 collinfo.directive[NUM_WT] = DIRECTIVE_UNDEFINED;
1165 * Ordinary character priorities
1167 for (i = 0; i <= UCHAR_MAX; i++) {
1168 if ((cc = get_collchar(i, 0)) != NULL) {
1169 for (j = 0; j < NUM_WT; j++) {
1170 chars[i].pri[j] = get_weight(cc->ref[j], j);
1173 for (j = 0; j < NUM_WT; j++) {
1175 get_weight(pri_undefined[j], j);
1178 * Per POSIX, for undefined characters, we
1179 * also have to add a last item, which is the
1182 chars[i].pri[NUM_WT] = i;
1187 * Substitution tables
1189 for (i = 0; i < NUM_WT; i++) {
1190 collate_subst_t *st = NULL;
1191 n = collinfo.subst_count[i] = avl_numnodes(&substs[i]);
1192 if ((st = calloc(sizeof (collate_subst_t) * n, 1)) == NULL) {
1193 fprintf(stderr, "out of memory");
1197 for (sb = avl_first(&substs[i]); sb;
1198 sb = AVL_NEXT(&substs[i], sb)) {
1199 if ((st[n].key = resolve_pri(sb->key)) < 0) {
1200 /* by definition these resolve! */
1203 if (st[n].key != (n | COLLATE_SUBST_PRIORITY)) {
1206 for (j = 0; sb->ref[j]; j++) {
1207 st[n].pri[j] = get_weight(sb->ref[j], i);
1211 if (n != collinfo.subst_count[i])
1218 * Chains, i.e. collating elements
1220 collinfo.chain_count = avl_numnodes(&elem_by_expand);
1221 chain = calloc(sizeof (collate_chain_t), collinfo.chain_count);
1222 if (chain == NULL) {
1223 fprintf(stderr, "out of memory");
1226 for (n = 0, ce = avl_first(&elem_by_expand);
1228 ce = AVL_NEXT(&elem_by_expand, ce), n++) {
1229 (void) wsncpy(chain[n].str, ce->expand, COLLATE_STR_LEN);
1230 for (i = 0; i < NUM_WT; i++) {
1231 chain[n].pri[i] = get_weight(ce->ref[i], i);
1234 if (n != collinfo.chain_count)
1238 * Large (> UCHAR_MAX) character priorities
1240 large = calloc(sizeof (collate_large_t) * avl_numnodes(&collchars), 1);
1241 if (large == NULL) {
1242 fprintf(stderr, "out of memory");
1247 for (cc = avl_first(&collchars); cc; cc = AVL_NEXT(&collchars, cc)) {
1249 /* we already gathered those */
1250 if (cc->wc <= UCHAR_MAX)
1252 for (j = 0; j < NUM_WT; j++) {
1253 if ((pri = get_weight(cc->ref[j], j)) < 0) {
1256 if (undef && (pri >= 0)) {
1257 /* if undefined, then all priorities are */
1260 large[i].pri.pri[j] = pri;
1264 large[i].val = cc->wc;
1265 collinfo.large_count = i++;
1269 if ((f = open_category()) == NULL) {
1273 /* Time to write the entire data set out */
1275 if ((wr_category(vers, COLLATE_STR_LEN, f) < 0) ||
1276 (wr_category(&collinfo, sizeof (collinfo), f) < 0) ||
1277 (wr_category(&chars, sizeof (chars), f) < 0)) {
1281 for (i = 0; i < NUM_WT; i++) {
1282 sz = sizeof (collate_subst_t) * collinfo.subst_count[i];
1283 if (wr_category(subst[i], sz, f) < 0) {
1287 sz = sizeof (collate_chain_t) * collinfo.chain_count;
1288 if (wr_category(chain, sz, f) < 0) {
1291 sz = sizeof (collate_large_t) * collinfo.large_count;
1292 if (wr_category(large, sz, f) < 0) {