Bug 1124920 - Remove PLDHashTable::Operate(). r=froydnj.
authorNicholas Nethercote <nnethercote@mozilla.com>
Thu, 22 Jan 2015 15:43:18 -0800
changeset 239309 9e060a6c859ecb71ae6499e0ecdddcacde44f8e4
parent 239308 32fe616d49503106a386d172ca2367453c2de77b
child 239310 740907c7d4ca0de7713cbc4b639b21794236d1e6
push id497
push usermleibovic@mozilla.com
push dateWed, 28 Jan 2015 16:43:37 +0000
reviewersfroydnj
bugs1124920
milestone38.0a1
Bug 1124920 - Remove PLDHashTable::Operate(). r=froydnj.
dom/base/nsContentList.cpp
embedding/components/commandhandler/nsCommandParams.cpp
xpcom/glue/pldhash.cpp
xpcom/glue/pldhash.h
--- a/dom/base/nsContentList.cpp
+++ b/dom/base/nsContentList.cpp
@@ -219,17 +219,17 @@ NS_GetContentList(nsINode* aRootNode,
     PL_DHashTableInit(&gContentListHashTable, &hash_table_ops,
                       sizeof(ContentListHashEntry));
   }
 
   ContentListHashEntry *entry = nullptr;
   // First we look in our hashtable.  Then we create a content list if needed
   if (gContentListHashTable.IsInitialized()) {
 
-    // A PL_DHASH_ADD is equivalent to a PL_DHASH_LOOKUP for cases
+    // A PL_DHashTableAdd is equivalent to a PL_DHashTableLookup for cases
     // when the entry is already in the hashtable.
     entry = static_cast<ContentListHashEntry *>
                        (PL_DHashTableAdd(&gContentListHashTable, &hashKey));
     if (entry)
       list = entry->mContentList;
   }
 
   if (!list) {
@@ -330,17 +330,17 @@ GetFuncStringContentList(nsINode* aRootN
                       sizeof(FuncStringContentListHashEntry));
   }
 
   FuncStringContentListHashEntry *entry = nullptr;
   // First we look in our hashtable.  Then we create a content list if needed
   if (gFuncStringContentListHashTable.IsInitialized()) {
     nsFuncStringCacheKey hashKey(aRootNode, aFunc, aString);
 
-    // A PL_DHASH_ADD is equivalent to a PL_DHASH_LOOKUP for cases
+    // A PL_DHashTableAdd is equivalent to a PL_DHashTableLookup for cases
     // when the entry is already in the hashtable.
     entry = static_cast<FuncStringContentListHashEntry *>
                        (PL_DHashTableAdd(&gFuncStringContentListHashTable,
                                          &hashKey));
     if (entry) {
       list = entry->mContentList;
 #ifdef DEBUG
       MOZ_ASSERT_IF(list, list->mType == ListType::sType);
--- a/embedding/components/commandhandler/nsCommandParams.cpp
+++ b/embedding/components/commandhandler/nsCommandParams.cpp
@@ -203,17 +203,17 @@ nsCommandParams::SetISupportsValue(const
   }
   foundEntry->mISupports = value;   // addrefs
   return NS_OK;
 }
 
 NS_IMETHODIMP
 nsCommandParams::RemoveValue(const char* aName)
 {
-  // PL_DHASH_REMOVE doesn't tell us if the entry was really removed, so we
+  // PL_DHashTableRemove doesn't tell us if the entry was really removed, so we
   // return NS_OK unconditionally.
   (void)PL_DHashTableRemove(&mValuesHash, (void *)aName);
   return NS_OK;
 }
 
 nsCommandParams::HashEntry*
 nsCommandParams::GetNamedEntry(const char* aName)
 {
--- a/xpcom/glue/pldhash.cpp
+++ b/xpcom/glue/pldhash.cpp
@@ -347,17 +347,17 @@ PLDHashTable::Finish()
 void
 PL_DHashTableFinish(PLDHashTable* aTable)
 {
   aTable->Finish();
 }
 
 PLDHashEntryHdr* PL_DHASH_FASTCALL
 PLDHashTable::SearchTable(const void* aKey, PLDHashNumber aKeyHash,
-                          PLDHashOperator aOp)
+                          bool aIsAdd)
 {
   METER(mStats.mSearches++);
   NS_ASSERTION(!(aKeyHash & COLLISION_FLAG),
                "!(aKeyHash & COLLISION_FLAG)");
 
   /* Compute the primary hash address. */
   PLDHashNumber hash1 = HASH1(aKeyHash, mHashShift);
   PLDHashEntryHdr* entry = ADDRESS_ENTRY(this, hash1);
@@ -376,54 +376,54 @@ PLDHashTable::SearchTable(const void* aK
     return entry;
   }
 
   /* Collision: double hash. */
   int sizeLog2 = PL_DHASH_BITS - mHashShift;
   PLDHashNumber hash2 = HASH2(aKeyHash, sizeLog2, mHashShift);
   uint32_t sizeMask = (1u << sizeLog2) - 1;
 
-  /* Save the first removed entry pointer so PL_DHASH_ADD can recycle it. */
+  /* Save the first removed entry pointer so Add() can recycle it. */
   PLDHashEntryHdr* firstRemoved = nullptr;
 
   for (;;) {
     if (MOZ_UNLIKELY(ENTRY_IS_REMOVED(entry))) {
       if (!firstRemoved) {
         firstRemoved = entry;
       }
     } else {
-      if (aOp == PL_DHASH_ADD) {
+      if (aIsAdd) {
         entry->keyHash |= COLLISION_FLAG;
       }
     }
 
     METER(mStats.mSteps++);
     hash1 -= hash2;
     hash1 &= sizeMask;
 
     entry = ADDRESS_ENTRY(this, hash1);
     if (PL_DHASH_ENTRY_IS_FREE(entry)) {
       METER(mStats.mMisses++);
-      return (firstRemoved && aOp == PL_DHASH_ADD) ? firstRemoved : entry;
+      return (firstRemoved && aIsAdd) ? firstRemoved : entry;
     }
 
     if (MATCH_ENTRY_KEYHASH(entry, aKeyHash) &&
         matchEntry(this, entry, aKey)) {
       METER(mStats.mHits++);
       return entry;
     }
   }
 
   /* NOTREACHED */
   return nullptr;
 }
 
 /*
  * This is a copy of SearchTable, used by ChangeTable, hardcoded to
- *   1. assume |aOp == PL_DHASH_ADD|,
+ *   1. assume |aIsAdd| is true,
  *   2. assume that |aKey| will never match an existing entry, and
  *   3. assume that no entries have been removed from the current table
  *      structure.
  * Avoiding the need for |aKey| means we can avoid needing a way to map
  * entries to keys, which means callers can use complex key types more
  * easily.
  */
 PLDHashEntryHdr* PL_DHASH_FASTCALL
@@ -522,143 +522,141 @@ PLDHashTable::ChangeTable(int aDeltaLog2
     }
     oldEntryAddr += mEntrySize;
   }
 
   free(oldEntryStore);
   return true;
 }
 
-MOZ_ALWAYS_INLINE PLDHashEntryHdr*
-PLDHashTable::Operate(const void* aKey, PLDHashOperator aOp)
+MOZ_ALWAYS_INLINE PLDHashNumber
+PLDHashTable::GetKeyHash(const void* aKey)
 {
-  PLDHashEntryHdr* entry;
-
-  MOZ_ASSERT(aOp == PL_DHASH_LOOKUP || mRecursionLevel == 0);
-  INCREMENT_RECURSION_LEVEL(this);
-
   PLDHashNumber keyHash = mOps->hashKey(this, aKey);
   keyHash *= PL_DHASH_GOLDEN_RATIO;
 
   /* Avoid 0 and 1 hash codes, they indicate free and removed entries. */
   ENSURE_LIVE_KEYHASH(keyHash);
   keyHash &= ~COLLISION_FLAG;
 
-  switch (aOp) {
-    case PL_DHASH_LOOKUP:
-      METER(mStats.mLookups++);
-      entry = SearchTable(aKey, keyHash, aOp);
-      break;
-
-    case PL_DHASH_ADD: {
-      /*
-       * If alpha is >= .75, grow or compress the table.  If aKey is already
-       * in the table, we may grow once more than necessary, but only if we
-       * are on the edge of being overloaded.
-       */
-      uint32_t capacity = Capacity();
-      if (mEntryCount + mRemovedCount >= MaxLoad(capacity)) {
-        /* Compress if a quarter or more of all entries are removed. */
-        int deltaLog2;
-        if (mRemovedCount >= capacity >> 2) {
-          METER(mStats.mCompresses++);
-          deltaLog2 = 0;
-        } else {
-          METER(mStats.mGrows++);
-          deltaLog2 = 1;
-        }
-
-        /*
-         * Grow or compress the table.  If ChangeTable() fails, allow
-         * overloading up to the secondary max.  Once we hit the secondary
-         * max, return null.
-         */
-        if (!ChangeTable(deltaLog2) &&
-            mEntryCount + mRemovedCount >= MaxLoadOnGrowthFailure(capacity)) {
-          METER(mStats.mAddFailures++);
-          entry = nullptr;
-          break;
-        }
-      }
+  return keyHash;
+}
 
-      /*
-       * Look for entry after possibly growing, so we don't have to add it,
-       * then skip it while growing the table and re-add it after.
-       */
-      entry = SearchTable(aKey, keyHash, aOp);
-      if (!ENTRY_IS_LIVE(entry)) {
-        /* Initialize the entry, indicating that it's no longer free. */
-        METER(mStats.mAddMisses++);
-        if (ENTRY_IS_REMOVED(entry)) {
-          METER(mStats.mAddOverRemoved++);
-          mRemovedCount--;
-          keyHash |= COLLISION_FLAG;
-        }
-        if (mOps->initEntry && !mOps->initEntry(this, entry, aKey)) {
-          /* We haven't claimed entry yet; fail with null return. */
-          memset(entry + 1, 0, mEntrySize - sizeof(*entry));
-          entry = nullptr;
-          break;
-        }
-        entry->keyHash = keyHash;
-        mEntryCount++;
-      }
-      METER(else {
-        mStats.mAddHits++;
-      });
-      break;
-    }
+MOZ_ALWAYS_INLINE PLDHashEntryHdr*
+PLDHashTable::Lookup(const void* aKey)
+{
+  INCREMENT_RECURSION_LEVEL(this);
 
-    case PL_DHASH_REMOVE:
-      entry = SearchTable(aKey, keyHash, aOp);
-      if (ENTRY_IS_LIVE(entry)) {
-        /* Clear this entry and mark it as "removed". */
-        METER(mStats.mRemoveHits++);
-        PL_DHashTableRawRemove(this, entry);
+  METER(mStats.mLookups++);
 
-        /* Shrink if alpha is <= .25 and the table isn't too small already. */
-        uint32_t capacity = Capacity();
-        if (capacity > PL_DHASH_MIN_CAPACITY &&
-            mEntryCount <= MinLoad(capacity)) {
-          METER(mStats.mShrinks++);
-          (void) ChangeTable(-1);
-        }
-      }
-      METER(else {
-        mStats.mRemoveMisses++;
-      });
-      entry = nullptr;
-      break;
-
-    default:
-      NS_NOTREACHED("0");
-      entry = nullptr;
-  }
+  PLDHashNumber keyHash = GetKeyHash(aKey);
+  PLDHashEntryHdr* entry = SearchTable(aKey, keyHash, /* isAdd = */ false);
 
   DECREMENT_RECURSION_LEVEL(this);
 
   return entry;
 }
 
 MOZ_ALWAYS_INLINE PLDHashEntryHdr*
-PLDHashTable::Lookup(const void* aKey)
-{
-  return Operate(aKey, PL_DHASH_LOOKUP);
-}
-
-MOZ_ALWAYS_INLINE PLDHashEntryHdr*
 PLDHashTable::Add(const void* aKey)
 {
-  return Operate(aKey, PL_DHASH_ADD);
+  PLDHashNumber keyHash;
+  PLDHashEntryHdr* entry;
+
+  MOZ_ASSERT(mRecursionLevel == 0);
+  INCREMENT_RECURSION_LEVEL(this);
+
+  /*
+   * If alpha is >= .75, grow or compress the table.  If aKey is already
+   * in the table, we may grow once more than necessary, but only if we
+   * are on the edge of being overloaded.
+   */
+  uint32_t capacity = Capacity();
+  if (mEntryCount + mRemovedCount >= MaxLoad(capacity)) {
+    /* Compress if a quarter or more of all entries are removed. */
+    int deltaLog2;
+    if (mRemovedCount >= capacity >> 2) {
+      METER(mStats.mCompresses++);
+      deltaLog2 = 0;
+    } else {
+      METER(mStats.mGrows++);
+      deltaLog2 = 1;
+    }
+
+    /*
+     * Grow or compress the table.  If ChangeTable() fails, allow
+     * overloading up to the secondary max.  Once we hit the secondary
+     * max, return null.
+     */
+    if (!ChangeTable(deltaLog2) &&
+        mEntryCount + mRemovedCount >= MaxLoadOnGrowthFailure(capacity)) {
+      METER(mStats.mAddFailures++);
+      entry = nullptr;
+      goto exit;
+    }
+  }
+
+  /*
+   * Look for entry after possibly growing, so we don't have to add it,
+   * then skip it while growing the table and re-add it after.
+   */
+  keyHash = GetKeyHash(aKey);
+  entry = SearchTable(aKey, keyHash, /* isAdd = */ true);
+  if (!ENTRY_IS_LIVE(entry)) {
+    /* Initialize the entry, indicating that it's no longer free. */
+    METER(mStats.mAddMisses++);
+    if (ENTRY_IS_REMOVED(entry)) {
+      METER(mStats.mAddOverRemoved++);
+      mRemovedCount--;
+      keyHash |= COLLISION_FLAG;
+    }
+    if (mOps->initEntry && !mOps->initEntry(this, entry, aKey)) {
+      /* We haven't claimed entry yet; fail with null return. */
+      memset(entry + 1, 0, mEntrySize - sizeof(*entry));
+      entry = nullptr;
+      goto exit;
+    }
+    entry->keyHash = keyHash;
+    mEntryCount++;
+  }
+  METER(else {
+    mStats.mAddHits++;
+  });
+
+exit:
+  DECREMENT_RECURSION_LEVEL(this);
+  return entry;
 }
 
 MOZ_ALWAYS_INLINE void
 PLDHashTable::Remove(const void* aKey)
 {
-  Operate(aKey, PL_DHASH_REMOVE);
+  MOZ_ASSERT(mRecursionLevel == 0);
+  INCREMENT_RECURSION_LEVEL(this);
+
+  PLDHashNumber keyHash = GetKeyHash(aKey);
+  PLDHashEntryHdr* entry = SearchTable(aKey, keyHash, /* isAdd = */ false);
+  if (ENTRY_IS_LIVE(entry)) {
+    /* Clear this entry and mark it as "removed". */
+    METER(mStats.mRemoveHits++);
+    PL_DHashTableRawRemove(this, entry);
+
+    /* Shrink if alpha is <= .25 and the table isn't too small already. */
+    uint32_t capacity = Capacity();
+    if (capacity > PL_DHASH_MIN_CAPACITY &&
+        mEntryCount <= MinLoad(capacity)) {
+      METER(mStats.mShrinks++);
+      (void) ChangeTable(-1);
+    }
+  }
+  METER(else {
+    mStats.mRemoveMisses++;
+  });
+
+  DECREMENT_RECURSION_LEVEL(this);
 }
 
 PLDHashEntryHdr* PL_DHASH_FASTCALL
 PL_DHashTableLookup(PLDHashTable* aTable, const void* aKey)
 {
   return aTable->Lookup(aKey);
 }
 
--- a/xpcom/glue/pldhash.h
+++ b/xpcom/glue/pldhash.h
@@ -96,29 +96,25 @@ PL_DHASH_ENTRY_IS_FREE(PLDHashEntryHdr* 
 
 MOZ_ALWAYS_INLINE bool
 PL_DHASH_ENTRY_IS_BUSY(PLDHashEntryHdr* aEntry)
 {
   return !PL_DHASH_ENTRY_IS_FREE(aEntry);
 }
 
 /*
- * To consolidate keyHash computation and table grow/shrink code, we use a
- * single entry point for lookup, add, and remove operations.  The operation
- * codes are declared here, along with codes returned by PLDHashEnumerator
- * functions, which control PL_DHashTableEnumerate's behavior.
+ * These are the codes returned by PLDHashEnumerator functions, which control
+ * PL_DHashTableEnumerate's behavior.
  */
-typedef enum PLDHashOperator
+enum PLDHashOperator
 {
-  PL_DHASH_LOOKUP = 0,        /* lookup entry */
-  PL_DHASH_ADD = 1,           /* add entry */
-  PL_DHASH_REMOVE = 2,        /* remove entry, or enumerator says remove */
   PL_DHASH_NEXT = 0,          /* enumerator says continue */
-  PL_DHASH_STOP = 1           /* enumerator says stop */
-} PLDHashOperator;
+  PL_DHASH_STOP = 1,          /* enumerator says stop */
+  PL_DHASH_REMOVE = 2         /* enumerator says remove */
+};
 
 /*
  * Enumerate entries in table using etor:
  *
  *   count = PL_DHashTableEnumerate(table, etor, arg);
  *
  * PL_DHashTableEnumerate calls etor like so:
  *
@@ -198,17 +194,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 PL_DHASH_LOOKUPs */
+    uint32_t        mLookups;       /* number of Lookup() 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 */
@@ -309,23 +305,23 @@ public:
     const PLDHashTable* mTable;       /* Main table pointer */
     char* mEntryAddr;                 /* Pointer to the next entry to check */
     uint32_t mEntryOffset;            /* The number of the elements returned */
   };
 
   Iterator Iterate() const { return Iterator(this); }
 
 private:
+  PLDHashNumber GetKeyHash(const void* aKey);
+
   PLDHashEntryHdr* PL_DHASH_FASTCALL
-    SearchTable(const void* aKey, PLDHashNumber aKeyHash, PLDHashOperator aOp);
+    SearchTable(const void* aKey, PLDHashNumber aKeyHash, bool aIsAdd);
 
   PLDHashEntryHdr* PL_DHASH_FASTCALL FindFreeEntry(PLDHashNumber aKeyHash);
 
-  PLDHashEntryHdr* Operate(const void* aKey, PLDHashOperator aOp);
-
   bool ChangeTable(int aDeltaLog2);
 };
 
 /*
  * Compute the hash code for a given key to be looked up, added, or removed
  * from aTable.  A hash code may have any PLDHashNumber value.
  */
 typedef PLDHashNumber (*PLDHashHashKey)(PLDHashTable* aTable,
@@ -346,18 +342,18 @@ typedef bool (*PLDHashMatchEntry)(PLDHas
  * any reference-decrementing callback shortly.
  */
 typedef void (*PLDHashMoveEntry)(PLDHashTable* aTable,
                                  const PLDHashEntryHdr* aFrom,
                                  PLDHashEntryHdr* aTo);
 
 /*
  * Clear the entry and drop any strong references it holds.  This callback is
- * invoked during a PL_DHASH_REMOVE operation (see below for operation codes),
- * but only if the given key is found in the table.
+ * invoked by PL_DHashTableRemove(), but only if the given key is found in the
+ * table.
  */
 typedef void (*PLDHashClearEntry)(PLDHashTable* aTable,
                                   PLDHashEntryHdr* aEntry);
 
 /*
  * Initialize a new entry, apart from keyHash.  This function is called when
  * PL_DHashTableAdd finds no existing entry for the given key, and must add a
  * new one.  At that point, aEntry->keyHash is not set yet, to avoid claiming