时间轮设计和正则表达式使用方法- 惊觉

个人主页：小则又沐风

个人专栏：
• [数据结构]
• [竞赛专栏]
• [C语言]
• [C++]
• [Linux]
• [OJ项目]
• [MySQL]

•[GIT]

时间轮

1.什么是时间轮

我们先不来讲解什么是时间轮，我们先来讲解一下我们在写代码的时候我们可能遇到的问题。

我们需要实现一个功能：模拟实现闹钟的工作方式来定时完成一些任务，并且需要设计一个延迟执行、取消执行等功能。

我们应该怎么实现这个功能呢？

这个看起来功能看起来实现是无从下手的。

但是我们如果了解时间轮的话，我们就可以有一点头绪了。

时间轮的设计是这样的：

2.时间轮是怎么设计的

我们将会设计一个指针，这个指针将会在一个容器中移动，在指针所在的位置下的任务将会被执行。

所以我们只需要控制这个指针的移动速度就可以解决上述的问题。

具体是怎么实现的呢？

我们先来说实现的大概逻辑：

我们使用的容器是数组，然后我们的任务将会挂在这个数组上，当指针走到对应的位置的时候我们就会让这个位置的任务自动执行。

但是我们是怎么做到让任务进行自动执行的呢？

这让我想到了之前实现日志的操作了，我们是这样设计的：

我们先封装一个任务的类，然后我们将需要进行任务的回调函数设计进入这个类中，然后我们把析构函数的行为改为执行这个回调函数。

所以当我们每次的释放一个任务类的时候就是我们执行任务的时候。

所以我们指针的行为就是释放。

但是还有一个问题：

我们现在应该大概是解决了这个任务执行的逻辑了，但是怎么去实现任务的延迟呢？也就是我们收到一个信号之后我们怎么对这个任务执行的时间进行推迟呢？

首先我们明确的一点就是我们的任务执行的时间是和任务这个类实例化出的对象的生命周期有关的，所以我们的思路就是延长这个对象的生命周期。

所以我们将会引入智能指针。

首先我们的任务对象将会是一个new出来的，我们让一个智能指针拥有她，这样我们的对象的销毁的条件就是持有这个对象的智能指针的个数是0。

所以当我们进行延长执行任务的时间的时候我们的操作就是增加拥有对象智能指针的个数。

这样我们就可以做到延迟任务了，因为增加了引用计数之后我们第一次释放就不会引起析构函数。

下面是一个简单的示例代码：

std::shared_ptr<int> p=std::make_shared<int>(42);
std::shared_ptr<int> p1=p;

3.解决细节问题

现在我们大体的逻辑已经阐述明白了，现在需要解决的就是一些细节上的问题了。

首先我们上述的逻辑容器选择是一个数组，但是更具体地是我们使用的是二维数组，因为一维的数组只能挂上一个任务。

其次我们如果设计的任务是在30s后执行的话，我们该怎么进行设计呢？

我们就把这个数组地大小开辟到30.

但是当我们的任务需要在一天后执行呢？

难道我们需要开辟的数组空间需要24*60*60这么大的嘛？

不是的。

我们的设计可以更改成这样的：

我们设计三个数组。

第一个是秒数组（大小60）

第二个是分数组（大小60）

第三个是时数组（大小24）

我们的指针现在时数组中运动每次经过一个时的空间的时候就会检查这个小时内有没有挂有任务。

如果有就进行进入分数组，进行移动，然后停在一个有任务的空间，然后进入到秒数组中。

4、代码实现

#include<iostream>
#include<vector>
#include<unordered_map>
#include <functional>
#include <memory>
#include <unistd.h>
#include <cstdint>


using TaskFun =std::function<void()>;
using ReleaseFun =std::function<void()>;
class Task
{
    public:
    Task(uint64_t id,uint32_t timeout,const TaskFun& fun)
    :_id(id)
    ,_timeout(timeout)
    ,_func(fun)
    ,_iscancel(false)
    {
    }
    ~Task()
    {
        if(_iscancel==false)
        {
            _func();
        }
        _release();
    }
    void Setcancel()
    {
        _iscancel=true;
    }
    void SetRelease(const ReleaseFun &cb)
    {
        _release=cb;
    }
    uint32_t Timeout()
    {
        return _timeout;
    }
    private:
    uint64_t _id; //任务对象的ID；
    uint32_t _timeout; //时间超限的设置；
    bool _iscancel; //是否取消任务的执行；
    TaskFun _func; //任务的回调函数；
    ReleaseFun _release; //清除在时间轮中的信息；
};

class TimeWhell
{
    public:

    void RvmTimer(uint64_t id)
    {
        auto it=_timer.find(id);
        if(it!=_timer.end())
        {
            _timer.erase(it);
        }
    }
    public:
    void addtimewhell(uint64_t id,uint32_t timeout,const TaskFun& fun)
    {
        TaskPtr p(new Task(id,timeout,fun));
        p->SetRelease(std::bind(&TimeWhell::RvmTimer,this,id));
        _timer[id]=WeakPtr(p);
        int pos = (ticket+timeout)%capacity;
        _Timewhell[pos].push_back(p);
    }
    void flush(uint64_t id)
    {
        auto it=_timer.find(id);
        if(it!=_timer.end())
        {
           TaskPtr p1=it->second.lock();
           if(p1)
           {
            int pos =(ticket+p1->Timeout())%capacity;
           _Timewhell[pos].push_back(p1);
           }
        }
        return;
    }
    void cancel(uint64_t id)
    {
        auto it =_timer.find(id);
        if(it!=_timer.end())
        {
            TaskPtr p=it->second.lock();
            if(p)
            {
                p->Setcancel();
            }
        }
        return;
    }
    void Run()
    {
        ticket=(ticket+1)%capacity;
        _Timewhell[ticket].clear();
    }
    TimeWhell()
    :ticket(0)
    ,capacity(60)
    ,_Timewhell(capacity)
    {
    }
    private:
    using TaskPtr = std::shared_ptr<Task>;
    using WeakPtr = std::weak_ptr<Task>;
    int ticket;//指针;
    int capacity;//大小
    std::vector<std::vector<TaskPtr>> _Timewhell;
    std::unordered_map<uint64_t,WeakPtr> _timer;
};

正则表达式的介绍

1、什么是正则表达式

简单来说这个就是我们来解决字符串处理的工具。

更加具体的来说就是这个工具能够在我们提供的字符串中提取到我们想要的部分。

那么这有什么用呢？

实际上这个工具的用处超级的大。

我们下面就以解析一个HTTP的ULR为例子来剖析这个工具的使用。

2、如何使用正则表达式

在我们进行编写网络通信服务器的时候，尤其当我们使用的协议是HTTP协议的时候，我们需要有一个工作就是需要对用户请求的URL进行分析处理。

但是我们自己对这个字符串进行处理的时候，我们难免都会觉得头痛。

所以我们需要寻求一个工具来辅助我们完成这个工作。

我们依赖的工具就是这个正则表达式。

我们就以解析这个字符串为例子

"get /baidu/login?user=xiaoming&pass=123123 HTTP/1.1\r\n"

首先呢，我们想要使用这个工具就要包含这个工具的头文件。

#include<regex>

三步学会使用正则表达式

1.创建一个smatch对象

这个对象就是我们之后按我们设定的需求提取字符串之后存储的地方。

2.设置我们的提取要求

这是我们使用正则表达式来提取字符串的最重要的步骤了。

std::regex re( pattern, flags );

第一个参数中需要我们自己来设计提取字符串的方法。

第二个参数需要我们来设置提取字符串的时候需要遵守的规则。

3，根据上述的准备和目标字符串进行提取

bool ret = std::regex_match(str,smatch,re)

这样我们就完成了。

下面来详细讲解一下设置提取要求这一步。

 std::regex res("(GET|HEAD|POST|PUT|DELETE) .*",std::regex::icase);

在这里我们的设置是什么意思呢？

就是匹配括号里面的任意一个，因为我们的URL第一个可能是其中的一个。

后面的标记位设置是不区分大小写。

那么后面的我们应该怎么提取呢？

([^?]*) [^?]代表的是提取非？的字符，后面的*表示的是可以及进行多次的匹配。
\\?(.*) 提取非换行符的字符
(HTTP\\/1\\.[01]) 提取HTTP/1.0或者HTTP/1.0。([01])代表的是匹配其中的一个。

但是我上面的代码的原字符串是不包含末尾的换行符的。

现在我们来加上去。

  std::regex res("(GET|HEAD|POST|PUT|DELETE) ([^?]*)\\?(.*) (HTTP\\/1\\.[01])(?:\r\n)?",std::regex::icase);

这样的(?:)?

(?:)表示匹配某个格式字符串，但是不提取,

最后的？表示的是匹配前边的表达式0次或1次

因为有的URL是没有？后面连续的一串的，所以我们需要添加上一个匹配0次或1次。

 std::regex res("(GET|HEAD|POST|PUT|DELETE) ([^?]*)(?:\\?(.*))? (HTTP\\/1\\.[01])(?:\n|\r\n)?",std::regex::icase);

这是我们简单的提取的设置。

下面是进行测试的代码：

#include<iostream>
#include<regex>
int main()
{
    std::string str="get /baidu/login?user=xiaoming&pass=123123 HTTP/1.1\r\n";
    std::smatch matches;
    std::regex res("(GET|HEAD|POST|PUT|DELETE) ([^?]*)(?:\\?(.*))? (HTTP\\/1\\.[01])(?:\n|\r\n)?",std::regex::icase);
    bool ret = std::regex_match(str,matches,res);
    if (ret == false) {
        return -1;
    }
    std::string method = matches[1];
    std::transform(method.begin(), method.end(), method.begin(), ::toupper);
    std::cout << method << std::endl;
    for (int i = 0; i < matches.size(); i++) {
        std::cout << i << " : ";
        std::cout << matches[i] << std::endl;
    }
    return 0;
}

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/jiaomorning/article/details/166372637

时间轮设计和正则表达式使用方法

时间轮