本文是刷leetcode的一点心得。

1 算法设计领域的迭代和递归

  在计算机程序设计或者算法设计领域，迭代和递归在本质上是一致的： 每次递归或迭代是为了解决原问题的子问题，然后根据子问题的结果和当前问题的状态 综合求解当前问题。所不同的是：在递归方法中，先求得子问题的解，然后接合当前 状态求得问题结果。而在迭代方法中，使用栈保存当前问题的求解状态，然后把当前问题 分解为子问题，并把当前状态和子问题入栈；接下来对栈中的元素迭代求解，并记录最终 结果的中间状态，直到栈为空，此时返回最终的求解结果。
  对于很多问题，用递归的方法很容易就容易解决，而用迭代的方法则不那么 直观，甚至感觉难以下手。这是因为在递归方法中，保存中间结果和栈的操作都交由函数 调用去实现了，而在迭代方法中，这些都需要在算法中手动处理。不过，只要能认识到递归 和函数其实是一样的，那么就可以很自信的说：能用递归解决的问题就一定能用迭代解决。
  下面以一些leetcode中的题目为例进行分析。

2 例题

  Invert Binary Tree
Recursive Version:

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

TreeNode* invertTreeRecursive(TreeNode* root) {
    if (root == NULL || (root->left == NULL && root->right == NULL)) {
        return root;
    }

    if (root->left) {
        root->left = invertTreeRecursive(root->left);
    }
    if (root->right) {
        root->right = invertTreeRecursive(root->right);
    }
    TreeNode *tmpNode = root->left;
    root->left = root->right;
    root->right = tmpNode;
    return root;
}

Iterative Version:

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

TreeNode* invertTreeIterative(TreeNode* root) {
    if (root == NULL || (root->left == NULL && root->right == NULL)) {
        return root;
    }

    stack<TreeNode*> theStack;
    theStack.push(root);
    while (!theStack.empty()) {
        TreeNode *topNode = theStack.top();
        if (topNode->left == NULL && topNode->right == NULL) {
            theStack.pop();
        } else {
            TreeNode *tmpNode = topNode->left;
            topNode->left = topNode->right;
            topNode->right = tmpNode;

            theStack.pop();
            if (topNode->left) {
                theStack.push(topNode->left);
            }
            if (topNode->right) {
                theStack.push(topNode->right);
            }
        }
    }  // while  

    return root;
}

3 结论

  能用递归解决的问题，就一定能用迭代解决。

  本文是针对x86-64指令和ABI的综述，其内容翻译自参考文献[1]。

1 引言

x86-64指令一般有两个操作数：源操作数和目的操作数，目的操作数也即指令执行结果。
linux下的x86-64指令格式采用AT&T格式，也即源操作数在左边，目的操作数在右边。
绝大多数x86-64指令采用后缀字母标示操作数的大小，例如q表示64为，b表示8位，w表示16位，l表示32位。

2 寄存器

x86-64有16个64位通用寄存器，在AT&T格式中使用%做前缀，其定义和在ABI中的角色如下表所示：

寄存器%rbp，%rbx和%r12~%r15是callee-save的，也即由被调用函数保存。

3 函数调用约定

Mac OS Ｘ和Ｌinux操作系统的函数调用都遵从System V ABI，
有三个x86-64指令用来实现函数调用和返回：
   call:返回地址(当前下一条指令地址)压栈，控制权转移到操作数所在的地址；
  leave:设置栈指针%rsp为为帧%rbp，恢复帧指针%rbp为栈上保存的帧指针，
        该指针从函数栈上弹出；
    ret:返回值从函数栈弹出，并跳转到该地址；

3.1 函数参数

函数调用的前6个参数通过寄存器传递，传递顺序为%rdi,%rsi,%rdx,%rcx,%r8,%r9。超出部分的参数通过函数 栈帧传递。%rax用作第一个函数返回值，%rdx用作第二个函数返回值。

3.2 函数栈帧

函数栈帧从高地址往低地址方向增长，System V ABI使用两个寄存器访问函数栈帧：帧指针%rbp和栈指针%rsp。 帧指针%rbp指向当前函数栈帧基址(栈底)，栈指针%rsp指向当前函数栈帧栈顶。
一般说来，帧指针%rbp用来存取函数栈帧上的数据，例如传递进来的函数参数，或者函数的本地局部变量。 System V ABI要求要求函数栈帧16字节对齐，这要求函数栈帧的大小应该是16的倍数。
函数栈帧结构图如下所示：

3.3 函数调用协议

函数调用协议分为caller端和callee端，每端各有两个重要步骤：
1）caller端首先保存caller-save寄存器到到函数栈上，并根据ABI加载函数参数到规定的寄存器和函数栈位置，然后执行call指令；
2）call指令使得程序控制转向callee函数，该函数首先需要执行链接和初始化任务，这些任务由以下指令序列完成：
    pushq %rbp;
    movq %rsp, %rbp;
    subq $N, %rbp;
pushq指令用来保存帧指针，movq指令初始化帧指针为当前栈指针，subq指令为callee函数分配栈空间；对于callee-save的那些寄存器，如果在函数体中用到这些寄存器，那么接下来需要通过一系列pushq指令保存这些callee-save寄存器到函数栈帧上。程序接下来执行函数体部分代码。
3）函数体部分执行完以后，将执行callee返回部分：首先将函数返回值置入%rax中；然后释放函数栈帧空间，并恢复%rsp，%rbp寄存器；最后调用leave/ret指令返回到caller部分。
4）在caller端，如果它为callee的函数参数分配了存储空间，则在此时需要释放这些空间。
至此，一个完整的函数调用过程完成。

4 指令

关于指令部分，内容实在太多，具体请参考x86-64的指令手册。此处仅仅略述操作数。 x86-64指令的操作数有三种：寄存器(以%为前缀)，立即数(以$为前缀)和内存地址。内存地址的寻址方式概述如下：

参考文献

http://www.classes.cs.uchicago.edu/archive/2009/spring/22620-1/docs/handout-03.pdf

  如果以Ubuntu(或者其变种Mint)作为日常工作环境的话，那么类似于字处理，挂QQ等将成为不可避免的需求。关于在Ubuntu上挂QQ，之前的解决方案是使用VirtualBox安装windows,然后在windows里安装QQ；最近也使用Qemu安装过Win7。很明显为挂个QQ而安装虚拟机太笨重，非常耗费系统资源。最近经过调研发现一种新解决办法，即WineQQ。亲测好用，记录之。

1. 安装依赖库

sudo apt-get install libgtk2.0-0  
sudo apt-get install ia32-libs  
sudo apt-get install lib32ncurses5  
sudo apt-get install liblcms2-2  

2. 下载并解压缩wineqq

  下载地址：http://www.ubuntukylin.com/applications/showimg.php?lang=cn&id=23
  然后用unzip命令解压缩，得到三个deb文件，安装之。

3. 安装wineqq

sudo dpkg -i wine-qqintl_0.1.3-2_i386.deb  
sudo dpkg -i ttf-wqy-microhei_0.2.0-beta-2_all.deb  
sudo dpkg -i fonts-wqy-microhei_0.2.0-beta-2_all.deb  

  然后在系统菜单的互联网子菜单里就可以发现刚安装的WineQQ，开启用之！

参考文献

http://bubuko.com/infodetail-343048.html

  Linux系统调用是连接用户态和内核态的纽带，弄清楚这个过程对于理解Linux操作系统具有十分重要的意义。下面以read系统调用为例分析这一过程。本文中Linux内核代码版本为3.16，glibc版本为2.20。

1. sys_read系统调用的定义(在内核文件fs/read_write.c中):

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

SYSCALL_DEFINE3(read, unsigned int, fd, char __user *, buf, size_t, count)
{
    struct fd f = fdget_pos(fd);
    ssize_t ret = -EBADF;

    if (f.file) {
        loff_t pos = file_pos_read(f.file);
        ret = vfs_read(f.file, buf, count, &pos);
        if (ret >= 0)
            file_pos_write(f.file, pos);
        fdput_pos(f);
    }
    return ret;
}

  sys_read的实现代码比较简单：首先根据文件描述符fd通过fdget_pos(fd)从当前进程结构中得到fd对应的struct fd结构（这个fd结构是struct file结构的进一步封装）；然后调用file_pos_read(f.file)得到当前文件读位置；最后调用vsf_read()进行文件读取操作；如果读取成功，则调用file_pos_write函数更新文件的读当前位置；最后调用fdput_pos函数更新文件的引用计数；最终sys_read返回读取的字节数。
  sys_read系统调用实现的核心是vfs_read函数，这涉及到Linux的VFS虚拟文件系统机制，这是另外一个主题，在此就不深入展开了。

2. SYSCALL_DEFINEx宏的定义

  SYSCALL_DEFINEx宏是理解Linux内核系统调用定义的关键，该宏在include/linux/syscalls.h中定义：

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

#define SYSCALL_DEFINE1(name, ...) SYSCALL_DEFINEx(1, _##name, __VA_ARGS__)  
#define SYSCALL_DEFINE2(name, ...) SYSCALL_DEFINEx(2, _##name, __VA_ARGS__)  
#define SYSCALL_DEFINE3(name, ...) SYSCALL_DEFINEx(3, _##name, __VA_ARGS__)  
#define SYSCALL_DEFINE4(name, ...) SYSCALL_DEFINEx(4, _##name, __VA_ARGS__)  
#define SYSCALL_DEFINE5(name, ...) SYSCALL_DEFINEx(5, _##name, __VA_ARGS__)  
#define SYSCALL_DEFINE6(name, ...) SYSCALL_DEFINEx(6, _##name, __VA_ARGS__)  

#define SYSCALL_DEFINEx(x, sname, ...)          \  
SYSCALL_METADATA(sname, x, __VA_ARGS__)         \
__SYSCALL_DEFINEx(x, sname, __VA_ARGS__)

#define __SYSCALL_DEFINEx(x, name, ...)                     \  
asmlinkage long sys##name(__MAP(x,__SC_DECL,__VA_ARGS__))   \
    __attribute__((alias(__stringify(SyS##name))));         \

  其中SYSCALL_METADATA是和CONFIG_FTRACE_SYSCALLS相关的一个宏定义；关键字asmlinkage告诉编译器函数的参数从栈上获得，所有系统调用都采取这种参数传递方式；##用在宏中表示字符串链接。__stringify表示字符串化，也即:

1
2

#define __stringify_1(x...) #x  
#define __stringify(x...)   __stringify_1(x)  

1. 新建插件文件plugins/category_list_tag.rb, 内容如下:

module Jekyll  
  class CategoryListTag < Liquid::Tag  
    def render(context)  
      html = ""  
      categories = context.registers[:site].categories.keys  
      categories.sort.each do |category|  
        posts_in_category = context.registers[:site].categories[category].size  
        category_dir = context.registers[:site].config['category_dir']  
        category_url = File.join(category_dir, category.gsub(/_|\P{Word}/, '-').gsub(/-{2,}/, '-').downcase)  
        html << "<li class='category'><a href='/#{category_url}/'>#{category} (#{posts_in_category})</a></li>\n"  
      end  
      html  
    end  
  end  
end  

Liquid::Template.register_tag('category_list', Jekyll::CategoryListTag)  

2. 新建source/_includes/asides/category_list.html文件，内容如下：

<section>  
  <h1>Categories</h1>  
  <ul id="categories">  
    { % category_list % }  
  </ul>  
</section>  

3. 修改_config.yml文件，在default_asides项中添加asides/category_list.html, 值之间以逗号隔开:

default_asides:[asides/category_list.html, asides/recent_posts.html, ...]  

4. rake generate; rake preview; rake deploy;

参考资料：

http://www.cnblogs.com/oec2003/archive/2013/05/31/3109577.html

经过充分调研，选定Octopress作为技术博客系统框架。 下面是在Linux mint 13操作系统上安装Octopress和在Github上部署的过程。

安装

1.安装git, ruby和nodejs

apt-get install git
apt-get install libruby1.9.1
apt-get install ruby1.9.1
apt-get install ruby1.9.1-dev
apt-get install nodejs

2.下载Octopress

git clone git://github.com/imathis/octopress.git octopress
cd octopress

3.安装依赖

gem install bundler
rbenv rehash
bundle install

4.安装默认Octopress主题

rake install

在Github上部署Octopress

1.在Github个人帐号上创建仓库

我的Github个人帐号为weizhenwei，创建仓库weizhenwei.github.io.git

2.部署Octopress到Github

1.rake setup_github_pages    #关联仓库weizhenwei.github.io.git的完整路径；
2.rake generate              #内容生成；
3.rake preview               #内容预览，在本地浏览器localhost:4000预览；
4.rake deploy                #内容部署，上传到github仓库上的master分支；

3.Octopress源代码保存

git add .
git commit -m "my comment"
git push origin source       # 源代码保存到source分支；

4.Octopress配置

主要是修改_config.yml文件。

博客内容撰写：

rake new_post["title“]       # 创建博客文件，该文件在sorce/_post目录下；
然后编辑这个博客文件；
rake generate;
rake preview;
rake deploy;
git add .
git commit -m "my comment"
git push origin source

添加新页面：

1. rake new_page["aboutme"], 该命令自动生成source/aboutme目录以及其下的index.markdown文件;  
2. 编辑source/aboutme/index.markdown文件, 添加内容;  
3. 修改souce/_includes/custom/navigation.html文件，将1.中新建文件路径添加到该文件中。
4. rake generate; rake preview; rake deploy;  
5. git add .; git commit -m "comment"; git push origin source;  

注意事项：

1.在新的地方git clone代码之后，需要checkout到source分支，
  然后再运行rake setup_github_pages命令连接上仓库url。
2. master分支是内容分支，全部是由rake deploy命令提交；
   source分支是源代码分支，用git命令进行提交；
   两个分支不可搞混。

参考文献：

http://octopress.org/docs/setup/
http://octopress.org/docs/deploying/github/
http://octopress.org/docs/blogging/
http://stackoverflow.com/questions/21356212/failed-to-deploy-to-github-pages-using-octopress