2 * CDE - Common Desktop Environment
4 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
6 * These libraries and programs are free software; you can
7 * redistribute them and/or modify them under the terms of the GNU
8 * Lesser General Public License as published by the Free Software
9 * Foundation; either version 2 of the License, or (at your option)
12 * These libraries and programs are distributed in the hope that
13 * they will be useful, but WITHOUT ANY WARRANTY; without even the
14 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15 * PURPOSE. See the GNU Lesser General Public License for more
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with these librararies and programs; if not, write
20 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
21 * Floor, Boston, MA 02110-1301 USA
23 // $XConsortium: PathTable.cc /main/4 1996/06/11 17:07:57 cde-hal $
24 #include "PathTable.h"
27 #include "utility/debug.h"
29 extern SymbolTable* gElemSymTab;
31 unsigned int letterHash(const LetterType& x)
36 EncodedPath::~EncodedPath()
39 f_SVectors.clearAndDestroy();
43 EncodedPath::EncodedPath(SSPath* p, unsigned int asPattern) :
44 f_size(p -> entries()), f_patternSize(0), f_SVectors(letterHash),
45 f_wildCard(gElemSymTab -> wildCardId()),
46 f_unlimitedWildCard(gElemSymTab -> unlimitedWildCardId()),
47 f_copyOfS(new BitVector(WORD_SIZE, 0))
50 f_array = new LetterType[f_size];
52 CC_TPtrDlistIterator<PathTerm> l_pathIter(*p);
58 while (++l_pathIter) {
61 // Count pattern size, excluding "*".
63 f_array[i] = (LetterType)((l_pathIter.key() -> symbol()).id());
64 if ( f_array[i] != f_unlimitedWildCard )
69 if ( asPattern == true ) {
72 // Compute the S arrays.
73 // Examples pat = a b a c
89 int j = patternLength()-1;
93 // i records each PathTerm position in the list
96 while (++l_pathIter) {
97 l_id = (LetterType)((l_pathIter.key() -> symbol()).id());
99 l_bv = f_SVectors.findValue(&l_id);
101 l_bv = new BitVector(patternLength(), 0);
102 f_SVectors.insertKeyAndValue(new LetterType(l_id), l_bv);
106 ///////////////////////////////////////////////////
107 // reverse the order in the bit vector:
108 // MSB position ==> set LSB bit in the bit vector
109 ///////////////////////////////////////////////////
110 if ( l_id != f_unlimitedWildCard ) {
111 l_bv -> setBitTo(j, 1);
113 //////////////////////////////////////////////////
114 // only set position when an expr is attatched
116 //////////////////////////////////////////////////
117 if ( l_pathIter.key() -> pqexpr() && l_id != f_wildCard ) {
119 MESSAGE(cerr, "==========");
120 debug(cerr, (void*)l_bv);
125 l_bv -> recordPositions(i, j);
132 ///////////////////////////////////////////////////
133 // do not set bits for unlimitedWildCards that
134 // begin or end the pattern
135 ///////////////////////////////////////////////////
136 if ( j < patternLength() - 1 )
137 l_bv -> setBitTo(j+1, 1);
143 ///////////////////////////////////////////////////
144 // special treatment to the ? symbols:
145 // OR S(?) back to each S's.
146 ///////////////////////////////////////////////////
147 BitVector* l_BitVectorWildCard = f_SVectors.findValue(&f_wildCard);
148 hashTableIterator<LetterType, BitVector> l_SVIter(f_SVectors);
150 if ( l_BitVectorWildCard ) {
152 if ( *l_SVIter.key() != f_wildCard &&
153 *l_SVIter.key() != f_unlimitedWildCard
156 (*l_SVIter.value()) |= (*l_BitVectorWildCard);
164 debug(cerr, (*l_SVIter.key()));
165 debug(cerr, (*l_SVIter.value()));
175 _match(LetterType* pattern, int n,
176 LetterType* text, int m,
178 LetterType unlimitedWildCard
181 // A naive (brute force) string matching algorithm that handles
182 // wild card (?) and unlimited wild card (*) symbols.
183 unsigned int findMisMatch = false;
185 for ( int i=0; i<n; i++ ) { // over the "text" string
187 for ( int j=0; j<m; j++ ) { // over the pattern
188 if ( pattern[j] == wildCard ) {
191 if ( pattern[j] == unlimitedWildCard ) {
200 if ( pattern[j] != unlimitedWildCard )
204 for ( int x=i+1; x<n; x++ ) {
205 if ( text[x] == pattern[j] )
210 wildCard, unlimitedWildCard
218 if ( pattern[j] != text[i] ) {
224 if ( findMisMatch == false )
232 EncodedPath::match(EncodedPath& text, SSPath* patternPath, SSPath* elementPath)
234 ////////////////////////////////////////////////
235 // text: the encoded string for the element path
236 // elementPath: the element path
238 // this: the encoded string for the pattern string
239 // patternPath: the pattern path
240 ////////////////////////////////////////////////
243 ////////////////////////////////////////////////
244 // the unlimited wildcard vector
245 ////////////////////////////////////////////////
246 BitVector* l_U = f_SVectors.findValue(&f_unlimitedWildCard);
248 if ( l_U && patternLength() == 0 )
251 ////////////////////////////////////////////////
252 // the wildcard vector
253 ////////////////////////////////////////////////
254 BitVector* l_W = f_SVectors.findValue(&f_wildCard);
256 // the S vector of each Letter, including that for '?'
259 // the accumulated result vector
260 BitVector l_R(patternLength(), 0);
262 // placeholder for '*''s contribution
263 BitVector l_I(patternLength(), 0);
265 // hole position record of each path term in the pattern path
268 // expr pointer of each path term in the pattern path
271 CC_TPtrDlistIterator<PathTerm>* elementPathNextPtr = 0;
274 elementPathNextPtr = new CC_TPtrDlistIterator<PathTerm>(*elementPath);
276 // loop over text string
277 for ( int i=0; i<text.length(); i++) {
280 ++(*elementPathNextPtr);
282 //MESSAGE(cerr, "===================");
283 //debug(cerr, text.f_array[i]);
285 ////////////////////////////////////////////////
286 // get this character's vector, including '?'s
287 ////////////////////////////////////////////////
288 l_S = f_SVectors.findValue(&text.f_array[i]);
291 //debug(cerr, (void*)l_S);
293 //MESSAGE(cerr, "checking qualifies");
294 //////////////////////
296 //////////////////////
297 if ( patternPath && l_S -> positionArray() ) {
302 f_copyOfS -> setTo(*l_S);
304 //debug(cerr, *patternPath);
306 positionArrayIteratorT l_positionNext(*(l_S -> positionArray()));
307 while (++ l_positionNext) {
309 l_pr = l_positionNext.key();
311 //cerr << " calling patternPath -> fastGetAt(): " << (void*)patternPath << "l_pr.pathTermPos= " << l_pr.pathTermPos << endl;
313 expr = patternPath -> fastGetAt(l_pr.pathTermPos) -> pqexpr();
315 debug(cerr, int(expr));
317 MESSAGE(cerr, "qualify checking is needed.");
318 debug(cerr, *(elementPathNext -> key()));
323 expr->evaluate(elementPathNextPtr->key()->element()) == PQFalse )
325 //MESSAGE(cerr, form("set position %d to 0", l_pr.bitPos));
326 f_copyOfS -> setBitTo(l_pr.bitPos, 0);
329 /////////////////////////////////////////
330 // make l_S point at its modified copy
331 /////////////////////////////////////////
337 ////////////////////////////////////////////////
338 // get unlimited wildcard's vector.
339 ////////////////////////////////////////////////
343 //MESSAGE(cerr, "l_I");
348 ////////////////////////////////////////////////
349 // shift the partial result vector right once
350 ////////////////////////////////////////////////
351 l_R.shiftRightOneBit();
352 //MESSAGE(cerr, "after l_R >> 1");
355 ////////////////////////////////////////////////
356 // AND in this character's vector
357 ////////////////////////////////////////////////
361 //MESSAGE(cerr, "after AND with l_S");
364 ///////////////////////////////////////////////
365 // this branch is impossible to reach.
366 ///////////////////////////////////////////////
367 //MESSAGE(cerr, "l_R set all bits to 0");
372 ///////////////////////////////////////////////
373 // OR in unlimited wild char's vector.
374 ///////////////////////////////////////////////
377 //MESSAGE(cerr, "after OR with l_I");
381 //MESSAGE(cerr, "===================");
383 ///////////////////////////////////////////////
384 // Use this test to get the first matched position
385 // if ( l_R.getBit(0) == 1 )
387 ///////////////////////////////////////////////
390 delete elementPathNextPtr;
392 ///////////////////////////////////////////////
394 // the last symbol must match
396 ///////////////////////////////////////////////
397 if ( l_R.getBit(0) == 1 )
404 basePathFeature::~basePathFeature()
410 PathFeature::~PathFeature()
412 delete f_encodedPath ;
415 unsigned int basePathFeature::operator==(const basePathFeature& pf) const
417 cerr << "Warning: basePathFeature::operator==() called\n";
421 unsigned int PathFeature::operator==(const PathFeature& pf) const
423 cerr << "Warning: PathFeature::operator==() called\n";
427 void pathSelector(BitVector& bv)
432 PathFeature::match(SSPath& p)
434 EncodedPath l_ep(&p);
436 if ( f_path -> containSelector() == false )
437 return f_encodedPath -> match(l_ep, 0, 0);
439 return f_encodedPath -> match(l_ep, f_path, &p);
443 // /////////////////////////////////////////////////////////////////////////
447 // /////////////////////////////////////////////////////////////////////////
450 unsigned symHashFunc(const Symbol& s)
455 PathTable::PathTable()
457 f_lastSymIndexCount(0)
461 PathTable::~PathTable()
463 f_pathFeatureList.clearAndDestroy();
464 for (unsigned int i = 0 ; i < f_lastSymIndexCount; i++) {
465 //f_lastSymIndex[i].clearAndDestroy();
466 f_lastSymIndex[i] -> clear();
467 delete f_lastSymIndex[i];
469 delete f_lastSymIndex;
472 LetterType PathTable::findIndex(SSPath& p)
474 return (LetterType) ((p.last() -> symbol()).id());
477 void PathTable::initLastSymIndex()
479 f_lastSymIndexCount = gElemSymTab -> IdsAssigned()+1;
480 f_lastSymIndex = new CC_TPtrDlist_PathFeature_Ptr_T[f_lastSymIndexCount];
481 for (unsigned int i=0; i<f_lastSymIndexCount; i++)
482 f_lastSymIndex[i] = new CC_TPtrDlist<PathFeature>;
485 CC_TPtrDlistIterator<PathFeature> l_pfIter(f_pathFeatureList);
486 PathFeature* l_pathFeature = 0;
490 while ( ++l_pfIter ) {
491 l_pathFeature = l_pfIter.key();
492 x = findIndex( *(l_pathFeature->path()) );
493 //f_lastSymIndex[x] -> prepend(l_pathFeature); // backward order
494 f_lastSymIndex[x] -> append(l_pathFeature); // select the matching rule
495 // in the same order rules
501 FeatureSet* PathTable::getFeatureSet(SSPath& p)
503 if ( f_lastSymIndex == 0 ) {
510 fs[0] = getFeatureSet(findIndex(p), p, pids[0]);
511 fs[1] = getFeatureSet(gElemSymTab -> wildCardId(), p, pids[1]);
512 fs[2] = getFeatureSet(gElemSymTab -> unlimitedWildCardId(), p, pids[2]);
517 for ( int i=1; i<3; i++ ) {
526 PathTable::getFeatureSet(int bucketIndex, SSPath& p, int& pathId)
528 CC_TPtrDlistIterator<PathFeature> l_pathFeatureIter(*f_lastSymIndex[bucketIndex]);
530 l_pathFeatureIter.reset();
532 PathFeature* l_pathFeature = 0;
534 while ( ++l_pathFeatureIter ) {
536 l_pathFeature = l_pathFeatureIter.key();
538 //debug(cerr, *(l_pathFeature->path()));
539 //debug(cerr, *(l_pathFeature->featureSet()));
541 if ( l_pathFeature -> match(p) ) {
542 //MESSAGE(cerr, "match");
543 pathId = l_pathFeature -> id();
544 return l_pathFeature -> featureSet();
552 void PathTable::addPathFeatureSet(PathFeature* x)
554 //MESSAGE(cerr, "addPathFeatureSet():");
555 //debug(cerr, *(x->path()));
556 //debug(cerr, *(x->featureSet()));
558 if ( x -> path() -> containSelector() )
559 x -> path() -> fastGetIndex();
561 EncodedPath* l_epath = new EncodedPath(x -> path(), true);
562 unsigned int id = f_pathFeatureList.entries()+1;
564 x -> setEncodedPath(l_epath);
567 f_pathFeatureList.insert(x);
571 ostream& operator<<(ostream& out, PathTable& pt)
573 CC_TPtrDlistIterator<PathFeature> l_pfIter(pt.f_pathFeatureList);
574 PathFeature* l_pathFeature = 0;
576 while ( ++l_pfIter ) {
577 l_pathFeature = l_pfIter.key();
579 out << *(l_pathFeature)->path() << ' ' << *(l_pathFeature->featureSet())
583 // this will cause errors if gTopOfStack is not set properly
584 FeatureSet *set = l_pathFeature->featureSet()->evaluate();
594 void PathFeatureList::appendList(PathFeatureList& list)
596 PathFeatureListIterator l_Iter(list);
597 while ( ++ l_Iter ) {
598 append(l_Iter.key());
602 PathFeatureList::~PathFeatureList()