二进制的叮当喵

WebServer项目——timer详解 定时器的介绍 为了提高Web服务器的效率，我们考虑给每一个HTTP连接加一个定时器。 定时器给每一个HTTP连接设置一个过期时间，然后我们定时清理超过过期时间的连接，会减少服务器的无效资源的耗费，提高服务器的运行效率。 我们还需要考虑一下如何管理和组织这些定时器。设置定时器的主要目的是为了清理过期连接，为了方便找到过期连接，首先考虑使用优先队列，按过期时间排序，让过期的排在前面就可以了。但是这样的话，虽然处理过期连接方便了，当时没法更新一个连接的过期时间。 最后，选择一个折中的方法。用vector容器存储定时器，然后在这之上实现堆结构，这样各个操作的代价就得到了相对均衡。 定时器的组成 定时器结点 为了实现定时器的功能，我们首先需要辨别每一个HTTP连接，每一个HTTP连接会有一个独有的描述符（socket），我们可以用这个描述符来标记这个连接，记为id。同时，我们还需要设置每一个HTTP连接的过期时间。 为了后面处理过期连接的方便，我们给每一个定时器里面放置一个回调函数，用来关闭过期连接。 为了便于定时器结点的比较，主要是后续堆结构的实现方便 ...

WebServer项目——HTTPresponse详解 HTTPresponse简介 这个类和HTTPrequest相反，是给相应的连接生成相应报文的。HTTPrequest是解析请求行，请求头和数据体，那么HTTPresponse就是生成请求行，请求头和数据体。 HTTPresponse的组成 所需变量和自定义的数据结构 首先，我们需要一个变量code_来代表HTTP的状态。 在HTTPrequest中解析到的路径信息是相对路径，我们还需要补全，所以需要一个变量path_代表解析得到的路径，一个变量srcDir_表示根目录，除此之外，我们还需要一个哈希表提供4XX状态码到响应文件路径的映射。 我们在实现所需函数的过程中，需要知道HTTP连接是否处于KeepAlive状态，所以用一个变量isKeepAlive_表示。 由于使用了共享内存，所以也需要变量和数据结构指示相关信息： 12char* mmFile_;struct stat mmFileStat_; 所以，总结如下： 123456789101112int code_;bool isKeepAlive_;std::string ...

WebServer项目——HTTPrequest详解 HTTPrequest简介 这个类主要的功能是解析HTTP的请求信息。 HTTP的请求包括：请求行(request line)、请求头部(header)、空行 和 请求数据 四个部分组成。 抓包的request结构如下： 1234567GET /mix/76.html?name=kelvin&password=123456 HTTP/1.1Host: www.baidu.com Upgrade-Insecure-Requests: 1User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_11_5) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/56.0.2924.87 Safari/537.36Accept: text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,*/*;q=0.8Accept-Encoding: gzip, deflate, s ...

WebServer项目——HTTPconnection详解 HTTPconnection简介 这个类就是对一个HTTP连接的抽象，负责对一个HTTP请求的解析和回复，以及提供读写的接口。 这个读写接口的底层就是靠buffer缓冲区来实现的，这个缓冲区提供了读写的接口。但是，写借口照样用了分散写的方法实现。然后就是对从socket连接中读取的数据进行解析，以及对请求做出响应。这部分的实现主要依赖于HTTPrequest和HTTPresponse来完成。 HTTPconnection组成 其中的构造函数和析构函数略去不谈，缺省就可以。 所需变量和自定义的数据结构 对于一个HTTP连接而言，我们需要用变量fd_唯一地标记它，用isClose_表示它是否需要关闭这个连接，已备后续关闭连接的函数的判断。一个HTTP连接还需要读写数据，所以给每一个HTTP连接定义一个读缓冲区和一个写缓冲区。在解析请求和响应请求的时候，我们借助HTTPrequest和HTTPresponse完成，所以也需要各种定义一个这两种变量。 总结一下，如下所示： 12345678int fd_; ...

WebServer项目——epoller详解 epoller的简介 web服务器需要与客户端之间发生大量的IO操作，这也是性能的瓶颈之一。在这个项目中，我们用IO多路复用技术中的epoll来尽可能地提高一下性能。 epoll区别于select和poll，不需要每次轮询整个描述符集合来查找哪个描述符对应的IO已经做好准备了，epoll采用事件驱动的方式，当有事件准备就绪后就会一次返回已经做好准备的所有描述符集合。 epoll提供的程序接口有： 1int epoll_create(int size); 在内核中创建epoll实例并返回一个epoll文件描述符。 在最初的实现中，调用者通过 size 参数告知内核需要监听的文件描述符数量。如果监听的文件描述符数量超过 size, 则内核会自动扩容。而现在 size 已经没有这种语义了，但是调用者调用时 size 依然必须大于 0，以保证后向兼容性。 1int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event); 向 epfd 对应的内核epoll 实例添加、修改或删除对 ...

WebServer项目——buffer详解 buffer缓冲区的介绍 在这个项目中，客户端连接发来的HTTP请求以及回复给客户端所请求的资源，都需要缓冲区的存在。其实，在操作系统的内核中就有缓冲区的实现，read()/write()的调用就离不开缓冲区的支持。但是，在这里用缓冲区的实现不太方便。所以，在这个项目中实现了一个符合需要的缓冲区结构。 在C++的STL库中，vector容器其实就很适合作为缓冲区。为了能够满足我们的需要，我们以vector容器作为底层实体，在它的上面封装自己所需要的方法来实现一个自己的buffer缓冲区，满足读写的需要。 buffer缓冲区的组成 省去每一个类必有的构造和析构函数，还需要以下部分： buffer的存储实体 缓冲区的最主要需要是读写数据的存储，也就是需要一个存储的实体。自己去写太繁琐了，直接用vector来完成。也就是buffer缓冲区里面需要一个： 1std::vector<char>buffer_; buffer所需要的变量 由于buffer缓冲区既要作为读缓冲区，也要作为写缓冲区，所以我们既需要指示当前读到哪里了，也需要指示当前 ...

用C++实现的高性能WEB服务器，经过webbenchh压力测试可以实现上万的QPS 项目地址：https://github.com/Aged-cat/WebServer 功能 利用IO复用技术Epoll与线程池实现多线程的Reactor高并发模型； 利用正则与状态机解析HTTP请求报文，实现处理静态资源的请求； 利用标准库容器封装char，实现自动增长的缓冲区； 基于堆结构实现的定时器，关闭超时的非活动连接； 改进了线程池的实现，QPS提升了45%+； 项目详解 WebServer项目——buffer详解 WebServer项目——epoller详解 WebServer项目——timer详解 WebServer项目——threadpool详解 WebServer项目——HTTPconnection详解 WebServer项目——HTTPrequest详解 WebServer项目——HTTPresponse详解 WebServer项目——webserver详解 环境要求 Linux C++11 项目启动 123mkdir binmake./bin/myserver 压力测试 1 ...

手撕堆排序 题目描述 给你一个整数数组 nums，请你运用堆排序将该数组升序排列。 示例 1： 12输入：nums = [5,2,3,1]输出：[1,2,3,5] 示例 2： 12输入：nums = [5,1,1,2,0,0]输出：[0,0,1,1,2,5] 提示： 1 <= nums.length <= 50000 -50000 <= nums[i] <= 50000 算法思路 运用堆排序在原数组的基础上完成排序的思路主要分为两步： 建立大根堆； 然后将大根堆最大的元素，也就是第一个元素，与大根堆中最后一个元素进行调换，然后将剩下的len - 1个数重新调整为大根堆。重复这个过程，最后会得到一个有序的序列。 然后主要的过程分为两个，一个是建立大根堆的过程，一个是调整大根堆的过程。 首先是向下调整的过程： 对于下标为index的元素，如果要将这个元素以下的元素重新调整为大根堆，那么就需要将index的元素与它的两个子节点中较大元素进行比较。如果num[index] < num[maxChild]，那么就需要调换元素。然后通过这个方法，将这个元素以下 ...

剑指 Offer 36. 二叉搜索树与双向链表 题目描述 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 为了让您更好地理解问题，以下面的二叉搜索树为例： 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。 下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。 特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。 解题思路 这道题要将一颗二叉搜索树转变为有序链表，而二叉搜索树的中序遍历就是有序的，所以我们遍历结点的方法就可以选用中序遍历的方法。 然后就是关键的转变过程。由于需要转化为双向链表，所以需要一个指针标记当前指针的前一个结点，记为pre。由于需要构造循环链表，我们再用一个指针标记头结点。 当整颗树完成转化之后，要将头尾指针连接起来。头结点我们可以通过判断pre ...

二叉树前序中序后序层序遍历总结 相关题目 No. 144 二叉树的前序遍历 No. 94 二叉树的中序遍历 No. 145 二叉树的后序遍历 No. 102 二叉树的层序遍历 解法总结 关于二叉树遍历的概念不再赘述，直接开始怼题目。 先对前序遍历、中序遍历和后序遍历做总结，层序遍历拎出来单独说。 关于二叉树的定义如下： 12345678struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}}; 递归解法 前序 ...