lf_fifo don't use union anymore, just for one ==

5 files changed, 97 insertions, 86 deletions

diff --git a/Makefile b/Makefile
index 27586c4..a12803a 100644
--- a/Makefile
+++ b/Makefile
@@ -3,7 +3,7 @@
 CC     = gcc
 STD    = _GNU_SOURCE
 CFLAGS = -DDEBUG
-BIN    = cas container_of lock_free_queue_test lf_fifo
+BIN    = cas container_of lock_free_queue_test lf_fifo_test
 
 .c.o:
 	$(CC) -c -Wall -I. $(CFLAGS) -D$(STD) $<
@@ -21,8 +21,6 @@ container_of: container_of.o
 lock_free_queue_test: lock_free_queue.o lock_free_queue_test.o
 	$(CC) lock_free_queue.o lock_free_queue_test.o -o lock_free_queue_test
 
-
-
 lf_fifo.o: lf_fifo.h lf_cas.h
 
 lf_fifo_test: lf_fifo.o lf_fifo_test.o
diff --git a/lf_fifo_cas.h b/lf_cas.h
index e380f8e..1a21bf1 100644
--- a/lf_fifo_cas.h
+++ b/lf_cas.h
@@ -1,5 +1,5 @@
 /*
- * File     : lf_fifo_cas.h
+ * File     : lf_cas.h
  * Author   : Jérémy Zurcher  <jeremy@asynk.ch>
  * Date     : 01/11/09 
  * License  :
@@ -25,18 +25,37 @@
  *
  */
 
-#include "lf_fifo.h"
+#ifndef _LF_CAS_H_
+#define _LF_CAS_H_
+
+# ifdef __cplusplus
+extern "C" {
+# endif /* __cplusplus */
+
+struct lf_pointer;
+
+typedef struct lf_pointer {
+    volatile struct lf_pointer *ptr;
+    volatile unsigned int count;
+} lf_pointer_t;
+
 
 /* CMPXCHG8B m64   Compare EDX:EAX with m64. If equal, set ZF and load ECX:EBX into m64. Else, clear ZF and load m64 into EDX:EAX. */
-static inline unsigned int cas( volatile struct split *mem,
-                                volatile struct split old,
-                                volatile struct split new ) {
+static inline unsigned int cas( volatile lf_pointer_t *mem,
+                                volatile lf_pointer_t old,
+                                volatile lf_pointer_t new ) {
     char result;
     __asm__ __volatile__("lock; cmpxchg8b %0; setz %1;"
             : "=m"(*mem), "=q"(result)
-            : "m"(*mem), "d" (old.count), "a" (old.next),
-            "c" (new.count), "b" (new.next)
+            : "m"(*mem), "d" (old.count), "a" (old.ptr),
+            "c" (new.count), "b" (new.ptr)
             : "memory");
     return (int)result;
 }
 
+# ifdef __cplusplus
+}
+# endif /* __cplusplus */
+
+# endif /* _LF_CAS_H_ */
+
diff --git a/lf_fifo.c b/lf_fifo.c
index ba71847..1f4ab90 100644
--- a/lf_fifo.c
+++ b/lf_fifo.c
@@ -26,86 +26,90 @@
  */
 
 #include "lf_fifo.h"
-#include "lf_fifo_cas.h"
 #include "stdlib.h"
 
+union ptr_u {
+    lf_pointer_t ptr;
+    volatile long long concat;
+};
+
 /* initialize an empty lf_fifo structure */
 void lf_fifo_init( lf_fifo_t *q ) {
-    q->head.split.next = q->tail.split.next = NULL;
-    q->head.split.count = q->tail.split.count = 0;
+    q->head.ptr = q->tail.ptr = NULL;
+    q->head.count = q->tail.count = 0;
 }
 
 /* push a node at the tail of q */
-void lf_fifo_push( lf_fifo_t *q, pointer_t *node ) {
-    pointer_t tail;
-    pointer_t last;
-    pointer_t tmp;
+void lf_fifo_push( lf_fifo_t *q, lf_pointer_t *node ) {
+    lf_pointer_t tail;
+    lf_pointer_t last;
+    lf_pointer_t tmp;
 
     /* init node */
-    node->split.next = NULL;
-    node->split.count = 0;
+    node->ptr = NULL;
+    node->count = 0;
 
     /* set tmp to point to node */
-    tmp.split.next = node;
-    tmp.split.count = 1;
+    tmp.ptr = node;
+    tmp.count = 1;
 
     for(;;) {
         /* snapshot tail */
-        tail.concat = q->tail.concat;
+        tail = q->tail;
         /* nothing in tail link as first node */
-        if ( tail.split.next==NULL && cas( &q->tail.split, tail.split, tmp.split ) ) {                  /* TODO right place ?? */
-            q->head.split.next = node;
-            /* q->head.split.count = 1; ??? */
+        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.concat = (*tail.split.next).concat;
+            last = *tail.ptr;
             /* if tail is still consistant */
-            if (tail.concat == q->tail.concat) {
+            if (((union ptr_u)tail).concat == ((union ptr_u)q->tail).concat) {
                 /* if last is the last node */
-                if (last.split.next == NULL) {
-                    tmp.split.count = last.split.count+1;
-                    if ( cas( &tail.split.next->split, last.split, tmp.split ) ) break;
+                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.split.count = tail.split.count+1;
-                    cas( &q->tail.split, tail.split, last.split );
+                    last.count = tail.count+1;
+                    cas( &q->tail, tail, last );
                 }
             }
         }
     }
     /* try to swing tail to the next node */
-    tmp.split.count = tail.split.count+1;
-    cas( &q->tail.split, tail.split, tmp.split );
+    tmp.count = tail.count+1;
+    cas( &q->tail, tail, tmp );
 }
 
 /* pop a node from the head of q */
-pointer_t* pop( lf_fifo_t *q ) {
-    pointer_t head;
-    pointer_t tail;
-    pointer_t tmp;
-    pointer_t *node;
+lf_pointer_t* pop( lf_fifo_t *q ) {
+    lf_pointer_t head;
+    lf_pointer_t tail;
+    lf_pointer_t tmp;
+    lf_pointer_t *node;
 
     for(;;) {
         /* snapshot head */
-        head.concat = q->head.concat;
+        head = q->head;
         /* return NULL if queue is empty */
-        if (head.split.next == NULL) { return NULL; }                                                   /* TODO before snapshot using q-> ?? */
+        if (head.ptr == NULL) { return NULL; }                      /* TODO before snapshot using q-> ?? */
         /* snapshot tail */
-        tail.concat = q->tail.concat;
+        tail = q->tail;
         /* if there is only one node in the queue */
-        if ( tail.split.next == head.split.next ) {
+        if ( tail.ptr == head.ptr ) {
             /* tail points to NULL */
-            tmp.split.next = NULL;
-            tmp.split.count = tail.split.count+1;
-            cas( &q->tail.split, tail.split, tmp.split );
+            tmp.ptr = NULL;
+            tmp.count = tail.count+1;
+            cas( &q->tail, tail, tmp );
         } else {
             /* get the node ptr */
-            node = (pointer_t *)head.split.next;
+            node = (lf_pointer_t *)head.ptr;
             /* get the next head ready */
-            tmp.split.next = node->split.next;
-            tmp.split.count = head.split.count+1;
-            if ( cas( &q->head.split, head.split, tmp.split ) ) break;
+            tmp.ptr = node->ptr;
+            tmp.count = head.count+1;
+            if ( cas( &q->head, head, tmp ) ) break;
         }
     }
     return node;
diff --git a/lf_fifo.h b/lf_fifo.h
index dc3e87d..cfecee1 100644
--- a/lf_fifo.h
+++ b/lf_fifo.h
@@ -25,6 +25,7 @@
  *
  */
 
+#include "lf_cas.h"
 
 #ifndef _LF_FIFO_H_
 #define _LF_FIFO_H_
@@ -33,27 +34,19 @@
 extern "C" {
 # endif /* __cplusplus */
 
-typedef union pointer {
-    struct split {
-        volatile union pointer *next;
-        volatile unsigned int count;
-    } split;
-    volatile unsigned long long concat;
-} pointer_t;
-
 typedef struct queue {
-    pointer_t head;
-    pointer_t tail;
+    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 );
 
 /* push a node at the tail of q */
-void lf_fifo_push( lf_fifo_t *q, pointer_t *node );
+void lf_fifo_push( lf_fifo_t *q, lf_pointer_t *node );
 
 /* pop a node from the head of q */
-pointer_t* pop( lf_fifo_t *q );
+lf_pointer_t* pop( lf_fifo_t *q );
 
 # ifdef __cplusplus
 }
diff --git a/lf_fifo_test.c b/lf_fifo_test.c
index 9d5a6bc..86898cb 100644
--- a/lf_fifo_test.c
+++ b/lf_fifo_test.c
@@ -30,41 +30,38 @@
 #include "stddef.h"
 
 #include "lf_fifo.h"
-#include "lf_fifo_cas.h"
 
-#define container_of(ptr, type, member) ({			\
-	const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
-	(type *)( (char *)__mptr - offsetof(type,member) );})
+#define container_of(ptr, type, member) ( { (type*)(((char*)ptr)-offsetof(type,member)); } )
 
 struct node {
     int data;
-    pointer_t link;
+    lf_pointer_t link;
 };
 
 int main(int argc, char *argv[]) {
-    pointer_t new;
-    pointer_t old;
-    pointer_t mem;
+    lf_pointer_t new;
+    lf_pointer_t old;
+    lf_pointer_t mem;
     int ret;
 
     lf_fifo_t q;
-    pointer_t *it;
+    lf_pointer_t *it;
     struct node data[10];
     int i;
 
     /* check comprae_and_swap */
-    mem.split.count = 0;
-    old.split.count = 6;
-    new.split.count = 666;
-    mem.split.next = (void*)&argc;
-    old.split.next = (void*)&argc;
-    new.split.next = (void*)&argv;
-    ret = cas(&mem.split, old.split, new.split);
-    printf("ret %d -> (%d,%X)\n", ret, mem.split.count, (unsigned int)mem.split.next);
+    mem.count = 0;
+    old.count = 6;
+    new.count = 666;
+    mem.ptr = (void*)&argc;
+    old.ptr = (void*)&argc;
+    new.ptr = (void*)&argv;
+    ret = cas(&mem, old, new);
+    printf("ret %d -> (%d,%X)\n", ret, mem.count, (unsigned int)mem.ptr);
 
-    mem.split.count=6;
-    ret = cas(&mem.split, old.split, new.split);
-    printf("ret %d -> (%d,%X)\n", ret, mem.split.count, (unsigned int)mem.split.next);
+    mem.count=6;
+    ret = cas(&mem, old, new);
+    printf("ret %d -> (%d,%X)\n", ret, mem.count, (unsigned int)mem.ptr);
 
     /* init data */
     for(i=0; i<10; i++) data[i].data=i;
@@ -75,20 +72,20 @@ int main(int argc, char *argv[]) {
     printf("pop %X\n",(unsigned int)pop( &q ));
     for(i=0; i<10; i++) lf_fifo_push( &q, &data[i].link );
 
-    it = (pointer_t*)q.head.split.next;
+    it = (lf_pointer_t*)q.head.ptr;
     while(it!=NULL) {
         printf("data : %d\n",container_of(it,struct node,link)->data);
-        it = (pointer_t*)it->split.next;
+        it = (lf_pointer_t*)it->ptr;
     }
     
     for(i=0; i<5; i++) {
         it = pop( &q );
         printf("pop %X %d\n",(unsigned int)it,container_of(it,struct node,link)->data);
     }
-    it = (pointer_t*)q.head.split.next;
+    it = (lf_pointer_t*)q.head.ptr;
     while(it!=NULL) {
         printf("data : %d\n",container_of(it,struct node,link)->data);
-        it = (pointer_t*)it->split.next;
+        it = (lf_pointer_t*)it->ptr;
     }
 
     return EXIT_SUCCESS;