diff options
Diffstat (limited to 'src/mergesort.c')
-rw-r--r-- | src/mergesort.c | 100 |
1 files changed, 100 insertions, 0 deletions
diff --git a/src/mergesort.c b/src/mergesort.c new file mode 100644 index 00000000..a8353203 --- /dev/null +++ b/src/mergesort.c @@ -0,0 +1,100 @@ +/* + * Copyright (c) 2017 Elise Lennion <elise.lennion@gmail.com> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + */ + +#include <stdint.h> +#include <expression.h> +#include <gmputil.h> +#include <list.h> + +static int expr_msort_cmp(const struct expr *e1, const struct expr *e2); + +static int concat_expr_msort_cmp(const struct expr *e1, const struct expr *e2) +{ + struct list_head *l = (&e2->expressions)->next; + const struct expr *i1, *i2; + int ret; + + list_for_each_entry(i1, &e1->expressions, list) { + i2 = list_entry(l, typeof(struct expr), list); + + ret = expr_msort_cmp(i1, i2); + if (ret) + return ret; + + l = l->next; + } + + return false; +} + +static int expr_msort_cmp(const struct expr *e1, const struct expr *e2) +{ + switch (e1->ops->type) { + case EXPR_SET_ELEM: + return expr_msort_cmp(e1->key, e2->key); + case EXPR_VALUE: + return mpz_cmp(e1->value, e2->value); + case EXPR_CONCAT: + return concat_expr_msort_cmp(e1, e2); + case EXPR_MAPPING: + return expr_msort_cmp(e1->left, e2->left); + default: + BUG("Unknown expression %s\n", e1->ops->name); + } +} + +static void list_splice_sorted(struct list_head *list, struct list_head *head) +{ + struct list_head *h = head->next; + struct list_head *l = list->next; + + while (l != list) { + if (h == head || + expr_msort_cmp(list_entry(l, typeof(struct expr), list), + list_entry(h, typeof(struct expr), list)) < 0) { + l = l->next; + list_add_tail(l->prev, h); + continue; + } + + h = h->next; + } +} + +static void list_cut_middle(struct list_head *list, struct list_head *head) +{ + struct list_head *s = head->next; + struct list_head *e = head->prev; + + while (e != s) { + e = e->prev; + + if (e != s) + s = s->next; + } + + __list_cut_position(list, head, s); +} + +void list_expr_sort(struct list_head *head) +{ + struct list_head *list; + LIST_HEAD(temp); + + list = &temp; + + if (list_empty(head) || list_is_singular(head)) + return; + + list_cut_middle(list, head); + + list_expr_sort(head); + list_expr_sort(list); + + list_splice_sorted(list, head); +} |