Mercurial > hg > Members > masakoha > testcode
changeset 39:120c8116e831
refactoring
author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 02 Mar 2015 22:15:55 +0900 |
parents | d15b9d342421 |
children | c25b75f764a7 |
files | regex/main.cc |
diffstat | 1 files changed, 50 insertions(+), 25 deletions(-) [+] |
line wrap: on
line diff
--- a/regex/main.cc Sun Mar 01 14:10:25 2015 +0900 +++ b/regex/main.cc Mon Mar 02 22:15:55 2015 +0900 @@ -10,53 +10,71 @@ const char *usr_help_str = "Usage: ./regex [-file filename] [-sw SearchWord]\n"; +typedef struct result { + int matchNum; + int matchLineNum; + char* matchLine; +} Result, *ResultPtr; + +typedef struct bmData { + int* skipTable; + char* readText; + int readTextLen; + char* searchWord; + int searchWordLen; +} BMData, *BMDataPtr; + //Boyer Moore法に使用するテーブルを作成 -int* -createBMskiptable(u_char *search_word,int search_word_len,int *skip_table) +int * +createBMskiptable(BMDataPtr bmdata) { + int searchWordLen = bmdata->searchWordLen; + char *searchWord = bmdata->searchWord; + int* skipTable = (int*)malloc(sizeof(int)*256); + for(int i = 0; i < 256; ++i){ - skip_table[i] = search_word_len; + bmdata->skipTable[i] = searchWordLen; } - for(int j = 0; j < search_word_len - 1; ++j){ - skip_table[search_word[j]] = search_word_len - j - 1; + for(int j = 0; j < searchWordLen - 1; ++j){ + bmdata->skipTable[(u_char)searchWord[j]] = searchWordLen - j - 1; } - return skip_table; + return skipTable; } //Boyer Moore法による文字列検索アルゴリズム -static int BMmethod(u_char *text,int textLen, - u_char *pattern,int swLen,int *skipTable) +static void* BMmethod(BMDataPtr bmdata,ResultPtr result) { - int i = swLen - 1; + int i = bmdata->searchWordLen - 1; int matchCounter = 0; - while ( i < textLen){ - int j = swLen - 1; - while (text[i] == pattern[j]){ + while ( i < bmdata->readTextLen){ + int j = bmdata->searchWordLen - 1; + while (bmdata->readText[i] == bmdata->searchWord[j]){ if (j == 0){ matchCounter++; } --i; --j; } - i = i + fmax(skipTable[text[i]],swLen - j); + i = i + fmax(bmdata->skipTable[(u_char)bmdata->readText[i]],bmdata->searchWordLen - j); } - return matchCounter; + + result->matchNum = matchCounter; + return result; } int main(int argc, char* argv[]) { char *filename = 0; - // "u_char" is "unsigned char" in sys/types.h - u_char *searchWord = 0; + char *searchWord = 0; // check argument for (int i = 0; argv[i]; i++) { if (strcmp(argv[i], "-file") == 0) { filename = (char*)argv[i+1]; i++; }else if (strcmp(argv[i], "-sw") == 0) { - searchWord = (u_char*)argv[i+1]; i++; + searchWord = (char*)argv[i+1]; i++; } } @@ -78,9 +96,15 @@ fprintf(stderr,"can't fstat %s\n",filename); } + BMDataPtr bmdata = (BMDataPtr)malloc(sizeof(BMData)); + textfile = (char*)malloc(sb.st_size); read(fd,textfile,sb.st_size); + bmdata->readText = textfile; + bmdata->readTextLen = sb.st_size; + bmdata->skipTable = (int*)malloc(sizeof(int)*256); + if (textfile == (char*)-1) { fprintf(stderr,"Can't mmap file\n"); perror(NULL); @@ -88,17 +112,18 @@ } // prepare Boyer Moore Search + bmdata->searchWord = searchWord; + bmdata->searchWordLen = strlen((const char*)bmdata->searchWord); + bmdata->skipTable = createBMskiptable(bmdata); - int *skipTable = (int*)malloc(256 * sizeof(int)); // 文字列に対応した table を用意 - int searchWordLen = strlen((const char*)searchWord); - int *BMskip_table = createBMskiptable(searchWord, searchWordLen, skipTable); + ResultPtr result = (ResultPtr)malloc(sizeof(Result)); - int matchNum = BMmethod((u_char*)textfile,sb.st_size,searchWord,searchWordLen,BMskip_table); + BMmethod(bmdata,result); - printf("sword: %s len: %d\n",searchWord,searchWordLen); - printf("Match : %d\n",matchNum); + printf("sword: %s len: %d\n",bmdata->searchWord,bmdata->searchWordLen); + printf("Match : %d\n",result->matchNum); - free(textfile); - free(skipTable); + free(result); + free(bmdata); return 0; }