606 lines
15 KiB
C
606 lines
15 KiB
C
/*
|
|
* CDE - Common Desktop Environment
|
|
*
|
|
* Copyright (c) 1993-2012, The Open Group. All rights reserved.
|
|
*
|
|
* These libraries and programs are free software; you can
|
|
* redistribute them and/or modify them under the terms of the GNU
|
|
* Lesser General Public License as published by the Free Software
|
|
* Foundation; either version 2 of the License, or (at your option)
|
|
* any later version.
|
|
*
|
|
* These libraries and programs are distributed in the hope that
|
|
* they will be useful, but WITHOUT ANY WARRANTY; without even the
|
|
* implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
|
|
* PURPOSE. See the GNU Lesser General Public License for more
|
|
* details.
|
|
*
|
|
* You should have received a copy of the GNU Lesser General Public
|
|
* License along with these libraries and programs; if not, write
|
|
* to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
|
|
* Floor, Boston, MA 02110-1301 USA
|
|
*/
|
|
// $XConsortium: PathTable.cc /main/4 1996/06/11 17:07:57 cde-hal $
|
|
#include "PathTable.h"
|
|
#include "Debug.h"
|
|
#include "Feature.h"
|
|
#include "utility/debug.h"
|
|
|
|
extern SymbolTable* gElemSymTab;
|
|
|
|
unsigned int letterHash(const LetterType& x)
|
|
{
|
|
return x;
|
|
}
|
|
|
|
EncodedPath::~EncodedPath()
|
|
{
|
|
delete [] f_array ;
|
|
f_SVectors.clearAndDestroy();
|
|
delete f_copyOfS;
|
|
}
|
|
|
|
EncodedPath::EncodedPath(SSPath* p, unsigned int asPattern) :
|
|
f_size(p -> entries()), f_patternSize(0), f_SVectors(letterHash),
|
|
f_wildCard(gElemSymTab -> wildCardId()),
|
|
f_unlimitedWildCard(gElemSymTab -> unlimitedWildCardId()),
|
|
f_copyOfS(new BitVector(WORD_SIZE, 0))
|
|
{
|
|
|
|
f_array = new LetterType[f_size];
|
|
|
|
CC_TPtrDlistIterator<PathTerm> l_pathIter(*p);
|
|
|
|
BitVector *l_bv = 0;
|
|
|
|
int i = 0;
|
|
|
|
while (++l_pathIter) {
|
|
|
|
//
|
|
// Count pattern size, excluding "*".
|
|
//
|
|
f_array[i] = (LetterType)((l_pathIter.key() -> symbol()).id());
|
|
if ( f_array[i] != f_unlimitedWildCard )
|
|
f_patternSize++;
|
|
i++;
|
|
}
|
|
|
|
if ( asPattern == true ) {
|
|
|
|
//
|
|
// Compute the S arrays.
|
|
// Examples pat = a b a c
|
|
// S(a) = 1 0 1 0
|
|
// S(b) = 0 0 0 0
|
|
// S(c) = 0 0 0 1
|
|
//
|
|
// pat = a ? a c
|
|
// S(a) = 1 1 1 0
|
|
// S(c) = 0 1 0 1
|
|
// S(?) = 0 1 0 0
|
|
//
|
|
// pat = a * a c
|
|
// S(a) = 1 1 0
|
|
// S(c) = 0 0 1
|
|
// S(*) = 1 0 0
|
|
//
|
|
l_pathIter.reset();
|
|
int j = patternLength()-1;
|
|
|
|
LetterType l_id;
|
|
|
|
// i records each PathTerm position in the list
|
|
int i=0;
|
|
|
|
while (++l_pathIter) {
|
|
l_id = (LetterType)((l_pathIter.key() -> symbol()).id());
|
|
|
|
l_bv = f_SVectors.findValue(&l_id);
|
|
if ( l_bv == 0 ) {
|
|
l_bv = new BitVector(patternLength(), 0);
|
|
f_SVectors.insertKeyAndValue(new LetterType(l_id), l_bv);
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////
|
|
// reverse the order in the bit vector:
|
|
// MSB position ==> set LSB bit in the bit vector
|
|
///////////////////////////////////////////////////
|
|
if ( l_id != f_unlimitedWildCard ) {
|
|
l_bv -> setBitTo(j, 1);
|
|
|
|
//////////////////////////////////////////////////
|
|
// only set position when an expr is attatched
|
|
// to the term
|
|
//////////////////////////////////////////////////
|
|
if ( l_pathIter.key() -> pqexpr() && l_id != f_wildCard ) {
|
|
/*
|
|
MESSAGE(cerr, "==========");
|
|
debug(cerr, (void*)l_bv);
|
|
debug(cerr, *l_bv);
|
|
debug(cerr, i);
|
|
debug(cerr, j);
|
|
*/
|
|
l_bv -> recordPositions(i, j);
|
|
|
|
}
|
|
|
|
j--;
|
|
|
|
} else {
|
|
///////////////////////////////////////////////////
|
|
// do not set bits for unlimitedWildCards that
|
|
// begin or end the pattern
|
|
///////////////////////////////////////////////////
|
|
if ( j < patternLength() - 1 )
|
|
l_bv -> setBitTo(j+1, 1);
|
|
}
|
|
i++;
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////
|
|
// special treatment to the ? symbols:
|
|
// OR S(?) back to each S's.
|
|
///////////////////////////////////////////////////
|
|
BitVector* l_BitVectorWildCard = f_SVectors.findValue(&f_wildCard);
|
|
hashTableIterator<LetterType, BitVector> l_SVIter(f_SVectors);
|
|
|
|
if ( l_BitVectorWildCard ) {
|
|
while (++l_SVIter) {
|
|
if ( *l_SVIter.key() != f_wildCard &&
|
|
*l_SVIter.key() != f_unlimitedWildCard
|
|
)
|
|
{
|
|
(*l_SVIter.value()) |= (*l_BitVectorWildCard);
|
|
}
|
|
}
|
|
}
|
|
/*
|
|
#ifdef DEBUG
|
|
l_SVIter.reset();
|
|
while (++l_SVIter) {
|
|
debug(cerr, (*l_SVIter.key()));
|
|
debug(cerr, (*l_SVIter.value()));
|
|
}
|
|
#endif
|
|
*/
|
|
}
|
|
}
|
|
|
|
|
|
|
|
unsigned int
|
|
_match(LetterType* pattern, int n,
|
|
LetterType* text, int m,
|
|
LetterType wildCard,
|
|
LetterType unlimitedWildCard
|
|
)
|
|
{
|
|
// A naive (brute force) string matching algorithm that handles
|
|
// wild card (?) and unlimited wild card (*) symbols.
|
|
unsigned int findMisMatch = false;
|
|
|
|
for ( int i=0; i<n; i++ ) { // over the "text" string
|
|
|
|
for ( int j=0; j<m; j++ ) { // over the pattern
|
|
if ( pattern[j] == wildCard ) {
|
|
continue;
|
|
} else
|
|
if ( pattern[j] == unlimitedWildCard ) {
|
|
|
|
for (;;) {
|
|
|
|
j++;
|
|
|
|
if ( j == m )
|
|
return true;
|
|
|
|
if ( pattern[j] != unlimitedWildCard )
|
|
break;
|
|
}
|
|
|
|
for ( int x=i+1; x<n; x++ ) {
|
|
if ( text[x] == pattern[j] )
|
|
if (
|
|
_match(
|
|
&pattern[j], m-j,
|
|
&text[x], n-x,
|
|
wildCard, unlimitedWildCard
|
|
) == true
|
|
)
|
|
return true;
|
|
|
|
}
|
|
|
|
} else {
|
|
if ( pattern[j] != text[i] ) {
|
|
findMisMatch = true;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
if ( findMisMatch == false )
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
|
|
unsigned int
|
|
EncodedPath::match(EncodedPath& text, SSPath* patternPath, SSPath* elementPath)
|
|
{
|
|
////////////////////////////////////////////////
|
|
// text: the encoded string for the element path
|
|
// elementPath: the element path
|
|
//
|
|
// this: the encoded string for the pattern string
|
|
// patternPath: the pattern path
|
|
////////////////////////////////////////////////
|
|
|
|
|
|
////////////////////////////////////////////////
|
|
// the unlimited wildcard vector
|
|
////////////////////////////////////////////////
|
|
BitVector* l_U = f_SVectors.findValue(&f_unlimitedWildCard);
|
|
|
|
if ( l_U && patternLength() == 0 )
|
|
return true;
|
|
|
|
////////////////////////////////////////////////
|
|
// the wildcard vector
|
|
////////////////////////////////////////////////
|
|
BitVector* l_W = f_SVectors.findValue(&f_wildCard);
|
|
|
|
// the S vector of each Letter, including that for '?'
|
|
BitVector* l_S = 0;
|
|
|
|
// the accumulated result vector
|
|
BitVector l_R(patternLength(), 0);
|
|
|
|
// placeholder for '*''s contribution
|
|
BitVector l_I(patternLength(), 0);
|
|
|
|
// hole position record of each path term in the pattern path
|
|
posRecord l_pr;
|
|
|
|
// expr pointer of each path term in the pattern path
|
|
PQExpr* expr = 0;
|
|
|
|
CC_TPtrDlistIterator<PathTerm>* elementPathNextPtr = 0;
|
|
|
|
if ( elementPath )
|
|
elementPathNextPtr = new CC_TPtrDlistIterator<PathTerm>(*elementPath);
|
|
|
|
// loop over text string
|
|
for ( int i=0; i<text.length(); i++) {
|
|
|
|
if ( elementPath )
|
|
++(*elementPathNextPtr);
|
|
|
|
//MESSAGE(cerr, "===================");
|
|
//debug(cerr, text.f_array[i]);
|
|
|
|
////////////////////////////////////////////////
|
|
// get this character's vector, including '?'s
|
|
////////////////////////////////////////////////
|
|
l_S = f_SVectors.findValue(&text.f_array[i]);
|
|
|
|
if ( l_S ) {
|
|
//debug(cerr, (void*)l_S);
|
|
//debug(cerr, *l_S);
|
|
//MESSAGE(cerr, "checking qualifies");
|
|
//////////////////////
|
|
// check qualifies.
|
|
//////////////////////
|
|
if ( patternPath && l_S -> positionArray() ) {
|
|
|
|
////////////////////
|
|
// get a copy of S
|
|
////////////////////
|
|
f_copyOfS -> setTo(*l_S);
|
|
|
|
//debug(cerr, *patternPath);
|
|
|
|
positionArrayIteratorT l_positionNext(*(l_S -> positionArray()));
|
|
while (++ l_positionNext) {
|
|
|
|
l_pr = l_positionNext.key();
|
|
|
|
//cerr << " calling patternPath -> fastGetAt(): " << (void*)patternPath << "l_pr.pathTermPos= " << l_pr.pathTermPos << endl;
|
|
|
|
expr = patternPath -> fastGetAt(l_pr.pathTermPos) -> pqexpr();
|
|
/*
|
|
debug(cerr, int(expr));
|
|
if ( expr ) {
|
|
MESSAGE(cerr, "qualify checking is needed.");
|
|
debug(cerr, *(elementPathNext -> key()));
|
|
}
|
|
*/
|
|
|
|
if ( expr &&
|
|
expr->evaluate(elementPathNextPtr->key()->element()) == PQFalse )
|
|
{
|
|
//MESSAGE(cerr, form("set position %d to 0", l_pr.bitPos));
|
|
f_copyOfS -> setBitTo(l_pr.bitPos, 0);
|
|
}
|
|
}
|
|
/////////////////////////////////////////
|
|
// make l_S point at its modified copy
|
|
/////////////////////////////////////////
|
|
l_S = f_copyOfS;
|
|
}
|
|
} else
|
|
l_S = l_W;
|
|
|
|
////////////////////////////////////////////////
|
|
// get unlimited wildcard's vector.
|
|
////////////////////////////////////////////////
|
|
if ( l_U ) {
|
|
l_I.setTo(l_R);
|
|
l_I &= (*l_U);
|
|
//MESSAGE(cerr, "l_I");
|
|
//debug(cerr, l_I);
|
|
|
|
}
|
|
|
|
////////////////////////////////////////////////
|
|
// shift the partial result vector right once
|
|
////////////////////////////////////////////////
|
|
l_R.shiftRightOneBit();
|
|
//MESSAGE(cerr, "after l_R >> 1");
|
|
//debug(cerr, l_R);
|
|
|
|
////////////////////////////////////////////////
|
|
// AND in this character's vector
|
|
////////////////////////////////////////////////
|
|
if ( l_S ) {
|
|
l_R &= (*l_S);
|
|
//debug(cerr, *l_S);
|
|
//MESSAGE(cerr, "after AND with l_S");
|
|
//debug(cerr, l_R);
|
|
} else {
|
|
///////////////////////////////////////////////
|
|
// this branch is impossible to reach.
|
|
///////////////////////////////////////////////
|
|
//MESSAGE(cerr, "l_R set all bits to 0");
|
|
l_R.setAllBitsTo(0);
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////
|
|
// OR in unlimited wild char's vector.
|
|
///////////////////////////////////////////////
|
|
if ( l_U ) {
|
|
l_R |= l_I;
|
|
//MESSAGE(cerr, "after OR with l_I");
|
|
//debug(cerr, l_R);
|
|
}
|
|
//debug(cerr, l_R);
|
|
//MESSAGE(cerr, "===================");
|
|
|
|
///////////////////////////////////////////////
|
|
// Use this test to get the first matched position
|
|
// if ( l_R.getBit(0) == 1 )
|
|
// return true;
|
|
///////////////////////////////////////////////
|
|
|
|
}
|
|
delete elementPathNextPtr;
|
|
|
|
///////////////////////////////////////////////
|
|
//
|
|
// the last symbol must match
|
|
//
|
|
///////////////////////////////////////////////
|
|
if ( l_R.getBit(0) == 1 )
|
|
return true;
|
|
else
|
|
return false;
|
|
|
|
}
|
|
|
|
basePathFeature::~basePathFeature()
|
|
{
|
|
delete f_path;
|
|
delete f_featureSet;
|
|
}
|
|
|
|
PathFeature::~PathFeature()
|
|
{
|
|
delete f_encodedPath ;
|
|
}
|
|
|
|
unsigned int basePathFeature::operator==(const basePathFeature& pf) const
|
|
{
|
|
cerr << "Warning: basePathFeature::operator==() called\n";
|
|
return true;
|
|
}
|
|
|
|
unsigned int PathFeature::operator==(const PathFeature& pf) const
|
|
{
|
|
cerr << "Warning: PathFeature::operator==() called\n";
|
|
return true;
|
|
}
|
|
|
|
void pathSelector(BitVector& bv)
|
|
{
|
|
}
|
|
|
|
unsigned int
|
|
PathFeature::match(SSPath& p)
|
|
{
|
|
EncodedPath l_ep(&p);
|
|
|
|
if ( f_path -> containSelector() == false )
|
|
return f_encodedPath -> match(l_ep, 0, 0);
|
|
else
|
|
return f_encodedPath -> match(l_ep, f_path, &p);
|
|
}
|
|
|
|
|
|
// /////////////////////////////////////////////////////////////////////////
|
|
//
|
|
// class PathTable
|
|
//
|
|
// /////////////////////////////////////////////////////////////////////////
|
|
|
|
|
|
unsigned symHashFunc(const Symbol& s)
|
|
{
|
|
return s.hash();
|
|
}
|
|
|
|
PathTable::PathTable()
|
|
: f_lastSymIndex(0),
|
|
f_lastSymIndexCount(0)
|
|
{
|
|
}
|
|
|
|
PathTable::~PathTable()
|
|
{
|
|
f_pathFeatureList.clearAndDestroy();
|
|
for (unsigned int i = 0 ; i < f_lastSymIndexCount; i++) {
|
|
//f_lastSymIndex[i].clearAndDestroy();
|
|
f_lastSymIndex[i] -> clear();
|
|
delete f_lastSymIndex[i];
|
|
}
|
|
delete f_lastSymIndex;
|
|
}
|
|
|
|
LetterType PathTable::findIndex(SSPath& p)
|
|
{
|
|
return (LetterType) ((p.last() -> symbol()).id());
|
|
}
|
|
|
|
void PathTable::initLastSymIndex()
|
|
{
|
|
f_lastSymIndexCount = gElemSymTab -> IdsAssigned()+1;
|
|
f_lastSymIndex = new CC_TPtrDlist_PathFeature_Ptr_T[f_lastSymIndexCount];
|
|
for (unsigned int i=0; i<f_lastSymIndexCount; i++)
|
|
f_lastSymIndex[i] = new CC_TPtrDlist<PathFeature>;
|
|
|
|
|
|
CC_TPtrDlistIterator<PathFeature> l_pfIter(f_pathFeatureList);
|
|
PathFeature* l_pathFeature = 0;
|
|
|
|
LetterType x;
|
|
|
|
while ( ++l_pfIter ) {
|
|
l_pathFeature = l_pfIter.key();
|
|
x = findIndex( *(l_pathFeature->path()) );
|
|
//f_lastSymIndex[x] -> prepend(l_pathFeature); // backward order
|
|
f_lastSymIndex[x] -> append(l_pathFeature); // select the matching rule
|
|
// in the same order rules
|
|
// appear in the
|
|
// stylesheet
|
|
}
|
|
}
|
|
|
|
FeatureSet* PathTable::getFeatureSet(SSPath& p)
|
|
{
|
|
if ( f_lastSymIndex == 0 ) {
|
|
initLastSymIndex();
|
|
}
|
|
|
|
int pids[3];
|
|
FeatureSet* fs[3];
|
|
|
|
fs[0] = getFeatureSet(findIndex(p), p, pids[0]);
|
|
fs[1] = getFeatureSet(gElemSymTab -> wildCardId(), p, pids[1]);
|
|
fs[2] = getFeatureSet(gElemSymTab -> unlimitedWildCardId(), p, pids[2]);
|
|
|
|
int index = 0;
|
|
int x = pids[0];
|
|
|
|
for ( int i=1; i<3; i++ ) {
|
|
if ( pids[i] > x )
|
|
index = i;
|
|
}
|
|
|
|
return fs[index];
|
|
}
|
|
|
|
FeatureSet*
|
|
PathTable::getFeatureSet(int bucketIndex, SSPath& p, int& pathId)
|
|
{
|
|
CC_TPtrDlistIterator<PathFeature> l_pathFeatureIter(*f_lastSymIndex[bucketIndex]);
|
|
|
|
l_pathFeatureIter.reset();
|
|
|
|
PathFeature* l_pathFeature = 0;
|
|
|
|
while ( ++l_pathFeatureIter ) {
|
|
|
|
l_pathFeature = l_pathFeatureIter.key();
|
|
|
|
//debug(cerr, *(l_pathFeature->path()));
|
|
//debug(cerr, *(l_pathFeature->featureSet()));
|
|
|
|
if ( l_pathFeature -> match(p) ) {
|
|
//MESSAGE(cerr, "match");
|
|
pathId = l_pathFeature -> id();
|
|
return l_pathFeature -> featureSet();
|
|
}
|
|
}
|
|
|
|
pathId = 0;
|
|
return 0;
|
|
}
|
|
|
|
void PathTable::addPathFeatureSet(PathFeature* x)
|
|
{
|
|
//MESSAGE(cerr, "addPathFeatureSet():");
|
|
//debug(cerr, *(x->path()));
|
|
//debug(cerr, *(x->featureSet()));
|
|
|
|
if ( x -> path() -> containSelector() )
|
|
x -> path() -> fastGetIndex();
|
|
|
|
EncodedPath* l_epath = new EncodedPath(x -> path(), true);
|
|
unsigned int id = f_pathFeatureList.entries()+1;
|
|
|
|
x -> setEncodedPath(l_epath);
|
|
x -> setID(id);
|
|
|
|
f_pathFeatureList.insert(x);
|
|
|
|
}
|
|
|
|
ostream& operator<<(ostream& out, PathTable& pt)
|
|
{
|
|
CC_TPtrDlistIterator<PathFeature> l_pfIter(pt.f_pathFeatureList);
|
|
PathFeature* l_pathFeature = 0;
|
|
|
|
while ( ++l_pfIter ) {
|
|
l_pathFeature = l_pfIter.key();
|
|
|
|
out << *(l_pathFeature)->path() << ' ' << *(l_pathFeature->featureSet())
|
|
<< endl;
|
|
|
|
#ifdef DEBUG
|
|
// this will cause errors if gTopOfStack is not set properly
|
|
FeatureSet *set = l_pathFeature->featureSet()->evaluate();
|
|
out << *set << endl;
|
|
delete set ;
|
|
#endif
|
|
}
|
|
|
|
|
|
return out;
|
|
}
|
|
|
|
void PathFeatureList::appendList(PathFeatureList& list)
|
|
{
|
|
PathFeatureListIterator l_Iter(list);
|
|
while ( ++ l_Iter ) {
|
|
append(l_Iter.key());
|
|
}
|
|
}
|
|
|
|
PathFeatureList::~PathFeatureList()
|
|
{
|
|
clearAndDestroy();
|
|
}
|