diff options
| -rw-r--r-- | lf_fifo.c | 156 | ||||
| -rw-r--r-- | lf_fifo.h | 19 |
2 files changed, 92 insertions, 83 deletions
@@ -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; } @@ -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 } |