月度归档： 2017年2月

如何恢复全局INDEX

一般来说，当需要分配全局惟一id时，一般都会有一个变量来记录当前最新的id值，比如叫INDEX变量。

每次需要分配id时，只要简单的自增一下INDEX变量，然后INDEX的值即为当前分配出去的ID的值。

为了最大可能的延迟复用已经分配过的id，一般来说不会去特殊处理INDEX变量，即每次自增INDEX，并允许回绕情况的发生。

但是最近碰到问题就是，我有一堆分配过的id，如何重新恢复出INDEX的值。具体场景如下：

struct obj {
        unsigned int id;
        time_t createtime;
        ...
}

每一个obj对象都需要有一个全局惟一id和创建时间(createtime字段)与其关联，因此每new一个obj对象就需要为其分配一个不重复的全局id。

obj可以被人为删除，也会被过期删除，因此无法保证在任何时间所有还存活着的obj对象id是连续的。这些obj对象会被定时写入数据库。

一旦进程被重启，程序会从数据库加载所有还存活着的obj对象，以便可以恢复现场，使重启进程这一操作透明。要保证整个逻辑正确性，还必须要能正确的恢复出INDEX变量。

那么问题来了，而由于某种原因，INDEX并不方便被存入数据库中。

因此必须要根据现有的存活obj对象来恢复出在进程重启前的INDEX的值。

第一反应，肯定是遍历一之后找到obj对象中最大的id即为原来的INDEX，但是这里有一个陷阱就是INDEX会回绕，一旦INDEX会回绕之后，这个算法就不正确了。

考虑这样一种情况，进程运行了数月都没有重启，这时残留的obj对象id可能就只剩下0xfffffffe,0xffffffff,0,1,3,5这些了，重启之后采用上述算法无法重新恢复出重启前INDEX的值为5.

再一看，还有一个createtime用作参考，只要取obj对象中createtime最大的那个对象的id为INDEX就行了。

然而，由于createtime是以秒为单位的，逻辑上无法保证1秒只创建一个obj对象，问题再次绕回到第一个算法所遇到的困境。

因此，看起来，想要正确恢复出INDEX的值就必须解决回绕的问题。

要解决这个问题，就必须要有一种大小比较算法，这种算法即使在回绕时，也能正确判断大小。比如在0xfffffffe,0xffffffff,0,1,3,5这一堆id中，此算法会认为5是最大值，而在3,5,7,9这一块id中认为9才是最大值。

那么究竟有没有这种算法呢？比较巧的是，还真有这种算法。

假设有A，B，C三个32位无符号值，C=(A+B) % 4G。那么只要B大于0且小于2G，C – A就一定大于0。不过这里有一个陷阱，如果A和C是无符号变量，那么一定要将C-A的值转换为int之后再使用。

再回到设定场景中去，虽然我们1秒可以new很多个obj对象，但是绝不可能new出2G个之多。

有了这个事实和算法，答案就呼之欲出了，其中一种实现如下：

unsigned int id = 0;
time_t time = 0;
for (auto const &obj:objs) {
        if (obj.createtime < time)
                continue;
        if (obj.createtime > time) {
                time = obj.createtime;
                id = obj.id;
        } else if ((int)(id - obj.id) < 0) {
                 id = obj.id
        }
}
//now we got the final INDEX value

ps. 在阐述这个blog之前，我曾请教了几个人，但似乎并没有其他更好的做法，觉得这个实现还算精巧，就做个笔记.

为什么要有头文件

我在写C文件时，一般会首先确定这个模块需要哪些功能，然后在头文件中定义相应的接口函数。之后才是在C文件中实现，在实现过程中除非有遗漏的接口，不然是不会再切回头文件的，一般辅助函数我都是直接以static的方式定义在C文件中。

在写C++代码时，这些代码辅助类的函数，都必需要以private的方式在头文件中声明。这会导致在写代码时，需要频繁在h/cpp之间切换，极度令人不舒服。

因此每次在写C++代码时，都免不了在心里抱怨几句为什么不把private函数直接定义在cpp文件中，或者干脆像java一样不要头文件算了。

前两天把这事跟朋友抱怨了一下，结果竟然得到了一个反问为什么需要头文件，头文件的作用到底是什么？

有人说头文件是为了展现接口，以头文件和.a或.so发布时，别人只要看头文件就可以知道提供了什么接口，然而对于java这类没有头文件的语言来讲只要一个工具同样可以提取出来class文件中的public接口信息。因此我觉得还是需要从编译器角度来分析一下头文件的用途。

那么C语言的头文件到底起到什么作用呢？且看下面一段代码(ps.为了使这段代码在任何平台上效果都一样，使用了stdint.h中的可移植类型):

////////////compile: gcc -o a a.c b.c
////////////b.h
#ifndef _B_H
#define _B_H
#include <stdint.h>
struct test {
        uint8_t a1;
        uint8_t a2;
        uint8_t b1;
        uint8_t b2;
};
#endif
////////////b1.h
#ifndef	_B1_H
#define	_B1_H
#include <stdint.h>
struct test {
        uint16_t a;
        uint16_t b;
};
extern struct test T;
#endif
////////////b.c
#include "b.h"
struct test T = {.a1 = 1, .a2 = 2, .b1 = 3, .b2 = 4};
////////////a.c
#include &lt;stdio.h&gt;
#include "b1.h"
int main()
{
        printf("a:0x%x b:0x%x\n", T.a, T.b);
        return 0;
}

这段代码的运行结果很有意思，是’a:0x201 b:0x403’。

这段代码编译器不会报任何错误，甚至连警告也不会报。为什么会这样呢？这要从几个.c文件变成elf(linux)/exe(win)文件过程说起。

从c文件到可执行文件至少要经过两个阶段，即‘编译’和‘链接’。
‘编译’会将相应的C代码转换成相应的汇编，但保留符号名（如上述代码中的T）然后生成.o文件.
而‘链接’会收集所有的.o文件然后为每个符号分配地址，并将.o文件中的相应的符号换成相关地址并生成相应格式的可执行文件（ps.上面的流程并不严谨).

以a.c中的代码为例，在编译时T.a语句其实就已经转换为了与*((uint16_t*)((uint8_t *)&T+0))等效的汇编代码，相应的T.b的语句等效*((uint16_t*)((uint8_t *)&T+sizeof(uint16_t))).这一点其实可以通过gcc -S来反汇编证明。

那么头文件的功能就呼之欲出了，在‘编译期间’为了保证能生成正确的汇编代码，必须要头文件指明struct的字段分布，及此c文件中引用的符号在外部有提供（这就是声明的意义)。

当然头文件所带来的问题也正像上述代码中描述的一样，当给出一个错误的头文件时编译器并不会察觉，在没有源码的情况下，这种错误极难发现。

那么java是如何实现的呢？我尝试着写了两个类编译了一下。猜测，他应该是在编译时自动提取出本类的声明信息，然后放在.class文件中，当javac编译时用到某个类时就去找当前目录下打开‘类.class’文件，从其中提出取类的声明信息，从而达到与有头文件有相同的效果。

ps. 我怀疑.class的声明信息与其反射机制有密切关系，但是jvm的代码量有20多万行，找到其反射部分的实现还是比较麻烦的，天气这么冷还是先放一下:)

pps. 如果C语言也这么搞的话，似乎是行不通的，java中的类的概念，可以约定使用哪个类就从‘类名.class’文件中寻找，如果是C呢，找一个struct test的布局去test.o中找？那找一个函数helloworld应该去哪个文件中找呢？

在与Qwerty交流后发现，查找helloworld函数时可以根据此c文件import的模块来实现，那么似乎为C引用import机制也并不是不太可能。

简单思考了一下，在不改变现有编译流程的情况下，似乎可以为c文件引入一个轻量级import机制来代替头文件。

我们可以在编译器（如：gcc）之上包个壳，假设叫xcc，然后为.o为文件也加上一个壳叫.m。

.m文件其实包含了其源文件中的public的函数接口定义和一个完整的gcc编译出来的.o文件内容。

xcc的执行流程大概如下：

1. 使用xcc编译A.c文件时，xcc首先分析出A.c文件中的声明信息’T’及import的模块’M’。
2. 从M.m文件中提取出M.c文件中的声明信息T，并生成M.h文件，之后将a.c中的import ‘M’替换为#include “M.h”,并另存为到/tmp/A.c.tmp。
3. 调用相应的编译器如’gcc’编译/tmp/A.c.tmp生成A.o
4. 将A.c的声明信息T追加到A.o的最后（之所以追加到最后，是因为A.m可以被当作A.o直接传给ld, 这样我们就不用为ld再包一个壳了)

有一个特例，一个struct是否要导出，必须要等分析完所有的导出接口之后才能决定，如果在导出接口参数中有用到，那么我们就可以将其导出到头文件中。

如此，我们就有了一个兼容import的C语言。