RValue Reference

发表于 2018-03-30

In C++, there are rvalues and lvalues. An lvalue is an expression whose address can be taken, a locator value–essentially, an lvalue provides a (semi)permanent piece of memory. You can make assignments to lvalues.
An expression is an rvalue if it results in a temporary object.

比如说：

1 2 3 4 5 6 7 8

int a = 1; string b = 'lijinlong'; int& getRef() { return a; } getRef() = 3;

其中a、b、getRef()都是lvalue。

1 2 3 4 5 6

string getName() { return "lijinlong"; } getName(); string str(string("hahaha"));

getName()、string(“hahaha”)是rvalue。

C++11引入了RValue Reference，可以这样定义：

1	typename&& ref;

引入RValue Reference的目的是为了避免对临时变量不必要的复制。一般用在构造函数或者是=重载函数的参数上。
标准库中提供了std::move(lvalue)函数来把一个lvalue转换成一个rvalue。详细用法以及需要注意的问题见参考。

参考：
Move semantics and rvalue references in C++11

C++ Object Model

发表于 2018-03-30

C++类的内存布局如下：

当类存在虚函数的时候，类的内存布局中将会多出一个vptr的虚函数表指针，其指向的不仅仅有虚函数表，还包括成员变量的类型信息。如果是单继承，那类的内存布局将会是下面这样的：

如果是多继承，内存布局是这样的：

上面几幅图的布局作为参考，不同的编译器实现会不同。

参考：
Inheritance in C++

关于公司

发表于 2018-03-29

青睐每一家Engineering Driven却又不坑员工的公司。

c++11的condition_variable

发表于 2018-03-22

C++11提供了一种类似于二值信号量的condition_variable，用法如下：

1 2 3 4 5 6 7

/* thread A */ cv.notify_one(); // or cv.notify_all(); /* thread B */ cv.wait(); // or cv.wait_for()、cv.wait_util()

Reference:
C++11 condition_variable

MTU和MSS

发表于 2018-03-17

MTU(Maximum Transmission Unit)
MSS(Maximum Segment Size)

为防止IP datagram的分片，MTU可通过Path MTU Discovery来调整。
TCP/IP 协议栈中，为什么选择 IP 层负责分片？
WIKIPEDIA: Path MTU Discovery

小明的故事

发表于 2018-03-17

一天早上，小明在家里无聊，打开编辑器写了一段程序：

1 2 3 4 5 6 7

#include <cstdio> int main() { printf("55555\n"); printf("Xiao Ming loves Xiao Dong.\n"); return 0; }

小明喜欢着他的室友小东，可是他一直都不敢说，因为他怕说了之后，就连室友都做不了了，所以只能在无聊的时候写写这样的程序来发发牢骚。
编译，运行，命令行显示出以下结果：

1 2 3 4 5

xiaoming@ubuntu:~/code$ g++ Test.cpp xiaoming@ubuntu:~/code$ ./a.out 55555 Xiao Dong loves Xiao Ming. xiaoming@ubuntu:~/code$

咦，不对呀，我刚才要打印的明明是“Xiao Ming loves Xiao Dong”，为什么输出却是“Xiao Dong loves Xiao Ming.”呢？难道我整天做着白日梦做的我的手脚都不听脑子使唤了？唉。小明一边叹着气一边返回修改代码，想把字符串给改回来。可是当他打开Test.cpp的时候，无论怎么看，上面写着的都是：

1	printf("Xiao Ming loves Xiao Dong.\n");

为什么！！！为什么我明明打印的是“Xiao Ming loves Xiao Dong”，输出的却是“Xiao Dong loves Xiao Ming.”呢！！！难道…..小明脑子里想着各种狗血的可能性。不，不可能，小明把自己从思绪中拽了回来，叹了口气，肯定是上天看我可怜，用某种不可预知的力量让我的电脑发生了几个比特的错位，导致了现在这个结果，逗我开心吧。于是，小明在代码中加了一个for循环：

1 2 3 4 5 6 7 8 9 10 11 12

#include <cstdio> int main() { printf("55555\n"); int i; /* 循环100次为了确认刚才发生的是意外 */ for(i = 0; i < 100; i++) printf("Xiao Ming loves Xiao Dong.\n"); return 0; }

这样总好了吧。这次命令行应该会输出100个“Xiao Ming loves Xiao Dong.”了吧。小明想着。
编译，运行。眼前的一幕让小明彻底傻眼了….屏幕出现是齐刷刷的100行“Xiao Dong loves Xiao Ming.”。为什么！！！到底是为什么！！！此时的小明又激动又崩溃又开心。突然，他想起了几天前看到的一篇文章：
How to wrap a system call (libc function) in Linux
然后又想起了前几天电脑借过给小东用。难道？！难道？！小明不敢相信自己的猜测，他用颤抖着的手打开家目录下的.bashrc，文件末尾的几行文字让他老脸一红。也许，他的猜测是正确的。

1 2 3 4

... # modified by Xiao Dong on 2018-2-14 export LD_PRELOAD=/usr/lib/xiaodong.so ...

小明用nm命令查看了xiaodong.so里面实现了的API：

1 2 3 4

xiaoming@ubuntu:~/code$ nm /usr/lib/xiaodong.so ... 0000000000000760 T puts ...

这个xiaodong.so实现了一个跟libc的puts函数同名的puts，如果在程序执行时预先加载这个xiaodong.so，这个puts就会覆盖掉libc原先的puts，而printf函数内部实现刚好又是调用puts…所以说，小东肯定在xiaodong.so里面的puts函数上做了一些手脚。咦，说不定这个so的源代码还藏在这台电脑的某个角落里呢，看看：

1 2 3 4

xiaoming@ubuntu:~/code$ sudo updatedb xiaoming@ubuntu:~/code$ locate xiaodong /home/xiaoming/.test/xiaodong.cpp ...

原来，源代码藏在家目录下的一个隐藏的文件夹里，内容如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

#ifndef __USE_GNU #define __USE_GNU #endif #include <cstring> #include <sys/types.h> #include <dlfcn.h> typedef ssize_t (*puts_func_t)(const void*); puts_func_t g_real_puts = (puts_func_t)dlsym(RTLD_NEXT, "puts"); extern "C" { int puts(const char* buf) { if(strcmp(buf, "Xiao Ming loves Xiao Dong.") == 0) return g_real_puts("Xiao Dong loves Xiao Ming."); return g_real_puts(buf); } };

至此，真相就大白了。
死鬼，原来你一直也喜欢着我呀，小明的脸变得更红了。怎么办？怎么办？是要去找他呢，还是先假装什么也不知道？小明的内心挣扎着…..(未完待续)

哈希树笔记

发表于 2017-11-04

结构

哈希树的结构如下图所示

主要思想是：插入的每一个数据通过模多个质数来确定在树中的位置。图为四层哈希树，除第一层外每一层都会有一个质数对即将插入的数取模，质数从最小开始，逐步增大，如图中第二层的质数为2，第三层为3，第四层为5（如果有第五层则为7）。首先假设最下面一层（第四层）才存储数据，其它层（第一道三层）都不存储数据。假如要插入28，则其检索路径就如上图所示。最终它被插入到第四层的绿色节点中。

容量

基于哈希树最下面一层才存储数据的假设，一个4层哈希树的存储容量为
2 * 3 * 5 = 30

容量内不会发生冲突

哈希数据结构最主要的问题是解决键值的冲突。神奇的是，哈希树在容量范围内并不会发生冲突，比如上图的四层哈希树的键值在30以内并不会发生冲突。一个8层的哈希树的容量为：
2 * 3 * 5 * 7 * 11 * 13 * 17 = 510510
且键值在510510内不会发生冲突。
证明如下：

要证明哈希树在容量范围内并不会发生冲突，只需要证明树中存储数据的任意一个节点只对应容量范围内的唯一一个数即可。
设现有一颗n + 1层的哈希树，从第二层到第n+1层的质数分别为m₁,m₂,m₃…m_n。现有一个容量范围内的数据x，x除以m₁的余数为a₁，除以m₂的余数为a₂，以此类推。即：
x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
x ≡ a₃ (mod m₃)
…
x ≡ a_n (mod m_n)
令
t₁ = k₁m₁ + a₁(k₁为非负整数，下面同上)
t₂ = k₂m₂ + a₂
…
t_n = k_nm_n + a_n
下面我们试着构造T = t₁ + t₂ + … + t_n，使得T满足：
T ≡ a₁ (mod m₁)
T ≡ a₂ (mod m₂)
T ≡ a₃ (mod m₃)
…
T ≡ a_n (mod m_n)
我们知道，如果t₁ % m₁ = a₁，则(t₁ + km₁) % m₁ = a₁，所以若要(t₁ + t₂) % m₁ = a₁，则需t₂为m₁的倍数，以此类推，若要(t₁ + t₂ + … + t_n) % m₁ = a₁，则当t₂,t₃…t_n都为m₁的倍数的时候,等式成立。所以若要：
T % m₁ = a₁
T % m₂ = a₂
…
T % m_n = a_n
则：
t₁除以m₁余a₁，t₂,t₃ … t_n都是m₁的倍数
t₂除以m₂余a₂，t₁,t₃ … t_n都是m₂的倍数
…
t_n除以m_n余a_n，t₁,t₂ … t_{n - 1}都是m_n的倍数
整理得：
t₁除以m₁余a₁，t₁是m₂,m₃…m_n的公倍数
t₂除以m₂余a₂，t₂是m₁,m₃…m_n的公倍数
…
t_n除以m_n余a_n，t_n是m₁,m₂…m_{n - 1}的公倍数
置：
t₁为满足 除以m₁余a₁且为(m₂m₃…m_n)的倍数 的数
t₂为满足 除以m₂余a₂且为(m₁m₃…m_n)的倍数 的数
…
t_n为满足 除以m_n余a_n且为(m₁m₂…m_{n - 1})的倍数 的数
即：
t_i = a_iM_iM_i^-1
（其中M = m₁ + m₂ + … + m_i, M_i = M / m_i, M_i^-1为M_i的逆元）
此时T = t₁ + t₂ + … + t_n满足：
T % m₁ = a₁
T % m₂ = a₂
…
T % m_n = a_n
但此时的T不是最小解。若a % b = c，则（a - kb) % b = c，所以
x = T - kM（k尽量大，只要x不为负即可）
所以x = T % M，即:
x = (a₁M₁M₁^-1 + a₂M₂M₂^-1 + … + a_nM_nM_n^-1) % (m₁m₂…m_n)
所以x是一个小于容量M的唯一的整数解，所以哈希树最后一层的每个位置都可以对应一个容量内的唯一一个整数，所以哈希树在容量内不会发生冲突。

变体

以上所述的哈希树只是在最后一层可以存储数据，容量为：
m₁m₂…m_n
事实上，为了节省空间，第二层到最后一层都可以存储数据，下面这张图很好地说明了这一点：

变体的容量为：
m₁ + m₁m₂ + m₁m₂m₃ + … + m₁m₂…m_n

与哈希表比较

哈希树与哈希表的能实现的功能基本一样，但与哈希表不同的是，哈希树算法是稳定算法，查询一个数据的算法复杂度是O(k)，而哈希表查询一个数据正常情况下是O(1)。而且当需要更多的空间存储数据的时候，哈希树只需要增加层数即可，而哈希表需要更多的空间存储数据时则需要rehash并对空间扩容，相对比较麻烦。

自己搭建静态博客的评论系统

发表于 2017-10-09

起因

本来博客上的第三方评论系统“多说”用的好好的，突然有一天一个朋友跟我说多说的评论系统现在已经不能用了，而且众多国内的评论系统也都已经停止运营，他的博客换上了Disqus(链接)。我上去他的博客一看发现博文底下空荡荡的什么也没有，Disqus并没有被加载出来。后来经了解发现原来如果想用Disqus，就必须翻到墙外去才能用。这么一来几乎所有的hexo评论系统在国内都不能用了。于是想，既然我有自己的服务器，可不可以自己搭建一个像多说一样的评论系统呢。

实现

hexo的主题构架

我们先来借鉴一下多说在hexo中的实现，先看看hexo的主题构架（我用的主题是NexT.Pisces)。进入主题的layout目录

发现原来NexT.Pisces主题是用swig写的。我们来看看_layout.swig里面的内容:

如图中所示，_layout.swig里面与comment有关的内容有两处（图中用红方框标注）。我们先看_partials/comments.swig的内容，如下所示：

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

{% if page.comments %} <div class="comments" id="comments"> <% if (theme.duoshuo and theme.duoshuo.shortname) or theme.duoshuo_shortname %} <div class="ds-thread" data-thread-key="{{ page.path }}" data-title="{{ page.title }}" data-url="{{ page.permalink }}"> </div> {% elseif theme.facebook_sdk.enable and theme.facebook_comments_plugin.enable %} <div class="fb-comments" data-href="{{ page.permalink }}" data-numposts="{{ theme.facebook_comments_plugin.num_of_posts }}" data-width="{{ theme.facebook_comments_plugin.width }}" data-colorscheme="{{ theme.facebook_comments_plugin.scheme }}"> </div> {% elseif theme.disqus_shortname %} <div id="disqus_thread"> <noscript> Please enable JavaScript to view the <a href="//disqus.com/?ref_noscript">comments powered by Disqus.</a> </noscript> </div> {% elseif theme.hypercomments_id %} <div id="hypercomments_widget"></div> {% endif %} </div> {% endif %}

在comments.swig中，先判断博客的评论功能是否为开启（page.comments是否为true），如果评论开启，则判断用户指定了哪一个评论系统，比如第一个if判断多说评论系统是否开启，第二个if判断facebook的评论插件是否开启等。这里拿多说举例，如果是多说评论系统，则插入一段html到网页中（应该是预留着用来渲染多说评论的样式的）：

1 2 3

<div class="ds-thread" data-thread-key="{{ page.path }}" data-title="{{ page.title }}" data-url="{{ page.permalink }}"> </div>

接着我们看第二处，_scripts/third-party/comments.swig里面的内容：

1 2 3

{% include './comments/duoshuo.swig' %} {% include './comments/disqus.swig' %} {% include './comments/hypercomments.swig' %}

里面简单地引进了3个swig文件，以多说为例，我们接着跟进./comments/duoshuo.swig:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

{% if (theme.duoshuo and theme.duoshuo.shortname) or theme.duoshuo_shortname %} ...... <script type="text/javascript"> var duoshuoQuery = {short_name:"{{duoshuo_shortname}}"}; (function() { var ds = document.createElement('script'); ds.type = 'text/javascript';ds.async = true; ds.id = 'duoshuo-script'; ds.src = (document.location.protocol == 'https:' ? 'https:' : 'http:') + '//static.duoshuo.com/embed.js'; ds.charset = 'UTF-8'; (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(ds); })(); </script> ...... {% endif %}

以上代码只贴出了与评论相关的内容，至于其它的一些多说文章搜索等功能相关的省略掉了。我们看上面的js代码，此段代码先创建一个script标签，接着将其src指向多说域名下的一个js
文件（此文件已经失效，我猜这个js的功能是获取数据，然后渲染_partials/comments.swig里面的多说相关的div，让其成为多说评论的最终样子）。
至此，多说评论系统在hexo中的前端实现就大致看明白了。

跨域请求与获取数据

由于博客域名跟多说域名不是同一个域名，所以这里涉及到跨域传递信息的问题。在之后的实现中，我们使用jsonp的方式进行跨域传递信息。这里举一个jquery文档里面的官方例子：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

<script> (function() { var flickerAPI = "http://api.flickr.com/services/feeds/photos_public.gne?jsoncallback=?"; $.getJSON( flickerAPI, { tags: "mount rainier", tagmode: "any", format: "json" }) .done(function( data ) { $.each( data.items, function( i, item ) { $( "<img>" ).attr( "src", item.media.m ).appendTo( "#images" ); if ( i === 3 ) { return false; } }); }); })(); </script>

jquery会随机生成一个函数名，来替换掉flickerAPI里面的第二个？，假设这个函数名为jquery123456。只有服务器响应的数据格式为jquery123456(xxx)的时候才能成功调用done函数，其中xxx是json数据。根据约定，参数data的内容将会是是xxx的内容。

前端实现

首先呢，我们修改_partials/comments.swig里面的内容，加入自己的评论框样式（暂且把自己搭建的这个第三方评论系统叫shuoshuo…..),如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

{% if page.comments %} <div class="comments" id="comments"> {% if theme.shuoshuo %} <div id="shuoshuo_comment"> <h3>Comments</h3> <hr> <div id="comment_list" data-key="{{ page.path }}"> </div> <div id="post_box"> <input type="text" id="name_" placeholder="input your name here" /><br> <textarea id="content_" placeholder="input what you want to say here"></textarea><br> <button onclick="submitComment()">submit</button> </div> </div> {% elif (theme.duoshuo and theme.duoshuo.shortname) or theme.duoshuo_shortname %} ......

此时记得在主题的_config.yml中加入一项

1 2	# shuoshuo shuoshuo: true

接着我们在_scripts/third-party/comments下新建一个swig文件叫shuoshuo.swig，内容如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

{% if theme.shuoshuo %} <script type="text/javascript"> var shuoshuoQuery = {short_name:""}; (function() { var ds = document.createElement('script'); ds.type = 'text/javascript'; ds.async = true; ds.id = 'shuoshuo-script'; ds.src = (document.location.protocol == 'https:' ? 'https:' : 'http:') + '//23.106.145.179:8090/test/create.js'; ds.charset = 'UTF-8'; (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(ds); })(); </script> {% endif %}

代码功能很简单，就是动态引进一个js脚本23.106.145.179:8090/test/create.js（获取数据和渲染评论的代码将会在里面，23.106.145.179是我的服务器地址）。接着我们修改_scripts/third-party/comments.swig将shuoshuo.swig include进来：

1 2 3 4

{% include './comments/duoshuo.swig' %} {% include './comments/shuoshuo.swig' %} {% include './comments/disqus.swig' %} {% include './comments/hypercomments.swig' %}

最后呢，我们看看23.106.145.179:8090/test/create.js到底干了什么：

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

//闭包 (function() { var box = $('#comment_list'); var key = box.data('key'); //利用jsonp的方式从服务器获取评论数据，接着渲染在网页上 window.loadComment = function() { $.getJSON("http://23.106.145.179:8090/test/?jsonp=?", { key: key }).done(function(data) { prehtml = ""; for(var i = 0; i < data.length; i++) { prehtml += "<p>name: " + data[i].name + "<br>time: " + data[i].createTime + "<br>content: " + data[i].content + "</p>"; } box.html(prehtml); }); } //向服务器提交评论，由于ajax不允许跨域，所以依然使用jsonp的方法 window.submitComment = function() { var name = $('#name_').val(); var content = $('#content_').val(); if(name == undefined || name == "" || content == undefined || content == "") { alert("name or comment can not be null"); return; } $.getJSON("http://23.106.145.179:8090/test/post_comment.jsp?jsonp=?", { key: key, name: name, content: content }).done(function(data) { console.log(data); //刷新评论列表 loadComment(); $('#name_').val(''); $('#content_').val(''); }); } //网页刚被打开的时候加载好评论 loadComment(); })();

后端实现

后端要做的工作比较简单，就是负责响应客户端的请求和存储数据就好了，另外要防范一下xss和sql注入，我们来看看数据库结构：

1 2 3 4 5 6 7 8

create table comment( id int primary key auto_increment, domain varchar(128) not null, comment_key varchar(200) not null, name varchar(128) not null, content varchar(2048) not null, create_time timestamp default current_timestamp );

domain、comment_key、name、content、create_time分别为域名、文章路径、评论人昵称、评论内容、创建时间。标识一篇文章的评论列表的组合键为(domain:域名，comment_key:该域名下的文章路径或者文章名)。

https之痛

由于github pages中强制要求使用https协议，在使用https网站中使用http外链是不允许的，我并没有https证书，无奈之下只能将博客转到国内的coding的pages服务上(coding允许使用http)。

后记

如下面所示，自己写的这个第三方评论功能并没有样式，看起来比较简朴，一个比较牵强的理由是这样比较显复古风（其实是因为博主懒得写了0.0）。原理挺简单的，有兴趣的朋友可以自己搭建一个。如果自己懒得写了，也可以给我发一封邮件（邮箱地址在博客的“关于我”中可以找到），我可以把你的域名加入我服务器的允许域名中，然后直接用我的评论系统。

快速幂运算算法

发表于 2017-08-26

一般思路的求幂函数会是如下所示：

1 2 3 4 5 6 7

long long power(int a, int n) { int i; long long result = 1; for(i = 0; i < n; i++) result *= a; return result; }

以上函数算法复杂度为O(n)，快速幂算法可以将幂运算的算法复杂度降到O(logn)。原理如下。
比如计算3^13，因为13的二进制表示为1101，所以：

1	3 ^ 13 = 3 ^ [1] * 3 ^ [00] * 3 ^ [100] * 3 ^ [1000]

（注：中括号内为二进制表示）
类似的，我们对于所有幂运算都可以化成以上形式，算法复杂度由原来的O(n)变为O(logn)，矩阵快速幂运算代码实现如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

//重载矩阵类的^运算符 Matrix operator^(int n) { Matrix result, multi; result.init(); //初始化为单位矩阵 multi = *this; while(n) { if(n & 0x1) { result = result * multi; } multi = multi * multi; n >>= 1; } return result; }

(注：Matrix为矩阵)

应用（快速计算斐波那契数列）：
一般计算斐波那契数列我们用递推的方法：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

long long calc1(int n) { if(n == 1 || n == 2) return 1; else if(n <= 0) return -1; int i; long long *arr = new long long[n]; arr[0] = 1; arr[1] = 1; for(i = 2; i < n; i++) { arr[i] = arr[i - 1] + arr[i - 2]; } return arr[i - 1]; }

如果我们要求斐波那契数列的第一亿项，递推求值的方式将会花费很长的时间。
由于f(n) = f(n - 1) + f(n - 2)，所以

推出

至此我们就可以在求斐波那契数列中应用上快速幂运算了：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

long long calc2(int n) { if(n == 1 || n == 2) return 1; else if(n <= 0) return -1; Matrix m; m.arr[0][0] = 1; m.arr[0][1] = 1; m.arr[1][0] = 1; m.arr[1][1] = 0; Matrix a = m ^ (n - 2); return a.arr[0][0] * 1 + a.arr[0][1] * 1; }

一个基于动态规划lcs算法的迷你文本比较器

发表于 2017-03-28

github地址https://github.com/kimlongli/min-diff
此项目暂时不超过一百行代码，主体文件为diff.js。

使用方法如下：

• 引入js文件

  1	<script type="text/javascript" src="diff.js"></script>

• 调用diff函数获取结果

  1	result = diff(txt1, txt2);

其中txt1和txt2为需要比较的文本内容，比较结果将会以以下结果返回：

1 2 3 4 5

function test() { a = 1; + b = a + 2; - c = b; }

每行前面的+代表这是增加的行，-代表这是减少的行。
可以通过demo来了解具体的实例。