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:
- Is it of the proper complexity?
- Are there any subtle bugs my testing didn't reveal?
- 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));
}
