#include <linux/init.h>
#include <linux/module.h>
#include <linux/types.h>
#include <linux/mm.h>
#include <linux/slab.h>
//#include "regexp.h"

typedef enum{CHAR, DOT, BEGIN, END, STAR, PLUS, QUES, LIST, TYPENUM}TYPE;

typedef struct RE{
	TYPE type;
	int ch;
	char *ccl;
	int nccl;
	struct RE *next;
}RE;

int match_longest = 0;
char *match_first = NULL;


static void * getmem(size_t size)
{
	void *tmp;
	if((tmp = kmalloc(size, GFP_ATOMIC))==NULL)
	{
		printk("malloc failed");
		return NULL;
	}
	return tmp;
}

static size_t creat_list(char *str, int start, int end)
{
	size_t cnt = end - start + 1;
	for(; start <= end ;start++)
		*str++ = start;
	return (cnt > 0)?cnt:0;
}

static int in_list(char ch, RE *regexp)
{
	char *str = regexp->ccl;
	if(regexp->type != LIST)
		return 0;
	for(; *str && ch != *str; str++)
		;
	return (*str != '\0') ^ regexp->nccl;
}

static void regexp_free(RE *regexp)
{
	RE *tmp;
	for(; regexp; regexp = tmp)
	{
		tmp = regexp->next;
		kfree(regexp);
	}
}

static RE* compile(char *regexp)
{
	RE head, *tail, *tmp;
	char *pstr;
	int err_flag = 0;

	for(tail = &head; *regexp != '\0' && err_flag == 0; regexp++)
	{
		tmp = getmem(sizeof(RE));
		switch(*regexp){
			case '\\':
				regexp++;
				if(*regexp == 'd')
				{
					tmp->type = LIST;
					tmp->nccl = 0;
					tmp->ccl = getmem(11);
					creat_list(tmp->ccl, '0','9');
					tmp->ccl[11] = '\0';
				}else if(*regexp == 'D')
				{
					tmp->type = LIST;
					tmp->nccl = 1;
					tmp->ccl = getmem(11);
					creat_list(tmp->ccl, '0','9');
					tmp->ccl[11] = '\0';
				}else
				{
					tmp->type = CHAR;
					tmp->ch = *(regexp + 1);
				}
				break;
			case '.':
				tmp->type = DOT;
				break;
			case '^':
				tmp->type = BEGIN;
				tmp->ch = '^';
				break;
			case '$':
				tmp->type = END;
				tmp->ch = '$';
				break;
			case '*':
				tmp->type = STAR;
				break;
			case '+':
				tmp->type = PLUS;
				break;
			case '?':
				tmp->type = QUES;
				break;
			case '[':
				pstr = tmp->ccl = getmem(256);
				tmp->nccl = 0;
				if(*++regexp == '^')
				{
					tmp->nccl = 1;
					regexp++;
				}
				while(*regexp != '\0' && *regexp != ']')
				{
					if(*regexp != '-')
					{
						*pstr++ = *regexp++;
						continue;
					}
					if(pstr == tmp->ccl || *(regexp + 1) == ']')
					{
						err_flag = 1;
						break;
					}
					pstr += creat_list(pstr, *(regexp - 1) + 1, *(regexp + 1));
					regexp += 2;
				}
				*pstr = '\0';
				if(*regexp == '\0')
					err_flag = 1;
				tmp->type = LIST;
				break;
			default:
				tmp->type = CHAR;
				tmp->ch = *regexp;
		}

		tail->next = tmp;
		tail = tmp;
	}

	tail->next = NULL;
	if(err_flag)
	{
		regexp_free(head.next);
		return NULL;
	}
	return head.next;
}

#define MATCH_ONE(reg, text) \
   	(reg->type == DOT || in_list(*text, reg) || *text == reg->ch)
#define MATCH_ONE_P(reg, text) \
   	(in_list(*text++, reg) || *(text - 1) == reg->ch || reg->type == DOT)

static int matchhere(RE *regexp, char *text);

static int matchstar(RE *cur, RE *regexp, char *text)
{
	do{
		if(matchhere(regexp, text))
			return 1;
	}while(*text != '\0' && MATCH_ONE_P(cur, text));
	return 0;
}

static int matchstar_l(RE *cur, RE *regexp, char *text)
{
	char *t;
	for(t = text; *t != '\0' && MATCH_ONE(cur, t); t++)
		;
	do{
		if(matchhere(regexp, t))
			return 1;
	}while(t-- > text);
	return 0;
}

static int matchplus(RE *cur, RE *regexp, char *text)
{
	while(*text != '\0' && MATCH_ONE_P(cur, text))
	{
		if(matchhere(regexp, text))
			return 1;
	}
	return 0;
}

static int matchplus_l(RE *cur, RE *regexp, char *text)
{
	char *t;
	for(t = text; *t != '\0' && MATCH_ONE(cur, t); t++)
		;
	for(; t > text; t--)
	{
		if(matchhere(regexp, t))
			return 1;
	}
	return 0;
}

static int matchques(RE *cur, RE *regexp, char *text)
{
	int cnt = 1;
	char *t = text;
	if(*t != '\0' && cnt-- && MATCH_ONE(cur, t))
		t++;
	do{
		if(matchhere(regexp, t))
			return 1;
	}while(t-- > text);
	return 0;
}

static int (*matchfun[TYPENUM][2])(RE *, RE *, char *) = {
	0, 0, 0, 0, 0, 0, 0, 0,
	matchstar, matchstar_l,
	matchplus, matchplus_l,
	matchques, matchques,
};

static int matchhere(RE *regexp, char *text)
{
	if(regexp == NULL)
		return 1;
	if(regexp->type == END && regexp->next == NULL)
		return *text == '\0';
	if(regexp->next && matchfun[regexp->next->type][match_longest])
		return matchfun[regexp->next->type][match_longest](regexp, regexp->next->next, text);

	if(*text != '\0' && MATCH_ONE(regexp, text))
		return matchhere(regexp->next, text + 1);
	return 0;
}

/* 
 * return value:
 *		-1		error
 *		0		not match
 *		1		matched
 */
int regexp_match(char *reg, char *text)
{
	int ret;
	RE *regexp = compile(reg);
	if(regexp == NULL)
		return -1;

	if(regexp->type == BEGIN)
	{
		ret = matchhere(regexp->next, text);
		goto out;
	}

	do{
		if(ret = matchhere(regexp, text))
		{
			goto out;
		}
	}while(*text++ != '\0');

out:
	regexp_free(regexp);
	return ret;
}


void TEST_reg_func(char *reg, char * str, int ret)
{
	
	if (ret != regexp_match(reg, str)) {
		if (reg)
			printk("reg = %s,", reg);
		else
			printk("reg = null");
		if (str)
			printk("str = %s ", str);
		else
			printk("str= null");
		printk("error, unit test.... failed, ret = %d\n",ret);
	}
	else {
		if (reg && str)
			printk("[unit test] %s %s......ok,ret = %d\n", reg, str, ret);
	}
}

void TEST_regexp(void)
{
	TEST_reg_func(".*baidu.com$", "www.baidu.com", 1);
	TEST_reg_func("^sina.com", "www.sina.com.cn", 0);
	TEST_reg_func("^sina.com", "sina.com.cn", 1);
	TEST_reg_func(".*baidu.com$", "www.baidu.com223", 0);
}