00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042 #include "PathTree.hpp"
00043 #include "ContMan.hpp"
00044
00045 #ifdef USE_FORWARD_DATAGUIDE
00046 MemStreamer mypathtreemem(5);
00047 MemStreamer *pathtreemem=&mypathtreemem;
00048 #else
00049 MemStreamer *pathtreemem=&blockmem;
00050 #endif
00051
00052
00053
00054
00055
00056 #ifdef USE_FORWARD_DATAGUIDE
00057 inline void PathTreeNode::ComputePathDictNode(FSMManStateItem *stateitem)
00058 {
00059 PathDictNode *mypathdictnode=pathdict.FindOrCreateRootPath(stateitem->pathexpr);
00060 FSMState *curstate=stateitem->pathexpr->GetReverseFSMStartState();
00061 char overpoundedge;
00062
00063 PathTreeNode *curpathtreenode=this;
00064
00065 while((curpathtreenode->labelid!=LABEL_UNDEFINED)&&
00066 (curstate->HasPoundsAhead()))
00067
00068 {
00069 curstate=curstate->GetNextState(curpathtreenode->labelid,&overpoundedge);
00070
00071
00072
00073 if(overpoundedge)
00074 mypathdictnode=pathdict.FindOrCreatePath(mypathdictnode,curpathtreenode->labelid);
00075
00076 curpathtreenode=curpathtreenode->parent;
00077 }
00078 stateitem->pathdictnode=mypathdictnode;
00079 }
00080 #endif
00081
00082 inline void PathTreeNode::ComputeInitStateList(unsigned char *isaccepting)
00083
00084
00085 {
00086 VPathExpr *pathexpr=pathexprman.GetVPathExprs();
00087 FSMManStateItem **statelistref=&fsmstatelist;
00088
00089 *isaccepting=1;
00090
00091
00092 while(pathexpr!=NULL)
00093 {
00094 #ifdef PROFILE
00095 pathtree.fsmstatecount++;
00096 #endif
00097
00098
00099 *statelistref=new FSMManStateItem();
00100
00101 (*statelistref)->pathexpr =pathexpr;
00102
00103 #ifndef USE_FORWARD_DATAGUIDE
00104
00105 (*statelistref)->curstate =pathexpr->GetReverseFSMStartState();
00106
00107
00108 (*statelistref)->pathdictnode=pathdict.FindOrCreateRootPath(pathexpr);
00109 #else
00110 (*statelistref)->curstate =pathexpr->GetForwardFSMStartState();
00111 ComputePathDictNode(*statelistref);
00112 #endif
00113
00114
00115
00116 if((*statelistref)->curstate->IsAccepting()==0)
00117 *isaccepting=0;
00118
00119 statelistref=&((*statelistref)->next);
00120 pathexpr=pathexpr->GetNext();
00121 }
00122 *statelistref=NULL;
00123 }
00124
00125 inline void PathTreeNode::ComputeNextStateList(TLabelID labelid,unsigned char *isaccepting)
00126
00127
00128 {
00129 FSMManStateItem *newstatelist=NULL,**newstatelistref=&fsmstatelist,
00130 *newfsmstate;
00131 FSMState *nextstate;
00132 char overpoundedge;
00133
00134
00135 FSMManStateItem *prevstatelist=parent->fsmstatelist;
00136
00137 *isaccepting=1;
00138
00139
00140 while(prevstatelist!=NULL)
00141 {
00142
00143 nextstate=prevstatelist->curstate->GetNextState(labelid,&overpoundedge);
00144 if(nextstate==NULL)
00145
00146
00147 {
00148 prevstatelist=prevstatelist->next;
00149 continue;
00150 }
00151
00152 #ifdef PROFILE
00153 pathtree.fsmstatecount++;
00154 #endif
00155
00156 newfsmstate=new FSMManStateItem();
00157
00158 newfsmstate->pathexpr =prevstatelist->pathexpr;
00159 newfsmstate->curstate =nextstate;
00160
00161 #ifndef USE_FORWARD_DATAGUIDE
00162
00163
00164 newfsmstate->overpoundedge =(unsigned long)overpoundedge;
00165
00166
00167
00168 if(overpoundedge)
00169 newfsmstate->pathdictnode=pathdict.FindOrCreatePath(prevstatelist->pathdictnode,labelid);
00170 else
00171
00172 newfsmstate->pathdictnode=prevstatelist->pathdictnode;
00173 #else
00174 if(nextstate->IsFinal())
00175 ComputePathDictNode(newfsmstate);
00176 else
00177 newfsmstate->pathdictnode=NULL;
00178 #endif
00179
00180
00181
00182 if(nextstate->IsAccepting()==0)
00183 *isaccepting=0;
00184
00185 *newstatelistref=newfsmstate;
00186 newstatelistref=&(newfsmstate->next);
00187
00188 prevstatelist=prevstatelist->next;
00189 }
00190 *newstatelistref=NULL;
00191 }
00192
00193
00194
00195 void PathTree::CreateRootNode()
00196
00197 {
00198 unsigned char isaccepting;
00199
00200 rootnode.parent=NULL;
00201 rootnode.labelid=LABEL_UNDEFINED;
00202 #ifdef PROFILE
00203 nodecount=0;
00204 lookupcount=0;
00205 hashitercount=0;
00206 fsmstatecount=0;
00207 #endif
00208
00209
00210 rootnode.ComputeInitStateList(&isaccepting);
00211
00212 rootnode.isaccepting=isaccepting;
00213 }
00214
00215
00216 #define ComputePathTreeHashIdx(node,labelid) ((((unsigned long)(node))+(labelid))&PATHTREE_HASHMASK)
00217
00218 PathTreeNode *PathTree::ExtendCurPath(PathTreeNode *curnode,TLabelID labelid)
00219
00220
00221
00222
00223
00224 {
00225 unsigned char isaccepting;
00226 PathTreeNode *node;
00227
00228 #ifndef USE_NO_DATAGUIDE
00229 unsigned long hashidx=ComputePathTreeHashIdx(curnode,labelid);
00230
00231 #ifdef PROFILE
00232 lookupcount++;
00233 #endif
00234
00235
00236
00237 node=pathtreehashtable[hashidx];
00238
00239 while(node!=NULL)
00240 {
00241 #ifdef PROFILE
00242 hashitercount++;
00243 #endif
00244
00245 if((node->parent==curnode)&&
00246 (node->labelid==labelid))
00247 break;
00248 node=node->nextsamehash;
00249 }
00250
00251 if(node!=NULL)
00252
00253 return node;
00254
00255 #ifdef PROFILE
00256 nodecount++;
00257 #endif
00258
00259 #endif // USE_NO_DATAGUIDE
00260
00261
00262 node=new PathTreeNode();
00263 node->parent=curnode;
00264 node->labelid=labelid;
00265
00266
00267 node->ComputeNextStateList(labelid,&isaccepting);
00268
00269 node->isaccepting=isaccepting;
00270
00271 #ifndef USE_NO_DATAGUIDE
00272 node->nextsamehash=pathtreehashtable[hashidx];
00273 pathtreehashtable[hashidx]=node;
00274 #endif
00275
00276 return node;
00277 }
00278
00279 void PathTree::ReleaseMemory()
00280 {
00281
00282
00283
00284
00285 for(int i=0;i<PATHTREE_HASHSIZE;i++)
00286 pathtreehashtable[i]=NULL;
00287 }