Chinaunix首页 | 论坛 | 博客
  • 博客访问: 746098
  • 博文数量: 116
  • 博客积分: 923
  • 博客等级: 准尉
  • 技术积分: 1635
  • 用 户 组: 普通用户
  • 注册时间: 2011-10-06 21:43
个人简介

一直帮老板搬运代码!!!

文章分类
文章存档

2013年(47)

2012年(69)

分类: LINUX

2013-05-18 12:18:00

说明:这里是把nginx的定时器完全抽取出来(不过实现单线程的处理,如果多线程得把源码拿过来添加锁的那部分就行)

ngx_eventtimer.h 头文件

#pragma once

#ifdef WIN32
#else
#include
#include
#include
#include
#endif
#include "../common/pubinclude.h"

#include
#include
#include

#define ngx_thread_volatile      volatile

#if defined(_MSC_VER) || defined(_WINDOWS_)
#if !defined(_WINSOCK2API_) && !defined(_WINSOCKAPI_)
 struct timeval
 {
  long tv_sec;
  long tv_usec;
 };
#endif
#else
#endif

#if defined(_MSC_VER) || defined(_WINDOWS_)
int gettimeofday(struct timeval* tv,void *);
#endif

* TODO: auto_conf: ngx_inline   inline __inline __inline__ */
#ifndef ngx_inline
#define ngx_inline      inline
#endif

typedef intptr_t        ngx_int_t; //long int 定义
typedef uintptr_t       ngx_uint_t; //unsigned  int定义

//tree
typedef ngx_uint_t  ngx_rbtree_key_t;
typedef ngx_int_t   ngx_rbtree_key_int_t;
typedef ngx_rbtree_key_t      ngx_msec_t;
typedef ngx_rbtree_key_int_t  ngx_msec_int_t;

//错误吗的定义
#define  NGX_OK          0
#define  NGX_ERROR      -1
#define  NGX_AGAIN      -2
#define  NGX_BUSY       -3
#define  NGX_DONE       -4
#define  NGX_DECLINED   -5
#define  NGX_ABORT      -6

#define ngx_rbt_red(node)               ((node)->color = 1)
#define ngx_rbt_black(node)             ((node)->color = 0)
#define ngx_rbt_is_red(node)            ((node)->color)
#define ngx_rbt_is_black(node)          (!ngx_rbt_is_red(node))
#define ngx_rbt_copy_color(n1, n2)      (n1->color = n2->color)

#define ngx_tm_sec            tm_sec
#define ngx_tm_min            tm_min
#define ngx_tm_hour           tm_hour
#define ngx_tm_mday           tm_mday
#define ngx_tm_mon            tm_mon
#define ngx_tm_year           tm_year
#define ngx_tm_wday           tm_wday
#define ngx_tm_isdst          tm_isdst

#define ngx_tm_sec_t          int
#define ngx_tm_min_t          int
#define ngx_tm_hour_t         int
#define ngx_tm_mday_t         int
#define ngx_tm_mon_t          int
#define ngx_tm_year_t         int
#define ngx_tm_wday_t         int

 /* a sentinel must be black */
#define ngx_rbtree_sentinel_init(node)  ngx_rbt_black(node)
typedef struct tm             ngx_tm_t;

#define ngx_gettimeofday(tp)  (void) gettimeofday(tp, NULL); //封装当前时间
#define ngx_msleep(ms)        (void) usleep(ms * 1000)
#define ngx_sleep(s)          (void) sleep(s)

#define NGX_TIMER_INFINITE  (ngx_msec_t) -1
#define NGX_TIMER_LAZY_DELAY  300

typedef struct ngx_rbtree_node_s  ngx_rbtree_node_t;
struct ngx_rbtree_node_s {
 ngx_rbtree_key_t       key; //时间
 ngx_rbtree_node_t     *left;
 ngx_rbtree_node_t     *right;
 ngx_rbtree_node_t     *parent;
 u_char                 color;
 u_char                 data;
};

typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root, ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
typedef struct ngx_rbtree_s  ngx_rbtree_t;
struct ngx_rbtree_s
{
 ngx_rbtree_node_t     *root;
 ngx_rbtree_node_t     *sentinel;
 ngx_rbtree_insert_pt   insert;
};

//event
typedef struct ngx_event_s       ngx_event_t;
typedef void (*ngx_event_handler_pt)(ngx_event_t *ev);
//事件结构,使用位域保存多个字节,有利于缩短长度
struct ngx_event_s
{
 void            *data;

 ngx_event_handler_pt  handler; //accepte 的回调函数
 ngx_rbtree_node_t     timer;//字段,很容易看出属于红黑树节点类型变量,红黑树就是通过该字段来组织事件对象。

 /* the links of the posted queue */
 ngx_event_t     *next;
 ngx_event_t    **prev;
};

ngx_int_t ngx_event_timer_init();
void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *root, ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
ngx_inline ngx_rbtree_node_t * ngx_rbtree_min(ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,ngx_rbtree_node_t *node);
ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);

ngx_inline void ngx_event_del_timer(ngx_event_t *ev);
void ngx_event_add_timer(ngx_event_t *ev, ngx_msec_t timer);
void ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree, ngx_rbtree_node_t *node);
void ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree, ngx_rbtree_node_t *node);

extern ngx_rbtree_node_t          ngx_event_timer_sentinel;//属于红黑树节点类型变量,在红黑树的操作过程中当作哨兵使用,同时它是static的,所以作用域仅限于模块内。
extern ngx_rbtree_t  ngx_event_timer_rbtree; //装了事件计时红黑树树结构
extern volatile ngx_msec_t ngx_current_msec;

void ngx_rbtree_insert_value(ngx_rbtree_node_t *root, ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
void ngx_timezone_update(void);
void ngx_localtime(time_t s, ngx_tm_t *tm);
void ngx_libc_localtime(time_t s, struct tm *tm);
void ngx_libc_gmtime(time_t s, struct tm *tm);

ngx_msec_t ngx_event_find_timer(void);
void ngx_event_expire_timers(void);

*
* The red-black tree code is based on the algorithm described in
* the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
*/
void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root,ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root,ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);

void ngx_time_update(void);

//time
#define  ngx_add_timer ngx_event_add_timer
#define  ngx_del_timer ngx_event_del_timer

#define ngx_rbtree_init(tree, s, i)                                           \
 ngx_rbtree_sentinel_init(s);                                              \
 (tree)->root = s;                                                         \
 (tree)->sentinel = s;                                                     \
 (tree)->insert = i

 

实现文件:ngx_eventtimer.cpp

#include "ngx_eventtimer.h"

ngx_rbtree_node_t          ngx_event_timer_sentinel;//属于红黑树节点类型变量,在红黑树的操作过程中当作哨兵使用,同时它是static的,所以作用域仅限于模块内。
volatile ngx_msec_t ngx_current_msec;
ngx_rbtree_t  ngx_event_timer_rbtree; //装了事件计时红黑树树结构

#if defined(_MSC_VER) || defined(_WINDOWS_)
int gettimeofday(struct timeval* tv,void *)
{
 union {
  long long ns100;
  FILETIME ft;
 } now;

 GetSystemTimeAsFileTime (&now.ft);
 tv->tv_usec = (long) ((now.ns100 / 10LL) % 1000000LL);
 tv->tv_sec = (long) ((now.ns100 - 116444736000000000LL) / 10000000LL);
 return (0);
}
#endif

*
* the event timer rbtree may contain the duplicate keys, however,
* it should not be a problem, because we use the rbtree to find
* a minimum timer value only
*/
//事件时间的初始化
ngx_int_t ngx_event_timer_init()
{
 ngx_rbtree_init(&ngx_event_timer_rbtree, &ngx_event_timer_sentinel,ngx_rbtree_insert_timer_value); //插入红黑数

 return NGX_OK;
}

//查找事件时间
ngx_msec_t ngx_event_find_timer(void)
{
 ngx_msec_int_t      timer;
 ngx_rbtree_node_t  *node, *root, *sentinel;

 if (ngx_event_timer_rbtree.root == &ngx_event_timer_sentinel) { //判断红黑树的根,然后退出
  return NGX_TIMER_INFINITE;//这里退出,返回秒数
 }

 //保存相应的值
 root = ngx_event_timer_rbtree.root;
 sentinel = ngx_event_timer_rbtree.sentinel;

 node = ngx_rbtree_min(root, sentinel);

 timer = (ngx_msec_int_t) node->key - (ngx_msec_int_t) ngx_current_msec; //计算出描述

 return (ngx_msec_t) (timer > 0 ? timer : 0);
}

//处理过期事件
void ngx_event_expire_timers(void)
{
 ngx_event_t        *ev;
 ngx_rbtree_node_t  *node, *root, *sentinel;

 sentinel = ngx_event_timer_rbtree.sentinel;

 for ( ;; ) {

  root = ngx_event_timer_rbtree.root;

  if (root == sentinel) {
   return;
  }

  node = ngx_rbtree_min(root, sentinel);

  /* node->key <= ngx_current_time */

  if ((ngx_msec_int_t) node->key - (ngx_msec_int_t) ngx_current_msec <= 0)
  {
   ev = (ngx_event_t *) ((char *) node - offsetof(ngx_event_t, timer));

   ngx_rbtree_delete(&ngx_event_timer_rbtree, &ev->timer);

   ev->handler(ev);

   continue;
  }

  break;
 }

}


///////////////////////////////////////////////
void ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree,ngx_rbtree_node_t *node)
{
 ngx_rbtree_node_t  **root, *temp, *sentinel;

 /* a binary tree insert */

 root = (ngx_rbtree_node_t **) &tree->root;
 sentinel = tree->sentinel;

 if (*root == sentinel) {
  node->parent = NULL;
  node->left = sentinel;
  node->right = sentinel;
  ngx_rbt_black(node);
  *root = node;

  return;
 }

 tree->insert(*root, node, sentinel);

 /* re-balance tree */

 while (node != *root && ngx_rbt_is_red(node->parent)) {

  if (node->parent == node->parent->parent->left) {
   temp = node->parent->parent->right;

   if (ngx_rbt_is_red(temp)) {
    ngx_rbt_black(node->parent);
    ngx_rbt_black(temp);
    ngx_rbt_red(node->parent->parent);
    node = node->parent->parent;

   } else {
    if (node == node->parent->right) {
     node = node->parent;
     ngx_rbtree_left_rotate(root, sentinel, node);
    }

    ngx_rbt_black(node->parent);
    ngx_rbt_red(node->parent->parent);
    ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
   }

  } else {
   temp = node->parent->parent->left;

   if (ngx_rbt_is_red(temp)) {
    ngx_rbt_black(node->parent);
    ngx_rbt_black(temp);
    ngx_rbt_red(node->parent->parent);
    node = node->parent->parent;

   } else {
    if (node == node->parent->left) {
     node = node->parent;
     ngx_rbtree_right_rotate(root, sentinel, node);
    }

    ngx_rbt_black(node->parent);
    ngx_rbt_red(node->parent->parent);
    ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);
   }
  }
 }

 ngx_rbt_black(*root);
}


void ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
            ngx_rbtree_node_t *sentinel)
{
 ngx_rbtree_node_t  **p;

 for ( ;; ) {

  p = (node->key < temp->key) ? &temp->left : &temp->right;

  if (*p == sentinel) {
   break;
  }

  temp = *p;
 }

 *p = node;
 node->parent = temp;
 node->left = sentinel;
 node->right = sentinel;
 ngx_rbt_red(node);
}


void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
{
 ngx_rbtree_node_t  **p;

 for ( ;; ) {

  /*
  * Timer values
  * 1) are spread in small range, usually several minutes,
  * 2) and overflow each 49 days, if milliseconds are stored in 32 bits.
  * The comparison takes into account that overflow.
  */

  /*  node->key < temp->key */

  p = ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key
   < 0)
   ? &temp->left : &temp->right;

  if (*p == sentinel) {
   break;
  }

  temp = *p;
 }

 *p = node;
 node->parent = temp;
 node->left = sentinel;
 node->right = sentinel;
 ngx_rbt_red(node);
}


void ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
{
 ngx_uint_t           red;
 ngx_rbtree_node_t  **root, *sentinel, *subst, *temp, *w;

 /* a binary tree delete */

 root = (ngx_rbtree_node_t **) &tree->root;
 sentinel = tree->sentinel;

 if (node->left == sentinel) {
  temp = node->right;
  subst = node;

 } else if (node->right == sentinel) {
  temp = node->left;
  subst = node;

 } else {
  subst = ngx_rbtree_min(node->right, sentinel);

  if (subst->left != sentinel) {
   temp = subst->left;
  } else {
   temp = subst->right;
  }
 }

 if (subst == *root) {
  *root = temp;
  ngx_rbt_black(temp);

  /* DEBUG stuff */
  node->left = NULL;
  node->right = NULL;
  node->parent = NULL;
  node->key = 0;

  return;
 }

 red = ngx_rbt_is_red(subst);

 if (subst == subst->parent->left) {
  subst->parent->left = temp;

 } else {
  subst->parent->right = temp;
 }

 if (subst == node) {

  temp->parent = subst->parent;

 } else {

  if (subst->parent == node) {
   temp->parent = subst;

  } else {
   temp->parent = subst->parent;
  }

  subst->left = node->left;
  subst->right = node->right;
  subst->parent = node->parent;
  ngx_rbt_copy_color(subst, node);

  if (node == *root) {
   *root = subst;

  } else {
   if (node == node->parent->left) {
    node->parent->left = subst;
   } else {
    node->parent->right = subst;
   }
  }

  if (subst->left != sentinel) {
   subst->left->parent = subst;
  }

  if (subst->right != sentinel) {
   subst->right->parent = subst;
  }
 }

 /* DEBUG stuff */
 node->left = NULL;
 node->right = NULL;
 node->parent = NULL;
 node->key = 0;

 if (red) {
  return;
 }

 /* a delete fixup */

 while (temp != *root && ngx_rbt_is_black(temp)) {

  if (temp == temp->parent->left) {
   w = temp->parent->right;

   if (ngx_rbt_is_red(w)) {
    ngx_rbt_black(w);
    ngx_rbt_red(temp->parent);
    ngx_rbtree_left_rotate(root, sentinel, temp->parent);
    w = temp->parent->right;
   }

   if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
    ngx_rbt_red(w);
    temp = temp->parent;

   } else {
    if (ngx_rbt_is_black(w->right)) {
     ngx_rbt_black(w->left);
     ngx_rbt_red(w);
     ngx_rbtree_right_rotate(root, sentinel, w);
     w = temp->parent->right;
    }

    ngx_rbt_copy_color(w, temp->parent);
    ngx_rbt_black(temp->parent);
    ngx_rbt_black(w->right);
    ngx_rbtree_left_rotate(root, sentinel, temp->parent);
    temp = *root;
   }

  } else {
   w = temp->parent->left;

   if (ngx_rbt_is_red(w)) {
    ngx_rbt_black(w);
    ngx_rbt_red(temp->parent);
    ngx_rbtree_right_rotate(root, sentinel, temp->parent);
    w = temp->parent->left;
   }

   if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
    ngx_rbt_red(w);
    temp = temp->parent;

   } else {
    if (ngx_rbt_is_black(w->left)) {
     ngx_rbt_black(w->right);
     ngx_rbt_red(w);
     ngx_rbtree_left_rotate(root, sentinel, w);
     w = temp->parent->left;
    }

    ngx_rbt_copy_color(w, temp->parent);
    ngx_rbt_black(temp->parent);
    ngx_rbt_black(w->left);
    ngx_rbtree_right_rotate(root, sentinel, temp->parent);
    temp = *root;
   }
  }
 }

 ngx_rbt_black(temp);
}


ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,ngx_rbtree_node_t *node)
{
 ngx_rbtree_node_t  *temp;

 temp = node->right;
 node->right = temp->left;

 if (temp->left != sentinel) {
  temp->left->parent = node;
 }

 temp->parent = node->parent;

 if (node == *root) {
  *root = temp;

 } else if (node == node->parent->left) {
  node->parent->left = temp;

 } else {
  node->parent->right = temp;
 }

 temp->left = node;
 node->parent = temp;
}


ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node)
{
 ngx_rbtree_node_t  *temp;

 temp = node->left;
 node->left = temp->right;

 if (temp->right != sentinel) {
  temp->right->parent = node;
 }

 temp->parent = node->parent;

 if (node == *root) {
  *root = temp;

 } else if (node == node->parent->right) {
  node->parent->right = temp;

 } else {
  node->parent->left = temp;
 }

 temp->right = node;
 node->parent = temp;
}

/////////////////////////////////////////////


*
* FreeBSD does not test /etc/localtime change, however, we can workaround it
* by calling tzset() with TZ and then without TZ to update timezone.
* The trick should work since FreeBSD 2.1.0.
*
* Linux does not test /etc/localtime change in localtime(),
* but may stat("/etc/localtime") several times in every strftime(),
* therefore we use it to update timezone.
*
* Solaris does not test /etc/TIMEZONE change too and no workaround available.
*/

//更新timezone时间
void ngx_timezone_update(void)
{
#if (NGX_FREEBSD)

 if (getenv("TZ")) {
  return;
 }

 putenv("TZ=UTC");

 tzset();

 unsetenv("TZ");

 tzset();

#elif (NGX_LINUX)
 time_t      s;
 struct tm  *t;
 char        buf[4];

 s = time(0);

 t = localtime(&s);

 strftime(buf, 4, "%H", t); //%H 24小时制的小时

#endif
}


void ngx_localtime(time_t s, ngx_tm_t *tm)
{
 ngx_tm_t  *t;

 t = localtime(&s);
 *tm = *t;

 tm->ngx_tm_mon++;
 tm->ngx_tm_year += 1900;
}


void ngx_libc_localtime(time_t s, struct tm *tm)
{
#if (NGX_HAVE_LOCALTIME_R)
 (void) localtime_r(&s, tm);

#else
 struct tm  *t;

 t = localtime(&s);
 *tm = *t;

#endif
}


void ngx_libc_gmtime(time_t s, struct tm *tm)
{
#if (NGX_HAVE_LOCALTIME_R)
 (void) gmtime_r(&s, tm);

#else
 struct tm  *t;

 t = gmtime(&s);
 *tm = *t;

#endif
}


////
ngx_inline void ngx_event_del_timer(ngx_event_t *ev)
{
 ngx_rbtree_delete(&ngx_event_timer_rbtree, &ev->timer);
}


void ngx_event_add_timer(ngx_event_t *ev, ngx_msec_t timer)
{
 ngx_msec_t      key;

 key = ngx_current_msec + timer;

 ev->timer.key = key;

 ngx_rbtree_insert(&ngx_event_timer_rbtree, &ev->timer);

}

ngx_inline ngx_rbtree_node_t * ngx_rbtree_min(ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
{
 while (node->left != sentinel) {
  node = node->left;
 }

 return node;
}

void ngx_time_update(void)
{
    time_t           sec;
    ngx_uint_t       msec;
    struct timeval   tv;

    ngx_gettimeofday(&tv); //获得当前时间

    sec = tv.tv_sec;
    msec = tv.tv_usec / 1000;
    ngx_current_msec = (ngx_msec_t) sec * 1000 + msec; //当前事件的秒数
}



使用和测试:
////test event timer
//#include "../eventtimer/ngx_eventtimer.h"
//#include
//
//int main()
//{
//
// ngx_time_update();
//
//    ngx_event_timer_init();
// ngx_msec_int_t timer,delta;
// delta = ngx_current_msec; //当前的秒数
// ngx_event_t *ev = new ngx_event_t;
// ngx_add_timer(ev,10000);
//
// ngx_event_t *ev1 = new ngx_event_t;
// ngx_add_timer(ev1,10);
//
// ngx_event_t *ev2 = new ngx_event_t;
// ngx_add_timer(ev2,9999);
//
// ngx_event_t *ev3 = new ngx_event_t;
// ngx_add_timer(ev3,8888);
// timer = ngx_event_find_timer();
// ngx_time_update();
// timer = ngx_event_find_timer();
//
// delta = ngx_current_msec - delta; //算出处理进程事件的秒数
//
// if (delta) {
//        ngx_event_expire_timers();
//    }
//
// timer = ngx_event_find_timer();
// printf("find timer is %lld\n",timer);
//
// ngx_event_expire_timers();
// return 0;
//}


 


阅读(7499) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~