2008年8月20日
#
Macro Recursion
author: Kevin Lynx
Preface
本文可能是<代码自动生成-宏带来的奇技淫巧>的续写。我尽力阐述如何让宏递归（或者说重复）地有规律地产生一
些符号，而让我们少写很多重复代码，也许这些代码只有那么一点点的不同。将这项小技巧用于底层库的编写，会让代码
看起来干净不少，同时文件尺寸也会骤然下降。
Problem
如果你曾经写过functor，那么你肯定对某些代码进行粘贴复制然后修改。更让人郁闷的是，这些代码基本是一样的。
例如，一个典型的functor可能为：
template <typename Prototype>
class functor;
template <typename R, typename P1>
class functor<R(P1)>;
template <typename R, typename P1, typename P2>
class functor<R(P1,P2)>;
//好，接下去你可能厌烦了，可能会复制一个带有两个参数的functor，然后修改为处理3个参数的。
这只是一个很简单的问题。宏不是c++里的东西，本文自然也不是讨论各种花哨的模板技术的。如果我之前那篇关于
宏的文章只是让你去分析问题以及更深层次地认识宏，那么现在我将分享我的这部分思想给你。
关于上面的问题，我们期待得到这样的解决方案：
template <typename R, DEF_PARAM( 2 )>
class functor<R( DEF_ARG( 2 ) )>;
那么，它将自动生成：
template <typename R, typename P1, typename P2>
class functor<R(P1,P2)>;
也就是说，DEF_PARAM(n)这个宏将根据n值自动生成一串符号，例如DEF_PARAM(2)就生成typename P1, typename P2。
同样，DEF_ARG(n)也会根据参数生成类似于P1,P2,...,Pn的符号串。
思考
仔细思考下，我们可以看出DEF_PARAM和DEF_ARG这样的宏具有一种递归的特性（其实说成重复可能更合适）：每次展
开的内容基本一样，不断调用自身直到遇到终止条件。
那么，我们的目标锁定于，用宏来实现递归。
Pre-Implement
在开始之前，我需要告诉你一些基本的东西：
在阅读一个宏时，你最好按照预处理的处理方式去逐个展开。当我说到展开时，我的意思是把宏替换为宏体。预处理器
展开宏的过程大致为：如果宏参数也是个宏，那么先将宏参数全部展开，再展开该宏；这个时候会扫描展开后的宏，如果
遇到其他宏，则继续展开。例如有一下宏：
#define PI 3.14
#define MUL_PI( n ) n * PI
#define TWO 2
当我们写下MUL_PI( TWO )时，预处理发现MUL_PI的参数TWO 是个宏，那么先将TWO展开得到2，然后将2放进宏体展开
得到 2 * PI；预处理器对 2 * PI 进行扫描，发现还有宏PI，于是对PI做展开，得到 2 * 3.14。这个过程是递归的。
但是也有例外，如果MUL_PI对宏参数进行了#或者##，那么该宏参数不会被展开。（参见以前那篇文章吧）
任何时候，你可以通过以下宏去查看某个宏展开后的样子，可以方便你调试你的宏：
#define TO_STRING( x ) TO_STRING1( x )
#define TO_STRING1( x ) #x
（为什么要写个TO_STRING1，因为这是为了让x充分展开，避免上面提到的那个例外）
其他规则我会在文中需要的地方提出来。
实现
就像大部分介绍递归函数时候给的例子，这里我也将阶乘作为例子。考虑如下典型的阶乘函数：
int fac( int n )
{
if( n == 1 ) return 1;
return n * fac( n - 1 );
}
其核心部分在于 n * fac( n - 1 )，我们假设我们的宏也可以写成这样的的形式：
#define FAC( n ) n * FAC( n - 1 )
但是这样的宏是有问题的：
当宏被展开时，如果遇到了自身，那么将被处理为一般符号，例如展开FAC( 3 )时，会遇到 FAC( 2 )，那么就把FAC
( 2 )中的FAC当成了一搬符号。
这样的限制注定了我们无法让宏真正地调用自身来实现递归。于是，我们不得不写下以下丑陋的符号，从而去模拟递
归的每一次符号调用：
#define FAC_1( n ) 1
#define FAC_2( n ) n * FAC_##(n-1)( n - 1 )
#define FAC_3( n ) n * FAC_##(n-1)( n - 1 )
这系列宏有点别扭（如果你足够细心），因为我们明显知道FAC_2返回的将是2，而FAC_3返回的当时6。我们这里只是
模拟，同样，这使得我们可以把FAC_1作为递归的终止条件。
我们的预想是，当调用FAC_3时，它把n-1的值2合并到FAC_中，从而调用FAC_2，以此类推。
但是这依然有问题，编译器会提示‘找不到符号FAC_’。导致这个问题的原因在于：宏展开只是单纯的字符替换，是我们
想太多了，预处理器并不会去计算( n - 1 )的值是多少，也就是我们无法得到FAC_2这个宏。
所以，FAC_3( 3 ) 会被初次替换为 3 * FAC_(3-1)( 3 - 1 )。这个时候编译器就把FAC_当成了一个普通符号。我们可以
自己定义个FAC_来证明这一点：
#define FAC_( n ) T
那么，FAC_3( 3 )就被替换为 3 * T(3-1)( 3 - 1 )。
解决这个问题的办法关键在于，让预处理器自动计算出( n - 1 )。记住，我们解决问题的唯一办法是：字符替换。
所以，我们可以写下如下代码：
#define DEC_1 0
#define DEC_2 1
#define DEC_3 2
#define DEC( n ) DEC_##n
通过，DEC( n )这个宏，我们可以获取到一个( n -1 )的数。例如，DEC( 3 )被替换为 DEC_3，继续替换为 2。
于是，我们新的FAC系列宏变为：
#define FAC_1( n ) 1
#define FAC_2( n ) n * FAC_##DEC( n )( n - 1 )
#define FAC_3( n ) n * FAC_##DEC( n )( n - 1 )
不好意思，这样依然是不正确的！预处理器直接把FAC_和DEC( n )连接成符号了，而不是单个地先处理他们，最后再
合并他们。
OK，先解决这个问题：先处理FAC_和DEC( n )，再合并他们，而不是先合并他们。要解决这个问题，可以通过第三个宏
来实现：
#define CHR( x, y ) x##y
作为连接两个符号为一个符号的宏，这个宏显然是不正确的，因为宏展开还有个规则：如果宏体对宏参数使用了#或##，
那么宏参数不会被展开，也就是说：如果CHR( FAC_, DEC( 3 ) 那么得到的只会是 FAC_DEC( 3 )。通常情况下我们是
再写个宏：
#define CHR( x, y ) CHR1( x, y )
#define CHR1( x, y ) x##y
从而可以保证在正式连接x和y前，x和y都被完全展开。
这个时候，我们的FAC系列宏变为：
#define FAC_1( n ) 1
#define FAC_2( n ) n * CHR( FAC_, DEC( n ) )( n - 1 )
#define FAC_3( n ) n * CHR( FAC_, DEC( n ) )( n - 1 )
结果呢？结果还是有问题。= =
我们假设CHR( FAC_, DEC( n ) )已经真的按我们预想展开为 FAC_2了，那么FAC_3( 3 )会被展开为什么呢？
被展开为 3 * FAC_2( 3 - 1 )。这是错误的，传给 FAC_2 的参数是 3 - 1就意味着错误。我们又臆想预处理器会
帮我们计算 3 - 1的结果了。我们必须保证传给 FAC_2的参数是个数字2。解决这个问题的办法就是通过DEC(n)宏。
于是，FAC系列宏变为：
#define FAC_1( n ) 1
#define FAC_2( n ) n * CHR( FAC_, DEC( n ) )( DEC( n ) )
#define FAC_3( n ) n * CHR( FAC_, DEC( n ) )( DEC( n ) )
这个时候，FAC_3( 3 )将会被替换为：3*2*1。这就是我们要的结果。
In practice
以上只是向你展示一个过程，用宏去计算阶乘，就像用模板去计算阶乘（模板元编程）一样，只是一个用于展示的东西，
没有什么实际价值。接下来我们开始有实际的工作，完成之前的预想：
template <typename R, typename P1, typename P2, typename P3>
class functor<R (P1, P2, P3)>
直接:
template <typename R, PARAM( 3 )>
class functor<R (ARG( 3 ))>
先考虑PARAM宏，该宏的任务就是生成类似于：typename P1, typename P2, typename P3这样的符号。我们假象它每一次
递归都生成 typename Pn, 的字符串，那么当他递归完时，可能就生成typename P1, typename P2, typename P3, 结果
多了个逗号，也许最后一次结果不该有逗号。
ARG宏和PARAM宏本质上相同，只是重复的符号不是typename Pn，而是Pn。
最直接想到的是：
#define PARAM_1( n ) typename P##n
#define PARAM_2( n ) CHR( PARAM_, DEC( n ) )( DEC( n ) )##,typename P##n
#define PARAM_3( n ) CHR( PARAM_, DEC( n ) )( DEC( n ) )##,typename P##n
结果我们得到了个错误的展开结果：
typename PDEC( 2 ),typename PDEC( 3 ),typename P3
这个问题出在：PARAM_3( 3 )当替换为 PARAM_2( DEC( n ) )时，因为PARAM_2(n)宏对于宏参数n使用了##，也就是那个
typename P##n，所以这里不会把 DEC( n )展开，而是直接接到P后面。所以就成了typename PDEC( 3 )。
为了消除这个问题，我们改进PARAM为：
#define TYPE( n ) ,typename P##n
#define PARAM_1( n ) CHR( typename P, n )
#define PARAM_2( n ) CHR( CHR( PARAM_, DEC( n ) )( DEC( n ) ), TYPE( n ) )
#define PARAM_3( n ) CHR( CHR( PARAM_, DEC( n ) )( DEC( n ) ), TYPE( n ) )
之所以加入TYPE(n)，是因为 ,typename P##n 这个宏本身存在逗号，将其直接用于宏体会出现问题。
于是，我们得到了正确的结果。
其实，PARAM系列宏宏体基本是一样的，除了终止条件那个宏，为什么我们要写这么多呢？理由在于宏体不能自己调用
自己，所以才有了PARAM_3, PARAM_2。
我们可以将上面的一系列宏抽象化，使其具有可复用性：
#define PARAM( n ) ,typename P##n
#define PARAM_END typename P
#define ARG( n ) ,P##n
#define ARG_END P
#define PARAM_1( n ) CHR( typename P, n )
#define PARAM_2( n ) CHR( CHR( PARAM_, DEC( n ) )( DEC( n ) ), TYPE( n ) )
#define PARAM_3( n ) CHR( CHR( PARAM_, DEC( n ) )( DEC( n ) ), TYPE( n ) )
#define REPEAT_1( n, f, e ) CHR( e, n )
#define REPEAT_2( n, f, e ) CHR( CHR( REPEAT_, DEC( n ) )( DEC( n ), f, e ), f( n ) )
#define REPEAT_3( n, f, e ) CHR( CHR( REPEAT_, DEC( n ) )( DEC( n ), f, e ), f( n ) )
#define DEF_PARAM( n ) REPEAT_##n( n, PARAM, PARAM_END )
#define DEF_ARG( n ) REPEAT_##n( n, ARG, ARG_END )
我们创建了可重用的REPEAT系列宏，用于创建诸如typename P1, typename P2, typename P3或者P1,P2,P3之类的符号，
通过更上层的DEF_PARAM(n)和DEF_ARG(n)，就可以直接创建出我们上面所需要的符号串，例如：
DEF_PARAM( 3 ) 就得到 typename P1, typename P2, typename P3
DEF_ARG( 3 ) 就得到 P1, P2, P3
More in practice
下载中提供了我使用这个宏递归技术写的lua_binder(如果你看过<实现自己的LUA绑定器-一个模板编程挑战 >)，你
可以与上一个版本做一下比较，代码少了很多。
同样，我希望你也能获取这种宏递归的思想。
相关下载
使用宏递归的lua_binder
2008年8月13日
#
摘要: 实现LUA绑定器 author : Kevin Lynx Preface 当LUA脚本调用我们注册的C函数时，我们需要逐个地从LUA栈里取出调用参数，当函数返回时，又需要一个一个地往LUA栈压入返回值，并且我们注册的函数只能是int()(lua_State*)类型。这很不方便，对于上层程序员来说更不方便。 因此我们要做的...
阅读全文
2008年8月12日
#
2008年8月5日
#
Implement CGI in your httpd
author : Kevin Lynx
Purpose
为我们的http server加入CGI的功能，并不是要让其成为真正响应CGI query功能的web server。正如klhttpd的开发初衷一样，
更多的时候我们需要的是一个嵌入式(embeded)的web server。
而加入CGI功能（也许它算不上真正的CGI），则是为了让我们与client拥有更多的交互能力。我们也许需要为我们的应用程序
加入一个具有网页外观的界面，也许这才是我的目的。
Brief
CGI，common gateway interface，在我看来它就是一个公共约定。客户端浏览器提交表单(form)操作结果给服务器，服务器
解析这些操作，完成这些操作，然后创建返回信息（例如一个静态网页），返回给浏览器。
因为浏览器遵循了CGI发送请求的标准，那么我们所要做的就是解析收到的请求，处理我们自己的逻辑，返回信息给客户端即可。
Detail...
如果你要获取CGI的更多信息，你可以在网上查阅相关信息。如果你要获取web server对CGI标准的处理方式，我无法提供给你
这些信息。不过我愿意提供我的臆测：
处理CGI请求通常都是由脚本去完成（当然也可以用任何可执行程序完成）。就我所获取的资料来看，只要一门语言具备基本的
输入输出功能，它就可以被用作CGI脚本。浏览器以key-value的形式提交query string，一个典型的以GET方式提交query string的
URL类似于：http://host/cgi-bin/some-script.cgi?name=kevin+lynx&age=22。不必拘泥于我上句话中出现的一些让你产生问号的
名词。我可以告诉你，这里举出的URL（也许更准确的说法是URI）中问号后面的字符串即为一个query string。
我希望你看过我的上一篇草文<实现自己的http server>，你应该知道一个典型的GET请求时怎样的格式，应该知道什么是initial
line，应该知道HTTP请求有很多method，例如GET、POST、HEAD等。
一个CGI请求通常使用GET或POST作为其request method。对于一个GET类型的CGI请求，一个典型的request类似于：
GET /cgi-bin/some-script.cgi?name=kevin+lynx&age=22 HTTP/1.1
other headers...
...
我上面举例的那个URL则可能出现在你的浏览器的地址栏中，它对我们不重要。
而对于POST类型的CGI请求呢？query string只是被放到了optional body里，如：
POST /cgi-bin/some-script.cgi HTTP/1.1
other heads...
...
name=kevin+lynx&age=22
不管我说到什么，我希望你不要陷入概念的泥潭，我希望你能明确我在brief里提到的what can we do and how to do。
How about the web browser ?
我总是想引领你走在实践的路上(on the practice way)。作为一个程序员，你有理由自负，但是你没任何理由小觑任何一个
编程问题。打开你的编译器，现在就敲下main。
so，我们需要知道如何利用我们的浏览器，让我们更为顺手地实践我们的想法。
你也许会写：<html><head><title>HTML test</title></head><body>it's a html</body></html>这样的HTML标记语言。但是
这没有利用上CGI。check out the url in the reference section and learn how to write FORMs.
这个时候你应该明白：
<html>
<head>
<title>CGI test</title>
</head>
<body>
<FORM ACTION="./cgi-bin/test.cgi">
<INPUT TYPE="text" NAME="name" SIZE=20 VALUE="Your name">
</FORM>
</body>
</html>
加入<FORM>来添加表单，加入<INPUT TYPE="text"加一个edit box控件。那么当你在里面输入名字按下回车键时，浏览器将整理
出一个CGI query string发给服务器。
我希望你能在浏览器里看到以问号打头的key-value形式的字符串。
So here we go...
在你自己已有的http server的代码基础上，让浏览器来请求一个包含FORM的网页，例如以上我举例的html。当浏览器将请求发
给服务器的时候，看看服务器这边收到的request。即使你猜到了什么，我也建议你看看，这样你将看到一个真正的CGI query是怎么
样的。
so you know，CGI请求本质上也就是一连串的key-value字符串。真正的http server会将这些字符串传给CGI脚本。脚本只需要
输出处理结果信息到标准输出，服务器就会收集这些输出然后发给客户端。
你也许在揣摩，我们的httpd如何地exec一个外部程序或脚本，如何等待脚本执行完（需不需要异步？），然后如何收集标准输
出上的信息，然后是否需要同步地将这些信息送往客户端。
这很没必要。如果我们的http server真的只是被embeded到其他程序的。我们只需要将query的逻辑处理交给上层模块即可。
What's the next..
现在你知道什么是CGI query string，你也许稍微思考下就知道接下来你该如何去做(if you smart enough)。记住我们的目标，
只是解析CGI query string，然后处理相关逻辑，返回处理结果信息给客户端。
所以接下来，呃，接下来，everything is up to you：分析那些恼人的字符串，将其从&的间隔中整理出来，得到一个key-value
的表，将这个表给你的上层模块，上层模块根据query scritp决定执行什么逻辑，根据这个表获取需要的参数，处理，将结果格式
化为HTML之类的东西，then response。
就这么简单。
Example...
同样，我提供了源码，从而证明我不是纸上谈兵夸夸其谈。我希望我公开源码的习惯能受到你的赞同。
下载带CGI的http server.
Reference:
http://hoohoo.ncsa.uiuc.edu/cgi/ (获取服务器需要做的)
http://www.ietf.org/rfc/rfc3875 (rfc cgi)
http://www.cmis.brighton.ac.uk/~mas/mas/courses/html/html2.html (学会写带FORM的HTML)
2008年7月30日
#
Write your own http server
author : Kevin Lynx
Why write your own?
看这个问题的人证明你知道什么是http server，世界上有很多各种规模的http server，为什么要自己实现一个？其实没什么
理由。我自己问自己，感觉就是在自己娱乐自己，或者说只是练习下网络编程，或者是因为某日我看到某个库宣称自己附带一个小
型的http server时，我不知道是什么东西，于是就想自己去实现一个。
What's httpd ?
httpd就是http daemon，这个是类unix系统上的名称，也就是http server。httpd遵循HTTP协议，响应HTTP客户端的request，
然后返回response。
那么，什么是HTTP协议？最简单的例子，就是你的浏览器与网页服务器之间使用的应用层协议。虽然官方文档说HTTP协议可以
建立在任何可靠传输的协议之上，但是就我们所见到的，HTTP还是建立在TCP之上的。
httpd最简单的response是返回静态的HTML页面。在这里我们的目标也只是一个响应静态网页的httpd而已(也许你愿意加入CGI
特性)。
More details about HTTP protocol
在这里有必要讲解HTTP协议的更多细节，因为我们的httpd就是要去解析这个协议。
关于HTTP协议的详细文档，可以参看rfc2616。但事实上对于实现一个简单的响应静态网页的httpd来说，完全没必要读这么一
分冗长的文档。在这里我推荐<HTTP Made Really Easy>，以下内容基本取自于本文档。
- HTTP协议结构
HTTP协议无论是请求报文(request message)还是回应报文(response message)都分为四部分：
* 报文头 (initial line )
* 0个或多个header line
* 空行(作为header lines的结束)
* 可选body
HTTP协议是基于行的协议，每一行以\r\n作为分隔符。报文头通常表明报文的类型(例如请求类型)，报文头只占一行；header line
附带一些特殊信息，每一个header line占一行，其格式为name:value，即以分号作为分隔；空行也就是一个\r\n；可选body通常
包含数据，例如服务器返回的某个静态HTML文件的内容。举个例子，以下是一个很常见的请求报文，你可以截获浏览器发送的数据
包而获得：
1 GET /index.html HTTP/1.1
2 Accept-Language: zh-cn
3 Accept-Encoding: gzip, deflate
4 User-Agent: Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; .NET CLR 2.0.50727; MAXTHON 2.0)
5 Host: localhost
6 Connection: Keep-Alive
7
我为每一行都添加了行号，第1行就是initial line，2-6行是header lines，7行是一个header line的结束符，没有显示出来。
以下是一个回应报文：
1 HTTP/1.1 200 OK
2 Server: klhttpd/0.1.0
3 Content-Type: text/html
4 Content-Length: 67
5
6 <head><head><title>index.html</title></head><body>index.html</body>
第6行就是可选的body，这里是index.html这个文件的内容。
- HTTP request method
因为我们做的事服务器端，所以我们重点对请求报文做说明。首先看initial line，该行包含几个字段，每个字段用空格分开，例
如以上的GET /index.html HTTP/1.1就可以分为三部分：GET、/index.html、HTTP/1.1。其中第一个字段GET就是所谓的request
method。它表明请求类型，HTTP有很多method，例如：GET、POST、HEAD等。
就我们的目标而言，我们只需要实现对GET和HEAD做响应即可。
GET是最普遍的method，表示请求一个资源。什么是资源？诸如HTML网页、图片、声音文件等都是资源。顺便提一句，HTTP协议
中为每一个资源设置一个唯一的标识符，就是所谓的URI(更宽泛的URL)。
HEAD与GET一样，不过它不请求资源内容，而是请求资源信息，例如文件长度等信息。
- More detail
继续说说initial line后面的内容：
对应于GET和HEAD两个method，紧接着的字段就是资源名，其实从这里可以看出，也就是文件名(相对于你服务器的资源目录)，例
如这里的/index.html；最后一个字段表明HTTP协议版本号。目前我们只需要支持HTTP1.1和1.0，没有多大的技术差别。
然后是header line。我们并不需要关注每一个header line。我只罗列有用的header line :
- Host : 对于HTTP1.1而言，请求报文中必须包含此header，如果没有包含，服务器需要返回bad request错误信息。
- Date : 用于回应报文，用于客户端缓存数据用。
- Content-Type : 用于回应报文，表示回应资源的文件类型，以MIME形式给出。什么是MIME？它们都有自己的格式，例如：
text/html, image/jpg, image/gif等。
- Content-Length : 用于回应报文，表示回应资源的文件长度。
body域很简单，你只需要将一个文件全部读入内存，然后附加到回应报文段后发送即可，即使是二进制数据。
- 回应报文
之前提到的一个回应报文例子很典型，我们以其为例讲解。首先是initial line，第一个字段表明HTTP协议版本，可以直接以请求
报文为准(即请求报文版本是多少这里就是多少)；第二个字段是一个status code，也就是回应状态，相当于请求结果，请求结果
被HTTP官方事先定义，例如200表示成功、404表示资源不存在等；最后一个字段为status code的可读字符串，你随便给吧。
回应报文中最好跟上Content-Type、Content-Length等header。
具体实现
正式写代码之前我希望你能明白HTTP协议的这种请求/回应模式，即客户端发出一个请求，然后服务器端回应该请求。然后继续
这个过程(HTTP1.1是长连接模式，而HTTP1.0是短连接，当服务器端返回第一个请求时，连接就断开了)。
这里，我们无论客户端，例如浏览器，发出什么样的请求，请求什么资源，我们都回应相同的数据：
/**//* 阻塞地接受一个客户端连接 */
SOCKET con = accept( s, 0, 0 );
/**//* recv request */
char request[1024] = { 0 };
ret = recv( con, request, sizeof( request ), 0 );
printf( request );
/**//* whatever we recv, we send 200 response */
{
char content[] = "<head><head><title>index.html</title></head><body>index.html</body>";
char response[512];
sprintf( response, "HTTP/1.1 200 OK\r\nContent-Type: text/html\r\nContent-Length: %d\r\n\r\n%s", strlen( content ), content );
ret = send( con, response, strlen( response ), 0 );
}
closesocket( con );
程序以最简单的阻塞模式运行，我们可以将重点放在协议的分析上。运行程序，在浏览器里输入http://localhost:8080/index.html
，然后就可以看到浏览器正常显示content中描述的HTML文件。假设程序在8080端口监听。
现在你基本上明白了整个工作过程，我们可以把代码写得更全面一点，例如根据GET的URI来载入对应的文件然后回应给客户端。
其实这个很简单，只需要从initial line里解析出(很一般的字符串解析)URI字段，然后载入对应的文件即可。例如以下函数：
void http_response( SOCKET con, const char *request )
{
/**//* get the method */
char *token = strtok( request, " " );
char *uri = strtok( 0, " " );
char file[64];
sprintf( file, ".%s", uri );
{
/**//* load the file content */
FILE *fp = fopen( file, "rb" );
if( fp == 0 )
{
/**//* response 404 status code */
char response[] = "HTTP/1.1 404 NOT FOUND\r\n\r\n";
&nbs