diff options
author | 2016-06-03 00:19:26 +0200 | |
---|---|---|
committer | 2016-06-03 00:19:26 +0200 | |
commit | 431013db724d26590a6d0f87b6afbf8e3fa08208 (patch) | |
tree | 634c9197d6dd1dfebbb124d797f5c13b1c605a92 /common/list.c | |
parent | Fix output command when varible not set (diff) | |
parent | Merge pull request #692 from zandrmartin/inplace-merge-sort (diff) | |
download | sway-431013db724d26590a6d0f87b6afbf8e3fa08208.tar.gz sway-431013db724d26590a6d0f87b6afbf8e3fa08208.tar.zst sway-431013db724d26590a6d0f87b6afbf8e3fa08208.zip |
Merge branch 'master' of https://github.com/SirCmpwn/sway into variables_corner_cases
Diffstat (limited to 'common/list.c')
-rw-r--r-- | common/list.c | 59 |
1 files changed, 58 insertions, 1 deletions
diff --git a/common/list.c b/common/list.c index a7585a31..d57234e3 100644 --- a/common/list.c +++ b/common/list.c | |||
@@ -59,7 +59,7 @@ void list_cat(list_t *list, list_t *source) { | |||
59 | } | 59 | } |
60 | } | 60 | } |
61 | 61 | ||
62 | void list_qsort(list_t* list, int compare(const void *left, const void *right)) { | 62 | void list_qsort(list_t *list, int compare(const void *left, const void *right)) { |
63 | qsort(list->items, list->length, sizeof(void *), compare); | 63 | qsort(list->items, list->length, sizeof(void *), compare); |
64 | } | 64 | } |
65 | 65 | ||
@@ -72,3 +72,60 @@ int list_seq_find(list_t *list, int compare(const void *item, const void *data), | |||
72 | } | 72 | } |
73 | return -1; | 73 | return -1; |
74 | } | 74 | } |
75 | |||
76 | static void list_swap(list_t *list, int src, int dest) { | ||
77 | void *tmp = list->items[src]; | ||
78 | list->items[src] = list->items[dest]; | ||
79 | list->items[dest] = tmp; | ||
80 | } | ||
81 | |||
82 | static void list_rotate(list_t *list, int from, int to) { | ||
83 | void *tmp = list->items[to]; | ||
84 | |||
85 | while (to > from) { | ||
86 | list->items[to] = list->items[to - 1]; | ||
87 | to--; | ||
88 | } | ||
89 | |||
90 | list->items[from] = tmp; | ||
91 | } | ||
92 | |||
93 | static void list_inplace_merge(list_t *list, int left, int last, int mid, int compare(const void *a, const void *b)) { | ||
94 | int right = mid + 1; | ||
95 | |||
96 | if (compare(&list->items[mid], &list->items[right]) <= 0) { | ||
97 | return; | ||
98 | } | ||
99 | |||
100 | while (left <= mid && right <= last) { | ||
101 | if (compare(&list->items[left], &list->items[right]) <= 0) { | ||
102 | left++; | ||
103 | } else { | ||
104 | list_rotate(list, left, right); | ||
105 | left++; | ||
106 | mid++; | ||
107 | right++; | ||
108 | } | ||
109 | } | ||
110 | } | ||
111 | |||
112 | static void list_inplace_sort(list_t *list, int first, int last, int compare(const void *a, const void *b)) { | ||
113 | if (first >= last) { | ||
114 | return; | ||
115 | } else if ((last - first) == 1) { | ||
116 | if (compare(&list->items[first], &list->items[last]) > 0) { | ||
117 | list_swap(list, first, last); | ||
118 | } | ||
119 | } else { | ||
120 | int mid = (int)((last + first) / 2); | ||
121 | list_inplace_sort(list, first, mid, compare); | ||
122 | list_inplace_sort(list, mid + 1, last, compare); | ||
123 | list_inplace_merge(list, first, last, mid, compare); | ||
124 | } | ||
125 | } | ||
126 | |||
127 | void list_stable_sort(list_t *list, int compare(const void *a, const void *b)) { | ||
128 | if (list->length > 1) { | ||
129 | list_inplace_sort(list, 0, list->length - 1, compare); | ||
130 | } | ||
131 | } | ||