数据结构【三】：简单优先队列PriorityQueue

在数据结构【二】：简单阻塞队列BlockingQueue的基础上添加权限属性:priority,并控制enqueue时根据priority排序插入.

1.定义priority取值范围0~9

2.dequeue取出priority值最大的节点(最高进先出 largest-in，first-out ).

3.若priority相等,则继续遵循FIFO原则

注意 : 此代码未经生产环境检验,仅供学习参考.

PriorityQueue.h

#ifndef CUR_PRIORITYQUEUE_H
#define CUR_PRIORITYQUEUE_H
#include <stdlib.h>
#include <pthread.h>


struct node{
    int value;
    int priority; //优先级,取值范围0~9
    struct node * next;
};


typedef struct PriorityQueue_ST{
    int capacity,remaining,closed;
    struct node * head, *tail;
    pthread_mutex_t queue_mutex;
    pthread_cond_t  cond_not_full;
    pthread_cond_t  cond_not_empty;
    pthread_cond_t  cond_empty;
}PriorityQueue;


extern PriorityQueue* empty_queue(int _capacity);
extern int queue_free(PriorityQueue *q);
extern int is_empty(const PriorityQueue *q);
extern int is_full(const PriorityQueue *q);
extern int enqueue(struct node *item, PriorityQueue *q);
extern struct node* dequeue(PriorityQueue *q);

#endif

PriorityQueue.c

#include "PriorityQueue.h"
#include <stdio.h>

PriorityQueue* empty_queue(int _capacity)
{
     PriorityQueue *q = malloc(sizeof(PriorityQueue));
     q->head  = q->tail = NULL;
     q->capacity = q->remaining = _capacity;
     q->closed = 0;
     pthread_mutex_init(&q->queue_mutex , NULL);
     pthread_cond_init(&q->cond_not_full , NULL);
     pthread_cond_init(&q->cond_not_empty , NULL);
     pthread_cond_init(&q->cond_empty , NULL);
     return q;
}
 
int queue_free(PriorityQueue *q)
{
    pthread_mutex_lock(&q->queue_mutex);
    printf("close queue...
");
    q->closed = 1;
    //等待cond_empty
    while(!is_empty(q))
    {
        pthread_cond_wait(&q->cond_empty, &q->queue_mutex);
    }
    free(q);
    pthread_mutex_unlock(&q->queue_mutex);
    printf("closed...
");
}

int is_empty(const PriorityQueue *q)
{
    return q->capacity == q->remaining;
}

int is_full(const PriorityQueue *q)
{
    return q->remaining == 0;
}

int enqueue(struct node *item, PriorityQueue *q)
{

    if(q->closed) goto err;
    //lock
    pthread_mutex_lock(&q->queue_mutex);
    //等待cond_not_full
    while(is_full(q))
    {
        pthread_cond_wait(&q->cond_not_full, &q->queue_mutex);
    }
    //设置最权限:大为9,最小为0,默认为0
    item->priority = item->priority > 9 ? 9 : item->priority;
    item->priority = item->priority < 0 ? 0 : item->priority;

    if(is_empty(q))
    {
        q->head = q->tail = item;
        //通知所有等待cond_not_empty的线程
        pthread_cond_broadcast(&q->cond_not_empty);
    }
    else
    {
        //插入时按优先级排序 : order by priority desc
        struct node *big = NULL;
        struct node *small = q->head;
        while(small != NULL && small->priority >= item->priority)
        {
            big = small;
            small = small->next;
        }
        
        if(small == NULL)
        {
            //尾部插入 : big = q->tail
            q->tail->next = item;
            q->tail = item;
        }else if(big == NULL)
        {
            //头部插入
            q->head = item;
            item->next = small;
        }else
        {
            //中部插入
            big->next = item;
            item->next = small;
        }
        
    }
    q->remaining--;
    //unlock
    pthread_mutex_unlock(&q->queue_mutex);

    return 0;
err : 
    return -1;
}

struct node* dequeue(PriorityQueue *q)
{
    
    //已经关闭的空队列
    if(q->closed && is_empty(q)) goto err;
    //lock 
    pthread_mutex_lock(&q->queue_mutex);
    //空队列,等待cond_not_empty
    while(!q->closed && is_empty(q))
    {
        pthread_cond_wait(&q->cond_not_empty, &q->queue_mutex);
    }
    //take
    struct node * temp = q->head;
    q->head = q->head->next;


    //在未关闭队列的情况下,唤醒enqueue等待线程
    if(!q->closed && is_full(q))
    {
        pthread_cond_broadcast(&q->cond_not_full); //TODO 1
    }
    q->remaining++; 
    //唤醒关闭队列线程
    if(q->closed && is_empty(q))
    {
        pthread_cond_signal(&q->cond_empty);//TODO 2
    }

    //注意:TODO 1和TODO 2其实是互斥的,不可能同时满足条件
    //必须先判断是否激活cond_not_full然后remaining++
    //最后再判断是否激活cond_empty
    //unlock
    pthread_mutex_unlock(&q->queue_mutex);
    return temp;
err:
    return NULL;
}

测试代码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "PriorityQueue.h"
extern void* func_put(void* _q);

PriorityQueue *q;
pthread_t thread1;
void main()
{
    q = empty_queue(5);
    pthread_create(&thread1,NULL,func_put,(void*)q);
    srand((int) time(0));

    int i;
    for(i=1; i<=10; i++)
    {
        struct node * item = (struct node *)malloc(sizeof(struct node));
        item->value = i;
        item->next = NULL;
        item->priority = (0 + rand() % 10);
        enqueue(item,q);
        printf("enqueue -> value : %d, priority : %d, remaining : %d
",i,item->priority,q->remaining);
        sleep(1);
    }
    queue_free(q);
}

void* func_put(void* _q)
{
    PriorityQueue *q = (PriorityQueue*)_q;
    struct node *item;
    while((item = dequeue(q)) != NULL)
    {
        printf("dequeue -> value : %d, priority : %d, remaining : %d
",item->value,item->priority,q->remaining);
        free(item);
        sleep(3);
    }
}

测试结果: