You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@xerces.apache.org by am...@apache.org on 2005/02/02 10:27:54 UTC
cvs commit: xml-xerces/c/src/xercesc/util RefHash2KeysTableOf.c RefHash2KeysTableOf.hpp
amassari 2005/02/02 01:27:54
Modified: c/src/xercesc/util RefHash2KeysTableOf.c
RefHash2KeysTableOf.hpp
Log:
Added rehashing capabilities
Revision Changes Path
1.15 +121 -57 xml-xerces/c/src/xercesc/util/RefHash2KeysTableOf.c
Index: RefHash2KeysTableOf.c
===================================================================
RCS file: /home/cvs/xml-xerces/c/src/xercesc/util/RefHash2KeysTableOf.c,v
retrieving revision 1.14
retrieving revision 1.15
diff -u -r1.14 -r1.15
--- RefHash2KeysTableOf.c 30 Dec 2004 14:52:34 -0000 1.14
+++ RefHash2KeysTableOf.c 2 Feb 2005 09:27:53 -0000 1.15
@@ -16,6 +16,9 @@
/**
* $Log$
+ * Revision 1.15 2005/02/02 09:27:53 amassari
+ * Added rehashing capabilities
+ *
* Revision 1.14 2004/12/30 14:52:34 amassari
* Added API to remove all entries having the same primary key
*
@@ -98,6 +101,7 @@
, fAdoptedElems(adoptElems)
, fBucketList(0)
, fHashModulus(modulus)
+ , fCount(0)
, fHash(0)
{
initialize(modulus);
@@ -115,6 +119,7 @@
, fAdoptedElems(adoptElems)
, fBucketList(0)
, fHashModulus(modulus)
+ , fCount(0)
, fHash(0)
{
initialize(modulus);
@@ -129,6 +134,7 @@
, fAdoptedElems(true)
, fBucketList(0)
, fHashModulus(modulus)
+ , fCount(0)
, fHash(0)
{
initialize(modulus);
@@ -167,13 +173,7 @@
// ---------------------------------------------------------------------------
template <class TVal> bool RefHash2KeysTableOf<TVal>::isEmpty() const
{
- // Just check the bucket list for non-empty elements
- for (unsigned int buckInd = 0; buckInd < fHashModulus; buckInd++)
- {
- if (fBucketList[buckInd] != 0)
- return false;
- }
- return true;
+ return (fCount==0);
}
template <class TVal> bool RefHash2KeysTableOf<TVal>::
@@ -187,8 +187,52 @@
template <class TVal> void RefHash2KeysTableOf<TVal>::
removeKey(const void* const key1, const int key2)
{
- unsigned int hashVal;
- removeBucketElem(key1, key2, hashVal);
+ // Hash the key
+ unsigned int hashVal = fHash->getHashVal(key1, fHashModulus);
+ assert(hashVal < fHashModulus);
+
+ //
+ // Search the given bucket for this key. Keep up with the previous
+ // element so we can patch around it.
+ //
+ RefHash2KeysTableBucketElem<TVal>* curElem = fBucketList[hashVal];
+ RefHash2KeysTableBucketElem<TVal>* lastElem = 0;
+
+ while (curElem)
+ {
+ if (fHash->equals(key1, curElem->fKey1) && (key2==curElem->fKey2))
+ {
+ if (!lastElem)
+ {
+ // It was the first in the bucket
+ fBucketList[hashVal] = curElem->fNext;
+ }
+ else
+ {
+ // Patch around the current element
+ lastElem->fNext = curElem->fNext;
+ }
+
+ // If we adopted the elements, then delete the data
+ if (fAdoptedElems)
+ delete curElem->fData;
+
+ // Delete the current element
+ // delete curElem;
+ // destructor is empty...
+ // curElem->~RefHash2KeysTableBucketElem();
+ fMemoryManager->deallocate(curElem);
+ fCount--;
+ return;
+ }
+
+ // Move both pointers upwards
+ lastElem = curElem;
+ curElem = curElem->fNext;
+ }
+
+ // We never found that key
+ ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager);
}
template <class TVal> void RefHash2KeysTableOf<TVal>::
@@ -232,6 +276,7 @@
// destructor is empty...
// curElem->~RefHash2KeysTableBucketElem();
fMemoryManager->deallocate(toBeDeleted);
+ fCount--;
}
else
{
@@ -244,6 +289,9 @@
template <class TVal> void RefHash2KeysTableOf<TVal>::removeAll()
{
+ if(isEmpty())
+ return;
+
// Clean up the buckets first
for (unsigned int buckInd = 0; buckInd < fHashModulus; buckInd++)
{
@@ -272,6 +320,7 @@
// Clean out this entry
fBucketList[buckInd] = 0;
}
+ fCount=0;
}
// this function transfer the data from key1 to key2
@@ -304,7 +353,24 @@
lastElem->fNext = curElem->fNext;
}
- put(key2, curElem->fKey2, curElem->fData);
+ // this code comes from put(), but it doesn't update fCount
+ unsigned int hashVal2;
+ RefHash2KeysTableBucketElem<TVal>* newBucket = findBucketElem(key2, curElem->fKey2, hashVal2);
+ if (newBucket)
+ {
+ if (fAdoptedElems)
+ delete newBucket->fData;
+ newBucket->fData = curElem->fData;
+ newBucket->fKey1 = key2;
+ newBucket->fKey2 = curElem->fKey2;
+ }
+ else
+ {
+ newBucket =
+ new (fMemoryManager->allocate(sizeof(RefHash2KeysTableBucketElem<TVal>)))
+ RefHash2KeysTableBucketElem<TVal>(key2, curElem->fKey2, curElem->fData, fBucketList[hashVal2]);
+ fBucketList[hashVal2] = newBucket;
+ }
RefHash2KeysTableBucketElem<TVal>* elemToDelete = curElem;
@@ -315,7 +381,7 @@
// delete elemToDelete;
// destructor is empty...
// curElem->~RefHash2KeysTableBucketElem();
- fMemoryManager->deallocate(elemToDelete);
+ fMemoryManager->deallocate(elemToDelete);
}
else
{
@@ -367,6 +433,13 @@
// ---------------------------------------------------------------------------
template <class TVal> void RefHash2KeysTableOf<TVal>::put(void* key1, int key2, TVal* const valueToAdopt)
{
+ // Apply 4 load factor to find threshold.
+ unsigned int threshold = fHashModulus * 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;
RefHash2KeysTableBucketElem<TVal>* newBucket = findBucketElem(key1, key2, hashVal);
@@ -389,6 +462,7 @@
new (fMemoryManager->allocate(sizeof(RefHash2KeysTableBucketElem<TVal>)))
RefHash2KeysTableBucketElem<TVal>(key1, key2, valueToAdopt, fBucketList[hashVal]);
fBucketList[hashVal] = newBucket;
+ fCount++;
}
}
@@ -437,59 +511,52 @@
template <class TVal> void RefHash2KeysTableOf<TVal>::
-removeBucketElem(const void* const key1, const int key2, unsigned int& hashVal)
+rehash()
{
- // Hash the key
- hashVal = fHash->getHashVal(key1, fHashModulus);
- assert(hashVal < fHashModulus);
-
- //
- // Search the given bucket for this key. Keep up with the previous
- // element so we can patch around it.
- //
- RefHash2KeysTableBucketElem<TVal>* curElem = fBucketList[hashVal];
- RefHash2KeysTableBucketElem<TVal>* lastElem = 0;
-
- while (curElem)
+ unsigned int index;
+ unsigned int oldMod = fHashModulus;
+ fHashModulus = (fHashModulus * 8) + 1;
+
+ RefHash2KeysTableBucketElem<TVal>** oldBucketList = fBucketList;
+
+ fBucketList = (RefHash2KeysTableBucketElem<TVal>**) fMemoryManager->allocate
+ (
+ fHashModulus * sizeof(RefHash2KeysTableBucketElem<TVal>*)
+ );//new RefHash2KeysTableBucketElem<TVal>*[fHashModulus];
+ for (index = 0; index < fHashModulus; index++)
+ fBucketList[index] = 0;
+
+
+ // Rehash all existing entries.
+ for (index = 0; index < oldMod; index++)
{
- if (fHash->equals(key1, curElem->fKey1) && (key2==curElem->fKey2))
+ // Get the bucket list head for this entry
+ RefHash2KeysTableBucketElem<TVal>* curElem = oldBucketList[index];
+ RefHash2KeysTableBucketElem<TVal>* nextElem;
+ while (curElem)
{
- if (!lastElem)
- {
- // It was the first in the bucket
- fBucketList[hashVal] = curElem->fNext;
- }
- else
- {
- // Patch around the current element
- lastElem->fNext = curElem->fNext;
- }
-
- // If we adopted the elements, then delete the data
- if (fAdoptedElems)
- delete curElem->fData;
+ // Save the next element before we detach this one
+ nextElem = curElem->fNext;
- // Delete the current element
- // delete curElem;
- // destructor is empty...
- // curElem->~RefHash2KeysTableBucketElem();
- fMemoryManager->deallocate(curElem);
+ unsigned int hashVal = fHash->getHashVal(curElem->fKey1, fHashModulus, fMemoryManager);
+ assert(hashVal < fHashModulus);
- return;
+ RefHash2KeysTableBucketElem<TVal>* newHeadElem = fBucketList[hashVal];
+
+ // Insert at the start of this bucket's list.
+ curElem->fNext = newHeadElem;
+ fBucketList[hashVal] = curElem;
+
+ curElem = nextElem;
}
-
- // Move both pointers upwards
- lastElem = curElem;
- curElem = curElem->fNext;
}
-
- // We never found that key
- ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager);
+
+ fMemoryManager->deallocate(oldBucketList);//delete[] oldBucketList;
+
}
-
// ---------------------------------------------------------------------------
// RefHash2KeysTableOfEnumerator: Constructors and Destructor
// ---------------------------------------------------------------------------
@@ -625,11 +692,8 @@
return;
// Else find the next non-empty bucket
- while (true)
+ while (fToEnum->fBucketList[fCurHash]==0)
{
- if (fToEnum->fBucketList[fCurHash])
- break;
-
// Bump to the next hash value. If we max out return
fCurHash++;
if (fCurHash == fToEnum->fHashModulus)
1.15 +13 -6 xml-xerces/c/src/xercesc/util/RefHash2KeysTableOf.hpp
Index: RefHash2KeysTableOf.hpp
===================================================================
RCS file: /home/cvs/xml-xerces/c/src/xercesc/util/RefHash2KeysTableOf.hpp,v
retrieving revision 1.14
retrieving revision 1.15
diff -u -r1.14 -r1.15
--- RefHash2KeysTableOf.hpp 30 Dec 2004 14:52:34 -0000 1.14
+++ RefHash2KeysTableOf.hpp 2 Feb 2005 09:27:54 -0000 1.15
@@ -16,6 +16,9 @@
/*
* $Log$
+ * Revision 1.15 2005/02/02 09:27:54 amassari
+ * Added rehashing capabilities
+ *
* Revision 1.14 2004/12/30 14:52:34 amassari
* Added API to remove all entries having the same primary key
*
@@ -204,8 +207,8 @@
// -----------------------------------------------------------------------
RefHash2KeysTableBucketElem<TVal>* findBucketElem(const void* const key1, const int key2, unsigned int& hashVal);
const RefHash2KeysTableBucketElem<TVal>* findBucketElem(const void* const key1, const int key2, unsigned int& hashVal) const;
- void removeBucketElem(const void* const key1, const int key2, unsigned int& hashVal);
- void initialize(const unsigned int modulus);
+ void initialize(const unsigned int modulus);
+ void rehash();
// -----------------------------------------------------------------------
@@ -223,15 +226,19 @@
// fHashModulus
// The modulus used for this hash table, to hash the keys. This is
// also the number of elements in the bucket list.
- //
- // fHash
- // The hasher for the key1 data type.
+ //
+ // fCount
+ // The number of elements currently in the map
+ //
+ // fHash
+ // The hasher for the key1 data type.
// -----------------------------------------------------------------------
MemoryManager* fMemoryManager;
bool fAdoptedElems;
RefHash2KeysTableBucketElem<TVal>** fBucketList;
unsigned int fHashModulus;
- HashBase* fHash;
+ 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