cmd/localedef/collate.c

	collate.c revision 6b5e5868e7ebf1aff3a5abd7d0c4ef0e5fbf3648
/*
 * This file and its contents are supplied under the terms of the
 * Common Development and Distribution License ("CDDL"), version 1.0.
 * You may only use this file in accordance with the terms version 1.0
 * of the CDDL.
 *
 * A full copy of the text of the CDDL should have accompanied this
 * source.  A copy of the CDDL is also available via the Internet at
 * http://www.illumos.org/license/CDDL.
 */

/*
 * Copyright 2010 Nexenta Systems, Inc.  All rights reserved.
 */

/*
 * LC_COLLATE database generation routines for localedef.
 */

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>
#include <sys/types.h>
#include <sys/avl.h>
#include <string.h>
#include <unistd.h>
#include <wchar.h>
#include <widec.h>
#include <limits.h>
#include "localedef.h"
#include "parser.tab.h"
#include "collate.h"

/*
 * In order to resolve the priorities, we create a table of priorities.
 * Entries in the table can be in one of three states.
 *
 * UNKNOWN is for newly allocated entries, and indicates that nothing
 * is known about the priority.  (For example, when new entries are created
 * for collating-symbols, this is the value assigned for them until the
 * collating symbol's order has been determined.
 *
 * RESOLVED is used for an entry where the priority indicates the final
 * numeric weight.
 *
 * REFER is used for entries that reference other entries.  Typically
 * this is used for forward references.  A collating-symbol can never
 * have this value.
 *
 * The "self" field is a reference to or own index in the pri list.
 *
 * The "pass" field is used during final resolution to aid in detection
 * of referencing loops.  (For example <A> depends on <B>, but <B> has its
 * priority dependent on <A>.)
 */
typedef enum {
    UNKNOWN,    /* priority is totally unknown */
    RESOLVED,   /* priority value fully resolved */
    REFER       /* priority is a reference (index) */
} res_t;

typedef struct priority {
    res_t       res;
    int32_t     pri;
    int32_t     self;
    int     pass;
    int     lineno;
} collpri_t;


#define NUM_WT  collinfo.directive_count

/*
 * These are the abstract collating symbols, which are just a symbolic
 * way to reference a priority.
 */
struct collsym {
    char        *name;
    int32_t     ref;
    avl_node_t  avl;
};

/*
 * These are also abstract collating symbols, but we allow them to have
 * different priorities at different levels.
 */
typedef struct collundef {
    char        *name;
    int32_t     ref[COLL_WEIGHTS_MAX];
    avl_node_t  avl;
} collundef_t;

/*
 * These are called "chains" in libc.  This records the fact that two
 * more characters should be treated as a single collating entity when
 * they appear together.  For example, in Spanish <C><h> gets collated
 * as a character between <C> and <D>.
 */
struct collelem {
    char        *symbol;
    wchar_t     *expand;
    int32_t     ref[COLL_WEIGHTS_MAX];
    avl_node_t  avl_bysymbol;
    avl_node_t  avl_byexpand;
};

/*
 * Individual characters have a sequence of weights as well.
 */
typedef struct collchar {
    wchar_t     wc;
    wchar_t     ref[COLL_WEIGHTS_MAX];
    avl_node_t  avl;
} collchar_t;

/*
 * Substitution entries.  The key is itself a priority.  Note that
 * when we create one of these, we *automatically* wind up with a
 * fully resolved priority for the key, because creation of
 * substitutions creates a resolved priority at the same time.
 */
typedef struct {
    int32_t     key;
    int32_t     ref[COLLATE_STR_LEN];
    avl_node_t  avl;
} subst_t;

static avl_tree_t   collsyms;
static avl_tree_t   collundefs;
static avl_tree_t   elem_by_symbol;
static avl_tree_t   elem_by_expand;
static avl_tree_t   collchars;
static avl_tree_t   substs[COLL_WEIGHTS_MAX];

/*
 * This is state tracking for the ellipsis token.  Note that we start
 * the initial values so that the ellipsis logic will think we got a
 * magic starting value of NUL.  It starts at minus one because the
 * starting point is exclusive -- i.e. the starting point is not
 * itself handled by the ellipsis code.
 */
static int currorder = EOF;
static int lastorder = EOF;
static collelem_t *currelem;
static collchar_t *currchar;
static collundef_t *currundef;
static wchar_t ellipsis_start = 0;
static int32_t ellipsis_weights[COLL_WEIGHTS_MAX];

/*
 * We keep a running tally of weights.
 */
static int nextpri = 1;

/*
 * This array collects up the weights for each level.
 */
static int32_t order_weights[COLL_WEIGHTS_MAX];
static int curr_weight = 0;
static int32_t subst_weights[COLLATE_STR_LEN];
static int curr_subst = 0;

/*
 * Some initial priority values.
 */
static int32_t pri_undefined[COLL_WEIGHTS_MAX];
static int32_t pri_ignore;

static collate_info_t collinfo;

static collpri_t    *prilist = NULL;
static int      numpri = 0;
static int      maxpri = 0;

static void start_order(int);

static int32_t
new_pri(void)
{
    int i;

    if (numpri >= maxpri) {
        maxpri = maxpri ? maxpri * 2 : 1024;
        prilist = realloc(prilist, sizeof (collpri_t) * maxpri);
        if (prilist == NULL) {
            errf(_("out of memory"));
            return (-1);
        }
        for (i = numpri; i < maxpri; i++) {
            prilist[i].res = UNKNOWN;
            prilist[i].pri = 0;
            prilist[i].pass = 0;
            prilist[i].self = i;
        }
    }
    return (numpri++);
}

static collpri_t *
get_pri(int32_t ref)
{
    if ((ref < 0) || (ref > numpri)) {
        INTERR;
        return (NULL);
    }
    return (&prilist[ref]);
}

static void
set_pri(int32_t ref, int32_t v, res_t res)
{
    collpri_t   *pri;

    pri = get_pri(ref);

    if ((res == REFER) && ((v < 0) || (v >= numpri))) {
        INTERR;
    }

    /* Resolve self references */
    if ((res == REFER) && (ref == v)) {
        v = nextpri;
        res = RESOLVED;
    }

    if (pri->res != UNKNOWN) {
        warn(_("repeated item in order list (first on %d)"),
            pri->lineno);
        return;
    }
    pri->lineno = lineno;
    pri->pri = v;
    pri->res = res;
}

static int32_t
resolve_pri(int32_t ref)
{
    collpri_t   *pri;
    static int32_t  pass = 0;

    pri = get_pri(ref);
    pass++;
    while (pri->res == REFER) {
        if (pri->pass == pass) {
            /* report a line with the circular symbol */
            lineno = pri->lineno;
            errf(_("circular reference in order list"));
            return (-1);
        }
        if ((pri->pri < 0) || (pri->pri >= numpri)) {
            INTERR;
            return (-1);
        }
        pri->pass = pass;
        pri = &prilist[pri->pri];
    }

    if (pri->res == UNKNOWN) {
        return (-1);
    }
    if (pri->res != RESOLVED)
        INTERR;

    return (pri->pri);
}

static int
collsym_compare(const void *n1, const void *n2)
{
    const collsym_t *c1 = n1;
    const collsym_t *c2 = n2;
    int rv;

    rv = strcmp(c1->name, c2->name);
    return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
}

static int
collundef_compare(const void *n1, const void *n2)
{
    const collundef_t *c1 = n1;
    const collundef_t *c2 = n2;
    int rv;

    rv = strcmp(c1->name, c2->name);
    return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
}

static int
element_compare_symbol(const void *n1, const void *n2)
{
    const collelem_t *c1 = n1;
    const collelem_t *c2 = n2;
    int rv;

    rv = strcmp(c1->symbol, c2->symbol);
    return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
}

static int
element_compare_expand(const void *n1, const void *n2)
{
    const collelem_t *c1 = n1;
    const collelem_t *c2 = n2;
    int rv;

    rv = wcscmp(c1->expand, c2->expand);
    return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
}

static int
collchar_compare(const void *n1, const void *n2)
{
    wchar_t k1 = ((const collchar_t *)n1)->wc;
    wchar_t k2 = ((const collchar_t *)n2)->wc;

    return (k1 < k2 ? -1 : k1 > k2 ? 1 : 0);
}

static int
subst_compare(const void *n1, const void *n2)
{
    int32_t k1 = ((const subst_t *)n1)->key;
    int32_t k2 = ((const subst_t *)n2)->key;

    return (k1 < k2 ? -1 : k1 > k2 ? 1 : 0);
}

void
init_collate(void)
{
    int i;

    avl_create(&collsyms, collsym_compare, sizeof (collsym_t),
        offsetof(collsym_t, avl));

    avl_create(&collundefs, collundef_compare, sizeof (collsym_t),
        offsetof(collundef_t, avl));

    avl_create(&elem_by_symbol, element_compare_symbol, sizeof (collelem_t),
        offsetof(collelem_t, avl_bysymbol));
    avl_create(&elem_by_expand, element_compare_expand, sizeof (collelem_t),
        offsetof(collelem_t, avl_byexpand));

    avl_create(&collchars, collchar_compare, sizeof (collchar_t),
        offsetof(collchar_t, avl));

    for (i = 0; i < COLL_WEIGHTS_MAX; i++)
        avl_create(&substs[i], subst_compare, sizeof (subst_t),
            offsetof(subst_t, avl));

    (void) memset(&collinfo, 0, sizeof (collinfo));

    /* allocate some initial priorities */
    pri_ignore = new_pri();

    set_pri(pri_ignore, 0, RESOLVED);

    for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
        pri_undefined[i] = new_pri();

        /* we will override this later */
        set_pri(pri_undefined[i], COLLATE_MAX_PRIORITY, UNKNOWN);
    }
}

void
define_collsym(char *name)
{
    collsym_t   *sym;
    avl_index_t where;

    if ((sym = calloc(sizeof (*sym), 1)) == NULL) {
        errf(_("out of memory"));
        return;
    }
    sym->name = name;
    sym->ref = new_pri();

    if (avl_find(&collsyms, sym, &where) != NULL) {
        /*
         * This should never happen because we are only called
         * for undefined symbols.
         */
        INTERR;
        return;
    }
    avl_insert(&collsyms, sym, where);
}

collsym_t *
lookup_collsym(char *name)
{
    collsym_t   srch;

    srch.name = name;
    return (avl_find(&collsyms, &srch, NULL));
}

collelem_t *
lookup_collelem(char *symbol)
{
    collelem_t  srch;

    srch.symbol = symbol;
    return (avl_find(&elem_by_symbol, &srch, NULL));
}

static collundef_t *
get_collundef(char *name)
{
    collundef_t srch;
    collundef_t *ud;
    avl_index_t where;
    int     i;

    srch.name = name;
    if ((ud = avl_find(&collundefs, &srch, &where)) == NULL) {
        if (((ud = calloc(sizeof (*ud), 1)) == NULL) ||
            ((ud->name = strdup(name)) == NULL)) {
            errf(_("out of memory"));
            return (NULL);
        }
        for (i = 0; i < NUM_WT; i++) {
            ud->ref[i] = new_pri();
        }
        avl_insert(&collundefs, ud, where);
    }
    add_charmap_undefined(name);
    return (ud);
}

static collchar_t *
get_collchar(wchar_t wc, int create)
{
    collchar_t  srch;
    collchar_t  *cc;
    avl_index_t where;
    int     i;

    srch.wc = wc;
    cc = avl_find(&collchars, &srch, &where);
    if ((cc == NULL) && create) {
        if ((cc = calloc(sizeof (*cc), 1)) == NULL) {
            errf(_("out of memory"));
            return (NULL);
        }
        for (i = 0; i < NUM_WT; i++) {
            cc->ref[i] = new_pri();
        }
        cc->wc = wc;
        avl_insert(&collchars, cc, where);
    }
    return (cc);
}

void
end_order_collsym(collsym_t *sym)
{
    start_order(T_COLLSYM);
    /* update the weight */

    set_pri(sym->ref, nextpri, RESOLVED);
    nextpri++;
}

void
end_order(void)
{
    int     i;
    int32_t     pri;
    int32_t     ref;
    collpri_t   *p;

    /* advance the priority/weight */
    pri = nextpri;

    switch (currorder) {
    case T_CHAR:
        for (i = 0; i < NUM_WT; i++) {
            if (((ref = order_weights[i]) < 0) ||
                ((p = get_pri(ref)) == NULL) ||
                (p->pri == -1)) {
                /* unspecified weight is a self reference */
                set_pri(currchar->ref[i], pri, RESOLVED);
            } else {
                set_pri(currchar->ref[i], ref, REFER);
            }
            order_weights[i] = -1;
        }

        /* leave a cookie trail in case next symbol is ellipsis */
        ellipsis_start = currchar->wc + 1;
        currchar = NULL;
        break;

    case T_ELLIPSIS:
        /* save off the weights were we can find them */
        for (i = 0; i < NUM_WT; i++) {
            ellipsis_weights[i] = order_weights[i];
            order_weights[i] = -1;
        }
        break;

    case T_COLLELEM:
        if (currelem == NULL) {
            INTERR;
        } else {
            for (i = 0; i < NUM_WT; i++) {

                if (((ref = order_weights[i]) < 0) ||
                    ((p = get_pri(ref)) == NULL) ||
                    (p->pri == -1)) {
                    set_pri(currelem->ref[i], pri,
                        RESOLVED);
                } else {
                    set_pri(currelem->ref[i], ref, REFER);
                }
                order_weights[i] = -1;
            }
        }
        break;

    case T_UNDEFINED:
        for (i = 0; i < NUM_WT; i++) {
            if (((ref = order_weights[i]) < 0) ||
                ((p = get_pri(ref)) == NULL) ||
                (p->pri == -1)) {
                set_pri(pri_undefined[i], -1, RESOLVED);
            } else {
                set_pri(pri_undefined[i], ref, REFER);
            }
            order_weights[i] = -1;
        }
        break;

    case T_SYMBOL:
        if (((ref = order_weights[i]) < 0) ||
            ((p = get_pri(ref)) == NULL) ||
            (p->pri == -1)) {
            set_pri(currundef->ref[i], pri, RESOLVED);
        } else {
            set_pri(currundef->ref[i], ref, REFER);
        }
        order_weights[i] = -1;
        break;

    default:
        INTERR;
    }

    nextpri++;
}

static void
start_order(int type)
{
    int i;

    lastorder = currorder;
    currorder = type;

    /* this is used to protect ELLIPSIS processing */
    if ((lastorder == T_ELLIPSIS) && (type != T_CHAR)) {
        errf(_("character value expected"));
    }

    for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
        order_weights[i] = -1;
    }
    curr_weight = 0;
}

void
start_order_undefined(void)
{
    start_order(T_UNDEFINED);
}

void
start_order_symbol(char *name)
{
    currundef = get_collundef(name);
    start_order(T_SYMBOL);
}

void
start_order_char(wchar_t wc)
{
    collchar_t  *cc;
    int32_t     ref;

    start_order(T_CHAR);

    /*
     * If we last saw an ellipsis, then we need to close the range.
     * Handle that here.  Note that we have to be careful because the
     * items *inside* the range are treated exclusiveley to the items
     * outside of the range.  The ends of the range can have quite
     * different weights than the range members.
     */
    if (lastorder == T_ELLIPSIS) {
        int     i;

        if (wc < ellipsis_start) {
            errf(_("malformed range!"));
            return;
        }
        while (ellipsis_start < wc) {
            /*
             * pick all of the saved weights for the
             * ellipsis.  note that -1 encodes for the
             * ellipsis itself, which means to take the
             * current relative priority.
             */
            if ((cc = get_collchar(ellipsis_start, 1)) == NULL) {
                INTERR;
                return;
            }
            for (i = 0; i < NUM_WT; i++) {
                collpri_t *p;
                if (((ref = ellipsis_weights[i]) == -1) ||
                    ((p = get_pri(ref)) == NULL) ||
                    (p->pri == -1)) {
                    set_pri(cc->ref[i], nextpri, RESOLVED);
                } else {
                    set_pri(cc->ref[i], ref, REFER);
                }
                ellipsis_weights[i] = NULL;
            }
            ellipsis_start++;
            nextpri++;
        }
    }

    currchar = get_collchar(wc, 1);
}

void
start_order_collelem(collelem_t *e)
{
    start_order(T_COLLELEM);
    currelem = e;
}

void
start_order_ellipsis(void)
{
    int i;

    start_order(T_ELLIPSIS);

    if (lastorder != T_CHAR) {
        errf(_("illegal starting point for range"));
        return;
    }

    for (i = 0; i < NUM_WT; i++) {
        ellipsis_weights[i] = order_weights[i];
    }
}

void
define_collelem(char *name, wchar_t *wcs)
{
    collelem_t  *e;
    avl_index_t where1;
    avl_index_t where2;
    int     i;

    if (wcslen(wcs) >= COLLATE_STR_LEN) {
        errf(_("expanded collation element too long"));
        return;
    }

    if ((e = calloc(sizeof (*e), 1)) == NULL) {
        errf(_("out of memory"));
        return;
    }
    e->expand = wcs;
    e->symbol = name;

    /*
     * This is executed before the order statement, so we don't
     * know how many priorities we *really* need.  We allocate one
     * for each possible weight.  Not a big deal, as collating-elements
     * prove to be quite rare.
     */
    for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
        e->ref[i] = new_pri();
    }

    /* A character sequence can only reduce to one element. */
    if ((avl_find(&elem_by_symbol, e, &where1) != NULL) ||
        (avl_find(&elem_by_expand, e, &where2) != NULL)) {
        errf(_("duplicate collating element definition"));
        return;
    }
    avl_insert(&elem_by_symbol, e, where1);
    avl_insert(&elem_by_expand, e, where2);
}

void
add_order_bit(int kw)
{
    uint8_t bit = DIRECTIVE_UNDEF;

    switch (kw) {
    case T_FORWARD:
        bit = DIRECTIVE_FORWARD;
        break;
    case T_BACKWARD:
        bit = DIRECTIVE_BACKWARD;
        break;
    case T_POSITION:
        bit = DIRECTIVE_POSITION;
        break;
    default:
        INTERR;
        break;
    }
    collinfo.directive[collinfo.directive_count] |= bit;
}

void
add_order_directive(void)
{
    if (collinfo.directive_count >= COLL_WEIGHTS_MAX) {
        errf(_("too many directives (max %d)"), COLL_WEIGHTS_MAX);
    }
    collinfo.directive_count++;
}

static void
add_order_pri(int32_t ref)
{
    if (curr_weight >= NUM_WT) {
        errf(_("too many weights (max %d)"), NUM_WT);
        return;
    }
    order_weights[curr_weight] = ref;
    curr_weight++;
}

void
add_order_collsym(collsym_t *s)
{
    add_order_pri(s->ref);
}

void
add_order_char(wchar_t wc)
{
    collchar_t *cc;

    if ((cc = get_collchar(wc, 1)) == NULL) {
        INTERR;
        return;
    }

    add_order_pri(cc->ref[curr_weight]);
}

void
add_order_collelem(collelem_t *e)
{
    add_order_pri(e->ref[curr_weight]);
}

void
add_order_ignore(void)
{
    add_order_pri(pri_ignore);
}

void
add_order_symbol(char *sym)
{
    collundef_t *c;
    if ((c = get_collundef(sym)) == NULL) {
        INTERR;
        return;
    }
    add_order_pri(c->ref[curr_weight]);
}

void
add_order_ellipsis(void)
{
    /* special NULL value indicates self reference */
    add_order_pri(NULL);
}

void
add_order_subst(void)
{
    subst_t *s;
    avl_index_t where;
    int i;

    if ((s = calloc(sizeof (*s), 1)) == NULL) {
        errf(_("out of memory"));
        return;
    }
    s->key = new_pri();

    /*
     * We use a self reference for our key, but we set a high bit
     * to indicate that this is a substitution reference.  This
     * will expedite table lookups later, and prevent table
     * lookups for situations that don't require it.  (In short,
     * its a big win, because we can skip a lot of binary
     * searching.)
     */
    set_pri(s->key, (nextpri | COLLATE_SUBST_PRIORITY), RESOLVED);

    for (i = 0; i < curr_subst; i++) {
        s->ref[i] = subst_weights[i];
        subst_weights[i] = 0;
    }
    curr_subst = 0;

    if (avl_find(&substs[curr_weight], s, &where) != NULL) {
        INTERR;
        return;
    }
    avl_insert(&substs[curr_weight], s, where);

    /*
     * We are using the current (unique) priority as a search key
     * in the substitution table.
     */
    add_order_pri(s->key);
}

static void
add_subst_pri(int32_t ref)
{
    if (curr_subst >= COLLATE_STR_LEN) {
        errf(_("substitution string is too long"));
        return;
    }
    subst_weights[curr_subst] = ref;
    curr_subst++;
}

void
add_subst_char(wchar_t wc)
{
    collchar_t *cc;


    if (((cc = get_collchar(wc, 1)) == NULL) ||
        (cc->wc != wc)) {
        INTERR;
        return;
    }
    /* we take the weight for the character at that position */
    add_subst_pri(cc->ref[curr_weight]);
}

void
add_subst_collelem(collelem_t *e)
{
    add_subst_pri(e->ref[curr_weight]);
}

void
add_subst_collsym(collsym_t *s)
{
    add_subst_pri(s->ref);
}

void
add_subst_symbol(char *ptr)
{
    collundef_t *cu;

    if ((cu = get_collundef(ptr)) != NULL) {
        add_subst_pri(cu->ref[curr_weight]);
    }
}

void
dump_collate(void)
{
    FILE            *f;
    int         i, j, n;
    size_t          sz;
    int32_t         pri;
    collelem_t      *ce;
    collchar_t      *cc;
    subst_t         *sb;
    char            vers[COLLATE_STR_LEN];
    collate_char_pri_t  char_pri[UCHAR_MAX + 1];
    collate_large_pri_t *large;
    collate_subst_t     *subst[COLL_WEIGHTS_MAX];
    collate_chain_pri_t *chain;

    (void) memset(&char_pri, 0, sizeof (char_pri));
    (void) memset(vers, 0, COLLATE_STR_LEN);
    (void) snprintf(vers, sizeof (vers), COLLATE_VERSION);

    /*
     * We need to make sure we arrange for the UNDEFINED field
     * to show up.
     */
    for (i = 0; i < NUM_WT; i++) {
        if (resolve_pri(pri_undefined[i]) == -1) {
            set_pri(pri_undefined[i], -1, RESOLVED);
            /* they collate at the end of everything else */
            collinfo.undef_pri[i] = COLLATE_MAX_PRIORITY;
        }
    }

    collinfo.undef_pri[NUM_WT] = COLLATE_MAX_PRIORITY;
    collinfo.directive[NUM_WT] = DIRECTIVE_UNDEFINED;

    /*
     * Ordinary character priorities
     */
    for (i = 0; i <= UCHAR_MAX; i++) {
        if ((cc = get_collchar(i, 0)) != NULL) {
            for (j = 0; j < NUM_WT; j++) {
                char_pri[i].pri[j] = resolve_pri(cc->ref[j]);
            }
        } else {
            for (j = 0; j < NUM_WT; j++) {
                char_pri[i].pri[j] =
                    resolve_pri(pri_undefined[j]);
            }
            /*
             * Per POSIX, for undefined characters, we
             * also have to add a last item, which is the
             * character code.
             */
            char_pri[i].pri[NUM_WT] = i;
        }
    }

    /*
     * Substitution tables
     */
    for (i = 0; i < collinfo.directive_count; i++) {
        collate_subst_t *st = NULL;
        n = collinfo.subst_count[i] = avl_numnodes(&substs[i]);
        if ((st = calloc(sizeof (collate_subst_t) * n, 1)) == NULL) {
            errf(_("out of memory"));
            return;
        }
        n = 0;
        for (sb = avl_first(&substs[i]); sb;
            sb = AVL_NEXT(&substs[i], sb)) {
            if ((st[n].key = resolve_pri(sb->key)) < 0) {
                /* by definition these resolve! */
                INTERR;
            }
            for (j = 0; sb->ref[j]; j++) {
                st[n].pri[j] = resolve_pri(sb->ref[j]);
            }
            n++;
        }
        if (n != collinfo.subst_count[i])
            INTERR;
        subst[i] = st;
    }

    /*
     * Chains, i.e. collating elements
     */
    collinfo.chain_count = avl_numnodes(&elem_by_expand);
    chain = calloc(sizeof (collate_chain_pri_t), collinfo.chain_count);
    if (chain == NULL) {
        errf(_("out of memory"));
        return;
    }
    for (n = 0, ce = avl_first(&elem_by_expand);
        ce != NULL;
        ce = AVL_NEXT(&elem_by_expand, ce), n++) {
        (void) wsncpy(chain[n].str, ce->expand, COLLATE_STR_LEN);
        for (i = 0; i < NUM_WT; i++) {
            chain[n].pri[i] = resolve_pri(ce->ref[i]);
        }
    }
    if (n != collinfo.chain_count)
        INTERR;

    /*
     * Large (> UCHAR_MAX) character priorities
     */
    large = calloc(sizeof (collate_large_pri_t) * avl_numnodes(&collchars),
        1);
    if (large == NULL) {
        errf(_("out of memory"));
        return;
    }

    i = 0;
    for (cc = avl_first(&collchars); cc; cc = AVL_NEXT(&collchars, cc)) {
        int undef = 0;
        /* we already gathered those */
        if (cc->wc <= UCHAR_MAX)
            continue;
        for (j = 0; j < NUM_WT; j++) {
            if ((pri = resolve_pri(cc->ref[j])) < 0) {
                undef = 1;
            }
            if (undef && (pri >= 0)) {
                /* if undefined, then all priorities are */
                INTERR;
            } else {
                large[i].pri.pri[j] = pri;
            }
        }
        if (!undef) {
            large[i].val = cc->wc;
            collinfo.large_pri_count = i++;
        }
    }

    if ((f = open_category()) == NULL) {
        return;
    }

    /* Time to write the entire data set out */

    if ((wr_category(vers, COLLATE_STR_LEN, f) < 0) ||
        (wr_category(&collinfo, sizeof (collinfo), f) < 0) ||
        (wr_category(&char_pri, sizeof (char_pri), f) < 0)) {
        return;
    }

    for (i = 0; i < NUM_WT; i++) {
        sz =  sizeof (collate_subst_t) * collinfo.subst_count[i];
        if (wr_category(subst[i], sz, f) < 0) {
            return;
        }
    }
    sz = sizeof (collate_chain_pri_t) * collinfo.chain_count;
    if (wr_category(chain, sz, f) < 0) {
        return;
    }
    sz = sizeof (collate_large_pri_t) * collinfo.large_pri_count;
    if (wr_category(large, sz, f) < 0) {
        return;
    }

    close_category(f);
}