15
\$\begingroup\$

From K&R exercise 1-21,

Write a program entab that replaces strings of blanks by the minimum number of tabs and blanks to achieve the same spacing. Use the same tab stops as for detab. When either a tab or a single blank would suffice to reach a tab stop, which should be given preference?

My solution:

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

#define MAXLEN  1000    // max line length
#define TABSTOP 8       // tabstop width

int get_line(char line[], int maxlen);
char * entab(char line[], int len);

int main(void)
{
    char line[MAXLEN];  // input line container
    char *entabbed;     // entabbed version of input line
    int len = 0;        // input line length
    int e_len = 0;      // entabbed line length

    while((len = get_line(line, MAXLEN)) > 0) {
        // produce entabbed version
        entabbed = entab(line, len);
        while (entabbed[e_len] != '\0') {
            e_len++;
        }

        // print entabbed version
        printf("%s", entabbed);
        if (entabbed[e_len-1] != '\n') {
            printf("\n");
        }

        free(entabbed);
    }

    return 0;
}

int get_line(char line[], int maxlen)
{
    int i = 0;  // current index
    int c;      // current character

    while (i < maxlen-1 && (c = getchar()) != EOF) {
        line[i++] = c;
        if (c == '\n') {
            break;
        }
    }
    line[i] = '\0';

    // clear input buffer of overflow
    if (i > 0 && line[i-1] != '\n') {
        while ((c = getchar()) != '\n' && c != EOF);
    }

    return i;
}

char * entab(char line[], int len)
{
    int i;          // index into original line
    int e;          // index into entabbed version
    int spaces;     // buffered whitespace counter
    char c;         // current char
    char *entabbed; // entabbed version

    e        = 0;
    spaces   = 0;
    entabbed = (char *) malloc(len * sizeof(char) + 1);

    for (i = 0; i < len; i++) {
        c = line[i];

        if (c == ' ') {
            if ((i+1) % TABSTOP == 0) {
                entabbed[e++] = '\t';
                spaces = 0;
            } else {
                spaces++;
            }
        } else {
            while (spaces > 0) {
                entabbed[e++] = ' ';
                spaces--;
            }

            entabbed[e++] = c;
        }
    }

    return entabbed;
}

I know there are probably more sophisticated ways of handling the input, but I've restricted myself to material covered by the first chapter of K&R.

\$\endgroup\$
  • 1
    \$\begingroup\$ You could use strlen() instead of the (faulty because of initialization) loop to determine the length of the entabbed string. OTOH, that may not have been covered at this point, though handling malloc() before strlen() would be a bit surprising. \$\endgroup\$ – Jonathan Leffler Dec 25 '15 at 15:25
  • \$\begingroup\$ @JonathanLeffler yes, I realized after the fact that I hadn't really restricted myself to chapter 1 material, since pointers and the heap aren't covered that early in the book. \$\endgroup\$ – ivan Dec 25 '15 at 16:47
  • 1
    \$\begingroup\$ the expression: sizeof(char) is defined in the standard as 1. Multiplying any value by 1 does not change its value. Therefore the expression in the parameter to malloc() has no effect. Using that expression just clutters the code, making it more difficult to understand, debug, maintain. Suggest removing that expression. \$\endgroup\$ – user3629249 Dec 26 '15 at 0:16
  • 2
    \$\begingroup\$ when calling malloc() or calloc() or realloc() the returned value is of type: void * so can be assigned to any other pointer. Casting the returned value just clutters the code, making understaning, debug and maintenance more difficult. Suggest removing the cast from calls to malloc. When calling malloc(), calloc() or realloc() always check (!=NULL) the returned value to assure the operation was successful. \$\endgroup\$ – user3629249 Dec 26 '15 at 0:19
  • \$\begingroup\$ @user3629249 Thanks for letting me know! This is a bad practice I picked up from a terrible book (not K&R). Good to know I can stop doing this. \$\endgroup\$ – ivan Dec 26 '15 at 15:44
15
\$\begingroup\$

I see some things that could help you improve your program.

Learn a recent version of C

I still have my K&R first edition from 1978, however it would be a very poor choice to use for learning C today. The version of C it teaches has been obsolete for decades. I don't know which edition you're using (looks like a more recent one by the style of code) but it would be best to learn C99 or C11. You may already be doing this, but it would be good to check.

Declare variables closer to where they're used

It may be a result of the book you're reading to learn C (per the previous point) but in modern C, we don't declare all of the variables at the top of the function that will be used in the entire function. Instead, declare the variables closer to where they're first used.

Reorder functions to avoid prototypes

You can eliminate the function prototypes by rearranging the function definitions so that each function is defined before its first appearance. In this case, that simply means moving main last, below the other functions.

Use const where practical

The current version of entab doesn't alter the passed line. This can be clearly indicated by making that parameter const:

char * entab(const char line[], int len)

Avoid frequent memory allocations

Memory allocation operations can be expensive in terms of time and are also yet another thing that can go wrong in terms of running out of memory or forgetting to free the block. With that in mind, there are two obvious choices. One would be to pass in an output buffer and length to entab() and the other is to do the entabbing in place. I'd advocate the latter approach since we know that an entabbed line will never be larger than the input string.

Fix bug #1

The first time through the loop, e_len is 0 and gets incremented to point to the terminating '\0', but the value is never reset to zero for the second and subsequent lines. That's a bug. Instead, I'd recommend changing from this

while (entabbed[e_len] != '\0') {
    e_len++;
}

To this:

for (e_len = 0; entabbed[e_len] != '\0'; ++e_len) 
{}

Fix bug #2

Within the entab function, the terminating '\0' is never copied to the resulting copy of the line. The result is that the line may or may not be properly terminated. This is easily fixed by changing the for loop there from this:

for (i = 0; i < len; i++) {

to this:

for (i = 0; i <= len; i++) {

Eliminate return 0 at the end of main

Since C99, the compiler automatically generates the code corresponding to return 0 at the end of main so there is no need to explicitly write it.

\$\endgroup\$
  • 3
    \$\begingroup\$ Mm, good point about C version. I'm using the 2nd edition of K&R, which appears to be C89 (ANSI). Do you have any book recommendations for learning a newer version? \$\endgroup\$ – ivan Dec 24 '15 at 20:27
  • \$\begingroup\$ Reordering the functions to avoid using prototypes goes against some of the advice I've read/heard elsewhere. Is this also a convention that's changed over time, or is it more of a personal preference? \$\endgroup\$ – ivan Dec 24 '15 at 20:29
  • \$\begingroup\$ Ah, bug #1 totally escaped me. Thank you. \$\endgroup\$ – ivan Dec 24 '15 at 20:32
  • \$\begingroup\$ And bug #2 as well. I thought I had it, but was of course off by one. \$\endgroup\$ – ivan Dec 24 '15 at 20:35
  • 3
    \$\begingroup\$ Off-by-one errors are among the very most common. I haven't a good book recommendation, but anything published 2000 or later should include the C99 standard. For avoiding prototypes, for single-file projects, it's easer/better/faster to do so. For multifile projects, prototypes typically go into a header file (.h file) and the implementation of those functions go into a separate .c file. \$\endgroup\$ – Edward Dec 24 '15 at 20:38
8
\$\begingroup\$

I have to say that this is a really well-written program. Nice work! I don't think you hit most of the usual newbie pitfalls like forgetting to free memory you allocated.

Given the constraints of only using stuff covered in the first chapter of K&R there's not a lot to add, but I'll mention a few small things.

Don't forget to NULL-terminate your strings

In entab() you aren't NULL-terminating the string. It probably happens to work out because the memory you allocate may already have zeros in it. But you should explicitly add a \0 at the end:

...
    entabbed[i] = '\0';
    return entabbed;
}

The calling function relies on the entabbed string to be NULL-terminated when you calculate its length, so it's important to remember this!

Some bugs

There are 2 subtle things that I see that could cause problems in the future. One is a bug and the other is working correctly here, but could be problematic in other cases.

In entab() you allocate memory, but you don't handle the case where you're out of memory and the allocation fails. You should plan for that both in the entab() function and in the caller by doing this:

char * entab(char line[], int len)
{
    int i;          // index into original line
    int e;          // index into entabbed version
    int spaces;     // buffered whitespace counter
    char c;         // current char
    char *entabbed; // entabbed version

    e        = 0;
    spaces   = 0;
    entabbed = (char *) malloc(len * sizeof(char) + 1);
    if (entabbed == NULL)
    {
        return NULL;
    }
...

And the caller needs to make sure what it got back is not NULL;

while((len = get_line(line, MAXLEN)) > 0) {
    // produce entabbed version
    entabbed = entab(line, len);
    if (entabbed == NULL) {
        printf("Unable to allocate entabbed string!\n");
        return 1; // <- or some other error
    }

    while (entabbed[e_len] != '\0') {
        e_len++;
    }

The other issue is not a bug as you've written it, but I wanted to point it out so it doesn't bite you in the future. When you allocate the entabbed string, you do this:

entabbed = (char *) malloc(len * sizeof(char) + 1);

Here len is the number of characters and the + 1 is to hold the NULL terminator. But the NULL terminator is the same size as a character, so it really should be:

entabbed = (char *) malloc((len + 1) * sizeof(char));

This works fine for now because a char is 1 byte. But when you start working with wide characters or Unicode characters, that may not hold true. You want len + 1 elements that are the size of your data type, not len elements the size of your data type plus 1 byte.

For the future

Once you've learned more of the standard library, you can replace some of your code with standard library calls like getline() or fgets() and strlen() to calculate the length of a string. I don't recall when those are covered in K&R, but you'll probably learn about them soon. Good luck!

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for the helpful comments. As for the null-terminator, I'm relying on it being copied from the original string. Good point about where I put the +1 in my call to malloc, I totally overlooked that. I knew I should be handling the case where malloc fails, but I got lazy :). \$\endgroup\$ – ivan Dec 24 '15 at 20:23
  • \$\begingroup\$ Hm, I guess I fibbed also when I said I'm only using stuff from the first chapter, since malloc/free aren't covered yet. \$\endgroup\$ – ivan Dec 24 '15 at 20:26
  • \$\begingroup\$ regarding this line: entabbed = (char *) malloc((len + 1) * sizeof(char)); multiplying by 1 has absolutely no effect on the parameter passed to malloc. And, in C, do not cast the returned value from malloc. Suggest: if( NULL == (entabbed = malloc( len + 1 )) ) { perror( "malloc failed"); exit( EXIT_FAILURE ); } \$\endgroup\$ – user3629249 Dec 26 '15 at 0:36

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.