Move DJB hash to support. NFC

[JDevlieghere]

Summary

This patch moves the DJB hash to support. It is used by dwarf for hasing
in the accelerator tables. Moving to support because we don't want to
link dsymutil against the BinaryFormat lib.

[aprantl]

This makes sense following the example of MD5.h

Don't you need to add it to the module map as well? Alternatively we could just stick this into MatchExtras.h/cpp.

include/llvm/Support/DJB.h

21 ↗

(On Diff #131635)

-> DWARF` accelerator tables.

[JDevlieghere]

In D42594#989492, @aprantl wrote:

Don't you need to add it to the module map as well?

Correct me if I'm wrong, but isn't it implicitly covered by umbrella "Support" in include/llvm/module.modulemap?

[JDevlieghere]

Added DWARF to Doxygen comment.

[aprantl]

If the module map is using an umbrella directory, then this will automatically work. Thanks!

llvm/trunk/include/llvm/BinaryFormat/Dwarf.h

enum {
     LINKAGE_OFFSET = 7,
     LINKAGE_MASK = 1 << LINKAGE_OFFSET
   };
 };
 
 /// Constants that define the DWARF format as 32 or 64 bit.
 enum DwarfFormat : uint8_t { DWARF32, DWARF64 };
 
-/// The Bernstein hash function used by the accelerator tables.
-uint32_t djbHash(StringRef Buffer, uint32_t H = 5381);
-
 } // End of namespace dwarf
 
 } // End of namespace llvm
 
 #endif

llvm/trunk/include/llvm/Support/DJB.h

+//===-- llvm/Support/DJB.h ---DJB Hash --------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains support for the DJ Bernstein hash function.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_DJB_H
+#define LLVM_SUPPORT_DJB_H
+
+#include "llvm/ADT/StringRef.h"
+
+namespace llvm {
+
+/// The Bernstein hash function used by the DWARF accelerator tables.
+uint32_t djbHash(StringRef Buffer, uint32_t H = 5381);
+} // namespace llvm
+
+#endif // LLVM_SUPPORT_DJB_H

llvm/trunk/lib/BinaryFormat/Dwarf.cpp

 bool llvm::dwarf::isValidFormForVersion(Form F, unsigned Version,
                                         bool ExtensionsOk) {
   if (FormVendor(F) == DWARF_VENDOR_DWARF) {
     unsigned FV = FormVersion(F);
     return FV > 0 && FV <= Version;
   }
   return ExtensionsOk;
 }
-
-uint32_t llvm::dwarf::djbHash(StringRef Buffer, uint32_t H) {
-  for (char C : Buffer.bytes())
-    H = ((H << 5) + H) + C;
-  return H;
-}

llvm/trunk/lib/CodeGen/AsmPrinter/DwarfAccelTable.h

 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/CodeGen/DIE.h"
 #include "llvm/CodeGen/DwarfStringPoolEntry.h"
 #include "llvm/MC/MCSymbol.h"
 #include "llvm/Support/Allocator.h"
+#include "llvm/Support/DJB.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cstddef>
 #include <cstdint>
 #include <vector>
 
 // The dwarf accelerator tables are an indirect hash table optimized
private:
   struct HashData {
     StringRef Str;
     uint32_t HashValue;
     MCSymbol *Sym;
     DwarfAccelTable::DataArray &Data; // offsets
 
     HashData(StringRef S, DwarfAccelTable::DataArray &Data)
         : Str(S), Data(Data) {
-      HashValue = dwarf::djbHash(S);
+      HashValue = djbHash(S);
     }
 
 #ifndef NDEBUG
     void print(raw_ostream &OS) {
       OS << "Name: " << Str << "\n";
       OS << "  Hash Value: " << format("0x%x", HashValue) << "\n";
       OS << "  Symbol: ";
       if (Sym)

llvm/trunk/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp

 //===- DWARFAcceleratorTable.cpp ------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h"
 
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/DebugInfo/DWARF/DWARFRelocMap.h"
 #include "llvm/Support/Compiler.h"
+#include "llvm/Support/DJB.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cstddef>
 #include <cstdint>
 #include <utility>
 
 using namespace llvm;
 

 }
 
 iterator_range<AppleAcceleratorTable::ValueIterator>
 AppleAcceleratorTable::equal_range(StringRef Key) const {
   if (!IsValid)
     return make_range(ValueIterator(), ValueIterator());
 
   // Find the bucket.
-  unsigned HashValue = dwarf::djbHash(Key);
+  unsigned HashValue = djbHash(Key);
   unsigned Bucket = HashValue % Hdr.NumBuckets;
   unsigned BucketBase = sizeof(Hdr) + Hdr.HeaderDataLength;
   unsigned HashesBase = BucketBase + Hdr.NumBuckets * 4;
   unsigned OffsetsBase = HashesBase + Hdr.NumHashes * 4;
 
   unsigned BucketOffset = BucketBase + Bucket * 4;
   unsigned Index = AccelSection.getU32(&BucketOffset);
 

llvm/trunk/lib/Support/CMakeLists.txt

add_llvm_library(LLVMSupport
   ConvertUTF.cpp
   ConvertUTFWrapper.cpp
   CrashRecoveryContext.cpp
   DataExtractor.cpp
   Debug.cpp
   DebugCounter.cpp
   DeltaAlgorithm.cpp
   DAGDeltaAlgorithm.cpp
+  DJB.cpp
   Error.cpp
   ErrorHandling.cpp
   FileUtilities.cpp
   FileOutputBuffer.cpp
   FoldingSet.cpp
   FormattedStream.cpp
   FormatVariadic.cpp
   GlobPattern.cpp

llvm/trunk/lib/Support/DJB.cpp

+//===-- Support/DJB.cpp ---DJB Hash -----------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains support for the DJ Bernstein hash function.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/DJB.h"
+
+uint32_t llvm::djbHash(StringRef Buffer, uint32_t H) {
+  for (char C : Buffer.bytes())
+    H = ((H << 5) + H) + C;
+  return H;
+}