Algorithm (and tests) to parse lists of unsigned 32-bit ints from strings in C

Question

What?

I have an algorithm that parses comma separated lists of unsigned 32-bit ints from strings. Here is an example of what a list could look like:

1302,51,2312,2,52

The algorithm uses a custom data structure called parse_input which is a data structure that is a FIFO of numbers. This structure is passed to another unrelated function that parses some data with the help of this list of numbers. parse_input_push is used to add a number to the queue.

The byte_array structure used in the tests has a separate code review.

I would like feedback on everything. Even the tests!

Files

Source

#define MAX_NUM_GLYPHS 11                                                                                                                                                                                           

static bool number_len_ok(const char *literal_num, size_t curr_num_len)                                                                                                                                             
{                                                                                                                                                                                                                   
        if (curr_num_len != MAX_NUM_GLYPHS - 1) return true;                                                                                                                                                        

        size_t i = 0;                                                                                                                                                                                               
        char *max_literal_num = "4294967296";                                                                                                                                                                       

        for (; i < curr_num_len; i++) {                                                                                                                                                                             
                if (literal_num[i] > max_literal_num[i]) return false;                                                                                                                                              
        }                                                                                                                                                                                                           

        return true;                                                                                                                                                                                                
}                                                                                                                                                                                                                   

int parse_num_list(struct parse_input *lookup, char *num_list)                                                                                                                                                      
{                                                                                                                                                                                                                   
        size_t i = 0;                                                                                                                                                                                               
        size_t curr_num_len = 0;                                                                                                                                                                                    
        size_t list_len = strlen(num_list);                                                                                                                                                                         
        char literals[MAX_NUM_GLYPHS] = {0};                                                                                                                                                                        
        char curr_glyph;                                                                                                                                                                                            
        bool prev_was_comma = false;                                                                                                                                                                                

        for (; i < list_len; i++) {                                                                                                                                                                                 
                if (curr_num_len >= MAX_NUM_GLYPHS) return -1;                                                                                                                                                      

                curr_glyph = num_list[i];                                                                                                                                                                           

                if (curr_glyph == ',') {                                                                                                                                                                            
                        if (prev_was_comma) return -2;                                                                                                                                                              
                        if (!number_len_ok(literals, curr_num_len)) return -1;                                                                                                                                      

                        parse_input_push(lookup, atoi(literals));                                                                                                                                                   
                        memset(literals, '\0', 10);                                                                                                                                                                 
                        curr_num_len = 0;                                                                                                                                                                           
                        prev_was_comma = true;                                                                                                                                                                      

                        continue;                                                                                                                                                                                   
                }                                                                                                                                                                                                   

                if (curr_glyph < '0' || curr_glyph > '9') return -2;                                                                                                                                                

                prev_was_comma = false;                                                                                                                                                                             
                literals[curr_num_len++] = curr_glyph;                                                                                                                                                              
        }                                                                                                                                                                                                           

        if (!number_len_ok(literals, curr_num_len)) return -1;                                                                                                                                                      

        parse_input_push(lookup, atoi(literals));                                                                                                                                                                   

        return 0;                                                                                                                                                                                                   
}

Tests

void test_ok_parse_num_list()                                                                                                                                                                                       
{                                                                                                                                                                                                                   
        char num_list[] = "124,1231231,2,20202,4294967296,1";                                                                                                                                                       
        struct byte_array *lookup_name = byte_array_from_cstring("chr1");                                                                                                                                           
        struct parse_input *lookup = parse_input_create(lookup_name);                                                                                                                                               
        int ret = parse_num_list(lookup, num_list);                                                                                                                                                                 

        byte_array_decref(lookup_name);                                                                                                                                                                             
        parse_input_decref(lookup);                                                                                                                                                                                 

        assert(ret == 0);                                                                                                                                                                                           

        printf("[ OK ] Parse num list\n");                                                                                                                                                                          
}                                                                                                                                                                                                                   

void test_too_big_parse_num_list()                                                                                                                                                                                  
{                                                                                                                                                                                                                   
        char num_list[] =  "124,1231231,2,20202,42949672952,1";                                                                                                                                                     
        char num_list2[] = "124,1231231,2,20202,9999999999,666";                                                                                                                                                    
        char num_list3[] = "124,1231231,2,20202,4294967297,1";                                                                                                                                                      
        struct byte_array *lookup_name = byte_array_from_cstring("chr1");                                                                                                                                           
        struct parse_input *lookup = parse_input_create(lookup_name);                                                                                                                                               
        int ret = parse_num_list(lookup, num_list);                                                                                                                                                                 

        assert(ret == -1);                                                                                                                                                                                          
        ret = parse_num_list(lookup, num_list2);                                                                                                                                                                    
        assert(ret == -1);                                                                                                                                                                                          
        ret = parse_num_list(lookup, num_list3);                                                                                                                                                                    
        assert(ret == -1);                                                                                                                                                                                          

        byte_array_decref(lookup_name);                                                                                                                                                                             
        parse_input_decref(lookup);                                                                                                                                                                                 

        printf("[ OK ] Parse too big num list\n");                                                                                                                                                                  
}                                                                                                                                                                                                                   

void test_invalid_parse_num_list()                                                                                                                                                                                  
{                                                                                                                                                                                                                   
        char num_list[] =  "124,1231231.,2,20202,429496,1";                                                                                                                                                         
        char num_list2[] = "124,1231231,2,20202,99999999ö,666";                                                                                                                                                     
        char num_list3[] = "124,1231231,2,20202,4294967,1,,,,";                                                                                                                                                     
        struct byte_array *lookup_name = byte_array_from_cstring("chr1");                                                                                                                                           
        struct parse_input *lookup = parse_input_create(lookup_name);                                                                                                                                               
        int ret = parse_num_list(lookup, num_list);                                                                                                                                                                 

        assert(ret == -2);                                                                                                                                                                                          
        ret = parse_num_list(lookup, num_list2);                                                                                                                                                                    
        assert(ret == -2);                                                                                                                                                                                          
        ret = parse_num_list(lookup, num_list3);                                                                                                                                                                    
        assert(ret == -2);                                                                                                                                                                                          

        byte_array_decref(lookup_name);                                                                                                                                                                             
        parse_input_decref(lookup);                                                                                                                                                                                 

        printf("[ OK ] Parse invalid num list\n");                                                                                                                                                                  
}

Lstor · Accepted Answer · 2013-07-19 13:06:42Z

Having tests is good. I recommend using a test framework, for example googletest.
You are obviously using C99 (otherwise parts of your code wouldn't compile). C99 does not require variable instantiation at the beginning of a scope. You should generally create your variables as late as possible, to limit their scope. This includes moving your for loop counters into the loop.

Like this:

for (size_t i = 0; i < curr_num_len; i++) {
    if (literal_num[i] > max_literal_num[i]) return false;
}

Use a const instead of #define. That way you get normal scope rules, easier debugging, more readable compilation errors and so on.
Don't use literal constants ("magic numbers"). Why does your function return -2 and -1? Give them names instead: return PARSE_ERROR;. Why do you memset 10 bytes of literals, when its size is MAX_NUM_GLYPHS?
I'd probably rename number_len_ok() to something along is_number_too_large() (and inverted the return values).
You are assuming that numbers are located together and in order in the character set. It doesn't necessarily have to be that way (although it almost always is).
Are the input strings allowed to have spaces? You don't have any tests for that.
Your parsing function could probably be written in a bit cleaner and/or more readable way. This is left as an exercise to the reader :-)
You're missing #includes for memset, atoi etc.

Again, thank you very much! Will look into googletest, didn't even know it existed before! — rzetterberg, Jul 19 '13 at 13:11

William Morris · Answer 2 · 2013-07-22 21:25:54Z

What is number_len_ok supposed to do? max_literal_num is set to "4294967296" which is the string rep of 2^32. Is this supposed to be the maximum length number you can parse - ten characters in other words? Why would you compare the individual characters of the number you are parsing to the individual chars of this string? If you pass the string "9", length 1 the function will return false. This makes no sense to me.

I don't really follow why you are using such a complicated parsing function either, so maybe I am missing the point of this code altogether...

EDIT

It is now clear to me that you really are just trying to parse out the numbers from a string (I was a bit obtuse before :-). My comment above was wrong in that "9" would not fail due to the initial conditional, but many (most?) 10-character strings starting from "1000000007" would fail.

As I said, the code is very complicated for what it does. You should investigate what the standard library can offer for this sort of parsing. The strtol function is like atoi but sets errno if it finds that the number cannot be parsed (eg the number is too long or not valid). strtol returns a signed long (there is also a strtoul for unsigned long), which can be greater than 32 bits so if you really must restrict input to 32-bit integers you will need to test its return value.

Something like the following would seem to do what you need without all of the copying characters and other tests etc.

static int parse(...lookup, const char *s)
{
    char *end;
    errno = 0;
    while (*s != '\0') {
        long n = strtol(s, &end, 0);
        if (errno != 0) {
            // handle EINVAL, ERANGE (see man strtol)
        } else if (end == s) {
            // handle case where no number was found
        } else if (*end != ',') {
            // handle delimiter other than comma
        } else {
            parse_input_push(lookup, n);
        }
        s = end + 1;
    }
    return ...
}

Note that testing is good. For something like this it is quite possible to test all good inputs for a single-number string:

for (int i=0; i<LONG_MAX; ++i) {
    char buf[100];
    snprintf(buf, sizeof buf, "%ld", i);
    if (parse(lookup, i) != 0) {
        // Failed !!!
    }
    else if (i != /* get number from 'lookup' */) {
        // Failed !!!
    }
}

Hope this is more useful than my initial comment :-)

Thank you for pointing this out. It's not readable, very messy AND I haven't even written a comment. Basically the goal is to check that when the number string has the maximum amount of characters allowed the actual numeric value is not larger than 4294967296. For example the number string 9999999999 has the same amount of characters as 4294967296, but the actual numeric value is higher. — rzetterberg, Jul 21 '13 at 14:46
Unreadability, messiness and a lack of comments are secondary problems compared to the function not doing what you think it does :-) — William Morris, Jul 21 '13 at 23:50
That's why I wrote tests to make sure the function behaves as expected. And all tests succeeds. Maybe I missed what use case you say doesn't work? — rzetterberg, Jul 22 '13 at 10:49
I see now that your initial condition rules out most of the failing numbers (such as '9' suggested in my answer). But there are still many that fail. Start at 1000000007 and keep counting. — William Morris, Jul 22 '13 at 12:48
Actually 1000000007 is a valid number and will not fail. I added it to my tests just to be sure. — rzetterberg, Jul 22 '13 at 12:58

asked	11 months ago
viewed	168 times
active	4 months ago

current community

your communities

more stack exchange communities

Algorithm (and tests) to parse lists of unsigned 32-bit ints from strings in C

What?

Files

Source

Tests

2 Answers

Your Answer

Not the answer you're looking for? Browse other questions tagged c algorithm parsing lookup c99 or ask your own question.

Linked

Hot Network Questions

current community

your communities

more stack exchange communities

Algorithm (and tests) to parse lists of unsigned 32-bit ints from strings in C

What?

Files

Source

Tests

2 Answers

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c algorithm parsing lookup c99 or ask your own question.

Linked

Related

Hot Network Questions