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_NATIVE_HASHTABLE_H
     11 #define LLVM_DEBUGINFO_PDB_NATIVE_HASHTABLE_H
     12 
     13 #include "llvm/ADT/SparseBitVector.h"
     14 #include "llvm/ADT/iterator.h"
     15 #include "llvm/Support/Endian.h"
     16 #include "llvm/Support/Error.h"
     17 #include <cstdint>
     18 #include <iterator>
     19 #include <utility>
     20 #include <vector>
     21 
     22 namespace llvm {
     23 
     24 class BinaryStreamReader;
     25 class BinaryStreamWriter;
     26 
     27 namespace pdb {
     28 
     29 class HashTableIterator;
     30 
     31 class HashTable {
     32   friend class HashTableIterator;
     33 
     34   struct Header {
     35     support::ulittle32_t Size;
     36     support::ulittle32_t Capacity;
     37   };
     38 
     39   using BucketList = std::vector<std::pair<uint32_t, uint32_t>>;
     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 
     67   BucketList Buckets;
     68   mutable SparseBitVector<> Present;
     69   mutable SparseBitVector<> Deleted;
     70 
     71 private:
     72   static uint32_t maxLoad(uint32_t capacity);
     73   void grow();
     74 
     75   static Error readSparseBitVector(BinaryStreamReader &Stream,
     76                                    SparseBitVector<> &V);
     77   static Error writeSparseBitVector(BinaryStreamWriter &Writer,
     78                                     SparseBitVector<> &Vec);
     79 };
     80 
     81 class HashTableIterator
     82     : public iterator_facade_base<HashTableIterator, std::forward_iterator_tag,
     83                                   std::pair<uint32_t, uint32_t>> {
     84   friend class HashTable;
     85 
     86   HashTableIterator(const HashTable &Map, uint32_t Index, bool IsEnd);
     87 
     88 public:
     89   HashTableIterator(const HashTable &Map);
     90 
     91   HashTableIterator &operator=(const HashTableIterator &R);
     92   bool operator==(const HashTableIterator &R) const;
     93   const std::pair<uint32_t, uint32_t> &operator*() const;
     94   HashTableIterator &operator++();
     95 
     96 private:
     97   bool isEnd() const { return IsEnd; }
     98   uint32_t index() const { return Index; }
     99 
    100   const HashTable *Map;
    101   uint32_t Index;
    102   bool IsEnd;
    103 };
    104 
    105 } // end namespace pdb
    106 
    107 } // end namespace llvm
    108 
    109 #endif // LLVM_DEBUGINFO_PDB_NATIVE_HASHTABLE_H
    110