链式队列

链式队列–使用链表模拟实现队列先进先出，主要由一个一个数据节点连接而成。下面代码封装了两种模式队列
一、更具入队出队改变队列长度，动态分配内存，以及节点内存大小也是动态更具需要分配
二、初始化为定长，节点空间固定大小，连接成环形队列。

图解两种模式队列

• 动态分配内存
• 固定内存环形队列

• queue.h
• queue.c

#ifndef __QUEUE_PUBLIC_H__
#define __QUEUE_PUBLIC_H__
#include <pthread.h>

typedef unsigned char  Type;

//链表节点
typedef struct Node
{
	Type* buff;
	size_t len;
	struct Node* next;
}Node;

//链表
typedef struct QueueList
{
	pthread_mutex_t mutex_lock;		//互斥锁防止同时出队，和入队活着一个出队一个入队时出现不同步
	size_t res;					//记录链表节点总个数
	size_t size;				//记录每个节点buff空间大小
	Node* head;		
	Node* tail;
}QueueList;

//初始化链式队列
int queuelist_init(QueueList** queue,int len,int size);
//创建节点
Node* node_create(QueueList* queue,Type* buff,int len);
//队列为空
int is_qempty(QueueList* queue);
//队列满
int is_qfull(QueueList* queue);
//队列字符串个数
int queuelist_num(QueueList* queue);
//入队(尾添加)
int Push_QueueList(QueueList* queue,Type* buff,int len);
//出队(头删除)
int Pop_QueueList(QueueList* queue,Type* buff,int len);
//清空队列中数据
void clean_queuelist(QueueList* queue,int len);
//销毁队列
int destroy_queuelist(QueueList** queue);

#endif

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <string.h>
#include "queue.h"



//初始化链式队列，len，size 都为0创建变长队列，都不为0创建len长度，每个size大小的队列
int queuelist_init(QueueList** queue,int len,int size)
{
	if((0 == len && 0 == size) || (0 < len && 0 < size))
	{		
		*queue = (QueueList*)malloc(sizeof(QueueList));
		if(NULL == *queue)
		{
			perror("failed while malloc <queuelist>");
			return -1;
		}
	int ret = pthread_mutex_init(&(*queue)->mutex_lock,NULL);
	if(ret)
	{
		printf("failed while MutexCreate\n");
		free(*queue);
		queue = NULL;
		return -1;
	}
		(*queue)->head = NULL;
		(*queue)->tail = NULL;
		(*queue)->res = 0;
		if(0 == len && 0 == size)
		{
			(*queue)->size =0;
			return 0;
		}

		(*queue)->size = size;
		for(int i = 0;i < len;i++)
		{
			Node* node = node_create(*queue,NULL,0);
			if(node == NULL)
			{
				return -1;
			}
			if(NULL == (*queue)->head && NULL == (*queue)->tail)
			{
				(*queue)->head = node;
				(*queue)->tail = node;
			}
			(*queue)->tail->next = node;
			(*queue)->tail = node;
			
		}
		(*queue)->tail->next = (*queue)->head;
		(*queue)->tail = (*queue)->head;
		return 0;
	}
	return -1;	
}

//创建节点 size == 0创建buff长度的节点，size> 0创建size长度的节点
Node* node_create(QueueList* queue,Type* buff,int len)
{

	Node* node = (Node*)malloc(sizeof(Node));
	if(NULL == node)
	{
		perror("failed while malloc <node>\n");
		return node;
	}

	node->buff =  (0 == queue->size) ? (Type*)malloc(len) : (Type*)malloc(queue->size);
	node->next = NULL;
	node->len = len;
	if(queue->size > 0)
	{
		bzero(node->buff,queue->size);
		return node;
	}

	memcpy(node->buff,buff,len);
	return node;
}

//队列为空
int is_qempty(QueueList* queue)
{
	if(NULL == queue)
	{
//		perror("queue is NULLL\n");
		return -1;
	}

	if(queue->res == 0)
	{
		return 1;
	}
	
	return 0;
}

//队列满
int is_qfull(QueueList* queue)
{
	if(NULL == queue)
	{
		printf("queue is NULL\n");
		return -1;
	}
	
	if(queue->size == 0)
	{
		printf("queue type error\n");
		return -1;
	}
	
	if(queue->res > 0 && queue->size > 0 && queue->head == queue->tail )
	{
		return 1;
	}
	return 0;
}

//队列字符串个数
int queuelist_num(QueueList* queue)
{
	if(NULL == queue)
	{
		perror("queue is NULL");
		return -1;
	}
	return queue->res;
}

//入队(尾添加)
int Push_QueueList(QueueList* queue,Type* buff,int len)
{
	pthread_mutex_lock(&queue->mutex_lock);
	if(NULL == queue)
	{
		perror("push fail,queue is NULL");
		pthread_mutex_unlock(&queue->mutex_lock);
		return -2;
	} 
	if(NULL == buff)
	{
		perror("push fail,buff is NULL");
		pthread_mutex_unlock(&queue->mutex_lock);
		return -1;
	}
	
	if(0 == queue->size)
	{
		Node* node = NULL;
		node = node_create(queue,buff,len);
		if(NULL == node)
		{
			pthread_mutex_unlock(&queue->mutex_lock);
			return -1;
		}
	
		if(NULL == queue->head)
		{
			queue->head = node;
			queue->tail = node;
			queue->res++;
			pthread_mutex_unlock(&queue->mutex_lock);
			return len;
		}
	
		queue->tail->next = node;
		queue->tail = node;
	}
	else
	{
		if(1 == is_qfull(queue))
		{
			printf("queue full\n");
			pthread_mutex_unlock(&queue->mutex_lock);
			return -1;
		}
		if(len > queue->size)
		{
			printf("buff too larger!\n");
			return -1;
		}
		memcpy(queue->tail->buff,buff,len);
		queue->tail->len = len;
		queue->tail=queue->tail->next;
	}
	queue->res++;
	pthread_mutex_unlock(&queue->mutex_lock);
	return len;
}

//出队(头删除)
int Pop_QueueList(QueueList* queue,Type* buff,int len)
{
	pthread_mutex_lock(&queue->mutex_lock);
	if(NULL == queue)
	{
		perror("pop fail,queue is NULL");
		pthread_mutex_unlock(&queue->mutex_lock);
		return -2;
	}
	
	if(1 == is_qempty(queue))
	{
		perror("pop fail,queue is empty");
		pthread_mutex_unlock(&queue->mutex_lock);
		return -1;
	}

	if(queue->head->len > len)
	{
		printf("buff is too samll!\n");
		pthread_mutex_unlock(&queue->mutex_lock);
		return -1;
	}

	int size=queue->head->len;
	memcpy(buff,queue->head->buff,queue->head->len);
	memset(queue->head->buff,0x0,queue->size);
	Node* node = queue->head;
	queue->head->len = 0;
	queue->head = queue->head->next;
	queue->res--;
	if(queue->size > 0)
	{
		pthread_mutex_unlock(&queue->mutex_lock);
		return size;
	}
	if(0 == queue->res) 
	{
		queue->tail=NULL;
	}
	free(node->buff);
	free(node);
    pthread_mutex_unlock(&queue->mutex_lock);
	return size;

}

void clean_queuelist(QueueList* queue,int len)
{
	Type buff[len];
	while(!is_qempty(queue))
	{
		Pop_QueueList(queue,buff,len);
	}
}

//销毁队列
int destroy_queuelist(QueueList** queue)
{
	pthread_mutex_lock(&(*queue)->mutex_lock);
	if(NULL == *queue)
	{
		pthread_mutex_unlock(&(*queue)->mutex_lock);
		return -1;
	}
	Node* head_node = (*queue)->head;
	for(Node* node = (*queue)->head;node != NULL && (*queue)->size == 0;)
	{
		Node* temp = node;
		node = node->next;
		free(temp->buff);
		free(temp);
		(*queue)->res--;
	}
	for(Node* node = (*queue)->head;(*queue)->size > 0;)
	{
		Node* temp = node;
		node = node->next;
		free(temp->buff);
		free(temp);
		(*queue)->res--;
		if(head_node == node) break;
	}
	free(*queue);
	(*queue) = NULL;
	pthread_mutex_unlock(&(*queue)->mutex_lock);
	return 0;
}