1 /* Copyright (c) 2015, 2017 The Linux Foundation. All rights reserved.
2 *
3 * Redistribution and use in source and binary forms, with or without
4 * modification, are permitted provided that the following conditions are
5 * met:
6 * * Redistributions of source code must retain the above copyright
7 * notice, this list of conditions and the following disclaimer.
8 * * Redistributions in binary form must reproduce the above
9 * copyright notice, this list of conditions and the following
10 * disclaimer in the documentation and/or other materials provided
11 * with the distribution.
12 * * Neither the name of The Linux Foundation, nor the names of its
13 * contributors may be used to endorse or promote products derived
14 * from this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED
17 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
18 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
20 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
23 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
24 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
25 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
26 * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 *
28 */
29 #ifndef __LOC_UNORDERDED_SETMAP_H__
30 #define __LOC_UNORDERDED_SETMAP_H__
31
32 #include <algorithm>
33 #include <unordered_set>
34 #include <unordered_map>
35
36 using std::unordered_set;
37 using std::unordered_map;
38
39 namespace loc_util {
40
41 // Trim from *fromSet* any elements that also exist in *rVals*.
42 // The optional *goneVals*, if not null, will be populated with removed elements.
43 template <typename T>
trimSet(unordered_set<T> & fromSet,const unordered_set<T> & rVals,unordered_set<T> * goneVals)44 inline static void trimSet(unordered_set<T>& fromSet, const unordered_set<T>& rVals,
45 unordered_set<T>* goneVals) {
46 for (auto val : rVals) {
47 if (fromSet.erase(val) > 0 && nullptr != goneVals) {
48 goneVals->insert(val);
49 }
50 }
51 }
52
53 // this method is destructive to the input unordered_sets.
54 // the return set is the interset extracted out from the two input sets, *s1* and *s2*.
55 // *s1* and *s2* will be left with the intersect removed from them.
56 template <typename T>
removeAndReturnInterset(unordered_set<T> & s1,unordered_set<T> & s2)57 static unordered_set<T> removeAndReturnInterset(unordered_set<T>& s1, unordered_set<T>& s2) {
58 unordered_set<T> common(0);
59 for (auto b = s2.begin(); b != s2.end(); b++) {
60 auto a = find(s1.begin(), s1.end(), *b);
61 if (a != s1.end()) {
62 // this is a common item of both l1 and l2, remove from both
63 // but after we add to common
64 common.insert(*a);
65 s1.erase(a);
66 s2.erase(b);
67 }
68 }
69 return common;
70 }
71
72 template <typename KEY, typename VAL>
73 class LocUnorderedSetMap {
74 unordered_map<KEY, unordered_set<VAL>> mMap;
75
76
77 // Trim the VALs pointed to by *iter*, with everything that also exist in *rVals*.
78 // If the set becomes empty, remove the map entry. *goneVals*, if not null, records
79 // the trimmed VALs.
trimOrRemove(typename unordered_map<KEY,unordered_set<VAL>>::iterator iter,const unordered_set<VAL> & rVals,unordered_set<VAL> * goneVals)80 bool trimOrRemove(typename unordered_map<KEY, unordered_set<VAL>>::iterator iter,
81 const unordered_set<VAL>& rVals, unordered_set<VAL>* goneVals) {
82 trimSet<VAL>(iter->second, rVals, goneVals);
83 bool removeEntry = (iter->second.empty());
84 if (removeEntry) {
85 mMap.erase(iter);
86 }
87 return removeEntry;
88 }
89
90 public:
LocUnorderedSetMap()91 inline LocUnorderedSetMap() {}
LocUnorderedSetMap(size_t size)92 inline LocUnorderedSetMap(size_t size) : mMap(size) {}
93
empty()94 inline bool empty() { return mMap.empty(); }
95
96 // This gets the raw pointer to the VALs pointed to by *key*
97 // If the entry is not in the map, nullptr will be returned.
getValSetPtr(const KEY & key)98 inline unordered_set<VAL>* getValSetPtr(const KEY& key) {
99 auto entry = mMap.find(key);
100 return (entry != mMap.end()) ? &(entry->second) : nullptr;
101 }
102
103 // This gets a copy of VALs pointed to by *key*
104 // If the entry is not in the map, an empty set will be returned.
getValSet(const KEY & key)105 inline unordered_set<VAL> getValSet(const KEY& key) {
106 auto entry = mMap.find(key);
107 return (entry != mMap.end()) ? entry->second : unordered_set<VAL>(0);
108 }
109
110 // This gets all the KEYs from the map
getKeys()111 inline unordered_set<KEY> getKeys() {
112 unordered_set<KEY> keys(0);
113 for (auto entry : mMap) {
114 keys.insert(entry.first);
115 }
116 return keys;
117 }
118
remove(const KEY & key)119 inline bool remove(const KEY& key) {
120 return mMap.erase(key) > 0;
121 }
122
123 // This looks into all the entries keyed by *keys*. Remove any VALs from the entries
124 // that also exist in *rVals*. If the entry is left with an empty set, the entry will
125 // be removed. The optional parameters *goneKeys* and *goneVals* will record the KEYs
126 // (or entries) and the collapsed VALs removed from the map, respectively.
trimOrRemove(unordered_set<KEY> && keys,const unordered_set<VAL> & rVals,unordered_set<KEY> * goneKeys,unordered_set<VAL> * goneVals)127 inline void trimOrRemove(unordered_set<KEY>&& keys, const unordered_set<VAL>& rVals,
128 unordered_set<KEY>* goneKeys, unordered_set<VAL>* goneVals) {
129 trimOrRemove(keys, rVals, goneKeys, goneVals);
130 }
trimOrRemove(unordered_set<KEY> & keys,const unordered_set<VAL> & rVals,unordered_set<KEY> * goneKeys,unordered_set<VAL> * goneVals)131 inline void trimOrRemove(unordered_set<KEY>& keys, const unordered_set<VAL>& rVals,
132 unordered_set<KEY>* goneKeys, unordered_set<VAL>* goneVals) {
133 for (auto key : keys) {
134 auto iter = mMap.find(key);
135 if (iter != mMap.end() && trimOrRemove(iter, rVals, goneVals) && nullptr != goneKeys) {
136 goneKeys->insert(iter->first);
137 }
138 }
139 }
140
141 // This adds all VALs from *newVals* to the map entry keyed by *key*. Or if it
142 // doesn't exist yet, add the set to the map.
add(const KEY & key,const unordered_set<VAL> & newVals)143 bool add(const KEY& key, const unordered_set<VAL>& newVals) {
144 bool newEntryAdded = false;
145 if (!newVals.empty()) {
146 auto iter = mMap.find(key);
147 if (iter != mMap.end()) {
148 iter->second.insert(newVals.begin(), newVals.end());
149 } else {
150 mMap[key] = newVals;
151 newEntryAdded = true;
152 }
153 }
154 return newEntryAdded;
155 }
156
157 // This adds to each of entries in the map keyed by *keys* with the VALs in the
158 // *enwVals*. If there new entries added (new key in *keys*), *newKeys*, if not
159 // null, would be populated with those keys.
add(const unordered_set<KEY> & keys,const unordered_set<VAL> && newVals,unordered_set<KEY> * newKeys)160 inline void add(const unordered_set<KEY>& keys, const unordered_set<VAL>&& newVals,
161 unordered_set<KEY>* newKeys) {
162 add(keys, newVals, newKeys);
163 }
add(const unordered_set<KEY> & keys,const unordered_set<VAL> & newVals,unordered_set<KEY> * newKeys)164 inline void add(const unordered_set<KEY>& keys, const unordered_set<VAL>& newVals,
165 unordered_set<KEY>* newKeys) {
166 for (auto key : keys) {
167 if (add(key, newVals) && nullptr != newKeys) {
168 newKeys->insert(key);
169 }
170 }
171 }
172
173 // This puts *newVals* into the map keyed by *key*, and returns the VALs that are
174 // in effect removed from the keyed VAL set in the map entry.
175 // This call would also remove those same VALs from *newVals*.
update(const KEY & key,unordered_set<VAL> & newVals)176 inline unordered_set<VAL> update(const KEY& key, unordered_set<VAL>& newVals) {
177 unordered_set<VAL> goneVals(0);
178
179 if (newVals.empty()) {
180 mMap.erase(key);
181 } else {
182 auto curVals = mMap[key];
183 mMap[key] = newVals;
184 goneVals = removeAndReturnInterset(curVals, newVals);
185 }
186 return goneVals;
187 }
188 };
189
190 } // namespace loc_util
191
192 #endif // #ifndef __LOC_UNORDERDED_SETMAP_H__
193