6
\$\begingroup\$

I am doing C coding practice by reinventing a getline function that works with any streams. Any comments on the overall code quality, including correctness, style and performance, are greatly appreciated.

fgetln.h:

#ifndef FGETLN_H
#define FGETLN_H
#include <stdio.h>

char *fgetln(FILE *fp);
/* 
 * Read a line from fp, dynamically allocate memory and store it as a string.
 * The '\n' at the end of the line and any '\0' before are discarded. Return
 * a pointer to the string when successful; return NULL if the line is empty
 * or an error occurs.
 *
 * This function implements the "callee allocates, caller frees" model. You
 * should pass the returned pointer to free() when it is no longer needed.
 */

#endif  // FGETLN_H

fgetln.c:

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

#define EXPAND_RATIO 2
// Aggressiveness of memory expansion, must be an integer ≥ 2.

char *fgetln(FILE *fp)
{
    signed char c;

    // Look for hints of an empty line and discard any '\0' at the start.
    while (true) {
        c = getc(fp);
        if (c == '\0') continue;
        if (c == '\n' || c == EOF) return NULL;
        break;
    }

    // If we have reached here, the line has content in it.
    ungetc(c, fp);

    char *p_tmp, *line = NULL;
    size_t arr_size = sizeof(char);
    bool end_of_line = false;
    unsigned long long i = 0;

    p_tmp = realloc(line, arr_size);
    if (p_tmp == NULL) goto err_cleanup;
    line = p_tmp;

    do {
        c = getc(fp);
        if (c == '\0') continue;
        if (c == '\n' || c == EOF) {
            end_of_line = true;
            c = '\0';
        }

        if ((i * sizeof(char)) == arr_size) {
            if (arr_size == SIZE_MAX) {
                if (c != '\0') goto err_cleanup;  // Too long
            } else {
                // Assuming SIZE_MAX % sizeof(char) == 0.
                arr_size = arr_size > (SIZE_MAX / EXPAND_RATIO)
                         ? SIZE_MAX
                         : arr_size * EXPAND_RATIO;
                p_tmp = realloc(line, arr_size);
                if (p_tmp == NULL) goto err_cleanup;
                line = p_tmp;
            }
        }

        line[i++] = c;
    } while (!end_of_line);

    // Shorten the string to its logical size if available.
    size_t logic_size = i * sizeof(char);

    if (logic_size < arr_size) {
        p_tmp = realloc(line, logic_size);
        if (p_tmp == NULL) goto err_cleanup;
        line = p_tmp;
    }
    return line;

err_cleanup:
    free(line);
    return NULL;
}

#undef EXPAND_RATIO
\$\endgroup\$
4
  • \$\begingroup\$ "The '\n' at the end of the line and any '\0' before are discarded." deserves clarification. Yes both are discarded, yet '\0' does not stop the reading whereas '\n' does. Is that your intent? \$\endgroup\$ Jan 8 at 21:49
  • \$\begingroup\$ "... if the line is empty" would benefit with more info. C line defines line as "... each line consisting of zero or more characters plus a terminating new-line character. Whether the last line requires a terminating new-line character is implementation-defined." So a line includes the '\n'. Is your "line is empty" is when code reads and get nothing, just end-of-file, initially reads a '\n', and/or something else? \$\endgroup\$ Jan 8 at 21:53
  • \$\begingroup\$ @chux Yes what you described is the intended behavior. What I had in mind is kind of data cleansing. The function reads a line from the stream, where only \n and EOF are deemed as line delimiters (the two are also read in as part of the line). But if for any reason a \0 appears in the middle, I chose to disacrd it and move on because if it's kept mid-array, data behind it becomes inaccessible to printf("%s") and some string-handling functions. \$\endgroup\$
    – UM-Li
    Jan 9 at 1:49
  • \$\begingroup\$ @chux Then the processed array, free of \0 in the middle, is stored as a string, with the \n or EOF replaced with a \0. Situations I thought of where the "line is empty" include "[zero or more \0]EOF", "[zero or more \0]\n", and nothing at all. Now I see it's conceptually confusing to name the function "get a line" while discarding the terminating new-line character. I was bugged by the inconsistency that the tail of the stream may lack an \n at the end while previous lines all have one. \$\endgroup\$
    – UM-Li
    Jan 9 at 1:49
5
\$\begingroup\$

Excellent comment in the header. It's very important to be clear who owns the returned memory and how to release it. It ought to mention that both newline and \0 are considered as end-of-line characters.

Good realloc() usage - we don't leak when allocation fails.

Some small improvements:

#define EXPAND_RATIO 2

Why do we need a preprocessor macro for this? I would use a simple static const size_t.

size_t arr_size = sizeof(char);

sizeof (char) is 1 by definition (since sizeof yields the number of char required for its argument). I wouldn't start with such a small buffer anyway, since almost every line will need several realloc() calls. Start with something sensible, such as 40 (half the width of a standard terminal).

p_tmp = realloc(line, arr_size);
if (p_tmp == NULL) goto err_cleanup;
line = p_tmp;

Since we know that line is null at this point, we should just use malloc() to be clearer, and eliminate a window where *line is invalid:

char *line = malloc(arr_size);
if (!line) return line;
    if ((i * sizeof(char)) == arr_size) {

We can remove the multiplication by 1 from this:

    if (i == arr_size) {
        if (arr_size == SIZE_MAX) {

Ooh, that's very thorough. We're unlikely to have managed to allocate that much memory in a single chunk!

            // Assuming SIZE_MAX % sizeof(char) == 0.

Again, any number modulo 1 is zero, so that's a truism, not a mere assumption.

#undef EXPAND_RATIO

Arguably overkill, given that this is the very end of the translation unit anyway.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Minor: "Why do we need a preprocessor macro for this? I would use a simple static const size_t" --> Then SIZE_MAX / EXPAND_RATIO would be a runtime division and not compile time as a const size_t object is not constant. Some compilers may be understanding though. \$\endgroup\$ Jan 8 at 11:20
  • 1
    \$\begingroup\$ "It ought to mention that both newline and NUL are considered as end-of-line characters." is a tad unclear as "NUL" is an ASCII code definition (not a C one) and NULL is a C one that are often confused with "NUL" given their similarity. I'd recommend '\0' or null character or maybe "NUL" --> "ASCII NUL". \$\endgroup\$ Jan 8 at 11:28
4
\$\begingroup\$

Overall, a good and thoughtful effort.

Bug: Treats character as EOF

When EOF == -1 and code reads a character with the value of 255, the c = getc(fp); likely converts that 255 to -1. Later, the loop incorrectly exits.

signed char c;
    c = getc(fp);
    if (c == '\n' || c == EOF) return NULL;  // Maybe true for wrong reason

Instead use an int c to well distinguish the 256 (0-255) + 1 (EOF) different responses from getc().

// signed char c;
int c;

Design weakness

Code should distinguish from reading an empty line and end-of-file. Then the caller can properly distinguish between an empty line and end-of-file. Testing for feof() is insufficient considering the various other reasons for a NULL return.

OP's design returns NULL for both.

 if (c == '\n' || c == EOF) return NULL;

Pseudo-code alternative (memory management not shown)

 Read input until \n of EOF
 if loop end due to EOF and nothing read (or input error), return NULL
 Append \0
 ...

More: Code returns NULL for 5 conditions (I recommend 3 with a mod):

  • Immediate '\n'. This I recommend to not return NULL.
  • Immediate end-of-file: OK
  • Immediate input error: I recommend to always return NULL on input error.
  • Out of memory (growing): OK
  • Out of memory (shrinking): I recommend to return the original pointer - see below.

Missing include

fgetln.c fails to include fgetln.h. This is important to test for consistency and makefile auto dependency generation. I recommend to include it first before other <> in this file.

Test needed with code using OP's algorithm.

Minor: Questionable type

unsigned long long i is sufficient as size_t i

Minor: Error exit not needed

If a memory re-allocation fails when shrinking, code could simply continue.

if (logic_size < arr_size) {
    p_tmp = realloc(line, logic_size);
    //if (p_tmp == NULL) goto err_cleanup;
    //line = p_tmp;
    if (p_tmp) line = p_tmp;
}

Non-ASCII code

Consider using only ASCII for maximum compliance.

// ... must be an integer ≥ 2.
... must be an integer >= 2.

Minor: sizeof(type) vs. sizeof(refenced pointer)

sizeof(char) is always 1. If code wants to emphasize the size of the referenced pointer, use it directly and avoid the effort to manually match the type.

char *line = NULL;
// size_t arr_size = sizeof(char);
size_t arr_size = sizeof *line;

This is easier to maintain, should one move code to say wchar_t *line = NULL;

Pedantic: missing check

Check return of ungetc(c, fp);.

... or, IMO better, re-write code to not need ungetc(). It is there mainly convenience of the loop.

Reasonable use of goto


Some sample alternative code. Memory management details only stubbed in.

void* realloc_grow(size_t *sz, void *s);
void realloc_shrink(size_t *sz, void *s);

char* fgetln(FILE *fp) {
  unsigned char *s = NULL;
  size_t i = 0;
  size_t sz = 0;
  int ch;

  while ((ch = fgetc(fp)) != EOF) {
    if (ch == '\0') {
      continue;
    }
    if (i + 1 >= sz) {
      if (realloc_grow(&sz, &s) == NULL) {
        free(s);
        return NULL; // OOM
      }
    }
    if (ch == '\n')
      break;
    s[i++] = (unsigned char) ch;
  }

  if (ch == EOF) {
    if (feof(fp)) {
      if (sz == 0) {
        return NULL; // end-of-file with no input
      }
    } else {
      free(s);
      return NULL; // input error
    }
  }

  s[i++] = '\0';
  realloc_shrink(&i, &s);
  return (char*) s;
}
\$\endgroup\$
6
  • \$\begingroup\$ Thank you very much for the detailed comments and sample code! After changing the type of c to int, a character with the value 255 is able to pass the first while loop. But if it would've caused char type overflow at the first while loop, I figure it will still overflow when being stored because line has the type char * too and is accordingly realloc()ed? Should I change the type of p_tmp and line to unsigned char *, or maybe avoid character types altogether in favor of integer types? \$\endgroup\$
    – UM-Li
    Jan 9 at 1:47
  • \$\begingroup\$ As for the unneeded test part, I was thinking of the edge case that the array can only accommodate one more character before its size exceeds SIZE_MAX. If c happens to be a line delimiter (\n or EOF), it is replaced with \0 and put in that last slot to form a string. If c is anything else (won't be \0, or the loop would've continueed before the replacement), the array cannot both hold it and form a string without exceeding SIZE_MAX. \$\endgroup\$
    – UM-Li
    Jan 9 at 1:55
  • \$\begingroup\$ But now I've noticed the bug in this conditional test. If i == arr_size == SIZE_MAX, writing to line[i] leads to buffer overflow. \$\endgroup\$
    – UM-Li
    Jan 9 at 1:55
  • 1
    \$\begingroup\$ @UM-Li "I figure it will still overflow when being stored because line has the type char * too" --> Conversion, not overflow is your concern here. The issue existed before with signed char c; ... c = getc(fp); and reading character 255 and assigning it to a signed char. That is the same situation with line[i++] = c; (c == 255, char is signed). When conversion is out of range to a signed integer, the result is implementation defined (ID). Fortunately that is usually simple wrap around and no trouble. To avoid this ID behavior, use unsigned char as in my sample code. \$\endgroup\$ Jan 9 at 1:57
  • \$\begingroup\$ @UM-Li ... the re-allocation is not an concern here as the issue is not one of buffer overflow, but out-of-range to char` conversions. \$\endgroup\$ Jan 9 at 2:00
3
\$\begingroup\$

Overall this isn't a bad effort. I can't see any problems, aside from clobbering the EOF, mostly it's stylistic choices. So good job 👍.

Comments go above

It's much more common for the comment in a header to be ABOVE the function, rather than below it. This is ok for now as there's only one function, but when you have more it will confuse people.

If you're going to continue to put it below then you should at least put the function signature in the comment, so that people know which function you're talking about. i.e.

char *fgetln(FILE *fp);
/* 
 * fgetln:
 * Read a line from fp, dynamically allocate memory and store it as a string.

This is also true for:

#define EXPAND_RATIO 2
// Aggressiveness of memory expansion, must be an integer ≥ 2.

Be precise in your documentation

/* 
 * Read a line from fp, dynamically allocate memory and store it as a string.
 * The '\n' at the end of the line and any '\0' before are discarded. Return
 * a pointer to the string when successful; return NULL if the line is empty
 * or an error occurs.
 *
 * This function implements the "callee allocates, caller frees" model. You
 * should pass the returned pointer to free() when it is no longer needed.
 */

This reads as saying the \0 BEFORE the start of the line are discarded. The actual code discards all \0! This will confuse some people who expect inner \0 to be preserved.

/* 
 * fgetln:
 * Read from fp until '\n' or EOF and store it in dynamically allocate memory as a zero-terminated string.
 *
 * The '\n' at the end of the line is discarded, as are any '\0' read before the end of the line.
 
 * Return a pointer to the string when successful; 
 * Return NULL if the line is empty or an error occurs.
 *
 * This function implements the "callee allocates, caller frees" model. You
 * should pass the returned pointer to free() when it is no longer needed.
 */

Reading an empty line

 * a pointer to the string when successful; return NULL if the line is empty
 * or an error occurs.
 

How does a client using your code differentiate between and empty line and an error? Why do you consider an empty line to be so bad? :) Have you considered returning an empty string instead? i.e. return "";?

Use the correct return type from standard functions

signed char c;
c = getc(fp);

getc is defined as returning an int. You're losing the ability to check for EOF here, as the manual specifically says it returns a char cast as int or EOF.

Also, why specify that the char is signed? What use is that to you in this code? I can't see any checks that rely on the value of c being < 0.

unsigned long long i = 0;

This should be a size_t, as

  1. you're using it to hold the sizes of allocations
  2. you're using it in conjunction with sizeof, which returns size_t
  3. unsigned long long is MASSIVE and probably bigger than size_t, and therefore any valid allocation

ungetc

// If we have reached here, the line has content in it.
ungetc(c, fp);

Not all streams handle ungetc too well. It's usually better to handle the buffering of the last value yourself. (i.e. invert your loop so that it reads a char at the end of it, and the top of the loop expects a buffered char)

(Also, the manual for ungetc specifically points out it's going to cast the int into an unsigned char, furthering my confusion about your choice of signed char)

Appropriate length variable names

i is far too short for a variable that:

  1. Isn't directly a loop counter
  2. Has a scope that spans 50 lines of code

Also, i is misleading as it isn't a loop counter, it's a LENGTH. Therefore it should be named length or count or something.

Declare variables where they're needed and with the smallest scope

This:

char *p_tmp, *line = NULL;
size_t arr_size = sizeof(char);
bool end_of_line = false;
unsigned long long i = 0;

p_tmp = realloc(line, arr_size);
if (p_tmp == NULL) goto err_cleanup;
line = p_tmp;

is better as:

size_t arr_size = sizeof(char);
bool end_of_line = false;
unsigned long long i = 0;

char *line = NULL;
char *p_tmp = realloc(line, arr_size);
if (p_tmp == NULL) goto err_cleanup;
line = p_tmp;

This way the p_tmp and line variables are correctly scoped (i.e. they exist for as little as possible) and always have a valid value.

I would go so far as to say that an even better route is:

char *p_tmp = realloc(line, arr_size);
if (p_tmp == NULL) goto err_cleanup_noline; //or just return NULL here
char *line = p_tmp;

This way avoids line existing as a null pointer for a while. Thus we can now rememebr that line is ALWAYS non-null.

Or even just use malloc to begin with, as realloc for a non-existing pointer to a know size is a bit of obfuscation.

The same goes for c. It's better to declare individual c variables inside each scope rather than a single function-spanning c. This way ensures that no stale data is accidentally used.

DRY:

Don't repeat yourself

    c = getc(fp);
    if (c == '\0') continue;
    if (c == '\n' || c == EOF) {
        end_of_line = true;
        c = '\0';
    }

This code is identical to the previous block, except that it sets a boolean. This could easily be refactored into a function such as this:

char strip_until_next_char(bool *end_of_line) {
    while (true) {
        int c = getc(fp);
        if (c == '\0') continue;
        if (c == '\n' || c == EOF) {
            *end_of_line = true;
            return '\0';
        }
        *end_of_line = false;
        return (char) c;
    }
}

or:

bool strip_until_next_char(char *out_c) {
    while (true) {
        int c = getc(fp);
        if (c == '\0') continue;
        if (c == '\n' || c == EOF) {
            *out_c = '\0';
            return true;
        }
        *out_c = (char) c;
        return false;
    }
}

Spare me the details

Ideally, code would read like flowing English. That means it's easy to see what it does at an algorithmic level and we don't have to worry about which bits move where. It also means it's easy to adjust and spot the flaws in it. To do that we can refactor the code into functions that say what they do. Thus:

do {
    char c;
    end_of_line = strip_until_next_char(&c);
    
    bool ok = ensure_allocation_fits(string_length, &line, &arr_size, end_of_line);
    if (!ok) {
        goto err_cleanup;
    }

    line[i++] = c;
} while (!end_of_line);

sizeof(char)

sizeof returns multiples of char, thus sizeof(char) is defined as being 1. It's nice that you're being explicit about the contents of your allocations, but if so I think it'd be best if you did this:

size_t arr_size = 1 * sizeof(char);

average case

How often do you expect to do strings of size 1?

Currently you'll go 1, 2, 4, 8. So you'll do 4 reallocs just to get to an average length of a short string. Give that you do a shrink-realloc at the end of your program you might save yourself some time and simply start with an allocation of 100 or something.

undef

#undef EXPAND_RATIO

This is commendable, but also kind of pointless. Unless you expect the code to be included into something? Importantly though: it's not idiomatic. Most people only undef something when they want to immediately define it again.

\$\endgroup\$
4
  • \$\begingroup\$ Thank you for the review. What type i should be still bugs me. My intention was that i acts purely as an array index as in line[i++] = c;. I figured i doesn't represent size itself, thus the integer type and occurrences of i * sizeof(char) despite it's just "×1". Should i still be defined as a size_t? \$\endgroup\$
    – UM-Li
    Jan 8 at 18:15
  • \$\begingroup\$ "You're losing the ability to check for EOF here, as the manual specifically says it returns a char cast as int or EOF." --> A problem for a different reason. EOF is very often -1 and assigning signed char c = getc(fp); is not a problem when end-of-file/input error occurs. OTOH reading character 255 likely also results in a -1 saved - losing differentiation from EOF. IAC, agree with conclusion: use int c. \$\endgroup\$ Jan 9 at 2:12
  • \$\begingroup\$ The function uses an int to represent all chars and EOF. The cast to char is truncation, so you're technically losing the EOF, as that's out of range of the char. :) \$\endgroup\$
    – Pod
    Jan 9 at 13:36
  • 1
    \$\begingroup\$ @UM-Li: a big pain point for me when using C, especially with the POSIX API, is "which integer should this be??". There's so many of them and they all need to be used together! Why size_t in this case? Imagine if i was SIZE_MAX + 1. What would that mean for your program? Is it something you'd want it to be? Note that C will promote SIZE_MAX to unsigned long long in that equality check. \$\endgroup\$
    – Pod
    Jan 9 at 13:45

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.