Bug 1185399 (part 1) - Remove macros from pldhash.h. r=froydnj.
authorNicholas Nethercote <nnethercote@mozilla.com>
Mon, 20 Jul 2015 17:06:38 -0700
changeset 253843 3bbc89c5395c96a82b7d9345539b6478501686f4
parent 253842 b4b0bb04601d9beefda7429a4ba449c99332f109
child 253844 c642708766fdd9fcecb2a7a72cbeda64ba5d444f
push id29081
push usercbook@mozilla.com
push dateTue, 21 Jul 2015 14:57:20 +0000
treeherdermozilla-central@512c7e8f0030 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersfroydnj
bugs1185399
milestone42.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1185399 (part 1) - Remove macros from pldhash.h. r=froydnj.
layout/generic/nsLineBox.h
toolkit/components/telemetry/Telemetry.cpp
xpcom/glue/nsTHashtable.h
xpcom/glue/pldhash.cpp
xpcom/glue/pldhash.h
xpcom/tests/gtest/TestPLDHash.cpp
--- a/layout/generic/nsLineBox.h
+++ b/layout/generic/nsLineBox.h
@@ -338,17 +338,17 @@ private:
   void NoteFramesMovedFrom(nsLineBox* aFromLine);
 
   void SwitchToHashtable()
   {
     MOZ_ASSERT(!mFlags.mHasHashedFrames);
     uint32_t count = GetChildCount();
     mFlags.mHasHashedFrames = 1;
     uint32_t minLength = std::max(kMinChildCountForHashtable,
-                                  uint32_t(PL_DHASH_DEFAULT_INITIAL_LENGTH));
+                                  uint32_t(PLDHashTable::kDefaultInitialLength));
     mFrames = new nsTHashtable< nsPtrHashKey<nsIFrame> >(std::max(count, minLength));
     for (nsIFrame* f = mFirstChild; count-- > 0; f = f->GetNextSibling()) {
       mFrames->PutEntry(f);
     }
   }
   void SwitchToCounter() {
     MOZ_ASSERT(mFlags.mHasHashedFrames);
     uint32_t count = GetChildCount();
--- a/toolkit/components/telemetry/Telemetry.cpp
+++ b/toolkit/components/telemetry/Telemetry.cpp
@@ -100,17 +100,18 @@ HistogramGet(const char *name, const cha
 
 enum reflectStatus
 ReflectHistogramSnapshot(JSContext *cx, JS::Handle<JSObject*> obj, Histogram *h);
 
 template<class EntryType>
 class AutoHashtable : public nsTHashtable<EntryType>
 {
 public:
-  explicit AutoHashtable(uint32_t initLength = PL_DHASH_DEFAULT_INITIAL_LENGTH);
+  explicit AutoHashtable(uint32_t initLength =
+                         PLDHashTable::kDefaultInitialLength);
   typedef bool (*ReflectEntryFunc)(EntryType *entry, JSContext *cx, JS::Handle<JSObject*> obj);
   bool ReflectIntoJS(ReflectEntryFunc entryFunc, JSContext *cx, JS::Handle<JSObject*> obj);
 };
 
 template<class EntryType>
 AutoHashtable<EntryType>::AutoHashtable(uint32_t initLength)
   : nsTHashtable<EntryType>(initLength)
 {
--- a/xpcom/glue/nsTHashtable.h
+++ b/xpcom/glue/nsTHashtable.h
@@ -85,17 +85,17 @@ template<class EntryType>
 class nsTHashtable
 {
   typedef mozilla::fallible_t fallible_t;
 
 public:
   // Separate constructors instead of default aInitLength parameter since
   // otherwise the default no-arg constructor isn't found.
   nsTHashtable()
-    : mTable(Ops(), sizeof(EntryType), PL_DHASH_DEFAULT_INITIAL_LENGTH)
+    : mTable(Ops(), sizeof(EntryType), PLDHashTable::kDefaultInitialLength)
   {}
   explicit nsTHashtable(uint32_t aInitLength)
     : mTable(Ops(), sizeof(EntryType), aInitLength)
   {}
 
   /**
    * destructor, cleans up and deallocates
    */
--- a/xpcom/glue/pldhash.cpp
+++ b/xpcom/glue/pldhash.cpp
@@ -180,46 +180,46 @@ MinLoad(uint32_t aCapacity)
 // - capacity cannot be too small.
 static inline void
 BestCapacity(uint32_t aLength, uint32_t* aCapacityOut,
              uint32_t* aLog2CapacityOut)
 {
   // Compute the smallest capacity allowing |aLength| elements to be inserted
   // without rehashing.
   uint32_t capacity = (aLength * 4 + (3 - 1)) / 3; // == ceil(aLength * 4 / 3)
-  if (capacity < PL_DHASH_MIN_CAPACITY) {
-    capacity = PL_DHASH_MIN_CAPACITY;
+  if (capacity < PLDHashTable::kMinCapacity) {
+    capacity = PLDHashTable::kMinCapacity;
   }
 
   // Round up capacity to next power-of-two.
   uint32_t log2 = CeilingLog2(capacity);
   capacity = 1u << log2;
-  MOZ_ASSERT(capacity <= PL_DHASH_MAX_CAPACITY);
+  MOZ_ASSERT(capacity <= PLDHashTable::kMaxCapacity);
 
   *aCapacityOut = capacity;
   *aLog2CapacityOut = log2;
 }
 
-static MOZ_ALWAYS_INLINE uint32_t
-HashShift(uint32_t aEntrySize, uint32_t aLength)
+/* static */ MOZ_ALWAYS_INLINE uint32_t
+PLDHashTable::HashShift(uint32_t aEntrySize, uint32_t aLength)
 {
-  if (aLength > PL_DHASH_MAX_INITIAL_LENGTH) {
+  if (aLength > kMaxInitialLength) {
     MOZ_CRASH("Initial length is too large");
   }
 
   uint32_t capacity, log2;
   BestCapacity(aLength, &capacity, &log2);
 
   uint32_t nbytes;
   if (!SizeOfEntryStore(capacity, aEntrySize, &nbytes)) {
     MOZ_CRASH("Initial entry store size is too large");
   }
 
   // Compute the hashShift value.
-  return PL_DHASH_BITS - log2;
+  return kHashBits - log2;
 }
 
 PLDHashTable::PLDHashTable(const PLDHashTableOps* aOps, uint32_t aEntrySize,
                            uint32_t aLength)
   : mOps(aOps)
   , mHashShift(HashShift(aEntrySize, aLength))
   , mEntrySize(aEntrySize)
   , mEntryCount(0)
@@ -342,17 +342,17 @@ PLDHashTable::ClearAndPrepareForLength(u
 
   this->~PLDHashTable();
   new (this) PLDHashTable(ops, entrySize, aLength);
 }
 
 void
 PLDHashTable::Clear()
 {
-  ClearAndPrepareForLength(PL_DHASH_DEFAULT_INITIAL_LENGTH);
+  ClearAndPrepareForLength(kDefaultInitialLength);
 }
 
 // If |IsAdd| is true, the return value is always non-null and it may be a
 // previously-removed entry. If |IsAdd| is false, the return value is null on a
 // miss, and will never be a previously-removed entry on a hit. This
 // distinction is a bit grotty but this function is hot enough that these
 // differences are worthwhile.
 template <PLDHashTable::SearchReason Reason>
@@ -375,17 +375,17 @@ PLDHashTable::SearchTable(const void* aK
   /* Hit: return entry. */
   PLDHashMatchEntry matchEntry = mOps->matchEntry;
   if (MATCH_ENTRY_KEYHASH(entry, aKeyHash) &&
       matchEntry(this, entry, aKey)) {
     return entry;
   }
 
   /* Collision: double hash. */
-  int sizeLog2 = PL_DHASH_BITS - mHashShift;
+  int sizeLog2 = kHashBits - mHashShift;
   PLDHashNumber hash2 = HASH2(aKeyHash, sizeLog2, mHashShift);
   uint32_t sizeMask = (1u << sizeLog2) - 1;
 
   /*
    * Save the first removed entry pointer so Add() can recycle it. (Only used
    * if Reason==ForAdd.)
    */
   PLDHashEntryHdr* firstRemoved = nullptr;
@@ -442,17 +442,17 @@ PLDHashTable::FindFreeEntry(PLDHashNumbe
   PLDHashEntryHdr* entry = ADDRESS_ENTRY(this, hash1);
 
   /* Miss: return space for a new entry. */
   if (EntryIsFree(entry)) {
     return entry;
   }
 
   /* Collision: double hash. */
-  int sizeLog2 = PL_DHASH_BITS - mHashShift;
+  int sizeLog2 = kHashBits - mHashShift;
   PLDHashNumber hash2 = HASH2(aKeyHash, sizeLog2, mHashShift);
   uint32_t sizeMask = (1u << sizeLog2) - 1;
 
   for (;;) {
     NS_ASSERTION(!ENTRY_IS_REMOVED(entry),
                  "!ENTRY_IS_REMOVED(entry)");
     entry->mKeyHash |= COLLISION_FLAG;
 
@@ -470,35 +470,35 @@ PLDHashTable::FindFreeEntry(PLDHashNumbe
 }
 
 bool
 PLDHashTable::ChangeTable(int32_t aDeltaLog2)
 {
   MOZ_ASSERT(mEntryStore);
 
   /* Look, but don't touch, until we succeed in getting new entry store. */
-  int32_t oldLog2 = PL_DHASH_BITS - mHashShift;
+  int32_t oldLog2 = kHashBits - mHashShift;
   int32_t newLog2 = oldLog2 + aDeltaLog2;
   uint32_t newCapacity = 1u << newLog2;
-  if (newCapacity > PL_DHASH_MAX_CAPACITY) {
+  if (newCapacity > kMaxCapacity) {
     return false;
   }
 
   uint32_t nbytes;
   if (!SizeOfEntryStore(newCapacity, mEntrySize, &nbytes)) {
     return false;   // overflowed
   }
 
   char* newEntryStore = (char*)malloc(nbytes);
   if (!newEntryStore) {
     return false;
   }
 
   /* We can't fail from here on, so update table parameters. */
-  mHashShift = PL_DHASH_BITS - newLog2;
+  mHashShift = kHashBits - newLog2;
   mRemovedCount = 0;
   mGeneration++;
 
   /* Assign the new entry store to table. */
   memset(newEntryStore, 0, nbytes);
   char* oldEntryStore;
   char* oldEntryAddr;
   oldEntryAddr = oldEntryStore = mEntryStore;
@@ -524,17 +524,17 @@ PLDHashTable::ChangeTable(int32_t aDelta
 }
 
 MOZ_ALWAYS_INLINE PLDHashNumber
 PLDHashTable::ComputeKeyHash(const void* aKey)
 {
   MOZ_ASSERT(mEntryStore);
 
   PLDHashNumber keyHash = mOps->hashKey(this, aKey);
-  keyHash *= PL_DHASH_GOLDEN_RATIO;
+  keyHash *= kGoldenRatio;
 
   /* Avoid 0 and 1 hash codes, they indicate free and removed entries. */
   ENSURE_LIVE_KEYHASH(keyHash);
   keyHash &= ~COLLISION_FLAG;
 
   return keyHash;
 }
 
@@ -652,17 +652,17 @@ PLDHashTable::Remove(const void* aKey)
     mEntryStore ? SearchTable<ForSearchOrRemove>(aKey, ComputeKeyHash(aKey))
                 : nullptr;
   if (entry) {
     /* Clear this entry and mark it as "removed". */
     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 &&
+    if (capacity > kMinCapacity &&
         mEntryCount <= MinLoad(capacity)) {
       (void) ChangeTable(-1);
     }
   }
 }
 
 PLDHashEntryHdr* PL_DHASH_FASTCALL
 PL_DHashTableSearch(PLDHashTable* aTable, const void* aKey)
@@ -722,21 +722,21 @@ PL_DHashTableRawRemove(PLDHashTable* aTa
 // 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.
 void
 PLDHashTable::ShrinkIfAppropriate()
 {
   uint32_t capacity = Capacity();
   if (mRemovedCount >= capacity >> 2 ||
-      (capacity > PL_DHASH_MIN_CAPACITY && mEntryCount <= MinLoad(capacity))) {
+      (capacity > kMinCapacity && mEntryCount <= MinLoad(capacity))) {
     uint32_t log2;
     BestCapacity(mEntryCount, &capacity, &log2);
 
-    int32_t deltaLog2 = log2 - (PL_DHASH_BITS - mHashShift);
+    int32_t deltaLog2 = log2 - (kHashBits - mHashShift);
     MOZ_ASSERT(deltaLog2 <= 0);
 
     (void) ChangeTable(deltaLog2);
   }
 }
 
 MOZ_ALWAYS_INLINE size_t
 PLDHashTable::SizeOfExcludingThis(
--- a/xpcom/glue/pldhash.h
+++ b/xpcom/glue/pldhash.h
@@ -20,43 +20,16 @@
 #if defined(__GNUC__) && defined(__i386__)
 #define PL_DHASH_FASTCALL __attribute__ ((regparm (3),stdcall))
 #elif defined(XP_WIN)
 #define PL_DHASH_FASTCALL __fastcall
 #else
 #define PL_DHASH_FASTCALL
 #endif
 
-/*
- * Table capacity limit; do not exceed.  The max capacity used to be 1<<23 but
- * that occasionally that wasn't enough.  Making it much bigger than 1<<26
- * probably isn't worthwhile -- tables that big are kind of ridiculous.  Also,
- * the growth operation will (deliberately) fail if |capacity * mEntrySize|
- * overflows a uint32_t, and mEntrySize is always at least 8 bytes.
- */
-#define PL_DHASH_MAX_CAPACITY           ((uint32_t)1 << 26)
-
-#define PL_DHASH_MIN_CAPACITY           8
-
-/*
- * Making this half of the max capacity ensures it'll fit. Nobody should need
- * an initial length anywhere nearly this large, anyway.
- */
-#define PL_DHASH_MAX_INITIAL_LENGTH     (PL_DHASH_MAX_CAPACITY / 2)
-
-/* This gives a default initial capacity of 8. */
-#define PL_DHASH_DEFAULT_INITIAL_LENGTH 4
-
-/*
- * Multiplicative hash uses an unsigned 32 bit integer and the golden ratio,
- * expressed as a fixed-point 32-bit fraction.
- */
-#define PL_DHASH_BITS           32
-#define PL_DHASH_GOLDEN_RATIO   0x9E3779B9U
-
 typedef uint32_t PLDHashNumber;
 
 class PLDHashTable;
 struct PLDHashTableOps;
 
 /*
  * Table entry header structure.
  *
@@ -65,20 +38,20 @@ struct PLDHashTableOps;
  * The key need not be stored in the entry; it may be part of the value, but
  * need not be stored at all.
  *
  * Callback types are defined below and grouped into the PLDHashTableOps
  * structure, for single static initialization per hash table sub-type.
  *
  * Each hash table sub-type should make its entry type a subclass of
  * PLDHashEntryHdr. The mKeyHash 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 mKeyHash value is table size invariant, and it is
- * maintained automatically -- users need never access it.
+ * hash code returned from the hashKey callback (see below) by kGoldenRatio,
+ * then constraining the result to avoid the magic 0 and 1 values. The stored
+ * mKeyHash value is table size invariant, and it is maintained automatically
+ * -- users need never access it.
  */
 struct PLDHashEntryHdr
 {
 private:
   friend class PLDHashTable;
 
   PLDHashNumber mKeyHash;
 };
@@ -259,26 +232,43 @@ private:
   uint32_t            mGeneration;    /* entry storage generation number */
   char*               mEntryStore;    /* entry storage; allocated lazily */
 
 #ifdef DEBUG
   mutable Checker mChecker;
 #endif
 
 public:
+  // Table capacity limit; do not exceed. The max capacity used to be 1<<23 but
+  // that occasionally that wasn't enough. Making it much bigger than 1<<26
+  // probably isn't worthwhile -- tables that big are kind of ridiculous.
+  // Also, the growth operation will (deliberately) fail if |capacity *
+  // mEntrySize| overflows a uint32_t, and mEntrySize is always at least 8
+  // bytes.
+  static const uint32_t kMaxCapacity = ((uint32_t)1 << 26);
+
+  static const uint32_t kMinCapacity = 8;
+
+  // Making this half of kMaxCapacity ensures it'll fit. Nobody should need an
+  // initial length anywhere nearly this large, anyway.
+  static const uint32_t kMaxInitialLength = kMaxCapacity / 2;
+
+  // This gives a default initial capacity of 8.
+  static const uint32_t kDefaultInitialLength = 4;
+
   // Initialize the table with |aOps| and |aEntrySize|. The table's initial
   // capacity is chosen such that |aLength| elements can be inserted without
   // rehashing; if |aLength| is a power-of-two, this capacity will be
   // |2*length|. However, because entry storage is allocated lazily, this
   // initial capacity won't be relevant until the first element is added; prior
   // to that the capacity will be zero.
   //
   // This will crash if |aEntrySize| and/or |aLength| are too large.
   PLDHashTable(const PLDHashTableOps* aOps, uint32_t aEntrySize,
-               uint32_t aLength = PL_DHASH_DEFAULT_INITIAL_LENGTH);
+               uint32_t aLength = kDefaultInitialLength);
 
   PLDHashTable(PLDHashTable&& aOther)
       // These two fields are |const|. Initialize them here because the
       // move assignment operator cannot modify them.
     : mOps(aOther.mOps)
     , mEntrySize(aOther.mEntrySize)
       // Initialize these two fields because they are required for a safe call
       // to the destructor, which the move assignment operator does.
@@ -314,17 +304,17 @@ public:
   PLDHashEntryHdr* Search(const void* aKey);
   PLDHashEntryHdr* Add(const void* aKey, const mozilla::fallible_t&);
   PLDHashEntryHdr* Add(const void* aKey);
   void Remove(const void* aKey);
 
   void RawRemove(PLDHashEntryHdr* aEntry);
 
   // This function is equivalent to
-  // ClearAndPrepareForLength(PL_DHASH_DEFAULT_INITIAL_LENGTH).
+  // ClearAndPrepareForLength(kDefaultInitialLength).
   void Clear();
 
   // This function clears the table's contents and frees its entry storage,
   // leaving it in a empty state ready to be used again. Afterwards, when the
   // first element is added the entry storage that gets allocated will have a
   // capacity large enough to fit |aLength| elements without rehashing.
   //
   // It's conceptually the same as calling the destructor and then re-calling
@@ -415,23 +405,30 @@ public:
   // Use this if you need to initialize an Iterator in a const method. If you
   // use this case, you should not call Remove() on the iterator.
   Iterator ConstIter() const
   {
     return Iterator(const_cast<PLDHashTable*>(this));
   }
 
 private:
+  // Multiplicative hash uses an unsigned 32 bit integer and the golden ratio,
+  // expressed as a fixed-point 32-bit fraction.
+  static const uint32_t kHashBits = 32;
+  static const uint32_t kGoldenRatio = 0x9E3779B9U;
+
+  static uint32_t HashShift(uint32_t aEntrySize, uint32_t aLength);
+
   static bool EntryIsFree(PLDHashEntryHdr* aEntry);
 
   // We store mHashShift rather than sizeLog2 to optimize the collision-free
   // case in SearchTable.
   uint32_t CapacityFromHashShift() const
   {
-    return ((uint32_t)1 << (PL_DHASH_BITS - mHashShift));
+    return ((uint32_t)1 << (kHashBits - mHashShift));
   }
 
   PLDHashNumber ComputeKeyHash(const void* aKey);
 
   enum SearchReason { ForSearchOrRemove, ForAdd };
 
   template <SearchReason Reason>
   PLDHashEntryHdr* PL_DHASH_FASTCALL
--- a/xpcom/tests/gtest/TestPLDHash.cpp
+++ b/xpcom/tests/gtest/TestPLDHash.cpp
@@ -73,35 +73,35 @@ TestCrashyOperation(void (*aCrashyOperat
   _gdb_sleep_duration = old_gdb_sleep_duration;
 #endif
 }
 
 void
 InitCapacityOk_InitialLengthTooBig()
 {
   PLDHashTable t(PL_DHashGetStubOps(), sizeof(PLDHashEntryStub),
-                 PL_DHASH_MAX_INITIAL_LENGTH + 1);
+                 PLDHashTable::kMaxInitialLength + 1);
 }
 
 void
 InitCapacityOk_InitialEntryStoreTooBig()
 {
   // Try the smallest disallowed power-of-two entry store size, which is 2^32
   // bytes (which overflows to 0). (Note that the 2^23 *length* gets converted
   // to a 2^24 *capacity*.)
   PLDHashTable t(PL_DHashGetStubOps(), (uint32_t)1 << 23, (uint32_t)1 << 8);
 }
 
 TEST(PLDHashTableTest, InitCapacityOk)
 {
-  // Try the largest allowed capacity.  With PL_DHASH_MAX_CAPACITY==1<<26, this
+  // Try the largest allowed capacity.  With kMaxCapacity==1<<26, this
   // would allocate (if we added an element) 0.5GB of entry store on 32-bit
   // platforms and 1GB on 64-bit platforms.
   PLDHashTable t1(PL_DHashGetStubOps(), sizeof(PLDHashEntryStub),
-                 PL_DHASH_MAX_INITIAL_LENGTH);
+                  PLDHashTable::kMaxInitialLength);
 
   // Try the largest allowed power-of-two entry store size, which is 2^31 bytes
   // (Note that the 2^23 *length* gets converted to a 2^24 *capacity*.)
   PLDHashTable t2(PL_DHashGetStubOps(), (uint32_t)1 << 23, (uint32_t)1 << 7);
 
   // Try a too-large capacity (which aborts).
   TestCrashyOperation(InitCapacityOk_InitialLengthTooBig);
 
@@ -309,17 +309,17 @@ TEST(PLDHashTableTest, Iterator)
   ASSERT_EQ(t.Capacity(), 64u);
 
   // The fourth removing iterator removes all remaining items. This reduces
   // the capacity to the minimum.
   for (auto iter = t.Iter(); !iter.Done(); iter.Next()) {
     iter.Remove();
   }
   ASSERT_EQ(t.EntryCount(), 0u);
-  ASSERT_EQ(t.Capacity(), unsigned(PL_DHASH_MIN_CAPACITY));
+  ASSERT_EQ(t.Capacity(), unsigned(PLDHashTable::kMinCapacity));
 }
 
 // See bug 931062, we skip this test on Android due to OOM. Also, it's slow,
 // and so should always be last.
 #ifndef MOZ_WIDGET_ANDROID
 TEST(PLDHashTableTest, GrowToMaxCapacity)
 {
   // This is infallible.
@@ -332,17 +332,18 @@ TEST(PLDHashTableTest, GrowToMaxCapacity
     if (!PL_DHashTableAdd(t, (const void*)numInserted, mozilla::fallible)) {
       break;
     }
     numInserted++;
   }
 
   // We stop when the element count is 96.875% of PL_DHASH_MAX_SIZE (see
   // MaxLoadOnGrowthFailure()).
-  if (numInserted != PL_DHASH_MAX_CAPACITY - (PL_DHASH_MAX_CAPACITY >> 5)) {
+  if (numInserted !=
+      PLDHashTable::kMaxCapacity - (PLDHashTable::kMaxCapacity >> 5)) {
     delete t;
     ASSERT_TRUE(false);
   }
 
   delete t;
 }
 #endif