本節では置換表クラスの実装を行います。
"hash.c"に記述します。

• Hashクラスの構造

  最初にHashクラスの構造を定義します。
  

  struct _Hash
  {
  	int Num;
  	unsigned long Mask;
  	HashData *Data;
  	int GetNum;
  	int HitNum;
  };
  

  Numは登録可能な局面データの数です。
  Maskはハッシュ値から局面データのインデックスを求めるのに使用します。
  例えばNumが0x1000であれば、Maskを0x0fffとしてハッシュ値とMaskのANDをとった値がインデックスとなります。
  Dataは局面データの配列です。
  GetNumはHash_Get()が呼ばれた回数です。
  HitNumはHash_Get()が1を返した回数です。
  

• 局面データ

  局面データHashDataは以下のようになっています。
  ハッシュ値と局面情報から構成されています。
  

  struct _HashData
  {
  	HashValue Value;
  	HashInfo Info;
  };
  typedef struct _HashData HashData;
  

• 置換表クラスの生成

  次に置換表クラスの生成を行います。
  

  static int Hash_Initialize(Hash *self, int in_size)
  {
  	memset(self, 0, sizeof(Hash));
  	self->Num = 1 << in_size;
  	self->Mask = (1 << in_size) - 1;
  	self->Data = malloc(sizeof(HashData) * self->Num);
  	if (!self->Data) {
  		return 0;
  	}
  	Hash_Clear(self);
  	return 1;
  }
  
  Hash *Hash_New(int in_size)
  {
  	Hash *self;
  
  	self = malloc(sizeof(Hash));
  	if (self) {
  		if (!Hash_Initialize(self, in_size)) {
  			Hash_Delete(self);
  			self = NULL;
  		}
  	}
  	return self;
  }
  

  Hashクラスに必要なメモリの確保を行っています。
  同時にNumとMaskの設定も行います。
  Hash_Clear()を呼び出して局面データの初期化を行っていますが、この処理については後述します。
  

• 置換表クラスの破棄

  生成関数を実装したので、次は破棄関数の実装を行います。
  内容は生成時に確保したメモリを解放するだけです。
  

  static void Hash_Finalize(Hash *self)
  {
  	if (self->Data) {
  		free(self->Data);
  	}
  }
  
  void Hash_Delete(Hash *self)
  {
  	Hash_Finalize(self);
  	free(self);
  }
  

• 局面データの初期化

  生成時に呼び出していたHash_Clear()の内部は以下のようになっています。
  

  void Hash_Clear(Hash *self)
  {
  	int i;
  
  	for (i = 0; i < self->Num; i++) {
  		self->Data[i].Value.Low = ~i;
  	}
  	self->GetNum = 0;
  	self->HitNum = 0;
  }
  

  前に説明しましたが、ハッシュ値と局面データのインデックスは下位n bit(nは置換表の大きさに依存)が一致しています。
  そこで各データのハッシュ値の下位をインデックスを反転させた値にすることで「何も登録されていない状態」にします。
  その後GetNum、HitNumを0にします。

次節では局面情報の登録、取得処理を実装します。