1/*
2 * Copyright (C) 2015-2017 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#pragma once
27
28#include <wtf/BitVector.h>
29#include <wtf/CommaPrinter.h>
30#include <wtf/IndexKeyType.h>
31
32namespace WTF {
33
34// This is a set for things that have an index(). It's super efficient for BasicBlocks. It's only
35// efficient for Values if you don't create too many of these sets, since Values can have very sparse
36// indices and there are a lot of Values.
37
38// If you want a set of BasicBlocks, you do IndexSet<BasicBlock>. So, T = BasicBlock.
39template<typename T>
40class IndexSet {
41public:
42 IndexSet()
43 {
44 }
45
46 bool add(const T& value)
47 {
48 return !m_set.set(IndexKeyType<T>::index(value));
49 }
50
51 template<typename Iterable>
52 bool addAll(const Iterable& iterable)
53 {
54 bool result = false;
55 for (const T& value : iterable)
56 result |= add(value);
57 return result;
58 }
59
60 bool remove(const T& value)
61 {
62 return m_set.clear(IndexKeyType<T>::index(value));
63 }
64
65 bool contains(const T& value) const
66 {
67 if (!value)
68 return false;
69 return m_set.get(IndexKeyType<T>::index(value));
70 }
71
72 size_t size() const
73 {
74 return m_set.bitCount();
75 }
76
77 bool isEmpty() const
78 {
79 return m_set.isEmpty();
80 }
81
82 template<typename CollectionType>
83 class Iterable {
84 public:
85 Iterable(const CollectionType& collection, const BitVector& set)
86 : m_collection(collection)
87 , m_set(set)
88 {
89 }
90
91 class iterator {
92 public:
93 iterator()
94 : m_collection(nullptr)
95 {
96 }
97
98 iterator(const CollectionType& collection, BitVector::iterator iter)
99 : m_collection(&collection)
100 , m_iter(iter)
101 {
102 }
103
104 T operator*()
105 {
106 return m_collection->at(*m_iter);
107 }
108
109 iterator& operator++()
110 {
111 ++m_iter;
112 return *this;
113 }
114
115 bool operator==(const iterator& other) const
116 {
117 return m_iter == other.m_iter;
118 }
119
120 bool operator!=(const iterator& other) const
121 {
122 return !(*this == other);
123 }
124
125 private:
126 const CollectionType* m_collection;
127 BitVector::iterator m_iter;
128 };
129
130 iterator begin() const { return iterator(m_collection, m_set.begin()); }
131 iterator end() const { return iterator(m_collection, m_set.end()); }
132
133 private:
134 const CollectionType& m_collection;
135 const BitVector& m_set;
136 };
137
138 // For basic blocks, you do:
139 // indexSet.values(procedure);
140 //
141 // For values, you do:
142 // indexSet.values(procedure.values());
143 template<typename CollectionType>
144 Iterable<CollectionType> values(const CollectionType& collection) const
145 {
146 return Iterable<CollectionType>(collection, indices());
147 }
148
149 const BitVector& indices() const { return m_set; }
150
151 void dump(PrintStream& out) const
152 {
153 CommaPrinter comma;
154 for (size_t index : indices())
155 out.print(comma, T::dumpPrefix, index);
156 }
157
158private:
159 BitVector m_set;
160};
161
162} // namespace WTF
163
164using WTF::IndexSet;
165