摘要：
第一章：实现队列 值得注意的是，Item是void*类型，也就是说，这个队列可以存储任何类型，因为我们实际上存储了指针。（这样描述真的可以吗？）队列的源代码。h如下/***@filequeue h*@brief**/#ifndefQUEUE_h#defineQUEUE_h#defineMAXQUEUESIZE1000typedefenseumboolean｛False，True｝bool；typedefvoid*项目；typedefstructQueue*QueueADT；QueueADTNewQueue；voidFreeQueue；voidEnQueue；ItemDeQueue；boolQueueIsEmpty；boolQueueIsFull；intQueueLength；ItemGetQueueItem；#endiqueue的源代码。c如下：/***@filequeue。c*@brief*/#include #include #include #include #include“queue.h”structQueue｛Itemelements[MAXQUEUESIZE]；intiHead；intiCount；｝；QueueADTNewQueue｛QueueADTqueue；queue=malloc；queue-˃iHead=queue-˃iCount=0；return；｝voidFreeQueue｛free；｝voidEnQueue｛if｛printf；exit（-1）；｝队列-˃元素[%MAXQUEUESIZE]=x；队列-˃iCount++；｝ItemDeQueue｛Itemresult；if｛printf；exit（-1）；｝result=queue-˃elements[queue-˃iHead]；队列-˃iHead=%MAXQUEUESIZE；队列-˃iCount--；return；}boolQueueIsEmpty｛return；｝boolQueueIsFull｛return；｝intQueueLength｛return；｝ItemGetQueueItem｛如果｛returnqueue-˃元素[%MAXQUEUESIZE]；｝输出函数退出（-1）；}第2章：事件队列事件队列是真实队列API上的一个简单包。仅添加了DoEvent函数。
我觉得实现一个队列还是比较有意思的事情，采用常见的循环数组实现的方式。
值得注意的是，Item项是void *类型的，也就是说这个队列可以存储任意类型，因为我们其实存储的是指针。（这么描述真的没问题吗？）
queue.h的源代码如下
/** * @file queue.h * @brief * */ #ifndef QUEUE_H #define QUEUE_H
#define MAXQUEUESIZE 1000 typedef enum boolean{False,True} bool; typedef void * Item; typedef struct Queue * QueueADT; QueueADT NewQueue(void); void FreeQueue(QueueADT queue); void EnQueue(QueueADT queue,Item x); Item DeQueue(QueueADT queue); bool QueueIsEmpty(QueueADT queue); bool QueueIsFull(QueueADT queue); int QueueLength(QueueADT queue); Item GetQueueItem(QueueADT queue,int index); #endif
queue.c的源代码如下：
/** * @file queue.c * @brief */ #include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <assert.h> #include "queue.h" struct Queue { Item elements[MAXQUEUESIZE]; int iHead; int iCount; }; QueueADT NewQueue(void) { QueueADT queue; queue = (QueueADT)malloc(sizeof(struct Queue)); queue->iHead = queue->iCount = 0; return (queue); } void FreeQueue(QueueADT queue) { free(queue); } void EnQueue(QueueADT queue,Item x) { if(QueueIsFull(queue)) { printf("QueueIsFull "); exit(-1); } queue->elements[(queue->iHead+queue->iCount)%MAXQUEUESIZE] = x; queue->iCount++; } Item DeQueue(QueueADT queue) { Item result; if(QueueIsEmpty(queue)) { printf("QueueIsEmpty "); exit(-1); } result = queue->elements[queue->iHead]; queue->iHead = (queue->iHead + 1)%MAXQUEUESIZE; queue->iCount--; return (result); } bool QueueIsEmpty(QueueADT queue) { return (queue->iCount == 0); } bool QueueIsFull(QueueADT queue) { return (queue->iCount == MAXQUEUESIZE); } int QueueLength(QueueADT queue) { return (queue->iCount); } Item GetQueueItem(QueueADT queue,int index) { if(index >= 0 && index < QueueLength(queue)) { return queue->elements[(queue->iHead + index)%MAXQUEUESIZE]; } printf("index < 0 or index > queue length "); exit(-1); }
事件队列实在队列API上做一个简单的封装。
只是添加了一个DoEvent(QueueADT queue)函数。
Event.h
#ifndef MY_EVENT_H #define MY_EVENT_H #include "queue.h" #define NewEventQueue() NewQueue() typedef struct Event * Event_ptr; void FreeEventQueue(QueueADT queue,void(*FreeEventNode)(Event_ptr x)); void EnEventQueue(QueueADT queue,void (* pEvent)(void * argument),void * argument, size_t size); void DoEvent(QueueADT queue); #endif // MY_EVENT_H
Event.c
#include <assert.h> #include <stdlib.h> #include <stdio.h> #include "Event.h" #include <string.h> typedef struct Event { void (* pEvent)(void * argument); void * argument; }Event; inline static void QuitIfPtrIsNULL(void * ptr,const char * message) { if(ptr == NULL) { fprintf(stderr,"%s ",message); exit(-1); } } void FreeEventQueue(QueueADT queue,void(*FreeEventNode)(Event_ptr x)) { int i = 0; for(i = 0;i < QueueLength(queue);i++) { FreeEventNode(GetQueueItem(queue,i)); //释放单个节点malloc的内存，由用户实现 } FreeQueue(queue); } void EnEventQueue(QueueADT queue,void (* pEvent)(void * argument),void * argument, size_t size) { Event * x = NULL; QuitIfPtrIsNULL(queue,"queue == NULL"); QuitIfPtrIsNULL(pEvent,"pEvent == NULL"); x = (Event *)malloc(sizeof(Event)); QuitIfPtrIsNULL(x,"malloc error"); x->pEvent = pEvent; x->argument = malloc(size); memcpy(x->argument,argument,size); EnQueue(queue,x); } void DoEvent(QueueADT queue) { Event * x = NULL; QuitIfPtrIsNULL(queue,"queue == NULL"); if(!QueueIsEmpty(queue)) { x = DeQueue(queue); QuitIfPtrIsNULL(x,"some thing is wrong"); x->pEvent(x->argument); free(x->argument); free(x); } }
在完成底层库之后，可以进行事件模拟了，当然，由于在linux下面编程，略微风骚的扩展了下功能，用了定时器，一次检测事件，一次处理事件。
代码如下：
#include <stdio.h> #include <stdlib.h> #include <sys/select.h> #include <sys/time.h> #include <unistd.h> #include <signal.h> #include <termios.h> #include "queue.h" #include "Event.h" #include "kbhit.h" unsigned int TimerCount; QueueADT queue; void PrintChar(void * c) { char * a = (char *)c; printf(" %c",*a); } void timefunc(int sig) /* 定时事件代码 */ { if(TimerCount++ % 7 != 0) //why I am 7,but not 2? { if(kbhit()) { char c = getch(); EnEventQueue(queue,PrintChar,&c,sizeof(c)); } } else { DoEvent(queue); } signal(SIGPROF, timefunc); /* 捕获定时信号 */ } int main() { queue = NewQueue(); struct itimerval value; value.it_value.tv_sec = 0; // 定时1.5秒 value.it_value.tv_usec = 100000; value.it_interval.tv_sec = 0; // 定时1.5秒 value.it_interval.tv_usec = 100000; signal(SIGPROF, timefunc); // 捕获定时信号 setitimer(ITIMER_PROF, &value, NULL); // 定时开始 while (1); return 0; }
如上所示，假如TimerCount++ % 2 == 0 那么检测事件的频率和处理事件的频率就一样了，通过调整参数，我们可看到经典讨论下reader和writter问题。
让读者的频率加快，或者让写者的速率加快。
由于linux下面没有kbhit和getch函数，所以照搬了网上的两段代码，如下。
#include <stdio.h> #include <termios.h> #include <unistd.h> #include <fcntl.h> int kbhit(void) { struct termios oldt, newt; int ch; int oldf; tcgetattr(STDIN_FILENO, &oldt); newt = oldt; newt.c_lflag &= ~(ICANON | ECHO); tcsetattr(STDIN_FILENO, TCSANOW, &newt); oldf = fcntl(STDIN_FILENO, F_GETFL, 0); fcntl(STDIN_FILENO, F_SETFL, oldf | O_NONBLOCK); ch = getchar(); tcsetattr(STDIN_FILENO, TCSANOW, &oldt); fcntl(STDIN_FILENO, F_SETFL, oldf); if(ch != EOF) { ungetc(ch, stdin); return 1; } return 0; } int getch(void) { struct termios oldt,newt; int ch; tcgetattr( STDIN_FILENO, &oldt ); newt = oldt; newt.c_lflag &= ~( ICANON | ECHO ); tcsetattr( STDIN_FILENO, TCSANOW, &newt ); ch = getchar(); tcsetattr( STDIN_FILENO, TCSANOW, &oldt ); return ch; }
检验发现，实现的也不是特别好。