登录
当前位置： 首页 > 工具软件 > AMPS > 使用案例 >

AMPS:队列源码解读

胡玉书
2023-12-01

  队列概念很简单，就是排队，先进先出，通常有链表形式和数组形式（即链接类型和顺序类型），它也是软件构建的一个基本数据结构，看看AMPS中的队列实现。

 AMPS_Queue.h

#ifndef __HEADER_AMPS_QUEUE_H
#define __HEADER_AMPS_QUEUE_H

#ifdef __cplusplus
extern "C" {
#endif

#include "AMPS_Defines.h"
#include "AMPS_LinkList.h"

typedef struct _AMPSListBasedQueue		t_AMPSListBasedQueue;
typedef struct _AMPSArrayBasedQueue		t_AMPSArrayBasedQueue;

/*链表形式的队列*/
struct _AMPSListBasedQueue
{
    int 			unCount;      /*队列结点个数*/
    t_AMPSSList* 		poQueueHead;  /*队列头指针*/
    t_AMPSSList* 		poQueueTail;  /*队列尾指针*/
};

int Queue_EnQueueListBasedData(void* r_pvAMPSContext, void* r_pvAMPSListBasedQueue, void* r_pvDataToEnQueue);
int Queue_EnQueueListBasedDataAtHead(void* r_pvAMPSContext, void* r_pvAMPSListBasedQueue, 
                                     void* r_pvDataToEnQueue);
void* Queue_DeQueueListBasedData(void* r_pvAMPSContext, void* r_pvAMPSListBasedQueue);
int Queue_GetListBasedQueueLength(void* r_pvAMPSContext, void* r_pvAMPSListBasedQueue);

/*数组形式的队列*/
struct _AMPSArrayBasedQueue
{
	int				nSizeOfQueue; /*队列总大小*/
    int 			unCount;      /*当前结点个数*/
    unsigned char**	ppuchQueue;   /*队列结点内容(可看做一个长度为nSizeOfQueue,内容为char*的数组)*/

	int				nHeadIndex;   /*队列头下标*/
	int				nTailIndex;   /*队列尾下标*/
};

int Queue_EnQueueArrayBasedInit(void* r_pvAMPSContext, void* r_pvAMPSListBasedQueue, int r_nSizeOfQueue);
void Queue_EnQueueArrayBasedCleanup(void* r_pvAMPSContext, void* r_pvAMPSListBasedQueue);
int Queue_EnQueueArrayBasedData(void* r_pvAMPSContext, void* r_pvAMPSArrayBasedQueue, void* r_pvDataToEnQueue);
void* Queue_DeQueueArrayBasedData(void* r_pvAMPSContext, void* r_pvAMPSArrayBasedQueue);
int Queue_GetArrayBasedQueueLength(void* r_pvAMPSContext, void* r_pvAMPSArrayBasedQueue);


#ifdef __cplusplus
}
#endif

#endif //__HEADER_AMPS_QUEUE_H

AMPS_Queue.c

/*****************************************************************
文件名称: AMPS_Queue.c
功能描述: 队列操作函数(包括链表类型队列和数据类型队列)
备注:     通常的队列是队头删除，队尾插入(这个函数库的实现刚好相反)
*****************************************************************/

#include "AMPS_Core.h"
#include "AMPS_Defines.h"
#include "AMPS_MemMgt.h"
#include "AMPS_Queue.h"
#include "AMPS_LinkList.h"

/*****************************************************************
函数名称: Queue_EnQueueListBasedData
功能描述: 向队列中写数据(链表类型队列) 队头插入
入参::
      void* r_pvAMPSContext AMPS应用上下文数据结构
      void* r_pvAMPSListBasedQueue 待写入的队列
      void* r_pvDataToEnQueue      待写入队列的数据

出参:
     --
返回值:
      int

*****************************************************************/
int Queue_EnQueueListBasedData(void* r_pvAMPSContext, void* r_pvAMPSListBasedQueue, void* r_pvDataToEnQueue)
{
	t_AMPSListBasedQueue* poAMPSListBasedQueue = r_pvAMPSListBasedQueue;

	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    /*向队列中添加结点，前向插入，即向队头插入*/
	if (NULL == SList_Prepend(&poAMPSListBasedQueue->poQueueHead, r_pvDataToEnQueue))
	{
		TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_ERROR, "SList_Prepend is failed.\n");
		return AMPS_ERROR_FAILURE;
	}

    /*在写入前，如果队列为空，队尾与队头指向同一位置*/
	if (0 == poAMPSListBasedQueue->unCount)
	{
		TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_DEBUG_2, "Set Tail to Head.\n");
		poAMPSListBasedQueue->poQueueTail = poAMPSListBasedQueue->poQueueHead;
	}

    /*队列中元素个数加1*/
	poAMPSListBasedQueue->unCount++;

	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");
	return AMPS_SUCCESS;
}

/*****************************************************************
函数名称: Queue_EnQueueListBasedData
功能描述: 向队列中写数据(链表类型队列)，队尾插入
入参::
      void* r_pvAMPSContext AMPS应用上下文数据结构
      void* r_pvAMPSListBasedQueue 待写入的队列
      void* r_pvDataToEnQueue      待写入队列的数据

出参:
     --
返回值:
      int

*****************************************************************/
int Queue_EnQueueListBasedDataAtHead(void* r_pvAMPSContext, void* r_pvAMPSListBasedQueue, void* r_pvDataToEnQueue)
{
	t_AMPSListBasedQueue* poAMPSListBasedQueue = r_pvAMPSListBasedQueue;
	t_AMPSSList* poSList = NULL;

	TRACE(QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    /*向队头追加结点*/
	poSList = SList_AppendEx(&poAMPSListBasedQueue->poQueueHead, r_pvDataToEnQueue);
	if(NULL == poSList)
	{
		TRACE(QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_ERROR, "SList_Prepend is failed.\n");
		return AMPS_ERROR_FAILURE;
	}

	if(0 == poAMPSListBasedQueue->unCount)
	{
		TRACE(QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_DEBUG_2, "Set Tail to Head.\n");
		poAMPSListBasedQueue->poQueueTail = poAMPSListBasedQueue->poQueueHead;
	}
	else
	{
        /*将队尾指向当前结点位置，即队头指向链表首结点，队尾指向链表尾结点*/
		poAMPSListBasedQueue->poQueueTail = poSList;
	}

	poAMPSListBasedQueue->unCount++;

	TRACE(QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");
	return AMPS_SUCCESS;
}

/*****************************************************************
函数名称: Queue_DeQueueListBasedData
功能描述: 队尾结点出队列(链表类型队列)
入参::
      void* r_pvAMPSContext AMPS应用上下文数据结构
      void* r_pvAMPSListBasedQueue 待操作的队列

出参:
     --
返回值:
      void* 队尾结点内容

*****************************************************************/
void* Queue_DeQueueListBasedData(void* r_pvAMPSContext, void* r_pvAMPSListBasedQueue)
{
	t_AMPSListBasedQueue* poAMPSListBasedQueue = r_pvAMPSListBasedQueue;
	t_AMPSSList* poSList = NULL;
	void* pvQueueData = NULL;

	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

	if (NULL == poAMPSListBasedQueue->poQueueTail || 0 == poAMPSListBasedQueue->unCount)
	{
		TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_DEBUG, "Queue is empty.\n");
		return NULL;
	}

    /*删除队尾结点*/
	poSList = poAMPSListBasedQueue->poQueueTail->poAMPSSListPrev;
	pvQueueData = poAMPSListBasedQueue->poQueueTail->pvData;

	if (AMPS_SUCCESS != SList_Remove(&poAMPSListBasedQueue->poQueueHead, poAMPSListBasedQueue->poQueueTail, NULL))
	{
		TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_ERROR, "SList_Remove is failed\n");
		return NULL;	
	}

	poAMPSListBasedQueue->poQueueTail = poSList;
	poAMPSListBasedQueue->unCount--;

    /*返回已删除的队尾结点的内容*/
	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");
	return pvQueueData;
}

/*****************************************************************
函数名称: Queue_DeQueueListBasedData
功能描述: 获取队列长度(链表类型队列)
入参::
      void* r_pvAMPSContext AMPS应用上下文数据结构
      void* r_pvAMPSListBasedQueue 待操作的队列

出参:
     --
返回值:
      int 队列长度

*****************************************************************/
int Queue_GetListBasedQueueLength(void* r_pvAMPSContext, void* r_pvAMPSListBasedQueue)
{
	t_AMPSListBasedQueue* poAMPSListBasedQueue = r_pvAMPSListBasedQueue;
    return (poAMPSListBasedQueue->unCount);
}


/*****************************************************************
函数名称: Queue_EnQueueArrayBasedInit
功能描述: 队列初始化(数组类型队列)
入参::
      void* r_pvAMPSContext AMPS应用上下文数据结构
      void* r_pvAMPSArrayBasedQueue 待操作的队列
      int r_nSizeOfQueue 队列总大小

出参:
     --
返回值:
      int 

*****************************************************************/
int Queue_EnQueueArrayBasedInit(void* r_pvAMPSContext, void* r_pvAMPSArrayBasedQueue, int r_nSizeOfQueue)
{
	t_AMPSArrayBasedQueue* poAMPSArrayBasedQueue = r_pvAMPSArrayBasedQueue;

	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    /*由于队列中存放结点内容的成员为char 
    **，所以需要在初始化时预先分配好内存，在队列销毁时释放*/
	poAMPSArrayBasedQueue->ppuchQueue = AMPS_InternalMalloc(sizeof(char*) * r_nSizeOfQueue);
	if (NULL == poAMPSArrayBasedQueue->ppuchQueue)
	{
		TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_ERROR, "AMPS_InternalMalloc failed for poAMPSArrayBasedQueue->poQueue.\n");
		return AMPS_ERROR_FAILURE;
	}

	poAMPSArrayBasedQueue->unCount = 0;
	poAMPSArrayBasedQueue->nHeadIndex = 0;
	poAMPSArrayBasedQueue->nTailIndex = 0;
	poAMPSArrayBasedQueue->nSizeOfQueue = r_nSizeOfQueue;

	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");
	return AMPS_SUCCESS;
}

/*****************************************************************
函数名称: Queue_EnQueueArrayBasedInit
功能描述: 队列销毁(数组类型队列)
入参::
      void* r_pvAMPSContext AMPS应用上下文数据结构
      void* r_pvAMPSArrayBasedQueue 待操作的队列

出参:
     --
返回值:
      void

*****************************************************************/
void Queue_EnQueueArrayBasedCleanup(void* r_pvAMPSContext, void* r_pvAMPSListBasedQueue)
{
	t_AMPSArrayBasedQueue* poAMPSArrayBasedQueue = r_pvAMPSListBasedQueue;

	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    /*释放在初始化时分配的结点内存*/
	AMPS_InternalFree(poAMPSArrayBasedQueue->ppuchQueue);

	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");
}

/*****************************************************************
函数名称: Queue_EnQueueArrayBasedData
功能描述: 向队列中写数据(数组类型队列)
入参::
      void* r_pvAMPSContext AMPS应用上下文数据结构
      void* r_pvAMPSArrayBasedQueue 待操作的队列
      void* r_pvDataToEnQueue       待写入的数据

出参:
     --
返回值:
      int

*****************************************************************/
int Queue_EnQueueArrayBasedData(void* r_pvAMPSContext, void* r_pvAMPSArrayBasedQueue, void* r_pvDataToEnQueue)
{
	t_AMPSArrayBasedQueue* poAMPSArrayBasedQueue = r_pvAMPSArrayBasedQueue;

	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    /*判断队列是否已满*/
	if((poAMPSArrayBasedQueue->unCount + 1) == poAMPSArrayBasedQueue->nSizeOfQueue)
	{
		TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_ERROR, "Queue is FULL.\n");
		return AMPS_ERROR_FAILURE;
	}

    /*新队列结点赋值*/
	//printf("Queue Head Index 1 ==> %d \n", poAMPSArrayBasedQueue->nHeadIndex);
	poAMPSArrayBasedQueue->ppuchQueue[poAMPSArrayBasedQueue->nHeadIndex] = r_pvDataToEnQueue;

    /*插入新结点*/
    poAMPSArrayBasedQueue->nHeadIndex = (poAMPSArrayBasedQueue->nHeadIndex + 1) % poAMPSArrayBasedQueue->nSizeOfQueue;
	//printf("Queue Head Index 2 ==> %d \n", poAMPSArrayBasedQueue->nHeadIndex);

    /*记数增1*/
	poAMPSArrayBasedQueue->unCount++;

	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");
	return AMPS_SUCCESS;
}


/*****************************************************************
函数名称: Queue_DeQueueArrayBasedData
功能描述: 从队尾删除结点(数组类型队列)
入参::
      void* r_pvAMPSContext AMPS应用上下文数据结构
      void* r_pvAMPSArrayBasedQueue 待操作的队列

出参:
     --
返回值:
      void* 已删除结点内容

*****************************************************************/
void* Queue_DeQueueArrayBasedData(void* r_pvAMPSContext, void* r_pvAMPSArrayBasedQueue)
{
	t_AMPSArrayBasedQueue* poAMPSArrayBasedQueue = r_pvAMPSArrayBasedQueue;
	void* pvQueueData = NULL;

	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    /*是否为空队列*/
	if (0 == poAMPSArrayBasedQueue->unCount)
	{
		TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_DEBUG, "Queue is empty.\n");
		return NULL;
	}

	//printf("Queueu Tail Index 1 ==> %d \n", poAMPSArrayBasedQueue->nTailIndex);
	pvQueueData = poAMPSArrayBasedQueue->ppuchQueue[poAMPSArrayBasedQueue->nTailIndex];

    /*从队尾删除结点，即队尾指针上移*/
	poAMPSArrayBasedQueue->nTailIndex = (poAMPSArrayBasedQueue->nTailIndex + 1) % poAMPSArrayBasedQueue->nSizeOfQueue;
	//printf("Queueu Tail Index 2 ==> %d \n", poAMPSArrayBasedQueue->nTailIndex);
	
	poAMPSArrayBasedQueue->unCount--;

	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");
	return pvQueueData;
}

/*****************************************************************
函数名称: Queue_DeQueueArrayBasedData
功能描述: 获取队列结点个数(数组类型队列)
入参::
      void* r_pvAMPSContext AMPS应用上下文数据结构
      void* r_pvAMPSArrayBasedQueue 待操作的队列

出参:
     --
返回值:
      int 队列结点个数

*****************************************************************/
int Queue_GetArrayBasedQueueLength(void* r_pvAMPSContext, void* r_pvAMPSArrayBasedQueue)
{
	t_AMPSArrayBasedQueue* poAMPSArrayBasedQueue = r_pvAMPSArrayBasedQueue;
    return (poAMPSArrayBasedQueue->unCount);
}


 类似资料：

相关阅读

Python bsonrpc源码解读SpringMVC源码解读之HandlerMapping - AbstractUrlHandlerMapping系列request分发SpringMVC源码解读之HandlerMappingJS中队列和双端队列实现及应用详解队列上有多重队列

相关文章

消息队列 RabbitMQ 之 幂等性、优先级队列、惰性队列消息队列Java PriorityBlockingQueue优先级阻塞队列解析Java ConcurrentLinkedQueue非阻塞式同步队列解析Redis消息队列

相关问答

同步队列？java - 如何理解Integer.parseInt源码？事件队列与消息队列的区别在Java中使用队列解决迷宫Akka Http-主机级客户端API源.队列模式

相关文档

Ruby 源码解读Laravel 源码详解Tornado 源码解析阅读 express 源码JDK 源码阅读笔记
快捷导航： 新手教程 算法原理 架构设计 Java进阶 数据库进阶 大厂专栏 面试经验 编程笔记 编程问答 所有专题 文档资料 工具软件 电子书籍 小牛导航
在线工具： 房贷计算器 个税计算器 Linux命令查询 Json格式化 正则表达式 颜色转换 AES加解密 SHA1加密 MD5加密 毒鸡汤 字数统计 随机密码生成 进制转换 Base64编解码 励志句子
Copyright © 2019-2024 小牛知识库@xnip.cn. All Rights Reserved.