CODEWITHSUNDEEP
cdictionarydata-structures
Crappy Programmer
Crappy Programmer

Reputation: 195

In plain C, how to do you make the equivalent of a "map"?

So I'm trying to make a program completely from scratch (no libraries included) and I have a function which is very ugly:

int parseUnsignedInt ( char * ch, unsigned int * ui )
{
/* Starting at character ch, reads the unsigned int into the
       variable ui, returns the number of characters read.
*/
    ui = 0; // unsigned integer into which the string representation is read 
    int m = 1; // multiplier
    int ncp = 0; // # of characters parsed
    while (*ch)
    {
        bool chid = false; // ch is a decimal
        for (int k = 0; k < decmapLength; ++k)
        {
            if (decmap[k].cval == *ch)
            {
                ui += decmap[k].ival * m;
                m *= 10;
                chid = true;
                break;
            }
        }
        if (!chid) break;
        ++ncp;
        ++ch;
    }
    return ncp;
}

Part of its ugliness stems from the fact that I needed a way to associate characters to integers ('0'->0, '1'->1, ..., '9'->9) and made an array or structs

typedef struct icpair
{
    char cval;
    int ival;
} icpair;

icpair decmap [10] = {{'0',0}, {'1',1}, {'2',2}, {'3',3}, {'4',4}, {'5',5}, {'6',6}, {'7',7}, {'8',8}, {'9',9}};
int decmapLength = sizeof(decmap)/sizeof(icpair);

for that purpose. But, looking up a value, if it even exists, accounts for the unsightly number of lines that could be condensed if there was a better way to do this in pure C. I also want this to be reliable, so no ASCII value subtraction like '9'-'ch'. Is this possible in pure C, and if so, how is it implemented?

Upvotes: 6

Views: 4303

Answers (2)

Jongware
Jongware

Reputation: 22478

If you want to map any 10 random characters to 0..9, you don't need a separate struct element ival -- the 'natural order' already indexes the correct digit right away. So you can use a single char array with a length of 10 random characters as a lookup.

If the characters in this array are successively incrementing by 1, you do not need the array at all. In that case you can subtract the first code, test if the result is between 0 and 9, indicating success, or reject the character otherwise.

This holds true for the set of digits in C, because the specification of C requires it:

In both the source and execution basic character sets, the value of each character after 0 in the above list shall be one greater than the value of the previous. (5.2.1 Character sets in ISO/IEC 9899:201x Normative Draft 2011 (PDF))

Thus, to get a numerical value for any digit, character - '0' is always true.

As a side note, this is not defined for the ranges A..Z and a..z. That means that if you treat 'A' as 0, it is not guaranteed that 'J'-'A' == 9. For that, you need the simple look-up character array again.

Upvotes: 0

Sydius
Sydius

Reputation: 14277

A simple map API in C might look like:

Map * map_create(void);
void map_insert(Map * map, char key, int value);
int map_find(Map * map, char key);
void map_destroy(Map * map);

Then you'd be able to do map_find(map, '0') to get the integer value, perhaps with the semantics of returning -1 if it isn't found.

The implementation of this could be done with a number of different data structures, depending on your needs. If you don't care about maintaining an order, a hash table would probably be most appropriate. If you do need to maintain the order based on key, for example, a binary tree might be a better idea (perhaps a red-black tree).

You could modify the API to take void * for the key and for the value to generalize it a bit (in the absence of generics, which C lacks). There would be added complexity like providing a hashing function for a hash table or a comparison function for a binary tree.

That said, doing *ch - '0' is safe to do and will work just fine.

Upvotes: 1

Related Questions