[vlc-devel] commit: async event handling: Push is now O(1) instead of O(n). (JP Dinger )

[git version control]

vlc | branch: master | JP Dinger <jpd at videolan.org> | Wed Jan 27 13:10:16 2010 +0100| [e783869a8dd6fcaf64dd8324c9938285f6b5c871] | committer: JP Dinger 

async event handling: Push is now O(1) instead of O(n).

> http://git.videolan.org/gitweb.cgi/vlc.git/?a=commit;h=e783869a8dd6fcaf64dd8324c9938285f6b5c871
---

 src/control/event_async.c |   76 ++++++++++++++++++++++++--------------------
 1 files changed, 41 insertions(+), 35 deletions(-)

diff --git a/src/control/event_async.c b/src/control/event_async.c
index ecb6fa8..bed235e 100644
--- a/src/control/event_async.c
+++ b/src/control/event_async.c
@@ -17,9 +17,9 @@
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
  *****************************************************************************/
 
 #ifdef HAVE_CONFIG_H
@@ -40,13 +40,16 @@ struct queue_elmt {
 };
 
 struct libvlc_event_async_queue {
-    struct queue_elmt * elements;
+    struct queue_elmt *first_elmt, *last_elmt;
     vlc_mutex_t lock;
     vlc_cond_t signal;
     vlc_thread_t thread;
     bool is_idle;
     vlc_cond_t signal_idle;
     vlc_threadvar_t is_asynch_dispatch_thread_var;
+#ifndef NDEBUG
+    long count;
+#endif
 };
 
 /*
@@ -71,37 +74,29 @@ static inline bool current_thread_is_asynch_thread(libvlc_event_manager_t * p_em
 }
 
 /* Lock must be held */
-static void push(libvlc_event_manager_t * p_em, libvlc_event_listener_t * listener, libvlc_event_t * event)
+static void push(libvlc_event_manager_t * p_em,
+                 libvlc_event_listener_t * listener, libvlc_event_t * event)
 {
-#ifndef NDEBUG
-    static const long MaxQueuedItem = 300000;
-    long count = 0;
-#endif
-
     struct queue_elmt * elmt = malloc(sizeof(struct queue_elmt));
     elmt->listener = *listener;
     elmt->event = *event;
     elmt->next = NULL;
 
     /* Append to the end of the queue */
-    struct queue_elmt * iter = queue(p_em)->elements;
-    if(!iter)
-    {
-        queue(p_em)->elements = elmt;
-        return;
-    }
+    if(!queue(p_em)->first_elmt)
+        queue(p_em)->first_elmt = elmt;
+    else
+        queue(p_em)->last_elmt->next = elmt;
+    queue(p_em)->last_elmt = elmt;
 
-    while (iter->next) {
-        iter = iter->next;
 #ifndef NDEBUG
-        if(count++ > MaxQueuedItem)
-        {
-            fprintf(stderr, "Warning: libvlc event overflow.\n");
-            abort();
-        }
-#endif
+    enum { MaxQueueSize = 300000 };
+    if(queue(p_em)->count++ > MaxQueueSize)
+    {
+        fprintf(stderr, "Warning: libvlc event overflow.\n");
+        abort();
     }
-    iter->next = elmt;
+#endif
 }
 
 static inline void queue_lock(libvlc_event_manager_t * p_em)
@@ -115,16 +110,23 @@ static inline void queue_unlock(libvlc_event_manager_t * p_em)
 }
 
 /* Lock must be held */
-static bool pop(libvlc_event_manager_t * p_em, libvlc_event_listener_t * listener, libvlc_event_t * event)
+static bool pop(libvlc_event_manager_t * p_em,
+                libvlc_event_listener_t * listener, libvlc_event_t * event)
 {
-    if(!queue(p_em)->elements)
-        return false; /* No elements */
+    if(!queue(p_em)->first_elmt)
+        return false; /* No first_elmt */
+
+    struct queue_elmt * elmt = queue(p_em)->first_elmt;
+    *listener = elmt->listener;
+    *event = elmt->event;
 
-    *listener = queue(p_em)->elements->listener;
-    *event = queue(p_em)->elements->event;
+    queue(p_em)->first_elmt = elmt->next;
+    if( !elmt->next ) queue(p_em)->last_elmt=NULL;
+
+#ifndef NDEBUG
+    queue(p_em)->count--;
+#endif
 
-    struct queue_elmt * elmt = queue(p_em)->elements;
-    queue(p_em)->elements = elmt->next;
     free(elmt);
     return true;
 }
@@ -132,24 +134,28 @@ static bool pop(libvlc_event_manager_t * p_em, libvlc_event_listener_t * listene
 /* Lock must be held */
 static void pop_listener(libvlc_event_manager_t * p_em, libvlc_event_listener_t * listener)
 {
-    struct queue_elmt * iter = queue(p_em)->elements;
+    struct queue_elmt * iter = queue(p_em)->first_elmt;
     struct queue_elmt * prev = NULL;
     while (iter) {
         if(listeners_are_equal(&iter->listener, listener))
         {
             struct queue_elmt * to_delete = iter;
             if(!prev)
-                queue(p_em)->elements = to_delete->next;
+                queue(p_em)->first_elmt = to_delete->next;
             else
                 prev->next = to_delete->next;
             iter = to_delete->next;
             free(to_delete);
+#ifndef NDEBUG
+            queue(p_em)->count--;
+#endif
         }
         else {
             prev = iter;
             iter = iter->next;
         }
     }
+    queue(p_em)->last_elmt=prev;
 }
 
 /**************************************************************************
@@ -180,7 +186,7 @@ libvlc_event_async_fini(libvlc_event_manager_t * p_em)
     vlc_cond_destroy(&queue(p_em)->signal_idle);
     vlc_threadvar_delete(&queue(p_em)->is_asynch_dispatch_thread_var);
 
-    struct queue_elmt * iter = queue(p_em)->elements;
+    struct queue_elmt * iter = queue(p_em)->first_elmt;
     while (iter) {
         struct queue_elmt * elemt_to_delete = iter;
         iter = iter->next;