diff options
Diffstat (limited to 'lfq.c')
| -rw-r--r-- | lfq.c | 113 |
1 files changed, 113 insertions, 0 deletions
@@ -0,0 +1,113 @@ +/* + * File : lfq.c + * Author : Jérémy Zurcher <jeremy@asynk.ch> + * 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( 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 ); +} + +/* shift a node from the head of q */ +pointer_t* shift( 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; +} + |