源码阅读

诡异的程序

3 Comments

几年前学习V8 javascript engine的时候，发现了一处诡异的实现，当时非常的困惑，这样的实现怎么可能正确运行呢？

下面是我缩减的代码：

#include <iostream>

typedef char* Address;

class A {
public:
  const static int i = 20;
  static int a[i];
  void print ()
  {
    for (int j = 0; j < i; ++j)
      std::cout << a[j] << std::endl;
  }
public:
  static A* FromAddress (Address addr) { return reinterpret_cast<A*>(addr+1); }
};

const int A::i;
int A::a[i] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

int main(int argc, char *argv[])
{
  A * a = new A;
  A * b = A::FromAddress (reinterpret_cast<Address>(a));
  b->print ();
  return 0;
}

如果你还没有发现其中的蹊跷指出，请看下面的gdb输出：

(gdb) start
Temporary breakpoint 1 at 0x804862d: file addr.cpp, line 23.
Starting program: /home/liang/project/hello_world/a.out

Temporary breakpoint 1, main (argc=1, argv=0xbfffe0d4) at addr.cpp:23
23        A * a = new A;
(gdb) n
24        A * b = A::FromAddress (reinterpret_cast<Address>(a));
(gdb) n
25        b->print ();
(gdb) p a
$1 = (A *) 0x804b008
(gdb) p b
$2 = (A *) 0x804b009
(gdb)

如果说b不是一个有效的、指向A的某个实例的指针，那么为什么无论在编译期还是执行期，上面的程序都没有报错呢？

我的理解：b指针包含两部分信息——类型和值，在调用print函数时，并不需要使用b指针的值，编译器能够在编译期找到正确的函数去调用，这一点可以通过检查汇编输出确认。同样，访问A的静态成员变量也不要b指针的值。那么，在什么情况下需要使用b指针的值的呢？一是访问非静态成员变量；二是调用虚成员函数。然而，class A恰恰没有这两类成员，所以上面的程序能够正常地编译和执行。

检查链表有环

1 Comment

检查链表是否有环，貌似目前的标准答案是使用两根指针。下面是Emacs中的实现，亮点在指针变量命名。

/* Signal `error' with message S, and additional arg ARG.
   If ARG is not a genuine list, make it a one-element list.  */

void
signal_error (const char *s, Lisp_Object arg)
{
  Lisp_Object tortoise, hare;

  hare = tortoise = arg;
  while (CONSP (hare))
    {
      hare = XCDR (hare);
      if (!CONSP (hare))
	break;

      hare = XCDR (hare);
      tortoise = XCDR (tortoise);

      if (EQ (hare, tortoise))
	break;
    }

  if (!NILP (hare))
    arg = Fcons (arg, Qnil);	/* Make it a list.  */

  xsignal (Qerror, Fcons (build_string (s), arg));
}

在Emacs源码中搜索tortoise，可以发现多处类似实现。