OmniSciDB  2e3a973ef4
InsertionOrderedMap.h
Go to the documentation of this file.
1 /*
2  * Copyright 2020 OmniSci, Inc.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 // InsertionOrderedMap: A hash map that remembers the insertion order for its values.
18 
19 // Simply a std::unordered_map plus a std::vector plus some helper functions to keep the
20 // two data structures in sync. This is one of the recommended approaches on Stack
21 // Overflow.
22 
23 // The class was thrown together quickly for a narrow purpose so is probably lacking some
24 // obvious features for general-purpose use.
25 
26 // An alternative to the unordered_map+vector design might be Boost's multi_index
27 // container, although we only want one index (the insertion ordering) so do we even need
28 // "multi"?
29 
30 #pragma once
31 
32 #include <unordered_map>
33 #include <vector>
34 
36  std::unordered_map<llvm::Value*, llvm::Value*> m_;
37  std::vector<llvm::Value*> v_;
38 
39  auto& operator[](llvm::Value* key) {
40  auto m_it = m_.find(key);
41  if (m_it == m_.end()) {
42  v_.push_back(key);
43  return m_[key];
44  }
45  return m_it->second;
46  }
47 
48  void replace(llvm::Value* key1, llvm::Value* key2) {
49  if (m_.count(key2)) {
50  return;
51  }
52  auto m_it = m_.find(key1);
53  if (m_it == m_.end()) {
54  return;
55  }
56  auto v_it = std::find(v_.begin(), v_.end(), key1);
57  if (v_it == v_.end()) {
58  return;
59  }
60  *v_it = key2;
61  m_[key2] = m_it->second;
62  m_.erase(m_it);
63  }
64 
65  struct Iterator {
67  std::vector<llvm::Value*>::iterator v_it_;
68 
69  Iterator(InsertionOrderedMap* that, std::vector<llvm::Value*>::iterator v_it)
70  : that_(that), v_it_(v_it) {}
71  auto& operator++() { return ++v_it_; }
72  auto operator++(int) { return v_it_++; }
73  auto& operator*() {
74  CHECK(that_);
75  CHECK(v_it_ != that_->v_.end());
76  CHECK(that_->m_.find(*v_it_) != that_->m_.end());
77  return *(that_->m_.find(*v_it_));
78  }
79  auto operator-> () {
80  CHECK(that_);
81  CHECK(v_it_ != that_->v_.end());
82  CHECK(that_->m_.find(*v_it_) != that_->m_.end());
83  return &*(that_->m_.find(*v_it_));
84  }
85  bool operator==(const Iterator& peer) { return (v_it_ == peer.v_it_); }
86  bool operator!=(const Iterator& peer) { return (v_it_ != peer.v_it_); }
87  };
88 
89  auto begin() { return Iterator{this, v_.begin()}; }
90  auto end() { return Iterator{this, v_.end()}; }
91 
92  auto find(llvm::Value* key) {
93  if (m_.count(key)) {
94  return Iterator{this, std::find(v_.begin(), v_.end(), key)};
95  } else {
96  return Iterator{this, v_.end()};
97  }
98  }
99 
100  std::pair<Iterator, bool> emplace(llvm::Value* key, llvm::Value* val) {
101  auto it = find(key);
102  if (it != end()) {
103  return std::pair(it, false);
104  } else {
105  m_.emplace(key, val);
106  v_.push_back(key);
107  return std::pair(Iterator{this, v_.end() - 1}, true);
108  }
109  }
110 }; // struct InsertionOrderedMap
std::pair< Iterator, bool > emplace(llvm::Value *key, llvm::Value *val)
bool operator!=(const Iterator &peer)
bool operator==(const Iterator &peer)
std::vector< llvm::Value * >::iterator v_it_
std::vector< llvm::Value * > v_
void replace(llvm::Value *key1, llvm::Value *key2)
auto & operator[](llvm::Value *key)
auto find(llvm::Value *key)
Iterator(InsertionOrderedMap *that, std::vector< llvm::Value *>::iterator v_it)
#define CHECK(condition)
Definition: Logger.h:197
std::unordered_map< llvm::Value *, llvm::Value * > m_