fastfind.c

来自「一个很有名的浏览器」· C语言 代码 · 共 795 行 · 第 1/2 页

static void
compress_tree(struct ff_node *leafset, struct fastfind_info *info)
{
	int cnt = 0;
	int pos = 0;
	int i;

	assert(info);
	if_assert_failed return;

	for (i = 0; i < info->uniq_chars_count; i++) {
		if (leafset[i].c) continue;

		if (leafset[i].l) {
			/* There's a leaf leafset, descend to it and recurse */
			compress_tree(info->leafsets[leafset[i].l], info);
		}

		if (leafset[i].l || leafset[i].e) {
			cnt++;
			pos = i;
		}
	}

	if (cnt != 1 || leafset[pos].c) return;

	/* Compress if possible ;) */
	for (i = 1; i < info->leafsets_count; i++) {
		if (info->leafsets[i] == leafset) {
			compress_node(leafset, info, i, pos);
			return;
		}
	}
}

#define ifcase(c) (info->case_aware ? (c) : toupper(c))

struct fastfind_index *
fastfind_index(struct fastfind_index *index, enum fastfind_flags flags)
{
	struct fastfind_key_value *p;
	struct fastfind_info *info;

	assert(index && index->reset && index->next);
	if_assert_failed goto return_error;

	info = init_fastfind(index, flags);
	if (!info) goto return_error;

	/* First search min, max, count and uniq_chars. */
	index->reset();

	while ((p = index->next())) {
		int key_len = strlen(p->key);
		int i;

		assert(key_len > 0 && key_len <= FF_MAX_KEYLEN);
		if_assert_failed goto return_error;

		if (key_len < info->min_key_len)
			info->min_key_len = key_len;

		if (key_len > info->max_key_len)
			info->max_key_len = key_len;

		for (i = 0; i < key_len; i++) {
			/* ifcase() test should be moved outside loops but
			 * remember we call this routine only once per list.
			 * So I go for code readability vs performance here.
			 * --Zas */
			int k = ifcase(p->key[i]);

			assert(k < FF_MAX_CHARS);
			if_assert_failed goto return_error;

			if (char2idx(k, info) == -1) {
				assert(info->uniq_chars_count < FF_MAX_CHARS);
				if_assert_failed goto return_error;

				info->uniq_chars[info->uniq_chars_count++] = k;
			}
		}

		info->count++;
	}

	if (!info->count) return 0;

	init_idxtab(info);

	/* Root leafset allocation */
	if (!alloc_leafset(info)) goto return_error;

	info->root_leafset = info->leafsets[info->leafsets_count];

	if (!alloc_ff_data(info)) goto return_error;

	/* Build the tree */
	index->reset();

	while ((p = index->next())) {
		int key_len = strlen(p->key);
		struct ff_node *leafset = info->root_leafset;
		int i;

#if 0
		fprintf(stderr, "K: %s\n", p->key);
#endif
		for (i = 0; i < key_len - 1; i++) {
			/* Convert char to its index value */
			int idx = info->idxtab[ifcase(p->key[i])];

			/* leafset[idx] is the desired leaf node's bucket. */

			if (leafset[idx].l == 0) {
				/* There's no leaf yet */
				if (!alloc_leafset(info)) goto return_error;
				leafset[idx].l = info->leafsets_count;
			}

			/* Descend to leaf */
			leafset = info->leafsets[leafset[idx].l];
		}

		/* Index final leaf */
		i = info->idxtab[ifcase(p->key[i])];

		leafset[i].e = 1;

		/* Memorize pointer to data */
		leafset[i].p = info->pointers_count;
		add_to_ff_data(p->data, key_len, info);
	}

	if (info->compress)
		compress_tree(info->root_leafset, info);

	return index;

return_error:
	fastfind_done(index);
	return NULL;
}

#undef ifcase


/* This macro searchs for the key in indexed list */
#define FF_SEARCH(what) do {							\
	int i;									\
										\
	for (i = 0; i < key_len; i++) {						\
		int lidx, k = what;						\
										\
		FF_DBG_iter(info);						\
										\
		FF_DBG_test(info);						\
		if (k >= FF_MAX_CHARS) return NULL;				\
		lidx = info->idxtab[k];						\
										\
		FF_DBG_test(info);						\
		if (lidx < 0) return NULL;					\
										\
		FF_DBG_test(info);						\
		if (current->c) {						\
			/* It is a compressed leaf. */				\
			FF_DBG_test(info);					\
			if (((struct ff_node_c *) current)->ch != lidx)		\
				return NULL;					\
		} else {							\
			current = &current[lidx];				\
		}								\
										\
		FF_DBG_test(info);						\
		if (current->e) {						\
			struct ff_data *data = &info->data[current->p];		\
										\
			FF_DBG_test(info);					\
			if (key_len == data->keylen) {				\
				FF_DBG_found(info);				\
				return data->pointer;				\
			}							\
		}								\
										\
		FF_DBG_test(info);						\
		if (!current->l) return NULL;					\
		current = (struct ff_node *) info->leafsets[current->l];	\
	}									\
} while (0)

void *
fastfind_search(struct fastfind_index *index, unsigned char *key, int key_len)
{
	struct ff_node *current;
	struct fastfind_info *info;

	assert(index);
	if_assert_failed return NULL;

	info = index->handle;

	assertm(info, "FastFind index %s not initialized", index->comment);
	if_assert_failed return NULL;

	FF_DBG_search_stats(info, key_len);

	FF_DBG_test(info); if (!key) return NULL;
	FF_DBG_test(info); if (key_len > info->max_key_len) return NULL;
	FF_DBG_test(info); if (key_len < info->min_key_len) return NULL;

	current = info->root_leafset;

	/* Macro and code redundancy are there to obtain maximum
	 * performance. Do not move it to an inlined function.
	 * Do not even think about it.
	 * If you find a better way (same or better performance) then
	 * propose it and be prepared to defend it. --Zas */

	FF_DBG_test(info);
	if (info->case_aware)
		FF_SEARCH(key[i]);
	else
		FF_SEARCH(toupper(key[i]));

	return NULL;
}

#undef FF_SEARCH

void
fastfind_done(struct fastfind_index *index)
{
	struct fastfind_info *info;

	assert(index);
	if_assert_failed return;

	info = index->handle;
	if (!info) return;

	FF_DBG_dump_stats(info);

	mem_free_if(info->data);
	while (info->leafsets_count) {
		mem_free_if(info->leafsets[info->leafsets_count]);
		info->leafsets_count--;
	}
	mem_free_if(info->leafsets);
	mem_free(info);

	index->handle = NULL;
}


/* EXAMPLE */

#if 0
struct list {
	unsigned char *tag;
	int val;
};

struct list list[] = {
	{"A",		1},
	{"ABBR",	2},
	{"ADDRESS",	3},
	{"B",		4},
	{"BASE",	5},
	{"BASEFONT",	6},
	{"BLOCKQUOTE",	7},
	{"BODY",	8},
	{"BR",		9},
	{"BUTTON",	10},
	{"CAPTION",	11},
	{"CENTER",	12},
	{"CODE",	13},
	{"DD",		14},
	{"DFN",		15},
	{"DIR",		16},
	{"DIV",		17},
	{"DL",		18},
	{"DT",		19},
	{"EM",		20},
	{"FIXED",	21},
	{"FONT",	22},
	{"FORM",	23},
	{"FRAME",	24},
	{"FRAMESET",	25},
	{"H1",		26},
	{"H2",		27},
	{"H3",		28},
	{"H4",		29},
	{"H5",		30},
	{"H6",		31},
	/* {"HEAD",	html_skip,	0, 0}, */
	{"HR",		32},
	{"I",		33},
	{"IFRAME",	34},
	{"IMG",		35},
	{"INPUT",	36},
	{"LI",		37},
	{"LINK",	38},
	{"LISTING",	39},
	{"MENU",	40},
	{"NOFRAMES",	41},
	{"OL",		42},
	{"OPTION",	43},
	{"P",		44},
	{"PRE",		45},
	{"Q",		46},
	{"S",		47},
	{"SCRIPT",	48},
	{"SELECT",	49},
	{"SPAN",	50},
	{"STRIKE",	51},
	{"STRONG",	52},
	{"STYLE",	53},
	{"SUB",		54},
	{"SUP",		55},
	{"TABLE",	56},
	{"TD",		57},
	{"TEXTAREA",	58},
	{"TH",		59},
	{"TITLE",	60},
	{"TR",		61},
	{"U",		62},
	{"UL",		63},
	{"XMP",		64},
	{NULL,		0}, /* List terminaison is key = NULL */
};


struct list *internal_pointer;

/* Reset internal list pointer */
void
reset_list(void)
{
	internal_pointer = list;
}

/* Returns a pointer to a struct that contains
 * current key and data pointers and increment
 * internal pointer.
 * It returns NULL when key is NULL. */
struct fastfind_key_value *
next_in_list(void)
{
	static struct fastfind_key_value kv;

	if (!internal_pointer->tag) return NULL;

	kv.key = internal_pointer->tag;
	kv.data = internal_pointer;

	internal_pointer++;

	return &kv;
}

static struct fastfind_index ff_index
	= INIT_FASTFIND_INDEX("example", reset_list, next_in_list);

int
main(int argc, char **argv)
{
	unsigned char *key = argv[1];
	struct list *result;

	if (!key || !*key) {
		fprintf(stderr, "Usage: fastfind keyword\n");
		exit(-1);
	}

	fprintf(stderr, "---------- INDEX PHASE -----------\n");
	/* Mandatory */
	fastfind_index(&ff_index, FF_COMPRESS);

	fprintf(stderr, "---------- SEARCH PHASE ----------\n");
	/* Without this one ... */
	result = (struct list *) fastfind_search(&ff_index, key, strlen(key));

	if (result)
		fprintf(stderr, " Found: '%s' -> %d\n", result->tag, result->val);
	else
		fprintf(stderr, " Not found: '%s'\n", key);

	fprintf(stderr, "---------- CLEANUP PHASE ----------\n");
	fastfind_done(&ff_index);

	exit(0);
}

#endif

#endif /* USE_FASTFIND */