aboutsummaryrefslogtreecommitdiff
path: root/gps/utils/LocUnorderedSetMap.h
diff options
context:
space:
mode:
Diffstat (limited to 'gps/utils/LocUnorderedSetMap.h')
-rw-r--r--gps/utils/LocUnorderedSetMap.h201
1 files changed, 201 insertions, 0 deletions
diff --git a/gps/utils/LocUnorderedSetMap.h b/gps/utils/LocUnorderedSetMap.h
new file mode 100644
index 0000000..7b25ad0
--- /dev/null
+++ b/gps/utils/LocUnorderedSetMap.h
@@ -0,0 +1,201 @@
+/* Copyright (c) 2015, 2017, 2020 The Linux Foundation. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following
+ * disclaimer in the documentation and/or other materials provided
+ * with the distribution.
+ * * Neither the name of The Linux Foundation, nor the names of its
+ * contributors may be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
+ * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
+ * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
+ * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ */
+#ifndef __LOC_UNORDERDED_SETMAP_H__
+#define __LOC_UNORDERDED_SETMAP_H__
+
+#include <algorithm>
+#include <loc_pla.h>
+
+#ifdef NO_UNORDERED_SET_OR_MAP
+ #include <set>
+ #include <map>
+#else
+ #include <unordered_set>
+ #include <unordered_map>
+#endif
+
+using std::unordered_set;
+using std::unordered_map;
+
+namespace loc_util {
+
+// Trim from *fromSet* any elements that also exist in *rVals*.
+// The optional *goneVals*, if not null, will be populated with removed elements.
+template <typename T>
+inline static void trimSet(unordered_set<T>& fromSet, const unordered_set<T>& rVals,
+ unordered_set<T>* goneVals) {
+ for (auto val : rVals) {
+ if (fromSet.erase(val) > 0 && nullptr != goneVals) {
+ goneVals->insert(val);
+ }
+ }
+}
+
+// this method is destructive to the input unordered_sets.
+// the return set is the interset extracted out from the two input sets, *s1* and *s2*.
+// *s1* and *s2* will be left with the intersect removed from them.
+template <typename T>
+static unordered_set<T> removeAndReturnInterset(unordered_set<T>& s1, unordered_set<T>& s2) {
+ unordered_set<T> common = {};
+ for (auto b = s2.begin(); b != s2.end(); b++) {
+ auto a = find(s1.begin(), s1.end(), *b);
+ if (a != s1.end()) {
+ // this is a common item of both l1 and l2, remove from both
+ // but after we add to common
+ common.insert(*a);
+ s1.erase(a);
+ s2.erase(b);
+ }
+ }
+ return common;
+}
+
+template <typename KEY, typename VAL>
+class LocUnorderedSetMap {
+ unordered_map<KEY, unordered_set<VAL>> mMap;
+
+ // Trim the VALs pointed to by *iter*, with everything that also exist in *rVals*.
+ // If the set becomes empty, remove the map entry. *goneVals*, if not null, records
+ // the trimmed VALs.
+ bool trimOrRemove(typename unordered_map<KEY, unordered_set<VAL>>::iterator iter,
+ const unordered_set<VAL>& rVals, unordered_set<VAL>* goneVals) {
+ trimSet<VAL>(iter->second, rVals, goneVals);
+ bool removeEntry = (iter->second.empty());
+ if (removeEntry) {
+ mMap.erase(iter);
+ }
+ return removeEntry;
+ }
+
+public:
+ inline LocUnorderedSetMap() {}
+ inline LocUnorderedSetMap(size_t size) : LocUnorderedSetMap() {
+ mMap.get_allocator().allocate(size);
+ }
+
+ inline bool empty() { return mMap.empty(); }
+
+ // This gets the raw pointer to the VALs pointed to by *key*
+ // If the entry is not in the map, nullptr will be returned.
+ inline unordered_set<VAL>* getValSetPtr(const KEY& key) {
+ auto entry = mMap.find(key);
+ return (entry != mMap.end()) ? &(entry->second) : nullptr;
+ }
+
+ // This gets a copy of VALs pointed to by *key*
+ // If the entry is not in the map, an empty set will be returned.
+ inline unordered_set<VAL> getValSet(const KEY& key) {
+ auto entry = mMap.find(key);
+ return (entry != mMap.end()) ? entry->second : unordered_set<VAL>{};
+ }
+
+ // This gets all the KEYs from the map
+ inline unordered_set<KEY> getKeys() {
+ unordered_set<KEY> keys = {};
+ for (auto entry : mMap) {
+ keys.insert(entry.first);
+ }
+ return keys;
+ }
+
+ inline bool remove(const KEY& key) {
+ return mMap.erase(key) > 0;
+ }
+
+ // This looks into all the entries keyed by *keys*. Remove any VALs from the entries
+ // that also exist in *rVals*. If the entry is left with an empty set, the entry will
+ // be removed. The optional parameters *goneKeys* and *goneVals* will record the KEYs
+ // (or entries) and the collapsed VALs removed from the map, respectively.
+ inline void trimOrRemove(unordered_set<KEY>&& keys, const unordered_set<VAL>& rVals,
+ unordered_set<KEY>* goneKeys, unordered_set<VAL>* goneVals) {
+ trimOrRemove(keys, rVals, goneKeys, goneVals);
+ }
+
+ inline void trimOrRemove(unordered_set<KEY>& keys, const unordered_set<VAL>& rVals,
+ unordered_set<KEY>* goneKeys, unordered_set<VAL>* goneVals) {
+ for (auto key : keys) {
+ auto iter = mMap.find(key);
+ if (iter != mMap.end() && trimOrRemove(iter, rVals, goneVals) && nullptr != goneKeys) {
+ goneKeys->insert(iter->first);
+ }
+ }
+ }
+
+ // This adds all VALs from *newVals* to the map entry keyed by *key*. Or if it
+ // doesn't exist yet, add the set to the map.
+ bool add(const KEY& key, const unordered_set<VAL>& newVals) {
+ bool newEntryAdded = false;
+ if (!newVals.empty()) {
+ auto iter = mMap.find(key);
+ if (iter != mMap.end()) {
+ iter->second.insert(newVals.begin(), newVals.end());
+ } else {
+ mMap[key] = newVals;
+ newEntryAdded = true;
+ }
+ }
+ return newEntryAdded;
+ }
+
+ // This adds to each of entries in the map keyed by *keys* with the VALs in the
+ // *enwVals*. If there new entries added (new key in *keys*), *newKeys*, if not
+ // null, would be populated with those keys.
+ inline void add(const unordered_set<KEY>& keys, const unordered_set<VAL>&& newVals,
+ unordered_set<KEY>* newKeys) {
+ add(keys, newVals, newKeys);
+ }
+
+ inline void add(const unordered_set<KEY>& keys, const unordered_set<VAL>& newVals,
+ unordered_set<KEY>* newKeys) {
+ for (auto key : keys) {
+ if (add(key, newVals) && nullptr != newKeys) {
+ newKeys->insert(key);
+ }
+ }
+ }
+
+ // This puts *newVals* into the map keyed by *key*, and returns the VALs that are
+ // in effect removed from the keyed VAL set in the map entry.
+ // This call would also remove those same VALs from *newVals*.
+ inline unordered_set<VAL> update(const KEY& key, unordered_set<VAL>& newVals) {
+ unordered_set<VAL> goneVals = {};
+ if (newVals.empty()) {
+ mMap.erase(key);
+ } else {
+ auto curVals = mMap[key];
+ mMap[key] = newVals;
+ goneVals = removeAndReturnInterset(curVals, newVals);
+ }
+ return goneVals;
+ }
+};
+
+} // namespace loc_util
+
+#endif // #ifndef __LOC_UNORDERDED_SETMAP_H__