1
\$\begingroup\$

So, I'm diving into C and decided to create cons cells. I'd like some thoughts on style and correctness. There are no warnings with -Wall -g and Valgrind doesn't complain about anything.

I'm really not sure what to do when the list is NULL in the first function.

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

struct Cell {
    int val;
    struct Cell *next;
};

struct Cell *cons(int val, struct Cell *rest)
{
    struct Cell *cell = malloc(sizeof(struct Cell));
    cell->val = val;
    cell->next = rest;
    return cell;
}

int first(struct Cell *list)
{
    if (list) {
        return list->val;
    }
    return 0;
}

struct Cell *rest(struct Cell *list)
{
    return list->next;
}

int length(struct Cell *list)
{
    if (list) {
        return 1 + length(rest(list));
    }
    return 0;
}

void destroy(struct Cell *list)
{
    if (list) {
        destroy(rest(list));
        free(list);
    }
}

void print(struct Cell *list)
{
    if (list) {
        printf("%d\n", first(list));
        print(rest(list));
    }
}

The main function.

int main(int argc, char *argv[])
{
    struct Cell *list = NULL;
    int i;
    for (i = 1; i < argc; ++i) {
        list = cons(atoi(argv[i]), list);
    }
    puts("Entire list:");
    print(list);
    puts("First:");
    printf("%d\n", first(list));
    puts("Rest:");
    print(rest(list));
    puts("Length:");
    printf("%d\n", length(list));
    destroy(list);
    return 0;
}

Running it.

./cons 1 2 3 4
\$\endgroup\$
1
  • \$\begingroup\$ I like it! Apart from the in-band error return in first I think it is very good C. \$\endgroup\$ – William Morris Aug 30 '13 at 1:56
3
\$\begingroup\$

A few comments:

typedef your structs:

typedef struct Cell
{
    int val;
    struct Cell *next;
} Cell;

typedef means you no longer have to write struct all over the place:

Cell *cons(int val, Cell *rest)
{
    Cell *cell = malloc(sizeof(Cell));
    cell->val = val;
    cell->next = rest;
    return cell;
}

That not only saves keystrokes, it also can make the code cleaner since it provides a bit more abstraction.


I would check if the pointer is NULL rather than if it isn't (related question):

int length(struct Cell *list)
{
    if (!list) return NULL; // or something else like -1
    return 1 + length(rest(list));
}

Set the pointer to NULL after freeing it.

void destroy(struct Cell *list)
{
    if (list)
    {
        destroy(rest(list));
        free(list);
        list = NULL;
    }
}

Re-using a freed pointer can be a subtle error. Your code keeps right on working, and then crashes for no clear reason because some seemingly unrelated code wrote in the memory that the re-used pointer happens to be pointing at. This is to prevent that.

\$\endgroup\$
7
  • \$\begingroup\$ Thanks for your feedback! I changed the code to use a typedef for the struct, but now I have a bunch of "incompatible pointer type" warnings. I'll have to invesitage that more. As for the length function, I understand the point of returning early, but aren't I already doing that? Also, I think a NULL (empty) list should return 0, and never NULL a negative integer. You're suggesting I NULL out the pointer because it's an argument and could be used elsewhere? \$\endgroup\$ – Jeremy Heiler Aug 29 '13 at 20:29
  • \$\begingroup\$ You are checking if a function is true and then exiting if it is false rather than checking if false and returning right away. NULL is defined as (void*) 0, not a negative number. And yes, you should always set the pointer to NULL when you are done using it. \$\endgroup\$ – syb0rg Aug 29 '13 at 20:34
  • \$\begingroup\$ What's with returning NULL as an int? In the best case, it's the same as returning 0. In the worst case, it blows up in your face. \$\endgroup\$ – idoby Aug 29 '13 at 20:40
  • \$\begingroup\$ @syb0rg I meant to say "or a negative number" per your inline comment. \$\endgroup\$ – Jeremy Heiler Aug 29 '13 at 20:57
  • \$\begingroup\$ I see no point in setting list to NULL here. If you were going to do it, you'd want to do so within the if (list) {...} block, not outside it. But what you really want is to set the caller's list pointer (if it is a pointer) to null and you can do that as it stands. \$\endgroup\$ – William Morris Aug 30 '13 at 1:47
2
\$\begingroup\$

In my opinion, this is pretty good C! Just a few nitpicks:

  • Function interface design: There's not much you can do if list is NULL in first, since C offers nothing like exceptions and your list contains an int, so you can't return an out-of-range value to indicate error, as is the convention sometimes. If signalling an error is crucial, I'd change the function interface to take a pointer to an int, where it would store the value, and return an error/success code. Generally it's easier (and acceptable) to rely on client code not to pass NULL, but this should be well documented in real-life code.
  • Recursion: I'd advise against the use of recursion when an iterative solution would work just as well. This is because stack space is ultimately limited and nothing guarantees the compiler would eliminate tail recursion even if you wrote your recursion that way.
  • Freeing pointed-to memory: Set the pointers that point to just-freed memory to NULL to avoid dereferencing them down the road. (This relies on a nullity check when appropriate, of course)
  • Typedefs: I'd actually advise against typedefing structs if you're accessing their members directly. Typedefs should represent either types that might change (like platform-specific ones) or opaque types you need to use accessor functions to read or mutate. Either way, if while coding you make no assumptions about the internal structure of the type, typedef it. Otherwise, you'd be better off letting client code (or other maintainer or even you a few weeks from now) know it's a struct. The same goes for pointer types.
\$\endgroup\$
4
  • \$\begingroup\$ Thanks! 1) In lisp fashion, calling first on an null or empty list just returns null. Would it be out of place to have it return int *, and have Cell use a int * for val? 2) I agree about not using recursion here. 3) Is this more-or-less a defensive action? It should be fine if there is no intention to ever use the pointer again, correct? I'm just diving deeper because Valgrind doesn't complain about it. 4) In this case, I think the Cell type is inconsequential since all operations on it can be done using cons, first, and rest. Even then you'd still suggest not using typedef? \$\endgroup\$ – Jeremy Heiler Aug 29 '13 at 21:24
  • \$\begingroup\$ Yes, your code is very lispy indeed. 1) I wouldn't store a int* in the list node. That serves no real purpose. Also, returning an int* from first would force the caller to dereference the return value to get to the actual content of the list node. This isn't really natural for a C programmer IMO. If you want to return "multiple values", pass pointers to the function. This way you can return an error code as well as "return" the content of the list node. \$\endgroup\$ – idoby Aug 29 '13 at 22:02
  • \$\begingroup\$ 3) Valgrind would only generally complain about accessing memory you shouldn't (like a freed pointer) or not deallocating all dynamically allocated memory. Since you've done neither, Valgrind is happy. But you run the risk of not being able to tell the pointers are invalid in the future, because they point to seemingly valid, but undesireable addresses. \$\endgroup\$ – idoby Aug 29 '13 at 22:14
  • \$\begingroup\$ Thanks. I suppose my next exercise should be more C oriented. \$\endgroup\$ – Jeremy Heiler Aug 30 '13 at 5: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.