TencentOS-tiny中環(huán)形隊(duì)列的實(shí)現(xiàn)

1. 什么是隊(duì)列隊(duì)列（queue）是一種只能在一端插入元素、在另一端刪除元素的數(shù)據(jù)結(jié)構(gòu)，遵循「先入先出」（FIFO）的規(guī)則。

隊(duì)列中有兩個基本概念：

隊(duì)頭指針（可變）：永遠(yuǎn)指向此隊(duì)列的第一個數(shù)據(jù)元素；

隊(duì)尾指針（可變）：永遠(yuǎn)指向此隊(duì)列的最后一個數(shù)據(jù)元素；

隊(duì)列中的數(shù)據(jù)存儲方式有兩種：

① 基于靜態(tài)連續(xù)內(nèi)存（數(shù)組）存儲，如圖：② 基于動態(tài)內(nèi)存（鏈表節(jié)點(diǎn)）存儲，如圖：

?

后續(xù)都使用基于靜態(tài)內(nèi)存存儲的隊(duì)列講解。

?隊(duì)列提供兩個統(tǒng)一的操作：

「入隊(duì)（enqueue）」

入隊(duì)將一個元素添加到隊(duì)尾，并將隊(duì)尾指針+1后移，如圖：

「出隊(duì)（dequeue）」

出隊(duì)將從隊(duì)頭中取出一個元素，并將隊(duì)頭指針+1后移，如圖：

2. 環(huán)形隊(duì)列2.1. 環(huán)形隊(duì)列的特點(diǎn)

普通隊(duì)列的入隊(duì)操作將隊(duì)尾指針后移+1，出隊(duì)操作將隊(duì)頭指針后移+1，操作幾次之后會發(fā)現(xiàn)隊(duì)頭指針和隊(duì)尾指針都跑到緩沖區(qū)的尾部去了：這就導(dǎo)致了前面的內(nèi)存空間全被浪費(fèi)，如果要重新恢復(fù)使用，則需要進(jìn)行元素和指針的移動：顯然這種隊(duì)列使用方式太不方便了，所以就誕生了環(huán)形隊(duì)列：「不用搬移元素和指針，一直可以重復(fù)利用這段內(nèi)存空間」。

2.2. 環(huán)形隊(duì)列的實(shí)現(xiàn)

TencentOS-tiny中環(huán)形隊(duì)列的實(shí)現(xiàn)在tos_ring_queue.h和tos_ring_queue.c中。

typedef struct k_ring_queue_st {

knl_obj_t knl_obj;

uint16_t head; //隊(duì)頭指針

uint16_t tail; //隊(duì)尾指針

size_t total; //記錄隊(duì)列中元素的個數(shù)

uint8_t *pool; //隊(duì)列底層的存儲結(jié)構(gòu)（一個數(shù)組）

size_t item_size; //隊(duì)列中每個元素的大小，單位：字節(jié)

size_t item_cnt; //隊(duì)列中可以容納的元素數(shù)量

} k_ring_q_t;

環(huán)形隊(duì)列初始化，將隊(duì)頭指針和隊(duì)尾置0：

__API__ k_err_t tos_ring_q_create（k_ring_q_t *ring_q， void *pool， size_t item_cnt， size_t item_size）

{

//省略了參數(shù)合法性檢查代碼

ring_q-》head = 0u;

ring_q-》tail = 0u;

ring_q-》total = 0;

ring_q-》pool = （uint8_t *）pool;

ring_q-》item_size = item_size;

ring_q-》item_cnt = item_cnt;

return K_ERR_NONE;

}

判斷環(huán)形隊(duì)列是否為滿或者為空：

__API__ int tos_ring_q_is_empty（k_ring_q_t *ring_q）

{

TOS_CPU_CPSR_ALLOC（）;

int is_empty = K_FALSE;

//省略了參數(shù)合法性檢查代碼

TOS_CPU_INT_DISABLE（）;

is_empty = （ring_q-》total == 0 ？ K_TRUE ： K_FALSE）;

TOS_CPU_INT_ENABLE（）;

return is_empty;

}

__API__ int tos_ring_q_is_full（k_ring_q_t *ring_q）

{

TOS_CPU_CPSR_ALLOC（）;

int is_full = K_FALSE;

//省略了參數(shù)合法性檢查代碼

TOS_CPU_INT_DISABLE（）;

is_full = （ring_q-》total == ring_q-》item_cnt ？ K_TRUE ： K_FALSE）;

TOS_CPU_INT_ENABLE（）;

return is_full;

}

環(huán)形隊(duì)列入隊(duì)操作的API如下：

__API__ k_err_t tos_ring_q_enqueue（k_ring_q_t *ring_q， void *item， size_t item_size）;

在此API中，入隊(duì)操作的實(shí)現(xiàn)如下：

__STATIC_INLINE__ void ring_q_item_increase（k_ring_q_t *ring_q）

{

ring_q-》tail = RING_NEXT（ring_q， ring_q-》tail）;

++ring_q-》total;

}

環(huán)形隊(duì)列出隊(duì)操作的API如下：

__API__ k_err_t tos_ring_q_dequeue（k_ring_q_t *ring_q， void *item， size_t *item_size）;

在此API中，出隊(duì)操作的實(shí)現(xiàn)如下：

__STATIC_INLINE__ void ring_q_item_decrease（k_ring_q_t *ring_q）

{

ring_q-》head = RING_NEXT（ring_q， ring_q-》head）;

--ring_q-》total;

}

在入隊(duì)和出隊(duì)操作的時候都使用了 RING_NEXT 宏，用來獲取在環(huán)形隊(duì)列中的下一個位置：

#define RING_NEXT（ring_q， index） （（index + 1） % ring_q-》item_cnt）

2.3. 環(huán)形隊(duì)列使用Demo

編寫如下的測試代碼：

#include 《tos_k.h》typedef struct item_st {

int a;

int b;

int c;

} item_t;

#define RING_QUEUE_ITEM_MAX 5uint8_t ring_q_buffer［RING_QUEUE_ITEM_MAX * sizeof（item_t）］;

k_ring_q_t ring_q;

void entry_task_demo（void *arg）

{

k_err_t err;

int i;

item_t item;

size_t item_size;

//創(chuàng)建環(huán)形隊(duì)列

tos_ring_q_create（&ring_q， ring_q_buffer， RING_QUEUE_ITEM_MAX， sizeof（item_t））;

//數(shù)據(jù)入隊(duì)

for（i = 0;i 《 RING_QUEUE_ITEM_MAX; i++）

{

item.a = i;

item.b = i;

item.c = i;

err = tos_ring_q_enqueue（&ring_q， &item， sizeof（item_t））;

if（err == K_ERR_NONE）

{

printf（“enqueue a item： %d %d %d

”， item.a， item.b， item.c）;

}

else

{

printf（“ring queue enqueue fail，err = %d

”， err）;

}

}

//隊(duì)列滿之后，繼續(xù)入隊(duì)

err = tos_ring_q_enqueue（&ring_q， &item， sizeof（item_t））;

if（err == K_ERR_RING_Q_FULL）

{

printf（“ring queue is full： %s

”， tos_ring_q_is_full（&ring_q） ？ “TRUE” ： “FALSE”）;

}

else

{

printf（“ring queue enqueue fail，err = %d

”， err）;

}

//數(shù)據(jù)出隊(duì)

for（i = 0; i 《 RING_QUEUE_ITEM_MAX; ++i）

{

err = tos_ring_q_dequeue（&ring_q， &item， &item_size）;

if（err == K_ERR_NONE）

{

printf（“dequeue a item（%d bytes）： %d %d %d

”， item_size， item.a， item.b， item.c）;

}

else

{

printf（“ring queue dequeue fail，err = %d

”， err）;

}

}

//沒有數(shù)據(jù)后繼續(xù)出隊(duì)

err = tos_ring_q_dequeue（&ring_q， &item， &item_size）;

if（err == K_ERR_RING_Q_EMPTY）

{

printf（“ring queue is empty： %s

”， tos_ring_q_is_empty（&ring_q） ？ “TRUE” ： “FALSE”）;

}

else

{

printf（“ring queue dequeue fail，err = %d

”， err）;

}

}

運(yùn)行結(jié)果如下：

3. 優(yōu)先級隊(duì)列3.1. 優(yōu)先級隊(duì)列的特點(diǎn)

優(yōu)先級隊(duì)列也是一種基于隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，但是它「不遵循FIFO」，而是按照每個元素的優(yōu)先級進(jìn)行出隊(duì)：「最高優(yōu)先級的先出隊(duì)」。

3.2. 優(yōu)先級隊(duì)列的實(shí)現(xiàn)

TencentOS-tiny中環(huán)形隊(duì)列的實(shí)現(xiàn)在tos_prio_queue.h和tos_prio_queue.c中。

優(yōu)先級隊(duì)列在數(shù)據(jù)入隊(duì)的時候，會按照入隊(duì)元素的優(yōu)先級進(jìn)行一次排序，「將優(yōu)先級值最?。▋?yōu)先級最高的元素）放在隊(duì)頭」，出隊(duì)的時候只需要取第一個元素即可。

正是因?yàn)檫@種特性，優(yōu)先級隊(duì)列的底層存儲結(jié)構(gòu)不能使用數(shù)組（排序太麻煩），而是使用了二項(xiàng)堆的數(shù)據(jù)結(jié)構(gòu)。

?

二項(xiàng)堆是一種二叉樹集合的數(shù)據(jù)結(jié)構(gòu)，在本文中不再深入講解，有興趣的讀者可以自己搜索閱讀。

?下面只給出優(yōu)先級隊(duì)列的API，「理解其規(guī)則，會用即可」。

創(chuàng)建優(yōu)先級隊(duì)列

__API__ k_err_t tos_prio_q_create（k_prio_q_t *prio_q， void *mgr_array， void *pool， size_t item_cnt， size_t item_size）;

參數(shù)描述

prio_q優(yōu)先級隊(duì)列控制塊指針

mgr_array提供一塊緩沖區(qū)用于內(nèi)部管理

pool隊(duì)列的緩沖區(qū)

item_cnt隊(duì)列可容納的元素數(shù)量

item_size每個元素的大小，單位字節(jié)

其中用于內(nèi)部管理的緩存區(qū)大小可以使用宏定義來計(jì)算，比如有5個元素的管理緩沖區(qū)大小：

uint8_t mgr_pool［TOS_PRIO_Q_MGR_ARRAY_SIZE（5）］;

元素入隊(duì)

__API__ k_err_t tos_prio_q_enqueue（k_prio_q_t *prio_q， void *item， size_t item_size， k_prio_t prio）;

其中優(yōu)先級的值遵循：數(shù)值越小，優(yōu)先級越高。

元素出隊(duì)

__API__ k_err_t tos_prio_q_dequeue（k_prio_q_t *prio_q， void *item， size_t *item_size， k_prio_t *prio）;

其中prio需要傳入一個地址，用于記錄出隊(duì)元素的優(yōu)先級。

3.3. 優(yōu)先級隊(duì)列使用Demo

#include 《tos_k.h》typedef struct item_st {

int a;

int b;

int c;

} item_t;

#define PRIO_QUEUE_ITEM_MAX 5uint8_t prio_q_buffer［PRIO_QUEUE_ITEM_MAX * sizeof（item_t）］;

uint8_t mgr_pool［TOS_PRIO_Q_MGR_ARRAY_SIZE（PRIO_QUEUE_ITEM_MAX）］;

k_prio_q_t prio_q;

void entry_task_demo（void *arg）

{

k_err_t err;

int i;

item_t item;

size_t item_size;

k_prio_t item_prio;

//創(chuàng)建優(yōu)先級隊(duì)列

tos_prio_q_create（&prio_q， mgr_pool， prio_q_buffer， PRIO_QUEUE_ITEM_MAX， sizeof（item_t））;

//數(shù)據(jù)入隊(duì)

for（i = PRIO_QUEUE_ITEM_MAX;i 》 0; i--）

{

item.a = i;

item.b = i;

item.c = i;

err = tos_prio_q_enqueue（&prio_q， &item， sizeof（item）， i）;

if（err == K_ERR_NONE）

{

printf（“enqueue a item： %d %d %d

”， item.a， item.b， item.c）;

}

else

{

printf（“prio queue enqueue fail，err = %d

”， err）;

}

}

//隊(duì)列滿之后，繼續(xù)入隊(duì)

err = tos_prio_q_enqueue（&prio_q， &item， sizeof（item_t）， i）;

if（err == K_ERR_PRIO_Q_FULL）

{

printf（“prio queue is full： %s

”， tos_prio_q_is_full（&prio_q） ？ “TRUE” ： “FALSE”）;

}

else

{

printf（“prio queue enqueue fail，err = %d

”， err）;

}

//數(shù)據(jù)出隊(duì)

for（i = 0; i 《 PRIO_QUEUE_ITEM_MAX; ++i）

{

err = tos_prio_q_dequeue（&prio_q， &item， &item_size， &item_prio）;

if（err == K_ERR_NONE）

{

printf（“dequeue a item［piro %d］： %d %d %d

”， item_prio， item.a， item.b， item.c）;

}

else

{

printf（“prio queue dequeue fail，err = %d

”， err）;

}

}

//沒有數(shù)據(jù)后繼續(xù)出隊(duì)

err = tos_prio_q_dequeue（&prio_q， &item， &item_size， &item_prio）;

if（err == K_ERR_PRIO_Q_EMPTY）

{

printf（“prio queue is empty： %s

”， tos_prio_q_is_empty（&prio_q） ？ “TRUE” ： “FALSE”）;

}

else

{

printf（“prio queue dequeue fail，err = %d

”， err）;

}

}

4. 總結(jié)① 普通隊(duì)列是一種只能在一端入隊(duì)，在一端出隊(duì)的數(shù)據(jù)結(jié)構(gòu)，規(guī)則：FIFO。

② 環(huán)形隊(duì)列對內(nèi)存空間的利用率最高，使用最多，規(guī)則：FIFO。

③ 優(yōu)先級隊(duì)列不遵循FIFO，每個元素都有自己的優(yōu)先級，規(guī)則：優(yōu)先級最高的元素先出隊(duì)。

責(zé)任編輯：haq