[PD-cvs] pd/src m_fifo.h,NONE,1.1.2.1 m_fifo.c,NONE,1.1.2.1

[Tim Blechmann]

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