Bug 1124973 (part 7) - Remove PL_DHashTableLookup. r=froydnj.
authorNicholas Nethercote <nnethercote@mozilla.com>
Mon, 26 Jan 2015 16:02:05 -0800
changeset 239569 1a087d928c9d9f2a6c9735e73fa5e2db6a954b7e
parent 239568 fd36ee6e8307bfe6e5ff49adb1ac64ccca5cf3dc
child 239570 3d3a77079fe518a463e2f7cefdd23139c7a7ec09
push id500
push userjoshua.m.grant@gmail.com
push dateThu, 29 Jan 2015 01:48:36 +0000
reviewersfroydnj
bugs1124973
milestone38.0a1
Bug 1124973 (part 7) - Remove PL_DHashTableLookup. r=froydnj. This patch: - Removes PL_DHashTableLookup(). - Removes PL_DHASH_ENTRY_IS_BUSY(). It's barely used and PL_DHASH_ENTRY_IS_FREE() suffices. - Removes a non-useful, non-sequitur comment ("However, use...").
xpcom/glue/pldhash.cpp
xpcom/glue/pldhash.h
--- a/xpcom/glue/pldhash.cpp
+++ b/xpcom/glue/pldhash.cpp
@@ -313,16 +313,22 @@ PL_DHashTableInit(PLDHashTable* aTable, 
 /* Match an entry's keyHash against an unstored one computed from a key. */
 #define MATCH_ENTRY_KEYHASH(entry,hash0) \
     (((entry)->keyHash & ~COLLISION_FLAG) == (hash0))
 
 /* Compute the address of the indexed entry in table. */
 #define ADDRESS_ENTRY(table, index) \
     ((PLDHashEntryHdr *)((table)->mEntryStore + (index) * (table)->mEntrySize))
 
+MOZ_ALWAYS_INLINE bool
+PL_DHASH_ENTRY_IS_FREE(PLDHashEntryHdr* aEntry)
+{
+  return aEntry->keyHash == 0;
+}
+
 MOZ_ALWAYS_INLINE void
 PLDHashTable::Finish()
 {
   INCREMENT_RECURSION_LEVEL(this);
 
   /* Clear any remaining live entries. */
   char* entryAddr = mEntryStore;
   char* entryLimit = entryAddr + Capacity() * mEntrySize;
@@ -536,35 +542,28 @@ PLDHashTable::GetKeyHash(const void* aKe
   /* Avoid 0 and 1 hash codes, they indicate free and removed entries. */
   ENSURE_LIVE_KEYHASH(keyHash);
   keyHash &= ~COLLISION_FLAG;
 
   return keyHash;
 }
 
 MOZ_ALWAYS_INLINE PLDHashEntryHdr*
-PLDHashTable::Lookup(const void* aKey)
+PLDHashTable::Search(const void* aKey)
 {
   INCREMENT_RECURSION_LEVEL(this);
 
-  METER(mStats.mLookups++);
+  METER(mStats.mSearches++);
 
   PLDHashNumber keyHash = GetKeyHash(aKey);
   PLDHashEntryHdr* entry = SearchTable(aKey, keyHash, /* isAdd = */ false);
 
   DECREMENT_RECURSION_LEVEL(this);
 
-  return entry;
-}
-
-MOZ_ALWAYS_INLINE PLDHashEntryHdr*
-PLDHashTable::Search(const void* aKey)
-{
-  PLDHashEntryHdr* entry = Lookup(aKey);
-  return PL_DHASH_ENTRY_IS_BUSY(entry) ? entry : nullptr;
+  return !PL_DHASH_ENTRY_IS_FREE(entry) ? entry : nullptr;
 }
 
 MOZ_ALWAYS_INLINE PLDHashEntryHdr*
 PLDHashTable::Add(const void* aKey)
 {
   PLDHashNumber keyHash;
   PLDHashEntryHdr* entry;
 
@@ -657,22 +656,16 @@ PLDHashTable::Remove(const void* aKey)
   METER(else {
     mStats.mRemoveMisses++;
   });
 
   DECREMENT_RECURSION_LEVEL(this);
 }
 
 PLDHashEntryHdr* PL_DHASH_FASTCALL
-PL_DHashTableLookup(PLDHashTable* aTable, const void* aKey)
-{
-  return aTable->Lookup(aKey);
-}
-
-PLDHashEntryHdr* PL_DHASH_FASTCALL
 PL_DHashTableSearch(PLDHashTable* aTable, const void* aKey)
 {
   return aTable->Search(aKey);
 }
 
 PLDHashEntryHdr* PL_DHASH_FASTCALL
 PL_DHashTableAdd(PLDHashTable* aTable, const void* aKey)
 {
@@ -756,17 +749,17 @@ PLDHashTable::Enumerate(PLDHashEnumerato
 
   MOZ_ASSERT(!didRemove || mRecursionLevel == 1);
 
   /*
    * Shrink or compress if a quarter or more of all entries are removed, or
    * if the table is underloaded according to the minimum alpha, and is not
    * minimal-size already.  Do this only if we removed above, so non-removing
    * enumerations can count on stable |mEntryStore| until the next
-   * non-lookup-Operate or removing-Enumerate.
+   * Add, Remove, or removing-Enumerate.
    */
   if (didRemove &&
       (mRemovedCount >= capacity >> 2 ||
        (capacity > PL_DHASH_MIN_CAPACITY &&
         mEntryCount <= MinLoad(capacity)))) {
     METER(mStats.mEnumShrinks++);
     capacity = mEntryCount;
     capacity += capacity >> 1;
@@ -1029,17 +1022,17 @@ PLDHashTable::DumpMeter(PLDHashEnumerato
   fprintf(aFp, "         number of searches: %u\n", mStats.mSearches);
   fprintf(aFp, "             number of hits: %u\n", mStats.mHits);
   fprintf(aFp, "           number of misses: %u\n", mStats.mMisses);
   fprintf(aFp, "      mean steps per search: %g\n",
           mStats.mSearches ? (double)mStats.mSteps / mStats.mSearches : 0.);
   fprintf(aFp, "     mean hash chain length: %g\n", mean);
   fprintf(aFp, "         standard deviation: %g\n", sigma);
   fprintf(aFp, "  maximum hash chain length: %u\n", maxChainLen);
-  fprintf(aFp, "          number of lookups: %u\n", mStats.mLookups);
+  fprintf(aFp, "         number of searches: %u\n", mStats.mSearches);
   fprintf(aFp, " adds that made a new entry: %u\n", mStats.mAddMisses);
   fprintf(aFp, "adds that recycled removeds: %u\n", mStats.mAddOverRemoved);
   fprintf(aFp, "   adds that found an entry: %u\n", mStats.mAddHits);
   fprintf(aFp, "               add failures: %u\n", mStats.mAddFailures);
   fprintf(aFp, "             useful removes: %u\n", mStats.mRemoveHits);
   fprintf(aFp, "            useless removes: %u\n", mStats.mRemoveMisses);
   fprintf(aFp, "removes that freed an entry: %u\n", mStats.mRemoveFrees);
   fprintf(aFp, "  removes while enumerating: %u\n", mStats.mRemoveEnums);
@@ -1056,17 +1049,17 @@ PLDHashTable::DumpMeter(PLDHashEnumerato
     uint32_t i = 0;
     do {
       if (aDump(this, entry, i++, aFp) != PL_DHASH_NEXT) {
         break;
       }
       hash1 -= hash2;
       hash1 &= sizeMask;
       entry = ADDRESS_ENTRY(this, hash1);
-    } while (PL_DHASH_ENTRY_IS_BUSY(entry));
+    } while (!PL_DHASH_ENTRY_IS_FREE(entry));
   }
 }
 
 void
 PL_DHashTableDumpMeter(PLDHashTable* aTable, PLDHashEnumerator aDump, FILE* aFp)
 {
   aTable->DumpMeter(aDump, aFp);
 }
--- a/xpcom/glue/pldhash.h
+++ b/xpcom/glue/pldhash.h
@@ -72,39 +72,22 @@ struct PLDHashTableOps;
  *
  * Each hash table sub-type should make its entry type a subclass of
  * PLDHashEntryHdr. The keyHash member contains the result of multiplying the
  * hash code returned from the hashKey callback (see below) by
  * PL_DHASH_GOLDEN_RATIO, then constraining the result to avoid the magic 0 and
  * 1 values. The stored keyHash value is table size invariant, and it is
  * maintained automatically -- users should never set it, and its only uses
  * should be via the entry macros below.
- *
- * However, use PL_DHASH_ENTRY_IS_BUSY for faster liveness testing of entries
- * returned by PL_DHashTableLookup and PL_DHashTableAdd, as these functions
- * never return a non-live, busy (i.e., removed) entry pointer to its caller.
- * See below for more details on these functions.
  */
 struct PLDHashEntryHdr
 {
   PLDHashNumber keyHash;  /* every entry must begin like this */
 };
 
-MOZ_ALWAYS_INLINE bool
-PL_DHASH_ENTRY_IS_FREE(PLDHashEntryHdr* aEntry)
-{
-  return aEntry->keyHash == 0;
-}
-
-MOZ_ALWAYS_INLINE bool
-PL_DHASH_ENTRY_IS_BUSY(PLDHashEntryHdr* aEntry)
-{
-  return !PL_DHASH_ENTRY_IS_FREE(aEntry);
-}
-
 /*
  * These are the codes returned by PLDHashEnumerator functions, which control
  * PL_DHashTableEnumerate's behavior.
  */
 enum PLDHashOperator
 {
   PL_DHASH_NEXT = 0,          /* enumerator says continue */
   PL_DHASH_STOP = 1,          /* enumerator says stop */
@@ -194,17 +177,17 @@ private:
 
 #ifdef PL_DHASHMETER
   struct PLDHashStats
   {
     uint32_t        mSearches;      /* total number of table searches */
     uint32_t        mSteps;         /* hash chain links traversed */
     uint32_t        mHits;          /* searches that found key */
     uint32_t        mMisses;        /* searches that didn't find key */
-    uint32_t        mLookups;       /* number of Lookup() calls */
+    uint32_t        mSearches;      /* number of Search() calls */
     uint32_t        mAddMisses;     /* adds that miss, and do work */
     uint32_t        mAddOverRemoved;/* adds that recycled a removed entry */
     uint32_t        mAddHits;       /* adds that hit an existing entry */
     uint32_t        mAddFailures;   /* out-of-memory during add growth */
     uint32_t        mRemoveHits;    /* removes that hit, and do work */
     uint32_t        mRemoveMisses;  /* useless removes that miss */
     uint32_t        mRemoveFrees;   /* removes that freed entry directly */
     uint32_t        mRemoveEnums;   /* removes done by Enumerate */
@@ -253,17 +236,16 @@ public:
   uint32_t EntryCount() const { return mEntryCount; }
   uint32_t Generation() const { return mGeneration; }
 
   bool Init(const PLDHashTableOps* aOps, uint32_t aEntrySize,
             const mozilla::fallible_t&, uint32_t aLength);
 
   void Finish();
 
-  PLDHashEntryHdr* Lookup(const void* aKey);
   PLDHashEntryHdr* Search(const void* aKey);
   PLDHashEntryHdr* Add(const void* aKey);
   void Remove(const void* aKey);
 
   void RawRemove(PLDHashEntryHdr* aEntry);
 
   uint32_t Enumerate(PLDHashEnumerator aEtor, void* aArg);
 
@@ -476,49 +458,38 @@ MOZ_WARN_UNUSED_RESULT bool PL_DHashTabl
 /*
  * Free |aTable|'s entry storage (via aTable->mOps->freeTable). Use this
  * function to destroy a PLDHashTable that is allocated on the stack or in
  * static memory and was created via PL_DHashTableInit().
  */
 void PL_DHashTableFinish(PLDHashTable* aTable);
 
 /*
- * To lookup a key in table, call:
- *
- *  entry = PL_DHashTableLookup(table, key);
- *
- * If PL_DHASH_ENTRY_IS_BUSY(entry) is true, key was found and it identifies
- * entry.  If PL_DHASH_ENTRY_IS_FREE(entry) is true, key was not found.
- */
-PLDHashEntryHdr* PL_DHASH_FASTCALL
-PL_DHashTableLookup(PLDHashTable* aTable, const void* aKey);
-
-/*
- * To lookup a key in table, call:
+ * To search for a key in |table|, call:
  *
  *  entry = PL_DHashTableSearch(table, key);
  *
- * If |entry| is non-null, key was found and it identifies entry.  If |entry|
- * is null, key was not found.
+ * If |entry| is non-null, |key| was found.  If |entry| is null, key was not
+ * found.
  */
 PLDHashEntryHdr* PL_DHASH_FASTCALL
 PL_DHashTableSearch(PLDHashTable* aTable, const void* aKey);
 
 /*
  * To add an entry identified by key to table, call:
  *
  *  entry = PL_DHashTableAdd(table, key);
  *
- * If entry is null upon return, then either the table is severely overloaded,
- * and memory can't be allocated for entry storage. Or if
- * aTable->mOps->initEntry is non-null, the aTable->mOps->initEntry op may have
+ * If entry is null upon return, then either (a) the table is severely
+ * overloaded and memory can't be allocated for entry storage, or (b)
+ * aTable->mOps->initEntry is non-null and aTable->mOps->initEntry op has
  * returned false.
  *
- * Otherwise, aEntry->keyHash has been set so that PL_DHASH_ENTRY_IS_BUSY(entry)
- * is true, and it is up to the caller to initialize the key and value parts
+ * Otherwise, aEntry->keyHash has been set so that PL_DHASH_ENTRY_IS_FREE(entry)
+ * is false, and it is up to the caller to initialize the key and value parts
  * of the entry sub-type, if they have not been set already (i.e. if entry was
  * not already in the table, and if the optional initEntry hook was not used).
  */
 PLDHashEntryHdr* PL_DHASH_FASTCALL
 PL_DHashTableAdd(PLDHashTable* aTable, const void* aKey);
 
 /*
  * To remove an entry identified by key from table, call:
@@ -528,17 +499,17 @@ PL_DHashTableAdd(PLDHashTable* aTable, c
  * If key's entry is found, it is cleared (via table->mOps->clearEntry) and
  * the entry is marked so that PL_DHASH_ENTRY_IS_FREE(entry).  This operation
  * returns null unconditionally; you should ignore its return value.
  */
 void PL_DHASH_FASTCALL
 PL_DHashTableRemove(PLDHashTable* aTable, const void* aKey);
 
 /*
- * Remove an entry already accessed via LOOKUP or ADD.
+ * Remove an entry already accessed via PL_DHashTableSearch or PL_DHashTableAdd.
  *
  * NB: this is a "raw" or low-level routine, intended to be used only where
  * the inefficiency of a full PL_DHashTableRemove (which rehashes in order
  * to find the entry given its key) is not tolerable.  This function does not
  * shrink the table if it is underloaded.  It does not update mStats #ifdef
  * PL_DHASHMETER, either.
  */
 void PL_DHashTableRawRemove(PLDHashTable* aTable, PLDHashEntryHdr* aEntry);