新增定时器时间轮,时间堆方案

ZWiley · ZWiley · Apr 14, 2020 · Apr 14, 2020 · Apr 16, 2020 · Apr 16, 2020
commit c32da40a80dd252cb83fbe11f093e4cc88d858d9
diff --git a/.vscode/c_cpp_properties.json b/.vscode/c_cpp_properties.json
diff --git a/.vscode/settings.json b/.vscode/settings.json
diff --git a/timer/min_heap.h b/timer/min_heap.h
@@ -0,0 1,188 @@
 /*
  * @Author: wiley
  * @LastEditors: wiley
  * @Date: 2020-06-04 16:57:52
  * @LastEditTime: 2020-06-04 17:35:26
  * @Description: file content
  * @FilePath: \TinyWebServer\timer\min_heap.h
  */ 
 #ifndef MIN_HEAP
 #define MIN_HEAP
 
 #include <time.h>
 #include "../http/http_conn.h"
 #include "../log/log.h"
 
 using std::exception;
 
 #define BUFFER_SIZE 64
 
 class heap_timer;
 
 struct client_data
 {
  sockaddr_in address;
  int sockfd;
  char buf[BUFFER_SIZE];
  heap_timer *timer;
 };
 
 class heap_timer {
 public:
  time_t expire;
  void (*cb_func)(client_data*);
  client_data *user_data;
 public:
  heap_timer(int delay) {
  expire = time(NULL) delay;
  }
 };
 
 class time_heap {
 private:
  heap_timer **array;
  int capacity;
  int cur_size();
 public:
  time_heap(int cap) throw (std::exception) :capacity(cap), cur_size(0) {
  array = new heap_timer *(capacity);
  if (!array) {
  throw std::exception();
  }
  for (int i = 0; i < capacity; i ) {
  array[i] = NULL;
  }
  }
 
  time_heap(heap_timer **init_array, int size, int capacity) 
  throw(std::exception) : cur_size(size), capacity(capacity) {
  if (capacity < size) {
  throw std::exception();
  }
  array = new heap_timer *(capacity);
  if (!array) {
  throw std::exception();
  }
  for (int i = 0; i < capacity; i ) {
  array[i] = NULL;
  }
  if (size != 0) {
  for (int i = 0; i < size; i ) {
  array[i] = init_array[i];
  }
  for (int i = (cur_size - 1) / 2; i >= 0; --i) {
  percolate_down(i);
  }
  }
  }
 
  ~time_heap() {
  for (int i = 0; i < cur_size(); i ) {
  delete array[i];
  }
  delete[] array;
  }
 
 public:
  void add_timer(heap_timer* timer) throw(std::exception) {
  if (!timer) {
  return ;
  }
  if (cur_size >= capacity) {
  resize();
  }
  int hole = cur_size ;
  int parent = 0;
  for (; hole > 0; hole = parent) {
  parent = (hole - 1) / 2;
  if (array[parent]->expire <= timer->expire) {
  break;
  }
  array[hole] = array[parent];
  }
  array[hole] = timer;
  }
 
  void del_timer(heap_time *timer) {
  if (!timer) {
  return;
  }
  timer->cb_func = NULL;
  }
 
  heap_timer *top() const {
  if (empty()) {
  return NULL;
  }
  return array[0];
  }
 
  void pop_timer() {
  if (empty()) {
  return;
  }
  if (array[0]) {
  delete array[0];
  array[0] = array[--cur_size];
  percolate_down(0);
  }
  }
 
  void tick() {
  heap_timer *tmp = array[0];
  time_t cur = time(NULL);
  while(!empty()) {
  if (!tmp) {
  break;
  }
  if(tmp->expire > cur) {
  break;
  }
  if (array[0]->cb_func) {
  array[0]->cb_func(array[0]->user_data);
  }
  pop_timer();
  tmp = array[0];
  }
  }
  bool empty() const {return cur_size == 0;}
 
 private:
  // 最小堆向下操作
  void percolate_down(int hole) {
  heap_timer *temp = array[hole];
  int child = 0;
  for (; ((hole * 2 1) <= (cur_size - 1)); hole = child) {
  child = hole * 2 1;
  if ((child < (cur_size - 1)) && (array[child 1]->expire < array[child]->expire)) {
  child;
  }
  if (array[child->expire] < temp->expire) {
  array[hole] = array[child];
  }
  else {
  break;
  }
  }
  array[hole] = temp; 
  }
 
  // 堆数组扩容一倍
  void resize() throw (std::exception) {
  heap_timer **temp = new heap_timer * [2 * capacity];
  for (int i = 0; i < 2 * capacity; i) {
  temp[i] = NULL;
  }
  if (!temp) {
  throw std::exception();
  }
  capacity = 2 * capacity;
  for (int i = 0; i < cur_size; i) {
  temp[i] = array[i];
  }
  delete[] array;
  array = temp;
  }
 };
 
 #endif
diff --git a/timer/time_wheel_timer.h b/timer/time_wheel_timer.h
@@ -0,0 1,161 @@
 /*
  * @Author: wiley
  * @LastEditors: wiley
  * @Date: 2020-06-04 16:08:50
  * @LastEditTime: 2020-06-04 16:53:17
  * @Description: file content
  * @FilePath: \TinyWebServer\timer\time_wheel_timer.h
  */ 
 #ifndef TIME_WHEEL_TIMER
 #define TIME_WHEEL_TIMER
 
 #include <time.h>
 #include "../http/http_conn.h"
 #include "../log/log.h"
 
 #define BUFFER_SIZE 64
 
 struct client_data
 {
  sockaddr_in address;
  int sockfd;
  char buf[BUFFER_SIZE];
  time_wheel_timer *timer;
 };
 
 class time_wheel_timer
 {
 public:
  int rotation; // 记录定时器在时间轮转多少圈后失效
  int time_slot; // 记录定时器属于时间轮上的哪个槽
  void (*cb_func)(client_data*); // 定时器回调函数
  client_data *user_data; //客户数据
  time_wheel_timer *next;
  time_wheel_timer *prev;
 
 public:
  time_wheel_timer(int rot, int ts) : next(NULL), prev(NULL), rotation(rot), time_slot(ts) {}
 };
 
 class time_wheel
 {
 private:
  /* data */
  static const int N = 60; // 时间轮上的槽的数目
  static const int SI = 1; // 每1s时间轮轮动一次，槽间隔为1s
  time_wheel_timer *slots[N]; // 时间轮的槽，其中每个元素指向一个定时器链表，链表无序
  int cur_slot; // 时间轮的当前槽
 
 public:
  time_wheel() : cur_slot(0) {
  for (int i = 0; i < N; i ) {
  slots[i] = NULL;
  }
  }
 
  ~time_wheel() {
  for (int i = 0; i < N; i ) {
  time_wheel_timer *tmp = slots[i];
  while (tmp) {
  slots[i] = tmp->next;
  delete tmp;
  tmp = slots[i];
  }
  }
  } 
 
  // 根据定时值timeout创建一个定时器，并把它插入合适槽中
  time_wheel_timer *add_timer(int timeout) {
  if (timeout < 0) {
  return NULL;
  }
  int ticks = 0;
  /**
  * 下面根据待插入定时器的超时值计算它将在时间轮转动多少个滴答后被触发，
  * 并将该滴答数存在变量ticks中，如果待插入定时器的超时值小于时间轮的槽间隔SI
  * 则将ticks向上折合为1， 否则就将ticks向下折合为timeout / SI
  */
  if (timeout < SI) {
  ticks = 1;
  }
  else {
  ticks = timeout / SI;
  }
  // 计算待插入的定时器在时间轮转动多少圈后被触发
  int rotation = ticks / N;
  // 计算待插入的定时器应该被插入哪个槽中
  int ts = (cur_slot (ticks % N)) % N;
  // 创建新的定时器，它在时间轮转动rotation圈之后被触发，且位于第ts个槽上
  time_wheel_timer *timer = new time_wheel_timer(rotation, ts);
  // 如果第ts个槽中尚无任何定时器，则把新建的定时器插入其中，并将该定时器设置为该槽的头结点
  if (!slots[ts]) {
  slots[ts] = timer;
  }
  else {
  timer->next = slots[ts];
  slots[ts]->prev = timer;
  slots[ts] = timer;
  }
  return timer;
  }
 
  // 删除定时器
  void del_timer(time_wheel_timer *timer) {
  if (!timer) {
  return;
  }
  int ts = timer->time_slot;
  // slots[ts] 是目标定时器所在槽的头结点，如果目标定时器就是头结点，则需要重置第ts个槽的头结点
  if (timer == slots[ts]) {
  slots[ts] = slots[ts]->next;
  if (slots[ts]) {
  slots[ts]->prev = NULL;
  }
  delete timer;
  }
  else {
  timer->prev->next = timer->next;
  if (timer->next) {
  timer->next->prev = timer->prev;
  }
  delete timer;
  }
  }
 
  // SI时间到后，调用该函数，时间轮向前滚动一个槽的间隔
  void tick() {
  time_wheel_timer *tmp = slots[cur_slot]; // 取得当前槽上头结点
  while (tmp)
  {
  // 如果定时器的rotation值大于0，则在这一轮不起作用
  if (tmp->rotation > 0) {
  tmp->rotation--;
  tmp = tmp->next;
  } 
  //否则说明定时器已经到期，于是执行定时任务，然后删除该定时器
  else {
  tmp->cb_func(tmp->user_data);
  if (tmp == slots[cur_slot]) {
  slots[cur_slot] = tmp->next;
  delete tmp;
  if (slots[cur_slot]) {
  slots[cur_slot]->prev = NULL;
  }
  tmp = slots[cur_slot];
  }
  else {
  tmp->prev->next = tmp->next;
  if (tmp->next) {
  tmp->next->prev = tmp->prev;
  }
  time_wheel_timer *tmp2 = tmp->next;
  delete tmp;
  tmp = tmp2;
  }
  }
  }
  cur_slot = cur_slot % N;
  }
 };
 
 #endif