Cオブジェクト向けプログラミング--抽象データ型(2)

下一篇:Cオブジェクト向けプログラミング--抽象データ型(1)、本編は主にSetを実現する
実装--Set
main.cは正常にコンパイルできますが、プログラムをコンパイルして実行する前に、抽象的なデータ型とメモリ管理を実現する必要があります.オブジェクトが情報を格納せず、各オブジェクトが少なくとも1つのsetに属している場合は、オブジェクトと各setを一意の小さな正の整数値で表すことができます.これらの正の整数値は、配列heap[]のインデックスを使用して表すことができます.
オブジェクトがsetのメンバーである場合、対応する配列要素にはsetを表す整数値が含まれます.
Setsはオブジェクトと同じ表示を持ち、new()はtypeのタイプ記述を気にせず、heap[]の値が0の要素を返します.コードは以下の通りです.

#if ! defined MANY || MANY < 1
#define	MANY	10
#endif

static int heap [MANY];

void * new (const void * type, ...)
{	int * p;							/* & heap[1..] */

	for (p = heap + 1; p < heap + MANY; ++ p)
		if (! * p)
			break;
	assert(p < heap + MANY);
	* p = MANY;
	return p;
}

0を使用してheap[]の有効な要素をマークすると、heap[0]へのポインタを返すことができません.setの場合、そのメンバーは0インデックスを得ることができます.New()は境界を越える可能性があり、assert()を使用して回避できます.elete()はnullポインタに注意し、heap[]要素を0に設定することで回収する必要があります.

void delete (void * _item)
{	int * item = _item;

	if (item)
	{	assert(item > heap && item < heap + MANY);
		* item = 0;
	}
}

注意:汎用ポインタを統一的に処理する必要があります.そこで、変数名に下線接頭辞を付ける方法を使用します.期待するタイプで名前が近いローカル変数を初期化するだけです.
1つのsetに含まれるオブジェクトは、各要素がsetを指し、1つの要素がMANYを含む場合はsetに追加できます.そうでない場合は、setに含まれていることを示します.

void * add (void * _set, const void * _element)
{	int * set = _set;
	const int * element = _element;

	assert(set > heap && set < heap + MANY);
	assert(* set == MANY);
	assert(element > heap && element < heap + MANY);

	if (* element == MANY)
		* (int *) element = set - heap;
	else
		assert(* element == set - heap);

	return (void *) element;
}

 
他の関数は簡単です.find()はsetに下線接頭辞の変数名要素が含まれているかどうかを判断するために使用されます.

void * find (const void * _set, const void * _element)
{	const int * set = _set;
	const int * element = _element;

	assert(set > heap && set < heap + MANY);
	assert(* set == MANY);
	assert(element > heap && element < heap + MANY);
	assert(* element);

	return * element == set - heap ? (void *) element : 0;
}

 
contains()はfind()で得られた結果を真の値に変換します.

int contains (const void * _set, const void * _element)
{
	return find(_set, _element) != 0;
}

drop()はfind()関数に依存して削除する要素がsetにあるかどうかをチェックします.もしそうであれば、対応するオブジェクト要素の値をMANYとマークします.

void * drop (void * _set, const void * _element)
{	int * element = find(_set, _element);

	if (element)
		* element = MANY;
	return element;
}

次に、2つのオブジェクトが等しいかどうかを判断する関数differ()が提供される.

int differ (const void * a, const void * b)
{
	return a != b;
}

 
完全なSet.cソースコードは以下の通りである.

#include <assert.h>
#include <stdio.h>

#include "new.h"
#include "Set.h"
#include "Object.h"

const void * Set;
const void * Object;

#if ! defined MANY || MANY < 1
#define	MANY	10
#endif

static int heap [MANY];

void * new (const void * type, ...)
{	int * p;							/* & heap[1..] */

	for (p = heap + 1; p < heap + MANY; ++ p)
		if (! * p)
			break;
	assert(p < heap + MANY);
	* p = MANY;
	return p;
}

void delete (void * _item)
{	int * item = _item;

	if (item)
	{	assert(item > heap && item < heap + MANY);
		* item = 0;
	}
}

void * add (void * _set, const void * _element)
{	int * set = _set;
	const int * element = _element;

	assert(set > heap && set < heap + MANY);
	assert(* set == MANY);
	assert(element > heap && element < heap + MANY);

	if (* element == MANY)
		* (int *) element = set - heap;
	else
		assert(* element == set - heap);

	return (void *) element;
}

void * find (const void * _set, const void * _element)
{	const int * set = _set;
	const int * element = _element;

	assert(set > heap && set < heap + MANY);
	assert(* set == MANY);
	assert(element > heap && element < heap + MANY);
	assert(* element);

	return * element == set - heap ? (void *) element : 0;
}

int contains (const void * _set, const void * _element)
{
	return find(_set, _element) != 0;
}

void * drop (void * _set, const void * _element)
{	int * element = find(_set, _element);

	if (element)
		* element = MANY;
	return element;
}

int differ (const void * a, const void * b)
{
	return a != b;
}