source: proto/parabix2/src/TagMatcher_multithreads.h @ 1055

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

multithreads

File size: 8.2 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 TagMatcher {
15  public:
16  SIMD_type tagMarks[SEGMENT_SIZE/BLOCK_SIZE];
17  SIMD_type miscMarks[SEGMENT_SIZE/BLOCK_SIZE];
18  char tags_buf[SEGMENT_SIZE];
19  int tags_buf_cur;
20  int stream_index;
21  char * srcbuf;
22  int depth;
23  int inTagPos;
24  int finalStartPos;
25  char* tag_stack[MAX_DEPTH];
26  int tag_lgth_stack[MAX_DEPTH];
27  SIMD_type NameFollows[SEGMENT_SIZE/BLOCK_SIZE+1]; // 1 extra block for sentinel
28  int buf_base;
29  enum TagMatchState {InStartTag, InEndTag, InAttName, Clear} state;
30  enum TagMatchMode {StartOfFile, InFile} mode;
31  struct attribute Attr[MAX_ATTS];
32  struct attribute InAtt;
33  int att_index;
34  int InFinalEndTag;
35
36  TagMatcher();
37  ~TagMatcher();
38  void setSrc(char * src);
39  int StreamScan(int chars_avail);
40  void store_streams(SIMD_type tagMark, SIMD_type NameFollow, SIMD_type miscMarks, int chars_avail);
41  int tag_match(int pos, int chars_avail);
42  void Advance_segment();
43  int does_match(char * s1, char * s2, int lgth);
44  int lookup_or_insert(char*s, int lgth);
45};
46
47int TagMatcher::lookup_or_insert(char* s, int lgth){
48  for(int i=0; i< att_index; i++)
49    if(lgth == Attr[i].lgth &&  does_match(s,Attr[i].start,lgth))
50      return 1;
51
52  Attr[att_index].start = s;
53  Attr[att_index].lgth = lgth;
54  att_index++;
55  return 0;
56}
57
58int TagMatcher::does_match(char * s1, char * s2, int lgth){
59    int matchlen = 0;
60    int i=0;
61    while (lgth > sizeof(SIMD_type)) {
62      /* full 16 byte match */
63      if (simd_all_eq_8(sisd_load_unaligned((SIMD_type*)&s1[i]), sisd_load_unaligned((SIMD_type*)&s2[i]))) {
64                lgth -= sizeof(SIMD_type);
65                i +=sizeof(SIMD_type);
66      }
67      else {
68                return 0;
69      }
70    }
71    if (lgth > cfzl(~_mm_movemask_epi8(simd_eq_8(sisd_load_unaligned((SIMD_type*)&s1[i]),
72                                                  sisd_load_unaligned((SIMD_type*)&s2[i])))))
73      return 0;
74    else return 1;
75}
76
77
78int TagMatcher:: tag_match(int pos, int chars_avail) {
79        int rt_val=0;
80//      end tag
81        if(srcbuf[pos]=='/' ){
82          pos++;
83          depth--;
84          if (depth<0)
85            return pos;
86          int lgth = tag_lgth_stack[depth];
87
88//        printf("pos = %i, lgth = %i, depth = %i\n",pos,lgth,depth);
89//        cout << "end tag is " << string(&srcbuf[pos],tag_lgth_stack[depth]) << endl ;
90
91          if (does_match(tag_stack[depth],&srcbuf[pos],lgth) && ((srcbuf[pos+lgth] == '>') ||(srcbuf[pos+lgth] <= ' '))) rt_val=0;
92          else if (pos + lgth >= SEGMENT_SIZE) {
93            state = InEndTag;
94            inTagPos = SEGMENT_SIZE - pos;
95            rt_val=0;
96          }
97          else {
98
99              fprintf(stderr,"tag name mismatch at position = %i\n",buf_base+pos);
100              exit(-1);
101          }
102
103          if (depth == 0){
104            while(srcbuf[pos]!='>'){
105              pos++;
106              if(pos>=chars_avail){
107                        InFinalEndTag = 1;
108                        return 0;
109              }
110            }
111            pos = bitstream_scan(miscMarks,pos+1);
112            if(pos!=chars_avail){
113              fprintf(stderr,"illegal content after root element at position = %i\n",buf_base+pos);
114              exit(-1);
115            }
116          }
117          return rt_val;
118        }
119//      empty tag
120        else if(srcbuf[pos]=='>'){
121          depth--;
122          if (depth == 0){
123            while(srcbuf[pos]!='>')
124              pos++;
125            pos = bitstream_scan(miscMarks,pos+1);
126
127            if(pos!=chars_avail){
128              fprintf(stderr,"illegal content after root element at position = %i\n",buf_base+pos);
129              exit(-1);
130            }
131          }
132        }
133//      start tag
134        else if(srcbuf[pos-1]=='<'){
135          att_index = 0;
136
137          if(depth<MAX_DEPTH){
138            int end_pos = bitstream_scan(NameFollows,pos);
139            tag_lgth_stack[depth] = end_pos-pos;
140            tag_stack[depth] = &srcbuf[pos];
141
142//              cout << "start tag is " << string(tag_stack[depth],tag_lgth_stack[depth]) << endl ;
143            if(end_pos<SEGMENT_SIZE){
144              depth++;
145            }
146            else{
147              state = InStartTag;
148              finalStartPos = pos;
149            }
150          }
151          else{
152            fprintf(stderr,"Max nesting depth exceeded at position =%i. depth = %i\n",buf_base+pos, depth);
153            exit(-1);
154          }
155        }
156//      attribute
157        else{
158          int end_pos = bitstream_scan(NameFollows,pos);
159          if(end_pos<SEGMENT_SIZE){
160            if(lookup_or_insert(&srcbuf[pos], end_pos-pos)){
161              fprintf(stderr,"Attribute name is not unique at position =%i.\n",buf_base+pos);
162              exit(-1);
163            }
164          }
165          else{
166            state = InAttName;
167            InAtt.start = &srcbuf[pos];
168            InAtt.lgth = SEGMENT_SIZE-pos;
169          }
170        }
171        return 0;
172}
173
174
175int TagMatcher::StreamScan(int chars_avail) {
176
177        int blk;
178        int blk_counts = (chars_avail+sizeof(ScanBlock)*8-1)/(sizeof(ScanBlock)*8);
179        int block_pos = 0;
180
181        if(mode == StartOfFile){
182          int pos = bitstream_scan(miscMarks,0);
183          if (pos==chars_avail){
184            fprintf(stderr,"no element at position =%i.\n",buf_base+pos);
185            exit(-1);
186          }
187          if(srcbuf[pos-1]!='<'|| srcbuf[pos]=='!'||srcbuf[pos]=='/'){
188#ifdef DUMP
189print_bit_block("srcbuf", sisd_load_unaligned((BitBlock *) srcbuf));
190#endif
191            fprintf(stderr,"illegal content before root element at position =%i.\n",buf_base+pos);
192            exit(-1);
193          }
194          mode = InFile;
195        }
196        for (blk = 0; blk < blk_counts; blk++) {
197                ScanBlock s = ((ScanBlock*)tagMarks)[blk];
198                while(s) {
199                        int code = tag_match(cfzl(s) + block_pos, chars_avail);
200                        if (code) return code;
201                        s = s & (s-1);  // clear rightmost bit.
202                }
203                block_pos += 8 * sizeof(ScanBlock);
204        }
205
206        return 0;
207}
208
209void TagMatcher::store_streams(SIMD_type tagMark, SIMD_type NameFollow, SIMD_type miscMark, int chars_avail){
210#ifdef DUMP
211print_bit_block("tagMark", tagMark);
212print_bit_block("NameFollow", NameFollow);
213print_bit_block("miscMark", miscMark);
214printf("chars_avail = %i\n", chars_avail);
215printf("stream_index = %i\n", stream_index);
216#endif
217  tagMarks[stream_index] = tagMark;
218  miscMarks[stream_index] = simd_not(miscMark);
219  NameFollows[stream_index] = NameFollow;
220  stream_index++;
221  if(stream_index==1){
222
223    if (InFinalEndTag == 1){
224      int pos = -1;
225      while(srcbuf[pos]!='>'){
226                pos++;
227                if(pos>=chars_avail){
228                  InFinalEndTag = 1;
229                  return;
230                }
231      }
232      pos = bitstream_scan(miscMarks,pos+1);
233#ifdef DUMP
234print_bit_block("miscMarks[0]", miscMarks[0]);
235printf("pos = %i\n", pos);
236#endif
237      if(pos!=chars_avail){
238        fprintf(stderr,"illegal content after root element at position = %i\n",buf_base+pos);
239        exit(-1);
240      }
241    }
242
243    if(state == InStartTag) {
244      state = Clear;
245      int remain_lgth = bitstream_scan(NameFollows,0);
246      memcpy(&tags_buf[tags_buf_cur],srcbuf,remain_lgth);
247      tag_lgth_stack[depth] += remain_lgth;
248      depth++;
249    }
250    else if (state == InEndTag) {
251      state = Clear;
252      int lgth = tag_lgth_stack[depth];
253      if (does_match(tag_stack[depth]+inTagPos,srcbuf,lgth-inTagPos) && ((srcbuf[lgth-inTagPos] == '>') ||(srcbuf[lgth-inTagPos] <= ' '))) return ;
254      else {
255          fprintf(stderr,"tag name mismatch at position = %i\n",buf_base);
256          exit(-1);
257      }
258    }
259    else if (state == InAttName) {
260      state = Clear;
261      int remain_lgth = bitstream_scan(NameFollows,0);
262      memcpy(&tags_buf[tags_buf_cur],srcbuf,remain_lgth);
263      if(lookup_or_insert(InAtt.start, InAtt.lgth+remain_lgth)){
264              fprintf(stderr,"Attribute name is not unique at position =%i.\n",buf_base);
265              exit(-1);
266      }
267    }
268  }
269}
270
271TagMatcher::TagMatcher(){
272  stream_index = 0;
273  depth = 0;
274  buf_base = 0;
275  state = Clear;
276  mode = StartOfFile;
277  InFinalEndTag = 0;
278  NameFollows[SEGMENT_SIZE/BLOCK_SIZE]=simd_const_1(1);  //sentinel
279}
280
281TagMatcher::~TagMatcher(){
282
283}
284
285void TagMatcher::setSrc(char * src){
286  srcbuf = src;
287}
288
289void TagMatcher::Advance_segment(){
290  buf_base += SEGMENT_SIZE;
291  stream_index=0;
292  tags_buf_cur = 0;
293  att_index = 0;
294  for(int i=0; i< depth; i++){
295    if(&tags_buf[tags_buf_cur]!=tag_stack[i])
296      memcpy(&tags_buf[tags_buf_cur],tag_stack[i],tag_lgth_stack[i]);
297    tag_stack[i] = &tags_buf[tags_buf_cur];
298    tags_buf_cur += tag_lgth_stack[i];
299  }
300  if(state == InStartTag) {
301      memcpy(&tags_buf[tags_buf_cur],&srcbuf[finalStartPos],tag_lgth_stack[depth]);
302      tag_stack[depth] = &tags_buf[tags_buf_cur];
303      tags_buf_cur += tag_lgth_stack[depth];
304  }
305  else if(state == InEndTag) {
306     memcpy(&tags_buf[tags_buf_cur],tag_stack[depth],tag_lgth_stack[depth]);
307    tag_stack[depth] = &tags_buf[tags_buf_cur];
308    tags_buf_cur += tag_lgth_stack[depth];
309  }
310  else if(state == InAttName) {
311      memcpy(&tags_buf[tags_buf_cur],InAtt.start,InAtt.lgth);
312      InAtt.start = &tags_buf[tags_buf_cur];
313      tags_buf_cur += InAtt.lgth;
314  }
315}
316
Note: See TracBrowser for help on using the repository browser.