本文共 5443 字,大约阅读时间需要 18 分钟。
根据上面链接所说的原理实现的单生产者,单消费者无锁队列
bool __sync_bool_compare_and_swap (type *ptr, type oldval,type newval, ...)
函数提供原子的比较和交换,如果*ptr == oldval,就将newval写入*ptr。队列头文件
/* * * Copyright (c) * * All rights reserved. * * * * 文件名称:queue.h * * 文件标识:无 * * 摘要:单生产者,单消费者无锁队列实现头文件 * * * * 当前版本:1.0 * * 作者:lishaozhe * * 完成日期:2014年6月14日 * * * * 取代版本: * * 原作者: * * 完成日期: * **/#ifdef QUEUE_H#else#define QUEUE_H#include#include #include "z_types.h"typedef struct queue_node_s{ char *data; struct queue_node_s *next; }queue_node_s, *queue_node_p; typedef struct { queue_node_p head,rear; /* 队头、队尾指针 */ }link_queue_s, *link_queue_p; /* 链队列的基本操作(9个) */ link_queue_p init_queue(void); /* 销毁队列Q(无论空否均可) */ void destroy_queue(link_queue_p queue); /* 将Q清为空队列 */ void clear_queue(link_queue_p queue); /* 若Q为空队列,则返回TRUE,否则返回FALSE */ int queue_empty(link_queue_p queue); /* 求队列的长度 */ int queue_length(link_queue_p queue); /* 插入元素e为Q的新的队尾元素 */ int en_queue(link_queue_p queue, char *buf); /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */ void * de_queue(link_queue_p queue); #endif
队列实现文件
/* * * Copyright (c) * * All rights reserved. * * * * 文件名称:queue.c * * 文件标识:无 * * 摘要:单生产者,单消费者无锁队列实现 * * * * 当前版本:1.0 * * 作者:lishaozhe * * 完成日期:2014年6月14日 * * * * 取代版本: * * 原作者: * * 完成日期: * **/#include "queue.h" link_queue_p init_queue(void) { /* 构造一个空队列Q */ printf("**************init_queue\n"); link_queue_p queue; queue_node_p node; queue = (link_queue_p)malloc(sizeof(link_queue_s)); if(NULL == queue) return NULL; node = (queue_node_p)malloc(sizeof(queue_node_s)); if(NULL == node) { free(queue); return NULL; } node->next = NULL; node->data = NULL; queue->head = queue->rear = node; return queue; } void destroy_queue(link_queue_p queue) { /* 销毁队列Q(无论空否均可) */ queue_node_p node; queue_node_p tmp = NULL; if (NULL == queue) return; node = queue->head->next; while(node) { tmp = node; node = node->next; free(tmp); } free(queue->head); queue->head = queue->rear=NULL; free(queue);} void clear_queue(link_queue_p queue) { /* 将Q清为空队列 */ queue_node_p node; queue_node_p tmp = NULL; if (NULL == queue) return; node = queue->head->next; while(node) { tmp = node; node = node->next; free(tmp); } queue->rear = queue->head; } int queue_empty(link_queue_p queue) { /* 若Q为空队列,则返回TRUE,否则返回FALSE */ if (NULL == queue) return FAILURE; if(queue->head->next == NULL) return TRUE; else return FALSE; } int queue_length(link_queue_p queue) { /* 求队列的长度 */ int i = 0; if (NULL == queue) return FAILURE; queue_node_p node = queue->head; while(node != queue->rear) { i++; node = node->next; } return i; } int en_queue(link_queue_p queue, char *buf) { /* 插入元素e为Q的新的队尾元素 */ queue_node_p tmp, oldp; int retry = 0; queue_node_p node = (queue_node_p)malloc(sizeof(queue_node_s)); if(NULL == node) /* 存储分配失败 */ { return FAILURE; } node->data = buf; node->next = NULL; tmp = queue->rear; oldp = tmp; do { if (retry > 3) { while (tmp->next != NULL) { tmp = tmp->next; } } retry++; } while( __sync_bool_compare_and_swap(&(tmp->next), NULL, node) != TRUE); //如果没有把结点链上,再试 __sync_bool_compare_and_swap(&(queue->rear), oldp, node); //置尾结点 return SUCCESS; } void * de_queue(link_queue_p queue) { /* 若队列不空,删除Q的队头元素,成功返回其值,失败返回NULL */ queue_node_p node; void * tmp = NULL; do{ node = queue->head->next; if (node == NULL) { return NULL; } }while( __sync_bool_compare_and_swap(&(queue->head->next), node, node->next) != TRUE); tmp = node->data; free(node); return tmp;}
类型头文件
/* * * Copyright (c) * * All rights reserved. * * * * 文件名称:z_types.h * * 文件标识:无 * * 摘要:类型定义头文件 * * * * 当前版本:1.0 * * 作者:lishaozhe * * 完成日期:2014年6月14日 * * * * 取代版本: * * 原作者: * * 完成日期: * **/#ifndef __Z_TYPES_H__#define __Z_TYPES_H__#includetypedef enum { FALSE = 0, TRUE = 1 } Bool;typedef unsigned char u8;typedef unsigned short u16;typedef unsigned int u32;typedef unsigned char uint8_t;typedef unsigned short int uint16_t;typedef unsigned int uint32_t;typedef unsigned char unchar;typedef unsigned short ushort;typedef unsigned int uint;typedef signed char int8_t;typedef short int int16_t;typedef int int32_t;/*typedef unsigned long u64;typedef unsigned long long u64;*/#define SUCCESS 0#define FAILURE -1#endif /* _Z_TYPES_H */
简单示例
#include#include "queue.h"int main(){ char buf[] = "One swallow does not make a summer."; char *tmp; link_queue_p queue; queue = init_queue(); printf("******************\n"); en_queue(queue, buf); printf("len = %d\n",queue_length(queue)); tmp = de_queue(queue); if (tmp) printf("tmp = %s\n", tmp); else printf("tmp = NULL\n"); printf("*********over*********\n"); destroy_queue(queue); return 1;}
Makefile
CFLAGS = -O2 -DHAVE_PF_RING -Wall -DDEBUG_POOL -D KK_DEBUG CC = gcc test:test.o queue.o ${CC} ${CFLAGS} test.o queue.o -o $@ test.o: $(CC) -c test.c queue.o: $(CC) -c queue.c clean: rm -rf *.o