diff options
author | Drew DeVault <sir@cmpwn.com> | 2016-06-02 17:05:41 -0400 |
---|---|---|
committer | Drew DeVault <sir@cmpwn.com> | 2016-06-02 17:05:41 -0400 |
commit | 68b517e1aee452463c7eff3775f8b56b0e48bc54 (patch) | |
tree | 6ccc4143129cdfe354aa01f80c80deff1cca4ca4 | |
parent | Merge pull request #691 from thuck/floating_size_conf (diff) | |
parent | implement stable sort for lists (diff) | |
download | sway-68b517e1aee452463c7eff3775f8b56b0e48bc54.tar.gz sway-68b517e1aee452463c7eff3775f8b56b0e48bc54.tar.zst sway-68b517e1aee452463c7eff3775f8b56b0e48bc54.zip |
Merge pull request #692 from zandrmartin/inplace-merge-sort
implement stable sort for lists
-rw-r--r-- | common/list.c | 59 | ||||
-rw-r--r-- | include/list.h | 3 | ||||
-rw-r--r-- | include/output.h | 2 | ||||
-rw-r--r-- | sway/output.c | 5 |
4 files changed, 64 insertions, 5 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 | } | ||
diff --git a/include/list.h b/include/list.h index b2e26f95..f478b6bb 100644 --- a/include/list.h +++ b/include/list.h | |||
@@ -20,5 +20,6 @@ void list_qsort(list_t *list, int compare(const void *left, const void *right)); | |||
20 | // Return index for first item in list that returns 0 for given compare | 20 | // Return index for first item in list that returns 0 for given compare |
21 | // function or -1 if none matches. | 21 | // function or -1 if none matches. |
22 | int list_seq_find(list_t *list, int compare(const void *item, const void *cmp_to), const void *cmp_to); | 22 | int list_seq_find(list_t *list, int compare(const void *item, const void *cmp_to), const void *cmp_to); |
23 | 23 | // stable sort since qsort is not guaranteed to be stable | |
24 | void list_stable_sort(list_t *list, int compare(const void *a, const void *b)); | ||
24 | #endif | 25 | #endif |
diff --git a/include/output.h b/include/output.h index 12bc478f..10c5bb53 100644 --- a/include/output.h +++ b/include/output.h | |||
@@ -16,7 +16,7 @@ void get_absolute_position(swayc_t *container, struct wlc_point *point); | |||
16 | // given wlc_point. | 16 | // given wlc_point. |
17 | void get_absolute_center_position(swayc_t *container, struct wlc_point *point); | 17 | void get_absolute_center_position(swayc_t *container, struct wlc_point *point); |
18 | 18 | ||
19 | int sort_workspace_cmp_qsort(const void *a, const void *b); | 19 | // stable sort workspaces on this output |
20 | void sort_workspaces(swayc_t *output); | 20 | void sort_workspaces(swayc_t *output); |
21 | 21 | ||
22 | #endif | 22 | #endif |
diff --git a/sway/output.c b/sway/output.c index 53b24232..d56a2f30 100644 --- a/sway/output.c +++ b/sway/output.c | |||
@@ -3,6 +3,7 @@ | |||
3 | #include <stdlib.h> | 3 | #include <stdlib.h> |
4 | #include "output.h" | 4 | #include "output.h" |
5 | #include "log.h" | 5 | #include "log.h" |
6 | #include "list.h" | ||
6 | 7 | ||
7 | swayc_t *output_by_name(const char* name, const struct wlc_point *abs_pos) { | 8 | swayc_t *output_by_name(const char* name, const struct wlc_point *abs_pos) { |
8 | if (strcasecmp(name, "left") == 0) { | 9 | if (strcasecmp(name, "left") == 0) { |
@@ -180,7 +181,7 @@ void get_absolute_center_position(swayc_t *container, struct wlc_point *point) { | |||
180 | point->y += container->height/2; | 181 | point->y += container->height/2; |
181 | } | 182 | } |
182 | 183 | ||
183 | int sort_workspace_cmp_qsort(const void *_a, const void *_b) { | 184 | static int sort_workspace_cmp_qsort(const void *_a, const void *_b) { |
184 | swayc_t *a = *(void **)_a; | 185 | swayc_t *a = *(void **)_a; |
185 | swayc_t *b = *(void **)_b; | 186 | swayc_t *b = *(void **)_b; |
186 | int retval = 0; | 187 | int retval = 0; |
@@ -199,5 +200,5 @@ int sort_workspace_cmp_qsort(const void *_a, const void *_b) { | |||
199 | } | 200 | } |
200 | 201 | ||
201 | void sort_workspaces(swayc_t *output) { | 202 | void sort_workspaces(swayc_t *output) { |
202 | list_qsort(output->children, sort_workspace_cmp_qsort); | 203 | list_stable_sort(output->children, sort_workspace_cmp_qsort); |
203 | } | 204 | } |