404频道

学习笔记

Posted on Edited on

题目

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.

分析

本题是一道非常简单的题目，但我能想到的思路有限，仅能想到排序法和哈希法两种算法，在Solution中提供了另外几种方法，这是非常值得我学习和思考的。本文仅将网站的思路拿过来，可以直接看该问题的Solution。

解答

暴力枚举法

最原始的解决办法，逐个元素比较是否为该数组中的最多元素，只要满足条件即可终止。时间复杂度为O(n^2)。

哈希表法

将数组中的元素遍历一遍，并将数组中元素的个数保存到哈希中。然后遍历哈希，从哈希中找到最多元素。时间复杂度O(n)，但需要占用一定的空间。

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
int majorityElement(vector<int> &num) {
        std::map<int, int> result_map;
        for (vector<int>::iterator iter = num.begin(); iter != num.end(); iter++)
        {
            if (result_map.find(*iter) == result_map.end())
            {
                result_map.insert(map<int, int>::value_type(*iter, 1));
            }
            else
            {
                result_map[*iter]++;                                                                                                                                            
            }
        }

        int max_count = 0;
        int result;
        for (std::map<int, int>::iterator iter = result_map.begin(); iter != result_map.end(); iter++)
        {
            if (iter->second > max_count)
            {
                result = iter->first;
                max_count = iter->second;
            }
        }
        return result;
    }

排序法

直接对元素进行排序，排序后元素的中间元素即为要求的最多元素。时间复杂度为O(nlogn)。

1
2
3
4
int majorityElementSort(vector<int> &num) {
   sort(num.begin(), num.end());
   return num[num.size() / 2];
}

随机抽取法

随机从数组中抽取元素，然后遍历数组判断该元素是否为最多元素。该算法利用了最多元素被随机抽取的概率最大的特点，但该算法效率的随机性较大，最好时间复杂度为O(n)，最坏情况下一直随机不到最多元素。

二分法

将数组均分为两份，分别求出两个数组中的最多元素A和B，则整个数组中的最多元素必然在两个子数组的最多元素A和B中，这一点可以通过举例子的方式来证明，但是仅凭感觉不太容易得出该结论。如果A==B，则结果就是A。如果A!=B，则分别求出A和B在这个数组中的元素个数。时间复杂度接近O(nlogn)。

其他

还有一些比较不容易想到的算法，这里就不列举了。至少我看过一次之后，下次这些算法仍然是记不住的。

Posted on Edited on

asleap是一个开源的vpn破解工具，最近查看了asleap的源码，该项目地址。本文的重点是对其中的带索引的字典文件的产生过程进行介绍，产生带索引的字典文件并不复杂，但是要想用简洁易懂的语言将该问题描述明白却不容易。

asleap破解vpn的机制是通过字典文件暴力破解的方式，该字典文件有dat数据文件和idx索引文件两个文件组成，两个文件均为二进制格式。asleap工程中自带了genkey程序，可以将文本的字典文件转换为asleap程序需要的带索引的字典文件。

本文以字典文件为以下内容讲解：

1
2
3
turquoise
da
test

读取字典文件并产生md4值

md4编码占16个字节，三个字典进行md4编码后的结果分别为：

1
2
3
18 07 33 43 f6 30 b5 f8 2c 38 c0 34 37 f2 81 6b
01 19 a3 80 94 40 60 3c 57 39 5e 73 f3 60 95 98
0c b6 94 88 05 f7 97 bf 2a 82 80 79 73 b8 95 37

将字典信息写入到临时文件

为了能够对最终生成的dat文件中的内容进行排序和便于索引，程序生成了256个临时文件，文件名格式为从genk-bucket-00.tmp到genk-bucket-ff.tmp。程序根据md4编码中的第14位将字典对应的信息分别写入到临时文件中，一个字典写入到临时文件的内容如下，如果一个临时文件中存在多个字典则依次存放：

1
2
3
4
5
struct hashpass_rec {
    unsigned char rec_size;		// 一个字典占用文件的大小，包括该变量+字典+字典对应的md4值共占用的字节数
    char          *password;	// 字典
    unsigned char hash[16];		// 字典对应的md4值
} __attribute__ ((packed));

本例子中turquoise对应结构体会写入到genk-bucket-81.tmp中，da和test对应结构体会依次写入到genk-bucket-95.tmp中。

读取临时文件并写入到dat数据文件中

最终dat文件中的数据内容为hashpass_rec的有序集合，排序的原则是按照md4的第14和15两个字节。依次读取256个临时文件中的hashpass_rec可以保证dat文件中的数据内容是按照第14字节排序的，但是不能够保证是按照第15个字节排序的。为了保证最终dat文件中的数据内容是按照第14和15字节有序的，在将一个临时文件中的内容写入到dat文件中前需要对该临时文件中的hashpass_rec结果按照hash变量的第15字节进行排序，直接使用C语言中的qsort进行排序。

该例子中da和test位于同一个临时文件中，需要根据hash变量的第15字节排序的结果为test、da，最终写入到dat文件中的排序结果为turquoise、test、da。

根据dat数据文件产生idx索引文件

idx索引文件中存放的是多个hashpassidx_rec结果，最多有256*256项，其结构定义如下：

1
2
3
4
5
struct hashpassidx_rec {
    unsigned char	        hashkey[2];	// 对应md4编码的第14和15字节
    off_t                   offset;		// 第一个匹配的hashpass_rec结构在dat文件中的偏移，占用4个字节
    unsigned long long int 	numrec;		// dat文件中共有多少个匹配的hashpass_rec结果
} __attribute__ ((packed));	// 字节对齐，需要填充4个字节

最终完成的dat文件和idx文件的指向如下图所示：

最终完成的dat文件和idx文件的指向

bug

genkeys.c文件中在读取字典文件时存在bug，在文件的207行将内容更改为：

1
2
3
4
5
6
while (!feof(inputfl)) {
		memset(password, 0, MAX_NT_PASSWORD + 1);
        fgets(password, MAX_NT_PASSWORD+1, inputfl);
		if (strlen(password) == 0) {
			continue;
		}

相关下载

字典文件等相关文件下载

Posted on Edited on

本文对我编写的常用的排序算法进行整理和总结，方便用时进行查阅和参考。

快速排序

快速排序是实际应用中的最好选择，采用了分治法的思想。通过一趟排序将待排序记录分割成独立的两部分，其中一部分的关键字均比另外一部分的小，分别对这两部分记录进行排序，已达到整个有序。

是否稳定：不稳定

时间复杂度：O(nlogn)

空间复杂度：O(logn)，需要栈来实现递归用

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
#include <stdio.h>
#include <vector>
#include <iostream>

int partition(std::vector<int> &numbers, int low, int high)
{
    int pivotkey = numbers[low];
    while (low < high)
    {
        while (low < high && numbers[high] >= pivotkey)
        {
            --high;
        }
        numbers[low] = numbers[high];
        while (low < high && numbers[low] <= pivotkey)
        {
            ++low;
        }
        numbers[high] = numbers[low];
        numbers[low] = pivotkey;
    }
    return low;
}


void quick_sort(std::vector<int> &numbers, int low, int high)
{
    if (low < high)
    {
        int pivotloc = partition(numbers, low, high);
        quick_sort(numbers, low, pivotloc - 1);
        quick_sort(numbers, pivotloc + 1, high);
    }
}

void quick_sort(std::vector<int> &numbers)
{
    quick_sort(numbers, 0, numbers.size() - 1);
}

int main()
{
    std::vector<int> numbers = {49, 38, 65, 97, 76, 13, 27, 49};
    quick_sort(numbers);
    for (int i=0; i<numbers.size(); i++)
    {
        printf("%d\t", numbers[i]);
    }
    printf("\n");
}

归并排序

将两个或两个以上的有序表组合成一个新的有序表。合并两个有序表的方法为：比较两个有序表中第一个数，谁小先取谁。继续进行比较，只要有一个有序表为空，直接将另一个有序表取出即可。

是否稳定：稳定

时间复杂度：O(nlogn)

空间复杂度：O(n) （当使用顺序存储时，为了能够实现两个有序表之间的合并），或O(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
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
/**
 * 归并排序使用递归算法的效率比较低，具体应用中会采用非递归算法代替
 */
void merge(std::vector<int> &numbers, std::vector<int> &extra, int low, int high, int middle)
{
    int i = low, j = middle+1, k = low;
    for (; i<=middle && j<=high; k++)
    {
        if (numbers[i] <= numbers[j])
        {
            extra[k] = numbers[i];
            i++;
        }
        else
        {
            extra[k] = numbers[j];
            j++;
        }
    }
    
    while (i <= middle)
    {
        extra[k++] = numbers[i++];
    }

    while (j <= middle)
    {
        extra[k++] = numbers[j++];
    }

    for (int m = low; m <= high; m++)
    {
        numbers[m] = extra[m];
    }
}


void merge_sort(std::vector<int> &numbers, std::vector<int> &extra, int low, int high)
{
    if (low == high)
    {
        return ;
    }
    int middle = (low + high) / 2;
    merge_sort(numbers, extra, low, middle);
    merge_sort(numbers, extra, middle + 1, high);
    merge(numbers, extra, low, high, middle);
}

void merge_sort(std::vector<int> &numbers)
{
    // 申请额外的存储空间来用于排序处理
    std::vector<int> extra = numbers;
    merge_sort(numbers, extra, 0, numbers.size() - 1);
}

int main()
{
    std::vector<int> numbers = {49, 38, 65, 97, 76, 13, 27, 49};
    merge_sort(numbers);

    for (int i=0; i<numbers.size(); i++)
    {
        printf("%d\t", numbers[i]);
    }
    printf("\n");
}

链式存储代码

以下为采用链式存储结构的代码，本答案为我在LeetCode上的Sort List 题目的答案，源码放在我的Github上。

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
95
96
97
98
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

/**
 * 使用归并排序方法，核心思想为将数组拆分为两半，分别对两半进行排序，排序完成后再进行一次排序，排序算法就可以采用插入排序的方式。
 * 对两半排序的算法仍然采用归并排序算法，即问题为递归问题
 * 在使用线性存储结果的归并排序算法中，会使用额外的空间来存储临时结果，空间复杂度为O(n)，而在链式存储中，空间复杂度为O(1)
 * 归并排序的时间复杂度为O(nlogn)
 * 如果存储结构为双向链表，可以使用快速排序
 */
ListNode* sortList(ListNode* head)
{
    if (head == nullptr || head->next == nullptr)
    {
        return head;
    }

    if (head->next->next == nullptr)
    {
        // 仅有两个元素，对两个元素进行排序后直接返回
        if (head->val < head->next->val)
        {
            return head;
        }
        else
        {
            ListNode *tmp = head->next;
            tmp->next = head;
            tmp->next->next = nullptr;
            return tmp;
        }
    }

    // 为了找到中间节点，这里采用快慢指针的方式，否则需要使用先遍历一次取长度，然后找到中间位置的两次遍历方式
    ListNode *fast = head;
    ListNode *slow = head;
    ListNode *slow_prev = nullptr;
    while (fast != nullptr && fast->next != nullptr)
    {
        fast = fast->next->next;
        slow_prev = slow;
        slow = slow->next;
    }
    fast = slow_prev->next;
    slow_prev->next = nullptr;

    // 分别对两段链表进行排序
    slow = sortList(head);
    fast = sortList(fast);

    // 对两段链表进行合并
    ListNode *node = nullptr, *result = nullptr;
    while (slow != nullptr && fast != nullptr)
    {
        if (slow->val < fast->val)
        {
            if (result != nullptr)
            {
                node->next = slow;
                node = node->next;
            }
            else
            {
                node = slow;
                result = slow;
            }
            slow = slow->next;
        }
        else
        {
            if (result != nullptr)
            {
                node->next = fast;
                node = node->next;
            }
            else
            {
                node = fast;
                result = fast;
            }
            fast = fast->next;
        }
    }
    if (slow != nullptr)
    {
        node->next = slow;
    }

    if (fast != nullptr)
    {
        node->next = fast;
    }

    return result;
}

直接插入排序

该排序算法的时间复杂度为O(n^2)，算法复杂度过高。分为顺序存储和链式存储两种算法，其中顺序存储每比较一个元素是从该元素往前比较的，而链式存储是从链头开始比较的，这点有所不同，造成不同的是由存储结构决定的。

顺序存储代码

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
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

void insertion_sort(std::vector<int> &numbers)
{
	if (numbers.size() <= 1)
	{
		return;
	}
	for (int i = 1; i < numbers.size(); i++)
	{
		for (int j = i; j > 0; j--)
		{
			if (numbers[j] < numbers[j - 1])
			{
				swap(numbers[j], numbers[j - 1]);
			}
			else
			{
				break;
			}
		}
	}
}

int main()
{
	int a[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
	vector<int> numbers(a, a + sizeof(a) / sizeof(int));
	insertion_sort(numbers);
	for (int i = 0; i<numbers.size(); i++)
	{
		printf("%d\t", numbers[i]);
	}
	return 0;
}

链式存储代码

以下代码为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
39
40
41
42
43
44
45
46
47
48
49
50
ListNode* insertionSortList(ListNode* head) 
{
    if (head == NULL)
    {
        return NULL;
    }
    
    // 初始化
    ListNode *node = head->next;
    ListNode *new_head = head;
    new_head->next = NULL;
    while (node != NULL)
    {
        ListNode *node_next = node->next;   // 先将当前遍历的下一个节点保存
        
        // 将当前节点插入到新链表中
        ListNode *new_node_tmp = new_head;
        if (node->val < new_node_tmp->val)
        {
            // 当前节点插入新链表的第一个位置
            node->next = new_head;
            new_head = node;
        }
        else
        {
            // 将当前节点插入到中间
            while (new_node_tmp->next != NULL)
            {
                if (node->val < new_node_tmp->next->val)
                {
                    node->next = new_node_tmp->next;
                    new_node_tmp->next = node;
                    break;
                }
                new_node_tmp = new_node_tmp->next;
            }
            
            // 将该节点插入到最后位置
            if (new_node_tmp->next == NULL)
            {
                new_node_tmp->next = node;
                node->next = NULL;
            }
        }
            
        // 开始遍历当前节点的下一个节点
        node = node_next;
    }
    return new_head;
}

Posted on Edited on

我的年总结是依照农历的，因为在我心中春节才算是一年的真正开始，因为只有春节的时候才能找到年的滋味，年的感觉，才能称之为年，阳历的年只能称之为year。

2014年又在不经意间过去了，很多地方跟2013年一样是平淡，工作和学习仍然是生活的主旋律，闲暇时间抽个时间玩玩dota放松一下，周末偶尔爬个小山锻炼下身体，对我的人生中算是比较重要的一年。

学习

2014年经历了结婚、毕业答辩和考驾照几件占用时间的事情，留给我业余时间用来学习的就少之又少了。结婚占用两个月时间，毕业论文占用了我两个月时间，考驾照占用了多个周末，工作出差占用了我一个月时间，留给我能够独立学习的晚上也就6个月时间。

开始的时候小看了硕士论文，以为很简单一事情，搞过这么多软件项目还搞不了一篇硕士论文。一直以来我看不起软件工程类论文，就一项目套个模板一介绍就是一篇论文，于是我选择了写一篇理论研究类论文，没有高大上的理论，而是在公司实践中真正用到的，《将Windows平台的C/C++程序向Linux平台移植的技术研究》，选择论文的时候我已经看到了该题目不太适合作为硕士论文，当我还是毅然作为了我的硕士论文题目，不得不说这是我今年的一大败笔。第一篇论文失败后，我重新走起了保守路线，以之前熟悉的系统为主线，辅以各种文档的拼凑，完成了一篇我曾经嗤之以项目类硕士论文，并顺利通过答辩。对于我这样的新手而言，写论文是一件漫长又痛苦的过程，占用了我大量的宝贵时间。

一直以来对嵌入式linux方向比较好奇，今年终于抵不住好奇，买了个2140开发板自己捣鼓了一段时间，由于时间关系虽然到现在也没有入门，多多少少对嵌入式已经有所了解。

感谢我的另一半，给我提供了足够的时间来干我想干的事情。

书籍

比起2013年，今年读过的书籍少了一些。

  • 《Linux/Unix系统编程手册》
  • 《编程珠玑》
  • 《LINUX设备驱动程序》（部分章节）
  • 《LINUX内核设计与实现》（大部分章节）
  • 《深度探索linux操作系统》
  • 《剑指Office》
  • 《大规模C++程序设计》
  • 《程序员的自我修养》（第二遍）
  • 《文明之光》
  • 《程序员健康指南》
  • 《黄金时代》
  • 《一只特立独行的猪》
  • 《算法导论》（部分章节）

工作

已经比较熟练掌握了公司产品的大部分技术，工作起来算是得心应手，但是却少了许多挑战，是时候该接收大挑战的了。工作的职位从后台组长到研发部副经理到研发部经理，开始了工作的转型，这是我不期望这么早来到的，我自认为技术的成长空间还很大，不想过早的接触管理岗位。

五月份的出差成为了我心中抹不去的痛，莫名其妙接受了任务，匆忙出差，不过坑才刚刚开始。要维护的是一个我没见过界面的产品，不过基本原理我是清楚的。产品有很多bug，这我可以理解，要不然也不会让我出差了，但要命的是我没有产品的代码，我接受的任务仅是去应付客户、发现bug后反馈、更新产品、施工，这明白着是市场+测试+维护的话，跟我半毛钱关系都没有。以上这些都无所谓，要知道我可不是一个顽固不化的程序员，但工作地点竟然是机房，而且机房是我见过最脏最乱的机房，我就站在一排机柜的后面的一堆烂纸箱子上吹着空调的冷风和机器的热风办公，时而蹲着，时而站着，时而坐着，时而将衣领撩起保暖，时而浑身打颤，以至于到现在我留下了膝盖隐隐作痛的毛病。而且系统bug不断，一连在不吃晚饭的情况下加班到大半夜好多次，而我竟然坚持下来了。原本三五天的出差计划，一待就是二十多天。这短短的二十多天成为了我今年最难忘的痛，多少次期望回到家里温暖的被窝，多少次期望在家吃着我做的炖土豆。

今年面试了不少人，通过面试也发现大部分技术人员的水平太差了，我甚至都搞不明白他们是怎么厚着脸皮来面试技术岗位的。济南软件行业实在是不景气，甚至找一个靠谱点的web或者php程序员都成为了公司的一大难题。

生活

长达五年的恋情在今年终于得到了升华，当然这升华是我不愿意这么快就看到的，多么希望能迟来几年，给原本一直以为自己还是个孩子的我一个接受的缓冲区，但站在两家人面前，我的想法竟然不能主导我。我对结婚这件事情持怎么简单怎么办的态度，结婚本就一仪式，豪华也罢，没有也罢，都是过眼云烟，为一天忙碌了一阵子仅为了那一天，而之后又有谁记得。结婚之所以在中国的古代非常重视，那是因为在农业社会中人民的娱乐方式非常单一，结婚可以成为人民心中的一个盼头和没有灯光的饭后侃的资本，现在娱乐方式早已多元化，相比之下结婚的光鲜早已显得微不足道。可结婚毕竟不是我一个人的事，甚至不是两个人的事，而是两家人的事。

结婚定在酷夏，定下来的时间比较匆忙，从定下来要结婚到结婚仅一个月时间，对我来说是莫大的好事，因为拖得时间越长占用的准备时间就越多。半年的婚前和半年的婚后生活，其实真的没人什么两样，都是美满的二人世界，希望这种状况能持续几年。

我一向对车比较排斥，始终认为汽车是一个比较失败的发明，用户体验特别差。好的设计应该让用户忽略其内部实现细节，好的发明不应该让用户花费大量的时间来学习怎样使用，甚至需要多个课时的专业培训。汽车不仅是一个毫无用户体验的发明，而且危险到极致，危险到一失误就会要掉人的性命。

但今年我随波逐流了，毕竟驾照是早晚要考的，晚考成本只会更高。于是考驾照提上了议程，8月初已经计划报名，只可惜流程过于复杂，到现在也才到了科目二的程度。先是报名需要办暂住证，暂住证一办就是15个工作日，直接拖到了十一之后。找个离家近的驾校报个名，一等就是一个月才考科目一。科目一考完一等又是一个月才开始分车学科目二。科目二刚开始学又开始继续了，一共练了两个工作日后驾校又开始集训了，又没我啥事了。好在我找了个陪练，练了几把就顺手了。

虽然驾照没有考出来，仅考到了科目二，算是完成了驾照的一半，但却耗去了我的部分经历。找驾校、准备科目一、学习科目二、找陪练，这些花费的都是我的时间。要是驾校培训行业能够再成熟些，再人性化些能给多少学车的人带来方便。

玩游戏多少有些过了，虽然每周也就不想学习的两个晚上用来玩游戏，但我深知自己不是玩游戏的料。很多时候为了能够赢一局，会熬夜到下半夜，这是非常不理智的。另外，以后尽量用其他方式来代替游戏放松，当然我深知其中的苦难。

旅行

去过一次云南，都在这里了。

清明节时间去过一次天津，天津比我想象的要好很多，各个地方特色比较明显，有别墅区、意大利风情区、现代的商业区等，这之间能够非常明显的区分，不像济南太混杂。不过天津的人却给我留下的印象不是很好，这也是小小的遗憾。

展望

在我心中已经为2015年制定好了一些计划，为家庭，为自己，2015年会是我人生的一个转折点，期望2015年能够顺利。我会努力的。

Posted on Edited on

题目

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

分析

该题目为经典题目，存在多种解题思路。

动态规划

求动态规划的关键在于找到状态方程。

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
/**
 * 问题的关键是找到状态方式，找到状态方程后问题就迎刃而解
 * 状态方程如下：
 * b[j]表示第j处，以a[j]结尾的子序列的最大和
 * b[j]=max(a[j] + b[j-1], a[j])
 * b数据的最大值即为问题的解
 * 问题转换为求解b数组
 * 时间复杂度为O(1)，空间复杂度为(n)，空间复杂度可以降为O(1)，为了使程序易读，不做调整
 */
int maxSubArray(int A[], int n) {
	if (n == 0)
	{
		return 0;
	}
	int *b = new int[n];
	b[0] = A[0];
	int max_b = b[0];
	for (int i=1; i<n; i++)
	{
		b[i] = std::max(A[i] + b[i-1], A[i]);
		if (max_b < b[i])
		{
			max_b = b[i];
		}
	}
	delete[] b;
	return max_b;
}

分治法

《算法导论》的分治策略一章有关于该问题的详细解释。该题利用分治法来解决要比二分查找类最简单的分治算法要复杂。将数组一分为二后，最大数组存在三种情况：在左半或右半部分、跨越中点分别占据左部分一点和右部分一点。对于跨越中点的情况，转化为求从中点开始向左的最大值和从中点开始向右的最大值之和。

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
class Solution {
public:
    int compare_array[4];

    int maxSubArray(int A[], int n) {
        return maxSubArray(A, 0, n - 1);
    }

    /**
     * leetcode not support stdarg.h
     */
    int max(int count, ...)
    {
        va_list ap;
        va_start(ap, count);
        int max = INT_MIN;
        for (int i=0; i<count; i++)
        {
            int temp = va_arg(ap, int);
            if (max < temp)
            {
                max = temp;
            }
        }
        va_end(ap);
        return max;
    }

    int max_compare_array()
    {
        int max_num = compare_array[0];
        for (int i=1; i<4; i++)
        {
            if (max_num < compare_array[i])
            {
                max_num = compare_array[i];
            }
        }
        return max_num;
    }

    int maxSubArray(int A[], int begin, int end)
    {
        //printf("begin : %d, end : %d\n", begin, end);
        if (begin == end)
        {
            return A[begin];
        }
        else if ((end - begin) == 1)
        {
            //return max(3, A[begin], A[begin] + A[end], A[end]);
            compare_array[0] = A[begin];
            compare_array[1] = A[begin] + A[end];
            compare_array[2] = A[end];
            compare_array[3] = INT_MIN;
            return max_compare_array();
        }
        int middle = (begin + end) / 2;
        // 处理左边子数组
        int max_left = maxSubArray(A, begin, middle);
        // 处理右边子数组
        int max_right = maxSubArray(A, middle + 1, end);
        // 处理跨越中点的情况
        int max_cross = maxCrossMiddle(A, begin, end);

        printf("begin : %d, end : %d, max_left = %d, max_right = %d, max_cross = %d\n", begin, end, max_left, max_right, max_cross);

        // 返回三者中的最大值
        compare_array[0] = max_left;
        compare_array[1] = max_right;
        compare_array[2] = max_cross;
        compare_array[3] = INT_MIN;
        return max_compare_array();
    }

    /**
     * 处理跨越中点的情况
     */
    int maxCrossMiddle(int A[], int begin, int end)
    {
        if (begin == end)
        {
            return A[begin];
        }
        int middle = (begin + end) / 2;
        // 求得[begin -- middle-1]的最大值
        int max_left = A[middle - 1];
        int sum = 0;
        for (int i=middle - 1; i>=begin && i >= 0; i--)
        {
            sum += A[i];
            if (max_left < sum)
            {
                max_left = sum;
            }
        }

        // 求得[middle+1 -- end]的最大值
        int max_right = A[middle + 1];
        sum = 0;
        for (int i=middle + 1; i<=end; i++)
        {
            sum += A[i];
            if (max_right< sum)
            {
                max_right = sum;
            }
        }

        compare_array[0] = A[middle];
        compare_array[1] = A[middle] + max_left;
        compare_array[2] = A[middle] + max_right;
        compare_array[3] = A[middle] + max_left + max_right;
        return max_compare_array();
    }
};

扫描算法

《编程珠玑》一书8.4节提到该算法，时间复杂度为O(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
int maxSubArray(int A[], int n) {
	if (n == 0)
	{
	    return 0;
	}
	int current_sum = 0;
	int max_sum = INT_MIN;

	for (int i=0; i<n; i++)
	{
	    if (current_sum <= 0)
	    {
		current_sum = A[i];
	    }
	    else
	    {
		current_sum += A[i];
	    }
	    if (current_sum > max_sum)
	    {
		max_sum = current_sum;
	    }
	}
	return max_sum;
}

Posted on Edited on

最近在看《Linux/Unix系统编程手册》一书，这里对书中提到的函数类型进行总结。

可重入

POSIX标准中的解释如下：

Reentrant Function:
A function whose effect, when called by two or more threads,is guaranteed to be as if the threads each executed thefunction one after another in an undefined order, even ifthe actual execution is interleaved.

可重入函数跟信号相关，一种更容易理解的解释为：

程序执行到某个函数foo()时，收到信号，于是暂停目前正在执行的函数，转到信号处理函数，而这个信号处理函数的执行过程中，又恰恰也会进入到刚刚执行的函数foo()，便发生了所谓的重入。此时如果foo()能够正确的运行，而且处理完成后，之前暂停的foo()也能够正确运行，则说明它是可重入的。

可重入函数需要满足如下几个条件：

  • 不在函数内部使用静态或全局数据
  • 不返回静态或全局数据，所有数据均有函数调用者提供
  • 使用本地数据或通过复制全局数据来保护全局数据
  • 不调用不可重入函数

标准的异步安全信号函数

异步信号安全的函数指当从信号处理函数调用时，可保证实现是安全的。如果某一个函数是可重入的，或者信号处理函数无法将其中断时，称该函数是异步信号安全的。

我的理解是可重入函数和标准的异步安全信号函数基本等同，只是描述层面不同。

线程安全

若函数可同时供多个线程安全的调用，则该函数为线程安全的函数。比较容易理解。

线程安全与可重入之间的关系

可重入函数一定为线程安全的函数。线程安全函数不一定是可重入函数。

不可重入函数，函数调用结果不具有可再现性，可通过互斥锁等机制供多个线程安全的调用，这样该不可重入函数即为线程安全的函数。

malloc函数内部维护了全局数据结构，因此为不可重入的，但是内部通过递归互斥量来确保为线程安全的函数。并且该互斥量必须是可递归的，否则当malloc函数重入的情况下，会造成死锁。在glibc中，malloc有线程安全和非线程安全两个版本，两个区别在于内部是否使用递归锁，当编译程序时使用了_pthreads选项时使用线程安全版本，否则使用非线程安全版本。

自动重启

Linux中的某些系统调用在阻塞的过程中，如果接受到信号并转去处理信号处理函数，当从信号处理函数返回时这些阻塞的系统调用默认会返回EINTR。为了避免信号处理函数对阻塞中的系统调用的打断，可以通过设置SA_RESTART标志的sigaction()来建立信号处理函数，从而令内核代表进程自动重启系统调用，而无需处理系统调用返回的EINTR错误。

并非所有的系统调用都支持自动重启，具体可参考《Linux/Unix系统编程手册（上册）》的21.5节。

参考资料

《Linux/Unix系统编程手册（上册）》

对可重性和线程安全的小结

Posted on Edited on

[TOC]

信号机制在Linux编程中一直是一个难点，因为信号往往跟进程、线程、定时器、I/O等多个层面都有牵涉，这些情况存在错综复杂的关系，堪比娱乐圈错综复杂的男女关系，要想全面理解信号机制确实不易。

信号种类

在Linux中可以通过如下命令来查看所有的信号：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
[kuring@localhost ~]$ kill -l
 1) SIGHUP       2) SIGINT       3) SIGQUIT      4) SIGILL       5) SIGTRAP
 6) SIGABRT      7) SIGBUS       8) SIGFPE       9) SIGKILL     10) SIGUSR1
11) SIGSEGV     12) SIGUSR2     13) SIGPIPE     14) SIGALRM     15) SIGTERM
16) SIGSTKFLT   17) SIGCHLD     18) SIGCONT     19) SIGSTOP     20) SIGTSTP
21) SIGTTIN     22) SIGTTOU     23) SIGURG      24) SIGXCPU     25) SIGXFSZ
26) SIGVTALRM   27) SIGPROF     28) SIGWINCH    29) SIGIO       30) SIGPWR
31) SIGSYS      34) SIGRTMIN    35) SIGRTMIN+1  36) SIGRTMIN+2  37) SIGRTMIN+3
38) SIGRTMIN+4  39) SIGRTMIN+5  40) SIGRTMIN+6  41) SIGRTMIN+7  42) SIGRTMIN+8
43) SIGRTMIN+9  44) SIGRTMIN+10 45) SIGRTMIN+11 46) SIGRTMIN+12 47) SIGRTMIN+13
48) SIGRTMIN+14 49) SIGRTMIN+15 50) SIGRTMAX-14 51) SIGRTMAX-13 52) SIGRTMAX-12
53) SIGRTMAX-11 54) SIGRTMAX-10 55) SIGRTMAX-9  56) SIGRTMAX-8  57) SIGRTMAX-7
58) SIGRTMAX-6  59) SIGRTMAX-5  60) SIGRTMAX-4  61) SIGRTMAX-3  62) SIGRTMAX-2
63) SIGRTMAX-1  64) SIGRTMAX

共64个信号，分为两种信号：非实时信号和实时信号。其中1-31个信号为非实时信号，32-64为实时信号。

当一信号在阻塞状态下产生多次信号，当解除该信号的阻塞后，非实时信号仅传递一次信号，而实时信号会传递多次。

对于非实时信号：内核会为每个信号维护一个信号掩码，并阻塞信号针对该进程的传递。如果将阻塞的信号发送给某进程，对该信号的传递将延时，直至从进程掩码中移除该信号为止。当从进程掩码中移除该信号时该信号将传递给该进程。如果信号在阻塞期间传递过多次该信号，信号解除阻塞后仅传递一次。

对于实时信号：实时信号采用队列化处理，一个实时信号的多个实例发送给进程，信号将会传递多次。可以制定伴随数据，用于产生信号时的数据传递。不同实时信号的传递顺序是固定的，优先传递信号编号小的。

信号阻塞

内核会为每个信号维护一个信号掩码，来阻塞内核将信号传递给该进程。如果将阻塞的信号发送给该进程，信号的传递将延后，从进程信号掩码中移除该信号后内核立刻将信号传递给该进程。如果一个信号在阻塞状态下产生多次，对于非实时信号稍后仅会传递一次，对于实时信号内核会进行排队处理，会传递多次。

信号处理函数

要想在进程中设置信号处理函数有两种选择：signal()和sigaction()。其中signal()函数提供的接口比较简单，但是在不同的UNIX系统之间存在差异，跨平台特性不是很好,signal()函数由于是C库函数，实现往往是采用sigaction()系统调用完成。sigaction()具有很好的跨平台性，但是使用较为复杂，但是却可以在信号处理程序中完成阻塞信号的作用。

在sigaction函数中可以指定调用信号处理函数时要阻塞的信号集，不允许这些信号中断信号处理函数的调用，直到信号处理函数调用完毕后信号才会传递。这一点通过signal函数是完不成的，利用signal函数设定的信号处理函数只能在信号处理函数开始时使用sigprocmask设置要阻塞的信号，在信号处理函数尾部利用sigprocmask还原信号，但在调用第一次调用sigprocmask函数之前和第二次调用sigprocmask函数之后的空白期内却无法防止要阻塞信号的传递。

信号处理函数中调用的函数尽量是异步信号安全的，C库中的函数不是异步信号安全的函数。

在信号处理函数中尽量避免访问全局变量，要访问全局变量可以使用volatile sig_atomic_t flag，volatile防止将编译器将变量优化到内存中，sig_atomic_t是一种整形数据类型，用来保证读写操作的原子性。

系统调用的中断

当系统调用阻塞时，之前创建了处理函数的信号传递过来。在信号处理函数返回后，默认情况下，系统调用会失败，并将errno置为EINTR。

如果调用指定了SA_RESTART标志的sigaction()函数来创建信号处理器函数，内核会在信号处理函数返回后自动重启系统调用，从而避免了信号处理函数对阻塞的系统调用产生的影响。比较不幸的是，并非所有的系统调用都支持该特性。

信号的同步生成和异步生成

这里的同步是对信号产生方式的描述，跟具体哪个信号无关。所有的信号均可同步生成，也可异步生成。

异步生成：引发信号产生的事件与进程的执行无关。例如，用户输入了中断字符、子进程终止等事件，这些信号的产生该进程是无法左右的。

同步生成：当执行特定的机制指令产生硬件异常时或进程使用raise()、kill()等向自身发生信号时，信号是同步传递的。这些信号的产生时间该进程是可以左右的。

信号传递的时机和顺序

同步产生的信号会立即传递给该进程。例如，当使用raise()函数向自身发送信号时，信号会在raise()调用前发生。

异步产生一个信号时，且在进程并未阻塞的情况下，信号也不会立即被传递。当且仅当进程正在执行，并且由内核态到用户态的下一次切换时才会传递信号。说人话就是在以下两种情况下会传递信号：进程获得调度时和系统调用完成时。这是因为内核会在进程在内核态和用户态进行的切换的时候才会检测信号。

非实时信号的传递顺序无法保障，实时信号的传递顺序是固定的，当多个不同的实时信号处于等待状态时，优先传递最小编号的信号。

信号和线程

信号模型是基于进程模型而设计的，应尽量避免在多线程中使用信号模型。

信号的发送可以针对整个进程，也可以针对特定线程。

当进程收到一个信号后，内核会任选一个线程来接收信号，并调用信号处理函数对信号进行处理。

每个线程可以独立设置信号掩码。

如果信号处理程序中断了对pthread_mutex_lock()和pthread_cond_wait()的调用，该调用会自动重启。

参考文章

《Linux/Unix系统编程手册》

Posted on Edited on

第一遍阅读unpv3后，对书中讲述的内容有了大体的认识，但对书中的具体细节地方却是早已忘记。重新阅读unpv3，这次不希望仍然是阅后即忘，于是通过编写代码的方式对书中的例子和注意事项加深理解。

为了能够将书中的很多细节问题理解清楚并且便于记忆，本文采用了编写书中代码并运行的方式，并将书中容易出错和意想不到的问题记在代码中。

本文的代码实例并未完全按照书中的代码实例，本着单个文件即能编译通过并运行的原则，本文对于很多系统调用并未做防御式编程处理。针对每个版本的程序中缺点和注意事项在代码中已经进行了标注。

鉴于高性能的epoll机制出现比较晚，晚于unp的编写时间，书中并未做介绍。

TCP客户端程序

客户端函数执行效率情况：select非阻塞式I/O版本>线程化版本>fork版本>select阻塞式I/O版本>停等版本，停等版本的执行效率非常低，在实际生产环境中不建议使用。

其中poll和select机制基本类似，书中并未给出poll版本。

停-等版本

最常规的实现思路，但效率非常低，且当程序阻塞在读取要发送内容时，程序是无法收到服务端的状态变化。

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
/**
 * 停-等版本
 * 该版本缺陷为当服务端发生某些事件时，客户端可能仍然阻塞于fgets调用中
 */
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <signal.h>

#define SERV_PORT 9877
#define MAXLINE 4096	/* max text line length */

void str_cli(FILE *fp, int sockfd)
{
	char sendline[MAXLINE], recvline[MAXLINE];
	while (fgets(sendline, MAXLINE, fp) != NULL)
	{
		/* 当阻塞在fgets函数时将服务器进程关闭时虽然给客户端发送了FIN信号，客户端并不会知道，
		 * 服务端关闭时第一次调用write服务器会返回RST，
		 * 当一个进程向某个收到RST的套接字执行写操作时，内核会向该进程发送一个SIGPIPE信号
		 * 该问题需要使用I/O复用技术来解决，或者使用fork处理的方式来解决
		 * */
		write(sockfd, sendline, strlen(sendline));
		int n = read(sockfd, recvline, MAXLINE);
		if (n == 0)
		{
			printf("str_cli: server terminated prematurely\n");
			exit(1);
		}

		// 向标准输出写内容，既可以使用write也可以使用fputs
		write(STDOUT_FILENO, recvline, n);

		// 使用fputs时需要注意将recvline数组有效内容的后面一位设置为'\0'
//		recvline[n] = '\0';
//		fputs(recvline, stdout);
	}
}

int main(int argc, char **argv)
{
	int sockfd;
	struct sockaddr_in	servaddr;

	if (argc != 2)
	{
		printf("usage: tcpcli <IPaddress>\n");
		exit(1);
	}

	// 当一个进程向某个收到RST的套接字执行写操作时，内核会向该进程发送一个SIGPIPE信号
	// 最好的方式是忽略此信号的处理方式，并在程序下面处理该异常情况
	signal(SIGPIPE, SIG_IGN);

	sockfd = socket(AF_INET, SOCK_STREAM, 0);

	bzero(&servaddr, sizeof(servaddr));
	servaddr.sin_family = AF_INET;
	servaddr.sin_port = htons(SERV_PORT);
	inet_pton(AF_INET, argv[1], &servaddr.sin_addr);

	connect(sockfd, (struct sockaddr*)&servaddr, sizeof(servaddr));

	str_cli(stdin, sockfd);		/* do it all */

	exit(0);
}

fork版本

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
/**
 * 阻塞式I/O的fork版本
 */
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <signal.h>

#define SERV_PORT 9877
#define MAXLINE 4096	/* max text line length */

/**
 * 即使服务端已经退出，子进程的read方法仍然能够感知到并且退出while循环，并给父进程发送SIGTERM,父进程对该信号的默认处理方式为退出
 * 优点：代码量比较少，每个进程只处理2个I/O流，从一个复制到另一个
 */
void str_cli(FILE *fp, int sockfd)
{
	char sendline[MAXLINE], recvline[MAXLINE];
	pid_t pid;
	if ((pid = fork()) == 0)
	{
		// child process : server -> stdout
		int n;
		while ((n = read(sockfd, recvline, MAXLINE)) > 0)
		{
			recvline[n] = '\0';
			fputs(recvline, stdout);
		}
		kill(getppid(), SIGTERM);
		exit(0);
	}

	// parent process : stdin -> server
	while (fgets(sendline, MAXLINE, fp) != NULL)
	{
		write(sockfd, sendline, strlen(sendline));
	}
	shutdown(sockfd, SHUT_WR);
	pause();
	return ;
}

int main(int argc, char **argv)
{
	int sockfd;
	struct sockaddr_in	servaddr;

	if (argc != 2)
	{
		printf("usage: tcpcli <IPaddress>\n");
		exit(1);
	}

	// 当一个进程向某个收到RST的套接字执行写操作时，内核会向该进程发送一个SIGPIPE信号
	// 最好的方式是忽略此信号的处理方式，并在程序下面处理该异常情况
	signal(SIGPIPE, SIG_IGN);

	sockfd = socket(AF_INET, SOCK_STREAM, 0);

	bzero(&servaddr, sizeof(servaddr));
	servaddr.sin_family = AF_INET;
	servaddr.sin_port = htons(SERV_PORT);
	inet_pton(AF_INET, argv[1], &servaddr.sin_addr);

	if (connect(sockfd, (struct sockaddr*)&servaddr, sizeof(servaddr)) != 0)
	{
		printf("connect error...\n");
		exit(1);
	}

	str_cli(stdin, sockfd);		/* do it all */

	exit(0);
}

阻塞式I/O的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
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/**
 * 阻塞式I/O的select版本
 */
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <signal.h>

#define SERV_PORT 9877
#define MAXLINE 4096	/* max text line length */

/**
 * 缺点：使用了阻塞式I/O，如果在向套接字调用write发送给服务器时，套接字缓冲区已满，write调用会阻塞，从而影响了后续的套接字缓冲区的读取
 */
void str_cli(FILE *fp, int sockfd)
{
	int maxfdp1;
	fd_set rset;
	char sendline[MAXLINE], recvline[MAXLINE];
	int stdineof = 0;
	FD_ZERO(&rset);
	for (; ;)
	{
		// select
		FD_SET(fileno(fp), &rset);
		FD_SET(sockfd, &rset);
		maxfdp1 = (fileno(fp) > sockfd ? fileno(fp) : sockfd) + 1;
		select(maxfdp1, &rset, NULL, NULL, NULL);

		// socket
		if (FD_ISSET(sockfd, &rset))
		{
			int n = read(sockfd, recvline, MAXLINE);
			if (n == 0)
			{
				if (stdineof == 1)
				{
					return ;
				}
				else
				{
					printf("str_cli: server terminated prematurely\n");
					exit(1);
				}
			}
			else if (n == -1)
			{
				exit(1);
			}
			recvline[n] = '\0';
			fputs(recvline, stdout);
//			write(STDOUT_FILENO, recvline, n);
		}

		// input
		if (FD_ISSET(fileno(fp), &rset))
		{
			// 此处不能使用fgets函数，该函数带有缓冲区功能，select跟带有缓冲区的c函数混合使用有问题
//			if (fgets(sendline, MAXLINE, fp) == NULL)
//			{
//				return ;
//			}
			int n = read(fileno(fp), sendline, MAXLINE);
			if (n == 0)
			{
				stdineof = 1;
				shutdown(sockfd, SHUT_WR);	// 关闭写
				FD_CLR(fileno(fp), &rset);
				continue;
			}
			else if (n == -1)
			{
				exit(1);
			}
			write(sockfd, sendline, n);
		}
	}
}

int main(int argc, char **argv)
{
	int sockfd;
	struct sockaddr_in	servaddr;

	if (argc != 2)
	{
		printf("usage: tcpcli <IPaddress>\n");
		exit(1);
	}

	sockfd = socket(AF_INET, SOCK_STREAM, 0);

	bzero(&servaddr, sizeof(servaddr));
	servaddr.sin_family = AF_INET;
	servaddr.sin_port = htons(SERV_PORT);
	inet_pton(AF_INET, argv[1], &servaddr.sin_addr);

	if (connect(sockfd, (struct sockaddr*)&servaddr, sizeof(servaddr)) != 0)
	{
		printf("connect error...\n");
		exit(1);
	}

	str_cli(stdin, sockfd);		/* do it all */

	exit(0);
}

非阻塞式I/O的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
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
/**
 * 非阻塞式I/O的select版本
 */
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <signal.h>
#include <fcntl.h>

#define SERV_PORT 9877
#define MAXLINE 4096	/* max text line length */
#define max(a,b) ( ((a)>(b)) ? (a):(b) )

/**
 * 优点：速度是最快的，可以防止进程在做任何工作时发生阻塞
 * 缺点：同时管理4个不同的I/O流，每个流都是非阻塞的，需要考虑到4个流的部分读和部分写问题。编码量是最多的，需要引入缓冲区管理机制。
 */
void str_cli(FILE *fp, int sockfd)
{
	// 将socket、标准输入和标准输出描述符设置为非阻塞方式
	int val = fcntl(sockfd, F_GETFL, 0);
	fcntl(sockfd, F_SETFL, val | O_NONBLOCK);

	val = fcntl(STDIN_FILENO, F_GETFL, 0);
	fcntl(STDIN_FILENO, F_SETFL, val | O_NONBLOCK);

	val = fcntl(STDOUT_FILENO, F_GETFL, 0);
	fcntl(STDOUT_FILENO, F_SETFL, val | O_NONBLOCK);

	char to[MAXLINE], fr[MAXLINE];
	char *toiptr, *tooptr, *friptr, *froptr;
	toiptr = tooptr = to;
	friptr = froptr = fr;
	int stdineof = 0;

	int maxfdp1 = max(max(STDIN_FILENO, STDOUT_FILENO), sockfd) + 1;
	fd_set rset, wset;
	for (; ;)
	{
		FD_ZERO(&rset);
		FD_ZERO(&wset);
		if (stdineof == 0 && toiptr < &to[MAXLINE])
		{
			FD_SET(STDIN_FILENO, &rset);
		}
		if (friptr < &fr[MAXLINE])
		{
			FD_SET(sockfd, &rset);
		}
		if (tooptr != toiptr)
		{
			FD_SET(sockfd, &wset);
		}
		if (froptr != friptr)
		{
			FD_SET(STDOUT_FILENO, &wset);
		}
		select(maxfdp1, &rset, &wset, NULL, NULL);	// select函数仍然是阻塞的
		// 标准输入
		if (FD_ISSET(STDIN_FILENO, &rset))
		{
			int n;
			if ((n = read(STDIN_FILENO, toiptr, &to[MAXLINE] - toiptr)) < 0)
			{
				// 对于非阻塞式IO，如果操作不能满足，相应系统调用会返回EWOULDBLOCK错误
				if (errno != EWOULDBLOCK)
				{
					printf("read error on stdin\n");
					exit(1);
				}
			}
			else if (n == 0)
			{
				fprintf(stderr, "EOF on stdin\n");
				stdineof = 1;
				if (tooptr == toiptr)
				{
					shutdown(sockfd, SHUT_WR);	// 缓冲区中没有数据要发送，关闭socket
				}
			}
			else
			{
				fprintf(stderr, "read %d bytes from stdin\n", n);
				toiptr += n;
				FD_SET(sockfd, &wset);
			}
		}

		// 从套接字读
		if (FD_ISSET(sockfd, &rset))
		{
			int n;
			if ((n = read(sockfd, friptr, &fr[MAXLINE] - friptr)) < 0)
			{
				if (errno != EWOULDBLOCK)
				{
					printf("read error on socket\n");
					exit(1);
				}
			}
			else if (n == 0)
			{
				fprintf(stderr, "EOF on socket\n");
				if (stdineof)
				{
					return ;
				}
				else
				{
					printf("server terminated prematurely\n");
					exit(1);
				}
			}
			else
			{
				fprintf(stderr, "read %d bytes from socket\n", n);
				friptr += n;
				FD_SET(STDOUT_FILENO, &wset);
			}
		}

		// 标准输出
		int n;
		if (FD_ISSET(STDOUT_FILENO, &wset) && ((n = friptr - froptr) > 0))
		{
			int nwritten;
			if ((nwritten = write(STDOUT_FILENO, froptr, n)) < 0)
			{
				if (errno != EWOULDBLOCK)
				{
					printf("write error to stdout\n");
					exit(1);
				}
			}
			else
			{
				fprintf(stderr, "wrote %d bytes to stdout\n", nwritten);
				froptr += nwritten;
				if (froptr == friptr)
				{
					froptr = friptr = fr;
				}
			}
		}

		// 向socket写
		if (FD_ISSET(sockfd, &wset) && ((n = toiptr - tooptr)) > 0)
		{
			int nwritten;
			if ((nwritten = write(sockfd, tooptr, n)) < 0)
			{
				if (errno != EWOULDBLOCK)
				{
					printf("write error to socket\n");
					exit(1);
				}
			}
			else
			{
				fprintf(stderr, "wrote %d bytes to socket\n", nwritten);
				tooptr += nwritten;
				if (tooptr == toiptr)
				{
					toiptr = tooptr = to;
					if (stdineof)
					{
						shutdown(sockfd, SHUT_WR);
					}
				}
			}
		}
	}

	return ;
}

/**
 * connect的非阻塞版本
 * 连接建立成功时，描述符变为可写；连接建立错误时，描述符变为即可读又可写
 * 优点：
 * 1、阻塞式的connect调用会消耗CPU时间，非阻塞式connect可以充分利用CPU时间，在等待的过程中可以处理其他工作
 * 2、可以同时建立多个连接，浏览器中会用到此技术
 * 3、阻塞式connect的函数超时过长，可以通过该函数设置超时时间
 * 4、阻塞式的套接字调用connect时，在TCP的三次握手完成之前被某些信号中断时并且connect未设置内核自动重启的标志时，connect将返回EINTR错误
 * 当再次调用connect等待未完成的连接时将会返回EADDRINUSE错误
 */
int connect_nonb(int sockfd, const struct sockaddr *saptr, socklen_t salen, int nsec)
{
	// 将套接字设置为非阻塞状态
	int flags = fcntl(sockfd, F_GETFL, 0);
	fcntl(sockfd, F_SETFL, flags | O_NONBLOCK);

	int error = 0;

	int n;
	if ((n = connect(sockfd, saptr, salen)) < 0)
	{
		// 连接未成功建立，正常情况下返回EINPROGRESS错误，表示操作正在处理
		if (errno != EINPROGRESS)
		{
			// EINPROGRESS表示连接建立已经启动，但是尚未完成
			return -1;
		}
	}
	else if (n == 0)
	{
		// 当服务器和客户端在一台主机上时会立即建立连接
		goto done;
	}

	// 当代码执行到如下过程中时，connect正在建立连接，可以在此位置执行业务相关代码
	// 当然真正使用时，在此位置加入其他代码并不合适，需要根据具体情况重新调整代码
	// 可以参照书中的web客户程序例子

	fd_set rset, wset;
	FD_ZERO(&rset);
	FD_SET(sockfd, &rset);
	wset = rset;

	struct timeval tval;
	tval.tv_sec = nsec;
	tval.tv_usec = 0;
	if ((n = select(sockfd + 1, &rset, &wset, NULL, nsec ? &tval : NULL)) == 0)
	{
		// 发生超时
		close(sockfd);
		errno = ETIMEDOUT;
		return -1;
	}

	// 当连接建立成功时sockfd变为可写，当连接建立失败时sockfd变为即可读又可写
	if (FD_ISSET(sockfd, &rset) || FD_ISSET(sockfd, &wset))
	{
		int len = sizeof(error);
		// 非可移植性函数，连接建立成功返回0，连接建立失败将错误值返回给error
		// 连接建立失败时，有返回-1和返回0的情况
		if (getsockopt(sockfd, SOL_SOCKET, SO_ERROR, &error, &len) < 0)
		{
			// solaris连接建立失败返回-1
			return -1;
		}
	}
	else
	{
		printf("select error:sockfd not set");
		exit(1);
	}
done:
	// 恢复套接字的文件状态标志
	fcntl(sockfd, F_SETFL, flags);
	if (error)
	{
		close(sockfd);
		errno = error;
		return -1;
	}
	return 0;
}

int main(int argc, char **argv)
{
	int sockfd;
	struct sockaddr_in	servaddr;

	if (argc != 2)
	{
		printf("usage: tcpcli <IPaddress>\n");
		exit(1);
	}

	// 当一个进程向某个收到RST的套接字执行写操作时，内核会向该进程发送一个SIGPIPE信号
	// 最好的方式是忽略此信号的处理方式，并在程序下面处理该异常情况
	signal(SIGPIPE, SIG_IGN);

	sockfd = socket(AF_INET, SOCK_STREAM, 0);

	bzero(&servaddr, sizeof(servaddr));
	servaddr.sin_family = AF_INET;
	servaddr.sin_port = htons(SERV_PORT);
	inet_pton(AF_INET, argv[1], &servaddr.sin_addr);

	//connect(sockfd, (struct sockaddr*)&servaddr, sizeof(servaddr));
	if (connect_nonb(sockfd, (struct sockaddr*)&servaddr, sizeof(servaddr), 50) < 0)
	{
		printf("socket connect error\n");
		exit(1);
	}

	str_cli(stdin, sockfd);		/* do it all */

	exit(0);
}

TCP服务端程序

服务器程序要处理大量并发，在设计时更要注重效率。

fork版本

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/**
 * fork版本
 * PPC(Process per Connection)模型
 */
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdlib.h>
#include <stdio.h>
#include <signal.h>
#include <strings.h>

#define SERV_PORT 9877
#define MAXLINE		4096	/* max text line length */

void sig_chld(int signo)
{
	if (signo != SIGIO)
	{
		return;
	}
	int stat;

	/* 此处不可以使用wait函数，当多个SIGCHLD信号同时发出时会因为信号覆盖而出现僵尸进程的情况
	pid_t pid = wait(&stat);
	printf("child %d terminated\n", pid);	// 非异步信号安全函数，此处不应该调用
	*/

	/* 使用非阻塞的参数WNOHANG来循环处理信号，避免信号丢失问题 */
	pid_t pid;
	while ((pid = waitpid(-1, &stat, WNOHANG)) > 0)
	{
		printf("child %d terminated\n", pid);
	}
}

void str_echo(int sockfd)
{
	ssize_t	n;
	char buf[MAXLINE];

again:
	while ( (n = read(sockfd, buf, MAXLINE)) > 0)
	{
		write(sockfd, buf, n);
	}

	if (n < 0 && errno == EINTR)
		goto again;
	else if (n < 0)
		printf("str_echo: read error\n");
}

/**
 * fork版本
 * 缺点：
 * 		1.fork需要将父进程的内存映像复制到子进程，并在子进程中复制所有的描述符，尽管现在的操作系统已经都实现了写时复制技术，但是耗时仍然比较多
 * 		2.父进程和子进程之间需要IPC机制进行通信，从子进程返回信息到父进程比较麻烦
 */
int main(int argc, char *argv[])
{
	signal(SIGCHLD, sig_chld);
    int listenfd, connfd;
    pid_t childpid;
    struct sockaddr_in cliaddr, servaddr;

    // socket
    listenfd = socket(AF_INET, SOCK_STREAM, 0);
    if (listenfd == -1)
    {
		printf("socket error\n");
		exit(1);
	}

    // bind
    bzero(&servaddr, sizeof(servaddr));
    servaddr.sin_family = AF_INET;
    servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
    servaddr.sin_port = htons(SERV_PORT);
    if (bind(listenfd,  (struct sockaddr*)&servaddr, sizeof(servaddr)) == -1)
    {
    	printf("bind error\n");
    	exit(1);
    }

    // listen
    // 套接字排队的最大连接数为20
    if (listen(listenfd, 20) == -1)
    {
    	printf("listen error\n");
    	exit(1);
    }

    for ( ; ; )
    {
    	socklen_t clilen = sizeof(cliaddr);
    	// 处理accept被信号中断时返回EINTR错误
		if ((connfd = accept(listenfd, (struct sockaddr*)&cliaddr, &clilen)) < 0)
		{
			if (errno == EINTR)
			{
				continue;
			}
			else
			{
				printf("accept error");
				exit(1);
			}
		}

		if ((childpid = fork()) == 0)
		{
			/* child process */
			close(listenfd); /* close listening socket */
			str_echo(connfd); /* process the request */
			exit(0);
		}
		close(connfd); /* parent closes connected socket */
	}
}

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
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
/**
 * select版本
 * 缺点：
 * 		1. 有最大并发数限制，一个进程最多打开FD_SETSIZE个文件描述符，FD_SETSIZE往往是1024或2048字节
 * 		2. select每次调用都会线性扫描全部的FD集合，这样效率就会呈现线性下降，把FD_SETSIZE改大的后果就是所有FD处理都慢慢来
 * 		3. 内核/用户空间内存拷贝问题，内核把FD消息通知给用户空间采取了内存拷贝方法
 */
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdlib.h>
#include <stdio.h>
#include <signal.h>
#include <sys/select.h>
#include <strings.h>

#define SERV_PORT 9877
#define MAXLINE		4096	/* max text line length */

/**
 * 使用select的需要维护client数组和allset的描述符集
 */
int main(int argc, char *argv[])
{
    struct sockaddr_in cliaddr, servaddr;

    // socket
    int listenfd = socket(AF_INET, SOCK_STREAM, 0);
    if (listenfd == -1)
    {
    	printf("socket error\n");
    	exit(1);
    }
    printf("finish socket...\n");

    // bind
    bzero(&servaddr, sizeof(servaddr));
    servaddr.sin_family = AF_INET;
    servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
    servaddr.sin_port = htons(SERV_PORT);
    if (bind(listenfd,  (struct sockaddr*)&servaddr, sizeof(servaddr)) == -1)
    {
    	printf("bind error\n");
    	exit(1);
    }
    printf("finish bind...\n");

    // listen
    // 套接字排队的最大连接数为20
    if (listen(listenfd, 20) == -1)
    {
    	printf("listen error\n");
    	exit(1);
    }
    printf("finish listening...\n");

    int maxfd = listenfd;
    int maxi = -1;
    int client[FD_SETSIZE];
    for (int i=0; i<FD_SETSIZE; i++)
    {
    	client[i] = -1;
    }
    fd_set allset;
    FD_ZERO(&allset);
    FD_SET(listenfd, &allset);

    for ( ; ; )
    {
    	fd_set rset = allset;
    	int nready = select(maxfd + 1, &rset, NULL, NULL, NULL);
    	if (FD_ISSET(listenfd, &rset))
    	{
    		// 设置client数组
    		socklen_t clilen = sizeof(cliaddr);
    		// 调用select时有个问题，见书中16.6节
    		// 如果调用accept时客户端已经关闭连接，此时accept会阻塞并直到新的客户端连接到来
    		// 为了解决该问题可以将套接字设置为非阻塞再调用accept
			int connfd = accept(listenfd, (struct sockaddr*)&cliaddr, &clilen);
			printf("accept one client:%d...\n", connfd);
			int i = 0;
			for (; i<FD_SETSIZE; i++)
			{
				if (client[i] < 0)
				{
					client[i] = connfd;
					break;
				}
			}

			FD_SET(connfd, &allset);

			if (i == FD_SETSIZE)
			{
				printf("too many clients");
				exit(-1);
			}
			if (connfd > maxfd)
			{
				maxfd = connfd;
			}
			if (i > maxi)
			{
				maxi = i;
			}
			if (--nready <= 0)
			{
				continue;
			}
    	}

    	// 检测所有客户端的数据
    	for (int i=0; i<=maxi; i++)
    	{
    		if (client[i] < 0)
    		{
    			continue;
    		}
    		if (FD_ISSET(client[i], &rset))
    		{
    			int n;
    			char buf[MAXLINE];
    			printf("start reading form one client...\n");
    			if ((n = read(client[i], buf, MAXLINE)) == 0)
				{
    				close(client[i]);
    				FD_CLR(client[i], &allset);
    				client[i] = -1;
				}
    			else
    			{
    				write(client[i], buf, n);
    			}
    			if (--nready <= 0)
    			{
    				break;
    			}
    		}
    	}
	}
}

poll版本

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
/**
 * poll版本
 * poll版本的解决了select文件描述符限制问题，但是仍然具备select的缺点中的2和3
 */
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdlib.h>
#include <stdio.h>
#include <signal.h>
#include <strings.h>
#include <poll.h>
#include <stropts.h>

#define SERV_PORT 9877
#define MAXLINE		4096	/* max text line length */
#define OPEN_MAX 1024  // 该宏已经从limit.h中移除，用来表示一个进程可以打开的最大描述符数目

/**
 * 使用select的缺点为需要维护client数组
 */
int main(int argc, char *argv[])
{
    struct sockaddr_in cliaddr, servaddr;

    // socket
    int listenfd = socket(AF_INET, SOCK_STREAM, 0);
    if (listenfd == -1)
    {
    	printf("socket error\n");
    	exit(1);
    }
    printf("finish socket...\n");

    // bind
    bzero(&servaddr, sizeof(servaddr));
    servaddr.sin_family = AF_INET;
    servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
    servaddr.sin_port = htons(SERV_PORT);
    if (bind(listenfd,  (struct sockaddr*)&servaddr, sizeof(servaddr)) == -1)
    {
    	printf("bind error\n");
    	exit(1);
    }
    printf("finish bind...\n");

    // listen
    // 套接字排队的最大连接数为20
    if (listen(listenfd, 20) == -1)
    {
    	printf("listen error\n");
    	exit(1);
    }
    printf("finish listening...\n");

    struct pollfd client[OPEN_MAX];
    client[0].fd = listenfd;
    client[0].events = POLLIN;
    for (int i=1; i<OPEN_MAX; i++)
    {
    	client[i].fd = -1;
    }

    int maxi = 0;	// 当前client正在使用的最大下标

    for ( ; ; )
    {
    	int nready = poll(client, maxi + 1, -1);
    	if (client[0].revents & POLLIN)
    	{
    		// 设置client数组
    		socklen_t clilen = sizeof(cliaddr);
			int connfd = accept(listenfd, (struct sockaddr*)&cliaddr, &clilen);
			printf("accept one client:%d...\n", connfd);
			int i = 1;
			for (; i<OPEN_MAX; i++)
			{
				if (client[i].fd < 0)
				{
					client[i].fd = connfd;
					break;
				}
			}

			if (i == OPEN_MAX)
			{
				printf("too many clients");
				exit(-1);
			}
			client[i].events = POLLIN;
			if (i > maxi)
			{
				maxi = i;
			}
			if (--nready <= 0)
			{
				continue;
			}
    	}

    	// 检测所有客户端的数据
    	for (int i=0; i<=maxi; i++)
    	{
    		if (client[i].fd < 0)
    		{
    			continue;
    		}
    		if (client[i].revents & (POLLIN | POLLERR))
    		{
    			int n;
    			char buf[MAXLINE];
    			printf("start reading form one client...\n");
    			if ((n = read(client[i].fd, buf, MAXLINE)) < 0)
				{
    				if (errno == ECONNRESET)
    				{
    					close(client[i].fd);
    					client[i].fd = -1;
    				}
    				else
    				{
    					printf("read client error\n");
    					exit(-1);
    				}
				}
    			else if (n == 0)
    			{
    				printf("client %d close\n", client[i].fd);
    				close(client[i].fd);
    				client[i].fd = -1;
    			}
    			else
    			{
    				write(client[i].fd, buf, n);
    			}
    			if (--nready <= 0)
    			{
    				break;
    			}
    		}
    	}
	}
}

多线程版本

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
95
96
97
98
99
/**
 * 多线程版本
 * TPC(Thread Per Connection)模型
 * 线程的开销虽然比进程小，但是仍然有比较大开销，因此并发数不是很高
 */
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdlib.h>
#include <stdio.h>
#include <signal.h>
#include <strings.h>
#include <pthread.h>

#define SERV_PORT 9877
#define MAXLINE		4096	/* max text line length */

void str_echo(int sockfd)
{
	ssize_t	n;
	char buf[MAXLINE];

again:
	while ( (n = read(sockfd, buf, MAXLINE)) > 0)
	{
		write(sockfd, buf, n);
	}

	if (n < 0 && errno == EINTR)
		goto again;
	else if (n < 0)
		printf("str_echo: read error\n");
}

static void *doit(void *arg)
{
	pthread_detach(pthread_self());
	str_echo((int)arg);
	close((int)arg);
	printf("close socket...\n");
	return NULL;
}

int main(int argc, char *argv[])
{
    int listenfd, connfd;
    struct sockaddr_in cliaddr, servaddr;

    // socket
    listenfd = socket(AF_INET, SOCK_STREAM, 0);
    if (listenfd == -1)
    {
		printf("socket error\n");
		exit(1);
	}

    // bind
    bzero(&servaddr, sizeof(servaddr));
    servaddr.sin_family = AF_INET;
    servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
    servaddr.sin_port = htons(SERV_PORT);
    if (bind(listenfd,  (struct sockaddr*)&servaddr, sizeof(servaddr)) == -1)
    {
    	printf("bind error\n");
    	exit(1);
    }

    // listen
    // 套接字排队的最大连接数为20
    if (listen(listenfd, 20) == -1)
    {
    	printf("listen error\n");
    	exit(1);
    }

    for ( ; ; )
    {
    	socklen_t clilen = sizeof(cliaddr);
    	// 处理accept被信号中断时返回EINTR错误
		if ((connfd = accept(listenfd, (struct sockaddr*)&cliaddr, &clilen)) < 0)
		{
			if (errno == EINTR)
			{
				continue;
			}
			else
			{
				printf("accept error");
				exit(1);
			}
		}
		printf("receive new client...\n");
		pthread_t tid;
		pthread_create(&tid, NULL, &doit, (void *)connfd);
	}
}

UDP

由于udp比较简单，书中并未将udp协议当做重点来讲解。

UDP客户端程序

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
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdlib.h>
#include <stdio.h>
#include <signal.h>
#include <strings.h>

#define SERV_PORT 9877
#define MAXLINE		4096	/* max text line length */

// sendto、recvfrom方式
void dg_cli(FILE *fp, int sockfd, const struct sockaddr *pservaddr, socklen_t servlen)
{
	char sendline[MAXLINE], recvline[MAXLINE + 1];
	struct sockaddr *preply_addr = (struct sockaddr *)malloc(servlen);

	while (fgets(sendline, MAXLINE, fp) != NULL)
	{
		sendto(sockfd, sendline, strlen(sendline), 0, pservaddr, servlen);
		int len = servlen;
		int n = recvfrom(sockfd, recvline, MAXLINE, 0, preply_addr, &len);
		// 为了防止接收到其他进程的数据，通过条件判断去除
		if (len != servlen || memcmp(pservaddr, preply_addr, len) != 0)
		{
			printf("reply from others (!ignore)\n");
			continue;
		}
		recvline[n] = 0;
		fputs(recvline, stdout);
	}
}

// connect、write、read方式
void dg_cli2(FILE *fp, int sockfd, const struct sockaddr *pservaddr, socklen_t servlen)
{
	char sendline[MAXLINE], recvline[MAXLINE + 1];

	connect(sockfd, (struct sockaddr *)pservaddr, servlen);

	while (fgets(sendline, MAXLINE, fp) != NULL)
	{
		write(sockfd, sendline, strlen(sendline));
		int n = read(sockfd, recvline, MAXLINE);
		recvline[n] = 0;
		fputs(recvline, stdout);
	}
}

int main(int argc, char *argv[])
{
	if (argc != 2)
	{
		printf("usage: tcpcli <IPaddress>\n");
		exit(1);
	}

	struct sockaddr_in servaddr;
	bzero(&servaddr, sizeof(servaddr));
	servaddr.sin_family = AF_INET;
	servaddr.sin_port = htons(SERV_PORT);
	inet_pton(AF_INET, argv[1], &servaddr.sin_addr);

	int sockfd = socket(AF_INET, SOCK_DGRAM, 0);
	dg_cli2(stdin, sockfd, (struct sockaddr*)&servaddr, sizeof(servaddr));
	exit(0);
}

UDP服务端程序

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
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdlib.h>
#include <stdio.h>
#include <signal.h>
#include <strings.h>

#define SERV_PORT 9877
#define MAXLINE		4096	/* max text line length */

void dg_echo(int sockfd, struct sockaddr *pcliaddr, socklen_t clilen)
{
	char mesg[MAXLINE];
	for (;;)
	{
		socklen_t len = clilen;
		int n;
		bzero(mesg, MAXLINE);
		if ((n = recvfrom(sockfd, mesg, MAXLINE, 0,  pcliaddr, &len)) < 0)
		{
			close(sockfd);
			printf("recvfrom error, error=%m\n");
			exit(1);
		}
		printf("recv %s\n", mesg);
		sendto(sockfd, mesg, n, 0, pcliaddr, len);
	}
}

int main(int argc, char *argv[])
{
	int sockfd = socket(AF_INET, SOCK_DGRAM, 0);
	struct sockaddr_in servaddr, cliaddr;
	bzero(&servaddr, sizeof(servaddr));
	servaddr.sin_family = AF_INET;
	servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
	servaddr.sin_port = htons(SERV_PORT);
	if (bind(sockfd,  (struct sockaddr*)&servaddr, sizeof(servaddr)) < 0)
	{
		printf("bind error\n");
		exit(1);
	}

	dg_echo(sockfd, (struct sockaddr*)&cliaddr, sizeof(cliaddr));
}

UDP服务端信号驱动式I/O版本

信号驱动式I/O：进程执行I/O系统调用告知内核启动某个I/O操作，内核启动I/O操作后立即返回到进程。进程在I/O操作发生期间继续执行。当操作完成或遇到错误时，内核以进程在I/O系统调用中指定的方式通知进程。

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
/**
 * 信号驱动式I/O在TCP套接字用途不大，该信号产生的过于频繁，它的出现并未指示发生的事情
 */
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdlib.h>
#include <stdio.h>
#include <signal.h>
#include <strings.h>
#include <fcntl.h>

#define SERV_PORT 9877
#define MAXLINE		4096	/* max text line length */

static int sockfd;

#define MAXDG 4096


typedef struct
{
	void *dg_data;				// 实际数据
	size_t dg_len;				// 实际数据长度
	struct sockaddr *dg_sa;		// 包含客户端地址
	socklen_t dg_salen;			// 客户端地址长度
} DG;

#define QSIZE 8
static DG dg[QSIZE];			// 存放数据的环形缓冲区

static long cntread[QSIZE + 1];
// 需要处理的下一个数据元素的下标
static int iget;
// 存放数据元素的下一个位置
static int iput;
static int nqueue;				// 队列中的数据个数
static socklen_t clilen;

static void sig_hup(int signo)
{
	int i=0;
	for (; i <= QSIZE; i++)
	{
		printf("cntread[%d = %ld\n", i, cntread[i]);
	}
}

static void sig_io(int signo)
{
	int nread;
	// 为了解决非实时信号不排队问题，采用循环读取方式
	for (nread = 0; ; )
	{
		// 检查队列是否已满
		if (nread >= QSIZE)
		{
			printf("receive overflow\n");
			exit(1);
		}
		DG *ptr = &dg[iput];
		ptr->dg_salen = clilen;
		ssize_t len = recvfrom(sockfd, ptr->dg_data, MAXDG, 0, ptr->dg_sa, &ptr->dg_salen);
		if (len < 0)
		{
			if (errno == EWOULDBLOCK)
			{
				break;
			}
			else
			{
				printf("recvfrom error\n");
				exit(1);
			}
		}
		ptr->dg_len = len;
		nread++;
		nqueue++;
		if (++iput >= QSIZE)
		{
			iput = 0;
		}
	}
	cntread[nread]++;
}

void dg_echo(int sockfd_arg, struct sockaddr *pcliaddr, socklen_t clilen_arg)
{
	sockfd = sockfd_arg;
	clilen = clilen_arg;
	int i = 0;
	for (; i<QSIZE; i++)
	{
		dg[i].dg_data = malloc(MAXDG);
		dg[i].dg_sa = (struct sockaddr *)malloc(clilen);
		dg[i].dg_salen = clilen;
	}
	iget = iput = nqueue = 0;
	signal(SIGHUP, sig_hup);

	// 在启动信号I/O前设置信号处理函数
	signal(SIGIO, sig_io);

	// 设置接收信号通知的进程，让本进程接收SIGIO信号
	fcntl(sockfd, F_SETOWN, getpid());

	// 为了能够在得到I/O事件后重复执行I/O操作，需要将文件描述符设置为非阻塞方式
	// O_ASYNC表示在文件描述符上使用信号驱动I/O
	int flags = fcntl(sockfd, F_GETFL);
	fcntl(sockfd, F_SETFL, flags | O_ASYNC | O_NONBLOCK);

	sigset_t zeromask, newmask, oldmask;
	sigemptyset(&zeromask);
	sigemptyset(&newmask);
	sigemptyset(&oldmask);

	// 设置新的信号掩码，阻塞SIGIO信号
	sigaddset(&newmask, SIGIO);
	sigprocmask(SIG_BLOCK, &newmask, &oldmask);
	for (; ;)
	{
		while (nqueue == 0)
		{
			// 挂起进程直到收到任何信号，该函数返回后SIGIO继续被阻塞
			sigsuspend(&zeromask);
		}
		// 解除SIGIO的阻塞
		sigprocmask(SIG_SETMASK, &oldmask, NULL);
		sendto(sockfd, dg[iget].dg_data, dg[iget].dg_len, 0, dg[iget].dg_sa, dg[iget].dg_salen);
		if (++iget >= QSIZE)
		{
			iget = 0;
		}
		// 为了能够修改nqueue的值，阻塞SIGIO信号
		sigprocmask(SIG_BLOCK, &newmask, &oldmask);
		nqueue--;
	}
}

int main(int argc, char *argv[])
{
	int sockfd = socket(AF_INET, SOCK_DGRAM, 0);
	struct sockaddr_in servaddr, cliaddr;
	bzero(&servaddr, sizeof(servaddr));
	servaddr.sin_family = AF_INET;
	servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
	servaddr.sin_port = htons(SERV_PORT);
	if (bind(sockfd,  (struct sockaddr*)&servaddr, sizeof(servaddr)) < 0)
	{
		printf("bind error\n");
		exit(1);
	}

	dg_echo(sockfd, (struct sockaddr*)&cliaddr, sizeof(cliaddr));
	return 1;
}

相关下载

本文中的实例，代码采用eclipse CDT编写，可以直接导入eclipse中运行。

下载实例

Posted on Edited on

最近这段时间回顾了下python，距离上次使用python已经超过两年的时间了。

相对于c++语言，python要灵活许多，对于工作中的一些小问题的解决可以通过python来实现比较高效和方便，比如网页的抓取和解析。甚至对于非IT的工作，也可以通过脚本的方式来解决，只要是工作中遇到反复处理的体力活劳动就可以考虑利用编程方式来解决。

本文以我的博客的文档列表页面为例，利用python对页面中的文章名进行提取。

文章列表页中的文章列表部分的url如下：

1
2
3
4
5
6
7
<ul class="listing">
    <li class="listing-item"><span class="date">2014-12-03</span><a href="/post/linux_funtion_advance_feature"  title="Linux函数高级特性" >Linux函数高级特性</a>
    </li>
    <li class="listing-item"><span class="date">2014-12-02</span><a href="/post/cgdb"  title="cgdb的使用" >cgdb的使用</a>
    </li>
...
</ul>

requests模块的安装

requests模块用于加载要请求的web页面。

在python的命令行中输入import requests，报错说明requests模块没有安装。

我这里打算采用easy_install的在线安装方式安装，发现系统中并不存在easy_install命令，输入sudo apt-get install python-setuptools来安装easy_install工具。

执行sudo easy_install requests安装requests模块。

Beautiful Soup安装

为了能够对页面中的内容进行解析，本文使用Beautiful Soup。当然，本文的例子需求较简单，完全可以使用分析字符串的方式。

执行sudo easy_install beautifulsoup4即可安装。

编码问题

python的编码问题确实是一个很头大的问题，尤其是对于不熟悉python的菜鸟。

python自身的编码问题就已经够头大的了，碰巧requests模块也有一个编码问题的bug，具体的bug见参考文章。

代码

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
#!/usr/bin/env python                                                                                                                                                           
# -*- coding: utf-8 -*-

' a http parse test programe '

__author__ = 'kuring lv'


import requests
import bs4

archives_url = "http://kuring.me/archive"

def start_parse(url) :
    print "开始获取(%s)内容" % url
    response = requests.get(url)
    print "获取网页内容完毕"
    
    soup = bs4.BeautifulSoup(response.content.decode("utf-8"))
    #soup = bs4.BeautifulSoup(response.text);
    
    # 为了防止漏掉调用close方法，这里使用了with语句
    # 写入到文件中的编码为utf-8
    with open('archives.txt', 'w') as f :
        for archive in soup.select("li.listing-item a") :
            f.write(archive.get_text().encode('utf-8') + "\n")
            print archive.get_text().encode('utf-8')

# 当命令行运行该模块时，__name__等于'__main__'
# 其他模块导入该模块时，__name__等于'parse_html'
if __name__ == '__main__' :
    start_parse(archives_url)

参考文章

Posted on Edited on

最近学习了《GNU Make项目管理》，改进了我之前一直在用的Makefile文件，解决我之前的Makefile中一直存在的修改依赖头文件后不能自动编译cpp文件的问题。本文列举了我常用的两个Makefile文件，其中第一个为我常用的Makefile，第二个为从网上找到的其他Makefile文件。

第一个Makefile

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
all:
INCLUDE = -I./

FLAGS = -g -Wall $(INCLUDE)
FLAGS += -fPIC

LIBDIR = -lz -lm -lcrypto

LINK = $(LIBDIR) -lpthread

GCC = g++

# for C++ language
CODE.cpp = main.cpp \
			trim.cpp

CPP.o = $(CODE.cpp:.cpp=.o)
OBJS.d = $(CODE.cpp:.cpp=.d)

OBJS.o = $(CPP.o)

# 解决头文件依赖
-include $(subst .cpp,.d,$(CODE.cpp))

%.d: %.cpp
	$(GCC) -M $(FLAGS) $< > $@.$$$$;		\
	sed 's,\($*\)\.o[ :]*,\1.o $@ : ,g' < $@.$$$$ > $@;	\
	rm -f $@.$$$$

# rule for C++ language
%.o : %.cpp	
	$(GCC) $(FLAGS) -o $@ -c $<	
	@echo $*.o build successfully!......

TARGET = main
	
$(TARGET) : $(OBJS.o) 
	$(GCC) $(OBJS.o) -o $(TARGET) $(LINK)
	@echo $(TARGET) BUILD OK!.........

all : $(TARGET)

.PHONY:
clean:
	rm -rf $(TARGET)
	rm -rf $(OBJS.o)
	rm -rf $(OBJS.d)
	rm -rf *.d

该文件特点为需要手工将需要编译的源文件手动添加到Makefile中，可能比较麻烦，但是编译时比较灵活。可以随意修改需要编译源文件的顺序和是否需要编译源文件。

第二个Makefile

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
95
###########################################################
#
# KEFILE FOR C/C++ PROJECT
# Author: swm8023 <swm8023@gmail.com>
# Date:   2014/01/30
#
###########################################################

.PHONY: all clean
all: 

# annotation when release version
DEBUG       := y
TARGET_PROG := main

# project directory	
DEBUG_DIR   := ./Debug
RELEASE_DIR := ./Release
BIN_DIR     := $(if $(DEBUG), $(DEBUG_DIR), $(RELEASE_DIR))

# shell command
CC    := gcc
CXX   := g++
RM    := rm -rf
MKDIR := mkdir -p
SED   := sed
MV    := mv

# init sources & objects & depends
sources_all := $(shell find . -name "*.c" -o -name "*.cpp" -o -name "*.h")
sources_c   := $(filter %.c, $(sources_all))
sources_cpp := $(filter %.cpp, $(sources_all))
sources_h   := $(filter %.h, $(sources_all))
objs        := $(addprefix $(BIN_DIR)/,$(strip $(sources_cpp:.cpp=.o) $(sources_c:.c=.o)))
deps        := $(addprefix $(BIN_DIR)/,$(strip $(sources_cpp:.cpp=.d) $(sources_c:.c=.d)))

# create directory
$(foreach dirname,$(sort $(dir $(sources_c) $(sources_cpp))),\
  $(shell $(MKDIR) $(BIN_DIR)/$(dirname)))

# complie & link variable
CFLAGS     := $(if $(DEBUG),-g -O, -O2)
CFLAGS     += $(addprefix -I ,$(sort $(dir $(sources_h))))
CXXFLAGS    = $(CFLAGS)
LDFLAGS    := 
LOADLIBES  += #-L/usr/include/mysql
LDLIBS     += #-lpthread -lmysqlclient

# add vpath
vpath %.h $(sort $(dir $(sources_h)))
vpath %.c $(sort $(dir $(sources_c)))
vpath %.cpp $(sort $(dir $(sources_cpp)))

# generate depend files
# actually generate after object generated, beacasue it only used when next make)
ifneq "$(MAKECMDGOALS)" "clean"
sinclude $(deps)
endif

# make-depend(depend-file,source-file,object-file,cc)
define make-depend
  $(RM) $1;                                     \
  $4 $(CFLAGS) -MM $2 |                         \
  $(SED) 's,\($(notdir $3)\): ,$3: ,' > $1.tmp; \
  $(SED) -e 's/#.*//'                           \
         -e 's/^[^:]*: *//'                     \
         -e 's/ *\\$$//'                        \
         -e '/^$$/ d'                           \
         -e 's/$$/ :/' < $1.tmp >> $1.tmp;      \
  $(MV) $1.tmp $1;
endef

# rules to generate objects file
$(BIN_DIR)/%.o: %.c
	@$(call make-depend,$(patsubst %.o,%.d,$@),$<,$@,$(CC))
	$(CC) $(CFLAGS) -o $@ -c $<

$(BIN_DIR)/%.o: %.cpp
	@$(call make-depend,$(patsubst %.o,%.d,$@),$<,$@,$(CXX))
	$(CXX) $(CXXFLAGS) -o $@ -c $<

# add-target(target,objs,cc)
define add-target
  REAL_TARGET += $(BIN_DIR)/$1
  $(BIN_DIR)/$1: $2
	$3 $(LDFLAGS) $$^ $(LOADLIBES) $(LDLIBS) -o $$@
endef

# call add-target
$(foreach targ,$(TARGET_PROG),$(eval $(call add-target,$(targ),$(objs),$(CXX))))

all: $(REAL_TARGET) $(TARGET_LIBS)

clean: 
	$(RM) $(BIN_DIR)

该Makefile为从一个通用的C/C++ Makefile中直接获得的，为了避免原博客以后不能访问的情况，这里备份一下。

该Makefile可以动检测Makefile所在目录及其子目录中的.c和.cpp文件，并进行编译，不需要手动修改Makefile来填写需要编译的源文件，比较自动化。

相关参考

第二个Makefile文件的作者博客中的两篇文章：GNU Make学习总结（一）和GNU Make学习总结（二）

相关下载

一个包含上述两个Makefile的例子

0%