This is an implementation of the merge sort algorithm for SLIST in
queue(3).
Merge sort is a stable algorithm that provides us a worst case run time
of O(n lg n) and uses at most O(n) of stack (where 'n' is the current
number of elements in the list).
The patch attached to this mail provides the following macros:
SLIST_MERGESORT_PROTOTYPE(name, type, field)
SLIST_MERGESORT_PROTOTYPE_STATIC(name, type, field)
These macros generates the merge sort functions prototypes, where:
- 'name' is the prefix prepended to the function name;
- 'type' is the struct type that we are using;
- 'field' is the data structure pointer to the next entry;
SLIST_MERGESORT_GENERATE(name, type, field, cmp)
SLIST_MERGESORT_GENERATE_STATIC(name, type, field, cmp)
These macros generates the merge sort functions, where:
- 'name' prefix prepended to the function name;
- 'type' struct type that we are using;
- 'field' data structure pointer to the next entry;
- 'cmp' the compare function that determines where to move the items
('< 0' means move left, '> 0' means move right and '0' items are equal);
NOTE: the compare function MUST return an signed variable, it doesn't
matter what type it is, it is recommended to return an integer (int).
The parameters must be 'struct type *' or 'void *'.
SLIST_MERGESORT(name, head)
This macro calls the mergesort function with name prefix 'name' and
returns a pointer to the list head (struct type *), if the list is empty
NULL is returned instead.
- 'name' prefix prepended to the functions name;
- 'head' is a pointer to the list head created by SLIST_HEAD();
It is possible to generate multiple sort functions using the 'name'
parameter illustrated by 'NHEAD' in the sample in this mail.
Usage example:
>>>>>> SAMPLE START
#include <sys/queue.h>
#include <err.h>
#include <stdio.h>
#include <stdlib.h>
struct number {
int n_number;
SLIST_ENTRY(number) n_entry;
};
static SLIST_HEAD(NHEAD, number) nhead = SLIST_HEAD_INITIALIZER(&nhead);
static int
number_cmp(struct number *n, struct number *nn)
{
if (n->n_number > nn->n_number)
return (1);
else if (n->n_number < nn->n_number)
return (-1);
return (0);
}
SLIST_MERGESORT_PROTOTYPE_STATIC(NHEAD, number, n_entry)
SLIST_MERGESORT_GENERATE_STATIC(NHEAD, number, n_entry, number_cmp)
int
main(int argc, char *argv[])
{
struct number *n;
int i;
for (i = 1; i < 500; i++) {
n = calloc(1, sizeof(*n));
if (n == NULL)
err(1, "calloc");
n->n_number = i;
SLIST_INSERT_HEAD(&nhead, n, n_entry);
}
printf("List:\n");
SLIST_FOREACH(n, &nhead, n_entry)
printf(" %d", n->n_number);
printf("\n");
SLIST_MERGESORT(NHEAD, &nhead);
printf("List sorted:\n");
SLIST_FOREACH(n, &nhead, n_entry)
printf(" %d", n->n_number);
printf("\n");
exit(EXIT_SUCCESS);
}
<<<<<< SAMPLE END
Index: queue.h
===================================================================
RCS file: /cvs/src/sys/sys/queue.h,v
retrieving revision 1.38
diff -u -p -r1.38 queue.h
--- queue.h 3 Jul 2013 15:05:21 -0000 1.38
+++ queue.h 26 Nov 2013 01:16:44 -0000
@@ -161,6 +161,57 @@ struct {
\
} \
} while (0)
+
+#define SLIST_MERGESORT_PROTOTYPE(name, type, field) \
+ SLIST_MERGESORT_PROTOTYPE_INTERNAL(name, type, field,)
+#define SLIST_MERGESORT_PROTOTYPE_STATIC(name, type, field) \
+ SLIST_MERGESORT_PROTOTYPE_INTERNAL(name, type, field,
__attribute__((__unused__)) static)
+#define SLIST_MERGESORT_PROTOTYPE_INTERNAL(name, type, field, attr) \
+ attr struct type *name##_MERGE(struct type *, struct type *); \
+ attr struct type *name##_MERGESORT(struct type *);
+
+#define SLIST_MERGESORT_GENERATE(name, type, field, cmp) \
+ SLIST_MERGESORT_GENERATE_INTERNAL(name, type, field, cmp,)
+#define SLIST_MERGESORT_GENERATE_STATIC(name, type, field, cmp)
\
+ SLIST_MERGESORT_GENERATE_INTERNAL(name, type, field, cmp,
__attribute__((__unused__)) static)
+#define SLIST_MERGESORT_GENERATE_INTERNAL(name, type, field, cmp, attr)
\
+ attr struct type * \
+ name##_MERGE(struct type *s, struct type *e) { \
+ struct type head; \
+ struct type *a = &head; \
+ while ((s != NULL) && (e != NULL)) { \
+ if ((cmp)(s, e) < 0) { \
+ a->field.sle_next = s; \
+ a = s; \
+ s = s->field.sle_next; \
+ } else { \
+ a->field.sle_next = e; \
+ a = e; \
+ e = e->field.sle_next; \
+ } \
+ } \
+ a->field.sle_next = (s != NULL) ? (s) : (e); \
+ return (head.field.sle_next); \
+ } \
+ attr struct type * \
+ name##_MERGESORT(struct type *a) { \
+ struct type *s, *e; \
+ if ((a == NULL) || (a->field.sle_next == NULL)) \
+ return (a); \
+ s = a; \
+ e = a->field.sle_next; \
+ while ((e != NULL) && (e->field.sle_next != NULL)) { \
+ a = a->field.sle_next; \
+ e = e->field.sle_next->field.sle_next; \
+ } \
+ e = a->field.sle_next; \
+ a->field.sle_next = NULL; \
+ return (name##_MERGE(name##_MERGESORT(s), \
+ name##_MERGESORT(e))); \
+ }
+#define SLIST_MERGESORT(name, head) \
+ ((head)->slh_first = name##_MERGESORT((head)->slh_first))
+
/*
* List definitions.
*/
