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
00043
00044
00045 #ifndef PATHDICT_HPP
00046 #define PATHDICT_HPP
00047
00048 #include "Types.hpp"
00049 #include "MemStreamer.hpp"
00050 #include "LabelDict.hpp"
00051 #include "ContMan.hpp"
00052
00053
00054 extern MemStreamer *pathdictmem;
00055
00056 class VPathExpr;
00057 class PathDict;
00058 class CompressContainerBlock;
00059 class UncompressContainerBlock;
00060
00061
00062 #define PATHDICT_HASHSIZE 512
00063 #define PATHDICT_HASHMASK 511
00064
00065
00066 class PathDictNode
00067
00068 {
00069 friend PathDict;
00070
00071 PathDictNode *parent;
00072
00073 union
00074 {
00075 TLabelID labelid;
00076
00077 VPathExpr *pathexpr;
00078 };
00079
00080
00081
00082
00083 union
00084 {
00085 CompressContainerBlock *compresscontblock;
00086 UncompressContainerBlock *uncompresscontblock;
00087 };
00088
00089
00090 PathDictNode *nextsamehash;
00091
00092 public:
00093
00094 void *operator new(size_t size)
00095 {
00096 return pathdictmem->GetByteBlock(size);
00097 }
00098
00099 CompressContainerBlock *GetCompressContainerBlock()
00100 {
00101 return compresscontblock;
00102 }
00103
00104 CompressContainerBlock *AssignCompressContainerBlock(unsigned contnum,unsigned userdatasize,VPathExpr *pathexpr)
00105
00106
00107 {
00108 compresscontblock=compresscontman.CreateNewContainerBlock(contnum,userdatasize,this,pathexpr);
00109 return compresscontblock;
00110 }
00111
00112 void PrintInfo();
00113
00114 VPathExpr *GetPathExpr() { return pathexpr;}
00115 };
00116
00117 inline unsigned long ComputePathDictHashIdx(PathDictNode *parent,TLabelID labelid)
00118
00119
00120 {
00121 return (((unsigned long)parent)+labelid)&PATHDICT_HASHMASK;
00122 }
00123
00124 inline unsigned long ComputePathDictHashIdx(VPathExpr *pathexpr)
00125
00126
00127 {
00128 return (((unsigned long)pathexpr)-1)&PATHDICT_HASHMASK;
00129 }
00130
00131
00132
00133 class PathDict
00134
00135 {
00136 PathDictNode *hashtable[PATHDICT_HASHSIZE];
00137 PathDictNode rootnode;
00138
00139 #ifdef PROFILE
00140
00141 unsigned long nodecount,lookupcount,hashitercount;
00142 #endif
00143
00144 public:
00145 void Init()
00146
00147 {
00148 int i;
00149 for(i=0;i<PATHDICT_HASHSIZE;i++)
00150 hashtable[i]=NULL;
00151 #ifdef PROFILE
00152 nodecount=0;
00153 lookupcount=0;
00154 hashitercount=0;
00155 #endif
00156 }
00157
00158 #ifdef USE_FORWARD_DATAGUIDE
00159 void ResetContBlockPtrs()
00160
00161
00162 {
00163 for(int i=0;i<PATHDICT_HASHSIZE;i++)
00164 {
00165 PathDictNode *node=hashtable[i];
00166 while(node!=NULL)
00167 {
00168 node->compresscontblock=NULL;
00169 node=node->nextsamehash;
00170 }
00171 }
00172 }
00173 #endif
00174
00175 PathDict() { Init(); }
00176
00177 PathDictNode *FindOrCreateRootPath(VPathExpr *pathexpr)
00178
00179 {
00180 unsigned long hashidx=ComputePathDictHashIdx(pathexpr);
00181 PathDictNode *node=hashtable[hashidx];
00182 #ifdef PROFILE
00183 lookupcount++;
00184 #endif
00185
00186 while(node!=NULL)
00187 {
00188 #ifdef PROFILE
00189 hashitercount++;
00190 #endif
00191 if(node->pathexpr==pathexpr)
00192 return node;
00193
00194 node=node->nextsamehash;
00195 }
00196
00197
00198 node=new PathDictNode();
00199
00200 #ifdef PROFILE
00201 nodecount++;
00202 #endif
00203
00204 node->parent=NULL;
00205 node->pathexpr=pathexpr;
00206 node->compresscontblock=NULL;
00207
00208
00209 node->nextsamehash=hashtable[hashidx];
00210 hashtable[hashidx]=node;
00211
00212 return node;
00213 }
00214
00215 PathDictNode *FindOrCreatePath(PathDictNode *parent,TLabelID labelid)
00216
00217
00218 {
00219 unsigned long hashidx=ComputePathDictHashIdx(parent,labelid);
00220 PathDictNode *node=hashtable[hashidx];
00221
00222 #ifdef PROFILE
00223 lookupcount++;
00224 #endif
00225
00226 while(node!=NULL)
00227 {
00228 #ifdef PROFILE
00229 hashitercount++;
00230 #endif
00231
00232 if((node->parent==parent)&&(node->labelid==labelid))
00233 return node;
00234
00235 node=node->nextsamehash;
00236 }
00237
00238
00239 node=new PathDictNode();
00240
00241 #ifdef PROFILE
00242 nodecount++;
00243 #endif
00244
00245 node->parent=parent;
00246 node->labelid=labelid;
00247 node->compresscontblock=NULL;
00248
00249 node->nextsamehash=hashtable[hashidx];
00250 hashtable[hashidx]=node;
00251
00252 return node;
00253 }
00254
00255 #ifdef PROFILE
00256 void PrintProfile()
00257 {
00258 printf("PathDict: nodecount=%lu lookupcount=%lu hashitercount=%lu\n",
00259 nodecount,lookupcount,hashitercount);
00260 }
00261 #endif
00262
00263
00264 };
00265
00266 extern PathDict pathdict;
00267
00268 #endif