Refactor StringMap.h, splitting StringMapEntry out to its own header.

[lattner]

Summary

StringMapEntry.h can have lower dependencies, than StringMap.h, which
is useful for public headers that want to expose inline methods on
StringMapEntry<> but don't need to expose all of StringMap.h. One
example of this is mlir's Identifier.h, another example is the existing
LLVM StringPool.h.

StringPool also could use a cleanup, I'll deal with that in a follow-on
patch.

[rriddle]

This justification for this split seems along the same lines as the split of DenseMap/DenseMapInfo, so LGTM.

llvm/include/llvm/ADT/StringMapEntry.h

50

nit: E -> entry here and InitVals -> initVals above.

[ekatz]

The variables naming convention is inconsistent.
LLVM is using CamelCase while MLIR is using camelBack.
I know there have been some discussions regarding changing LLVM to use camelBack for variables as well, but I am not sure if there was any conclusion...

[lattner]

fix casing in a couple places I missed

[lattner]

Good catch, thanks River.

Ehud, we have generally agreed we should move this direction, the question is how best to stage in the changes without breaking history pervasively. This is a new file, so that issue doesn't apply.

llvm/include/llvm/ADT/StringMap.h

 //===- StringMap.h - String Hash table map interface ------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines the StringMap class.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_STRINGMAP_H
 #define LLVM_ADT_STRINGMAP_H
 
-#include "llvm/ADT/StringRef.h"
-#include "llvm/Support/AllocatorBase.h"
+#include "llvm/ADT/StringMapEntry.h"
 #include "llvm/Support/PointerLikeTypeTraits.h"
 #include <initializer_list>
 #include <iterator>
 
 namespace llvm {
 
 template <typename ValueTy> class StringMapConstIterator;
 template <typename ValueTy> class StringMapIterator;
 template <typename ValueTy> class StringMapKeyIterator;
 
-/// StringMapEntryBase - Shared base class of StringMapEntry instances.
-class StringMapEntryBase {
-  size_t StrLen;
-
-public:
-  explicit StringMapEntryBase(size_t Len) : StrLen(Len) {}
-
-  size_t getKeyLength() const { return StrLen; }
-};
-
 /// StringMapImpl - This is the base class of StringMap that is shared among
 /// all of its instantiations.
 class StringMapImpl {
 protected:
   // Array of NumBuckets pointers to entries, null pointers are holes.
   // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed
   // by an array of the actual hash values as unsigned integers.
   StringMapEntryBase **TheTable = nullptr;
public:
   void swap(StringMapImpl &Other) {
     std::swap(TheTable, Other.TheTable);
     std::swap(NumBuckets, Other.NumBuckets);
     std::swap(NumItems, Other.NumItems);
     std::swap(NumTombstones, Other.NumTombstones);
   }
 };
 
-/// StringMapEntryStorage - Holds the value in a StringMapEntry.
-///
-/// Factored out into a separate base class to make it easier to specialize.
-/// This is primarily intended to support StringSet, which doesn't need a value
-/// stored at all.
-template <typename ValueTy>
-class StringMapEntryStorage : public StringMapEntryBase {
-public:
-  ValueTy second;
-
-  explicit StringMapEntryStorage(size_t strLen)
-      : StringMapEntryBase(strLen), second() {}
-  template <typename... InitTy>
-  StringMapEntryStorage(size_t strLen, InitTy &&... InitVals)
-      : StringMapEntryBase(strLen), second(std::forward<InitTy>(InitVals)...) {}
-  StringMapEntryStorage(StringMapEntryStorage &E) = delete;
-
-  const ValueTy &getValue() const { return second; }
-  ValueTy &getValue() { return second; }
-
-  void setValue(const ValueTy &V) { second = V; }
-};
-
-template <> class StringMapEntryStorage<NoneType> : public StringMapEntryBase {
-public:
-  explicit StringMapEntryStorage(size_t strLen, NoneType none = None)
-      : StringMapEntryBase(strLen) {}
-  StringMapEntryStorage(StringMapEntryStorage &E) = delete;
-
-  NoneType getValue() const { return None; }
-};
-
-/// StringMapEntry - This is used to represent one value that is inserted into
-/// a StringMap.  It contains the Value itself and the key: the string length
-/// and data.
-template <typename ValueTy>
-class StringMapEntry final : public StringMapEntryStorage<ValueTy> {
-public:
-  using StringMapEntryStorage<ValueTy>::StringMapEntryStorage;
-
-  StringRef getKey() const {
-    return StringRef(getKeyData(), this->getKeyLength());
-  }
-
-  /// getKeyData - Return the start of the string data that is the key for this
-  /// value.  The string data is always stored immediately after the
-  /// StringMapEntry object.
-  const char *getKeyData() const {
-    return reinterpret_cast<const char *>(this + 1);
-  }
-
-  StringRef first() const {
-    return StringRef(getKeyData(), this->getKeyLength());
-  }
-
-  /// Create a StringMapEntry for the specified key construct the value using
-  /// \p InitiVals.
-  template <typename AllocatorTy, typename... InitTy>
-  static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator,
-                                InitTy &&... InitVals) {
-    size_t KeyLength = Key.size();
-
-    // Allocate a new item with space for the string at the end and a null
-    // terminator.
-    size_t AllocSize = sizeof(StringMapEntry) + KeyLength + 1;
-    size_t Alignment = alignof(StringMapEntry);
-
-    StringMapEntry *NewItem =
-        static_cast<StringMapEntry *>(Allocator.Allocate(AllocSize, Alignment));
-    assert(NewItem && "Unhandled out-of-memory");
-
-    // Construct the value.
-    new (NewItem) StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...);
-
-    // Copy the string information.
-    char *StrBuffer = const_cast<char *>(NewItem->getKeyData());
-    if (KeyLength > 0)
-      memcpy(StrBuffer, Key.data(), KeyLength);
-    StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients.
-    return NewItem;
-  }
-
-  /// Create - Create a StringMapEntry with normal malloc/free.
-  template <typename... InitType>
-  static StringMapEntry *Create(StringRef Key, InitType &&... InitVal) {
-    MallocAllocator A;
-    return Create(Key, A, std::forward<InitType>(InitVal)...);
-  }
-
-  static StringMapEntry *Create(StringRef Key) {
-    return Create(Key, ValueTy());
-  }
-
-  /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded
-  /// into a StringMapEntry, return the StringMapEntry itself.
-  static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) {
-    char *Ptr = const_cast<char *>(KeyData) - sizeof(StringMapEntry<ValueTy>);
-    return *reinterpret_cast<StringMapEntry *>(Ptr);
-  }
-
-  /// Destroy - Destroy this StringMapEntry, releasing memory back to the
-  /// specified allocator.
-  template <typename AllocatorTy> void Destroy(AllocatorTy &Allocator) {
-    // Free memory referenced by the item.
-    size_t AllocSize = sizeof(StringMapEntry) + this->getKeyLength() + 1;
-    this->~StringMapEntry();
-    Allocator.Deallocate(static_cast<void *>(this), AllocSize);
-  }
-
-  /// Destroy this object, releasing memory back to the malloc allocator.
-  void Destroy() {
-    MallocAllocator A;
-    Destroy(A);
-  }
-};
-
 /// StringMap - This is an unconventional map that is specialized for handling
 /// keys that are "strings", which are basically ranges of bytes. This does some
 /// funky memory allocation and hashing things to make it extremely efficient,
 /// storing the string data *after* the value in the map.
 template <typename ValueTy, typename AllocatorTy = MallocAllocator>
 class StringMap : public StringMapImpl {
   AllocatorTy Allocator;
 

llvm/include/llvm/ADT/StringMapEntry.h

+//===- StringMapEntry.h - String Hash table map interface -------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the StringMapEntry class - it is intended to be a low
+// dependency implementation detail of StringMap that is more suitable for
+// inclusion in public headers than StringMap.h itself is.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_STRINGMAPENTRY_H
+#define LLVM_ADT_STRINGMAPENTRY_H
+
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/AllocatorBase.h"
+
+namespace llvm {
+
+/// StringMapEntryBase - Shared base class of StringMapEntry instances.
+class StringMapEntryBase {
+  size_t keyLength;
+
+public:
+  explicit StringMapEntryBase(size_t keyLength) : keyLength(keyLength) {}
+
+  size_t getKeyLength() const { return keyLength; }
+};
+
+/// StringMapEntryStorage - Holds the value in a StringMapEntry.
+///
+/// Factored out into a separate base class to make it easier to specialize.
+/// This is primarily intended to support StringSet, which doesn't need a value
+/// stored at all.
+template <typename ValueTy>
+class StringMapEntryStorage : public StringMapEntryBase {
+public:
+  ValueTy second;
+
+  explicit StringMapEntryStorage(size_t keyLength)
+      : StringMapEntryBase(keyLength), second() {}
+  template <typename... InitTy>
+  StringMapEntryStorage(size_t keyLength, InitTy &&... initVals)
+      : StringMapEntryBase(keyLength),
+        second(std::forward<InitTy>(initVals)...) {}
+  StringMapEntryStorage(StringMapEntryStorage &e) = delete;
+
+  const ValueTy &getValue() const { return second; }
+  ValueTy &getValue() { return second; }
+
+  void setValue(const ValueTy &V) { second = V; }
+};
+
+template <> class StringMapEntryStorage<NoneType> : public StringMapEntryBase {
+public:
+  explicit StringMapEntryStorage(size_t keyLength, NoneType none = None)
+      : StringMapEntryBase(keyLength) {}
+  StringMapEntryStorage(StringMapEntryStorage &entry) = delete;
+
+  NoneType getValue() const { return None; }
+};
+
+/// StringMapEntry - This is used to represent one value that is inserted into
+/// a StringMap.  It contains the Value itself and the key: the string length
+/// and data.
+template <typename ValueTy>
+class StringMapEntry final : public StringMapEntryStorage<ValueTy> {
+public:
+  using StringMapEntryStorage<ValueTy>::StringMapEntryStorage;
+
+  StringRef getKey() const {
+    return StringRef(getKeyData(), this->getKeyLength());
+  }
+
+  /// getKeyData - Return the start of the string data that is the key for this
+  /// value.  The string data is always stored immediately after the
+  /// StringMapEntry object.
+  const char *getKeyData() const {
+    return reinterpret_cast<const char *>(this + 1);
+  }
+
+  StringRef first() const {
+    return StringRef(getKeyData(), this->getKeyLength());
+  }
+
+  /// Create a StringMapEntry for the specified key construct the value using
+  /// \p InitiVals.
+  template <typename AllocatorTy, typename... InitTy>
+  static StringMapEntry *Create(StringRef key, AllocatorTy &allocator,
+                                InitTy &&... initVals) {
+    size_t keyLength = key.size();
+
+    // Allocate a new item with space for the string at the end and a null
+    // terminator.
+    size_t allocSize = sizeof(StringMapEntry) + keyLength + 1;
+    size_t alignment = alignof(StringMapEntry);
+
+    StringMapEntry *newItem =
+        static_cast<StringMapEntry *>(allocator.Allocate(allocSize, alignment));
+    assert(newItem && "Unhandled out-of-memory");
+
+    // Construct the value.
+    new (newItem) StringMapEntry(keyLength, std::forward<InitTy>(initVals)...);
+
+    // Copy the string information.
+    char *strBuffer = const_cast<char *>(newItem->getKeyData());
+    if (keyLength > 0)
+      memcpy(strBuffer, key.data(), keyLength);
+    strBuffer[keyLength] = 0; // Null terminate for convenience of clients.
+    return newItem;
+  }
+
+  /// Create - Create a StringMapEntry with normal malloc/free.
+  template <typename... InitType>
+  static StringMapEntry *Create(StringRef key, InitType &&... initVal) {
+    MallocAllocator allocator;
+    return Create(key, allocator, std::forward<InitType>(initVal)...);
+  }
+
+  static StringMapEntry *Create(StringRef key) {
+    return Create(key, ValueTy());
+  }
+
+  /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded
+  /// into a StringMapEntry, return the StringMapEntry itself.
+  static StringMapEntry &GetStringMapEntryFromKeyData(const char *keyData) {
+    char *ptr = const_cast<char *>(keyData) - sizeof(StringMapEntry<ValueTy>);
+    return *reinterpret_cast<StringMapEntry *>(ptr);
+  }
+
+  /// Destroy - Destroy this StringMapEntry, releasing memory back to the
+  /// specified allocator.
+  template <typename AllocatorTy> void Destroy(AllocatorTy &allocator) {
+    // Free memory referenced by the item.
+    size_t AllocSize = sizeof(StringMapEntry) + this->getKeyLength() + 1;
+    this->~StringMapEntry();
+    allocator.Deallocate(static_cast<void *>(this), AllocSize);
+  }
+
+  /// Destroy this object, releasing memory back to the malloc allocator.
+  void Destroy() {
+    MallocAllocator allocator;
+    Destroy(allocator);
+  }
+};
+
+} // end namespace llvm
+
+#endif // LLVM_ADT_STRINGMAPENTRY_H

llvm/lib/Support/StringMap.cpp

 //===--- StringMap.cpp - String Hash table map implementation -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the StringMap class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringExtras.h"
-#include "llvm/Support/Compiler.h"
 #include "llvm/Support/DJB.h"
 #include "llvm/Support/MathExtras.h"
-#include <cassert>
 
 using namespace llvm;
 
 /// Returns the number of buckets to allocate to ensure that the DenseMap can
 /// accommodate \p NumEntries without need to grow().
 static unsigned getMinBucketToReserveForEntries(unsigned NumEntries) {
   // Ensure that "NumEntries * 4 < NumBuckets * 3"
   if (NumEntries == 0)
StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) {
   // Otherwise, initialize it with zero buckets to avoid the allocation.
   TheTable = nullptr;
   NumBuckets = 0;
   NumItems = 0;
   NumTombstones = 0;
 }
 
 void StringMapImpl::init(unsigned InitSize) {
-  assert((InitSize & (InitSize-1)) == 0 &&
+  assert((InitSize & (InitSize - 1)) == 0 &&
          "Init Size must be a power of 2 or zero!");
 
   unsigned NewNumBuckets = InitSize ? InitSize : 16;
   NumItems = 0;
   NumTombstones = 0;
 
-  TheTable = static_cast<StringMapEntryBase **>(
-      safe_calloc(NewNumBuckets+1,
-                  sizeof(StringMapEntryBase **) + sizeof(unsigned)));
+  TheTable = static_cast<StringMapEntryBase **>(safe_calloc(
+      NewNumBuckets + 1, sizeof(StringMapEntryBase **) + sizeof(unsigned)));
 
   // Set the member only if TheTable was successfully allocated
   NumBuckets = NewNumBuckets;
 
   // Allocate one extra bucket, set it to look filled so the iterators stop at
   // end.
-  TheTable[NumBuckets] = (StringMapEntryBase*)2;
+  TheTable[NumBuckets] = (StringMapEntryBase *)2;
 }
 
 /// LookupBucketFor - Look up the bucket that the specified string should end
 /// up in.  If it already exists as a key in the map, the Item pointer for the
 /// specified bucket will be non-null.  Otherwise, it will be null.  In either
 /// case, the FullHashValue field of the bucket will be set to the hash value
 /// of the string.
 unsigned StringMapImpl::LookupBucketFor(StringRef Name) {
   unsigned HTSize = NumBuckets;
-  if (HTSize == 0) {  // Hash table unallocated so far?
+  if (HTSize == 0) { // Hash table unallocated so far?
     init(16);
     HTSize = NumBuckets;
   }
   unsigned FullHashValue = djbHash(Name, 0);
-  unsigned BucketNo = FullHashValue & (HTSize-1);
+  unsigned BucketNo = FullHashValue & (HTSize - 1);
   unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
 
   unsigned ProbeAmt = 1;
   int FirstTombstone = -1;
   while (true) {
     StringMapEntryBase *BucketItem = TheTable[BucketNo];
     // If we found an empty bucket, this key isn't in the table yet, return it.
     if (LLVM_LIKELY(!BucketItem)) {
       // If we found a tombstone, we want to reuse the tombstone instead of an
       // empty bucket.  This reduces probing.
       if (FirstTombstone != -1) {
         HashTable[FirstTombstone] = FullHashValue;
         return FirstTombstone;
       }
 
       HashTable[BucketNo] = FullHashValue;
       return BucketNo;
     }
 
     if (BucketItem == getTombstoneVal()) {
       // Skip over tombstones.  However, remember the first one we see.
-      if (FirstTombstone == -1) FirstTombstone = BucketNo;
+      if (FirstTombstone == -1)
+        FirstTombstone = BucketNo;
     } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) {
       // If the full hash value matches, check deeply for a match.  The common
       // case here is that we are only looking at the buckets (for item info
       // being non-null and for the full hash value) not at the items.  This
       // is important for cache locality.
 
       // Do the comparison like this because Name isn't necessarily
       // null-terminated!
-      char *ItemStr = (char*)BucketItem+ItemSize;
+      char *ItemStr = (char *)BucketItem + ItemSize;
       if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) {
         // We found a match!
         return BucketNo;
       }
     }
 
     // Okay, we didn't find the item.  Probe to the next bucket.
-    BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
+    BucketNo = (BucketNo + ProbeAmt) & (HTSize - 1);
 
     // Use quadratic probing, it has fewer clumping artifacts than linear
     // probing and has good cache behavior in the common case.
     ++ProbeAmt;
   }
 }
 
 /// FindKey - Look up the bucket that contains the specified key. If it exists
 /// in the map, return the bucket number of the key.  Otherwise return -1.
 /// This does not modify the map.
 int StringMapImpl::FindKey(StringRef Key) const {
   unsigned HTSize = NumBuckets;
-  if (HTSize == 0) return -1;  // Really empty table?
+  if (HTSize == 0)
+    return -1; // Really empty table?
   unsigned FullHashValue = djbHash(Key, 0);
-  unsigned BucketNo = FullHashValue & (HTSize-1);
+  unsigned BucketNo = FullHashValue & (HTSize - 1);
   unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
 
   unsigned ProbeAmt = 1;
   while (true) {
     StringMapEntryBase *BucketItem = TheTable[BucketNo];
     // If we found an empty bucket, this key isn't in the table yet, return.
     if (LLVM_LIKELY(!BucketItem))
       return -1;
 
     if (BucketItem == getTombstoneVal()) {
       // Ignore tombstones.
     } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) {
       // If the full hash value matches, check deeply for a match.  The common
       // case here is that we are only looking at the buckets (for item info
       // being non-null and for the full hash value) not at the items.  This
       // is important for cache locality.
 
       // Do the comparison like this because NameStart isn't necessarily
       // null-terminated!
-      char *ItemStr = (char*)BucketItem+ItemSize;
+      char *ItemStr = (char *)BucketItem + ItemSize;
       if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) {
         // We found a match!
         return BucketNo;
       }
     }
 
     // Okay, we didn't find the item.  Probe to the next bucket.
-    BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
+    BucketNo = (BucketNo + ProbeAmt) & (HTSize - 1);
 
     // Use quadratic probing, it has fewer clumping artifacts than linear
     // probing and has good cache behavior in the common case.
     ++ProbeAmt;
   }
 }
 
 /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
 /// delete it.  This aborts if the value isn't in the table.
 void StringMapImpl::RemoveKey(StringMapEntryBase *V) {
-  const char *VStr = (char*)V + ItemSize;
+  const char *VStr = (char *)V + ItemSize;
   StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength()));
   (void)V2;
   assert(V == V2 && "Didn't find key?");
 }
 
 /// RemoveKey - Remove the StringMapEntry for the specified key from the
 /// table, returning it.  If the key is not in the table, this returns null.
 StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) {
   int Bucket = FindKey(Key);
-  if (Bucket == -1) return nullptr;
+  if (Bucket == -1)
+    return nullptr;
 
   StringMapEntryBase *Result = TheTable[Bucket];
   TheTable[Bucket] = getTombstoneVal();
   --NumItems;
   ++NumTombstones;
   assert(NumItems + NumTombstones <= NumBuckets);
 
   return Result;
 }
 
 /// RehashTable - Grow the table, redistributing values into the buckets with
 /// the appropriate mod-of-hashtable-size.
 unsigned StringMapImpl::RehashTable(unsigned BucketNo) {
   unsigned NewSize;
   unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
 
   // If the hash table is now more than 3/4 full, or if fewer than 1/8 of
   // the buckets are empty (meaning that many are filled with tombstones),
   // grow/rehash the table.
   if (LLVM_UNLIKELY(NumItems * 4 > NumBuckets * 3)) {
-    NewSize = NumBuckets*2;
+    NewSize = NumBuckets * 2;
   } else if (LLVM_UNLIKELY(NumBuckets - (NumItems + NumTombstones) <=
                            NumBuckets / 8)) {
     NewSize = NumBuckets;
   } else {
     return BucketNo;
   }
 
   unsigned NewBucketNo = BucketNo;
   // Allocate one extra bucket which will always be non-empty.  This allows the
   // iterators to stop at end.
-  auto NewTableArray = static_cast<StringMapEntryBase **>(
-      safe_calloc(NewSize+1, sizeof(StringMapEntryBase *) + sizeof(unsigned)));
+  auto NewTableArray = static_cast<StringMapEntryBase **>(safe_calloc(
+      NewSize + 1, sizeof(StringMapEntryBase *) + sizeof(unsigned)));
 
   unsigned *NewHashArray = (unsigned *)(NewTableArray + NewSize + 1);
-  NewTableArray[NewSize] = (StringMapEntryBase*)2;
+  NewTableArray[NewSize] = (StringMapEntryBase *)2;
 
   // Rehash all the items into their new buckets.  Luckily :) we already have
   // the hash values available, so we don't have to rehash any strings.
   for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
     StringMapEntryBase *Bucket = TheTable[I];
     if (Bucket && Bucket != getTombstoneVal()) {
       // Fast case, bucket available.
       unsigned FullHash = HashTable[I];
-      unsigned NewBucket = FullHash & (NewSize-1);
+      unsigned NewBucket = FullHash & (NewSize - 1);
       if (!NewTableArray[NewBucket]) {
-        NewTableArray[FullHash & (NewSize-1)] = Bucket;
-        NewHashArray[FullHash & (NewSize-1)] = FullHash;
+        NewTableArray[FullHash & (NewSize - 1)] = Bucket;
+        NewHashArray[FullHash & (NewSize - 1)] = FullHash;
         if (I == BucketNo)
           NewBucketNo = NewBucket;
         continue;
       }
 
       // Otherwise probe for a spot.
       unsigned ProbeSize = 1;
       do {
-        NewBucket = (NewBucket + ProbeSize++) & (NewSize-1);
+        NewBucket = (NewBucket + ProbeSize++) & (NewSize - 1);
       } while (NewTableArray[NewBucket]);
 
       // Finally found a slot.  Fill it in.
       NewTableArray[NewBucket] = Bucket;
       NewHashArray[NewBucket] = FullHash;
       if (I == BucketNo)
         NewBucketNo = NewBucket;
     }