darray.c

This is an implementation of double-array structure for representing trie, as proposed by Junichi A

            da_relocate_base (d, s, new_base);
            next = new_base + c;
        }
    } else {
        Symbols    *symbols;
        TrieIndex   new_base;

        symbols = symbols_new ();
        symbols_add (symbols, c);
        new_base = da_find_free_base (d, symbols);
        symbols_free (symbols);

        da_set_base (d, s, new_base);
        next = new_base + c;
    }
    da_alloc_cell (d, next);
    da_set_check (d, next, s);

    return next;
}

static Bool
da_check_free_cell (DArray         *d,
                    TrieIndex       s)
{
    da_extend_pool (d, s);
    return (da_get_check (d, s) < 0);
}

static Bool
da_has_children    (DArray         *d,
                    TrieIndex       s)
{
    TrieIndex   base;
    uint16      c;

    base = da_get_base (d, s);
    if (TRIE_INDEX_ERROR == base || base < 0)
        return FALSE;

    for (c = 0; c < TRIE_CHAR_MAX; c++)
        if (da_get_check (d, base + c) == s)
            return TRUE;

    return FALSE;
}

static Symbols *
da_output_symbols  (DArray         *d,
                    TrieIndex       s)
{
    Symbols    *syms;
    TrieIndex   base;
    uint16      c;

    syms = symbols_new ();

    base = da_get_base (d, s);
    for (c = 0; c < TRIE_CHAR_MAX; c++)
        if (da_get_check (d, base + c) == s)
            symbols_add_fast (syms, (TrieChar) c);

    return syms;
}

static TrieChar *
da_get_state_key   (DArray         *d,
                    TrieIndex       state)
{
    TrieChar   *key;
    int         key_size, key_length;
    int         i;

    key_size = 20;
    key_length = 0;
    key = (TrieChar *) malloc (key_size);

    /* trace back to root */
    while (da_get_root (d) != state) {
        TrieIndex   parent;

        if (key_length + 1 >= key_size) {
            key_size += 20;
            key = (TrieChar *) realloc (key, key_size);
        }
        parent = da_get_check (d, state);
        key[key_length++] = (TrieChar) (state - da_get_base (d, parent));
        state = parent;
    }
    key[key_length] = '\0';

    /* reverse the string */
    for (i = 0; i < --key_length; i++) {
        TrieChar temp;

        temp = key[i];
        key[i] = key[key_length];
        key[key_length] = temp;
    }

    return key;
}

#define DA_EXTENDING_STEPS 16

static TrieIndex
da_find_free_base  (DArray         *d,
                    const Symbols  *symbols)
{
    TrieChar    first_sym;
    TrieIndex   s;

    /* find first free cell that is beyond the first symbol */
    first_sym = symbols_get (symbols, 0);
    s = -da_get_check (d, da_get_free_list (d));
    while (s != da_get_free_list (d) && s < (TrieIndex) first_sym + 3)
        s = -da_get_check (d, s);
    if (s == da_get_free_list (d)) {
        s = first_sym + 3;
        while (da_extend_pool (d, s), da_get_check (d, s) > 0)
            ++s;
    }

    /* search for next free cell that fits the symbols set */
    while (!da_fit_symbols (d, s - first_sym, symbols)) {
        /* extend pool before getting exhausted */
        if (-da_get_check (d, s) == da_get_free_list (d))
            da_extend_pool (d, d->num_cells);

        s = -da_get_check (d, s);
    }

    return s - first_sym;
}

static Bool
da_fit_symbols     (DArray         *d,
                    TrieIndex       base,
                    const Symbols  *symbols)
{
    int         i;

    for (i = 0; i < symbols_num (symbols); i++) {
        if (!da_check_free_cell (d, base + symbols_get (symbols, i)))
            return FALSE;
    }
    return TRUE;
}

static void
da_relocate_base   (DArray         *d,
                    TrieIndex       s,
                    TrieIndex       new_base)
{
    TrieIndex   old_base;
    Symbols    *symbols;
    int         i;

    old_base = da_get_base (d, s);
    symbols = da_output_symbols (d, s);

    for (i = 0; i < symbols_num (symbols); i++) {
        TrieIndex   old_next, new_next, old_next_base;

        old_next = old_base + symbols_get (symbols, i);
        new_next = new_base + symbols_get (symbols, i);
        old_next_base = da_get_base (d, old_next);

        /* allocate new next node and copy BASE value */
        da_alloc_cell (d, new_next);
        da_set_check (d, new_next, s);
        da_set_base (d, new_next, old_next_base);

        /* old_next node is now moved to new_next
         * so, all cells belonging to old_next
         * must be given to new_next
         */
        /* preventing the case of TAIL pointer */
        if (old_next_base > 0) {
            uint16      c;

            for  (c = 0; c < TRIE_CHAR_MAX; c++)
                if (da_get_check (d, old_next_base + c) == old_next)
                    da_set_check (d, old_next_base + c, new_next);
        }

        /* free old_next node */
        da_free_cell (d, old_next);
    }

    symbols_free (symbols);

    /* finally, make BASE[s] point to new_base */
    da_set_base (d, s, new_base);
}

static void
da_extend_pool     (DArray         *d,
                    TrieIndex       to_index)
{
    TrieIndex   new_begin;
    TrieIndex   i;
    TrieIndex   free_tail;

    if (to_index < d->num_cells)
        return;

    d->cells = (DACell *) realloc (d->cells, (to_index + 1) * sizeof (DACell));
    new_begin = d->num_cells;
    d->num_cells = to_index + 1;

    /* initialize new free list */
    for (i = new_begin; i < to_index; i++) {
        da_set_check (d, i, -(i + 1));
        da_set_base (d, i + 1, -i);
    }

    /* merge the new circular list to the old */
    free_tail = -da_get_base (d, da_get_free_list (d));
    da_set_check (d, free_tail, -new_begin);
    da_set_base (d, new_begin, -free_tail);
    da_set_check (d, to_index, -da_get_free_list (d));
    da_set_base (d, da_get_free_list (d), -to_index);
}

void
da_prune (DArray *d, TrieIndex s)
{
    while (da_get_root (d) != s && !da_has_children (d, s)) {
        TrieIndex   parent;

        parent = da_get_check (d, s);
        da_free_cell (d, s);
        s = parent;
    }
}

static void
da_alloc_cell      (DArray         *d,
                    TrieIndex       cell)
{
    TrieIndex   prev, next;

    prev = -da_get_base (d, cell);
    next = -da_get_check (d, cell);

    /* remove the cell from free list */
    da_set_check (d, prev, -next);
    da_set_base (d, next, -prev);
}

static void
da_free_cell       (DArray         *d,
                    TrieIndex       cell)
{
    TrieIndex   i, prev;

    /* find insertion point */
    i = -da_get_check (d, da_get_free_list (d));
    while (i != da_get_free_list (d) && i < cell)
        i = -da_get_check (d, i);

    prev = -da_get_base (d, i);

    /* insert cell before i */
    da_set_check (d, cell, -i);
    da_set_base (d, cell, -prev);
    da_set_check (d, prev, -cell);
    da_set_base (d, i, -cell);
}

Bool
da_enumerate (DArray *d, DAEnumFunc enum_func, void *user_data)
{
    return da_enumerate_recursive (d, da_get_root (d), enum_func, user_data);
}

static Bool
da_enumerate_recursive (DArray     *d,
                        TrieIndex   state,
                        DAEnumFunc  enum_func,
                        void       *user_data)
{
    Bool        ret;
    TrieIndex   base;

    base = da_get_base (d, state);

    if (base < 0) {
        TrieChar   *key;

        key = da_get_state_key (d, state);
        ret = (*enum_func) (key, state, user_data);
        free (key);
    } else {
        Symbols *symbols;
        int      i;

        ret = TRUE;
        symbols = da_output_symbols (d, state);
        for (i = 0; ret && i < symbols_num (symbols); i++) {
            ret = da_enumerate_recursive (d, base + symbols_get (symbols, i),
                                          enum_func, user_data);
        }

        symbols_free (symbols);
    }

    return ret;
}

/*
vi:ts=4:ai:expandtab
*/