2
\$\begingroup\$

Here I asked this question:

My goal is to go through the list of all English words (separated by '\n' characters) and find the longest word which doesn't have any of these characters: "gkmqvwxz". And I want to optimize it as much as possible

I updated the code with the help of suggestions from answers, but I still need comments on this updated version

Changes:

  1. Name of the file and the forbidden characters are no longer hard-coded. They are passed by arguments.
  2. Added several error checks.
  3. Used pointers instead of indexes.
  4. buffer is freed when we're done with it.
  5. Used bool instead of int for the return type of is_legal.
  6. Parameters to is_legal are made const since we don't change them.
  7. Skip next lines ('\n') remaining from previous lines.
  8. Added some functions to keep main simple.
  9. Removed superfluous headers (#include <string.h>, #include <stddef.h>, #include <unistd.h>).
  10. is_legal need not know about the entire buffer. Just the relevant pointers are now sent.
  11. length is no longer fixed. We get the size of the array at runtime
  12. buffer is terminated with null.

Updated code:

#include <ctype.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>


static inline bool is_legal(const char* beg, size_t size, const char* bad)
{
    for (; size-- !=0 ; ++beg) {                                 /* go through current word */
        char ch = tolower(*beg);                                /* The char might be upper case */
        for (const char* bad_ptr = bad; *bad_ptr; ++bad_ptr)
            if (ch == *bad_ptr)                                 /* If it is found, return false */
                return false;
    }

    return true;                                                /* else return true */
}

static inline size_t get_next_word_size(const char* beg)
{
    size_t size = 0; /* resulting size */
    for (; beg[size] && beg[size] != '\n'; ++size) /* read the next word */
    { } /* for loop doesn't have a body */
    return size;
}

static inline char* get_buffer(const char* filename)
{
    char *buffer = NULL;                     /* contents of the text file */

    size_t length;                 /* maximum size */
    FILE* fp;
    fp = fopen(filename, "rb");

    if (!fp) {                               /* checking if file is properly opened */
        perror("Couldn't open the file\n");
        return NULL;
    }

    if (fseek(fp, 0, SEEK_END)) {
        perror("Failed reading");
        return NULL;
    }

    length = ftell(fp);

    if (fseek(fp, 0, SEEK_SET)) {
        perror("Failed reading");
        return NULL;
    }

    buffer = malloc(length + 1); /* +1 for null terminator */

    if (buffer == NULL) {                   /* checking if memory is allocated properly */
        perror("Failed to allocate memory\n");
        free(buffer);
        return NULL;
    }

    fread(buffer, 1, length, fp);           /* read it all */
    fclose(fp);

    buffer[length] = '\0';                  /* terminate the string with null*/
    return buffer;
}


int main(int argc, char **argv)
{
    if (argc < 3) {
        printf("Usage: FileName BadChars");
        return 0;
    }

    char* filename = argv[1];
    char* badchars = argv[2];

    char *buffer = get_buffer(filename);

    if (buffer == NULL) {
        return -1;
    }

    const char *beg = buffer;               /* current word boundaries */
    size_t size = 0;

    const char *mbeg = beg;                 /* result word */
    size_t msize = 0;

    while (beg[size]) {
        beg += size + 1;                 /* +1 to skip the '\n' */
        size = get_next_word_size(beg);  /* get the size of the next word */

        if (size > msize && is_legal(beg, size, badchars)) { /* if it is a fit, save it */
            mbeg = beg;
            msize = size;
        }
    }

    printf("%.*s\n", msize, mbeg);  /* print the output */

    free(buffer);
    return 0;
}

I would especially appreciate comments regarding the way the code reads the entire file into a single dynamically allocated array. About if and how it could be improved. I wouldn't like to sacrifice the performance, but some "best practices" especially about this part are very welcome.

\$\endgroup\$
4
\$\begingroup\$

Questionable Design

The idea to read in the entire file and then process it has weaknesses:

  1. Code can only handle files fit-able in memory. Risks allocation failures.

  2. Limitations with file sizes more than SIZE_MAX and LONG_MAX.

Code could read in 1 "word" at a time.

If performance is an issue, then read in perhaps a block of memory at a time.

Expand uses

Consider if argc == 2, then with a stream view of the file as suggested above, stdin could be used as the input. This makes for a useful "pipe-able" tool.

foo | Ayxan_filter "gkmqvwxz"

Certainly a bug on first word

Code's first call to get_next_word_size() is get_next_word_size(1), I'd expect get_next_word_size(0)

Perform a size++ at the end of the loop rather than a + 1 at the beginning.

Wrong type

Precision specifier should be int, else code is UB.

// printf("%.*s\n", msize, mbeg);
printf("%.*s\n", (int) msize, mbeg);

We can assume msize <= INT_MAX too, but pedantic code would check that first.

Questionable processing with binary mode

File is opened in binary mode "rb" yet looks for '\n' as end-of-line. I can foresee trouble with text files that end lines with "\r\n" or the rare "\r".

For me, to be highly portable, I would still open in binary mode but use the presence of '\n' or '\r' as an end-of-line.

Code can quit early

Should the file contain a null character, its presence will stop the search early.

Robust could would not treat the file as a string, but as a character array.

Resource leak

fclose(fp); missing from various error returns from get_buffer().

islower()

islower(int ch) is defined for values in the unsigned char range and EOF. Calling it with a char can lead to undefined behavior with a negative value.

// char ch = tolower(*beg); 
char ch = tolower((unsigned char) *beg); 

is_legal() alternative

// No need for size, but append '\n' to the `bad` before this call.
static inline bool is_legal(const char* beg, /* size_t size, */ const char* bad) {
   char *y = strcspn(beg, bad);
   if (y == NULL) return true;
   return *y == '\n';
}

Strongly recommend:

To really move things along, rather than search each character to see it it is in a list of bad ones, create a table (I'd do all using unsigned char) This is reasonable as long as UCHAR_MAX is a sane a value. I suspect this will measurable improve performance.

bool bad_boys[UCHAR_MAX+1];
foo_populate(bad_boys, bad);

// Insure '\0', '\n' are true.
static inline bool is_legal_alt2(const char* beg, const bool *bad_boys) {
   const unsigned char* ubeg = (const unsigned char*) beg;
   while (!bad_boys[*ubeg]) {
     ubeg++;
   }
   return *ubeg == '\n' || ubeg == '\0';
}

Code assumes size_t is like long

The length returned is a long. Its range may be more or less than size_t. Better code would not assume either.

//size_t length;
//length = ftell(fp);
size_t length;
long ilength = ftell(fp);

#if LONG_MAX >= SIZE_MAX
// >= used here rather than > due to later +1 in the allocation
if (ilength >= SIZE_MAX) {
    perror("Too big\n");
    return NULL;         
}   
#endif

// Unclear what risks you want to take here.
// Suggest to just bail out
if (ilength < 0) {
    perror("Unclear size\n");
    return NULL;            
}

length = (size_t) ilength;

No check for ftell(), fread() error

An error here is critical and not so improbable.

ilength = ftell(fp);
// add
if (ilength == -1) {
    perror("ftell error\n");
    return NULL;            
}

//fread(buffer, 1, length, fp);  
if (fread(buffer, 1, length, fp) != length) {
    perror("fread error\n");
    return NULL;            
}

Questionable style

Consider a while loop

//for (; beg[size] && beg[size] != '\n'; ++size) /* read the next word */
//{ } /* for loop doesn't have a body */

while (beg[size] && beg[size] != '\n') {
  ++size;
}

Unneeded free()

No need for call free(NULL);

 if (buffer == NULL) {
    perror("Failed to allocate memory\n");
//  free(buffer);  // not needed
    return NULL;
}

Consider sentinels

A "word" may have leading/trailing spaces. In a pathological case, the longest word will be "". Consider sentinels characters to show clearly the word.

//printf("%.*s\n", msize, mbeg);
printf("\"%.*s\"\n", msize, mbeg);
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.