source: proto/parabix2/src/tag_matcher.h @ 912

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

Delete tag_matcher.cpp

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