Mercurial > hg > Applications > Grep
view regex/main.cc @ 40:c25b75f764a7
add Regex.h
author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 02 Mar 2015 22:18:37 +0900 |
parents | 120c8116e831 |
children | e1c5ecbf8836 |
line wrap: on
line source
#include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <math.h> #include <string.h> #include <sys/mman.h> #include <sys/stat.h> #include <sys/types.h> #include <fcntl.h> #include "Regex.h" const char *usr_help_str = "Usage: ./regex [-file filename] [-sw SearchWord]\n"; //Boyer Moore法に使用するテーブルを作成 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){ bmdata->skipTable[i] = searchWordLen; } for(int j = 0; j < searchWordLen - 1; ++j){ bmdata->skipTable[(u_char)searchWord[j]] = searchWordLen - j - 1; } return skipTable; } //Boyer Moore法による文字列検索アルゴリズム static void* BMmethod(BMDataPtr bmdata,ResultPtr result) { int i = bmdata->searchWordLen - 1; int matchCounter = 0; 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(bmdata->skipTable[(u_char)bmdata->readText[i]],bmdata->searchWordLen - j); } result->matchNum = matchCounter; return result; } int main(int argc, char* argv[]) { char *filename = 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 = (char*)argv[i+1]; i++; } } // prepare file read if (filename == 0) { puts(usr_help_str); exit(1); } struct stat sb; long fd = 0; char *textfile; if ((fd=open(filename,O_RDONLY,0666))==0) { fprintf(stderr,"can't open %s\n",filename); } if (fstat(fd,&sb)) { 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); exit(0); } // prepare Boyer Moore Search bmdata->searchWord = searchWord; bmdata->searchWordLen = strlen((const char*)bmdata->searchWord); bmdata->skipTable = createBMskiptable(bmdata); ResultPtr result = (ResultPtr)malloc(sizeof(Result)); BMmethod(bmdata,result); printf("sword: %s len: %d\n",bmdata->searchWord,bmdata->searchWordLen); printf("Match : %d\n",result->matchNum); free(result); free(bmdata); return 0; }