"Fossies" - the Fresh Open Source Software Archive  

Source code changes of the file "util/Hashtable.h" between
muscle8.20.zip and muscle8.30.zip

About: MUSCLE (Multi User Server Client Linking Environment) is a messaging server and networking API. The included server program ("muscled") lets its clients message each other, and/or store information in its serverside hierarchical database.

Hashtable.h  (muscle8.20):Hashtable.h  (muscle8.30)
skipping to change at line 277 skipping to change at line 277
bool ContainsKey(const KeyType & key) const {return (this->GetEntry(this->Com puteHash(key), key) != NULL);} bool ContainsKey(const KeyType & key) const {return (this->GetEntry(this->Com puteHash(key), key) != NULL);}
/** Returns true iff the table contains a mapping with the given value. (O(n ) search time) /** Returns true iff the table contains a mapping with the given value. (O(n ) search time)
* @param value the value to inquire about * @param value the value to inquire about
*/ */
bool ContainsValue(const ValueType & value) const; bool ContainsValue(const ValueType & value) const;
/** Returns true iff this Hashtable has the same contents as (rhs). /** Returns true iff this Hashtable has the same contents as (rhs).
* @param rhs The table to compare this table against * @param rhs The table to compare this table against
* @param considerOrdering Whether the order of the key/value pairs within t he tables should be considered as part of "equality". Defaults to false. * @param considerOrdering Whether the order of the key/value pairs within t he tables should be considered as part of "equality". Defaults to false.
* @returns true iff (rhs) is equal to to (this), false if they differ. * @returns true iff (rhs) is equal to (this), false if they differ.
*/ */
bool IsEqualTo(const HashtableBase & rhs, bool considerOrdering = false) cons t; bool IsEqualTo(const HashtableBase & rhs, bool considerOrdering = false) cons t;
/** Returns true iff this Hashtable would have the same contents as (rhs) aft
er we called Put() on this Hashtable once.
* @param rhs the Hashtable to compare against a hypothetically modified ver
sion of this Hashtable.
* @param key the key to imagine placing into this table
* @param value the value to imagine placing into this table
* @param considerOrdering if true, the ordering of the key/value pairs in t
he two tables will be considered. Defaults to false.
* @returns true iff (rhs) would be equal to (*this after a single Put()), o
r false if they would differ.
*/
bool WouldBeEqualToAfterPut(const HashtableBase & rhs, const KeyType & key, c
onst ValueType & value, bool considerOrdering = false) const {return WouldBeEqua
lToAfterPutOrRemove(rhs, key, &value, considerOrdering);}
/** Returns true iff this Hashtable would have the same contents as (rhs) aft
er we called Remove() on this Hashtable once.
* @param rhs the Hashtable to compare against a hypothetically modified ver
sion of this Hashtable.
* @param key the key to imagine removing from this table
* @param considerOrdering if true, the ordering of the key/value pairs in t
he two tables will be considered. Defaults to false.
* @returns true iff (rhs) would be equal to (*this after a single Remove())
, or false if they would differ.
*/
bool WouldBeEqualToAfterRemove(const HashtableBase & rhs, const KeyType & key
, bool considerOrdering = false) const {return WouldBeEqualToAfterPutOrRemove(rh
s, key, NULL, considerOrdering);}
/** Returns true iff this Hashtable would have the same contents as (rhs) aft
er we applied either a single Put() or a single Remove() operation to this Hasht
able.
* @param rhs the Hashtable to compare against a hypothetically modified ver
sion of this Hashtable.
* @param key the key to imagine calling Put() or Remove() on this table wit
h.
* @param optValue if non-NULL, we'll imagine calling Put(key, *optValue) on
this table; if NULL, we'll imagine calling Remove(key) on this table.
* @param considerOrdering if true, the ordering of the key/value pairs in t
he tables will be considered. Defaults to false.
* @returns true iff (rhs) is equal to (this after a single Put() or Remove(
)), false if they would differ.
*/
bool WouldBeEqualToAfterPutOrRemove(const HashtableBase & rhs, const KeyType
& key, const ValueType * optValue, bool considerOrdering = false) const;
/** Returns true iff the keys in this Hashtable are the same as the keys in ( rhs). /** Returns true iff the keys in this Hashtable are the same as the keys in ( rhs).
* Note that the ordering of the keys is not considered, only their values. Values in either table are not considered, either. * @note values in either table are not considered.
* @param rhs The Hashtable whose keys we should compare against our keys. * @param rhs The Hashtable whose keys we should compare against our keys.
* @param considerOrdering if true, the ordering of the key/value pairs in t he tables will be considered. Defaults to false.
* @returns true iff both Hashtables have the same set of Key objects. * @returns true iff both Hashtables have the same set of Key objects.
*/ */
template<class HisValueType, class HisHashFunctorType> bool AreKeySetsEqual(c onst HashtableBase<KeyType, HisValueType, HisHashFunctorType> & rhs) const; template<class HisValueType, class HisHashFunctorType> bool AreKeySetsEqual(c onst HashtableBase<KeyType, HisValueType, HisHashFunctorType> & rhs, bool consid erOrdering = false) const;
/** Returns true iff every key present in this Hashtable is also present in ( rhs). /** Returns true iff every key present in this Hashtable is also present in ( rhs).
* @param rhs the Hashtable to check the keys of against our own. * @param rhs the Hashtable to check the keys of against our own.
* @param considerOrdering if true, the ordering of the key/value pairs in t he tables will be considered. Defaults to false.
*/ */
template<class HisValueType, class HisHashFunctorType> bool AreKeysASubsetOf( const HashtableBase<KeyType, HisValueType, HisHashFunctorType> & rhs) const; template<class HisValueType, class HisHashFunctorType> bool AreKeysASubsetOf( const HashtableBase<KeyType, HisValueType, HisHashFunctorType> & rhs, bool consi derOrdering = false) const;
/** Returns true iff every key present in (rhs) is also present in this Hasht able. /** Returns true iff every key present in (rhs) is also present in this Hasht able.
* @param rhs the Hashtable to check the keys of against our own. * @param rhs the Hashtable to check the keys of against our own.
* @param considerOrdering if true, the ordering of the key/value pairs in t
he tables will be considered. Defaults to false.
*/
template<class HisValueType, class HisHashFunctorType> bool AreKeysASupersetO
f(const HashtableBase<KeyType, HisValueType, HisHashFunctorType> & rhs, bool con
siderOrdering = false) const {return rhs.AreKeysASubsetOf(*this, considerOrderin
g);}
/** Returns true iff every key and value present in this Hashtable is also pr
esent in (rhs).
* @param rhs the Hashtable to check the keys of against our own.
* @param considerOrdering if true, the ordering of the key/value pairs in t
he tables will be considered. Defaults to false.
*/ */
template<class HisValueType, class HisHashFunctorType> bool AreKeysASupersetO bool AreKeysAndValuesASubsetOf(const HashtableBase & rhs, bool considerOrderi
f(const HashtableBase<KeyType, HisValueType, HisHashFunctorType> & rhs) const {r ng = false) const;
eturn rhs.AreKeysASubsetOf(*this);}
/** Returns true iff every key and value present in (rhs) is also present in
this Hashtable.
* @param rhs the Hashtable to check the keys of against our own.
* @param considerOrdering if true, the ordering of the key/value pairs in t
he tables will be considered. Defaults to false.
*/
bool AreKeysAndValuesASupersetOf(const HashtableBase & rhs, bool considerOrde
ring = false) const {return rhs.AreKeysAndValuesASubsetOf(*this, considerOrderin
g);}
/** Returns the given key's position in the hashtable's linked list, or -1 if the key wasn't found. O(n) count time (if the key exists, O(1) if it doesn't) /** Returns the given key's position in the hashtable's linked list, or -1 if the key wasn't found. O(n) count time (if the key exists, O(1) if it doesn't)
* @param key a key value to find the index of * @param key a key value to find the index of
* @returns the position of the key in the iteration list, or -1 if the key is not in the table. * @returns the position of the key in the iteration list, or -1 if the key is not in the table.
*/ */
int32 IndexOfKey(const KeyType & key) const; int32 IndexOfKey(const KeyType & key) const;
/** Returns the index of the first (or last) occurrance of (value), or -1 if (value) does /** Returns the index of the first (or last) occurrance of (value), or -1 if (value) does
* not exist in this Hashtable. Note that the search is O(N). * not exist in this Hashtable. Note that the search is O(N).
* @param value The value to search for. * @param value The value to search for.
skipping to change at line 2213 skipping to change at line 2254
{ {
if (this == &rhs) return true; if (this == &rhs) return true;
if (GetNumItems() != rhs.GetNumItems()) return false; if (GetNumItems() != rhs.GetNumItems()) return false;
const HashtableEntryBase * e = this->IndexToEntryChecked(_iterHeadIdx); const HashtableEntryBase * e = this->IndexToEntryChecked(_iterHeadIdx);
if (considerOrdering) if (considerOrdering)
{ {
const HashtableEntryBase * hisE = rhs.IndexToEntryChecked(rhs._iterHeadIdx ); const HashtableEntryBase * hisE = rhs.IndexToEntryChecked(rhs._iterHeadIdx );
while(e) while(e)
{ {
if (!(hisE->_value == e->_value)) return false; if ((!AreKeysEqual(e->_key, hisE->_key))||(!(hisE->_value == e->_value) )) return false;
e = this->GetEntryIterNextChecked(e); e = this->GetEntryIterNextChecked(e);
hisE = rhs.GetEntryIterNextChecked(hisE); hisE = rhs.GetEntryIterNextChecked(hisE);
} }
} }
else else
{ {
while(e) while(e)
{ {
const HashtableEntryBase * hisE = rhs.GetEntry(e->_hash, e->_key); const HashtableEntryBase * hisE = rhs.GetEntry(e->_hash, e->_key);
if ((hisE == NULL)||(!(hisE->_value == e->_value))) return false; if ((hisE == NULL)||(!(hisE->_value == e->_value))) return false;
e = this->GetEntryIterNextChecked(e); e = this->GetEntryIterNextChecked(e);
} }
} }
return true; return true;
} }
template <class KeyType, class ValueType, class HashFunctorType> template <class KeyType, class ValueType, class HashFunctorType>
bool bool
HashtableBase<KeyType, ValueType, HashFunctorType> ::
WouldBeEqualToAfterPutOrRemove(const HashtableBase & rhs, const KeyType & key, c
onst ValueType * optValue, bool considerOrdering) const
{
if (optValue)
{
if (rhs.ContainsKey(key) == false) return false; // rhs can't be our end-
state if it doesn't contain the key we plan to add
if (this->ContainsKey(key))
{
if (rhs.GetNumItems() != this->GetNumItems()) return false; // rhs can
't be our post-replacement-state unless it is sized the same as (this)
if (considerOrdering)
{
HashtableIterator<KeyType, ValueType> rhsIter(rhs, HTIT_FLAG_NOREGIS
TER);
for (HashtableIterator<KeyType, ValueType> iter(*this, HTIT_FLAG_NOR
EGISTER); iter.HasData(); iter++,rhsIter++)
{
const KeyType & nextKey = iter.GetKey();
if ((!AreKeysEqual(rhsIter.GetKey(), nextKey))||(!(rhsIter.GetVal
ue() == (AreKeysEqual(nextKey,key)?*optValue:iter.GetValue())))) return false;
}
}
else
{
// Make sure the two tables are equal, except for (key) which will b
e set to the new value in rhs
for (HashtableIterator<KeyType, ValueType> iter(*this, HTIT_FLAG_NOR
EGISTER); iter.HasData(); iter++)
{
const KeyType & nextKey = iter.GetKey();
const ValueType * hisVal = rhs.Get(nextKey);
if ((hisVal == NULL)||(!(*hisVal == (AreKeysEqual(nextKey,key)?*o
ptValue:iter.GetValue())))) return false;
}
}
return true;
}
else
{
if (rhs.GetNumItems() != (this->GetNumItems()+1)) return false; // rhs
can't be our post-insert-state unless it is exactly one larger than (this)
return rhs.AreKeysAndValuesASupersetOf(*this, considerOrdering);
}
}
else
{
if (rhs.ContainsKey(key)) return false; // our post-modification-state wo
uld never contain (key) because we're planning to remove (key)
if (this->ContainsKey(key))
{
if (this->GetNumItems() != (rhs.GetNumItems()+1)) return false; // rhs
can't be our post-modification-state unless it is exactly one smaller than (thi
s)
return this->AreKeysAndValuesASupersetOf(rhs, considerOrdering);
}
else return IsEqualTo(rhs, considerOrdering); // in this case the propose
d call to sTable.Remove() will be a no-op, so just compare tables as-is
}
}
template <class KeyType, class ValueType, class HashFunctorType>
bool
HashtableBase<KeyType,ValueType,HashFunctorType>::ContainsValue(const ValueType & value) const HashtableBase<KeyType,ValueType,HashFunctorType>::ContainsValue(const ValueType & value) const
{ {
const HashtableEntryBase * e = this->IndexToEntryChecked(_iterHeadIdx); const HashtableEntryBase * e = this->IndexToEntryChecked(_iterHeadIdx);
while(e) while(e)
{ {
if (e->_value == value) return true; if (e->_value == value) return true;
e = GetEntryIterNextChecked(e); e = GetEntryIterNextChecked(e);
} }
return false; return false;
} }
skipping to change at line 2463 skipping to change at line 2554
e = this->IndexToEntryChecked(_iterTailIdx); e = this->IndexToEntryChecked(_iterTailIdx);
while((e)&&(idx--)) e = this->GetEntryIterPrevChecked(e); while((e)&&(idx--)) e = this->GetEntryIterPrevChecked(e);
} }
} }
return e; return e;
} }
template <class KeyType, class ValueType, class HashFunctorType> template <class KeyType, class ValueType, class HashFunctorType>
template <class HisValueType, class HisHashFunctorType> template <class HisValueType, class HisHashFunctorType>
bool bool
HashtableBase<KeyType,ValueType,HashFunctorType>::AreKeySetsEqual(const Hashtabl eBase<KeyType, HisValueType, HisHashFunctorType> & rhs) const HashtableBase<KeyType,ValueType,HashFunctorType>::AreKeySetsEqual(const Hashtabl eBase<KeyType, HisValueType, HisHashFunctorType> & rhs, bool considerOrdering) c onst
{ {
if (GetNumItems() != rhs.GetNumItems()) return false; if (GetNumItems() != rhs.GetNumItems()) return false;
for (HashtableIterator<KeyType, ValueType, HashFunctorType> iter(*this); iter if (considerOrdering)
.HasData(); iter++) if (rhs.ContainsKey(iter.GetKey()) == false) return false; {
HashtableIterator<KeyType, ValueType, HashFunctorType> rhsIter(rhs, HTIT_F
LAG_NOREGISTER);
for (HashtableIterator<KeyType, ValueType, HashFunctorType> iter(*this, HT
IT_FLAG_NOREGISTER); iter.HasData(); iter++, rhsIter++) if (!AreKeysEqual(iter.G
etKey(),rhsIter.GetKey())) return false;
}
else
{
for (HashtableIterator<KeyType, ValueType, HashFunctorType> iter(*this, HT
IT_FLAG_NOREGISTER); iter.HasData(); iter++) if (rhs.ContainsKey(iter.GetKey())
== false) return false;
}
return true; return true;
} }
template <class KeyType, class ValueType, class HashFunctorType> template <class KeyType, class ValueType, class HashFunctorType>
template <class HisValueType, class HisHashFunctorType> template <class HisValueType, class HisHashFunctorType>
bool bool
HashtableBase<KeyType,ValueType,HashFunctorType>::AreKeysASubsetOf(const Hashtab leBase<KeyType, HisValueType, HisHashFunctorType> & rhs) const HashtableBase<KeyType,ValueType,HashFunctorType>::AreKeysASubsetOf(const Hashtab leBase<KeyType, HisValueType, HisHashFunctorType> & rhs, bool considerOrdering) const
{ {
if (GetNumItems() > rhs.GetNumItems()) return false; // pigeonhole principle ! if (GetNumItems() > rhs.GetNumItems()) return false; // pigeonhole principle !
for (HashtableIterator<KeyType, ValueType, HashFunctorType> iter(*this); iter if (considerOrdering)
.HasData(); iter++) if (rhs.ContainsKey(iter.GetKey()) == false) return false; {
HashtableIterator<KeyType, ValueType, HashFunctorType> rhsIter(rhs, HTIT_F
LAG_NOREGISTER);
for (HashtableIterator<KeyType, ValueType, HashFunctorType> iter(*this, HT
IT_FLAG_NOREGISTER); iter.HasData(); iter++,rhsIter++)
{
if (rhsIter.HasData() == false) return false; // yes, this check is ne
cessary
while(!AreKeysEqual(iter.GetKey(),rhsIter.GetKey()))
{
rhsIter++;
if (rhsIter.HasData() == false) return false;
}
}
}
else
{
for (HashtableIterator<KeyType, ValueType, HashFunctorType> iter(*this, HT
IT_FLAG_NOREGISTER); iter.HasData(); iter++) if (rhs.ContainsKey(iter.GetKey())
== false) return false;
}
return true;
}
template <class KeyType, class ValueType, class HashFunctorType>
bool
HashtableBase<KeyType,ValueType,HashFunctorType>::AreKeysAndValuesASubsetOf(cons
t HashtableBase & rhs, bool considerOrdering) const
{
if (GetNumItems() > rhs.GetNumItems()) return false; // pigeonhole principle
!
if (considerOrdering)
{
HashtableIterator<KeyType, ValueType, HashFunctorType> rhsIter(rhs, HTIT_F
LAG_NOREGISTER);
for (HashtableIterator<KeyType, ValueType, HashFunctorType> iter(*this, HT
IT_FLAG_NOREGISTER); iter.HasData(); iter++,rhsIter++)
{
if (rhsIter.HasData() == false) return false; // yes, this check is ne
cessary
while(!AreKeysEqual(iter.GetKey(),rhsIter.GetKey()))
{
rhsIter++;
if (rhsIter.HasData() == false) return false;
}
if (!(iter.GetValue() == rhsIter.GetValue())) return false;
}
}
else
{
for (HashtableIterator<KeyType, ValueType, HashFunctorType> iter(*this, HT
IT_FLAG_NOREGISTER); iter.HasData(); iter++)
{
const ValueType * hisVal = rhs.Get(iter.GetKey());
if ((hisVal == NULL)||(!(*hisVal == iter.GetValue()))) return false;
}
}
return true; return true;
} }
// Linked-list MergeSort adapted from Simon Tatham's C code at http://www.chiark .greenend.org.uk/~sgtatham/algorithms/listsort.c // Linked-list MergeSort adapted from Simon Tatham's C code at http://www.chiark .greenend.org.uk/~sgtatham/algorithms/listsort.c
template <class KeyType, class ValueType, class HashFunctorType> template <class KeyType, class ValueType, class HashFunctorType>
template <class EntryCompareFunctorType> template <class EntryCompareFunctorType>
void void
HashtableBase<KeyType,ValueType,HashFunctorType>::SortByEntry(const EntryCompare FunctorType & ecf, void * cookie) HashtableBase<KeyType,ValueType,HashFunctorType>::SortByEntry(const EntryCompare FunctorType & ecf, void * cookie)
{ {
if (this->_iterHeadIdx == MUSCLE_HASHTABLE_INVALID_SLOT_INDEX) return; if (this->_iterHeadIdx == MUSCLE_HASHTABLE_INVALID_SLOT_INDEX) return;
 End of changes. 15 change blocks. 
14 lines changed or deleted 216 lines changed or added

Home  |  About  |  Features  |  All  |  Newest  |  Dox  |  Diffs  |  RSS Feeds  |  Screenshots  |  Comments  |  Imprint  |  Privacy  |  HTTP(S)