多级时间轮实现(C版)

多级时间轮实现(C版)

下面给出多级时间轮实现，类似于水表。
实现方式，多级数组加双向链表

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#define tw_uint unsigned

#define TVN_BITS 6
#define TVR_BITS 8
#define TVN_SIZE (1 << TVN_BITS)
#define TVR_SIZE (1 << TVR_BITS)
#define TVN_MASK (TVN_SIZE - 1)
#define TVR_MASK (TVR_SIZE - 1)

// 256
#define TIME_WHEEL_1 TVR_SIZE
#define TIME_WHEEL_2 (1 << (TVR_BITS + TVN_BITS))
#define TIME_WHEEL_3 (1 << (TVR_BITS + 2 * TVN_BITS))
#define TIME_WHEEL_4 (1 << (TVR_BITS + 3 * TVN_BITS))
// #define TIME_WHEEL_5 (1 << (TVR_BITS + 4 * TVN_BITS))


unsigned int globalTime = 0;

static unsigned int getCurTime() {
    return globalTime;
}

struct list_head {
    struct list_head *next, *prev;
};

static inline void INIT_LIST_HEAD(struct list_head *list) {
    list->next = list;
    list->prev = list;
}

static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
    node->prev = head->prev;
    node->next = head;
    head->prev = node;
    node->prev->next = node;
}

static inline void list_replace(struct list_head *old, struct list_head *node) {
    node->next = old->next;
    node->next->prev = node;
    node->prev = old->prev;
    node->prev->next = node;
}

static inline void list_replace_init(struct list_head *old, struct list_head *node) {
    list_replace(old, node);
    INIT_LIST_HEAD(old);
}

static inline int list_empty(const struct list_head *head) {
    return head->next == head;
}

#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

#define list_for_each_entry_safe(pos, n, head, member)\
for (pos = list_entry((head)->next, typeof(*pos), member),\
n = list_entry(pos->member.next, typeof(*pos), member);\
&pos->member != (head);\
pos = n, n = list_entry(n->member.next, typeof(*n), member))


static inline void list_del(struct list_head *node) {
    struct list_head *prev = node->prev;
    struct list_head *next = node->next;
    next->prev = prev;
    prev->next = next;
}

struct timer_list {
    tw_uint id; // 定时器id
    tw_uint ticks; // 定时器触发间隔
    tw_uint expires; // 定时器触发时间
    tw_uint repeatn; // 定时器重复触发次数
    struct list_head entry;
};

struct WHEEL_ROOT {
    struct list_head vec[TVR_SIZE];
};

struct WHEEL_OTHER {
    struct list_head vec[TVN_SIZE];
};

struct TIME_WHEEL {
    struct WHEEL_ROOT tv1;
    struct WHEEL_OTHER tv2;
    struct WHEEL_OTHER tv3;
    struct WHEEL_OTHER tv4;
    struct WHEEL_OTHER tv5;
    tw_uint timer_jiffies; // 当前的定时器时间
    tw_uint index;
};

struct TIME_WHEEL* tw_create() {
    struct TIME_WHEEL *tw = (struct TIME_WHEEL*)malloc(sizeof(struct TIME_WHEEL));
    memset(tw, 0, sizeof(*tw));
    int j;
    // 初始化主轮刻度为256
    for (j = 0; j < TVR_SIZE; j++) {
        INIT_LIST_HEAD(tw->tv1.vec + j);
    }
    // 初始化其他轮刻度为64
    for (j = 0; j < TVN_SIZE; j++) {
        INIT_LIST_HEAD(tw->tv2.vec + j);
        INIT_LIST_HEAD(tw->tv3.vec + j);
        INIT_LIST_HEAD(tw->tv4.vec + j);
        INIT_LIST_HEAD(tw->tv5.vec + j);
    }
    tw->timer_jiffies = getCurTime();
    tw->index = 0;
    return tw;
};

tw_uint tw_add(struct TIME_WHEEL * tw, tw_uint ticks, tw_uint repeatn);
static void internal_add_timer(struct TIME_WHEEL *tw, struct timer_list *timer);

tw_uint tw_add(struct TIME_WHEEL * tw, tw_uint ticks, tw_uint repeatn) {
    if (ticks == 0) ticks = 1;
    struct timer_list *timer = (struct timer_list*)malloc(sizeof(struct timer_list));
    INIT_LIST_HEAD(&timer->entry);
    timer->entry.next = NULL;
    timer->id = ++tw->index;
    timer->ticks = ticks;
    timer->repeatn = repeatn;
    timer->expires = tw->timer_jiffies + ticks;
    internal_add_timer(tw, timer);
    return 0;
}

static void internal_add_timer(struct TIME_WHEEL *tw, struct timer_list *timer) {
    tw_uint expires = timer->expires;
    tw_uint idx = expires - tw->timer_jiffies;
    struct list_head *vec;
    int index = 0;
    int tvIndex = 0;
    if (idx < TIME_WHEEL_1) {
        index = expires & TVR_MASK;
        vec = tw->tv1.vec + index;
        tvIndex = 1;
    } else if (idx < TIME_WHEEL_2) {
        index = (expires >> TVR_BITS) & TVN_MASK;
        vec = tw->tv2.vec + index;
        tvIndex = 2;
    } else if (idx < TIME_WHEEL_3) {
        index = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;
        vec = tw->tv3.vec + index;
        tvIndex = 3;
    } else if (idx < TIME_WHEEL_4) {
        index = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK;
        vec = tw->tv4.vec + index;
        tvIndex = 4;
    } else if (idx < 0) {
        index = tw->timer_jiffies & TVR_MASK;
        vec = tw->tv1.vec + index;
    } else {
        index = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
        vec = tw->tv5.vec + index;
        tvIndex = 5;
    }
    printf("Add to tv:%d idx:%d index:%d expires:%d globalTime:%d timerId:%d timerTicks:%d\n", tvIndex, idx, index, timer->expires, globalTime, timer->id, timer->ticks);
    list_add_tail(&timer->entry, vec);
}

static inline int INDEX(struct TIME_WHEEL *tw, int n) {
    return (tw->timer_jiffies >> (TVR_BITS + (n) * TVN_BITS)) & TVN_MASK;
}

static int cascade(struct TIME_WHEEL *tw, struct WHEEL_OTHER *tv, int index) {
    struct timer_list *timer, *tmp;
    struct list_head tv_list;
    list_replace_init(tv->vec + index, &tv_list);
    list_for_each_entry_safe(timer, tmp, &tv_list, entry) {
        internal_add_timer(tw, timer);
    }
    return index;
}

void tw_tick(struct TIME_WHEEL *tw);
void tw_tick(struct TIME_WHEEL *tw) {
    unsigned int now = getCurTime();
    while (now >= tw->timer_jiffies) {
        struct list_head work_list;
        struct list_head *head = &work_list;
        int index = tw->timer_jiffies & TVR_MASK;
        if (!index &&
        (!cascade(tw, &tw->tv2, INDEX(tw, 0))) &&
        (!cascade(tw, &tw->tv3, INDEX(tw, 1))) &&
        !cascade(tw, &tw->tv4, INDEX(tw, 2)))
        cascade(tw, &tw->tv5, INDEX(tw, 3));
        list_replace_init(tw->tv1.vec + index, &work_list);
        while (!list_empty(head)) {
            struct timer_list *timer = list_entry(head->next, timer_list, entry);
            list_del(&timer->entry); // 从链表节点中移除
            printf("globalTime:%d timerId:%d timerTicks:%d timerExpires:%d timerRepeatn:%d timer_jiffies:%d\n", globalTime, timer->id, timer->ticks, timer->expires, timer->repeatn, tw->timer_jiffies);
            if (timer->repeatn > 1) {
                tw_add(tw, timer->ticks, --timer->repeatn);
            }
            delete timer;
        }
        ++tw->timer_jiffies;
    }
}

int main()
{
    srand((unsigned)time(NULL));
    TIME_WHEEL *tw = tw_create();
    printf("hello kitty %llu\n", TIME_WHEEL_4);
    tw_add(tw, 0, 1);
    // tw_add(tw, 1, 1);
    // tw_add(tw, 2, 5);
    tw_add(tw, 3, 8);
    tw_add(tw, 256, 2);
    tw_add(tw, 257, 1);
    // tw_add(tw, 259, 1);
    // tw_add(tw, 256*64, 1);
    // tw_add(tw, 256*64-1, 1);
    // tw_add(tw, 256*64*64, 1);
    // tw_add(tw, 256*64*64-1, 1);
    int i;
    globalTime = 0;
    for (i = 0; i < 256*64*64; ++i) {
        tw_tick(tw);
        ++globalTime;
    }
    return 0;
}

以上就是基于C语言的时间轮的实现。