ure.c

ldap服务器源码

         i++, sp++) ;

    /*
     * Now find out if the state exists in the symbol's state list.
     */
    for (i = 0, stp = sp->states.slist;
         i < sp->states.slist_used && state > *stp; i++, stp++) ;

    if (i == sp->states.slist_used || state < *stp) {
        /*
         * Need to add the state in order.
         */
        if (sp->states.slist_used == sp->states.slist_size) {
            if (sp->states.slist_size == 0)
              sp->states.slist = (ucs2_t *) malloc(sizeof(ucs2_t) << 3);
            else
              sp->states.slist = (ucs2_t *)
                  realloc((char *) sp->states.slist,
                          sizeof(ucs2_t) * (sp->states.slist_size + 8));
            sp->states.slist_size += 8;
        }
        if (i < sp->states.slist_used)
          (void) _ure_memmove((char *) (sp->states.slist + i + 1),
                              (char *) (sp->states.slist + i),
                              sizeof(ucs2_t) * (sp->states.slist_used - i));
        sp->states.slist[i] = state;
        sp->states.slist_used++;
    }
}

static ucs2_t
_ure_add_state(ucs2_t nstates, ucs2_t *states, _ure_buffer_t *b)
{
    ucs2_t i;
    _ure_state_t *sp;

    for (i = 0, sp = b->states.states; i < b->states.states_used; i++, sp++) {
        if (sp->st.slist_used == nstates &&
            memcmp((char *) states, (char *) sp->st.slist,
                   sizeof(ucs2_t) * nstates) == 0)
          break;
    }

    if (i == b->states.states_used) {
        /*
         * Need to add a new DFA state (set of NFA states).
         */
        if (b->states.states_used == b->states.states_size) {
            if (b->states.states_size == 0)
              b->states.states = (_ure_state_t *)
                  malloc(sizeof(_ure_state_t) << 3);
            else
              b->states.states = (_ure_state_t *)
                  realloc((char *) b->states.states,
                          sizeof(_ure_state_t) * (b->states.states_size + 8));
            sp = b->states.states + b->states.states_size;
            (void) memset((char *) sp, '\0', sizeof(_ure_state_t) << 3);
            b->states.states_size += 8;
        }

        sp = b->states.states + b->states.states_used++;
        sp->id = i;

        if (sp->st.slist_used + nstates > sp->st.slist_size) {
            if (sp->st.slist_size == 0)
              sp->st.slist = (ucs2_t *)
                  malloc(sizeof(ucs2_t) * (sp->st.slist_used + nstates));
            else
              sp->st.slist = (ucs2_t *)
                  realloc((char *) sp->st.slist,
                          sizeof(ucs2_t) * (sp->st.slist_used + nstates));
            sp->st.slist_size = sp->st.slist_used + nstates;
        }
        sp->st.slist_used = nstates;
        (void) AC_MEMCPY((char *) sp->st.slist, (char *) states,
                      sizeof(ucs2_t) * nstates);
    }

    /*
     * Return the ID of the DFA state representing a group of NFA states.
     */
    return i;
}

static void
_ure_reduce(ucs2_t start, _ure_buffer_t *b)
{
    ucs2_t i, j, state, eval, syms, rhs;
    ucs2_t s1, s2, ns1, ns2;
    _ure_state_t *sp;
    _ure_symtab_t *smp;

    b->reducing = 1;

    /*
     * Add the starting state for the reduction.
     */
    _ure_add_state(1, &start, b);

    /*
     * Process each set of NFA states that get created.
     */
    for (i = 0; i < b->states.states_used; i++) {
        sp = b->states.states + i;

        /*
         * Push the current states on the stack.
         */
        for (j = 0; j < sp->st.slist_used; j++)
          _ure_push(sp->st.slist[j], b);

        /*
         * Reduce the NFA states.
         */
        for (j = sp->accepting = syms = 0; j < b->stack.slist_used; j++) {
            state = b->stack.slist[j];
            eval = 1;

            /*
             * This inner loop is the iterative equivalent of recursively
             * reducing subexpressions generated as a result of a reduction.
             */
            while (eval) {
                switch (b->expr[state].type) {
                  case _URE_SYMBOL:
                    ns1 = _ure_make_expr(_URE_ONE, _URE_NOOP, _URE_NOOP, b);
                    _ure_add_symstate(b->expr[state].lhs, ns1, b);
                    syms++;
                    eval = 0;
                    break;
                  case _URE_ONE:
                    sp->accepting = 1;
                    eval = 0;
                    break;
                  case _URE_QUEST:
                    s1 = b->expr[state].lhs;
                    ns1 = _ure_make_expr(_URE_ONE, _URE_NOOP, _URE_NOOP, b);
                    state = _ure_make_expr(_URE_OR, ns1, s1, b);
                    break;
                  case _URE_PLUS:
                    s1 = b->expr[state].lhs;
                    ns1 = _ure_make_expr(_URE_STAR, s1, _URE_NOOP, b);
                    state = _ure_make_expr(_URE_AND, s1, ns1, b);
                    break;
                  case _URE_STAR:
                    s1 = b->expr[state].lhs;
                    ns1 = _ure_make_expr(_URE_ONE, _URE_NOOP, _URE_NOOP, b);
                    ns2 = _ure_make_expr(_URE_PLUS, s1, _URE_NOOP, b);
                    state = _ure_make_expr(_URE_OR, ns1, ns2, b);
                    break;
                  case _URE_OR:
                    s1 = b->expr[state].lhs;
                    s2 = b->expr[state].rhs;
                    _ure_push(s1, b);
                    _ure_push(s2, b);
                    eval = 0;
                    break;
                  case _URE_AND:
                    s1 = b->expr[state].lhs;
                    s2 = b->expr[state].rhs;
                    switch (b->expr[s1].type) {
                      case _URE_SYMBOL:
                        _ure_add_symstate(b->expr[s1].lhs, s2, b);
                        syms++;
                        eval = 0;
                        break;
                      case _URE_ONE:
                        state = s2;
                        break;
                      case _URE_QUEST:
                        ns1 = b->expr[s1].lhs;
                        ns2 = _ure_make_expr(_URE_AND, ns1, s2, b);
                        state = _ure_make_expr(_URE_OR, s2, ns2, b);
                        break;
                      case _URE_PLUS:
                        ns1 = b->expr[s1].lhs;
                        ns2 = _ure_make_expr(_URE_OR, s2, state, b);
                        state = _ure_make_expr(_URE_AND, ns1, ns2, b);
                        break;
                      case _URE_STAR:
                        ns1 = b->expr[s1].lhs;
                        ns2 = _ure_make_expr(_URE_AND, ns1, state, b);
                        state = _ure_make_expr(_URE_OR, s2, ns2, b);
                        break;
                      case _URE_OR:
                        ns1 = b->expr[s1].lhs;
                        ns2 = b->expr[s1].rhs;
                        ns1 = _ure_make_expr(_URE_AND, ns1, s2, b);
                        ns2 = _ure_make_expr(_URE_AND, ns2, s2, b);
                        state = _ure_make_expr(_URE_OR, ns1, ns2, b);
                        break;
                      case _URE_AND:
                        ns1 = b->expr[s1].lhs;
                        ns2 = b->expr[s1].rhs;
                        ns2 = _ure_make_expr(_URE_AND, ns2, s2, b);
                        state = _ure_make_expr(_URE_AND, ns1, ns2, b);
                        break;
                    }
                }
            }
        }

        /*
         * Clear the state stack.
         */
        while (_ure_pop(b) != _URE_NOOP) ;

        /*
         * Reset the state pointer because the reduction may have moved it
         * during a reallocation.
         */
        sp = b->states.states + i;

        /*
         * Generate the DFA states for the symbols collected during the
         * current reduction.
         */
        if (sp->trans_used + syms > sp->trans_size) {
            if (sp->trans_size == 0)
              sp->trans = (_ure_elt_t *)
                  malloc(sizeof(_ure_elt_t) * (sp->trans_used + syms));
            else
              sp->trans = (_ure_elt_t *)
                  realloc((char *) sp->trans,
                          sizeof(_ure_elt_t) * (sp->trans_used + syms));
            sp->trans_size = sp->trans_used + syms;
        }

        /*
         * Go through the symbol table and generate the DFA state transitions
         * for each symbol that has collected NFA states.
         */
        for (j = syms = 0, smp = b->symtab; j < b->symtab_used; j++, smp++) {
            sp = b->states.states + i;

            if (smp->states.slist_used > 0) {
                sp->trans[syms].lhs = smp->id;
                rhs = _ure_add_state(smp->states.slist_used,
                                     smp->states.slist, b);
                /*
                 * Reset the state pointer in case the reallocation moves it
                 * in memory.
                 */
                sp = b->states.states + i;
                sp->trans[syms].rhs = rhs;

                smp->states.slist_used = 0;
                syms++;
            }
        }

        /*
         * Set the number of transitions actually used.
         */
        sp->trans_used = syms;
    }
    b->reducing = 0;
}

static void
_ure_add_equiv(ucs2_t l, ucs2_t r, _ure_buffer_t *b)
{
    ucs2_t tmp;

    l = b->states.states[l].id;
    r = b->states.states[r].id;

    if (l == r)
      return;

    if (l > r) {
        tmp = l;
        l = r;
        r = tmp;
    }

    /*
     * Check to see if the equivalence pair already exists.
     */
    for (tmp = 0; tmp < b->equiv_used &&
             (b->equiv[tmp].l != l || b->equiv[tmp].r != r);
         tmp++) ;

    if (tmp < b->equiv_used)
      return;

    if (b->equiv_used == b->equiv_size) {
        if (b->equiv_size == 0)
          b->equiv = (_ure_equiv_t *) malloc(sizeof(_ure_equiv_t) << 3);
        else
          b->equiv = (_ure_equiv_t *) realloc((char *) b->equiv,
                                              sizeof(_ure_equiv_t) *
                                              (b->equiv_size + 8));
        b->equiv_size += 8;
    }
    b->equiv[b->equiv_used].l = l;
    b->equiv[b->equiv_used].r = r;
    b->equiv_used++;
}

/*
 * Merge the DFA states that are equivalent.
 */
static void
_ure_merge_equiv(_ure_buffer_t *b)
{
    ucs2_t i, j, k, eq, done;
    _ure_state_t *sp1, *sp2, *ls, *rs;

    for (i = 0; i < b->states.states_used; i++) {
        sp1 = b->states.states + i;
        if (sp1->id != i)
          continue;
        for (j = 0; j < i; j++) {
            sp2 = b->states.states + j;
            if (sp2->id != j)
              continue;
            b->equiv_used = 0;
            _ure_add_equiv(i, j, b);
            for (eq = 0, done = 0; eq < b->equiv_used; eq++) {
                ls = b->states.states + b->equiv[eq].l;
                rs = b->states.states + b->equiv[eq].r;
                if (ls->accepting != rs->accepting ||
                    ls->trans_used != rs->trans_used) {
                    done = 1;
                    break;
                }
                for (k = 0; k < ls->trans_used &&
                         ls->trans[k].lhs == rs->trans[k].lhs; k++) ;
                if (k < ls->trans_used) {
                    done = 1;
                    break;
                }

                for (k = 0; k < ls->trans_used; k++)
                  _ure_add_equiv(ls->trans[k].rhs, rs->trans[k].rhs, b);
            }
            if (done == 0)
              break;
        }
        for (eq = 0; j < i && eq < b->equiv_used; eq++)
          b->states.states[b->equiv[eq].r].id =
              b->states.states[b->equiv[eq].l].id;
    }

    /*
     * Renumber the states appropriately.
     */
    for (i = eq = 0, sp1 = b->states.states; i < b->states.states_used;
         sp1++, i++)
      sp1->id = (sp1->id == i) ? eq++ : b->states.states[sp1->id].id;
}

/*************************************************************************
 *
 * API.
 *
 *************************************************************************/

ure_buffer_t
ure_buffer_create(void)
{
    ure_buffer_t b;

    b = (ure_buffer_t) calloc(1, sizeof(_ure_buffer_t));

    return b;
}

void
ure_buffer_free(ure_buffer_t buf)
{
    unsigned long i;

    if (buf == 0)
      return;

    if (buf->stack.slist_size > 0)
      free((char *) buf->stack.slist);

    if (buf->expr_size > 0)
      free((char *) buf->expr);

    for (i = 0; i < buf->symtab_size; i++) {
        if (buf->symtab[i].states.slist_size > 0)
          free((char *) buf->symtab[i].states.slist);
    }

    if (buf->symtab_size > 0)
      free((char *) buf->symtab);

    for (i = 0; i < buf->states.states_size; i++) {
        if (buf->states.states[i].trans_size > 0)
          free((char *) buf->states.states[i].trans);
        if (buf->states.states[i].st.slist_size > 0)
          free((char *) buf->states.states[i].st.slist);
    }

    if (buf->states.states_size > 0)
      free((char *) buf->states.states);

    if (buf->equiv_size > 0)
      free((char *) buf->equiv);

    free((char *) buf);
}

ure_dfa_t
ure_compile(ucs2_t *re, unsigned long relen, int casefold, ure_buffer_t buf)
{
    ucs2_t i, j, state;
    _ure_state_t *sp;
    _ure_dstate_t *dsp;
    _ure_trans_t *tp;
    ure_dfa_t dfa;

    if (re == 0 || *re == 0 || relen == 0 || buf == 0)
      return 0;

    /*
     * Reset the various fields of the compilation buffer.  Default the flags
     * to indicate the presense of the "^$" pattern.  If any other pattern
     * occurs, then this flag will be removed.  This is done to catch this
     * special pattern and handle it specially when matching.
     */
    buf->flags = _URE_DFA_BLANKLINE | ((casefold) ? _URE_DFA_CASEFOLD : 0);
    buf->reducing = 0;