From 9c483a02cb2c8d3c67c3cdd1f34630191fa55c1d Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= Date: Sat, 7 Nov 2009 16:59:49 +0100 Subject: lfq goes lf_fifo --- Makefile | 10 ++--- lf_fifo.c | 113 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ lf_fifo.h | 63 ++++++++++++++++++++++++++++++++ lf_fifo_cas.h | 42 +++++++++++++++++++++ lf_fifo_test.c | 95 ++++++++++++++++++++++++++++++++++++++++++++++++ lfq.c | 113 --------------------------------------------------------- lfq.h | 63 -------------------------------- lfq_cas.h | 42 --------------------- lfq_test.c | 95 ------------------------------------------------ 9 files changed, 318 insertions(+), 318 deletions(-) create mode 100644 lf_fifo.c create mode 100644 lf_fifo.h create mode 100644 lf_fifo_cas.h create mode 100644 lf_fifo_test.c delete mode 100644 lfq.c delete mode 100644 lfq.h delete mode 100644 lfq_cas.h delete mode 100644 lfq_test.c diff --git a/Makefile b/Makefile index a196f10..2265400 100644 --- a/Makefile +++ b/Makefile @@ -3,7 +3,7 @@ CC = gcc STD = _GNU_SOURCE CFLAGS = -DDEBUG -BIN = cas_test lock_free_queue_test lfq_test +BIN = cas_test lock_free_queue_test lf_fifo_test .c.o: $(CC) -c -Wall -I. $(CFLAGS) -D$(STD) $< @@ -16,13 +16,13 @@ cas_test: cas_test.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 -lfq.o: lfq.h lfq_cas.h +lf_fifo.o: lf_fifo.h lf_fifo_cas.h -lfq_test: lfq.o lfq_test.o - $(CC) lfq.o lfq_test.o -o lfq_test +lf_fifo_test: lf_fifo.o lf_fifo_test.o + $(CC) lf_fifo.o lf_fifo_test.o -o lf_fifo_test as: - $(CC) -S lfq.c + $(CC) -S lf_fifo.c clean: rm -f *~ *.o *.s core $(BIN) diff --git a/lf_fifo.c b/lf_fifo.c new file mode 100644 index 0000000..f13045f --- /dev/null +++ b/lf_fifo.c @@ -0,0 +1,113 @@ +/* + * File : lfq.c + * Author : Jérémy Zurcher + * Date : 01/11/09 + * License : + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * 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 + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE + * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION + * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION + * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + * + */ + +#include "lf_fifo.h" +#include "lf_fifo_cas.h" +#include "stdlib.h" + +/* 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; +} + +/* push a node at the tail of q */ +void lf_fifo_push_tail( lf_fifo_t *q, pointer_t *node ) { + pointer_t tail; + pointer_t last; + pointer_t tmp; + + /* init node */ + node->split.next = NULL; + node->split.count = 0; + + /* set tmp to point to node */ + tmp.split.next = node; + tmp.split.count = 1; + + for(;;) { + /* snapshot tail */ + tail.concat = q->tail.concat; + /* 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; ??? */ + return; + } else { + /* snapshot last through tail */ + last.concat = (*tail.split.next).concat; + /* if tail is still consistant */ + if (tail.concat == 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; + } else { + /* try to swing tail to the next node */ + last.split.count = tail.split.count+1; + cas( &q->tail.split, tail.split, last.split ); + } + } + } + } + /* try to swing tail to the next node */ + tmp.split.count = tail.split.count+1; + cas( &q->tail.split, tail.split, tmp.split ); +} + +/* pop a node from the head of q */ +pointer_t* pop_head( lf_fifo_t *q ) { + pointer_t head; + pointer_t tail; + pointer_t tmp; + pointer_t *node; + + for(;;) { + /* snapshot head */ + head.concat = q->head.concat; + /* return NULL if queue is empty */ + if (head.split.next == NULL) { return NULL; } /* TODO before snapshot using q-> ?? */ + /* snapshot tail */ + tail.concat = q->tail.concat; + /* if there is only one node in the queue */ + if ( tail.split.next == head.split.next ) { + /* tail points to NULL */ + tmp.split.next = NULL; + tmp.split.count = tail.split.count+1; + cas( &q->tail.split, tail.split, tmp.split ); + } else { + /* get the node ptr */ + node = (pointer_t *)head.split.next; + /* 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; + } + } + return node; +} + diff --git a/lf_fifo.h b/lf_fifo.h new file mode 100644 index 0000000..6cf896c --- /dev/null +++ b/lf_fifo.h @@ -0,0 +1,63 @@ +/* + * File : lf_fifo.h + * Author : Jérémy Zurcher + * Date : 02/11/09 + * License : + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * 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 + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE + * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION + * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION + * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + * + */ + + +#ifndef _LF_FIFO_H_ +#define _LF_FIFO_H_ + +# ifdef __cplusplus +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_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_tail( lf_fifo_t *q, pointer_t *node ); + +/* pop a node from the head of q */ +pointer_t* pop_head( lf_fifo_t *q ); + +# ifdef __cplusplus +} +# endif /* __cplusplus */ + +# endif /* _LF_FIFO_H_ */ + diff --git a/lf_fifo_cas.h b/lf_fifo_cas.h new file mode 100644 index 0000000..e380f8e --- /dev/null +++ b/lf_fifo_cas.h @@ -0,0 +1,42 @@ +/* + * File : lf_fifo_cas.h + * Author : Jérémy Zurcher + * Date : 01/11/09 + * License : + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * 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 + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE + * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION + * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION + * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + * + */ + +#include "lf_fifo.h" + +/* 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 ) { + 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) + : "memory"); + return (int)result; +} + diff --git a/lf_fifo_test.c b/lf_fifo_test.c new file mode 100644 index 0000000..e212197 --- /dev/null +++ b/lf_fifo_test.c @@ -0,0 +1,95 @@ +/* + * File : lf_fifo_test.c + * Author : Jérémy Zurcher + * Date : 01/11/09 + * License : + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * 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 + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE + * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION + * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION + * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + * + */ + +#include "stdio.h" +#include "stdlib.h" +#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) );}) + +struct node { + int data; + pointer_t link; +}; + +int main(int argc, char *argv[]) { + pointer_t new; + pointer_t old; + pointer_t mem; + int ret; + + lf_fifo_t q; + 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.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); + + /* init data */ + for(i=0; i<10; i++) data[i].data=i; + for(i=0; i<10; i++) printf("data[%d] :%d\n",i,data[i].data); + + /* check lf_fifo */ + lf_fifo_init( &q); + printf("pop %X\n",(unsigned int)pop_head( &q )); + for(i=0; i<10; i++) lf_fifo_push_tail( &q, &data[i].link ); + + it = (pointer_t*)q.head.split.next; + while(it!=NULL) { + printf("data : %d\n",container_of(it,struct node,link)->data); + it = (pointer_t*)it->split.next; + } + + for(i=0; i<5; i++) { + it = pop_head( &q ); + printf("pop %X %d\n",(unsigned int)it,container_of(it,struct node,link)->data); + } + it = (pointer_t*)q.head.split.next; + while(it!=NULL) { + printf("data : %d\n",container_of(it,struct node,link)->data); + it = (pointer_t*)it->split.next; + } + + return EXIT_SUCCESS; +} diff --git a/lfq.c b/lfq.c deleted file mode 100644 index 8fa9758..0000000 --- a/lfq.c +++ /dev/null @@ -1,113 +0,0 @@ -/* - * File : lfq.c - * Author : Jérémy Zurcher - * Date : 01/11/09 - * License : - * - * Permission is hereby granted, free of charge, to any person obtaining - * a copy of this software and associated documentation files (the - * "Software"), to deal in the Software without restriction, including - * without limitation the rights to use, copy, modify, merge, publish, - * 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 - * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE - * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION - * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION - * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - * - */ - -#include "lfq.h" -#include "lfq_cas.h" -#include "stdlib.h" - -/* initialize an empty lfq structure */ -void lfq_init( lfq_t *q ) { - q->head.split.next = q->tail.split.next = NULL; - q->head.split.count = q->tail.split.count = 0; -} - -/* push a node at the tail of q */ -void lfq_push_tail( lfq_t *q, pointer_t *node ) { - pointer_t tail; - pointer_t last; - pointer_t tmp; - - /* init node */ - node->split.next = NULL; - node->split.count = 0; - - /* set tmp to point to node */ - tmp.split.next = node; - tmp.split.count = 1; - - for(;;) { - /* snapshot tail */ - tail.concat = q->tail.concat; - /* 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; ??? */ - return; - } else { - /* snapshot last through tail */ - last.concat = (*tail.split.next).concat; - /* if tail is still consistant */ - if (tail.concat == 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; - } else { - /* try to swing tail to the next node */ - last.split.count = tail.split.count+1; - cas( &q->tail.split, tail.split, last.split ); - } - } - } - } - /* try to swing tail to the next node */ - tmp.split.count = tail.split.count+1; - cas( &q->tail.split, tail.split, tmp.split ); -} - -/* pop a node from the head of q */ -pointer_t* pop_head( lfq_t *q ) { - pointer_t head; - pointer_t tail; - pointer_t tmp; - pointer_t *node; - - for(;;) { - /* snapshot head */ - head.concat = q->head.concat; - /* return NULL if queue is empty */ - if (head.split.next == NULL) { return NULL; } /* TODO before snapshot using q-> ?? */ - /* snapshot tail */ - tail.concat = q->tail.concat; - /* if there is only one node in the queue */ - if ( tail.split.next == head.split.next ) { - /* tail points to NULL */ - tmp.split.next = NULL; - tmp.split.count = tail.split.count+1; - cas( &q->tail.split, tail.split, tmp.split ); - } else { - /* get the node ptr */ - node = (pointer_t *)head.split.next; - /* 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; - } - } - return node; -} - diff --git a/lfq.h b/lfq.h deleted file mode 100644 index 3906f9b..0000000 --- a/lfq.h +++ /dev/null @@ -1,63 +0,0 @@ -/* - * File : lfq.h - * Author : Jérémy Zurcher - * Date : 02/11/09 - * License : - * - * Permission is hereby granted, free of charge, to any person obtaining - * a copy of this software and associated documentation files (the - * "Software"), to deal in the Software without restriction, including - * without limitation the rights to use, copy, modify, merge, publish, - * 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 - * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE - * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION - * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION - * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - * - */ - - -#ifndef _LFQ_H_ -#define _LFQ_H_ - -# ifdef __cplusplus -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; -} lfq_t; - -/* initialize an empty lfq structure */ -void lfq_init( lfq_t *q ); - -/* push a node at the tail of q */ -void lfq_push_tail( lfq_t *q, pointer_t *node ); - -/* pop a node from the head of q */ -pointer_t* pop_head( lfq_t *q ); - -# ifdef __cplusplus -} -# endif /* __cplusplus */ - -# endif /* _LFQ_H_ */ - diff --git a/lfq_cas.h b/lfq_cas.h deleted file mode 100644 index a77e1ef..0000000 --- a/lfq_cas.h +++ /dev/null @@ -1,42 +0,0 @@ -/* - * File : lfq_cas.h - * Author : Jérémy Zurcher - * Date : 01/11/09 - * License : - * - * Permission is hereby granted, free of charge, to any person obtaining - * a copy of this software and associated documentation files (the - * "Software"), to deal in the Software without restriction, including - * without limitation the rights to use, copy, modify, merge, publish, - * 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 - * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE - * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION - * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION - * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - * - */ - -#include "lfq.h" - -/* 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 ) { - 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) - : "memory"); - return (int)result; -} - diff --git a/lfq_test.c b/lfq_test.c deleted file mode 100644 index 4223f3f..0000000 --- a/lfq_test.c +++ /dev/null @@ -1,95 +0,0 @@ -/* - * File : lfq_test.c - * Author : Jérémy Zurcher - * Date : 01/11/09 - * License : - * - * Permission is hereby granted, free of charge, to any person obtaining - * a copy of this software and associated documentation files (the - * "Software"), to deal in the Software without restriction, including - * without limitation the rights to use, copy, modify, merge, publish, - * 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 - * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE - * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION - * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION - * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - * - */ - -#include "stdio.h" -#include "stdlib.h" -#include "stddef.h" - -#include "lfq.h" -#include "lfq_cas.h" - -#define container_of(ptr, type, member) ({ \ - const typeof( ((type *)0)->member ) *__mptr = (ptr); \ - (type *)( (char *)__mptr - offsetof(type,member) );}) - -struct node { - int data; - pointer_t link; -}; - -int main(int argc, char *argv[]) { - pointer_t new; - pointer_t old; - pointer_t mem; - int ret; - - lfq_t q; - 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.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); - - /* init data */ - for(i=0; i<10; i++) data[i].data=i; - for(i=0; i<10; i++) printf("data[%d] :%d\n",i,data[i].data); - - /* check lfq */ - lfq_init( &q); - printf("pop %X\n",(unsigned int)pop_head( &q )); - for(i=0; i<10; i++) lfq_push_tail( &q, &data[i].link ); - - it = (pointer_t*)q.head.split.next; - while(it!=NULL) { - printf("data : %d\n",container_of(it,struct node,link)->data); - it = (pointer_t*)it->split.next; - } - - for(i=0; i<5; i++) { - it = pop_head( &q ); - printf("pop %X %d\n",(unsigned int)it,container_of(it,struct node,link)->data); - } - it = (pointer_t*)q.head.split.next; - while(it!=NULL) { - printf("data : %d\n",container_of(it,struct node,link)->data); - it = (pointer_t*)it->split.next; - } - - return EXIT_SUCCESS; -} -- cgit v1.1-2-g2b99