魔法のリスト - 続き

信じられないような話しですが、下記の方法で実現可能です。

        u            v            w
     +-----+      +-----+      +-----+
  .. | t^v |--><--| u^w |--><--| v^x | ..
     +-----+      +-----+      +-----+

t, u, v, w, x はセルのアドレス、「^」は排他的論理和(exclusive OR)です。つまり、ptr には直前のセルのアドレスと直後のセルのアドレスの排他的論理和を入れるのです。

リスト構造で現在位置にたどり着くためには少なくとも直前のセルのアドレスは知っているはずですから、もし、自分のセルのポインタに直前のセルのアドレス u と直後のセルのアドレス w の排他的論理和 u^w が入っているとしたら、直後のセルのアドレス w は、簡単な論理計算

  u^(u^w) = (u^u)^w = 0^w = w

によって、直前のセルのアドレスと自分のセルのポインタから計算できることがわかります。直後のセルから直前のセルのアドレスを求める場合は

  w^(u^w) = w^(w^u) = (w^w)^u = 0^w = u

ですが、直前と直後という関係は行きと戻りの進行方向とは無関係ですから、同じ結果になって当然です。

この方式の本質は、ポインタとして隣のセルの絶対アドレスでなく、アドレスの「差」を記憶していることにありますが、排他的論理和を使うと、どちらの方向の差も同じ値になるため記憶すべきデータが１つですむというのがアイデアの核心です。

以下、実際にプログラム magic.cを書いて試してみましょう。下記のプログラムは、数値データ 0, 1, 2, 3, 4 を格納したセルを双方向リストにして、行きと戻りが同じポインタでたどれることを実証しています。top はリストの先頭、 bot はリストの後尾です。

行きと戻りがまったく同じプログラムで実現されていることに注意してください。違うのは初期条件だけです。リストの端まで来たかどうかの判定

  if (next == NULL) break;

を取り去ると、永久に端から端まで、行ったり来たりすることになります。

ポインタに格納されるアドレスや直前直後のセルのアドレスを見たいときは、

  cc -DDEBUG magic.c -o magic

でコンパイルしてください。また、このプログラムはunsigned intと ポインタが同じ大きさであることを期待しています。もしそうでないシステムの場合は、排他的論理和を計算する部分を書き換えてください。


/*
 * magical list
 *
 * 1998-04-29 Kouichi Hirabayashi
 */

#include <stdio.h>
#include <stdlib.h>

#ifdef DEBUG
#define dprintf	printf
#else
#define dprintf
#endif

#define N	5

struct cell {
  int num;
  struct cell *ptr;
};

struct cell *top, *bot, *prev;

main(argc, argv) char **argv;
{
  int i;

  if (sizeof(struct cell *) != sizeof(unsigned int))
	printf(
"This program depneds on the fact that the size of pointer equals the size of integer.\n"),
	exit(1);

  /* making bidirectional list structure */
  dprintf("add list:\n");
  for (i = 0; i < N; i++)
	addlist(i);

  printf("forward:\n");
  prtlist(top);

  printf("backword:\n");
  prtlist(bot);
}

addlist(n)
{
  struct cell *p;

  p = (struct cell *)malloc(sizeof(struct cell));
  p->num = n;
  dprintf("%08x, %08x, %08x: ", prev, bot, p);
  printf("%d\n", n);
  if (top == NULL) {
	prev = NULL;
	top = bot = p;
	p->ptr = bot;
  }
  else {
	p->ptr = bot;
	bot->ptr = (struct cell *)((unsigned int)prev ^ (unsigned int)p);
	prev = bot;
	bot = p;
  }
}

prtlist(start) struct cell *start;
{
  struct cell *p, *next;

  for (prev = NULL, p = start; ; p = next) {
	dprintf("%08x,%08x,%08x: ", prev, p, p->ptr);
	printf("%d\n", p->num);
	next = (struct cell *)((unsigned int)prev ^ (unsigned int)p->ptr);
	if (next == NULL)
		break;
	prev = p;
	dprintf(" ->%08x\n", next);
  }
}

平林浩一, 1998