无锁队列--基于linuxkfifo实现

一直想写个无锁的队列，来提高项目后台的效率。

偶然看到linux内核的kfifo.h 实现原理。于是自己仿照了这个实现，目前linux应该是可以对外提供接口了。

#ifndef _NO_LOCK_QUEUE_H_
#define _NO_LOCK_QUEUE_H_

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <string>
#include <pthread.h>
#include <iostream>
using namespace  std;

#ifndef max
#define max(x, y) ({					typeof(x) _max1 = (x);				typeof(y) _max2 = (y);				(void) (&_max1 == &_max2);			_max1 > _max2 ? _max1 : _max2; })
#endif

#ifndef min
#define min(x, y) ({					typeof(x) _min1 = (x);				typeof(y) _min2 = (y);				(void) (&_min1 == &_min2);			_min1 < _min2 ? _min1 : _min2; })
#endif

class Kfifo 
{
public:
	Kfifo(unsigned int  isize);
	~Kfifo();
	unsigned int get(unsigned char *buffer, unsigned int len);
	unsigned int put(const unsigned char *buffer, unsigned int len);
	static unsigned long roundup_power_of_two(unsigned long val);
private:
	inline bool is_power_of_2(unsigned long n)
	{
		return (n != 0 && ((n & (n - 1)) == 0)); 
	};
	inline unsigned int unused()
	{
		return (mask + 1) - (in - out);
	}
	
private:
	unsigned int size;
	unsigned int in; 
	unsigned int out;
	unsigned int	mask;
	unsigned char* buffer;
};

struct proto
{
	unsigned int msgid;
	unsigned int cmd;
	unsigned int info;
	proto():msgid(0),cmd(0),info(0){}
};

#endif

#include "MKfifo.h"

Kfifo::~Kfifo()
{
	if (buffer) free(buffer);	
	size = in = out=0;
}
unsigned long Kfifo::roundup_power_of_two(unsigned long val)
{
	if (val & (val-1) == 0)
	{
		return val;
	}
	unsigned long maxulong = (unsigned long )((unsigned long ) ~0);
	unsigned long andv = ~(maxulong&(maxulong>>1));
	while((andv & val) == 0)
	andv = andv>>1;
	return andv<<1;
}
Kfifo::Kfifo(unsigned int isize):size(isize),in(0),out(0),mask(size - 1)
{
	if (!is_power_of_2(isize))
	{
		size = roundup_power_of_two(isize);
	}
	buffer =(unsigned char*) malloc(isize);
}

unsigned int Kfifo::get(unsigned char *_buffer, unsigned int len)
{
	unsigned int l;
	len = min(len, in - out);
	__sync_synchronize();

	l = min(len,size -(out&(size-1)));
	memcpy(_buffer,buffer + (out& (size-1)),l);
	memcpy(_buffer + l,buffer,len - l);

	 __sync_synchronize();

	 out +=len;
	 return len;

}
unsigned int Kfifo::put(const unsigned char *_buffer, unsigned int len)
{
	unsigned int l;
	len = min(len, size - in + out);
	 __sync_synchronize();
	 l = min(len, size - (in & (size - 1)));
	 memcpy(buffer + (in & (size - 1)), _buffer, l);
	 memcpy(buffer, _buffer + l, len - l);
	  __sync_synchronize();
	   in += len;
	   return len;

}

void * consumer(void * arg)
{
	printf("consumer\n");
	Kfifo* fifo = (Kfifo*) arg;
	if (!fifo)
	{
		return NULL;
	}

	for (;;)
	{
		proto p;
		unsigned int len = fifo->get((unsigned char*)&p,sizeof(p));
		if (len>0)
		{
			cout << "~~~~~~~~~~~~~~~~~~~~"<<endl;
			cout << "consumer proto msg id :"<<p.msgid<<endl;
			cout << "consumer proto msg cmd :"<<p.cmd<<endl;
			cout << "consumer proto msg info :"<<p.info<<endl;
			cout << "~~~~~~~~~~~~~~~~~~~~"<<endl;
		}
	}

	
	return (void *)fifo;
}
void* producer(void* args)
{
	Kfifo* fifo = (Kfifo*) args;
	
	if (!fifo)
	{
		return NULL;
	}
	unsigned int i=0;
	for (;;)
	{
		proto p;
		p.msgid = i++;
		p.cmd =  333;
		p.info = 44444;
		fifo->put((const unsigned char*)&p,sizeof(p));
		cout<<"producer put msgid :"<<p.msgid<<endl;
	}
	return (void*)fifo;
}
int main()
{
	Kfifo *fifo = new Kfifo(1024);
	pthread_t consumeid,producerid;
	pthread_create(&producerid,NULL,producer,(void*)fifo);
	pthread_create(&consumeid,NULL,consumer,(void*)fifo);

	printf("info!!\n");
	pthread_join(consumeid,NULL);
	pthread_join(producerid,NULL);
	return 0;
}

经过测试是可用的，我将在该队列的基础上，丰富其使用。