Convert pattern matching functions to NFA

Jan Breuer

2013-03-13 2dcf7d9fecb776290b33c35f80857986ff3e7f21

Convert pattern matching functions to NFA

 libscpi/src/utils.c

@@ -154,146 +154,201 @@
    return FALSE;
}

bool_t locateText(const char * str1, size_t len1, char ** str2, size_t * len2) {
enum locate_text_states {
    STATE_FIRST_WHITESPACE,
    STATE_TEXT_QUOTED,
    STATE_TEXT,
    STATE_LAST_WHITESPACE,
    STATE_COMMA,
    STATE_ERROR,
};

struct locate_text_nfa {
    enum locate_text_states state;
    int32_t startIdx;
    int32_t stopIdx;
    size_t i;
    int quot = 0;
    int32_t strStart = -1;
    int32_t strStop = -1;
    int valid = 0;
};


    for (i = 0; i < len1; i++) {
        if ((strStart < 0) && isspace((unsigned char)str1[i])) {
            continue;
        }

        if ((strStart < 0) && !quot && (str1[i] == '"')) {
            quot = 1;
            continue;
        }

        if (strStart < 0) {
            strStart = i;
        }

        if ((strStop < 0) && quot && (str1[i] == '"')) {
            strStop = i;
            valid = 1;
            continue;
        }

        if ((strStop >= 0) && quot && (str1[i] == ',')) {
            break;
        }

        if ((strStop >= 0) && quot && !isspace((unsigned char)str1[i])) {
            valid = 0;
        }

        if (!quot && !isspace((unsigned char)str1[i]) && (str1[i] != ',')) {
            strStop = i;
        }

        if (isspace((unsigned char)str1[i])) {
            continue;
        }

        if ((strStop >= 0) && (str1[i] == ',')) {
            valid = 1;
            break;
        }
    }

    if ((i == len1) && !quot) {
        valid = 1;
        if (strStop < 0) {
            strStop = i;
        } else {
            strStop++;
        }
        if (strStart < 0) {
            strStart = i;
        }
    } else if (!quot) {
        strStop++;
    }


    if (valid) {
        if (str2) {
            *str2 = (char *) &str1[strStart];
        }

        if (len2) {
            *len2 = strStop - strStart;
        }
    }

    return valid;
/**
 * Test locate text state, if it is correct final state
 */
static inline bool_t isFinalState(enum locate_text_states state) {
    return (
        ((state) == STATE_COMMA)
        || ((state) == STATE_LAST_WHITESPACE)
        || ((state) == STATE_TEXT) ||
        ((state) == STATE_FIRST_WHITESPACE)
    );
}

bool_t locateStr(const char * str1, size_t len1, char ** str2, size_t * len2) {
    size_t i;
    int32_t strStart = -1;
    int32_t strStop = -1;
    int valid = 0;


    for (i = 0; i < len1; i++) {
        if ((strStart < 0) && isspace((unsigned char)str1[i])) {
            continue;
        }

        if (strStart < 0) {
            strStart = i;
        }

        if (!isspace((unsigned char)str1[i]) && (str1[i] != ',')) {
            strStop = i;
        }

        if (isspace((unsigned char)str1[i])) {
            continue;
        }

        if (str1[i] == ',') {
            valid = 1;

            if (strStop < 0) {
                strStop = i;
/**
 * Perform locateText automaton to search string pattern
 * @param nfa stores automaton state
 * @param c current char processed
 */
static inline bool_t locateTextAutomaton(struct locate_text_nfa * nfa, unsigned char c) {
    switch(nfa->state) {
        /* first state locating only white spaces */
        case STATE_FIRST_WHITESPACE:
            if(isspace(c)) {
                nfa->startIdx = nfa->stopIdx = nfa->i + 1;
            } else if (c == ',') {
                nfa->state = STATE_COMMA;
            } else if (c == '"') {
                nfa->startIdx = nfa->i + 1;
                nfa->state = STATE_TEXT_QUOTED;
            } else {
                nfa->startIdx = nfa->i;
                nfa->stopIdx = nfa->i + 1;
                nfa->state = STATE_TEXT;
            }
            break;
        }
        /* state locating any text inside "" */
        case STATE_TEXT_QUOTED:
            if(c == '"') {
                nfa->state = STATE_LAST_WHITESPACE;
                nfa->stopIdx = nfa->i;
            }
            break;
        /* locate text ignoring quotes */
        case STATE_TEXT:
            if (c == ',') {
                nfa->state = STATE_COMMA;
            } else if (!isspace(c)) {
                nfa->stopIdx = nfa->i + 1;
            }
            break;
        /* locating text after last quote */
        case STATE_LAST_WHITESPACE:
            if (c == ',') {
                nfa->state = STATE_COMMA;
            } else if (!isspace(c)) {
                nfa->state = STATE_ERROR;
            }
            break;
    }

    if (i == len1) {
        valid = 1;
        if (strStop < 0) {
            strStop = i;
        } else {
            strStop++;
        }
        if (strStart < 0) {
            strStart = i;
        }
    /* if it is terminating state, break from for loop */
    if ((nfa->state == STATE_COMMA) || (nfa->state == STATE_ERROR)) {
        return FALSE;
    } else {
        strStop++;
        return TRUE;
    }
}

/**
 * Locate text in string. Text is separated by two ""
 *   example: "text", next parameter
 *   regexp: ^[ \t\r\n]*"([^"]*)"[ \t\r\n]*,?
 *   regexp: ^[ \t\r\n]*([^,]*)[ \t\r\n]*,?
 * @param str1 string to be searched
 * @param len1 length of string
 * @param str2 result
 * @param len2 length of result
 * @return string str1 contains text and str2 was set
 */
bool_t locateText(const char * str1, size_t len1, const char ** str2, size_t * len2) {
    struct locate_text_nfa nfa = {
        .startIdx = 0,
        .stopIdx = 0,
        .state = STATE_FIRST_WHITESPACE,
    };

    for (nfa.i = 0; nfa.i < len1; nfa.i++) {
        if(FALSE == locateTextAutomaton(&nfa, str1[nfa.i])) {
            break;
        }
    }

    if (isFinalState(nfa.state)) {

    if (valid) {
        if (str2) {
            *str2 = (char *) &str1[strStart];
            *str2 = &str1[nfa.startIdx];
        }

        if (len2) {
            *len2 = strStop - strStart;
            *len2 = nfa.stopIdx - nfa.startIdx;
        }
        return TRUE;
    }
    return FALSE;
}

/**
 * Perform locateStr automaton to search string pattern
 * @param nfa stores automaton state
 * @param c current char processed
 */
static inline bool_t locateStrAutomaton(struct locate_text_nfa * nfa, unsigned char c) {
    switch(nfa->state) {
        /* first state locating only white spaces */
        case STATE_FIRST_WHITESPACE:
            if(isspace(c)) {
                nfa->startIdx = nfa->stopIdx = nfa->i + 1;
            } else if (c == ',') {
                nfa->state = STATE_COMMA;
            } else {
                nfa->startIdx = nfa->i;
                nfa->stopIdx = nfa->i + 1;
                nfa->state = STATE_TEXT;
            }
            break;
        /* locate text ignoring quotes */
        case STATE_TEXT:
            if (c == ',') {
                nfa->state = STATE_COMMA;
            } else if (!isspace(c)) {
                nfa->stopIdx = nfa->i + 1;
            }
            break;
    }

    /* if it is terminating state, break from for loop */
    if ((nfa->state == STATE_COMMA) || (nfa->state == STATE_ERROR)) {
        return FALSE;
    } else {
        return TRUE;
    }
}

/**
 * Locate string in string.
 *   regexp: ^[ \t\r\n]*([^,]*)[ \t\r\n]*,?
 * @param str1 string to be searched
 * @param len1 length of string
 * @param str2 result
 * @param len2 length of result
 * @return string str1 contains text and str2 was set
 */
bool_t locateStr(const char * str1, size_t len1, const char ** str2, size_t * len2) {
    struct locate_text_nfa nfa = {
        .startIdx = 0,
        .stopIdx = 0,
        .state = STATE_FIRST_WHITESPACE,
    };

    for (nfa.i = 0; nfa.i < len1; nfa.i++) {
        if(FALSE == locateStrAutomaton(&nfa, str1[nfa.i])) {
            break;
        }
    }

    return valid;
    if (isFinalState(nfa.state)) {

        if (str2) {
            *str2 = &str1[nfa.startIdx];
        }

        if (len2) {
            *len2 = nfa.stopIdx - nfa.startIdx;
        }
        return TRUE;
    }
    return FALSE;
}


/**
 * Count white spaces from the beggining
 * @param cmd - command

 libscpi/src/utils.h

@@ -52,12 +52,15 @@
    size_t doubleToStr(double val, char * str, size_t len) LOCAL;
    size_t strToLong(const char * str, int32_t * val) LOCAL;
    size_t strToDouble(const char * str, double * val) LOCAL;
    bool_t locateText(const char * str1, size_t len1, char ** str2, size_t * len2) LOCAL;
    bool_t locateStr(const char * str1, size_t len1, char ** str2, size_t * len2) LOCAL;
    bool_t locateText(const char * str1, size_t len1, const char ** str2, size_t * len2) LOCAL;
    bool_t locateStr(const char * str1, size_t len1, const char ** str2, size_t * len2) LOCAL;
    size_t skipWhitespace(const char * cmd, size_t len) LOCAL;
    bool_t matchPattern(const char * pattern, size_t pattern_len, const char * str, size_t str_len) LOCAL;

#define min(a, b)  (((a) < (b)) ? (a) : (b))
#define max(a, b)  (((a) > (b)) ? (a) : (b))

#if 0
#define max(a,b) \
   ({ __typeof__ (a) _a = (a); \
       __typeof__ (b) _b = (b); \
@@ -68,6 +71,8 @@
       __typeof__ (b) _b = (b); \
     _a < _b ? _a : _b; })

#endif

#ifdef    __cplusplus
}
#endif

 libscpi/test/test_scpi_utils.c

@@ -138,8 +138,8 @@

void test_locateText() {

    char * v;
    char * b;
    const char * v;
    const char * b;
    size_t l;
    int result;

@@ -152,7 +152,7 @@
        result = locateText(v, strlen(v), &b, &l);       \
        CU_ASSERT(result == ex_res);                    \
        if (result == TRUE) {                           \
                CU_ASSERT(b == (s + ex_off));           \
                CU_ASSERT(b == (v + ex_off));           \
                CU_ASSERT(l == ex_len);                 \
        } else {                                        \
                CU_ASSERT(b == NULL);                   \
@@ -162,6 +162,8 @@


    TEST_LOCATE_TEXT("", TRUE, 0, 0);
    TEST_LOCATE_TEXT(",", TRUE, 0, 0);
    TEST_LOCATE_TEXT("\"\",", TRUE, 1, 0);
    TEST_LOCATE_TEXT("   ", TRUE, 3, 0);
    TEST_LOCATE_TEXT("a", TRUE, 0, 1);
    TEST_LOCATE_TEXT("ab", TRUE, 0, 2);
@@ -186,8 +188,8 @@

void test_locateStr() {

    char * v;
    char * b;
    const char * v;
    const char * b;
    size_t l;
    int result;

@@ -209,6 +211,7 @@
    } while(0)                                          \
    
    TEST_LOCATE_STR("", TRUE, 0, 0);
    TEST_LOCATE_STR(",", TRUE, 0, 0);
    TEST_LOCATE_STR("   ", TRUE, 3, 0);
    TEST_LOCATE_STR("a", TRUE, 0, 1);
    TEST_LOCATE_STR("ab", TRUE, 0, 2);