Mercurial > hg > Applications > Grep

comparison regex/bmsearch.cc @ 41:e1c5ecbf8836

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add bmsearch.cc
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Mon, 02 Mar 2015 23:35:10 +0900
parents
children ead0a307449e
comparison
equal deleted inserted replaced
40:c25b75f764a7 41:e1c5ecbf8836
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <unistd.h>
4 #include <math.h>
5 #include <string.h>
6 #include <sys/mman.h>
7 #include <sys/stat.h>
8 #include <sys/types.h>
9 #include <fcntl.h>
10 #include "regex.h"
11
12 //Boyer Moore法に使用するテーブルを作成
13 int *
14 createBMskiptable(BMDataPtr bmdata)
15 {
16 int searchWordLen = bmdata->searchWordLen;
17 char *searchWord = bmdata->searchWord;
18 int* skipTable = (int*)malloc(sizeof(int)*256);
19
20 for(int i = 0; i < 256; ++i){
21 bmdata->skipTable[i] = searchWordLen;
22 }
23
24 for(int j = 0; j < searchWordLen - 1; ++j){
25 bmdata->skipTable[(u_char)searchWord[j]] = searchWordLen - j - 1;
26 }
27 return skipTable;
28 }
29
30 //Boyer Moore法による文字列検索アルゴリズム
31 void* BMmethod(BMDataPtr bmdata,ResultPtr result)
32 {
33 int i = bmdata->searchWordLen - 1;
34 int matchCounter = 0;
35
36 while ( i < bmdata->readTextLen){
37 int j = bmdata->searchWordLen - 1;
38 while (bmdata->readText[i] == bmdata->searchWord[j]){
39 if (j == 0){
40 matchCounter++;
41 }
42 --i;
43 --j;
44 }
45 i = i + fmax(bmdata->skipTable[(u_char)bmdata->readText[i]],bmdata->searchWordLen - j);
46 }
47
48 result->matchNum = matchCounter;
49 return result;
50 }
51