summaryrefslogtreecommitdiffstats
path: root/src/seq.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/seq.c')
-rw-r--r--src/seq.c93
1 files changed, 81 insertions, 12 deletions
diff --git a/src/seq.c b/src/seq.c
index e0854f5..1edfe24 100644
--- a/src/seq.c
+++ b/src/seq.c
@@ -64,26 +64,95 @@ error_malloc_item:
return -1;
}
-static void event_sort(xas_seq *seq) {
- xas_seq_event_list_item *item = seq->first,
- *temp = NULL;
+static xas_seq_event_list_item *event_list_tail(xas_seq_event_list_item *head) {
+ if (head == NULL) {
+ return NULL;
+ }
- while (item) {
- temp = item;
+ while (head->next) {
+ head = head->next;
+ }
+
+ return head;
+}
+
+static xas_seq_event_list_item *event_list_partition(xas_seq_event_list_item *head,
+ xas_seq_event_list_item *end,
+ xas_seq_event_list_item **head_new,
+ xas_seq_event_list_item **end_new) {
+ xas_seq_event_list_item *pivot = end,
+ *prev = NULL,
+ *cur = head,
+ *tail = pivot;
+
+ while (cur != pivot) {
+ if (timercmp(&cur->ev->timestamp, &pivot->ev->timestamp, <)) {
+ if (*head_new == NULL) {
+ *head_new = cur;
+ }
- while (temp->next) {
- if (timercmp(&temp->ev->timestamp, &temp->next->ev->timestamp, >)) {
- xas_seq_event *ev = temp->ev;
+ prev = cur;
+ cur = cur->next;
+ } else {
+ xas_seq_event_list_item *tmp;
- temp->ev = temp->next->ev;
- temp->next->ev = ev;
+ if (prev) {
+ prev->next = cur->next;
}
- temp = temp->next;
+ tmp = cur->next;
+
+ cur->next = NULL;
+ tail->next = cur;
+ tail = cur;
+ cur = tmp;
}
+ }
- item = item->next;
+ if (*head_new == NULL) {
+ *head_new = pivot;
}
+
+ *end_new = tail;
+
+ return pivot;
+}
+
+static xas_seq_event_list_item *event_list_sort_recur(xas_seq_event_list_item *head,
+ xas_seq_event_list_item *end) {
+ xas_seq_event_list_item *head_new = NULL,
+ *end_new = NULL,
+ *pivot;
+
+ if (head == NULL || head == end) {
+ return head;
+ }
+
+ pivot = event_list_partition(head, end, &head_new, &end_new);
+
+ if (head_new != pivot) {
+ xas_seq_event_list_item *tmp = head_new;
+
+ while (tmp->next != pivot) {
+ tmp = tmp->next;
+ }
+
+ tmp->next = NULL;
+
+ head_new = event_list_sort_recur(head_new, tmp);
+
+ tmp = event_list_tail(head_new);
+ tmp->next = pivot;
+ }
+
+ pivot->next = event_list_sort_recur(pivot->next, end_new);
+
+ return head_new;
+}
+
+static void event_sort(xas_seq *seq) {
+ seq->first = event_list_sort_recur(seq->first, seq->last);
+ seq->last = event_list_tail(seq->first);
}
int xas_seq_add_event_off(xas_seq *seq,