C++博客-从头再来

QuickSort

易宝@byhh — Sat, 30 May 2015 15:22:00 GMT

复习快排

    int buf[1024] = {0};

    int partition(int first, int last)
    {
        int stand = buf[last];
        int i =0, j=0;
        //int e = last -1;
        for (;j <  last  ; j++ )
        {
            if (buf[j] <= stand )
            {
                int temp = buf[j];
                buf[j] = buf[i];
                buf[i] = temp;
                i++;
            }
        }
        int temp = buf[last];
        buf[last] = buf[i];
        buf[i] = temp;
        return i;
    }

    void myQuickSort(int begin, int end)
    {
        if (begin < end)
        {
            int pivot ;
            pivot = partition(begin, end);
myQuickSort(begin, pivot -1 );
            myQuickSort(pivot+1, end);
}
    }

int main()
{
srand(time(0));
    for (int i = 0; i < 1000; i++)
    {
        buf[i] = rand()  * 2342111134 % 6589453 ;
    }
    myQuickSort(0,1023);
  return 0;
}

在本实现里面，直接使用了最后一个元素作为基准。

在选择基准时其实是有多种方式的。1）选第一个，不推荐。2）算最后一个，不推荐。3）选首、尾、中的中间值。4）随机选择。

选择后将跑一趟比较，结果是左侧为小的数，右侧为大的数，原理是i,j 当数小于基准是则与左右的i 对换，这样保证了i左侧小于p i 到j 之间是大小p 的。

对于p 无需再排了。

需要特别注意的是partition 里面的元素位置与quicksort 分段是有关系的。如果在partition 里面处理了last 那么在分段时其实last 就不用了。

易宝@byhh 2015-05-30 23:22 发表评论

重学TCP协议(一)

易宝@byhh — Sat, 16 May 2015 13:58:00 GMT

目的：重新梳理TCP，全局理解协议中的细节，知道是怎样实现的，理解为什么要这样做，了解可能会带来什么问题。

PS:图片有空了慢慢贴。

简要介绍：

TCP协议是基于网络层IP协议的传输层协议，提供一种面向连接的，可靠的字节流服务(byte stream service )。在TCP连接中，仅支持两方进行彼此通信。

TCP的可靠性由以下方式来提供：

1）恰当的数据分段。即将字节流根据MSS来封包发送。

2）确认机制、重传机制。

3）首部的检验和。

4）网络层的IP数据报可能会失序，因此TCP需要将数据进行重新排序。

5）数据报可能会重复，必须恰当的丢弃重复的数据报。

6） TCP提供流量控制，可根据另一端的缓冲区情况发送恰当的数据（滑动窗口协议）。

7） TCP协议对字节流不作解释。由应用层对数据进行语义上的解释。

随便抓个包：

IP数据头

TCP数据头

头部中比较重要的数据结构

源端口，目的端口，序号，确认序号。标志位，窗口大小。

URG：紧急指针，一般用不上，忽略。

ACK：经常用，接收端发给源端，确认前一个包已收到。

PSH：个人没怎么碰到过。

RST：可以理解为重置连接，普通情况下当目标端口未开放会发送此RST回来，此外，连接中间的防火墙等网络设备也会发。

SYN：发起连接的标志，SYN Flood是基于的一种DOS攻击手法。

FIN：shutdown 时发送，告诉对方，我这边完成了，要送掉连接了。

1、 TCP连接的建议，三步握手。

1）源端发送SYN到服务器，表示喜娃怀与服务器的某个端口建立TCP连接，在TCP首部带上初始的序号（client ISN）。此报文中设置SYN=1；

2）服务器返回SYN包，带上服务器的初始序号（server ISN），并且ACK=client ISN+1设置SYN=1,ACK=1；

3）源端返回服务器ACK包， ack = server ISN+1;

PS:这边的Seq居然从0开始，之前都没注意过~~

关于ISN的选择，根据文献内容，应当随时间变化，避免网络中被延迟的分组被重新传递后导致的错误解释。

2、 TCP连接的终止，四步握手。

1）首先关闭的一方（A）发送FIN包。FIN在应用层、开发者面前就是socket.read 将返回EOF。

2）接受端（B）返回FIN的ACK包。

3） B关闭连接，发送FIN。

4） A发送ACK。

关闭阶段存在另外两衍生的流程。1） 2与3 两步可以合并，当B端无数据发送时，无需发放两个包，可以在一个包里面同时设置FIN+ACK，也就是上面的截图。2）当仅一端调用shutdown，另一端还存在数据发送时，存在半关闭连接的情况。即第2步结束后，B端继续发送数据，A端对这些数据仍然发送ACK，一直到B端发送FIN。

以下是一个简单的client + server 测试代码，通过简单的Sleep可以看出，当收到FIN包时，缓冲区的数据仍然存在，仅在后面多了一个EOF而已。

1 #!/usr/bin/env python
2 import socket
3 import time
4
5 host="192.168.5.106"
6 port=10000
7 s=socket.socket(socket.AF_INET,socket.SOCK_STREAM)
8 s.bind((host,port))
9 s.listen(5)
10 sock,addr=s.accept()
11 print "got connection form ",sock.getpeername()
12 while 1:
13   data=sock.recv(1)
14   time.sleep(0.1)
15   if not data:
16     print("~~~~~")
17     break
18   else:
19 print data
20

1 #!/usr/bin/env python
2 import socket
3 host="192.168.5.106"
4 port=10000
5 s=socket.socket(socket.AF_INET,socket.SOCK_STREAM)
6 s.connect((host,port))
7 s.send("hello from client")
8 s.close()

易宝@byhh 2015-05-16 21:58 发表评论

不忘初心方得始终

易宝@byhh — Tue, 05 May 2015 09:58:00 GMT

《程序员必读的职业规划书》

最开始好像是在微博上看到pdf版本，挺长挺有层次的一篇文章。

最近半年也是有点动的想法，但其实在规划这件事情上做的不够，有个参考指南可以慢慢对比一下自身

易宝@byhh 2015-05-05 17:58 发表评论

使用putty配置SSH通道，然后你懂的

易宝@byhh — Fri, 06 Feb 2015 07:15:00 GMT

因为某wall的原因，大家需要一个通道。

现在比较好的办法是使用hk或其他地方的vps ，然后搭个ssh过去，再使用Sock代理。

putty 已自带ssh通道的功能。但其不支持记住密码。很烦。

网上传的很多教程中使用了 myentunnel 。结果下载后一下，这逗比工具使用的还是putty，既然如此，何必使用额外的工具。

putty虽然记住密码不方便，但使用SSH自带的证书功能，也是可以实现自动登录的~

1、使用puttygen 生成密钥对。此处的 key passphrase 填写后，最终的private key 使用需要密码。。因此可以不填。

2、将public key 放入 /home/user/.ssh/authorized_keys中。此处需确保 .ssh authorized_keys 对其他用户仅可读。如755，否则无法使用。

3、在putty的Connection -> ssh -> auth 处可以选择private key .

4、在Connection -> Data 处可选填auto-login username。

5、为确保不会自动掉线，Connection keepalive 填上非0。如30

6、再save就行啦。后面再使用就方便了。

不过此种方法因为需要使用私钥文件，且对私钥文件无passphrase保护，需保证私钥的安全性，如放在私密的U盘中，仅使用时插上，离开时带走。

易宝@byhh 2015-02-06 15:15 发表评论

为线程命名

易宝@byhh — Fri, 30 Jan 2015 05:53:00 GMT

为Linux下线程加个名字。同样的Windows 也可以干。 chrome 的源码中有使用到这个trick，raise 一个Exception.

1 #include 
2 void set_thread_name(const char *prefix)
3 {
4     static int index = 0;
5     char thname[16];
6      snprintf(thname, sizeof(thname), "%s%d", prefix, __sync_fetch_and_add(&index, 1));
7     prctl(PR_SET_NAME, (usigned long)thname, 0, 0, 0); //~ refer to `man prctl`
8 }
9 


windows 版本 原文见:http://msdn.microsoft.com/en-us/library/xcb2z8hs(VS.90).aspx

//
// Usage: SetThreadName (-1, "MainThread");
//
#include 
const DWORD MS_VC_EXCEPTION=0x406D1388;

#pragma pack(push,8)
typedef struct tagTHREADNAME_INFO
{
   DWORD dwType; // Must be 0x1000.
   LPCSTR szName; // Pointer to name (in user addr space).
   DWORD dwThreadID; // Thread ID (-1=caller thread).
   DWORD dwFlags; // Reserved for future use, must be zero.
} THREADNAME_INFO;
#pragma pack(pop)

void SetThreadName( DWORD dwThreadID, char* threadName)
{
   THREADNAME_INFO info;
   info.dwType = 0x1000;
   info.szName = threadName;
   info.dwThreadID = dwThreadID;
   info.dwFlags = 0;

   __try
   {
      RaiseException( MS_VC_EXCEPTION, 0, sizeof(info)/sizeof(ULONG_PTR), (ULONG_PTR*)&info );
   }
   __except(EXCEPTION_EXECUTE_HANDLER)
   {
   }
}

易宝@byhh 2015-01-30 13:53 发表评论

Linux高性能服务器编程阅读随笔（一）

易宝@byhh — Tue, 21 Oct 2014 11:14:00 GMT

Page 76 . 5.4 监听socket

此处作者说法不完整。

通过Google "man listen " http://linux.die.net/man/2/listen

listen() marks the socket referred to by sockfd as a passive socket, that is, as a socket that will be used to accept incoming connection requests using accept(2).

The sockfd argument is a file descriptor that refers to a socket of type SOCK_STREAM or SOCK_SEQPACKET.

The backlog argument defines the maximum length to which the queue of pending connections for sockfd may grow. If a connection request arrives when the queue is full, the client may receive an error with an indication of ECONNREFUSED or, if the underlying protocol supports retransmission, the request may be ignored so that a later reattempt at connection succeeds.

可见与实现有关。

书的内容还是很全的，但作者的观点略感觉不对。服务器中用信号来通知的，或者说来做异步的，就我了解是几乎没有。作者去花了很多篇幅去介绍。

让人感觉完全是为了凑字数啊。书名里面的“高性能”要打个折扣了

易宝@byhh 2014-10-21 19:14 发表评论

reservoir sampling

易宝@byhh — Tue, 21 Oct 2014 05:09:00 GMT

今天和某同学聊到面试题，他提到被某投行打击很深的一个reservoir sampling问题。

于是我翻了翻。大致意思在网上很容易找到。

难是难理解其中的思维点：怎么发现的这个解法。

也就是如何诠释你的归纳法的出发点。

目前我的总结是，对于这种无限问题，先设定一个基础的通解。即在n的时候成立，再想办法证明当n = n+1的时候，结论也成立，或与原结论存在一定的对应关系。

这样就可以推导出来了。

易宝@byhh 2014-10-21 13:09 发表评论

个人梳理

易宝@byhh — Sun, 19 Oct 2014 13:06:00 GMT

干活四年，有近两年在打酱油。昨天与某前辈聊了聊，也发现确实荒废太多。

近期
1、重点把书完整的看一看。

2、把现有知识梳理一下，知道的与了解的都列一列。

3、有代码相关的多写一写，加强一下。

4、有设计相关的多想一想，不要“原来如此”，而要多“为什么不这样”。

易宝@byhh 2014-10-19 21:06 发表评论

手上的书籍

易宝@byhh — Mon, 22 Sep 2014 12:34:00 GMT

一、数据结构与算法分析

二、算法导论

三、unix环境高级编程

四、设计模式

五、linux 设备驱动程序

六、数学之美

七、c和指针

八、boost程序库完全开发指南

九、c++反汇编与逆向分析

十、python基础教程

十一、编程珠玑

十二、程序员自我修养

十三、Linux 多线程服务端编程

十四、大规模分布式存储系统（公司的）

十五、深入理解Linux内核

十六、格蠹汇编

十七、深入Linux内核架构

十八、TCP/IP详解

十九、UNIX网络编程套接字

二十、UNIX网络编程进程间通信（这两本速度的看完扔了）

二十一、ddos攻击与防范深度剖析

二十二、深入C++对象模型

二十三、Web前端黑客技术揭秘

易宝@byhh 2014-09-22 20:34 发表评论

syslog reload failed service syslog dead

易宝@byhh — Fri, 04 Jul 2014 08:36:00 GMT

今天碰到syslog 服务过阵子就会dead的情况。经多次确认，是打包的时候，脚本里面会执行syslog reload 导致。

而相同的配置文件restart 是OK的。

回来重新测试后，发现有个文件是不能读取的。也就是 appArmor 的权限没有配置。

经再次回忆，是当天晚上上线，本来应该将snmp 的目录 /var/log/* r , 写到配置文件中，但由于认为messages 同样在这个目录下，已经可读，就没有配置。

最后导致syslog reload 就失败。

易宝@byhh 2014-07-04 16:36 发表评论