Mercurial > hg > Applications > Grep

comparison c/regexParser/createBitVectorList.cc @ 105:766fc2476f01 bitVec-Kaito

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix indent size
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Wed, 18 Nov 2015 19:33:07 +0900
parents 3eb3cb5d581f
children c9f5ee891b5e
comparison
equal deleted inserted replaced
104:3eb3cb5d581f 105:766fc2476f01
11 BitVectorListPtr setNextBitVectorList(NodePtr n, BitVectorListPtr bvl, BitVectorListPtr next); 11 BitVectorListPtr setNextBitVectorList(NodePtr n, BitVectorListPtr bvl, BitVectorListPtr next);
12 12
13 BitVectorListPtr initBvl; 13 BitVectorListPtr initBvl;
14 14
15 BitVectorListPtr allocateBitVectorList() { 15 BitVectorListPtr allocateBitVectorList() {
16 BitVectorListPtr bvl = (BitVectorListPtr)malloc(sizeof(BitVectorList)); 16 BitVectorListPtr bvl = (BitVectorListPtr)malloc(sizeof(BitVectorList));
17 bvl->self = bvl; 17 bvl->self = bvl;
18 bvl->bi = (BitVectorPtr)malloc(sizeof(BitVector)); 18 bvl->bi = (BitVectorPtr)malloc(sizeof(BitVector));
19 19
20 return bvl; 20 return bvl;
21 } 21 }
22 22
23 BitVectorListPtr createBitVector(NodePtr n,BitVectorListPtr bvl) { 23 BitVectorListPtr createBitVector(NodePtr n,BitVectorListPtr bvl) {
24 BitVectorListPtr nextBvl = allocateBitVectorList(); 24 BitVectorListPtr nextBvl = allocateBitVectorList();
25 nextBvl->bi = bitSet(n->nodeNumber); 25 nextBvl->bi = bitSet(n->nodeNumber);
26 nextBvl->initBvl = initBvl; 26 nextBvl->initBvl = initBvl;
27 return nextBvl; 27 return nextBvl;
28 } 28 }
29 29
30 30
31 BitVectorListPtr initBitVector() { 31 BitVectorListPtr initBitVector() {
32
33 BitVectorListPtr bvl = allocateBitVectorList();
34 bvl->initBvl = initBvl = bvl;
35 bvl->bi = bitSet(0);
36 32
37 for (int i = 0; i < 256; i++) { 33 BitVectorListPtr bvl = allocateBitVectorList();
38 bvl->next[i] = NULL; 34 bvl->initBvl = initBvl = bvl;
39 } 35 bvl->bi = bitSet(0);
40 36
41 return bvl; 37 for (int i = 0; i < 256; i++) {
38 bvl->next[i] = NULL;
39 }
40
41 return bvl;
42 } 42 }
43 43
44 void printBitVectorList (BitVectorListPtr bvl) { 44 void printBitVectorList (BitVectorListPtr bvl) {
45 bool isFirstPrint = true; 45 bool isFirstPrint = true;
46 for (int i = 0; i < 256; i++) { 46 for (int i = 0; i < 256; i++) {
47 if (bvl->next[i] != NULL) { 47 if (bvl->next[i] != NULL) {
48 if (isFirstPrint){ 48 if (isFirstPrint){
49 puts("----"); 49 puts("----");
50 printf(" state : "); bitPrint(bvl->bi); 50 printf(" state : "); bitPrint(bvl->bi);
51 isFirstPrint = false; 51 isFirstPrint = false;
52 } 52 }
53 printf("input char : %c\n",i); 53 printf("input char : %c\n",i);
54 printf("next state : ");bitPrint(bvl->next[i]->bi); 54 printf("next state : ");bitPrint(bvl->next[i]->bi);
55 }
55 } 56 }
56 } 57
57 58 for (int i = 0; i < 256; i++) {
58 for (int i = 0; i < 256; i++) { 59 if (bvl->next[i] != NULL) {
59 if (bvl->next[i] != NULL) { 60 printBitVectorList(bvl->next[i]);
60 printBitVectorList(bvl->next[i]); 61 }
61 } 62 }
62 }
63 } 63 }
64 64
65 BitVectorListPtr descendTreeNode(NodePtr n,BitVectorListPtr bvl, BitVectorListPtr prev, bool &fromOr) { 65 BitVectorListPtr descendTreeNode(NodePtr n,BitVectorListPtr bvl, BitVectorListPtr prev, bool &fromOr) {
66 bool leftIsOr, rightIsOr; 66 bool leftIsOr, rightIsOr;
67 if (n->tokenType == '*') { 67 if (n->tokenType == '*') {
68
69 } else if (n->Value.character == '|') {
70 bvl = descendTreeNode(n->left, bvl, prev, leftIsOr);
71 setNextBitVectorList(n->left, prev, bvl);
72 bvl = descendTreeNode(n->right, bvl, prev, rightIsOr);
73 setNextBitVectorList(n->right, prev, bvl);
74 fromOr = true;
75 return prev;
76 } else if (n->Value.character == '+') {
77 bvl = descendTreeNode(n->left, bvl, prev, leftIsOr);
78 setNextBitVectorList(n->left, prev, bvl);
79 prev = bvl;
80 bvl = descendTreeNode(n->right, bvl, prev, rightIsOr);
81 68
82 if (leftIsOr){ 69 } else if (n->Value.character == '|') {
83 for (int i = 0; i < 256; i++) 70 bvl = descendTreeNode(n->left, bvl, prev, leftIsOr);
84 if (prev->next[i] != NULL) 71 setNextBitVectorList(n->left, prev, bvl);
85 setNextBitVectorList(n->right, prev->next[i], bvl); 72 bvl = descendTreeNode(n->right, bvl, prev, rightIsOr);
73 setNextBitVectorList(n->right, prev, bvl);
74 fromOr = true;
75 return prev;
76 } else if (n->Value.character == '+') {
77 bvl = descendTreeNode(n->left, bvl, prev, leftIsOr);
78 setNextBitVectorList(n->left, prev, bvl);
79 prev = bvl;
80 bvl = descendTreeNode(n->right, bvl, prev, rightIsOr);
81
82 if (leftIsOr){
83 for (int i = 0; i < 256; i++)
84 if (prev->next[i] != NULL)
85 setNextBitVectorList(n->right, prev->next[i], bvl);
86 }
87 else {
88 setNextBitVectorList(n->right, prev, bvl);
89 }
90
91 fromOr = false;
92 } else if (n->tokenType == 'a') {
93 bvl = createBitVector(n,bvl);
94 fromOr = false;
86 } 95 }
87 else { 96 return bvl;
88 setNextBitVectorList(n->right, prev, bvl);
89 }
90
91 fromOr = false;
92 } else if (n->tokenType == 'a') {
93 bvl = createBitVector(n,bvl);
94 fromOr = false;
95 }
96 return bvl;
97 } 97 }
98 98
99 BitVectorListPtr setNextBitVectorList(NodePtr n, BitVectorListPtr bvl, BitVectorListPtr next){ 99 BitVectorListPtr setNextBitVectorList(NodePtr n, BitVectorListPtr bvl, BitVectorListPtr next){
100 if (isalnum((int)n->Value.character)){ 100 if (isalnum((int)n->Value.character)){
101 bvl->next[(int)n->Value.character] = next; 101 bvl->next[(int)n->Value.character] = next;
102 } 102 }
103 return next; 103 return next;
104 } 104 }
105 105
106 BitVectorListPtr createBitVectorList(NodePtr n) { 106 BitVectorListPtr createBitVectorList(NodePtr n) {
107 BitVectorListPtr bvl = initBitVector(); 107 BitVectorListPtr bvl = initBitVector();
108 bool fromOr = false; 108 bool fromOr = false;
109 descendTreeNode(n, bvl, bvl, fromOr); 109 descendTreeNode(n, bvl, bvl, fromOr);
110 printBitVectorList(bvl); 110 printBitVectorList(bvl);
111 return bvl; 111 return bvl;
112 } 112 }