理解汇编代码和它与高级语言的联系

我们知道,现代编程很少有人会去用低级语言来编写代码了。因为写代码的效率很低,而且就算编写出了程序,可以在自己的机器上面跑,也不一定可以在其他的计算机上面跑,也就是说可移植性很差,与特定的机器有关(例如,就算都是x86,每个平台上语法也会不一样)。

而使用高级语言的话,通常情况下,现代的优化编译器产生的代码至少与一个熟练的汇编语言程序员手工编写的代码一样有效。最大的优点是,用高级语言编写的程序可以在很多不同的机器上编译和执行,而汇编代码则是与特定机器密切相关。但是这不意味着我们不需要知道汇编语言。我们必须了解典型的编译器在将C程序结构变换成机器代码时所做的转换。相对于C代码表示的计算操作,优化编译器能够重新排列执行顺序,消除不必要的计算,用快速操作替换慢速操作,甚至将递归计算变换成迭代计算

好的,让我们以C语言为例,了解高级语言和汇编的关系:

1
2
3
4
5
6
7
int accum = 0;

int sum(int x, int y) {
int t = x + y;
accum += t;
return t;
}

我们把它命名为hht.c,然后使用gcc编译器来编译它,在shell中使用如下命令:

1
gcc -o1 -S hht.c

其中的-o1参数是告诉编译器使用第一个优化(从得到的程序性能方面考虑,第二级 -o2 被认为是较好的选择)。其中的-S指定生成汇编代码。之后,我们可以看到一个汇编文件:

我们查看它:

如图所示,大多数GCC生成的汇编代码都有一个字符后缀,其中pushqmovl等等指令后面以q、l结尾。这些后缀是操作数大小的提示符。例如,数据传送指令有三种变体:movb(传送字节)、movw(传送字)和movl(传送双字,注意,汇编代码使用l表示4字节整数和8字节双精度浮点数。这不会产生歧义,因为浮点数使用的是一组完全不同的指令和寄存器)

所有以.开头的行都是指导汇编器和链接器的命令。通常可以忽略这些行。

每条汇编代码都对应一条机器指令。比如,pushq指令表示将寄存器%rbq的内容压入程序栈。这段汇编代码没有所有关于局部变量名或数据类型的信息。我们还看到了一个对全局变量accum的引用,这是因为编译器还不能确定这个变量会放在存储器中的哪个位置。

(未完,happy no ending)

485. Max Consecutive Ones (leetcode)

题目描述

Given a binary array,
find the maximum number of consecutive 1s in this array.

Example 1:
Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.

The maximum number of consecutive 1s is 3.

Note:

The input array will only contain 0 and 1.
The length of input array is a positive integer and will not exceed 10,000

题目大概的意思就是找到最多有几个连续的1

这题挺水的,但是开始的时候,我想了一下用这个数据结构,毕竟栈有个很重要的功能就是可以反悔,并且删除元素也很快,pop一下就好了。而在这题,需要反悔的地方就是如果有一个更多连续的1,那么,把连续1的个数压栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int n = nums.size();
stack<int> s;
int sum_max = 0;

for (int i = 0; i < n;i++) {
if (nums[i] == 1) {
sum_max++;
}
else if (nums[i] == 0) {
if (!s.empty()) {
if (sum_max > s.top()) {
s.pop();
s.push(sum_max);
}
}
else {
s.push(sum_max);
}

sum_max = 0;
}
}

if (!s.empty()) {
if (sum_max > s.top()) {
return sum_max;
}
else {
return s.top();
}
}
else {
return sum_max;
}
}
};

可以看到,这段代码很难看?因为是有太多的if 和 else了,原因就是我需要判断栈是否为空导致。而且,我在交换比较最大值的时候,也用了if else,实际上直接Max = max(Max, otherNum); 即可。

所以需要换了思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution  
{
public:
int findMaxConsecutiveOnes(vector<int>& nums)
{
int Max = 0, cnt = 0;
for(auto n:nums)
{
if(n == 1)
{
++cnt;
}
else
{
Max = max(Max, cnt);
cnt = 0;
}
}
Max = max(Max, cnt);
return Max;
}
};

总结

1、栈、队列等等数据结构在存放数据量很小的时候,可以不用使用。

2、比较两个最大值的时候,使用max()函数,不要自己写判断语句,显得代码难看。

并行和并发

来自:http://www.jianshu.com/p/202abfcb7b96

总体概念

并发

在单核 CPU 系统中,系统调度在某一时刻只能让一个进程运行,虽然这种调度机制有多种形式(大多数是时间片轮巡为主),但无论如何,要通过不断切换需要运行的进程让其运行的方式叫并发

并行

在多核 CPU 系统中,可以让两个以上的进程同时运行在不同的物理核心上,这种运行的方式就是并行

区别

  • 并发在微观上不是同时执行的,只是把时间分成若干段,使多个进程快速交替的执行,因为 CPU 计算速度很快,从宏观上看,好像这些进程都在同一个时间点执行
  • 并行是真正的细粒度上的同时进行:既同一时间点上同时运行着多个进程

多进程

多进程操作系统,指的是各种进程之间切换执行

超线程技术

通过采用特殊的硬件指令,可以把一个物理内核模拟成两个逻辑内核,在单处理器中实现线程级并行计算,从而实现在单处理器上模拟双处理器的效能。但它并不象两个真正的 CPU 那样,每个 CPU 都具有独立的资源。当两个线程都同时需要某一个资源时,其中一个要暂时停止,并让出资源,直到这些资源闲置后才能继续。因此超线程的性能并不等于两颗 CPU 的性能

用C++写一个服务器吧(二)

在这个系列的第一篇文章里面,我们说到了让浏览器来接收服务器发送给它的资源,并且显示出这个HTML页面。然后,结果并没有如预期的那样。在这篇文章,我们将解决这个问题。

好的,现在我们回忆一下第一篇文章。我们已经看到了,HTML文件里面的内容已经被我们完整的获取了。所以说,不是因为HTML的内容导致失败的。

然后,我们也看到了浏览器显示malformed HTTP status code "/index.html"这条信息。也就是说问题是出在了服务器那里。

我们再来审查元素看看:

发现响应出问题了。

遵循协议

在这个系列的第一篇文章里,我们谈到了协议这部分内容。而协议顾名思义就是一套标准、一套规范。谁不遵循这个规范,我就不按照你的意思去做。

关于涉及到HTTP协议的那部分内容出现在了两个地方:

我们发现,第二张图片中的响应头信息是对的。只是少了一些具体的信息,我们把她完善一些:

1
2
3
4
sprintf(buff, "HTTP/1.0 200 OK\r\n");
sprintf(buff, "%sServer: HHTWS Web Server\r\n", buff);
sprintf(buff, "%sContent-length: %d\r\n", buff, file_size);
sprintf(buff, "%sContent-type: %s\r\n\r\n", buff, file_type);

然后我们看看第一张图片发送的信息。

因为它是从表示连接的socket文件描述符中读取信息的,因此,读到的自然也就是请求头的信息。而此时,我们又把请求头中的信息发送给浏览器,显然是不符合响应头的要求的。因此,我们把这一行删掉,来看看结果:

OK,美丽的HTML页面出现了!!

我们来审查一下元素,看看

这些不正是我们在代码里面写的响应头吗?

OK。接下来做些小小的优化。

优化

虽然write()不太可能返回一个部分写的结果。而且,对write系统调用来说没有EOF情况。对于普通文件,除非发生一个错误,否则write将保证写入所有的请求。

所以,对于普通文件,不需要进行循环写入了。然后,对于其他类型–例如套接字–大概得有个循环来保证你真的写入了所有请求的字节

1
2
3
4
5
6
7
8
9
10
11
12
13
int makesure_write(int connect_fd, void* buff, int n) {
int remain_num = n;
int success_write_num = 0;
char* buff_current_postition = (char*)buff;

while (remain_num > 0) {
success_write_num = write(connect_fd, buff_current_postition, remain_num);
remain_num -= success_write_num;
buff_current_postition += success_write_num;
}

return n - remain_num;
}

好了,这次的教程结束。happy ending

496. Next Greater Element(leetcode)

题目描述

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2.
Find all the next greater numbers for nums1’s elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2.
If it does not exist, output -1 for this number.

简单的说就是对于第一个数组中的每一个数字,我们都去第二个数组里面找,直到找到第一个比它大的数字,然后放入一个容器里面。如果没有找到,就把-1放入容器里面。

Input: nums1 = [4,1,0], nums2 = [1,0,4,2].
Output: [-1,4,4]
    Explanation:
    For number 4 in the first array, 
    you cannot find the next greater number for it in the second array, 
    so output -1.

    For number 1 in the first array, 
    the next greater number for it in the second array is 4.

    For number 0 in the first array, 
    there is no next greater number for it in the second array, 
    so output 4.

Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
    For number 2 in the first array, 
    the next greater number for it in the second array is 3.

    For number 4 in the first array, 
    there is no next greater number for it in the second array, 
    so output -1

暴力破解

暴力破解,也就是没有利用数据之间的规律。毫无技巧可言,只需要细心一些即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
std::vector<int>::iterator iter;
std::vector<int> v;
for (std::vector<int>::iterator i = findNums.begin(); i != findNums.end(); ++i) {
iter = find(nums.begin(), nums.end(), *i);
int front = *iter;
int next = *(++iter);
--iter;
if ((iter != nums.end()) && (iter != --nums.end())) {
std::vector<int>::iterator j;
for (j = iter; j != nums.end(); ++j) {
if (*j > *iter) {
v.push_back(*j);
break;
}
}
if (j == nums.end()) {
v.push_back(-1);
}
}
else {
v.push_back(-1);
}
}

return v;
}
};

(建议对vector容器的遍历用下标来访问,而不是我上面的那样用迭代器来操作)

可以看出,这样的代码虽然可以解出来,但是太烂了,看起来和那个啥一样。所以我们就需要一种新的思路。

优化方案一

首先,我们仔细分析一下题目。题目说了第一个数组是第二个数组的子集对吧。那么,这就意味着我一定可以在第二个数组里面找到第一个数组中的元素。正是因为有了这个一定可以找到的特点,我们可以使用哈希表。让第二个数组中的元素值和它所在的位置做一个映射。这样做了之后,当我们需要在第二个数组里面查找第一个数组中的数据的时候,我们就可以以O(1)的时间复杂度找到这个元素在第二个数组中的位置。然后,我们只需要对它后面的元素进行遍历即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
vector<int> res(findNums.size());
unordered_map<int, int> m;
for (int i = 0; i < nums.size(); ++i) {
m[nums[i]] = i; // 做一个映射的关系
}
for (int i = 0; i < findNums.size(); ++i) {
res[i] = -1;
int start = m[findNums[i]];
for (int j = start + 1; j < nums.size(); ++j) {
if (nums[j] > findNums[i]) {
res[i] = nums[j];
break;
}
}
}

return res;
}
};

这样的话,是不是代码更清晰易懂了?

优化方案二

在优化方案一中,我们是利用哈希表在第二个数组中找第一个数组中的元素。但是我们并没有立马得出这个元素的后面出现的第一个比这个元素大的元素,那么我们可以想,是否能够利用哈希表来直接得到这个元素后面出现的第一个比这个元素大的元素呢?

我们的做法是把第二个数组中的元素和该元素后面出现的第一个最大值做一个映射。

那么为了减少无效的遍历(因为,这个元素前面的元素是没有意义的。例如:有个数组[1,3,4,2],当我们去查找4这个元素后面出现的第一个比4大的元素的时候,我们去遍历1和3是没有意义的。我们称之为无效的遍历)。所以我们使用栈这个数据结构帮我们解决掉无效的遍历,简化了搜索空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
vector<int> res;
stack<int> st;
unordered_map<int, int> m;
for (int num : nums) {
while (!st.empty() && st.top() < num) {
m[st.top()] = num; st.pop();
}
st.push(num);
}
for (int num : findNums) {
res.push_back(m.count(num) ? m[num] : -1);
}
return res;
}
};

总结

所以,遇到这种查找一个元素是否在这个数组(数组中的元素不重复)里面的问题,我们可以用哈希表来处理。首先对这个数组进行元素和位置的映射,然后,无论你要查找哪个元素,我都可以轻而易举的找到,而不用每次都去遍历来查找。

栈这种数据结构可以寻找相邻的更大或者更小的数字,简化搜索空间。

669. Trim a Binary Search Tree(leetcode)

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
Given a binary search tree and the lowest and highest boundaries as L and R, 
trim the tree so that all its elements lies in [L, R] (R >= L).
You might need to change the root of the tree,
so the result should return the new root of the trimmed binary search tree.

Example 1:
Input:
1
/ \
0 2

L = 1
R = 2

Output:
1
\
2

Example 2:
Input:
3
/ \
0 4
\
2
/
1

L = 1
R = 3

Output:
3
/
2
/
1

题目大意就是删除那些不在范围内的节点,同时保证这棵树还是一棵二分搜索树

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int L, int R) {
if (NULL == root) {
return NULL;
}

if ((root->val >= L) && (root->val <= R)) {
root->left = trimBST(root->left, L, R);
root->right = trimBST(root->right, L, R);
return root;
}

if (root->val < L) {
return trimBST(root->right, L, R); // 如果这个节点小于L,那么这个节点和它的左子树都被丢弃
}
if (root->val > R) {
return trimBST(root->left, L, R); // 如果这个节点大于R,那么这个节点和它的右子树都被丢弃
}
}
};

关键就是利用二叉树的性质:左子树中所有的节点都比父节点小,右子树所有的节点都比父节点大。

Add Two Numbers

题目描述

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Input: (1 -> 8) + (0)
Output: 1 -> 8

题目的意思就是模拟两个数的加法运算

思路

1、使用一个新的链表来存放这些加好的数字。

2、先让两个数字对应的部分相加,然后再加上上一次相加的进位(如果没有进位,那么进位实际上就是0),得到一个新的数字。

3、如果这个数字大于9,那么就要对这个数字进行进位了。其实就是分出个位和十位。保留个位,而十位留给下一次相加的数。

4、关键是要考虑两个链表不一样长的情况(也就是数字的位数不同的情况)。为了好操作,我们可以把短的链表用0来填充。而且由于链表的长度不一样,很容易会让本来就是NULL的节点往后面指。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *headNode = new ListNode(0), *currentNode = headNode;
ListNode *p = l1, *q = l2; // 一般我们不会去直接操作传过来的参数,所以另外保存它们
int carry = 0, x, y, sum;
while (p != NULL || q != NULL) {
x = (p != NULL) ? p->val : 0;
y = (q != NULL) ? q->val : 0;

sum = x + y + carry;
currentNode->next = new ListNode(sum % 10);
currentNode = currentNode->next;
carry = sum / 10;

if ((p != NULL) && (p->next != NULL)) {
p = p->next;
}
else {
p = NULL;
}

if ((q != NULL) && (q->next != NULL)) {
q = q->next;
}
else {
q = NULL;
}
}

if (carry > 0) {
currentNode->next = new ListNode(carry);
}

return headNode->next;
}
};

I/O多路复用之select()系统调用

为什么要使用I/O多路复用

应用程序常常需要在多于一个文件描述符上阻塞:例如响应键盘输入(stdin)、进程间通信以及同时操作多个文件。

在不使用线程(怎么理解线程的存在呢?我么可以举一个例子。当我们运行qq这个进程的时候,是可以执行不同的任务的。例如,我们可以在使用qq发送消息的同时来收发文件。而这两个不同的任务就是利用线程来完成的),尤其是独立处理每一个文件的情况下,进程无法在多个文件描述符上同时阻塞。如果文件都处于准备好被读写的状态,同时操作多个文件描述符是没有问题的。但是,一旦在该过程中出现一个未准备好的文件描述符(就是说,如果一个read()被调用,但没有读入数据),则这个进程将会阻塞,不能再操作其他文件。可能阻塞只有几秒钟,但是应用无响应也会造成不好的用户体验。然而,如果文件描述符始终没有任何可用数据,就可能一直阻塞下去。

如果使用非阻塞I/O,应用可以发起I/O请求并返回一个特别的错误,从而避免阻塞。但是,从两个方面来讲,这种方法效率较差。首先,进程需要以某种不确定的方式不断发起I/O操作,直到某个打开的文件描述符准备好进行I/O。其次,如果程序可以睡眠的话将更加有效,可以让处理器进行其他工作,直到一个或更多文件描述符可以进行I/O时再唤醒。

三种I/O多路复用方案

I/O多路复用允许应用在多个文件描述符上同时阻塞,并在其中某个可以读写时收到通知。这时I/O多路复用就成了应用的关键所在。

I/O多路复用的设计遵循一下原则:

1、I/O多路复用:当任何文件描述符准备好I/O时告诉我

2、在一个或更多文件描述符就绪前始终处于睡眠状态

3、唤醒:哪个准备好了?

4、在不阻塞的情况下处理所有I/O就绪的文件描述符

5、返回第一步,重新开始

Linux提供了三种I/O多路复用方案:selectpollepoll

先来说说select()

select()系统调用的声明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <sys/time.h>
#include <sys/types.h>
#include <unistd.h>

/*
作用:通知执行了select()的进程哪个Socket或文件可读
返回值:负值:select错误,见ERRORS。
正值:某些文件可读写或出错
0:等待超时,没有可读写或错误的文件
*/

int select (int n,
fd_set *readfds,
fd_set *writefds,
fd_set *exceptfds,
struct timeval *timeout
);

其中fd_setselect机制中提供的一种数据结构,实际上是一long类型的数组,每一个数组元素都能与一打开的文件句柄(不仅是socket句柄,还是其他文件或命名管道或设备句柄)建立联系,建立联系的工作由程序员完成,当调用select()时,由内核根据IO状态修改fd_set的内容,由此来通知执行了select()的进程哪一个socket或文件发生了可读或可写事件

监测的文件描述符可以分为三类,分别等待不同的事件。监测readfds集合中的文件描述符,确认其中是否有可读数据(也就是说,确认好了的文件描述符的读操作可以无阻塞的完成)。监测writefds集合中的文件描述符,确认其中是否有一个写操作可以不阻塞地完成。监测exceptfds中的文件描述符,确认其中是否有出现异常发生或者出现带外数据(这种情况只适用于套接字)。指定的集合可能为空(NULL)。相应的,select()则不对此类事件进行监测。

成功返回时,每个集合只包含对应类型的I/O就绪的文件描述符。举个例子,readfds集合中有两个文件描述符:7和9.当调用返回时,如果7还在集合中,该文件描述符就准备好进行无阻塞I/O了。如果9已不在集合中,它可能在被读取时会发生阻塞。出现错误返回-1

第一个参数n,等于所有集合中文件描述符的最大值加1。这样,select()的调用者需要找到最大的文件描述符值,并将其加1后传给第一个参数。

timeout参数是一个指向timeval结构体的指针,定义如下:

1
2
3
4
5
#include <sys/time.h>
struct timeval {
long tv_sec; /* seconds */
long tv_usec; /* microseconds */
};

如果这个参数不是NULL,即使此时没有文件描述符处于I/O就绪状态,select()调用也将在tv_sec秒、tv_usec微秒后返回。即 select在timeout时间内阻塞,超时时间之内有事件到来就返回了,否则在超时后不管怎样一定返回

如果时限中的两个值都是0,调用会立即返回,并报告调用时所有事件对应的文件描述符均不可用,且不等待任何后续事件。

若将NULL以形参传入,即不传入时间结构,就是将select置于阻塞状态,一定等到监视文件描述符集合中某个文件描述符发生变化为止

举个select()的小例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdio.h>
#include <sys/time.h>
#include <sys/types.h>
#include <unistd.h>

#define TIMEOUT 5 /* 选择超时秒数 */
#define BUF_LEN 1024 /* 读缓冲区字节 */

int main(int argc, char const *argv[])
{
struct timeval tv;
fd_set readfds;
int ret;

/* 等待输入 */
FD_ZERO(&readfds); // 把writefds集合中的所有文件描述符移除
FD_SET(STDIN_FILENO, &readfds); // 向writefds集合中添加文件描述符STDIN_FILENO。STDIN_FILENO就是标准输入设备(一般是键盘)的文件描述符。它的值为0

/* 设置等待为5秒 */
tv.tv_sec = TIMEOUT;
tv.tv_usec = 0;

/* 在指定的tv时间内阻塞 */
ret = select(STDIN_FILENO + 1, &readfds, NULL, NULL, &tv); // 通知执行了select()的进程哪个Socket或文件可读

if (ret == -1) {
perror("select");
return 1;
}
else if (!ret) {
printf("%d 秒 已经过去了. \n", TIMEOUT);
return 0;
}

if (FD_ISSET(STDIN_FILENO, &readfds)) { // 测试给定的文件描述符在不在给定的集合中。检查fdset联系的文件句柄fd是否可读写,当>0表示可读写
char buf[BUF_LEN + 1];
int len;
/* 保证没有阻塞 */
len = read(STDIN_FILENO, buf, BUF_LEN);
if (len == -1) {
perror("read");
return 1;
}
if (len) {
buf[len] = '\0';
printf("read: %s\n", buf);
}
return 0;
}
fprintf(stderr, "This should not happen!\n");

return 0;
}

让我们执行这段代码之后,等待5秒:

可以看到,在这5秒内,进程是处于阻塞状态的(因为文件描述符的状态没有发生变化)

现在让我们执行完这段代码后输入一些内容:

上面这个例子虽然只是检测了一个文件描述符(因此不是多路复用),但是对于select()这个系统调用的用法已经很清晰了。

用C++写一个Web服务器吧(一)

获取本服务器完整的源码

首先,要实现一个Web服务器,必须要有一定的理论基础,才知道要做什么事情(如何写代码)

理论知识

首先,我们要知道什么是客户端和服务器

客户端

与服务器相对应,为客户提供本地服务的程序。除了一些只在本地运行的应用程序之外,一般安装在普通的客户机上,需要与服务端互相配合运行

​ –摘自百度百科

举个例子,我们常常用的浏览器就是一个客户端

服务器

与客户端相对的,提供服务的。一般服务器上面都放有客户端需要的资源。当客户端请求服务器上的某些资源的时候,如果服务器允许的话,那么服务器可以返回这些资源给客户端。例如,浏览器去访问www.baidu.com的时候,百度的服务器就会返回一个html文件给浏览器,然后经过浏览器的渲染,呈现给用户一个美丽的页面

客户端与服务器进行交流的本质

我们知道,无论是客户端的程序还是服务器的程序,本质都是程序。那么当程序跑起来之后,就是进程了。而进程之间进行交流就需要使用进程通信的一些方法了。并且,这两个进程是处于不同的位置对吧(可能在世界的两端),不是简单的由父进程fork一下,然后使用类似于管道、信号之类的进程通信手段就可以完成通信的。既然它们是在网络中的,就需要遵循网络协议

网络协议

HTTP是一个客户端和服务器端请求和应答的标准协议。通常,由HTTP客户端发起一个请求,建立一个到服务器指定端口(默认是80端口)的TCP连接

因此我们要做的工作就是利用Linux系统提供的TCP通信接口来实现HTTP协议。此时我们用到的就是socket(套接字)

每一对网络连接称为一个socket对,包括两个端点的socket地址

socket处理请求与响应示意图

我们接下来要写的代码就是围绕这幅图进行的

IP和端口号

IP是用来在互联网中寻找主机用的,端口号则是用来区分应用的。比如说,我要访问www.baidu.com这个网页,我是需要知道它的IP地址才能访问的,除此之外,我还必须知道端口号。为什么呢?我们可以把IP地址想象成,而我不可能和通信吧,我还必须知道我要通信的这个人在哪里对吧,此时端口号就起了作用,用来标识哪个人

实现接受GET请求的功能

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <sys/types.h>
#include <sys/socket.h>
#include <sys/unistd.h>
#include <netinet/in.h>
#include <fstream>

using namespace std;

const int BUFFSIZE = 1024;
const int MAXLINK = 10; // 未经过处理的连接请求队列可以容纳的最大数目
const int DEFAULT_PORT = 8080;

char* get_file_name (char* buff) {
char* file_name = buff + 5;
char *space = strchr(file_name, ' ');
*space = '\0';
return file_name;
}

void deal_get_http(int connect_fd, char* buff) {
char* file_name = get_file_name(buff);
const char http_correct_header[] = "HTTP/1.1 200 OK\r\nContent-type: text/html\r\n\r\n";
int res = write(connect_fd, http_correct_header, strlen(http_correct_header));
if (res > 0) {
cout<<"send success"<<endl;
}
}

bool is_get_http(char* buff) {
if (!strncmp(buff, "GET", 3)) { // 如果是GET请求
return true;
}
else {
return false;
}
}

int main(int argc, char const *argv[])
{


int socket_fd, connect_fd;
struct sockaddr_in servaddr;
char buff[BUFFSIZE];

socket_fd = socket(AF_INET, SOCK_STREAM, 0);
if (socket_fd == -1) {
cout<<"create socket error"<<endl;
return -1;
}

memset(&servaddr, 0, sizeof(servaddr));
servaddr.sin_family = AF_INET;
servaddr.sin_addr.s_addr = htonl(INADDR_ANY); // IP必须是网络字节序,INADDR_ANY是绑定本机上所有IP
servaddr.sin_port = htons(DEFAULT_PORT); // 端口号必须是网络字节序

if (bind(socket_fd, (struct sockaddr*)&servaddr, sizeof(servaddr)) == -1) {
cout<<"bind error"<<endl;
return -1;
}

if (listen(socket_fd, MAXLINK) == -1) {
cout<<"listen error"<<endl;
}

connect_fd = accept(socket_fd, (struct sockaddr*)NULL, NULL);
if (connect_fd == -1) {
cout<<"accept error"<<endl;
}
else {
cout<<"连接成功"<<endl;
}

memset(buff, '\0', sizeof(buff));

recv(connect_fd, buff, BUFFSIZE - 1, 0); // 把请求头(或发送的消息)写入buff中
send(connect_fd, buff, BUFFSIZE - 1, 0); // 向客户端发送消息(发送buff中的内容)

cout<<"recive message from client: "<<buff<<endl;

if (is_get_http(buff)) {
cout<<"it is get http"<<endl;
deal_get_http(connect_fd, buff);
}

close(connect_fd);
close(socket_fd);

return 0;
}

好的,到这里,我们就已经写完了一个可以接收GET请求的服务器了,我们来测试一下:

在上面,我们只是模拟了使用telnet发送一个GET请求,这个请求去请求index.html文件,然后我们返回一部分响应头给客户端,此时并没有返回index.html的内容给客户端。接下来,我们就来完成这部分功能,一步一步的让这个服务器健全起来。

返回请求文件的内容

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void deal_get_http(int connect_fd, char* request_header) {
char* file_name = get_file_name(request_header);
int file_size = get_file_size(file_name);
char file_type[BUFFSIZE];
get_filetype(file_name, file_type);

int fd = open(file_name, O_RDONLY);
void* file_in_mem_addr = mmap(0, file_size, PROT_READ, MAP_PRIVATE, fd, 0); // 存储映射
close(fd);

char buff[BUFFSIZE];
strcat(buff, "HTTP/1.0 200 OK\r\n");
strcat(buff, "Server: HHTWS Web Server\r\n");
strcat(buff, "Connection: close\r\n");
strcat(buff, "Content-length: \r\n");
strcat(buff, "Content-type: \r\n\r\n");

send(connect_fd, buff, strlen(buff), 0);
send(connect_fd, file_in_mem_addr, file_size, 0);

munmap(file_in_mem_addr, file_size);
}

我们来看看效果:

存储映射机制

除了标准文件I/O,内核提供了另一种高级的I/O方式,允许应用程序将文件映射到内存中,即内存和文件中数据是一一对应的。程序员可以直接通过内存来访问文件,就像操作内存的数据块一样,甚至可以写入内存数据区,然后通过透明的映射机制将文件写入磁盘。

当映射一个文件描述符的时候,描述符引用计数增加。如果映射文件后关闭文件,你的进程依然可以访问该文件。当你取消映射或者进程终止时,对应的文件引用计数会减1。

遇到的问题

读取整个文件

开始的时候是想到了常规的方法,也就是使用fgets()函数等等,但是,因为它会给每一个字符串加上'\0'。所以当我使用它的时候,出现了一些乱码。之后我突然想起了我最近在《Linux系统编程》中看到的一个存储映射机制,于是就用上了它。非常方便的把文件的内容获取到了。

Segmentation fault问题

我在运行这个服务器的时候,出现了这个错误。最后经过排查,发现是由于存在野指针。开始的时候,我是这样定义一个文件类型的:

1
char* file_type;

然后我就直接把这个野指针给传进get_filetype函数里面去了。导致问题发生。

好了,到这里,我们就写完了一个可以说是完整的支持GET请求的Web服务器了。那小伙伴们是不是想在浏览器里面试一试效果!!看看能不能看到这个HTML文件被浏览器渲染出来!!

我们来试试!!

咦( ′◔ ‸◔`)?为什么不能在浏览器上面看到呢?小伙伴们,我将在下面一篇文章中继续为大家讲解。happy ending

(未完–持续更新加入新功能中)

整数反转

反转一个数字的问题还是很常见的问题,这里介绍一种简单的方法(关键是取余数、取整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>  
using namespace std;

int reserver_int(int n)
{
int m = 0;
while (n) {
m = m * 10 + n % 10;
n /= 10;
}
return m;
}

int main(int argc, char const *argv[])
{
int num;
cin>>num;
int the_reserver_int = reserver_int(num);
cout<<the_reserver_int;

return 0;
}

让我们来看看reserver_int这个函数的while部分

这个循环里面模拟的一个过程可以简单的表述成:每次取原来的数字的末尾,然后再拼接到新的数字的末尾

知道这个思路之后就很简单了,取一个数字的末尾a,就要用到%运算符,而把一个数字a拼接到一个数字b的末尾就是把这个数字b乘以10,再和a相加

然后就是循环的条件也是关键的地方,那么什么时候要结束呢?

很简单,当原来的那个数字的末尾全部被取下来了,也就不需要循环了。而表示取下一个数字的方法就是除以10

让字符数组和整型数组做一个映射