Home | History | Annotate | Download | only in Native 
      1 //===- HashTable.h - PDB Hash Table -----------------------------*- C++ -*-===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 
     10 #ifndef LLVM_DEBUGINFO_PDB_RAW_HASHTABLE_H
     11 #define LLVM_DEBUGINFO_PDB_RAW_HASHTABLE_H
     12 
     13 #include "llvm/ADT/ArrayRef.h"
     14 #include "llvm/ADT/SparseBitVector.h"
     15 #include "llvm/ADT/StringRef.h"
     16 #include "llvm/ADT/iterator.h"
     17 #include "llvm/Support/BinaryStreamArray.h"
     18 #include "llvm/Support/BinaryStreamReader.h"
     19 #include "llvm/Support/BinaryStreamWriter.h"
     20 #include "llvm/Support/Endian.h"
     21 #include "llvm/Support/Error.h"
     22 #include "llvm/Support/MathExtras.h"
     23 
     24 #include <cstdint>
     25 #include <utility>
     26 
     27 namespace llvm {
     28 namespace pdb {
     29 
     30 class HashTableIterator;
     31 
     32 class HashTable {
     33   friend class HashTableIterator;
     34   struct Header {
     35     support::ulittle32_t Size;
     36     support::ulittle32_t Capacity;
     37   };
     38 
     39   typedef std::vector<std::pair<uint32_t, uint32_t>> BucketList;
     40 
     41 public:
     42   HashTable();
     43   explicit HashTable(uint32_t Capacity);
     44 
     45   Error load(BinaryStreamReader &Stream);
     46 
     47   uint32_t calculateSerializedLength() const;
     48   Error commit(BinaryStreamWriter &Writer) const;
     49 
     50   void clear();
     51 
     52   uint32_t capacity() const;
     53   uint32_t size() const;
     54 
     55   HashTableIterator begin() const;
     56   HashTableIterator end() const;
     57   HashTableIterator find(uint32_t K);
     58 
     59   void set(uint32_t K, uint32_t V);
     60   void remove(uint32_t K);
     61   uint32_t get(uint32_t K);
     62 
     63 protected:
     64   bool isPresent(uint32_t K) const { return Present.test(K); }
     65   bool isDeleted(uint32_t K) const { return Deleted.test(K); }
     66   BucketList Buckets;
     67   mutable SparseBitVector<> Present;
     68   mutable SparseBitVector<> Deleted;
     69 
     70 private:
     71   static uint32_t maxLoad(uint32_t capacity);
     72   void grow();
     73 
     74   static Error readSparseBitVector(BinaryStreamReader &Stream,
     75                                    SparseBitVector<> &V);
     76   static Error writeSparseBitVector(BinaryStreamWriter &Writer,
     77                                     SparseBitVector<> &Vec);
     78 };
     79 
     80 class HashTableIterator
     81     : public iterator_facade_base<HashTableIterator, std::forward_iterator_tag,
     82                                   std::pair<uint32_t, uint32_t>> {
     83   friend class HashTable;
     84   HashTableIterator(const HashTable &Map, uint32_t Index, bool IsEnd);
     85 
     86 public:
     87   HashTableIterator(const HashTable &Map);
     88 
     89   HashTableIterator &operator=(const HashTableIterator &R);
     90   bool operator==(const HashTableIterator &R) const;
     91   const std::pair<uint32_t, uint32_t> &operator*() const;
     92   HashTableIterator &operator++();
     93 
     94 private:
     95   bool isEnd() const { return IsEnd; }
     96   uint32_t index() const { return Index; }
     97 
     98   const HashTable *Map;
     99   uint32_t Index;
    100   bool IsEnd;
    101 };
    102 
    103 } // end namespace pdb
    104 } // end namespace llvm
    105 
    106 #endif // LLVM_DEBUGINFO_PDB_RAW_HASHTABLE_H
    107