Abbreviate a string using dictionary in C

Question

Looking for Code Review: Abbreviate a given string using a dictionary of acceptable abbreviations.

Notes:

Only "whole words" should be abbreviated. That is, if the word "record" can be abbreviated to "rec", "records" SHOULD NOT be abbreviated to "recs".

• A "whole word" is a sequence of alphanumeric characters.
• If the abbreviated string will not fit in the destination buffer clamp the string.
• Bonus points for allowing the substitution to be case insensitive, but also case aware. It should handle three cases, the original word all lower case, all upper case, or the first letter only being capitalized. Mixed cases can be handled in any reasonable way.

• For example, if the dictionary contains: "record"->"rec":

  • "record" should be replaced with "rec"
  • "Record" should be replaced with "Rec"
  • "RECORD" should be replaced with "REC"
  • "ReCord" can be replaced with "rec", "Rec" or "REC"

• @param str - source string to abbreviate (NULL terminated)

• @param str_abbr - destination buffer to store abbreviated version of 'str'
• @param str_abbr_len - length of 'str_abbr' buffer, including NULL terminator
• @param dictionary - array of acceptable abbreviations
• @param dictionary_len - number of items in dictionary

abbr.h

#include <stdlib.h>

typedef struct
{
    const char * full;
    const char * abbr;
} dictionary_t;

void abbreviate_string(const char * str, char * str_abbr, size_t str_abbr_len, dictionary_t * dictionary, size_t dictionary_len);

const char* CheckMatchinDictionary(char *result, dictionary_t* dictionary, size_t dictionary_len ); 

abbr.c

#include "abbr.h"

void abbreviate_string(const char * str, char * str_abbr, size_t str_abbr_len, dictionary_t * dictionary, size_t dictionary_len)
{
    const char* inputString = str;
    char ** wordArray  = NULL;
    int numOfWords = 0;

    char* word = strtok (inputString," ,-.:;");
    while (word != NULL)
    {
        wordArray = realloc (wordArray, sizeof (char*) * ++numOfWords);

        //Check memory allocation
        if(wordArray == NULL)
            exit(-1);

        wordArray[numOfWords - 1] = word;
        word = strtok (NULL, " ,-.:;");
    }

    memset(str_abbr, 0, str_abbr_len - 1);
    int i;
    int stringLength = 0;
    for(i=0; i < numOfWords; ++i )
    {
        const char* result = CheckMatchinDictionary(wordArray[i], dictionary, dictionary_len );

        // Append to the str_abbr only if fits in the destination buffer
        if( stringLength < str_abbr_len - 1)
        {
            if(result != NULL)
            {
                strcat(str_abbr, result);
                stringLength += strlen(result);
            }
            else
            {
                strcat(str_abbr, wordArray[i]);
                stringLength += strlen(wordArray[i]);
            }

            strcat(str_abbr, " ");
            stringLength += 1;
        }
        else
        {
            if(result != NULL)
                strncat(str_abbr, result, str_abbr_len - stringLength - 1);
            else
                strncat(str_abbr, wordArray[i], str_abbr_len - stringLength - 1 );
        }

    }
    //printf("The abbreviated string is %s\n", str_abbr);

}

// Function to check the match from the dictionary
const char* CheckMatchinDictionary(char *input, dictionary_t* dictionary, size_t dictionary_len )
{
    unsigned int index;
    for(index=0; index < dictionary_len; ++index)
    {
        if(strcmp(dictionary[index].full, input) == 0)
            return dictionary[index].abbr;

        else if(strcasecmp(dictionary[index].full, input) == 0)
        {
           size_t length = strlen(dictionary[index].abbr);
           char* substr = malloc(sizeof(char) * length);
           strncpy(substr, input, length);
           substr[length + 1] = '\0';
           return substr;
        }

    }

    return NULL;
}

main

#include <string.h>
#include <stdio.h>
#include "abbr.h"

int main(void)
{
    /* Sample Dictionary */
    dictionary_t dictionary[] =
    {
        {"record", "rec"},
        {"maximum", "max"},
        {"minimum", "min"},
        {"number", "no"}
    };

    char str[100];
    char str_abbr[100];

    strcpy(str, "maximum record rate is:");

    abbreviate_string(str, str_abbr, sizeof(str_abbr), dictionary,   sizeof(dictionary) / sizeof(dictionary[0]));

    printf("%s -> %s\n", str, str_abbr);

    return 0;
}

Answer 1

1. Save time. Compile code with all warnings enabled.

2. Format code, with an auto formatter (saves time). Even better, unless a width is specified, Format narrow enough to prevent horizontal scroll bars when posted here.

3. Members of dictionary_t used in code before definition. If dictionary_t was defined in "abbr.h", then its re-declaration does not belong in main.c

4. #include <string.h> missing before call of strtok(). Standard include files should not be counted on to exist in "abbr.h".

5. Calling strtok (inputString,... with const char* inputString is undefined behavior as inputString points to const data.

6. #include <stdlib.h> missing before call of realloc().

7. Rather than sizeof (char*), use sizeof *wordArray in wordArray = realloc (wordArray, sizeof (char*) * ++numOfWords);. It is easier to code correctly, review and maintain.

8. CheckMatchinDictionary() called before declaration.

9. if( stringLength < str_abbr_len - 1) mixes signed-ness of compare. Suggest

   size_t str_abbr_len
   
   // int stringLength = 0;
   //....
   // if( stringLength < str_abbr_len - 1)
   
   size_t stringLength = 0;
   ....
   if(stringLength + 1 < str_abbr_len)
   

10. Strange code uses -1 in memset(str_abbr, 0, str_abbr_len - 1); If str_abbr_len == 0, then a far-too-big value is passed to memset(). Further, this does not completely fill the called array with zeros. (Bug?) Recommend memset(str_abbr, 0, str_abbr_len);. Further: Suggest name change: to str_abbr_len to str_abbr_size. The length of a string does not count the null character. Size better conveys the size of the array that holds a string.

11. strcasecmp() is not a standard C library function. Easier enough to make an equivalent function with tolower(), toupper().

12. Good attempted use of const.

13. The missing "abbr.h" unnecessarily complicated the review. @Toby Speight Better to have added it.

14. Bug? I would have expected stringLength updated in the else block.

15. As the function does not change the dictionary, code could use const to better convey code's function and allow some optimizations.

    void abbreviate_string(const char * str, char * str_abbr, size_t str_abbr_len, 
        // dictionary_t * dictionary, size_t dictionary_len)
        const dictionary_t * dictionary, size_t dictionary_len)
    

16. Advanced: pointers certainly do not point to overlapped data, so add restrict for additional optimization potential.

    void abbreviate_string(const char * restrict str, char * restrict str_abbr, 
        size_t str_abbr_len, const dictionary_t * restrict dictionary, 
        size_t dictionary_len)
    

17. A common idiom is to place the pointers to changed data first, rather than in the middle.

    //abbreviate_string(str, str_abbr, str_abbr_len, dictionary, dictionary_len)
      abbreviate_string(str_abbr, str_abbr_len, str, dictionary, dictionary_len)
    

18. Appended abbr.h should be tolerant of being included multiple times. Research code guards.