1 /* Copyright (c) 2015, 2017, 2020 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 <loc_pla.h>
34 
35 #ifdef NO_UNORDERED_SET_OR_MAP
36     #include <set>
37     #include <map>
38 #else
39     #include <unordered_set>
40     #include <unordered_map>
41 #endif
42 
43 using std::unordered_set;
44 using std::unordered_map;
45 
46 namespace loc_util {
47 
48 // Trim from *fromSet* any elements that also exist in *rVals*.
49 // The optional *goneVals*, if not null, will be populated with removed elements.
50 template <typename T>
trimSet(unordered_set<T> & fromSet,const unordered_set<T> & rVals,unordered_set<T> * goneVals)51 inline static void trimSet(unordered_set<T>& fromSet, const unordered_set<T>& rVals,
52                            unordered_set<T>* goneVals) {
53     for (auto val : rVals) {
54         if (fromSet.erase(val) > 0 && nullptr != goneVals) {
55             goneVals->insert(val);
56         }
57     }
58 }
59 
60 // this method is destructive to the input unordered_sets.
61 // the return set is the interset extracted out from the two input sets, *s1* and *s2*.
62 // *s1* and *s2* will be left with the intersect removed from them.
63 template <typename T>
removeAndReturnInterset(unordered_set<T> & s1,unordered_set<T> & s2)64 static unordered_set<T> removeAndReturnInterset(unordered_set<T>& s1, unordered_set<T>& s2) {
65     unordered_set<T> common = {};
66     for (auto b = s2.begin(); b != s2.end(); b++) {
67         auto a = find(s1.begin(), s1.end(), *b);
68         if (a != s1.end()) {
69             // this is a common item of both l1 and l2, remove from both
70             // but after we add to common
71             common.insert(*a);
72             s1.erase(a);
73             s2.erase(b);
74         }
75     }
76     return common;
77 }
78 
79 template <typename KEY, typename VAL>
80 class LocUnorderedSetMap {
81     unordered_map<KEY, unordered_set<VAL>> mMap;
82 
83     // Trim the VALs pointed to by *iter*, with everything that also exist in *rVals*.
84     // If the set becomes empty, remove the map entry. *goneVals*, if not null, records
85     // the trimmed VALs.
trimOrRemove(typename unordered_map<KEY,unordered_set<VAL>>::iterator iter,const unordered_set<VAL> & rVals,unordered_set<VAL> * goneVals)86     bool trimOrRemove(typename unordered_map<KEY, unordered_set<VAL>>::iterator iter,
87                       const unordered_set<VAL>& rVals, unordered_set<VAL>* goneVals) {
88         trimSet<VAL>(iter->second, rVals, goneVals);
89         bool removeEntry = (iter->second.empty());
90         if (removeEntry) {
91             mMap.erase(iter);
92         }
93         return removeEntry;
94     }
95 
96 public:
LocUnorderedSetMap()97     inline LocUnorderedSetMap() {}
LocUnorderedSetMap(size_t size)98     inline LocUnorderedSetMap(size_t size) : LocUnorderedSetMap() {
99         mMap.get_allocator().allocate(size);
100     }
101 
empty()102     inline bool empty() { return mMap.empty(); }
103 
104     // This gets the raw pointer to the VALs pointed to by *key*
105     // If the entry is not in the map, nullptr will be returned.
getValSetPtr(const KEY & key)106     inline unordered_set<VAL>* getValSetPtr(const KEY& key) {
107         auto entry = mMap.find(key);
108         return (entry != mMap.end()) ? &(entry->second) : nullptr;
109     }
110 
111     //  This gets a copy of VALs pointed to by *key*
112     // If the entry is not in the map, an empty set will be returned.
getValSet(const KEY & key)113     inline unordered_set<VAL> getValSet(const KEY& key) {
114         auto entry = mMap.find(key);
115         return (entry != mMap.end()) ? entry->second : unordered_set<VAL>{};
116     }
117 
118     // This gets all the KEYs from the map
getKeys()119     inline unordered_set<KEY> getKeys() {
120         unordered_set<KEY> keys = {};
121         for (auto entry : mMap) {
122             keys.insert(entry.first);
123         }
124         return keys;
125     }
126 
remove(const KEY & key)127     inline bool remove(const KEY& key) {
128         return mMap.erase(key) > 0;
129     }
130 
131     // This looks into all the entries keyed by *keys*. Remove any VALs from the entries
132     // that also exist in *rVals*. If the entry is left with an empty set, the entry will
133     // be removed. The optional parameters *goneKeys* and *goneVals* will record the KEYs
134     // (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)135     inline void trimOrRemove(unordered_set<KEY>&& keys, const unordered_set<VAL>& rVals,
136                              unordered_set<KEY>* goneKeys, unordered_set<VAL>* goneVals) {
137         trimOrRemove(keys, rVals, goneKeys, goneVals);
138     }
139 
trimOrRemove(unordered_set<KEY> & keys,const unordered_set<VAL> & rVals,unordered_set<KEY> * goneKeys,unordered_set<VAL> * goneVals)140     inline void trimOrRemove(unordered_set<KEY>& keys, const unordered_set<VAL>& rVals,
141                              unordered_set<KEY>* goneKeys, unordered_set<VAL>* goneVals) {
142         for (auto key : keys) {
143             auto iter = mMap.find(key);
144             if (iter != mMap.end() && trimOrRemove(iter, rVals, goneVals) && nullptr != goneKeys) {
145                 goneKeys->insert(iter->first);
146             }
147         }
148     }
149 
150     // This adds all VALs from *newVals* to the map entry keyed by *key*. Or if it
151     // doesn't exist yet, add the set to the map.
add(const KEY & key,const unordered_set<VAL> & newVals)152     bool add(const KEY& key, const unordered_set<VAL>& newVals) {
153         bool newEntryAdded = false;
154         if (!newVals.empty()) {
155             auto iter = mMap.find(key);
156             if (iter != mMap.end()) {
157                 iter->second.insert(newVals.begin(), newVals.end());
158             } else {
159                 mMap[key] = newVals;
160                 newEntryAdded = true;
161             }
162         }
163         return newEntryAdded;
164     }
165 
166     // This adds to each of entries in the map keyed by *keys* with the VALs in the
167     // *enwVals*. If there new entries added (new key in *keys*), *newKeys*, if not
168     // null, would be populated with those keys.
add(const unordered_set<KEY> & keys,const unordered_set<VAL> && newVals,unordered_set<KEY> * newKeys)169     inline void add(const unordered_set<KEY>& keys, const unordered_set<VAL>&& newVals,
170                     unordered_set<KEY>* newKeys) {
171         add(keys, newVals, newKeys);
172     }
173 
add(const unordered_set<KEY> & keys,const unordered_set<VAL> & newVals,unordered_set<KEY> * newKeys)174     inline void add(const unordered_set<KEY>& keys, const unordered_set<VAL>& newVals,
175                     unordered_set<KEY>* newKeys) {
176         for (auto key : keys) {
177             if (add(key, newVals) && nullptr != newKeys) {
178                 newKeys->insert(key);
179             }
180         }
181     }
182 
183     // This puts *newVals* into the map keyed by *key*, and returns the VALs that are
184     // in effect removed from the keyed VAL set in the map entry.
185     // This call would also remove those same VALs from *newVals*.
update(const KEY & key,unordered_set<VAL> & newVals)186     inline unordered_set<VAL> update(const KEY& key, unordered_set<VAL>& newVals) {
187         unordered_set<VAL> goneVals = {};
188         if (newVals.empty()) {
189             mMap.erase(key);
190         } else {
191             auto curVals = mMap[key];
192             mMap[key] = newVals;
193             goneVals = removeAndReturnInterset(curVals, newVals);
194         }
195         return goneVals;
196     }
197 };
198 
199 } // namespace loc_util
200 
201 #endif // #ifndef __LOC_UNORDERDED_SETMAP_H__
202