队列

queue.c

/** @file queue.c
  * @brief 队列.
  * @author [email protected]
  * @date 2010-7-30
  * @version 0.1
  * @note 实现了一个循环队列
  */
#include "queue.h"
#include <malloc.h> /* for malloc(), free() */
#include <string.h> /* for memcpy() */

 /*
  *@struct
  *@brief 队列的结构体定义.
  *@note 无
  */
struct queue_t {
    int front;   /* 队头*/
    int rear;    /* 队尾*/
    int elem_size; /* 单个元素的大小*/
    int capacity; /* 容量大小，以元素为单位*/
    void *data; /* 存放数据的内存块*/
};

int queue_init(queue_t **q, int elem_size)
{
    if(q == NULL) return ERR_NULL_POINTER;
    (*q) = (queue_t*)malloc(sizeof(queue_t));
    if((*q) == NULL) return ERR_MALLOC_FAILED;

    (*q)->front = 0;
    (*q)->rear = 0;
    (*q)->elem_size = elem_size;
    (*q)->capacity = 4;
    (*q)->data = malloc((*q)->capacity * (*q)->elem_size);
    return SUCCESS;
}

int queue_uninit(queue_t **q)
{
    if((q !=NULL) && (*q != NULL)) {
        free((*q)->data);

        free((*q));
        (*q) = NULL;
    }
    return 0;
}

void queue_clear(queue_t *q)
{
	if(q != NULL) {
		q->front = 0;
		q->rear = 0;
	}
}

bool queue_is_empty(const queue_t *q)
{
	if(q != NULL) {
        return q->front == q->rear;
	} else {
        return false;
	}
}

bool queue_is_full(const queue_t *q)
{
	if(q != NULL) {
        return (q->rear + 1) % q->capacity == q->front;
	} else {
        return false;
	}
}

int queue_enter(queue_t *q, const void *x)
{
    if(queue_is_full(q)) {
        void* const tmp = malloc(q->capacity * 2 * q->elem_size);
        if(tmp == NULL) return ERR_MALLOC_FAILED;
        if(q->front < q->rear) {
            memcpy(tmp, 
                (char*)q->data + q->front * q->elem_size, 
                (q->rear - q->front) * q->elem_size);
            q->rear -= q->front;
            q->front = 0;
        } else if(q->front > q->rear) {
            /* 拷贝q->front 到q->capacity 之间的数据*/
            memcpy(tmp, 
                (char*)q->data + q->front * q->elem_size, 
                (q->capacity - q->front) * q->elem_size);
            /* 拷贝q->data[0 到q->data[rear] 之间的数据*/
            memcpy((char*)tmp + 
                (q->capacity - q->front) * q->elem_size, 
                q->data, q->rear * q->elem_size);
            q->rear += q->capacity - q->front;
            q->front = 0;
        }
        free(q->data);
        q->data = tmp;
        q->capacity *= 2;
    }
	/* q->data[(q->rear)++] = x; */
	memcpy((char*)q->data + q->elem_size * q->rear, 
        x, q->elem_size);
	q->rear = (q->rear + 1) % q->capacity;
    return SUCCESS;
}

int queue_detach(queue_t *q, void* x)
{
    if(!queue_is_empty(q)) {
		/* *x = q->data[(q->front)++]; */
		memcpy(x, (char*)q->data + q->elem_size * q->front,
            q->elem_size);
		q->front = (q->front + 1) % q->capacity;
        return SUCCESS;
    } else {
        return ERR_OTHER;
    }
}

queue.h

/** @file queue.h
  * @brief 队列.
  * @author [email protected]
  * @date 2010-7-30
  * @version 0.1
  * @note 实现了一个循环队列 
  */
#ifndef _QUEUE_H_
#define _QUEUE_H_

#ifdef __cplusplus
extern "C"
{
#endif


#include "config.h"
/** 队列的不透明结构体. */
typedef struct queue_t queue_t;

/** 
  * @brief 初始化队列.
  * @param[out] q 队列结构体的二级指针
  * @return 成功返回0，失败返回错误码
  * @note 本函数会分配内存，创建一个queue_t对象，将其地址
  * 存放在h所指向的指针中
  * @remarks 无
  */
extern int queue_init(queue_t **q, int elem_size);

/** 
  * @brief 释放队列的内存空间.
  * @return 成功返回0，失败返回错误码
  * @note 释放掉队列的数据所占用的内存块，并释放队列对象
  * 本身所占用的内存
  * @remarks 无
  */
extern int queue_uninit(queue_t **q);

/** 
  * @brief 清空元素，但不释放内存.
  * @param[in] q 指向队列结构体的指针
  * @return 无
  * @note 无
  * @remarks 无
  */
extern void queue_clear(queue_t *q);

/** 
  * @brief 判断队列是否为空.
  * @param[in] q 指向队列结构体的指针
  * @return 是空，返回TRUE，否则返回FALSE
  * @note 无
  * @remarks 无
  */
extern bool queue_is_empty(const queue_t *q);

/** 
  * @brief 判断队列是否已满.
  * @param[in] q 指向队列结构体的指针
  * @return 满，返回TRUE，否则返回FALSE
  * @note 无
  * @remarks 无
  */
extern bool queue_is_full(const queue_t *q);

/** 
  * @brief 在队尾添加元素.
  * @param[in] q 指向队列结构体的指针
  * @param[in] x 要添加的元素
  * @return 成功返回0，失败返回错误码
  * @note 无
  * @remarks 无
  */
extern int queue_enter(queue_t *q, const void *x);

/** 
  * @brief 在队头删除元素.
  * @param[in] q 指向队列结构体的指针
  * @param[out] x 存放退出队列的元素
  * @return 成功返回0，失败返回错误码
  * @note 无
  * @remarks 无
  */
extern int queue_detach(queue_t *q, void *x);


#ifdef __cplusplus
}
#endif

#endif /* end of _QUEUE_H_ */