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

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

隊列中有兩個基本概念：

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

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

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

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

?

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

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

「入隊（enqueue）」

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

「出隊（dequeue）」

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

2. 環(huán)形隊列2.1. 環(huán)形隊列的特點

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

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

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

typedef struct k_ring_queue_st {

knl_obj_t knl_obj;

uint16_t head; //隊頭指針

uint16_t tail; //隊尾指針

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

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

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

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

} k_ring_q_t;

環(huán)形隊列初始化，將隊頭指針和隊尾置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)形隊列是否為滿或者為空：

__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)形隊列入隊操作的API如下：

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

在此API中，入隊操作的實現(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)形隊列出隊操作的API如下：

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

在此API中，出隊操作的實現(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;

}

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

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

2.3. 環(huán)形隊列使用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)形隊列

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

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

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）;

}

}

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

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ù)出隊

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ù)出隊

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）;

}

}

運行結(jié)果如下：

3. 優(yōu)先級隊列3.1. 優(yōu)先級隊列的特點

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

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

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

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

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

?

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

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

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

__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)先級隊列控制塊指針

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

pool隊列的緩沖區(qū)

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

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

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

uint8_t mgr_pool［TOS_PRIO_Q_MGR_ARRAY_SIZE（5）］;

元素入隊

__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)先級越高。

元素出隊

__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需要傳入一個地址，用于記錄出隊元素的優(yōu)先級。

3.3. 優(yōu)先級隊列使用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)先級隊列

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

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

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）;

}

}

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

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ù)出隊

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ù)出隊

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é)① 普通隊列是一種只能在一端入隊，在一端出隊的數(shù)據(jù)結(jié)構(gòu)，規(guī)則：FIFO。

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

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

責任編輯：haq