2
\$\begingroup\$

Continuing my foray into classic structures and algorithms, I've tried to implement merge sort for doubly-linked lists. From my (limited) testing it seems the thing I've concocted works, but several things worry me a bit:

  1. Is it of the proper complexity?
  2. Are there any subtle bugs my testing didn't reveal?
  3. What could be improved performance-wise?

The entire code can be found in this repo: link, in a frozen branch mergesort-review-29-12-17. Test driver is in test/list (uses check library).

Now for the code. Here's an excerpt from the header file:

struct list 
{
    struct list_elem *first, *last;
};

struct list_elem
{
    void *data;
    struct list_elem *prev, *next;
};

extern struct list *
list_create(void);i

extern void
list_destroy(struct list *);

extern void 
list_destroy_ex(struct list *, void (*destroyer)(void *data));

extern int
list_push(struct list *, void *data);

extern int
list_push_back(struct list *, void *data);

/* Append a list destructively. The resulting list will reuse elements of the
 * 'append' argument, avoiding copying it.
 * Optionally free the appended list.
 */
extern void
list_append_d(struct list *to, struct list *append, int do_free);

extern void *
list_pop(struct list *);

/* If 'desc' is false, sort the list in ascending order, otherwise sort it in
 * descending order.
 * 'cmp' should return a negative value if 'left < right', 0 if they are equal,
 * and a positive value if 'left > right'. 
 * Return a new sorted list, or NULL on an OOM condition. */
struct list *
list_sort(struct list *, int (*cmp)(void *left, void *right), int desc);

/* Same, but 'cmp' takes an extra argument. */
struct list *
list_sort_ex(struct list *, int (*cmp)(void *left, void *right, void *external_arg),
        int desc, void *external_arg);

There's also a couple helper functions that didn't make it into the header. Here are the declarations:

static void 
destroy_nested(void *list);

static struct list *
list_merge(struct list *group_a, struct list *group_b, 
        int (*cmp)(void *left, void *right), int desc);

static struct list *
list_merge_ex(struct list *group_a, struct list *group_b,
        int (*cmp)(void *left, void *right, void *arg), int desc, void *arg);

destroy_nested is a simple wrapper over list_destroy, with type signature suitable for passing it to list_destroy_ex. Such combination's job is to free a list which elements are also lists. The only interesting functions there are list_merge[_ex] and list_sort[_ex], the rest pretty much do what one would expect them to do, the code is trivial and I won't post it here unless asked.

list_merge[_ex] perform the 'merge' step of the algorithm. After they are done, group_a and group_b lists will be exausted, that is, contain nothing. Their elements will be transferred to the resulting merged list. They are implemented through a macro, because they only differ in a single line where comparison takes place. Here's the implementation:

#define MERGE_BODY(group_a, group_b, cmp, desc, cur_a, cur_b, cmp_line) \
{ \
    struct list *res = list_create(); \
    if (res == NULL) return NULL; \
 \
    struct list_elem *cur_a = group_a->first; \
    struct list_elem *cur_b = group_b->first; \
    while (cur_a != NULL && cur_b != NULL) { \
        int cmp_res = cmp_line; \
        struct list_elem *next_a = cur_a->next; \
        struct list_elem *next_b = cur_b->next; \
        /* Figure out which data to take. */ \
        if (desc && cmp_res < 0 || !desc && cmp_res > 0) { \
            list_extract_back(res, group_b, cur_b); \
            cur_b = next_b; \
        } else { \
            list_extract_back(res, group_a, cur_a); \
            cur_a = next_a; \
        } \
    } \
    if (cur_a != NULL) list_append_d(res, group_a, 0); \
    if (cur_b != NULL) list_append_d(res, group_b, 0); \
    return res; \
} \

static struct list *
list_merge(struct list *group_a, struct list *group_b,
        int (*cmp)(void *left, void *right), int desc)
{
    MERGE_BODY(group_a, group_b, cmp, desc, cur_a, cur_b, 
            cmp(cur_a->data, cur_b->data));
}

/* Same, but the comparison function takes an extra argument. */
static struct list *
list_merge_ex(struct list *group_a, struct list *group_b,
        int (*cmp)(void *left, void *right, void *arg), int desc, void *arg)
{
    MERGE_BODY(group_a, group_b, cmp, desc, cur_a, cur_b,
            cmp(cur_a->data, cur_b->data, arg));
}

And finally, this is the code that implements the list_sort[_ex] functions. Again, the macro is there because the two only differ in the way they call list_merge and list_merge_ex. I've chosen to use goto for the failure and clean-up because pasting the same code in nine-ish places felt just plain wrong.

#define SORT_BODY(list, cmp, desc, group_a, group_b, merge) \
{ \
    struct list *res = NULL; \
    struct list *groups = NULL; \
    struct list *next_groups = NULL; \
 \
    groups = list_create(); \
    if (groups == NULL) goto fail; \
 \
    /* Split the original list into lists of length 1 and put them in 'groups'. */ \
    struct list_elem *cur = list->first; \
    while (cur != NULL) { \
        struct list *new_list = list_create(); \
        if (new_list == NULL) goto fail; \
        if (!list_push(new_list, cur->data)) goto fail; \
        if (!list_push_back(groups, new_list)) goto fail; \
        cur = cur->next; \
    } \
 \
    size_t group_size = 1; \
    size_t len = list_length(list); \
    while (group_size < len) { \
        /* Merge adjacent groups and prepare a new layer from the \
         * merged groups. */ \
        next_groups = list_create(); \
        if (next_groups == NULL) goto fail; \
        struct list_elem *first = groups->first; \
        struct list_elem *second = first->next; \
        while (first != NULL && second != NULL) { \
            struct list *group_a = first->data; \
            struct list *group_b = second->data; \
            struct list *new_group = merge; \
            if (new_group == NULL) goto fail; \
            if (!list_push_back(next_groups, new_group)) { \
                list_destroy(new_group); \
                goto fail; \
            } \
            first = second->next; \
            second = first == NULL ? NULL : first->next; \
        } \
        /* If the number of groups is not even, 'first' will contain \
         * the trailing group. */ \
        if (first != NULL) { \
            struct list *extract = list_create(); \
            if (extract == NULL) goto fail; \
            list_append_d(extract, first->data, 0); \
            if (!list_push_back(next_groups, extract)) { \
                list_destroy(extract); \
                goto fail; \
            } \
        } \
        list_destroy_ex(groups, &destroy_nested); \
        groups = next_groups; \
        next_groups = NULL; \
        group_size <<= 1; \
    } /* while group_size < len */ \
 \
    /* Now 'groups' contains a single sorted list, which is what we want. */ \
    res = list_pop(groups); \
    list_destroy(groups); \
    return res; \
 \
    /* This goto greatly simplifies failure and clean-up code. */ \
fail: \
    if (res != NULL)  \
        list_destroy(list); \
    if (groups != NULL)  \
        list_destroy_ex(groups, &destroy_nested); \
    if (next_groups != NULL) \
        list_destroy_ex(groups, &destroy_nested); \
    return NULL; \
} \

struct list *
list_sort(struct list *list, int (*cmp)(void *left, void *right), int desc)
{
    SORT_BODY(list, cmp, desc, group_a, group_b,  
            list_merge(group_a, group_b, cmp, desc));
}

struct list *
list_sort_ex(struct list *list, int (*cmp)(void *left, void *right, void *arg),
        int desc, void *arg)
{
    SORT_BODY(list, cmp, desc, group_a, group_b,
            list_merge_ex(group_a, group_b, cmp, desc, arg));
}
\$\endgroup\$
4
\$\begingroup\$

I've chosen to use goto for the failure and clean-up because pasting the same code in nine-ish places felt just plain wrong.

How about writing a function and using it in nine-ish different places?

Is it of the proper complexity?

Using a rather complex macro rather than a function or multiple functions greatly increases the complexity of the code as does goto statements hidden in macros.

The largest problem I see with this code is that it is almost impossible to maintain. Programmers, software engineers and developers generally work in teams. You may be on vacation, you may have won the lottery, or someone may have left you five million dollars when this code needs to be updated. Trying to insert a line in a macro can be a nightmare. In the days before the ANSI C standard (before C89) large blocks of code like this might have been Okay for performance reasons, these days is best to write small functions that do only one thing and build the program up from the small functions.

It's difficult to get a large macro to compile since any syntax errors are all reported on the same line. It's difficult to debug because most debuggers will only show the macro, and any errors that get thrown are all on one line.

If you want to clean things up after an error in C, you might want to look into setjmp() and longjmp() and include setjmp.h in the file.

\$\endgroup\$

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.