source: proto/parabix2/src/tag_matcher.cpp @ 582

Last change on this file since 582 was 582, checked in by lindanl, 9 years ago

Add attributes uniqueness checking

File size: 6.1 KB
Line 
1#define MAX_DEPTH 100
2#include <algorithm>
3#include <iostream>
4using namespace std;
5
6#define MAX_DEPTH 100
7#define MAX_ATTS 100
8
9struct attribute{
10  char * start;
11  int lgth;
12};
13
14class tag_matcher {
15  public:
16  SIMD_type tagMarks[BUFFER_SIZE/BLOCK_SIZE];
17  char tags_buf[BUFFER_SIZE];
18  int tags_buf_cur;
19  int stream_index;
20  char * srcbuf;
21  int depth;
22  int inTagPos;
23  int finalStartPos;
24  char* tag_stack[MAX_DEPTH]; 
25  int tag_lgth_stack[MAX_DEPTH];
26  SIMD_type NameFollows[BUFFER_SIZE/BLOCK_SIZE+1]; // 1 extra block for sentinel
27  int buf_base;
28  enum TagMatchState {InStartTag, InEndTag, InAttName, Clear} state;
29  struct attribute Attr[MAX_ATTS];
30  struct attribute InAtt;
31  int att_index;
32   
33  tag_matcher(char * src);
34  ~tag_matcher(); 
35  int StreamScan(int chars_avail);
36  void store_streams(SIMD_type tagMark, SIMD_type NameFollow);
37  int tag_match(int pos);
38  void Advance_buffer();
39  int does_match(char * s1, char * s2, int lgth);
40  int lookup_or_insert(char*s, int lgth);
41};
42
43int tag_matcher::lookup_or_insert(char* s, int lgth){
44  for(int i=0; i< att_index; i++)
45    if(lgth == Attr[i].lgth &&  does_match(s,Attr[i].start,lgth))
46      return 1;
47 
48  Attr[att_index].start = s;
49  Attr[att_index].lgth = lgth;
50  att_index++;
51  return 0;
52}
53
54int tag_matcher::does_match(char * s1, char * s2, int lgth){
55    int matchlen = 0; 
56    int i=0;
57    while (lgth > sizeof(SIMD_type)) {
58      /* full 16 byte match */
59      if (simd_all_eq_8(sisd_load_unaligned((SIMD_type*)&s1[i]), sisd_load_unaligned((SIMD_type*)&s2[i]))) {
60        lgth -= sizeof(SIMD_type);
61        i +=sizeof(SIMD_type);
62      }
63      else {
64        return 0;
65      }
66    }
67    if (lgth > cfzl(~_mm_movemask_epi8(simd_eq_8(sisd_load_unaligned((SIMD_type*)&s1[i]), 
68                                                  sisd_load_unaligned((SIMD_type*)&s2[i])))))
69      return 0;
70    else return 1;
71}
72
73
74int tag_matcher:: tag_match(int pos) {
75//      end tag
76        if(srcbuf[pos]=='/' ){
77          pos++;
78          depth--;
79          if (depth<0)
80            return pos;
81          int lgth = tag_lgth_stack[depth];
82
83          if (does_match(tag_stack[depth],&srcbuf[pos],lgth) && ((srcbuf[pos+lgth] == '>') ||(srcbuf[pos+lgth] <= ' '))) return 0;
84          else if (pos + lgth >= BUFFER_SIZE + OVERLAP_BUFSIZE) {
85            state = InEndTag;
86            inTagPos = BUFFER_SIZE - pos;
87          }
88          else {
89//            cout << "matchlen = " << matchlen << endl;
90//            cout << "end tag is " << string(&srcbuf[pos],tag_lgth_stack[depth]) << endl ;
91//            cout << "start tag is " << string(tag_stack[depth],tag_lgth_stack[depth]) << endl ;
92              fprintf(stderr,"tag name mismatch at position = %i\n",buf_base+pos);
93              exit(-1);
94          }
95        }
96//      empty tag
97        else if(srcbuf[pos]=='>'){
98          depth--;
99        }
100//      start tag
101        else if(srcbuf[pos-1]=='<'){
102          att_index = 0;
103          if(depth<MAX_DEPTH){
104            int end_pos = bitstream_scan(NameFollows,pos);
105            tag_lgth_stack[depth] = end_pos-pos;
106            tag_stack[depth] = &srcbuf[pos];
107            if(end_pos<BUFFER_SIZE){
108              depth++;
109            }
110            else{
111              state = InStartTag;
112              finalStartPos = pos;
113            }
114          }
115          else{
116            fprintf(stderr,"Max nesting depth exceeded at position =%i. depth = %i\n",buf_base+pos, depth);
117            exit(-1);
118          }
119        }
120//      attribute
121        else{
122          int end_pos = bitstream_scan(NameFollows,pos);
123          if(end_pos<BUFFER_SIZE){
124            if(lookup_or_insert(&srcbuf[pos], end_pos-pos)){
125              fprintf(stderr,"Attribute name is not unique at position =%i.\n",buf_base+pos);
126              exit(-1);
127            }
128          }
129          else{
130            state = InAttName;     
131            InAtt.start = &srcbuf[pos];
132            InAtt.lgth = BUFFER_SIZE-pos;
133          }
134        }
135        return 0;
136}
137
138
139int tag_matcher::StreamScan(int chars_avail) {
140 
141        int blk;
142        int blk_counts = (chars_avail+sizeof(ScanBlock)*8-1)/(sizeof(ScanBlock)*8);
143        int block_pos = 0;
144       
145        for (blk = 0; blk < blk_counts; blk++) {
146                ScanBlock s = ((ScanBlock*)tagMarks)[blk];
147                while(s) {
148                        int code = (tag_match(cfzl(s) + block_pos));
149                        if (code) return code;
150                        s = s & (s-1);  // clear rightmost bit.
151                }
152                block_pos += 8 * sizeof(ScanBlock);
153        }
154
155        return 0;
156} 
157
158void tag_matcher::store_streams(SIMD_type tagMark, SIMD_type NameFollow){
159  tagMarks[stream_index] = tagMark;
160  NameFollows[stream_index] = NameFollow;
161  stream_index++; 
162  if(stream_index==1){
163    if(state == InStartTag) {
164      state = Clear;
165      int remain_lgth = bitstream_scan(NameFollows,0);
166      memcpy(&tags_buf[tags_buf_cur],srcbuf,remain_lgth);
167//       tags_buf_cur += remain_lgth;
168      tag_lgth_stack[depth] += remain_lgth;
169      depth++;
170    }
171    else if (state == InEndTag) {
172      state = Clear;
173      int lgth = tag_lgth_stack[depth];
174      if (does_match(tag_stack[depth]+inTagPos,srcbuf,lgth-inTagPos) && ((srcbuf[lgth] == '>') ||(srcbuf[lgth] <= ' '))) return ;       
175      else {
176          fprintf(stderr,"tag name mismatch at position = %i\n",buf_base);
177          exit(-1);
178      }     
179    }
180    else if (state == InAttName) {
181      state = Clear;
182      int remain_lgth = bitstream_scan(NameFollows,0);
183      memcpy(&tags_buf[tags_buf_cur],srcbuf,remain_lgth);
184//       tags_buf_cur += remain_lgth;       
185      if(lookup_or_insert(InAtt.start, InAtt.lgth+remain_lgth)){
186              fprintf(stderr,"Attribute name is not unique at position =%i.\n",buf_base);
187              exit(-1);
188      } 
189    }
190  } 
191}
192
193tag_matcher::tag_matcher(char * src){
194  stream_index = 0;
195  depth = 0;
196  srcbuf = src;
197  buf_base = 0;
198  state = Clear;
199  NameFollows[BUFFER_SIZE/BLOCK_SIZE]=simd_const_1(1);  //sentinel
200}
201
202tag_matcher::~tag_matcher(){
203 
204}
205
206void tag_matcher::Advance_buffer(){
207  buf_base += BUFFER_SIZE;
208  stream_index=0;
209  tags_buf_cur = 0;
210  att_index = 0;
211  for(int i=0; i< depth; i++){
212    if(&tags_buf[tags_buf_cur]!=tag_stack[i])
213      memcpy(&tags_buf[tags_buf_cur],tag_stack[i],tag_lgth_stack[i]);         
214    tag_stack[i] = &tags_buf[tags_buf_cur];
215    tags_buf_cur += tag_lgth_stack[i];
216  }
217  if(state == InStartTag) {
218      memcpy(&tags_buf[tags_buf_cur],&srcbuf[finalStartPos],tag_lgth_stack[depth]);           
219      tag_stack[depth] = &tags_buf[tags_buf_cur];
220      tags_buf_cur += tag_lgth_stack[depth];
221  }
222  if(state == InAttName) {
223      memcpy(&tags_buf[tags_buf_cur],InAtt.start,InAtt.lgth);
224      InAtt.start = &tags_buf[tags_buf_cur];
225      tags_buf_cur += InAtt.lgth;
226  }
227  srcbuf[-1] = srcbuf[BUFFER_SIZE-1];
228}
229
Note: See TracBrowser for help on using the repository browser.