-
Notifications
You must be signed in to change notification settings - Fork 10.3k
/
BlotMapVector.h
144 lines (120 loc) · 4.74 KB
/
BlotMapVector.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
//===- BlotMapVector.h - Map vector with "blot" operation ------*- C++ -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
#ifndef SWIFT_BASIC_BLOTMAPVECTOR_H
#define SWIFT_BASIC_BLOTMAPVECTOR_H
#include "llvm/ADT/DenseMap.h"
#include "swift/Basic/LLVM.h"
#include "swift/Basic/Range.h"
#include <vector>
namespace swift {
template <typename KeyT, typename ValueT>
bool compareKeyAgainstDefaultKey(const std::pair<KeyT, ValueT> &Pair) {
return Pair.first == KeyT();
}
/// \brief An associative container with fast insertion-order (deterministic)
/// iteration over its elements. Plus the special blot operation.
template <typename KeyT, typename ValueT,
typename MapTy = llvm::DenseMap<KeyT, size_t>,
typename VectorTy = std::vector<Optional<std::pair<KeyT, ValueT>>>>
class BlotMapVector {
/// Map keys to indices in Vector.
MapTy Map;
/// Keys and values.
VectorTy Vector;
public:
using iterator = typename VectorTy::iterator;
using const_iterator = typename VectorTy::const_iterator;
using key_type = KeyT;
using mapped_type = ValueT;
iterator begin() { return Vector.begin(); }
iterator end() { return Vector.end(); }
const_iterator begin() const { return Vector.begin(); }
const_iterator end() const { return Vector.end(); }
iterator_range<iterator> getItems() {
return swift::make_range(begin(), end());
}
ValueT &operator[](const KeyT &Arg) {
auto Pair = Map.insert(std::make_pair(Arg, size_t(0)));
if (Pair.second) {
size_t Num = Vector.size();
Pair.first->second = Num;
Vector.push_back({std::make_pair(Arg, ValueT())});
return (*Vector[Num]).second;
}
return Vector[Pair.first->second].getValue().second;
}
std::pair<iterator, bool>
insert(const std::pair<KeyT, ValueT> &InsertPair) {
auto Pair = Map.insert(std::make_pair(InsertPair.first, size_t(0)));
if (Pair.second) {
size_t Num = Vector.size();
Pair.first->second = Num;
Vector.push_back(InsertPair);
return std::make_pair(Vector.begin() + Num, true);
}
return std::make_pair(Vector.begin() + Pair.first->second, false);
}
iterator find(const KeyT &Key) {
typename MapTy::iterator It = Map.find(Key);
if (It == Map.end()) return Vector.end();
auto Iter = Vector.begin() + It->second;
if (!Iter->hasValue())
return Vector.end();
return Iter;
}
const_iterator find(const KeyT &Key) const {
return const_cast<BlotMapVector &>(*this)->find(Key);
}
/// This is similar to erase, but instead of removing the element from the
/// vector, it just zeros out the key in the vector. This leaves iterators
/// intact, but clients must be prepared for zeroed-out keys when iterating.
void erase(const KeyT &Key) { blot(Key); }
/// This is similar to erase, but instead of removing the element from the
/// vector, it just zeros out the key in the vector. This leaves iterators
/// intact, but clients must be prepared for zeroed-out keys when iterating.
void erase(iterator I) { erase((*I)->first); }
/// This is similar to erase, but instead of removing the element from the
/// vector, it just zeros out the key in the vector. This leaves iterators
/// intact, but clients must be prepared for zeroed-out keys when iterating.
void blot(const KeyT &Key) {
typename MapTy::iterator It = Map.find(Key);
if (It == Map.end()) return;
Vector[It->second] = None;
Map.erase(It);
}
void clear() {
Map.clear();
Vector.clear();
}
unsigned size() const { return Map.size(); }
ValueT lookup(const KeyT &Val) const {
auto Iter = Map.find(Val);
if (Iter == Map.end())
return ValueT();
auto &P = Vector[Iter->second];
if (!P.hasValue())
return ValueT();
return P->second;
}
size_t count(const KeyT &Val) const { return Map.count(Val); }
bool empty() const { return Map.empty(); }
};
template <typename KeyT, typename ValueT, unsigned N,
typename MapT = llvm::SmallDenseMap<KeyT, size_t, N>,
typename VectorT =
llvm::SmallVector<Optional<std::pair<KeyT, ValueT>>, N>>
class SmallBlotMapVector : public BlotMapVector<KeyT, ValueT, MapT, VectorT> {
public:
SmallBlotMapVector() {}
};
} // end namespace swift
#endif