/*
 *	clipsrch.c
 *
 *	POSIX標準のリニアサーチ関数
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2001-2014 Naoyuki Sawa
 *
 *	* Mon Jan 13 19:05:18 JST 2014 Naoyuki Sawa
 *	- lfind()とlsearch()の宣言を、clippce.h⇒include/search.hへ分離しました。
 *	- lfind()とlsearch()の実装を、clippce.c⇒clipsrch.cへ分離しました。
 *	* Fri Feb 14 21:17:26 JST 2014 Naoyuki Sawa
 *	- hcreate(),hsearch(),hdestroy(),hcreate_r(),hsearch_r(),hdestroy_r()を追加しました。
 */
#include "clip.h"

/****************************************************************************
 *	
 ****************************************************************************/

/* * Sat Jul 04 21:25:58 JST 2009 Naoyuki Sawa
 * - POSIX標準のリニアサーチ関数です。
 *   やや新しい標準のようで、P/ECE開発環境のEPSONライブラリには含まれていなかったので、ここで実装しました。
 *   単純な処理ですが、未ソートの配列をリニアサーチしたい(=bsearch()は使えない)場合は結構有るので、便利だと思います。
 * - 関数仕様は、Web上の資料や、MSDNなどを参照してください。(Visual C++ 6.0のMSDNにも載っています。)
 *   lfind()の引数で、numがポインタ渡しなのが無駄に見えますが、おそらく、lsearch()と引数型を一致させたためだと思います。
 *   また、base引数が、lfind()はconst、lsearch()は非constである違いに注意してください。
 *   lfind()は配列を変更せず、lsearch()は見つからなかったときに配列に要素を追加することを、明示するためだと思います。
 *   (その割には、lfind()の戻り値の型は非constになっている点が、一貫性がありませんが…)
 * - lsearch()を使って、簡単に、重複の無いセットを作成することができます。
 *   以下に、使用例を示します。
 *	<例>
 *		static int compare(const void* elem1, const void* elem2) {
 *			char* str1 = *(char**)elem1;
 *			char* str2 = *(char**)elem2;
 *			return strcmp(str1, str2);
 *		}
 *		void sample() {
 *			char* set[10];
 *			int num = 0;
 *			char* key;
 *			int i;
 *			if(num < 10) key = "One";   lsearch(&key, set, &num, sizeof set[0], compare);
 *			if(num < 10) key = "Two";   lsearch(&key, set, &num, sizeof set[0], compare);
 *			if(num < 10) key = "One";   lsearch(&key, set, &num, sizeof set[0], compare);
 *			if(num < 10) key = "Three"; lsearch(&key, set, &num, sizeof set[0], compare);
 *			if(num < 10) key = "Two";   lsearch(&key, set, &num, sizeof set[0], compare);
 *			if(num < 10) key = "Four";  lsearch(&key, set, &num, sizeof set[0], compare);
 *			for(i = 0; i < num; i++) { printf("%d: %s\n", i, set[i]); }
 *		}
 *	<結果>
 *		0: One
 *		1: Two
 *		2: Three
 *		3: Four
 */

void*
lfind(const void* key, const void* base, size_t* num, size_t width, int (*compare)(const void* elem1, const void* elem2))
{
	int i = *num;
	while(i) {
		if(!(*compare)(key, base)) {
			return (void*)base;
		}
		base = (char*)base + width;
		i--;
	}
	return NULL;
}

void*
lsearch(const void* key, void* base, size_t* num, size_t width, int (*compare)(const void* elem1, const void* elem2))
{
	void* ptr = lfind(key, base, num, width, compare);
	if(!ptr) {
		ptr = memcpy((char*)base + ((*num)++ * width), key, width);
	}
	return ptr;
}

/****************************************************************************
 *	
 ****************************************************************************/

/* hcreate(),hsearch(),hdestroy()用 */
static struct hsearch_data _htab;

/* struct hsearch_data の内部データ */
struct hsearch_internal_data {
	unsigned size;
	ENTRY table[0/*size*/];
};

/*--------------------------------------------------------------------------*/
int hcreate(size_t nel) {
	return hcreate_r(nel, &_htab);
}
int hcreate_r(size_t nel, struct hsearch_data* htab) {
	/* 引数が不正，又は，テーブルが初期化済みならば、エラー停止する。 */
	if(!nel || !htab || htab->internal) { DIE(); }
	/* 内部データを確保する。 */
	htab->internal = calloc(sizeof(struct hsearch_internal_data) + (sizeof(ENTRY) * nel), 1);
	if(!htab->internal) { DIE(); }	/* メモリ不足 */
	/* テーブルの最大エントリ数を格納する。 */
	htab->internal->size = nel;
	return 1;
}

/*--------------------------------------------------------------------------*/
ENTRY* hsearch(ENTRY item, ACTION action) {
	ENTRY* retval;
	hsearch_r(item, action, &retval, &_htab);
	return retval;
}
int hsearch_r(ENTRY item, ACTION action, ENTRY** retval, struct hsearch_data* htab) {
	ENTRY* table;
	unsigned size, i, n;
	/* 引数が不正か，又は，テーブルが未初期化ならば、エラー停止する。 */
	if(!item.key || !retval || !htab || !htab->internal) { DIE(); }
	/* テーブルの最大エントリ数と、テーブルアドレスを取り出しておく。 */
	size  = htab->internal->size;
	table = htab->internal->table;
	/* キーのハッシュを計算し、最初に参照するエントリ番号を決定する。 */
	i = (unsigned)crc32_ieee_r(item.key, strlen(item.key)) % size;
	/* 最初に参照するエントリから開始し、最大エントリ数に達するまで… */
	n = size;
	do {
		/* 空きエントリを見つけたら… */
		if(!table[i].key) {
			/* actionがFINDならば、ループを抜けエラー処理へ。 */
			if(action == FIND) { break; }
			/* actionがENTERならば、エントリを格納する。 */
			table[i] = item;
			*retval = &table[i];
			return 1;
		}
		/* キーが一致するエントリを見つけたら… */
		if(!strcmp(table[i].key, item.key)) {
			/* 検索が成功した場合、actionの値がENTERでも何もすべきではない。
			 * ■http://linuxjm.sourceforge.jp/html/LDP_man-pages/man3/hsearch.3.html
			 * ┃SVr4とPOSIX.1-2001の規定では、actionは検索が失敗したときにだけ意味を持つとなっている。
			 * ┃よって、検索が成功した場合、actionの値がENTERでも何もすべきではない。
			 * ┃バージョン2.3より前の)libcとglibcの実装はこの規格に違反しており、この状況で、指定されたkeyに対応するdataが更新される。
			 */
		//	if(action == ENTER) { table[i] = item; } ← こうしてはいけない!!
			*retval = &table[i];
			return 1;
		}
		if(++i == size) { i = 0; }
	} while(--n);
	/* actionがENTERで、keyがテーブル内に見つからず、テーブルに新しいエントリを追加する余地がなかった。
	 * 又は、actionがFINDで、keyがテーブル内に見つからなかった。
	 */
	*retval = NULL;
	return 0;
}

/*--------------------------------------------------------------------------*/
void hdestroy() {
	hdestroy_r(&_htab);
}
void hdestroy_r(struct hsearch_data* htab) {
	/* 引数が不正ならば、エラー停止する。 */
	if(!htab) { DIE(); }
	/* 内部データを開放する。テーブルが未初期化ならば、ダミー処理となる。 */
	free(htab->internal);
	/* テーブルが未初期化であることを、マークする。 */
	htab->internal = NULL;
}

