Update of /cvsroot/pure-data/pd/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv10276
Added Files: Tag: devel_0_38 m_fifo.h m_fifo.c Log Message: added fifo api ... lockfree at least on gcc / x86
--- NEW FILE: m_fifo.h --- /* Copyright (c) 2004, Tim Blechmann * For information on usage and redistribution, and for a DISCLAIMER OF ALL * WARRANTIES, see the file, "LICENSE.txt" in this distribution. */
#include "m_pd.h"
/* possibly this can go to m_pd.h */
/* used data structures */ EXTERN_STRUCT _fifo; #define t_fifo struct _fifo
/* function prototypes */ t_fifo * fifo_init(); void fifo_destroy(t_fifo*);
/* fifo_put() and fifo_get are the only threadsafe functions!!! */ void fifo_put(t_fifo*, void*); void* fifo_get(t_fifo*);
--- NEW FILE: m_fifo.c --- /* Copyright (c) 2004, Tim Blechmann * For information on usage and redistribution, and for a DISCLAIMER OF ALL * WARRANTIES, see the file, "LICENSE.txt" in this distribution. */
#include "stddef.h"
#include "m_pd.h" #include "m_fifo.h"
typedef struct _fifocell { void* data; /* pointer to our data */ struct _fifocell* next; } t_fifocell;
#ifdef LOCKFREE
/* lock-free fifo implementation adapted from: * Dominique Fober, Yann Orlarey, Stephane Letz * Lock-Free Techniques for Concurrent Access to Shared Objects */
/* for gcc on i386 */ #if defined(__GNUC__) && (defined(_X86_) || defined(__i386__) || defined(__i586__) || defined(__i686__))
#define CAS(mem, old, new) \ ({ __asm__ __volatile__( \ "lock cmpxchg %2,%0 \n" \ : : \ "m" (mem), "a" (old), "r" (new) ); \ old != (__typeof__(old))(mem); \ })
#define CAS2(mem, old1, old2, new1, new2) \ ({ __asm__ __volatile__( \ "lock cmpxchg8b %0 \n" \ : : \ "m" (mem), "a" (old1), "d" (old2), \ "b" (new1), "c"(new2)); \ old1 != (__typeof__(old1)) (mem); \ })
#else
#error Lockfree Fifo not yet implemented on this platform
#endif
struct _fifo { t_fifocell* head; unsigned long ocount; /* operation counter */ t_fifocell* tail; unsigned long icount; /* operation counter */ };
t_fifo* fifo_init() { t_fifo* ret = (t_fifo*) getbytes(sizeof(t_fifo)); t_fifocell * fifo_begin = (t_fifocell*) getbytes (sizeof (t_fifocell) );
fifo_begin->data = NULL; fifo_begin->next = NULL; ret->head = fifo_begin; ret->tail = fifo_begin; ret->icount = 0; ret->ocount = 0;
return ret; }
void fifo_destroy(t_fifo* fifo) { void * data;
do { data = fifo_get(fifo); } while (data != NULL);
freebytes(fifo->head, sizeof(t_fifocell)); freebytes(fifo, sizeof(t_fifo)); return; }
void fifo_put(t_fifo* fifo, void* data) { if (data != NULL) { t_fifocell * cell = (t_fifocell*) getbytes(sizeof(t_fifocell)); t_fifocell * tail; unsigned long icount; cell->data = data; cell->next = NULL; while(1) { icount = fifo->icount; tail = fifo->tail;
if (CAS(tail->next, NULL, cell)) break; else CAS2(fifo->tail, tail, icount, tail->next, icount + 1); } CAS2(fifo->tail, tail, icount, cell, icount +1); return; } else error("invalid data: NULL"); }
void* fifo_get(t_fifo* fifo) { t_fifocell * head; void* data; while (1) { unsigned long ocount = fifo->ocount; unsigned long icount = fifo->icount; t_fifocell * next;
head = fifo->head; next = head->next; if (ocount == fifo->ocount) { if (head == fifo->tail) { if (next == NULL) return NULL; CAS2(fifo->tail, head, icount, next, icount + 1); } else { data = next->data; if (CAS2(fifo->head, head, ocount, next, ocount+1)) break; } } }
freebytes(head, sizeof(t_fifocell)); return data; }
#else
/* we always have the implementation for posix systems with threadlocks */
#include "pthread.h" #include "errno.h"
struct _fifo { t_fifocell * head; t_fifocell * tail; pthread_mutex_t mutex; };
t_fifo * fifo_init() { t_fifo* ret = (t_fifo*) getbytes(sizeof (t_fifo)); t_fifocell * fifo_begin = (t_fifocell*) getbytes (sizeof (t_fifocell) ); fifo_begin->data = NULL; fifo_begin->next = NULL;
ret->head = fifo_begin; ret->tail = fifo_begin; pthread_mutex_init(&ret->mutex, NULL); pthread_mutex_unlock(&ret->mutex);
return ret; }
void fifo_destroy(t_fifo* fifo) { void * data; do { data = fifo_get(fifo); } while (data != NULL);
pthread_mutex_lock(&fifo->mutex); pthread_mutex_destroy(&fifo->mutex); freebytes(fifo, sizeof(t_fifo)); return; }
/* fifo_put() and fifo_get are the only threadsafe functions!!! */ void fifo_put(t_fifo* fifo, void* data) { if (data != NULL) { t_fifocell * cell = (t_fifocell*) getbytes(sizeof(t_fifocell)); cell->data = data; cell->next = NULL; pthread_mutex_lock(&fifo->mutex); fifo->tail->next = cell; fifo->tail = cell; pthread_mutex_unlock(&fifo->mutex); } return; }
/* this fifo_get returns NULL if the fifo is empty * or locked by another thread */ void* fifo_get(t_fifo* fifo) { t_fifocell * cell; void* data; if(pthread_mutex_trylock(&fifo->mutex) != EBUSY) { cell = fifo->head->next;
if (cell != NULL) { fifo->head->next = cell->next; if(cell == fifo->tail) fifo->tail = fifo->head; data = cell->data; freebytes (cell, sizeof(t_fifocell)); } else data = NULL;
pthread_mutex_unlock(&fifo->mutex); } else data = NULL; return data; } #endif