Read file line-by-line with circular buffer

Question

This isn't too complicated but I usually code in C++ instead of C. Doing memory management and IO in C always makes me feel like I'm doing everything wrong and making a mess. This is a small sample that has both which I think came out reasonable. I don't have C people to talk to so any critiques are welcome.

The goal here is to provide a means to read lines terminated by \n from a FILE pointer. The code tries to be reasonably efficient -- hence the circular buffer -- and not make unnecessary copies but it doesn't delve into detailed micro-optimization and I haven't profiled it. The test uses the code to simply print lines from a file.

I'd be interested even in style critiques of my C. I'd like to understand even the idiomatic differences between C and C++.

in.h

#include <stdio.h>
/* Is it possible to forward declare just FILE? */

struct LineCircBuffer
{
    FILE *f_;
    char *buff_;
    const char *buff_end_;
    const char *data_end_; /* last byte filled from file */
    const char *line_;
    const char *line_end_; /* points at ending newline */
};

int line_circ_buffer_init(struct LineCircBuffer* lcb, FILE *f);

void line_circ_buffer_free(struct LineCircBuffer* lcb);

void get_line(
    const char ** const ret_line,
    const char ** const ret_line_end,
    const struct LineCircBuffer * const lcb);

int next_line(struct LineCircBuffer * const lcb);

in.c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
/* stddef for size_t, I don't know if stdlib or stdio are guaranteed to provide
 * that typedef but on my system they do */
#include <stddef.h>
#include <assert.h>

#include "in.h"

#define TRUE 1
#define FALSE 0

#ifdef NDEBUG
#define INITIAL_BUFF_SIZE 4096
#else
/* smaller buffer size to reveal errors */
#define INITIAL_BUFF_SIZE 16
#endif

/* http://stackoverflow.com/a/1941337/1128289 */
#ifdef DEBUG
# define DEBUG_PRINT(x) printf x
#else
# define DEBUG_PRINT(x) do {} while (0)
#endif
/* usage: DEBUG_PRINT(("var1: %d; var2: %d; str: %s\n", var1, var2, str)); */

/* internal methods */
static void assert_lcb_valid_(const struct LineCircBuffer* lcb)
{
    /* I assume the compiler knows to skip this function if it's static and
     * NDEBUG is defined.  Rather than manually macro this out I rely on the
     * compiler and use a cast to void to make the compiler shut up about
     * warnings.
     */
    (void)lcb;
    assert(lcb != NULL);
    assert(lcb->buff_ != NULL);

    /* buff_ <= line_ <= data_end_ <= buff_end_ */
    assert(lcb->buff_ <= lcb->line_);
    /* true except for right after line_circ_buffer_init(), argh...
     * assert(lcb->line_ <= lcb->line_end_); */
    assert(lcb->line_end_ <= lcb->buff_end_);
}


static int all_lines_read_(struct LineCircBuffer *lcb)
{
    /* It is ambiguous whether
     * (1) A file has an empty last line and no final newline character.
     * (2) A file has a final newline character and no empty last line.
     * This code follows the Unix convention of a final newline characer.
     * This code will not print a blank line if there is a final newline,
     * but this code is tolerant of a non-blank last line that does not have a
     * newline.
     */
    /* line_end_ == data_end_ if no final newline
     * line_end_ + 1 == data_end_ otherwise
     */
    if (feof(lcb->f_) && (lcb->line_end_ == lcb->data_end_
                       || lcb->line_end_ + 1 == lcb->data_end_))
        return TRUE;
    else
        return FALSE;
}

/* external methods */
int line_circ_buffer_init(struct LineCircBuffer* lcb, FILE *f)
{
    /* 0: success
     * 1: memory allocation error
     * 2: file error
     */
    DEBUG_PRINT(("line_circ_buffer_init()"));

    if (!lcb)
        return 1;
    if (ferror(f))
        return 2;

    size_t buff_size = INITIAL_BUFF_SIZE;

    char *buff = (char*)malloc(buff_size);
    if (!buff)
        return 1;

    const size_t bytes_read = fread(buff, sizeof(char), buff_size, f);
    if (ferror(f))
        return 2;

    const char *data_end = buff + bytes_read;
    const char *buff_end = buff + buff_size;

    lcb->f_ = f;
    lcb->buff_ = buff;
    lcb->buff_end_ = buff_end;
    lcb->data_end_ = data_end;
    lcb->line_ = buff;
    lcb->line_end_ = buff - 1; /* weird, but it sets up next_line() */

    assert_lcb_valid_(lcb);
    return 0;
}


void line_circ_buffer_free(struct LineCircBuffer* lcb)
{
    free(lcb->buff_);
}


void get_line(
    const char ** const ret_line,
    const char ** const ret_line_end,
    const struct LineCircBuffer * const lcb)
{
    *ret_line = lcb->line_;
    *ret_line_end = lcb->line_end_;
}


int next_line(
    struct LineCircBuffer * const lcb)
{
    /* int next_line()
    * Advance the line produced by get_line().
    */
    /* return codes
    * 0: success, new line read and no errors detected
    * 1: no more lines can be read, no errors detected
    * 2: bad input (specifically, lcb == NULL)
    * 3: memory allocation error
    * 4: file error
    */

    DEBUG_PRINT(("next_line()"));

    if (lcb == NULL)
        return 2;
    /* assume internals of lcb in an ok state */

    if (all_lines_read_(lcb))
        return 1;

    /* next line */
    const char *line;
    const char *line_end;

    /* tentatively set start of line to terminator of previous line + 1 */
    line = lcb->line_end_ + 1;
    /* line may now be pointing at
     * (1) lcb->buff_end_
     * (2) a string that is unterminated
     * (4) a string that is terminated
     */

    /* if (1), fill the buffer from the beginning */
    if (line == lcb->buff_end_)
    {

        const size_t bytes_read = fread(lcb->buff_, sizeof(char),
                lcb->buff_end_ - lcb->buff_, lcb->f_);
        lcb->data_end_ = lcb->buff_ + bytes_read;
        line = lcb->buff_;
    }
    assert(line != lcb->buff_end_);
    /* (1) can no longer be true */

    line_end = (char*)memchr(line, '\n', lcb->data_end_ - line);
    /* while (2) is true, either
     * (a) feof is set and this is a full but unterminated line
     * (b) the buffer needs to be larger
     */
    while (line_end == NULL)
    {
        if (feof(lcb->f_))
        {
            line_end = lcb->data_end_;
            break;
        }

        // get a larger buffer for lcb->buff_ but hold onto the old one
        const size_t old_buff_size = lcb->buff_end_ - lcb->buff_;
        const size_t new_buff_size = old_buff_size*2;

        const char* const old_buff = lcb->buff_;
        const char* const old_buff_end = lcb->buff_end_;

        /* re-aiming lcb->buff_ invalidates most other members
         * fix buff_end_ and data_end_ in this loop
         * fix line_ and line_end_ at end of this function
         */
        lcb->buff_ = (char*)malloc(new_buff_size);
        if (!lcb->buff_)
            return 3;
        lcb->buff_end_ = lcb->buff_ + new_buff_size;

        /* copy unterminated string to front of the new buffer,
         * free old buffer */
        const size_t line_fragment_size = old_buff_end - line;
        memcpy(lcb->buff_, line, line_fragment_size);
        free((void*)old_buff);

        /* after copying, line starts at beginning of buffer */
        line = lcb->buff_;

        /* fill buffer from file and fix data_end_ */
        char *fill_start = lcb->buff_ + line_fragment_size;
        const size_t bytes_read = fread(fill_start, sizeof(char),
                lcb->buff_end_ - fill_start, lcb->f_);
        lcb->data_end_ = fill_start + bytes_read;

        /* look for terminator in the new data */
        line_end = (char*)memchr(fill_start, '\n', lcb->data_end_ - line);
    }
    assert(line_end != NULL || feof(lcb->f_));
    /* (2) can no longer be true */

    /* check (1) still untrue */
    assert(line != lcb->buff_end_);

    /* (3) remains, we're good to go */
    lcb->line_ = line;
    lcb->line_end_ = line_end;
    assert_lcb_valid_(lcb);
    return 0;
}

test.c

#include "in.h"
#include <stdio.h>

void usage(const char* argv0)
{
    printf("Usage: %s <input-filename>\n", argv0);
}

int main(int argc, char* argv[])
{
    if (argc < 1)
    {
        puts("Error: argc < 1");
        return 1;
    }
    if (argc != 2)
    {
        usage(argv[0]);
        return 1;
    }

    const char* const fname = argv[1];
    FILE* fp = fopen(fname, "rb");
    if (!fp)
    {
        printf("Unable to open file: %s\n", fname);
        return 1;
    }

    struct LineCircBuffer lcb;
    line_circ_buffer_init(&lcb, fp);

    while (!next_line(&lcb))
    {
        const char *line;
        const char *line_end;

        get_line(&line, &line_end, &lcb);
        const int line_size = line_end - line;

        printf("%.*s\n", line_size, line);
    }

    line_circ_buffer_free(&lcb);
}

Compiled as any of:

gcc-4.9 -Og -g -ggdb -std=c99 -Wall -Wextra -pedantic test.c in.c -o in_test
g++-4.9 -O3 -DNDEBUG -std=c++11 -Wall -Wextra -pedantic test.c in.c -o in_cpp
gcc-4.9 -O3 -DNDEBUG -std=c99 -Wall -Wextra -pedantic test.c in.c -o in

I compiled this as C++ with warnings as well as C because part of my goal when I use C is to be aware of how it is different from C++. I realize that void* in C automatically converts to char* but since this is such a trivial difference between the languages I went ahead and made it valid C++ too.

Usage is

./in filename

I tested it by diffing what was sent to stdout and the contents of a file. The output seems fine. Unfortunately homebrew won't install valgrind on OS X Yosemite so I'm sure about memory leaks. I do know of fgets.

Edward · Accepted Answer · 2014-12-31 19:35:47Z

Here are some things that may help you improve your code.

Simplify

It seems to me that this is a whole lot of code to implement something that could much more easily be done using fgets. Consider this possible implementation which both allocates memory and reads a line of text from a file:

#define BUFF_SIZE 16384

char *fgetsalloc(FILE *stream)
{
    char *s=malloc(BUFF_SIZE);
    if (s == NULL)
        return s;
    if (NULL == fgets(s, BUFF_SIZE, stream)) {
        free(s);
        return NULL;
    }
    return realloc(s, strlen(s));
}

Use `enum` for error return codes

Your error return codes are nicely documented in the source code, but not in the header and not as code. Ideally, the header would contain all the information needed for a user of the code. The things that are currently missing are brief descriptions of the code (including assumptions about internal state) and the error return codes. The return codes could easily be encapsulated as an enum.

Check for errors after `fread`

The line_circ_buffer_init() function checks for errors after fread but next_line does not.

Eliminate `bytes_read` variable

In every case, the bytes_read function can be eliminated by using the following line of code:

lcb->data_end_ = lcb->buff_ + fread(lcb->buff_, sizeof(char),
        lcb->buff_end_ - lcb->buff_, lcb->f_);

It doesn't make any significant difference in the generated code, but it helps the reader of the code understand by eliminating a variable that's only used once.

Use library functions to simplify your code

The large while loop within next_line could be mostly replaced by a single call to realloc.

Reconsider the interface

The structure currently has buff_end_ but when it's used within the code it's most often used to recover the length of the buffer. It would make more sense to simply store the length of the buffer. It would also reduce the confusion potential by having one fewer similarly named variables.

Also, the circular buffer structure is largely independent of the source of the data, so it may be more generally useful to implement it without such a close tie to the FILE structure.

Can the while loop really be replaced with realloc? The while loop doesn't copy everything, it copies from the last line fragment. I can't articulate well the reason I didn't use fgets so I didn't articulate such in the OP but... I guess I dislike that you have to know the max string length before hand. I wish I had something that behaves like what I have. — Praxeolitic, Dec 31 '14 at 16:09
If you used realloc you'd copy the whole buffer and not just the fragment, so the algorithm would be different, but equivalent. As for fgets, you could simply have a wrapper around fgets to automatically resize the buffer if that's the behavior you wanted. — Edward, Dec 31 '14 at 16:15
How does the C community feel about code that uses a large fixed size buffer like that? Is doing so normal? It's very likely large enough but what if... the file contents turn out to the writings on a prolific author with a broken return key? — Praxeolitic, Dec 31 '14 at 20:33
I wouldn't claim to speak for "the C community" but fixed size buffers are fairly common. Every existing use of fgets uses one, so experience would suggest it's not much of an impediment. — Edward, Dec 31 '14 at 20:41

vnp · Accepted Answer · 2014-12-31 21:24:39Z

A FILE structure already provides certain buffering; as mentioned, most of the functionality is achieved by fgets. On the other hand, the code is potentially very useful if operated on a file descriptor instead (a socket for example).
Magic numbers shall be avoided. Define a next_line return value as an enum, or as a set of macros.
Usage of sizeof(char) is questionable. First, it is equal to 1 by definition. Second, taking a size of type is a bad practice: if you decided to change the type, you'd need to fix sizeof as well. Taking size of a variable (e.g. sizeof(*buff)) is much safer.
Do not cast what malloc, memchr, etc. return. In C the cast is redundant, and may mask certain errors.
Separation of get_line and next_line is questionable. I'd rather not expose next_line to the client at all, but have get_line call it as necessary.

I also don't like the get_line/next_line separation but I wanted it to be possible to repeatedly retrieve the current line. Otherwise if you hit a line at which another function should take over, it's awkward to pass both the handle and the first line. Python's readline behaves like that and I can't stand it. After thinking about it I changed next_line to also return pointers to the line it advances to so iterating over lines is done with only next_line but get_line is still available. — Praxeolitic, Jan 1 '15 at 2:48

Stack Exchange Network

current community

your communities

more stack exchange communities

Read file line-by-line with circular buffer

2 Answers 2

Simplify

Use `enum` for error return codes

Check for errors after `fread`

Eliminate `bytes_read` variable

Use library functions to simplify your code

Reconsider the interface

Your Answer

Not the answer you're looking for? Browse other questions tagged c file circular-list or ask your own question.

Hot Network Questions

Read file line-by-line with circular buffer

2 Answers 2

Simplify

Use enum for error return codes

Check for errors after fread

Eliminate bytes_read variable

Use library functions to simplify your code

Reconsider the interface

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c file circular-list or ask your own question.

Related

Hot Network Questions

Use `enum` for error return codes

Check for errors after `fread`

Eliminate `bytes_read` variable