blautenb 2003/05/09 05:07:59
Modified: c/Projects/VC6.0/xsec/xsec_lib xsec_lib.dsp
c/src/transformers TXFMXPathFilter.cpp
c/src/utils XSECXPathNodeList.cpp XSECXPathNodeList.hpp
Log:
Re-implemented node-lists as an ordered list using binary search
Revision Changes Path
1.12 +8 -8 xml-security/c/Projects/VC6.0/xsec/xsec_lib/xsec_lib.dsp
Index: xsec_lib.dsp
===================================================================
RCS file: /home/cvs/xml-security/c/Projects/VC6.0/xsec/xsec_lib/xsec_lib.dsp,v
retrieving revision 1.11
retrieving revision 1.12
diff -u -r1.11 -r1.12
--- xsec_lib.dsp 8 May 2003 12:10:58 -0000 1.11
+++ xsec_lib.dsp 9 May 2003 12:07:59 -0000 1.12
@@ -821,6 +821,14 @@
# End Source File
# Begin Source File
+SOURCE=..\..\..\..\src\transformers\TXFMXPathFilter.cpp
+# End Source File
+# Begin Source File
+
+SOURCE=..\..\..\..\src\transformers\TXFMXPathFilter.hpp
+# End Source File
+# Begin Source File
+
SOURCE=..\..\..\..\src\transformers\TXFMXSL.cpp
# End Source File
# Begin Source File
@@ -836,13 +844,5 @@
SOURCE=..\..\..\..\src\framework\version.rc
# End Source File
# End Group
-# Begin Source File
-
-SOURCE=..\..\..\..\src\transformers\TXFMXPathFilter.cpp
-# End Source File
-# Begin Source File
-
-SOURCE=..\..\..\..\src\transformers\TXFMXPathFilter.hpp
-# End Source File
# End Target
# End Project
1.3 +42 -15 xml-security/c/src/transformers/TXFMXPathFilter.cpp
Index: TXFMXPathFilter.cpp
===================================================================
RCS file: /home/cvs/xml-security/c/src/transformers/TXFMXPathFilter.cpp,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- TXFMXPathFilter.cpp 8 May 2003 12:28:55 -0000 1.2
+++ TXFMXPathFilter.cpp 9 May 2003 12:07:59 -0000 1.3
@@ -437,19 +437,22 @@
return true;
}
-#if 0
+#if 1
void TXFMXPathFilter::walkDocument(DOMNode * n) {
+ // Non-recursive version
DOMNode * current = n;
DOMNode * next;
+ DOMNode * attParent;
bool done = false;
bool treeUp = false;
DOMNamedNodeMap * atts = n->getAttributes();
int attsSize = -1;
int currentAtt = -1;
+ lstsVectorType::iterator lstsIter;
- while (done == false) {
+ while (done == false && current != NULL) {
if (treeUp == true) {
@@ -462,6 +465,15 @@
else {
+ // Remove this node from the ancestor lists
+ for (lstsIter = m_lsts.begin(); lstsIter <
m_lsts.end(); ++lstsIter) {
+
+ if ((*lstsIter)->ancestorInScope ==
current) {
+ (*lstsIter)->ancestorInScope =
NULL;
+ }
+ }
+
+
// Check for another sibling
next = current->getNextSibling();
@@ -485,7 +497,6 @@
else {
// Check if the current node is in the result set. The
walk the children
- lstsVectorType::iterator lstsIter;
// First check if this node is in any lists, and if so,
// set the appropriate ancestor nodes (if necessary)
@@ -505,9 +516,9 @@
// Now that the ancestor setup is done, check to see if
this node is
// in scope.
- if (checkNodeInScope(n) && checkNodeInInput(n)) {
+ if (checkNodeInScope(current) &&
checkNodeInInput(current)) {
- m_xpathFilterMap.addNode(n);
+ m_xpathFilterMap.addNode(current);
}
@@ -522,8 +533,14 @@
// Attribute list complete
atts = NULL;
- current = current->getParentNode();
- treeUp = true;
+ current = attParent;
+ next = current->getFirstChild();
+ if (next == NULL)
+ treeUp = true;
+ else {
+ current = next;
+ treeUp = false;
+ }
}
@@ -537,23 +554,33 @@
else {
// Working on an element or other non-attribute
node
- atts = n->getAttributes();
+ atts = current->getAttributes();
+
if (atts != NULL && ((attsSize =
atts->getLength()) > 0)) {
currentAtt = 0;
+ attParent = current;
current = atts->item(0);
+ treeUp = false;
}
else {
- next = current->getNextSibling();
- if (next == NULL) {
- current =
current->getParentNode();
+ atts = NULL;
+
+ next = current->getFirstChild();
+
+ if (next != NULL) {
+ current = next;
+ treeUp = false;
+ }
+
+ else {
+
treeUp = true;
+
}
- else
- current = next;
}
} /* ! atts == NULL */
@@ -561,7 +588,7 @@
} /* while */
}
#endif
-#if 1
+#if 0
void TXFMXPathFilter::walkDocument(DOMNode * n) {
1.4 +130 -98 xml-security/c/src/utils/XSECXPathNodeList.cpp
Index: XSECXPathNodeList.cpp
===================================================================
RCS file: /home/cvs/xml-security/c/src/utils/XSECXPathNodeList.cpp,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- XSECXPathNodeList.cpp 1 Mar 2003 06:27:30 -0000 1.3
+++ XSECXPathNodeList.cpp 9 May 2003 12:07:59 -0000 1.4
@@ -84,9 +84,12 @@
// Constructors and Destructors.
//
--------------------------------------------------------------------------------
-XSECXPathNodeList::XSECXPathNodeList() {
+XSECXPathNodeList::XSECXPathNodeList(unsigned int initialSize) {
- mp_first = mp_last = NULL;
+ mp_elts = new const DOMNode *[initialSize];
+ m_size = initialSize;
+ m_current = 0;
+ m_num = 0;
}
@@ -94,20 +97,13 @@
// Copy Constructor
- // For now simply delete the old list and set with the new
- // Large overhead as we call other functions, but simplest way to
- // implement for now
-
- mp_first = mp_last = NULL;
+ mp_elts = new const DOMNode *[other.m_size];
+ m_size = other.m_size;
+ m_num = other.m_num;
- XSECXPathNodeListElt *cpyTmp;
+ for (unsigned int i = 0; i < m_num; ++i) {
- cpyTmp = other.mp_first;
-
- while (cpyTmp != NULL) {
-
- addNode(cpyTmp->element);
- cpyTmp = cpyTmp->next;
+ mp_elts[i] = other.mp_elts[i];
}
@@ -117,7 +113,7 @@
// Delete all the elements in the node list
- clear();
+ delete[] mp_elts;
}
@@ -127,16 +123,15 @@
// Large overhead as we call other functions, but simplest way to
// implement for now
- clear();
+ delete[] mp_elts;
- XSECXPathNodeListElt *cpyTmp;
+ mp_elts = new const DOMNode *[toCopy.m_size];
+ m_size = toCopy.m_size;
+ m_num = toCopy.m_num;
- cpyTmp = toCopy.mp_first;
+ for (unsigned int i = 0; i < m_num; ++i) {
- while (cpyTmp != NULL) {
-
- addNode(cpyTmp->element);
- cpyTmp = cpyTmp->next;
+ mp_elts[i] = toCopy.mp_elts[i];
}
@@ -148,22 +143,42 @@
// Utility Functions.
//
--------------------------------------------------------------------------------
-XSECXPathNodeList::XSECXPathNodeListElt * XSECXPathNodeList::findNode(const
DOMNode *n) {
+unsigned int XSECXPathNodeList::findNodeIndex(const DOMNode *n) {
- XSECXPathNodeListElt * tmp;
+ // Check default values
+ if (m_num == 0 || mp_elts[0] >= n)
+ return 0;
- tmp = mp_first;
+ // Binary search through the list to find where this node should be
- while (tmp != NULL) {
+ unsigned int l = 0; // Low
+ unsigned int h = m_num; // High
- if (tmp->element == n)
- return tmp;
+ unsigned int i;
- tmp = tmp->next;
+ while (true) {
- }
+ i = l + ((h - l) / 2);
- return NULL;
+ if (l == i)
+ return i + 1; // Insert point is the next element
+
+ if (mp_elts[i] == n) {
+ return i; // Found and in list
+ }
+
+ if (n > mp_elts[i]) {
+
+ // In top half of search space
+ l = i;
+
+ }
+
+ else
+ // In bottom half of search space
+ h = i;
+
+ }
}
@@ -174,90 +189,77 @@
void XSECXPathNodeList::addNode(const DOMNode *n) {
- XSECXPathNodeListElt *tmp;
-
- if (findNode(n) != NULL)
- return; // Allready exists
+ if (m_num == 0) {
+ mp_elts[0] = n;
+ m_num = 1;
+ return;
+ }
- XSECnew(tmp, XSECXPathNodeListElt);
- tmp->element = n;
+ unsigned int i = findNodeIndex(n);
- if (mp_first == NULL) {
+ if (i != m_num && mp_elts[i] == n)
+ return;
+#if 0
+ if (m_num == m_size) {
- tmp->next = NULL;
- tmp->last = NULL;
+ // need to re-create the list with a bigger aray
+ m_size *= 10;
+
+ const DOMNode ** newElts = new const DOMNode*[m_size];
+ for (unsigned j = 0; j < m_num; ++j) {
+ newElts[j] = mp_elts[j];
+ }
+ delete mp_elts;
+ mp_elts = newElts;
+
+ }
- mp_first = tmp;
- mp_last = tmp;
+ for (unsigned int j = m_num; j > i; --j) {
+ mp_elts[j] = mp_elts[j - 1];
+
}
+#endif
+ if (m_num == m_size) {
- else if (mp_last == NULL) {
+ // Need to create the list with a bigger array
+ m_size *= 10;
- delete tmp;
+ const DOMNode ** newElts = new const DOMNode*[m_size];
+ memcpy(newElts, mp_elts, sizeof(DOMNode *) * m_num);
- throw XSECException(XSECException::InternalError,
- "XSECXPathNodeList has an element that is incorrectly
linked");
+ delete mp_elts;
+ mp_elts = newElts;
}
- else {
+ memmove(&(mp_elts[i+1]), &(mp_elts[i]), (m_num - i) * sizeof(DOMNode
*));
- mp_last->next = tmp;
- tmp->last = mp_last;
- tmp->next = NULL;
- mp_last = tmp;
- }
+ mp_elts[i] = n;
+ ++m_num;
}
void XSECXPathNodeList::removeNode(const DOMNode *n) {
- XSECXPathNodeListElt * tmp;
+ unsigned int i = findNodeIndex(n);
- tmp = findNode(n);
-
- if (tmp == NULL)
+ if (i == m_num || mp_elts[i] != n)
+ // not found
return;
- if (tmp->last != NULL) {
+ for (unsigned int j = i; j < m_num; ++j)
+ mp_elts[j] = mp_elts[j+1];
- tmp->last->next = tmp->next;
+ m_num--;
- }
-
- if (tmp->next != NULL) {
-
- tmp->next->last = tmp->last;
-
- }
-
- if (mp_first == tmp)
- mp_first = tmp->next;
- if (mp_last == tmp)
- mp_last = tmp->last;
-
- delete tmp;
}
void XSECXPathNodeList::clear() {
- XSECXPathNodeListElt * tmp;
-
- tmp = mp_first;
-
- while (tmp != NULL) {
-
- mp_first = tmp->next;
- delete tmp;
-
- tmp = mp_first;
-
- }
-
- mp_last = NULL;
+ m_num = 0;
}
@@ -268,33 +270,63 @@
bool XSECXPathNodeList::hasNode(const DOMNode *n) {
- return (findNode(n) != NULL);
+ unsigned int i = findNodeIndex(n);
+
+ return (i != m_num && mp_elts[i] == n);
}
const DOMNode *XSECXPathNodeList::getFirstNode(void) {
- if (mp_first == NULL)
- return NULL;
-
- mp_search = mp_first->next;
- return mp_first->element;
+ m_current = 0;
+ return getNextNode();
}
const DOMNode *XSECXPathNodeList::getNextNode(void) {
- if (mp_search == NULL)
+ if (m_current == m_num)
return NULL;
- XSECXPathNodeListElt * tmp;
+ return mp_elts[m_current++];
- tmp = mp_search;
- mp_search = mp_search->next;
+}
- return tmp->element;
+//
--------------------------------------------------------------------------------
+// Intersect with another list
+//
--------------------------------------------------------------------------------
-}
+void XSECXPathNodeList::intersect(const XSECXPathNodeList &toIntersect) {
+
+ const DOMNode ** newList = new const DOMNode *[m_size];
+
+ unsigned int i = 0;
+ unsigned int j = 0;
+ unsigned int k = 0;
+
+ while (true) {
+
+ if (mp_elts[i] == toIntersect.mp_elts[j]) {
+ newList[k++] = mp_elts[i++];
+ j++;
+ }
+
+ else if (mp_elts[i] < toIntersect.mp_elts[j]) {
+ ++i;
+ }
+ else
+ ++j;
+
+ if (i == m_num || j == toIntersect.m_num)
+ break;
+
+ }
+
+ m_num = k;
+ delete[] mp_elts;
+ mp_elts = newList;
+
+}
1.4 +25 -24 xml-security/c/src/utils/XSECXPathNodeList.hpp
Index: XSECXPathNodeList.hpp
===================================================================
RCS file: /home/cvs/xml-security/c/src/utils/XSECXPathNodeList.hpp,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- XSECXPathNodeList.hpp 22 Feb 2003 08:47:26 -0000 1.3
+++ XSECXPathNodeList.hpp 9 May 2003 12:07:59 -0000 1.4
@@ -79,6 +79,8 @@
XSEC_DECLARE_XERCES_CLASS(DOMNode);
+#define _XSEC_NODELIST_DEFAULT_SIZE 100
+
/**
* @ingroup internal
*/
@@ -98,30 +100,12 @@
class DSIG_EXPORT XSECXPathNodeList {
-
-private:
-
- /**
- * \brief Element holder.
- *
- * Currently the list is implemented as a simple doubly linked list.
- */
-
- struct XSECXPathNodeListElt {
-
- const DOMNode * element; // Element
referred to
-
- XSECXPathNodeListElt * next,
- * last;
// For the list
-
- };
-
public:
/** @name Constructors, Destructors and operators */
//@{
- XSECXPathNodeList();
+ XSECXPathNodeList(unsigned int initialSize =
_XSEC_NODELIST_DEFAULT_SIZE);
/**
* \brief Copy Constructor
@@ -219,15 +203,32 @@
//@}
+ /** @name Manipulating Nodesets */
+ //@{
+
+ /**
+ *\brief Intersect with nodeset
+ *
+ * Delete any nodes in my list that are not in the intersect list
+ *
+ * @param toIntersect The list to intersect with.
+ */
+
+ void intersect(const XSECXPathNodeList &toIntersect);
+
+ //@}
+
private:
// Internal functions
- XSECXPathNodeListElt * findNode(const DOMNode * n);
+ unsigned int findNodeIndex(const DOMNode * n);
+
+ const DOMNode ** mp_elts;
// The current list of elements
- XSECXPathNodeListElt * mp_first;
// First node in list
- XSECXPathNodeListElt * mp_last;
// Last node in list
- XSECXPathNodeListElt * mp_search; //
Where we are in the return
+ unsigned int m_size;
// How big is the current array
+ unsigned int m_num;
// Number of elements in the array
+ unsigned int m_current;
// current point in list for getNextNode
};
