Mercurial > hg > Game > Cerium

annotate example/regex_mas/ppe/Exec.cc @ 1740:5a294d8e5643 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix
author Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
date Tue, 12 Nov 2013 16:56:43 +0900
parents dfeeb2f681db
children 36eb8c21281a
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1598
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 #include <stdio.h>
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 #include <string.h>
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 #include "Exec.h"
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 #include "Func.h"
1638
aa967337bda2 fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1634
diff changeset
5 #include "SchedTask.h"
1621
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
6 #define max(a,b)((a)>(b)?a:b)
1630
d2581892b8ad fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1623
diff changeset
7
1598
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 /* これは必須 */
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 SchedDefineTask(Exec);
1630
d2581892b8ad fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1623
diff changeset
10
1621
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
11 //ボイヤームーア法による文字列検索アルゴリズム
1740
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 1739
diff changeset
12 int BM_method(unsigned char *text,int *text_length,
1662
d865530672fa fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1660
diff changeset
13 unsigned char *pattern,unsigned long long *match_string)
1621
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
14 {
1739
dfeeb2f681db fix BMsearch
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 1690
diff changeset
15 int skip[256];
1655
963d2fc5f685 push (but can't run regex_mas)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1652
diff changeset
16 int text_len = (long int)text_length;
1662
d865530672fa fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1660
diff changeset
17 int pattern_len = strlen((char *)pattern);
1623
f82467ce38f3 fix regex_mas/ppe/Exec.cc . Convert char to unsigned char.
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1621
diff changeset
18 int i = 0;
1662
d865530672fa fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1660
diff changeset
19 int match_counter = 0;
1621
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
20
1739
dfeeb2f681db fix BMsearch
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 1690
diff changeset
21 for (i = 0; i < 256; ++i){
dfeeb2f681db fix BMsearch
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 1690
diff changeset
22 skip[i] = pattern_len;
dfeeb2f681db fix BMsearch
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 1690
diff changeset
23 }
1621
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
24
1739
dfeeb2f681db fix BMsearch
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 1690
diff changeset
25 for (i = 0; i < pattern_len-1 ; ++i){
dfeeb2f681db fix BMsearch
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 1690
diff changeset
26 skip[(int)pattern[i]] = pattern_len - i - 1;
dfeeb2f681db fix BMsearch
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 1690
diff changeset
27 }
1690
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 1680
diff changeset
28
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 1680
diff changeset
29
1621
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
30
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
31 i = pattern_len - 1;
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
32
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
33 while ( i < text_len){
1623
f82467ce38f3 fix regex_mas/ppe/Exec.cc . Convert char to unsigned char.
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1621
diff changeset
34 int j = pattern_len - 1;
1621
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
35 while (text[i] == pattern[j]){
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
36 if (j == 0){
1662
d865530672fa fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1660
diff changeset
37 match_counter++;
1621
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
38 }
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
39 --i;
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
40 --j;
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
41 }
1739
dfeeb2f681db fix BMsearch
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 1690
diff changeset
42 i = i + max((int)skip[(int)text[i]],pattern_len - j);
1621
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
43 }
1662
d865530672fa fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1660
diff changeset
44 return match_counter;
1621
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
45 }
1598
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
46
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 static int
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 run(SchedTask *s, void *rbuf, void *wbuf)
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
49 {
1740
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 1739
diff changeset
50 unsigned char *i_data = (unsigned char *)s->get_input(rbuf,0);
1662
d865530672fa fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1660
diff changeset
51 unsigned long long *o_data = (unsigned long long*)wbuf;
1740
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 1739
diff changeset
52 int *length = (int*)s->get_param(0);
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 1739
diff changeset
53 //unsigned char *search_word = (unsigned char*)s->get_input(1);
1680
e44e5a18392c fix regex_mas.
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 1676
diff changeset
54 unsigned char search_word[] = "doing";
1621
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
55
1740
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 1739
diff changeset
56 o_data[0] = BM_method(i_data,length,search_word,o_data);
1662
d865530672fa fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1660
diff changeset
57
1645
4698c92bf2ca Regex_mas implement time measurement.
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1644
diff changeset
58 //s->printf("in Exec.cc\n");
1621
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
59
1598
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 return 0;
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 }