You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@xerces.apache.org by an...@locus.apache.org on 2000/05/13 05:51:19 UTC
cvs commit: xml-xerces/c/src/dom NodeIDMap.cpp NodeIDMap.hpp AttrImpl.cpp DocumentImpl.cpp DocumentImpl.hpp NodeImpl.cpp NodeImpl.hpp
andyh 00/05/12 20:51:18
Modified: c/src/dom AttrImpl.cpp DocumentImpl.cpp DocumentImpl.hpp
NodeImpl.cpp NodeImpl.hpp
Added: c/src/dom NodeIDMap.cpp NodeIDMap.hpp
Log:
DOM GetElementsById(), new implementation
Revision Changes Path
1.17 +16 -1 xml-xerces/c/src/dom/AttrImpl.cpp
Index: AttrImpl.cpp
===================================================================
RCS file: /home/cvs/xml-xerces/c/src/dom/AttrImpl.cpp,v
retrieving revision 1.16
retrieving revision 1.17
diff -u -r1.16 -r1.17
--- AttrImpl.cpp 2000/04/28 23:21:22 1.16
+++ AttrImpl.cpp 2000/05/13 03:51:17 1.17
@@ -55,7 +55,7 @@
*/
/*
- * $Id: AttrImpl.cpp,v 1.16 2000/04/28 23:21:22 lehors Exp $
+ * $Id: AttrImpl.cpp,v 1.17 2000/05/13 03:51:17 andyh Exp $
*/
#include "AttrImpl.hpp"
@@ -64,6 +64,7 @@
#include "TextImpl.hpp"
#include "ElementImpl.hpp"
#include "DStringPool.hpp"
+#include "NodeIDMap.hpp"
AttrImpl::AttrImpl(DocumentImpl *ownerDoc, const DOMString &aName)
@@ -78,12 +79,15 @@
{
name = other.name.clone();
specified(false);
+ idAttr(false);
if (deep)
cloneChildren(other);
};
AttrImpl::~AttrImpl() {
+ if (this->idAttr())
+ this->getOwnerDocument()->getNodeIDMap()->remove(this);
};
@@ -177,6 +181,13 @@
);
}
+ // If this attribute was of type ID and in the map, take it out,
+ // then put it back in with the new name. For now, we don't worry
+ // about what happens if the new name conflicts
+ //
+ if (idAttr())
+ this->getOwnerDocument()->getNodeIDMap()->remove(this);
+
NodeImpl *kid;
while ((kid = firstChild) != null) // Remove existing kids
{
@@ -189,6 +200,10 @@
appendChild(ownerDocument->createTextNode(val));
specified(true);
changed();
+
+ if (idAttr())
+ this->getOwnerDocument()->getNodeIDMap()->add(this);
+
};
1.24 +17 -4 xml-xerces/c/src/dom/DocumentImpl.cpp
Index: DocumentImpl.cpp
===================================================================
RCS file: /home/cvs/xml-xerces/c/src/dom/DocumentImpl.cpp,v
retrieving revision 1.23
retrieving revision 1.24
diff -u -r1.23 -r1.24
--- DocumentImpl.cpp 2000/05/09 00:22:32 1.23
+++ DocumentImpl.cpp 2000/05/13 03:51:17 1.24
@@ -55,7 +55,7 @@
*/
/*
- * $Id: DocumentImpl.cpp,v 1.23 2000/05/09 00:22:32 andyh Exp $
+ * $Id: DocumentImpl.cpp,v 1.24 2000/05/13 03:51:17 andyh Exp $
*/
//
@@ -86,6 +86,7 @@
#include <internal/XMLReader.hpp>
#include "TreeWalkerImpl.hpp"
#include "NodeIteratorImpl.hpp"
+#include "NodeIDMap.hpp"
#include "DOM_Document.hpp"
@@ -97,6 +98,8 @@
namePool = new DStringPool(257);
iterators = 0L;
treeWalkers = 0L;
+ fNodeIDMap = 0;
+
};
@@ -113,8 +116,9 @@
docElement=null;
appendChild(createElementNS(fNamespaceURI, qualifiedName)); //root element
namePool = new DStringPool(257);
- iterators = 0L;
- treeWalkers = 0L;
+ iterators = 0;
+ treeWalkers = 0;
+ fNodeIDMap = 0;
}
void DocumentImpl::setDocumentType(DocumentTypeImpl *doctype)
@@ -158,6 +162,8 @@
// Do not delete docType and docElement pointers here.
// These are also normal child nodes of the document,
// and refcounting will take them out in the usual way.
+
+ delete fNodeIDMap;
};
@@ -651,7 +657,14 @@
ElementImpl *DocumentImpl::getElementById(const DOMString &elementId)
{
- return null;
+ if (fNodeIDMap == 0)
+ return null;
+
+ AttrImpl *theAttr = fNodeIDMap->find(elementId);
+ if (theAttr == null)
+ return null;
+
+ return theAttr->getOwnerElement();
}
1.18 +9 -5 xml-xerces/c/src/dom/DocumentImpl.hpp
Index: DocumentImpl.hpp
===================================================================
RCS file: /home/cvs/xml-xerces/c/src/dom/DocumentImpl.hpp,v
retrieving revision 1.17
retrieving revision 1.18
diff -u -r1.17 -r1.18
--- DocumentImpl.hpp 2000/05/09 00:22:32 1.17
+++ DocumentImpl.hpp 2000/05/13 03:51:17 1.18
@@ -58,7 +58,7 @@
*/
/*
- * $Id: DocumentImpl.hpp,v 1.17 2000/05/09 00:22:32 andyh Exp $
+ * $Id: DocumentImpl.hpp,v 1.18 2000/05/13 03:51:17 andyh Exp $
*/
//
@@ -98,6 +98,7 @@
class NodeFilterImpl;
class DOM_DOMImplementation;
class DOMString;
+class NodeIDMap;
typedef RefVectorOf<NodeIteratorImpl> NodeIterators;
typedef RefVectorOf<TreeWalkerImpl> TreeWalkers;
@@ -114,6 +115,7 @@
DocumentTypeImpl *docType;
ElementImpl *docElement;
DStringPool *namePool;
+ NodeIDMap *fNodeIDMap; // for use by GetElementsById().
NodeIterators *iterators;
TreeWalkers *treeWalkers;
@@ -164,17 +166,19 @@
//Introduced in DOM Level 2
virtual NodeImpl *importNode(NodeImpl *source, bool deep);
virtual ElementImpl *createElementNS(const DOMString &namespaceURI,
- const DOMString &qualifiedName);
+ const DOMString &qualifiedName);
virtual AttrImpl *createAttributeNS(const DOMString &namespaceURI,
- const DOMString &qualifiedName);
+ const DOMString &qualifiedName);
virtual DeepNodeListImpl *getElementsByTagNameNS(const DOMString &namespaceURI,
- const DOMString &localName);
+ const DOMString &localName);
virtual ElementImpl *getElementById(const DOMString &elementId);
//Return the index > 0 of ':' in the given qualified name qName="prefix:localName".
//Return 0 if there is no ':', or -1 if qName is malformed such as ":abcd".
static int indexofQualifiedName(const DOMString & qName);
- static bool isKidOK(NodeImpl *parent, NodeImpl *child);
+ static bool isKidOK(NodeImpl *parent, NodeImpl *child);
+
+ inline NodeIDMap * getNodeIDMap() {return fNodeIDMap;};
};
#endif
1.25 +3 -1 xml-xerces/c/src/dom/NodeImpl.cpp
Index: NodeImpl.cpp
===================================================================
RCS file: /home/cvs/xml-xerces/c/src/dom/NodeImpl.cpp,v
retrieving revision 1.24
retrieving revision 1.25
diff -u -r1.24 -r1.25
--- NodeImpl.cpp 2000/05/11 00:42:28 1.24
+++ NodeImpl.cpp 2000/05/13 03:51:17 1.25
@@ -55,7 +55,7 @@
*/
/*
- * $Id: NodeImpl.cpp,v 1.24 2000/05/11 00:42:28 andyh Exp $
+ * $Id: NodeImpl.cpp,v 1.25 2000/05/13 03:51:17 andyh Exp $
*/
// This class doesn't support having any children, and implements the behavior
@@ -85,6 +85,8 @@
const unsigned short NodeImpl::SPECIFIED = 0x1<<5;
const unsigned short NodeImpl::IGNORABLEWS = 0x1<<6;
const unsigned short NodeImpl::SETVALUE = 0x1<<7;
+const unsigned short NodeImpl::ID_ATTR = 0x1<<8;
+
NodeImpl::NodeImpl(DocumentImpl *ownerDoc)
{
1.18 +11 -1 xml-xerces/c/src/dom/NodeImpl.hpp
Index: NodeImpl.hpp
===================================================================
RCS file: /home/cvs/xml-xerces/c/src/dom/NodeImpl.hpp,v
retrieving revision 1.17
retrieving revision 1.18
diff -u -r1.17 -r1.18
--- NodeImpl.hpp 2000/04/28 00:31:45 1.17
+++ NodeImpl.hpp 2000/05/13 03:51:17 1.18
@@ -58,7 +58,7 @@
*/
/*
- * $Id: NodeImpl.hpp,v 1.17 2000/04/28 00:31:45 lehors Exp $
+ * $Id: NodeImpl.hpp,v 1.18 2000/05/13 03:51:17 andyh Exp $
*/
//
@@ -125,6 +125,7 @@
static const unsigned short SPECIFIED;
static const unsigned short IGNORABLEWS;
static const unsigned short SETVALUE;
+ static const unsigned short ID_ATTR;
void *userData;
@@ -269,6 +270,15 @@
inline void setValue(bool value) {
flags = (value ? flags | SETVALUE : flags & ~SETVALUE);
}
+
+ inline bool idAttr() {
+ return (flags & ID_ATTR) != 0;
+ }
+
+ inline void idAttr(bool value) {
+ flags = (value ? flags | ID_ATTR : flags & ~ID_ATTR);
+ }
+
};
1.1 xml-xerces/c/src/dom/NodeIDMap.cpp
Index: NodeIDMap.cpp
===================================================================
/*
* The Apache Software License, Version 1.1
*
* Copyright (c) 1999-2000 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution,
* if any, must include the following acknowledgment:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgment may appear in the software itself,
* if and wherever such third-party acknowledgments normally appear.
*
* 4. The names "Xerces" and "Apache Software Foundation" must
* not be used to endorse or promote products derived from this
* software without prior written permission. For written
* permission, please contact apache\@apache.org.
*
* 5. Products derived from this software may not be called "Apache",
* nor may "Apache" appear in their name, without prior written
* permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation, and was
* originally based on software copyright (c) 1999, International
* Business Machines, Inc., http://www.ibm.com . For more information
* on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*/
#include "DOMString.hpp"
#include "AttrImpl.hpp"
#include "NodeIDMap.hpp"
#include <util/XMLString.hpp>
static const int gPrimes[] = {997, 9973, 99991, 999983, 0 }; // To do - add a few more.
static const float gMaxFill = 0.8f; // The maximum fraction of the total
// table entries to consume before exanding.
NodeIDMap::NodeIDMap(int initialSize)
{
for (fSizeIndex = 0; gPrimes[fSizeIndex] < initialSize; fSizeIndex++);
{
if (gPrimes[fSizeIndex] == 0)
{
// We need a bigger size than the largest available one.
// Big trouble.
fSizeIndex--;
throw "NodeIDMap::NodeIDMap - big trouble.";
}
}
fSize = gPrimes[fSizeIndex];
fNumEntries = 0;
fMaxEntries = unsigned long(float(fSize) * gMaxFill);
fTable = new AttrImpl *[fSize];
unsigned int i;
for (i=0; i<fSize; i++)
fTable[i] = 0;
};
NodeIDMap::~NodeIDMap()
{
delete[] fTable;
fTable = 0;
};
void NodeIDMap::add(AttrImpl *attr)
{
//
// If the table is getting too full, grow it. We arbitrarily limit
// the table to 80 full, which should limit the average number of
// rehashes to a reasonable value.
//
if (fNumEntries >= fMaxEntries)
growTable();
fNumEntries++;
//
// Hash the value string from the ID attribute being added to the table
// 0 < Initial hash value < table size.
// An initial hash of zero would cause the rehash to fail.
//
DOMString id=attr->getValue();
unsigned int initalHash = XMLString::hashN(id.rawBuffer(), id.length(), fSize-1);
initalHash++;
unsigned int currentHash = initalHash;
//
// Loop looking for an empty slot for this ID.
// Don't even bother checking to see if the ID is already there -
// the table is only filled by the parser from valid documents, which
// can not have duplicates. Behavior of invalid docs is not defined.
//
while (true)
{
AttrImpl *tableSlot = fTable[currentHash];
if (tableSlot == 0 ||
tableSlot == (AttrImpl *)-1)
break;
currentHash += initalHash; // rehash
}
//
// We've found our slot. Stick the pointer to the attr into it.
//
fTable[currentHash] = attr;
};
void NodeIDMap::remove(AttrImpl *attr)
{
//
// Hash the value string from the ID attribute being added to the table
// 0 < Initial hash value < table size.
// An initial hash of zero would cause the rehash to fail.
//
DOMString id=attr->getValue();
unsigned int initalHash = XMLString::hashN(id.rawBuffer(), id.length(), fSize-1);
initalHash++;
unsigned int currentHash = initalHash;
//
// Loop looking for a slot pointing to an attr with this id.
//
while (true)
{
AttrImpl *tableSlot = fTable[currentHash];
if (tableSlot == 0)
{
// There is no matching entry in the table
return;
}
if (tableSlot == (AttrImpl *)-1)
{
// This slot contains an entry for a removed attribute.
// We need to keep looking - the one we are after could
// still show up later on.
continue;
}
if (tableSlot == attr)
{
// Found the attribute. Set the slot to -1 to indicate
// that it was once used, meaning that lookups, while never
// matching here, can not stop either, but must rehash again
// and continue searching.
fTable[currentHash] = (AttrImpl *)-1;
return;
}
currentHash += initalHash; // rehash.
}
};
AttrImpl *NodeIDMap::find(const DOMString &id)
{
//
// Get the hashcode for the supplied string.
//
unsigned int initalHash = XMLString::hashN(id.rawBuffer(), id.length(), fSize-1);
initalHash++;
unsigned int currentHash = initalHash;
//
// Loop looking for a slot pointing to an attr with this id.
//
while (true)
{
AttrImpl *tableSlot = fTable[currentHash];
if (tableSlot == 0)
{
// There is no matching entry in the table
return 0;
}
if (tableSlot == (AttrImpl *)-1)
{
// This slot contains an entry for a removed attribute.
// We need to keep looking - the one we are after could
// still show up later on.
continue;
}
if (tableSlot->getValue().equals(id))
return tableSlot;
currentHash += initalHash; // rehash
}
return 0; // Never gets here, but keeps some compilers happy.
};
//
// Grow the table to the next larger size.
// It has gotten too full for efficient operation.
// (We never fill it all the way)
//
void NodeIDMap::growTable()
{
AttrImpl **oldTable = fTable;
unsigned int oldSize = fSize;
//
// Figure the new table size.
//
fSizeIndex++;
unsigned int fSize = gPrimes[fSizeIndex];
if (fSize == 0)
{
// We need to grow bigger than the largest available size.
// Big trouble.
fSizeIndex--;
throw "NodeIDMap::growTable - big trouble.";
}
//
// Allocate the new table.
//
fTable = new AttrImpl *[fSize];
unsigned int i;
for (i=0; i<fSize; i++)
fTable[i] = 0;
fMaxEntries = unsigned long(float(fSize) * gMaxFill);
//
// Move entries over from the old table to the new one.
//
for (i=0; i<oldSize; i++)
add(oldTable[i]);
delete [] oldTable;
};
1.1 xml-xerces/c/src/dom/NodeIDMap.hpp
Index: NodeIDMap.hpp
===================================================================
#ifndef NodeIDMap_HEADER_GUARD_
#define NodeIDMap_HEADER_GUARD_
/*
* The Apache Software License, Version 1.1
*
* Copyright (c) 1999-2000 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution,
* if any, must include the following acknowledgment:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgment may appear in the software itself,
* if and wherever such third-party acknowledgments normally appear.
*
* 4. The names "Xerces" and "Apache Software Foundation" must
* not be used to endorse or promote products derived from this
* software without prior written permission. For written
* permission, please contact apache\@apache.org.
*
* 5. Products derived from this software may not be called "Apache",
* nor may "Apache" appear in their name, without prior written
* permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation, and was
* originally based on software copyright (c) 1999, International
* Business Machines, Inc., http://www.ibm.com . For more information
* on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*/
//
// This file is part of the internal implementation of the C++ XML DOM.
// It should NOT be included or used directly by application programs.
//
// Applications should include the file <dom/DOM.hpp> for the entire
// DOM API, or DOM_*.hpp for individual DOM classes, where the class
// name is substituded for the *.
//
//
// Class NodeIDMap is a hash table that is used in the implementation of
// of DOM_Document::getElementsByID().
//
// Why Yet Another HashTable implementation? Becuase it can be significantly
// smaller when tuned for this exact usage, and the generic RefHashTableOf
// from the xerces utils project is not a paricularly good fit.
//
class AttrImpl;
class DOMString;
class NodeIDMap {
public:
NodeIDMap(int initialSize); // Create a new hash table, sized to hold "initialSize"
// Entries. It will automatically grow if need be.
virtual ~NodeIDMap();
private:
NodeIDMap(const NodeIDMap &other); // No copy, assignement, comparison.
NodeIDMap &operator = (const NodeIDMap &other);
bool operator == (const NodeIDMap &other);
public:
void add(AttrImpl *attr); // Add the specified attribute to the table.
void remove(AttrImpl *other); // Remove the specified attribute.
// Does nothing if the node is not in the table.
AttrImpl *find(const DOMString &ID); // Find the attribute node in the table with this ID
private:
void growTable();
private:
AttrImpl **fTable;
unsigned int fSizeIndex; // Index of the current table size in the
// array of possible table sizes.
unsigned int fSize; // The current size of the table array
// (number of slots, not bytes.)
unsigned int fNumEntries; // The number of entries used.
unsigned int fMaxEntries; // The max number of entries to use before
// growing the table.
};
#endif