You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@xerces.apache.org by ga...@apache.org on 2003/05/15 12:37:09 UTC
cvs commit: xml-xerces/c/src/xercesc/util RefHashTableOf.c RefHashTableOf.hpp
gareth 2003/05/15 03:37:09
Modified: c/src/xercesc/util RefHashTableOf.c RefHashTableOf.hpp
Log:
Optimization. We now resize the hash when appropriate. Patch by Nathan Codding.
Revision Changes Path
1.7 +64 -3 xml-xerces/c/src/xercesc/util/RefHashTableOf.c
Index: RefHashTableOf.c
===================================================================
RCS file: /home/cvs/xml-xerces/c/src/xercesc/util/RefHashTableOf.c,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -r1.6 -r1.7
--- RefHashTableOf.c 4 Nov 2002 15:22:04 -0000 1.6
+++ RefHashTableOf.c 15 May 2003 10:37:08 -0000 1.7
@@ -56,6 +56,9 @@
/**
* $Log$
+ * Revision 1.7 2003/05/15 10:37:08 gareth
+ * Optimization. We now resize the hash when appropriate. Patch by Nathan Codding.
+ *
* Revision 1.6 2002/11/04 15:22:04 tng
* C++ Namespace Support.
*
@@ -130,7 +133,7 @@
// RefHashTableOf: Constructors and Destructor
// ---------------------------------------------------------------------------
template <class TVal> RefHashTableOf<TVal>::RefHashTableOf(const unsigned int modulus, const bool adoptElems)
- : fAdoptedElems(adoptElems), fBucketList(0), fHashModulus(modulus)
+ : fAdoptedElems(adoptElems), fBucketList(0), fHashModulus(modulus), fInitialModulus(modulus), fCount(0)
{
initialize(modulus);
@@ -139,7 +142,7 @@
}
template <class TVal> RefHashTableOf<TVal>::RefHashTableOf(const unsigned int modulus, const bool adoptElems, HashBase* hashBase)
- : fAdoptedElems(adoptElems), fBucketList(0), fHashModulus(modulus)
+ : fAdoptedElems(adoptElems), fBucketList(0), fHashModulus(modulus), fInitialModulus(modulus), fCount(0)
{
initialize(modulus);
// set hasher
@@ -147,7 +150,7 @@
}
template <class TVal> RefHashTableOf<TVal>::RefHashTableOf(const unsigned int modulus)
- : fAdoptedElems(true), fBucketList(0), fHashModulus(modulus)
+ : fAdoptedElems(true), fBucketList(0), fHashModulus(modulus), fInitialModulus(modulus), fCount(0)
{
initialize(modulus);
@@ -233,6 +236,8 @@
// Clean out this entry
fBucketList[buckInd] = 0;
}
+
+ fCount = 0;
}
// This method returns the data associated with a key. The key entry is deleted. The caller
@@ -313,6 +318,7 @@
if (fBucketList || fHash)
cleanup();
+ fHashModulus = fInitialModulus;
initialize(fHashModulus);
if (hashBase)
@@ -374,6 +380,14 @@
// ---------------------------------------------------------------------------
template <class TVal> void RefHashTableOf<TVal>::put(void* key, TVal* const valueToAdopt)
{
+
+ // Apply 0.75 load factor to find threshold.
+ unsigned int threshold = fHashModulus * 3 / 4;
+
+ // If we've grown too big, expand the table and rehash.
+ if (fCount >= threshold)
+ rehash();
+
// First see if the key exists already
unsigned int hashVal;
RefHashTableBucketElem<TVal>* newBucket = findBucketElem(key, hashVal);
@@ -394,6 +408,8 @@
newBucket = new RefHashTableBucketElem<TVal>(key, valueToAdopt, fBucketList[hashVal]);
fBucketList[hashVal] = newBucket;
}
+
+ fCount++;
}
@@ -401,6 +417,49 @@
// ---------------------------------------------------------------------------
// RefHashTableOf: Private methods
// ---------------------------------------------------------------------------
+template <class TVal> void RefHashTableOf<TVal>::
+rehash()
+{
+ unsigned int index;
+ unsigned int oldMod = fHashModulus;
+ fHashModulus *= 2;
+
+ RefHashTableBucketElem<TVal>** oldBucketList = fBucketList;
+
+ fBucketList = new RefHashTableBucketElem<TVal>*[fHashModulus];
+ for (index = 0; index < fHashModulus; index++)
+ fBucketList[index] = 0;
+
+
+ // Rehash all existing entries.
+ for (index = 0; index < oldMod; index++)
+ {
+ // Get the bucket list head for this entry
+ RefHashTableBucketElem<TVal>* curElem = oldBucketList[index];
+ RefHashTableBucketElem<TVal>* nextElem;
+ while (curElem)
+ {
+ // Save the next element before we detach this one
+ nextElem = curElem->fNext;
+
+ unsigned int hashVal = fHash->getHashVal(curElem->fKey, fHashModulus);
+ if (hashVal > fHashModulus)
+ ThrowXML(RuntimeException, XMLExcepts::HshTbl_BadHashFromKey);
+
+ RefHashTableBucketElem<TVal>* newHeadElem = fBucketList[hashVal];
+
+ // Insert at the start of this bucket's list.
+ curElem->fNext = newHeadElem;
+ fBucketList[hashVal] = curElem;
+
+ curElem = nextElem;
+ }
+ }
+
+ delete[] oldBucketList;
+
+}
+
template <class TVal> RefHashTableBucketElem<TVal>* RefHashTableOf<TVal>::
findBucketElem(const void* const key, unsigned int& hashVal)
{
@@ -479,6 +538,8 @@
// Delete the current element
delete curElem;
+ fCount--;
+
return;
}
1.7 +6 -0 xml-xerces/c/src/xercesc/util/RefHashTableOf.hpp
Index: RefHashTableOf.hpp
===================================================================
RCS file: /home/cvs/xml-xerces/c/src/xercesc/util/RefHashTableOf.hpp,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -r1.6 -r1.7
--- RefHashTableOf.hpp 4 Nov 2002 15:22:04 -0000 1.6
+++ RefHashTableOf.hpp 15 May 2003 10:37:08 -0000 1.7
@@ -56,6 +56,9 @@
/*
* $Log$
+ * Revision 1.7 2003/05/15 10:37:08 gareth
+ * Optimization. We now resize the hash when appropriate. Patch by Nathan Codding.
+ *
* Revision 1.6 2002/11/04 15:22:04 tng
* C++ Namespace Support.
*
@@ -220,6 +223,7 @@
const RefHashTableBucketElem<TVal>* findBucketElem(const void* const key, unsigned int& hashVal) const;
void removeBucketElem(const void* const key, unsigned int& hashVal);
void initialize(const unsigned int modulus);
+ void rehash();
// -----------------------------------------------------------------------
@@ -244,6 +248,8 @@
bool fAdoptedElems;
RefHashTableBucketElem<TVal>** fBucketList;
unsigned int fHashModulus;
+ unsigned int fInitialModulus;
+ unsigned int fCount;
HashBase* fHash;
};
---------------------------------------------------------------------
To unsubscribe, e-mail: xerces-cvs-unsubscribe@xml.apache.org
For additional commands, e-mail: xerces-cvs-help@xml.apache.org