rewrite lf_fifo

2 files changed, 92 insertions, 83 deletions

diff --git a/lf_fifo.c b/lf_fifo.c
index 6e58a4f..f4e3931 100644
--- a/lf_fifo.c
+++ b/lf_fifo.c
@@ -1,7 +1,7 @@
 /*
  * File     : lf_fifo.c
  * Author   : Jérémy Zurcher  <jeremy@asynk.ch>
- * Date     : 01/11/09 
+ * Date     : 2009/11/01
  * License  :
  *
  *  Permission is hereby granted, free of charge, to any person obtaining
@@ -11,10 +11,10 @@
  *  distribute, sublicense, and/or sell copies of the Software, and to
  *  permit persons to whom the Software is furnished to do so, subject to
  *  the following conditions:
- *  
+ *
  *  The above copyright notice and this permission notice shall be
  *  included in all copies or substantial portions of the Software.
- *  
+ *
  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
@@ -28,85 +28,93 @@
 #include "lf_fifo.h"
 #include <stdlib.h>
 
-/* initialize an empty lf_fifo structure */
-void lf_fifo_init( lf_fifo_t *q ) {
-    q->head.ptr = q->tail.ptr = NULL;
-    q->head.count = q->tail.count = 0;
+void lf_fifo_init( lf_fifo_t *fifo )
+{
+   lf_pointer_set(fifo->head,NULL);
+   lf_pointer_set(fifo->tail,NULL);
+   lf_counter_set(fifo->head,0);
+   lf_counter_set(fifo->tail,0);
 }
 
-/* push a node at the tail of q */
-void lf_fifo_push( lf_fifo_t *q, lf_pointer_t *node ) {
-    lf_pointer_t tail;
-    lf_pointer_t last;
-    lf_pointer_t tmp;
+void lf_fifo_push( lf_fifo_t *fifo, lf_pointer_t *node )
+{
+   lf_pointer_t tail;
+   lf_pointer_t last;
+   lf_pointer_t new_node;
 
-    /* init node */
-    node->ptr = NULL;
-    node->count = 0;
+   lf_pointer_set(*node,NULL);
+   lf_counter_set(*node,0);
 
-    /* set tmp to point to node */
-    tmp.ptr = node;
-    tmp.count = 1;
+   lf_pointer_set(new_node,node);
+   lf_counter_set(new_node,1);
 
-    for(;;) {
-        /* snapshot tail */
-        tail = q->tail;
-        /* nothing in tail link as first node */
-        if ( tail.ptr==NULL && cas( &q->tail, tail, tmp ) ) {       /* TODO right place ?? */
-            q->head.ptr = node;
-            /* q->head.count = 1; ??? */
-            return;
-        } else {
-            /* snapshot last through tail */
-            last = *tail.ptr;
-            /* if tail is still consistant */
-            if lf_eql(tail,q->tail) {
-                /* if last is the last node */
-                if (last.ptr == NULL) {
-                    tmp.count = last.count+1;
-                    if ( cas( tail.ptr, last, tmp ) ) break;
-                } else {
-                    /* try to swing tail to the next node */
-                    last.count = tail.count+1;
-                    cas( &q->tail, tail, last );
-                }
-            }
-        }
-    }
-    /* try to swing tail to the next node */
-    tmp.count = tail.count+1;
-    cas( &q->tail, tail, tmp );
+   for(;;)
+     {
+        tail = fifo->tail;
+        if (lf_pointer_null(tail))
+          {
+             /* link new_node as first node */
+             if (lf_cas(&fifo->tail, tail, new_node))
+               {
+                  lf_cas(&fifo->head, tail, new_node);
+                  break;
+               }
+          }
+        else
+          {
+             last = *((lf_pointer_t*)tail.pointer);
+             if (lf_pointer_null(last))
+               {
+                  /* link new_node as last node */
+                  if (lf_cas((lf_pointer_t*)(fifo->tail.pointer), last, new_node))
+                    {
+                       break;
+                    }
+               }
+             else
+               {
+                  /* try to swing tail to the next node */
+                  lf_counter_set(last,tail.counter+1);
+                  lf_cas(&fifo->tail, tail, last);
+               }
+          }
+     }
+   /* try to swing tail to the new node */
+   lf_counter_set(new_node,tail.counter+1);
+   lf_cas(&fifo->tail, tail, new_node);
 }
 
 /* pop a node from the head of q */
-lf_pointer_t* pop( lf_fifo_t *q ) {
-    lf_pointer_t head;
-    lf_pointer_t tail;
-    lf_pointer_t tmp;
-    lf_pointer_t *node;
+lf_pointer_t* lf_fifo_pop( lf_fifo_t *fifo )
+{
+   lf_pointer_t head;
+   lf_pointer_t tail;
+   lf_pointer_t tmp;
+   lf_pointer_t *node;
+
+   for(;;)
+     {
+        if (lf_pointer_null(fifo->head))
+          {
+             return NULL;
+          }
+
+        head = fifo->head;
+        tail = fifo->tail;
+        if (lf_eq(tail,head))
+          {
+             /* try to swing tail to the next node */
+             tmp = *((lf_pointer_t*)tail.pointer);
+             lf_counter_set(tmp,tail.counter+1);
+             lf_cas(&fifo->tail, tail, tmp);
+          }
 
-    for(;;) {
-        /* snapshot head */
-        head = q->head;
-        /* return NULL if queue is empty */
-        if (head.ptr == NULL) { return NULL; }                      /* TODO before snapshot using q-> ?? */
-        /* snapshot tail */
-        tail = q->tail;
-        /* if there is only one node in the queue */
-        if ( tail.ptr == head.ptr ) {
-            /* tail points to NULL */
-            tmp.ptr = NULL;
-            tmp.count = tail.count+1;
-            cas( &q->tail, tail, tmp );
-        } else {
-            /* get the node ptr */
-            node = (lf_pointer_t*)head.ptr;
-            /* get the next head ready */
-            tmp.ptr = node->ptr;
-            tmp.count = head.count+1;
-            if ( cas( &q->head, head, tmp ) ) break;
-        }
-    }
-    return node;
+        node = (lf_pointer_t*)head.pointer;
+        tmp = *node;
+        /* try to swing head to the next node */
+        lf_counter_set(tmp,head.counter+1);
+        if ( lf_cas(&fifo->head, head, tmp) ) break;
+     }
+   return node;
 }
 
diff --git a/lf_fifo.h b/lf_fifo.h
index 11de7c3..618b661 100644
--- a/lf_fifo.h
+++ b/lf_fifo.h
@@ -1,7 +1,7 @@
 /*
  * File     : lf_fifo.h
  * Author   : Jérémy Zurcher  <jeremy@asynk.ch>
- * Date     : 02/11/09 
+ * Date     : 2009/11/02
  * License  :
  *
  *  Permission is hereby granted, free of charge, to any person obtaining
@@ -11,10 +11,10 @@
  *  distribute, sublicense, and/or sell copies of the Software, and to
  *  permit persons to whom the Software is furnished to do so, subject to
  *  the following conditions:
- *  
+ *
  *  The above copyright notice and this permission notice shall be
  *  included in all copies or substantial portions of the Software.
- *  
+ *
  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
@@ -34,19 +34,20 @@
 extern "C" {
 # endif /* __cplusplus */
 
-typedef struct queue {
-    lf_pointer_t head;
-    lf_pointer_t tail;
+typedef struct _lf_fifo_t
+{
+   lf_pointer_t head;
+   lf_pointer_t tail;
 } lf_fifo_t;
 
 /* initialize an empty lf_fifo structure */
-void lf_fifo_init( lf_fifo_t *q );
+void lf_fifo_init( lf_fifo_t *fifo );
 
 /* push a node at the tail of q */
-void lf_fifo_push( lf_fifo_t *q, lf_pointer_t *node );
+void lf_fifo_push( lf_fifo_t *fifo, lf_pointer_t *node );
 
 /* pop a node from the head of q */
-lf_pointer_t* pop( lf_fifo_t *q );
+lf_pointer_t* lf_fifo_pop( lf_fifo_t *fifo );
 
 # ifdef __cplusplus
 }