2
\$\begingroup\$

I've attempted to make something similar to C++ and D templated lists in plain C. In this gist there's the full code of the header file and test driver I'm using. I'll post some excerpts from the header and all of the test driver.

My main questions are:

  1. Am I overusing the preprocessor? Is it OK to put all of the code generation into a macro (given the task at hand)?

  2. Does the code conform to the good practices? I haven't programmed in C for ages. I'm particularly interested in procedure naming - it feels somewhat unfortunate to me.

Here's the test driver (in full):

#include <assert.h>
#include <stdio.h>

#include "dlist.h"

/* We only use int lists in the following tests. Others are here just to 
 * demonstrate that different types of lists can coexist for as long as their
 * aliases are different. */
REQUIRE_DLIST(int, int);
REQUIRE_DLIST(int, foobar);
REQUIRE_DLIST(double, double);
IMPLEMENT_DLIST(int, int);
IMPLEMENT_DLIST(int, foobar); 
IMPLEMENT_DLIST(double, double);
//IMPLEMENT_DLIST(int, int); /* This will cause an error if uncommented. */

int
main(int argc, char** argv)
{
    struct dlist_int *list = create_dlist_int();
    if (list == NULL) {
        puts("Failed to create a list.");
        exit(EXIT_FAILURE);
    } else {
        puts("Successfully created a list.");
    }

    /* Test that we can push to the list. */
    push_dlist_int(list, 1);
    push_dlist_int(list, 2);
    push_dlist_int(list, 3);
    struct dlist_elem_int *cur = list->first;
    assert(cur->value == 3);
    cur = cur->next;
    assert(cur->value == 2);
    cur = cur->next;
    assert(cur->value == 1);
    puts("Successfully prepended three values to the list.");

    /* Test that we can push to the end of the list. */
    push_back_dlist_int(list, 10);
    push_back_dlist_int(list, 20);
    push_back_dlist_int(list, 30);
    cur = list->last;
    assert(cur->value == 30);
    cur = cur->prev;
    assert(cur->value == 20);
    cur = cur->prev;
    assert(cur->value == 10);
    puts("Successfully appended three values to the list.");

    /* Test that we can pop from both ends of the dlist. */
    assert(pop_dlist_int(list) == 3);
    assert(pop_back_dlist_int(list) == 30);
    assert(dlist_int_length(list) == 4);

    destroy_dlist_int(list, NULL, NULL);
    puts("Done.");
}

This is the REQUIRE_DLIST macro:

#define REQUIRE_DLIST(type, alias) \
    /* Base structs. */ \
    struct dlist_##alias { \
        struct dlist_elem_##alias *first, *last; \
    }; \
    struct dlist_elem_##alias { \
        struct dlist_elem_##alias *prev, *next; \
        type value; \
    }; \
    /* Base operations. */ \
    extern struct dlist_##alias *create_dlist_##alias(void); \
    extern void destroy_dlist_##alias( \
                struct dlist_##alias *list, \
                void (*destroyer)(type, void*), \
                void *arg); \
    extern void simple_destroy_dlist_##alias( \
            struct dlist_##alias *list, \
            void (*destroyer)(type)); \
    extern size_t preallocate_dlist_##alias(struct dlist_##alias *list, \
            size_t len); \
    /* Copying. */ \
    extern struct dlist_##alias *copy_dlist_##alias(struct dlist_##alias *list, \
            type (*copier)(type, void *), void *arg); \
    extern struct dlist_##alias *simple_copy_dlist_##alias(struct dlist_##al ias *list, \
            type (*copier)(type)); \
    /* Insertion. */ \
    extern int push_dlist_##alias(struct dlist_##alias *list, type value); \
    extern int push_back_dlist_##alias(struct dlist_##alias *list, type valu e); \
    extern size_t append_dlist_##alias( \
            struct dlist_##alias *append_to,  \
            struct dlist_##alias *tail); \
    extern size_t prepend_dlist_##alias(struct dlist_##alias *prepend_to, \
            dlist_##alias *head); \
    extern struct dlist_##alias \
        *cat_dlists_##alias(struct dlist_##alias *left, \
                struct dlist_##alias *right); \
    /* Deletion and popping. */ \
    extern type pop_dlist_##alias(struct dlist_##alias *list); \
    extern type pop_back_dlist_##alias(struct dlist_##alias *list); \
    extern size_t pop_n_dlist_##alias(struct dlist_##alias *list, size_t n); \
    extern size_t pop_back_n_dlist_##alias(struct dlist_##alias *list, size_ t n); \
    extern void clear_dlist_##alias( \
            struct dlist_##alias *list, \
            void (*destroyer)(type, void*), \
            void*); \
    extern void simple_clear_dlist_##alias( \
            struct dlist_##alias *list, \
            void (*destroyer)(type)); \
    /* Information retrieval. */ \
    extern size_t dlist_##alias##_length(struct dlist_##alias *list); \
    extern type dlist_##alias##_first(struct dlist_##alias *list); \
    extern type dlist_##alias##_last(struct dlist_##alias *list); \
    extern int dlist_##alias##_empty(struct dlist_##alias *list); \

/* End of REQUIRE_DLIST */

And these are some parts of IMPLEMENT_DLIST macro, hopefully enough to illustrate the point and the method:

#define IMPLEMENT_DLIST(type, alias) \
    /* Base operations - creation. */ \
    struct dlist_##alias \
    *create_dlist_##alias(void) { \
        struct dlist_##alias *res = malloc(sizeof(struct dlist_##alias)) ; \
        if (res == NULL) return NULL; \
        res->first = NULL; \
        res->last = NULL; \
        return res; \
    } \
    struct dlist_elem_##alias \
    *create_dlist_elem_##alias(type value) { \
        struct dlist_elem_##alias *res = malloc(sizeof(struct dlist_elem _##alias)); \
        if (res == NULL) return NULL; \
        res->prev = res->next = NULL; \
        res->value = value; \
        return res; \
    } \
    struct dlist_elem_##alias \
    *create_uninit_dlist_elem_##alias(void) { \
        struct dlist_elem_##alias *res = malloc(sizeof(struct dlist_elem _##alias)); \
        if (res == NULL) return NULL; \
        res->prev = res->next = NULL; \
        return res; \
    } \
    /* Base operations - clean up. */ \
    void \
    destroy_dlist_##alias(struct dlist_##alias *list, void (*destroyer)(type , void*), \
            void *arg) { \
        struct dlist_elem_##alias *cur = list->first; \
        while (cur != NULL) { \
            struct dlist_elem_##alias *next = cur->next; \
            if (destroyer != NULL)  \
                destroyer(cur->value, arg); \
            free(cur); \
            cur = next; \
        } \
        free(list); \
    } \
    void \
    simple_destroy_dlist_##alias(struct dlist_##alias *list, void (*destroye r)(type)) { \
        struct dlist_elem_##alias *cur = list->first; \
        while (cur != NULL) { \
            struct dlist_elem_##alias *next = cur->next; \
            if (destroyer != NULL) \
                destroyer(cur->value); \
            free(cur); \
            cur = next; \
        } \
        free(list); \
    } \
    /* Insertion. */ \
    int \
    push_dlist_##alias(struct dlist_##alias *list, type value) \
    { \
            struct dlist_elem_##alias *new_first = create_dlist_elem_##alias(value); \
            if (new_first == NULL) return 0; \
            if (list->first == NULL) { \
                    list->first = list->last = new_first; \
            } else { \
                    struct dlist_elem_##alias *old_first = list->first; \
                    old_first->prev = new_first; \
                    list->first = new_first; \
                    new_first->next = old_first; \
            } \
            return 1; \
    } \
    int \
    push_back_dlist_##alias(struct dlist_##alias *list, type value) \
    { \
            struct dlist_elem_##alias *new_last = create_dlist_elem_##alias(value); \
            if (new_last == NULL) return 0; \
            if (list->last == NULL) { \
                    list->first = list->last = new_last; \
            } else { \
                    struct dlist_elem_##alias *old_last = list->last; \
                    old_last->next = new_last; \
                    list->last = new_last; \
                    new_last->prev = old_last; \
            } \
            return 1; \
    } \
    /* Deletion. */ \
    type \
    pop_dlist_##alias(struct dlist_##alias *list) \
    { \
            struct dlist_elem_##alias *first = list->first; \
            type res = first->value; \
            if (first == list->last) { \
                    free(first); \
                    list->first = list->last = NULL; \
            } else { \
                    struct dlist_elem_##alias *second = first->next; \
                    second->prev = NULL; \
                    list->first = second; \
                    free(first); \
            } \
            return res; \
    } \
    type \
    pop_back_dlist_##alias(struct dlist_##alias *list) \
    { \
            struct dlist_elem_##alias *last = list->last; \
            type res = last->value; \
            if (list->first == last) { \
                    list->first = list->last = NULL; \
                    free(last); \
            } else { \
                    struct dlist_elem_##alias *second = last->prev; \
                    second->next = NULL; \
                    list->last = second; \
                    free(last); \
            } \
            return res; \
    } \
\$\endgroup\$
4
  • \$\begingroup\$ Why not a normal implementation with few convenience macros? \$\endgroup\$ Nov 26, 2017 at 11:16
  • \$\begingroup\$ @AdrianoRepetti What exactly do you mean by 'normal implementation'? The only thing that comes to my mind is a void *, perhaps unioned with some basic types. \$\endgroup\$
    – Michail
    Nov 26, 2017 at 12:10
  • \$\begingroup\$ Just how long did it take you to write and debug this? \$\endgroup\$
    – pacmaninbw
    Nov 26, 2017 at 17:06
  • \$\begingroup\$ @pacmaninbw I haven't timed it, but more than 3 hours and less than 6. Anywhere in between is a fair guess. \$\endgroup\$
    – Michail
    Nov 26, 2017 at 17:16

3 Answers 3

1
\$\begingroup\$

I hate to do this to you after you did all this work, but what's the point of generating code for every data type the linked list can store?

I see very little in this case except maybe a small amount of added type safety and more type info for the debugger, but C isn't a very type-safe language in general (that's part of the beauty of it as it allows us to just treat data as bits and bytes and copy it freely and so forth without invoking complex functions). To work with it often requires casting pointers to and from void* which is implicitly allowed.

Meanwhile there are so many cons to generating code for every single type from inflated binaries with code duplication (unless the linker is really smart), lengthier builds, and macro hell. That's not to dismiss the value of doing this with the preprocessor for all cases (I'll cover that below), but in this case it's a very heavy cost for a very arguably minor benefit.

Code Generation In Other Languages

There are very good reasons, actually requirements, for generic C++ containers to generate code for every single data type, but they don't apply to C. C++ has a richer type system with types that can have constructors, copy constructors, destructors, and overloaded operators. It also has exception-handling. A similar case applies to the D programming language. C++ code cannot ever break down an arbitrary data type and treat it like just bits and bytes as we can in C without fighting against the type system of the language. We cannot even do that for C++ classes/structs that don't define a manual copy constructor safely, as any one of their members may have a nontrivial copy ctor causing the type that contains that member to require a nontrivial copy ctor to be generated.

In C++, functions like memset and memcpy are considered horrid, evil functions because they fundamentally violate the nature of the C++ type system by x-raying it and manipulating bits and bytes. In C, these are fundamental functions to lean on because in C, data types are just "data". The two languages might have a lot of features in common but these differences in the type system make a world of difference philosophically.

When you combine all these factors, then you often do need to generate code for every data type a C++ linked list can handle, because each data type will potentially have unique logic to copy it, destroy it, default-construct it, and use operators on it, basically generating a potentially whole new linked list with different inlined code due to the differences in logic from creating, copying, destroying, comparing, etc. one type to the next. On top of that the type may throw an exception at many of these points which the container generally needs to catch and roll back its change transaction to be exception-safe, basically generating many implicit points in the implementation where a local T instance could be implicitly destroyed as well as exit points in a function which could wildly vary from one generated implementation to another. Basically C++ containers need the type information just to function at a basic level so they have to rely exclusively on code generation to be generic and handle any data type possible from primitives to user-defined types.

However, none of this applies to C's type system, so the primary rationale for generating code for every single data type required is gone.

C Cases For Code Generation

Now there are still some cases where code generation could be useful in C for efficiency, e.g. For example, qsort could be faster if it had type information it could work with in advance to compare each list element it's sorting without an indirect function call for every comparison. If that was the case, it would then be able to match the speed of std::sort in C++. There I'd consider it a very worthy trade-off if the C preprocessor was used to generate different versions of sorting functions based on the type being sorted. A vector/matrix math library might be another case where code generation is useful given the amount of type information it needs about scalar types to avoid invoking indirect functions all over the place to do arithmetical operations on the scalars.

However, such reasons don't apply to a simple doubly-linked list which barely needs to know anything about the element type it's storing beyond its size and possibly how to destroy it (for which a function pointer call is often implied anyway since C lacks destructors unless you want to specify the name of the function to destroy the type in the macro to generate a list, and an indirect function call in the context of freeing a list node is generally a trivial expense). There's very little reason to generate code in C for every single data type a linked list can handle except, again, a small amount of type safety in exchange for a great deal of redundancy and awkward preprocessor code which makes debugging the list operations themselves a nightmare.

Suggestion

I really suggest just getting comfortable with working with void pointers more often for data structures you want to generalize and specifying function pointers to copy and destroy and compare types and so forth along with specifying the memory size of the type to the container on creating it (this type size will also serve as a stride when you implement generic contiguous data structures). When you're debugging C code, you should develop the common habit of casting void* to the type you are interested in to inspect its fields. Generic containers in C shouldn't require compile-time type information for the most part, and most hardly benefit from it. Embrace the C mindset. Types just form bits and bytes you can freely x-ray and copy around. This lack of diversity between types will make your code featherweight with smaller binaries, generating the minimum amount of machine code, and fast to build. They are not "objects" and don't model abstractions beyond just "data". Otherwise I think you're using the wrong language for the job.

So my overall suggestion is actually somewhat in contradiction of your immediate goals, but in line with your overall goal of having a generalized linked list. I recommend creating a generic doubly-linked list which does not rely on the C preprocessor to generate unique code for each data type the list can store, and for that you can come up with a really rich implementation, like one which pools memory and achieves a greater deal of spatial locality with the list nodes to minimize the cache misses and page faults involved with iterating through it.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I have nearly forgotten how fun and flexible C is. Thank you for reminding me. \$\endgroup\$
    – Michail
    Dec 2, 2017 at 18:21
  • \$\begingroup\$ I think it's awesome but a little bit dangerous. I like to use a combo of C and C++ with C++ for safety and cost-free abstractions and C for really low-level stuff that benefits from being able to very explicitly control and manipulate memory at the bits and bytes level. It can help a lot with practical efficiency sometimes (especially with respect to cache-friendly memory access) to be able to just manipulate and copy data types while treating them as bits and bytes without fighting the type system. I love C for that purpose the most, as I tend to find myself cornered sometimes in C++ [...] \$\endgroup\$
    – user90268
    Dec 2, 2017 at 19:57
  • \$\begingroup\$ [...] given its richer type system when it comes to really being able to get fine-control over where everything is stored in memory and how the data is arranged. Also there's something very elegant in spite of the dangers of well-tested featherweight C code that you can rely on time and time again. \$\endgroup\$
    – user90268
    Dec 2, 2017 at 19:58
2
\$\begingroup\$

The code could be a lot more object oriented by putting some or all of the functions into the proper struct using pointers to functions within the struct.

Are You Overusing the C Preprocessor
Not necessarily, you might be abusing anyone that needs to use the code and definitely anyone that needs to maintain the code. The problem with this kind of code is that it is very hard to debug, since line numbers don't mean anything within a macro.

An alternative might be to use smaller macros and then building the larger macros from the smaller macros. An example would be the base structs which could be defined in their own macro and then added into the REQUIRE_DLIST macro. It might be better to move each function into it's own macro as well.

The fact that it hides so much of the implementation might make it less than a good programming practice.

\$\endgroup\$
2
  • \$\begingroup\$ i quite like the idea of splitting my monolithic macros into smaller pieces. It would help readability, produce nicer compiler errors and provide something similar to selective imports, which is a nice bonus. BTW, what is the consensus on using ## operator? Should I write it like I did, without spaces between it and the operands, or should I separate it from the operands with spaces? \$\endgroup\$
    – Michail
    Nov 26, 2017 at 19:05
  • \$\begingroup\$ @Michail Leave the ## operator as it is. \$\endgroup\$
    – pacmaninbw
    Nov 26, 2017 at 20:44
2
\$\begingroup\$

Lots of macros for hiding functional details yet user code exposes struct members with:

//                               vvvvvvv
struct dlist_elem_int *cur = list->first;
cur = list->last;
//        ^^^^^^

I'd expect access to be wrapped in a macro or function call too.

Perhaps:

struct dlist_elem_int *cur = dlist_first_int(list);
cur = dlist_last_int(list);

Unclear why there are 3 operands in destroy_dlist_int()

destroy_dlist_int(list, NULL, NULL);
vs
destroy_dlist_int(list);

I'm particularly interested in procedure naming - it feels somewhat unfortunate to me.

Agreed, it loses clarity to put the keyword dlist in the middle of the function name. I recommend first.

// push_dlist_int(list, 2);
// push_back_dlist_int(list, 10);
// destroy_dlist_int(list, NULL, NULL);

dlist_push_int(list, 2);
dlist_push_back_int(list, 10);
dlist_destroy_int(list, NULL, NULL);

Debug tip: A "user.h" should stand on its own. If it requires <various....h> include files, it should include there. A way to check that is for test code to use #include "dlist.h" first.

#include "dlist.h"
#include <assert.h>
#include <stdio.h>

A "user.h" should tolerate re-including. A way to check that is for test code to also use #include "dlist.h" last.

#include "dlist.h"
#include <assert.h>
#include <stdio.h>
#include "dlist.h"

Since OP's code makes heavy uses of macros, insuring the needed headers files do not have sequence inclusion dependencies is a good thing.

\$\endgroup\$
2
  • \$\begingroup\$ Thank you for the review, it's very helpful. About three operands in destroy_dlist_X: the intent was to allow some deallocator function to be passed to destroy_dlist. Would it be better to make base destroy take a single list argument and warn the user in the documentation that destroying a list with it will lead to memory leaks (and provide current destroy under some other name)? \$\endgroup\$
    – Michail
    Dec 1, 2017 at 18:02
  • \$\begingroup\$ @Michail In the midst of competing solutions that lacks a specified need, choses the simpler one. If a true need for a more complex one occurs, offer another destroy...(). \$\endgroup\$ Dec 1, 2017 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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