Add sorted linked list to sequenced events

2 files changed, 118 insertions, 68 deletions

diff --git a/include/xas/seq.h b/include/xas/seq.h
index f7ec322..86acefc 100644
--- a/include/xas/seq.h
+++ b/include/xas/seq.h
@@ -50,15 +50,20 @@ struct _xas_seq_event {
         enum xas_synth_type synth_type;
         const char *phrase;
     };
+};
+
+typedef struct _xas_seq_event_list_item xas_seq_event_list_item;
 
-    xas_seq_event *next;
+struct _xas_seq_event_list_item {
+    xas_seq_event *ev;
+    xas_seq_event_list_item *next;
 };
 
 typedef struct _xas_seq {
     xas_spatial_scene *scene;
 
-    xas_seq_event *first,
-                    *last;
+    xas_seq_event_list_item *first,
+                              *last;
 
     size_t buffer_size;
 } xas_seq;
diff --git a/src/seq.c b/src/seq.c
index b29a98a..42c20f6 100644
--- a/src/seq.c
+++ b/src/seq.c
@@ -26,64 +26,63 @@ error_malloc_seq:
 }
 
 void xas_seq_destroy(xas_seq *seq) {
-    xas_seq_event *event = seq->first;
+    xas_seq_event_list_item *item = seq->first;
 
-    while (event) {
-        xas_seq_event *next = event->next;
+    while (item) {
+        xas_seq_event_list_item *next = item->next;
 
-        free(event);
+        free(item->ev);
+        free(item);
 
-        event = next;
+        item = next;
     }
 
     free(seq);
 }
 
-static void add_event(xas_seq *seq, xas_seq_event *ev) {
-    xas_seq_event *current = seq->first,
-                    *prev    = NULL;
+static int add_event(xas_seq *seq, xas_seq_event *ev) {
+    xas_seq_event_list_item *item;
 
-    if (seq->first == NULL) {
-        seq->first = ev;
-        seq->last  = ev;
+    if ((item = malloc(sizeof(*item))) == NULL) {
+        goto error_malloc_item;
+    }
 
-        return;
+    item->ev   = ev;
+    item->next = NULL;
+
+    if (seq->first == NULL) {
+        seq->first = item;
+        seq->last  = item;
+    } else {
+        seq->last->next = item;
+        seq->last       = item;
     }
 
-    while (current) {
-        xas_seq_event *next = current->next;
+    return 0;
 
-        if (timercmp(&ev->timestamp, &seq->last->timestamp, >=)) {
-            seq->last->next = ev;
-            seq->last       = ev;
+error_malloc_item:
+    return -1;
+}
 
-            return;
-        } else if (timercmp(&ev->timestamp, &current->timestamp, >)) {
-            ev->next      = current->next;
-            current->next = ev;
+static void sort_events(xas_seq *seq) {
+    xas_seq_event_list_item *item = seq->first,
+                              *temp = NULL;
 
-            return;
-        } else if (prev && timercmp(&ev->timestamp, &prev->timestamp,    >)
-                        && timercmp(&ev->timestamp, &current->timestamp, <=)) {
-            prev->next = ev;
-            ev->next   = current;
+    while (item) {
+        temp = item;
 
-            return;
-        } else if (prev && timercmp(&ev->timestamp, &prev->timestamp,       <=)
-                        && timercmp(&ev->timestamp, &seq->first->timestamp, >)) {
-            ev->next         = seq->first->next;
-            seq->first->next = ev;
+        while (temp->next) {
+            if (timercmp(&temp->ev->timestamp, &temp->next->ev->timestamp, >)) {
+                xas_seq_event *ev = temp->ev;
 
-            return;
-        } else if (timercmp(&ev->timestamp, &seq->first->timestamp, <=)) {
-            ev->next   = seq->first;
-            seq->first = ev;
+                temp->ev       = temp->next->ev;
+                temp->next->ev = ev;
+            }
 
-            return;
+            temp = temp->next;
         }
 
-        prev    = current;
-        current = next;
+        item = item->next;
     }
 }
 
@@ -100,12 +99,16 @@ int xas_seq_add_event_off(xas_seq *seq,
     ev->objtype   = XAS_SEQ_OBJECT_ANY;
     ev->object    = object;
     ev->timestamp = timestamp;
-    ev->next      = NULL;
 
-    add_event(seq, ev);
+    if (add_event(seq, ev) < 0) {
+        goto error_add_event;
+    }
 
     return 0;
 
+error_add_event:
+    free(ev);
+
 error_malloc_ev:
     return -1;
 }
@@ -123,12 +126,16 @@ int xas_seq_add_event_on(xas_seq *seq,
     ev->objtype   = XAS_SEQ_OBJECT_ANY;
     ev->object    = object;
     ev->timestamp = timestamp;
-    ev->next      = NULL;
 
-    add_event(seq, ev);
+    if (add_event(seq, ev) < 0) {
+        goto error_add_event;
+    }
 
     return 0;
 
+error_add_event:
+    free(ev);
+
 error_malloc_ev:
     return -1;
 }
@@ -148,12 +155,16 @@ int xas_seq_add_set_position(xas_seq *seq,
     ev->object    = object;
     ev->timestamp = timestamp;
     ev->point     = point;
-    ev->next      = NULL;
 
-    add_event(seq, ev);
+    if (add_event(seq, ev) < 0) {
+        goto error_add_event;
+    }
 
     return 0;
 
+error_add_event:
+    free(ev);
+
 error_malloc_ev:
     return -1;
 }
@@ -173,12 +184,16 @@ int xas_seq_add_set_heading(xas_seq *seq,
     ev->object    = object;
     ev->timestamp = timestamp;
     ev->heading   = heading;
-    ev->next      = NULL;
 
-    add_event(seq, ev);
+    if (add_event(seq, ev) < 0) {
+        goto error_add_event;
+    }
 
     return 0;
 
+error_add_event:
+    free(ev);
+
 error_malloc_ev:
     return -1;
 }
@@ -198,12 +213,16 @@ int xas_seq_add_set_speed(xas_seq *seq,
     ev->object    = object;
     ev->timestamp = timestamp;
     ev->speed     = speed;
-    ev->next      = NULL;
 
-    add_event(seq, ev);
+    if (add_event(seq, ev) < 0) {
+        goto error_add_event;
+    }
 
     return 0;
 
+error_add_event:
+    free(ev);
+
 error_malloc_ev:
     return -1;
 }
@@ -223,12 +242,16 @@ int xas_seq_add_set_gain(xas_seq *seq,
     ev->object    = object;
     ev->timestamp = timestamp;
     ev->gain      = gain;
-    ev->next      = NULL;
 
-    add_event(seq, ev);
+    if (add_event(seq, ev) < 0) {
+        goto error_add_event;
+    }
 
     return 0;
 
+error_add_event:
+    free(ev);
+
 error_malloc_ev:
     return -1;
 }
@@ -247,13 +270,17 @@ int xas_seq_add_set_bank(xas_seq *seq,
     ev->objtype   = XAS_SEQ_OBJECT_BANK_PLAYER;
     ev->object    = object;
     ev->timestamp = timestamp;
-    ev->next      = NULL;
     ev->index     = index;
 
-    add_event(seq, ev);
+    if (add_event(seq, ev) < 0) {
+        goto error_add_event;
+    }
 
     return 0;
 
+error_add_event:
+    free(ev);
+
 error_malloc_ev:
     return -1;
 }
@@ -272,13 +299,17 @@ int xas_seq_add_set_player_flags(xas_seq *seq,
     ev->objtype   = XAS_SEQ_OBJECT_BANK_PLAYER;
     ev->object    = object;
     ev->timestamp = timestamp;
-    ev->next      = NULL;
     ev->flags     = flags;
 
-    add_event(seq, ev);
+    if (add_event(seq, ev) < 0) {
+        goto error_add_event;
+    }
 
     return 0;
 
+error_add_event:
+    free(ev);
+
 error_malloc_ev:
     return -1;
 }
@@ -297,13 +328,17 @@ int xas_seq_add_set_synth_type(xas_seq *seq,
     ev->objtype    = XAS_SEQ_OBJECT_SYNTH;
     ev->object     = object;
     ev->timestamp  = timestamp;
-    ev->next       = NULL;
     ev->synth_type = type;
 
-    add_event(seq, ev);
+    if (add_event(seq, ev) < 0) {
+        goto error_add_event;
+    }
 
     return 0;
 
+error_add_event:
+    free(ev);
+
 error_malloc_ev:
     return -1;
 }
@@ -322,13 +357,17 @@ int xas_seq_add_set_frequency(xas_seq *seq,
     ev->objtype   = XAS_SEQ_OBJECT_SYNTH;
     ev->object    = object;
     ev->timestamp = timestamp;
-    ev->next      = NULL;
     ev->frequency = frequency;
 
-    add_event(seq, ev);
+    if (add_event(seq, ev) < 0) {
+        goto error_add_event;
+    }
 
     return 0;
 
+error_add_event:
+    free(ev);
+
 error_malloc_ev:
     return -1;
 }
@@ -347,13 +386,17 @@ int xas_seq_add_phrase(xas_seq *seq,
     ev->objtype   = XAS_SEQ_OBJECT_VOX;
     ev->object    = object;
     ev->timestamp = timestamp;
-    ev->next      = NULL;
     ev->phrase    = phrase;
 
-    add_event(seq, ev);
+    if (add_event(seq, ev) < 0) {
+        goto error_add_event;
+    }
 
     return 0;
 
+error_add_event:
+    free(ev);
+
 error_malloc_ev:
     return -1;
 }
@@ -451,7 +494,7 @@ static inline void timerupdate(struct timeval *tv,
 }
 
 int xas_seq_play(xas_seq *seq, xas_audio_stream *sink) {
-    xas_seq_event *ev = seq->first;
+    xas_seq_event_list_item *item = seq->first;
     xas_audio_stream *source;
 
     size_t frame       = 0,
@@ -462,24 +505,26 @@ int xas_seq_play(xas_seq *seq, xas_audio_stream *sink) {
 
     int16_t *samples;
 
+    sort_events(seq);
+
     if ((source = xas_spatial_scene_stream_new(seq->scene,
                                                  seq->buffer_size)) == NULL) {
         goto error_spatial_scene_stream_new;
     }
 
-    while (ev) {
+    while (item) {
         struct timeval tv;
 
         ssize_t readlen;
 
         timerupdate(&tv, interval, frame);
 
-        while (ev && !timercmp(&tv, &ev->timestamp, <)) {
-            if (event_trigger(seq->scene, ev) < 0) {
+        while (item && !timercmp(&tv, &item->ev->timestamp, <)) {
+            if (event_trigger(seq->scene, item->ev) < 0) {
                 goto error_event_trigger;
             }
 
-            ev = ev->next;
+            item = item->next;
         }
 
         if ((readlen = xas_audio_stream_read(source,