音视频开发中的队列实现

〇、参考

《音视频开发进阶指南：基于Android与iOS平台的实践》：7.2.1 音频队列的实现

一、最小队列

• 使用C语言

  • C++类中的方法，对应到C中则为，结构体中的函数指针类型的属性

  • 结构体中的其他属性，称为常规属性

• 使用链表实现，将队列元素作为有效数据封装到链表节点中，最终连接成的链表就是一个队列

typedef struct PacketQueue {
	PacketList *mFirst;
  	PacketList *mLast;
  	Mutex      *mMutex;
  	Cond       *mCond;
  	int (*packet_queue_put)(PacketQueue *que, Packet *pkt);
  	int (*packet_queue_get)(PacketQueue *que, Packet *pkt, int block);
} PacketQueue;

1.0 自定义链表(节点)类型

链表的其中一个成员也是一个链表，由于这种特殊结构的存在，后面我们将链表节点类型和链表类型当成一回事，可以混用。

typedef struct PacketList{
	Packet *pkt;
	PacketList *next;
} PacketList;

1.1 队列常规属性

1. 头节点mFirst：链表节点类型，当链表只有一个节点时，头节点同时也是尾节点

2. 尾节点mLast：链表节点类型，当链表只有一个节点时，尾节点同时也是头节点

3. 互斥锁mMutex：和条件变量一起保证线程安全

4. 条件变量mCond：和互斥锁一起保证线程安全

1.2 队列函数指针属性

1. packet_queue_put：将一个包压入队列尾

2. packet_queue_get：从队列头获取一个包

1.2.1 packet_queque_put的实现

1.2.1.1 流程

1. abort *** 作：如果队列已经abort，什么都不做，返回-1

2. 将包封装为链表节点

3. 上锁（禁止其他线程这时候访问），准备将链表节点放入链表

4. 挂节点：将新链表节点放入链表尾部

   • 如果队列为空，令链表节点任命为尾结点兼头节点；

   • 如果队列不空，将链表节点挂在尾节点后边，然后将链表节点任命为尾节点。
     

     
     

5. 发信号：链表节点放入链表后，条件变量发送一个signal，告诉block住的线程，可以继续从队列中获取元素了

6. 解锁

1.2.1.2 细节说明

• 往链表中压入节点是在链表尾进行 *** 作，一般涉及不到头节点，仅当链表为空或只有一个链表节点时，会涉及到头节点。
  

  
  

  所以压包入列时，把对头节点的 *** 作当做特殊情况 *** 作写在特殊情况处理if中，把对尾节点的必经 *** 作（任命 *** 作）写在特殊情况处理if外。
  

  
  

1.2.1.3 完整代码

//成功返回1
//出错或队列abort了，返回-1
int packet_queue_put(PacketQueue *que, Packet *pkt)
{
	PacketList *pkt_lst; //定义一个链表类型的指针	
  	为pkt_lst分配内存, 若分配不成功返回-1；
  
  	if(mAbortRequest) return -1；
    
    //2. 将包封装为链表节点
    pkt_lst->pkt = pkt;
    pkt_lst->next = NULL;//未来该包后面挂哪个包，谁也不知道，所以为NULL
  
    //3. 上锁
  	LockMutex(que->mMutex);
  
    //4. 将链表节点放入链表尾部
    if(NULL == que->mLast){ //链表为空的其中一种表示方法
        que->mFirst = pkt_lst；
    }else{
        que->mLast->next = pkt_lst;
    }
    que->mLast = pkt_lst;
  
    //5. 发信号
    CondSignal(que->mCond);
  
    //6. 解锁
    UnlockMutex(que->mMutex);
    
  	释放pkt_lst的内存；
    return 1;
}

1.2.2 packet_queue_get的实现

1.2.2.1 流程

1. 上锁

2. abort *** 作：如果abort了队列，什么也不做，返回-1

3. 取节点：从链表取出头节点

   • 如果队列为空，

     • 如果block非0，表示实现一个blocking queue，则令当前线程阻塞在get方法，并解锁让其他线程得以访问队列，直到当前线程获得队列不为空的信号后，重新上锁再从队取一次包

     • 如果block为0，表示实现非blocking queue，则直接解锁后返回-1

   • 如果队列非空，取出头节点，并任命新的头节点（get方法必经 *** 作），若新的头节点为空（即队列此时为空），则还需重新任命新的尾节点也为空

4. 解封装：解封取出的链表节点，拿到包

5. 解锁

1.2.2.2 细节说明

1. CondWait(&mCond，&mMutex);可以实现队列为空时的要求

2. 当队列为空时取包，当前线程被阻塞，待队列非空后，有个重新取包的 *** 作。
   

   
   

   这一重新取包 *** 作通过循环实现，即将“从链表取出头节点”这一 *** 作放入循环中，同时在队列非空时的取包 *** 作后加上break。
   

   
   

3. 由于CondWait(&mCond, &mMutex);在返回前又把mMutx给锁上了(见SDL_几个完整头文件：SDL_mutex.h：SDL_CondWait的说明)，所以从链表取头节点之前的上锁 *** 作不用放进循环

4. 重新取包时也要判断队列是否abort了，所以判断队列是否abort了的逻辑也放入循环中，同时不能直接返回-1，因为此时已经上锁（进入循环前），要先解锁后再返回-1

5. 从链表中取头节点是在链表头部进行 *** 作，一般涉及不到尾节点，仅当链表为空或只有一个链表节点时，会涉及到尾节点。
   

   
   

   所以从链表中取头节点时，把对头节点的必经 *** 作（取出头节点然后任命新的头节点）写在特殊情况处理if外，把对尾节点的 *** 作当做特殊情况 *** 作写在特殊情况处理if中。
   

   
   

1.2.2.3 完整代码

//成功返回1
//非blocking queue为空时，返回0
//出错或队列abort了返回-1

int packet_queue_get(PacketQueue *que, Packet* pkt, int block){
  	ret = 0;
    PacketList *pkt_lst;
  	为pkt_lst分配内存，如果分配不成功返回-1；
  
    //1. 上锁
    LockMutex(que->mMutex);
	
  	while(1){
        //2. 队列abort时的 *** 作
    	if(mAbortRequest){
        	ret = -1；
            break;
        }
        
        //3. 从链表中取出头节点
        if(que->mFirst){ //队列非空
         	pkt_lst = mFirst;//取出头节点
          	mFirst = pkt_lst->next;//任命新的头节点
          	if(NULL == mFirst){//如果新的队列为空
            	mLast = NULL; 
            }
          	
            //4. 解封取出的链表节点，拿到包
          	pkt = pkt_lst->pkt;
          	ret = 1;
          	break;
        }else if(0 == block){
          	ret = 0; 
          	break;
        }else{
         	CondWait(que->mCond, que->mMutex); 
        }      
    }//while(1)
  
  	//5. 解锁
  	UnlockMutex(que->mMutex);
  
  	释放pkt_lst的内存；
  	return ret;
}

二、总结

• 空队列的两种表示方法

  1. if(NULL == mFirst)

  2. if(NULL == mLast)

• 只有一个元素的队列，该元素既是头节点也是尾节点

• 压包入队，尾节点 *** 作为必经 *** 作，头节点 *** 作为特殊情况 *** 作

• 取包出队，头节点 *** 作为必经 *** 作，尾节点 *** 作为特殊情况 *** 作

三、扩展功能队列 3.1 扩展常规属性

• 队列当前元素数目

• 队列当前字节数

3.2 扩展函数指针属性

• abort队列

• 销毁队列