dbertoni 01/05/10 10:47:53
Modified: c/src/PlatformSupport XalanDOMStringPool.cpp
XalanDOMStringPool.hpp
Log:
New hashtable and allocator implementations.
Revision Changes Path
1.10 +32 -80 xml-xalan/c/src/PlatformSupport/XalanDOMStringPool.cpp
Index: XalanDOMStringPool.cpp
===================================================================
RCS file: /home/cvs/xml-xalan/c/src/PlatformSupport/XalanDOMStringPool.cpp,v
retrieving revision 1.9
retrieving revision 1.10
diff -u -r1.9 -r1.10
--- XalanDOMStringPool.cpp 2001/04/30 20:56:23 1.9
+++ XalanDOMStringPool.cpp 2001/05/10 17:47:48 1.10
@@ -64,53 +64,14 @@
-bool
-XalanDOMStringPool::StringKey::operator<(const StringKey& theRHS) const
+XalanDOMStringPool::XalanDOMStringPool(
+ unsigned int theBlockSize,
+ unsigned int theBucketCount,
+ unsigned int theBucketSize) :
+ m_stringAllocator(theBlockSize),
+ m_stringCount(0),
+ m_hashTable(theBucketCount, theBucketSize)
{
- // Note that we don't really need lexicographical ordering, so this
- // is much cheaper.
- if (m_length < theRHS.m_length)
- {
- return true;
- }
- else if (m_length > theRHS.m_length)
- {
- return false;
- }
- else
- {
- unsigned int i = 0;
-
- while(i < m_length)
- {
- const XalanDOMChar theLHSChar = m_string[i];
- const XalanDOMChar theRHSChar = theRHS.m_string[i];
-
- if (theLHSChar < theRHSChar)
- {
- return true;
- }
- else if (theLHSChar > theRHSChar)
- {
- return false;
- }
- else
- {
- ++i;
- }
- }
-
- // They're equal, so return false...
- return false;
- }
-}
-
-
-
-XalanDOMStringPool::XalanDOMStringPool() :
- m_strings(),
- m_index()
-{
}
@@ -124,21 +85,21 @@
void
XalanDOMStringPool::clear()
{
- // Clear by swapping things, which is
- // guaranteed to free up all allocated memory.
- XalanDOMStringCollectionType().swap(m_strings);
+ m_stringAllocator.reset();
+
+ m_hashTable.clear();
- IndexMapType().swap(m_index);
+ m_stringCount = 0;
}
-XalanDOMStringPool::size_type
+unsigned int
XalanDOMStringPool::size() const
{
- assert(m_strings.size() == m_index.size());
+ assert(m_stringCount == m_hashTable.size());
- return m_strings.size();
+ return m_stringCount;
}
@@ -156,7 +117,7 @@
const XalanDOMChar* theString,
unsigned int theLength)
{
- assert(m_strings.size() == m_index.size());
+ assert(m_stringCount == m_hashTable.size());
if (theString == 0 || *theString == 0)
{
@@ -166,44 +127,35 @@
{
const unsigned int theActualLength = theLength ==
unsigned(-1) ? length(theString) : theLength;
-#if defined(XALAN_NO_NAMESPACES)
- typedef pair<IndexMapType::iterator, bool>
InsertPairType;
-#else
- typedef std::pair<IndexMapType::iterator, bool>
InsertPairType;
-#endif
-
- // Insert an entry into the index map.
- InsertPairType i =
- m_index.insert(
- IndexMapType::value_type(
- IndexMapType::key_type(theString,
theActualLength),
- (const XalanDOMString*)0));
+ unsigned int theBucketIndex;
- // Was it added?
- if (i.second == false)
+ const XalanDOMString* theTableString =
m_hashTable.find(theString, theActualLength, &theBucketIndex);
+
+ if (theTableString != 0)
{
- // Already there, so return it...
- return *(*(i.first)).second;
+ return *theTableString;
}
else
{
// Not found, so insert the string...
- const XalanDOMStringCollectionType::iterator
theIterator =
- m_strings.insert(m_strings.end(),
XalanDOMString());
+ XalanDOMString* const theNewString =
+ m_stringAllocator.allocateBlock();
+ assert(theNewString != 0);
+
+ new(theNewString) XalanDOMString(theString,
theActualLength);
- XalanDOMString& theNewString = *theIterator;
+ m_stringAllocator.commitAllocation(theNewString);
- assign(theNewString, theString, theActualLength);
+ assert(theActualLength == length(*theNewString));
- assert(theActualLength == length(theNewString));
+ ++m_stringCount;
- // Update the index entry that we just inserted...
- (*(i.first)).second = &theNewString;
-
(*(i.first)).first.changePointer(toCharArray(theNewString));
+ // Insert the string into the hash table...
+ m_hashTable.insert(*theNewString, theBucketIndex);
- assert(m_strings.size() == m_index.size());
+ assert(m_stringCount == m_hashTable.size());
- return theNewString;
+ return *theNewString;
}
}
}
1.8 +43 -78 xml-xalan/c/src/PlatformSupport/XalanDOMStringPool.hpp
Index: XalanDOMStringPool.hpp
===================================================================
RCS file: /home/cvs/xml-xalan/c/src/PlatformSupport/XalanDOMStringPool.hpp,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -r1.7 -r1.8
--- XalanDOMStringPool.hpp 2001/04/27 19:19:26 1.7
+++ XalanDOMStringPool.hpp 2001/05/10 17:47:49 1.8
@@ -69,7 +69,9 @@
+#include <PlatformSupport/ArenaAllocator.hpp>
#include <PlatformSupport/DOMStringHelper.hpp>
+#include <PlatformSupport/XalanDOMStringHashTable.hpp>
@@ -77,81 +79,22 @@
{
public:
- class XALAN_PLATFORMSUPPORT_EXPORT StringKey
- {
- public:
-
- explicit
- StringKey();
-
- StringKey(
- const XalanDOMChar* theString,
- unsigned int theLength) :
- m_string(theString),
- m_length(theLength)
- {
- }
-
- ~StringKey()
- {
- }
-
- bool
- operator<(const StringKey& theRHS) const;
-
- /*
- * OK, this is a really big hack. The problem is that we index
- * the strings in the pool by const XalanDOMChar* which are not
- * necessarily null-terminated. An added problem is that is too
- * inefficient to search the map for the string, then add it if
it
- * wasn't found. Instead, we want to insert a new entry in the
- * map, then figure out from the result of the insert whether or
- * not the entry was found. This call allows us to change the
- * pointer for the key to the persistent pointer from the new
- * string that we created, instead of the pointer that was
passed
- * into the call, which is not persistent. This won't screw up
- * the map since the map is ordered on the _value_ of the string
- * and not the pointer itself.
- *
- * @param theNewPointer The new pointer value to use for the
key.
- */
- void
- changePointer(const XalanDOMChar* theNewPointer) const
- {
- assert(theNewPointer != 0 && equals(theNewPointer,
m_string, m_length));
-#if defined(XALAN_NO_MUTABLE)
- ((StringKey*)this)->m_string = theNewPointer;
-#else
- m_string = theNewPointer;
-#endif
- }
-
- private:
-
- mutable const XalanDOMChar* m_string;
-
- unsigned int m_length;
- };
-
-#if defined(XALAN_NO_NAMESPACES)
- typedef deque<XalanDOMString> XalanDOMStringCollectionType;
-
- typedef map<
- StringKey,
- const XalanDOMString*,
- less<StringKey> > IndexMapType;
-#else
- typedef std::deque<XalanDOMString> XalanDOMStringCollectionType;
-
- typedef std::map<
- StringKey,
- const XalanDOMString*> IndexMapType;
-#endif
-
- typedef XalanDOMStringCollectionType::size_type size_type;
+ enum { eDefaultBlockSize = 1024,
+ eDefaultBucketCount =
XalanDOMStringHashTable::eDefaultBucketCount,
+ eDefaultBucketSize =
XalanDOMStringHashTable::eDefaultBucketSize };
+ /**
+ * Create a string pool.
+ *
+ * @param theBlockSize The block size for the allocator.
+ * @param theBucketCount The number of buckets to use for the hash
table. This should be a prime number for best results.
+ * @param theBucketSize The initial size of each bucket in the hash
table.
+ */
explicit
- XalanDOMStringPool();
+ XalanDOMStringPool(
+ unsigned int theBlockSize = eDefaultBlockSize,
+ unsigned int theBucketCount = eDefaultBucketCount,
+ unsigned int theBucketSize = eDefaultBucketSize);
virtual
~XalanDOMStringPool();
@@ -159,7 +102,6 @@
/**
* Clear the pool.
*
- * @param thePair key-value pair
*/
virtual void
clear();
@@ -167,9 +109,9 @@
/**
* Get the number of strings in the pool
*
- * @param thePair key-value pair
+ * @return the size of the pool.
*/
- virtual size_type
+ virtual unsigned int
size() const;
/**
@@ -193,6 +135,18 @@
const XalanDOMChar* theString,
unsigned int theLength =
unsigned(-1));
+ /**
+ * Get a reference to the pool's hash table. Useful for diagnostic
+ * purposes.
+ *
+ * @return a const reference to the hash table.
+ */
+ const XalanDOMStringHashTable&
+ getHashTable() const
+ {
+ return m_hashTable;
+ }
+
private:
// Not implemented, for now...
@@ -204,10 +158,21 @@
bool
operator==(const XalanDOMStringPool&) const;
+#if defined(XALAN_NO_DEFAULT_TEMPLATE_ARGUMENTS)
+ typedef ArenaBlock<XalanDOMString> ArenaBlockType;
+
+ typedef ArenaAllocator<XalanDOMString,
+ ArenaBlockType>
ArenaAllocatorType;
+#else
+ typedef ArenaAllocator<XalanDOMString> ArenaAllocatorType;
+#endif
+
// Data members...
- XalanDOMStringCollectionType m_strings;
+ ArenaAllocatorType m_stringAllocator;
+
+ unsigned int m_stringCount;
- IndexMapType m_index;
+ XalanDOMStringHashTable m_hashTable;
static const XalanDOMString s_emptyString;
};
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
