1 // *****************************************************************************
2 // * This file is part of the FreeFileSync project. It is distributed under    *
3 // * GNU General Public License: http://www.gnu.org/licenses/gpl-3.0           *
4 // * Copyright (C) Zenju (zenju AT freefilesync DOT org) - All Rights Reserved *
5 // *****************************************************************************
6 
7 #ifndef STL_TOOLS_H_84567184321434
8 #define STL_TOOLS_H_84567184321434
9 
10 #include <set>
11 #include <map>
12 #include <vector>
13 #include <memory>
14 #include <algorithm>
15 #include "type_tools.h"
16 #include "build_info.h"
17 
18 
19 //enhancements for <algorithm>
20 namespace zen
21 {
22 //erase selected elements from any container:
23 template <class T, class Alloc, class Predicate>
24 void erase_if(std::vector<T, Alloc>& v, Predicate p);
25 
26 template <class T, class LessType, class Alloc, class Predicate>
27 void erase_if(std::set<T, LessType, Alloc>& s, Predicate p);
28 
29 template <class KeyType, class ValueType, class LessType, class Alloc, class Predicate>
30 void erase_if(std::map<KeyType, ValueType, LessType, Alloc>& m, Predicate p);
31 
32 //append STL containers
33 template <class T, class Alloc, class C>
34 void append(std::vector<T, Alloc>& v, const C& c);
35 
36 template <class T, class LessType, class Alloc, class C>
37 void append(std::set<T, LessType, Alloc>& s, const C& c);
38 
39 template <class KeyType, class ValueType, class LessType, class Alloc, class C>
40 void append(std::map<KeyType, ValueType, LessType, Alloc>& m, const C& c);
41 
42 template <class M, class K, class V>
43 V& map_add_or_update(M& map, const K& key, const V& value); //efficient add or update without "default-constructible" requirement (Effective STL, item 24)
44 
45 template <class T, class Alloc>
46 void removeDuplicates(std::vector<T, Alloc>& v);
47 
48 //binary search returning an iterator
49 template <class ForwardIterator, class T, typename CompLess>
50 ForwardIterator binary_search(ForwardIterator first, ForwardIterator last, const T& value, CompLess less);
51 
52 template <class BidirectionalIterator, class T>
53 BidirectionalIterator find_last(BidirectionalIterator first, BidirectionalIterator last, const T& value);
54 
55 //replacement for std::find_end taking advantage of bidirectional iterators (and giving the algorithm a reasonable name)
56 template <class BidirectionalIterator1, class BidirectionalIterator2>
57 BidirectionalIterator1 search_last(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
58                                    BidirectionalIterator2 first2, BidirectionalIterator2 last2);
59 
60 template <class InputIterator1, class InputIterator2>
61 bool equal(InputIterator1 first1, InputIterator1 last1,
62            InputIterator2 first2, InputIterator2 last2);
63 
64 template <class ByteIterator> size_t hashBytes                      (ByteIterator first, ByteIterator last);
65 template <class ByteIterator> size_t hashBytesAppend(size_t hashVal, ByteIterator first, ByteIterator last);
66 
67 
68 //support for custom string classes in std::unordered_set/map
69 struct StringHash
70 {
71     template <class String>
operatorStringHash72     size_t operator()(const String& str) const
73     {
74         const auto* strFirst = strBegin(str);
75         return hashBytes(reinterpret_cast<const char*>(strFirst),
76                          reinterpret_cast<const char*>(strFirst + strLength(str)));
77     }
78 };
79 
80 
81 
82 
83 
84 
85 //######################## implementation ########################
86 
87 template <class T, class Alloc, class Predicate> inline
erase_if(std::vector<T,Alloc> & v,Predicate p)88 void erase_if(std::vector<T, Alloc>& v, Predicate p)
89 {
90     v.erase(std::remove_if(v.begin(), v.end(), p), v.end());
91 }
92 
93 
94 namespace impl
95 {
96 template <class S, class Predicate> inline
set_or_map_erase_if(S & s,Predicate p)97 void set_or_map_erase_if(S& s, Predicate p)
98 {
99     for (auto it = s.begin(); it != s.end();)
100         if (p(*it))
101             s.erase(it++);
102         else
103             ++it;
104 }
105 }
106 
107 
108 template <class T, class LessType, class Alloc, class Predicate> inline
erase_if(std::set<T,LessType,Alloc> & s,Predicate p)109 void erase_if(std::set<T, LessType, Alloc>& s, Predicate p) { impl::set_or_map_erase_if(s, p); } //don't make this any more generic! e.g. must not compile for std::vector!!!
110 
111 
112 template <class KeyType, class ValueType, class LessType, class Alloc, class Predicate> inline
erase_if(std::map<KeyType,ValueType,LessType,Alloc> & m,Predicate p)113 void erase_if(std::map<KeyType, ValueType, LessType, Alloc>& m, Predicate p) { impl::set_or_map_erase_if(m, p); }
114 
115 
116 template <class T, class Alloc, class C> inline
append(std::vector<T,Alloc> & v,const C & c)117 void append(std::vector<T, Alloc>& v, const C& c) { v.insert(v.end(), c.begin(), c.end()); }
118 
119 
120 template <class T, class LessType, class Alloc, class C> inline
append(std::set<T,LessType,Alloc> & s,const C & c)121 void append(std::set<T, LessType, Alloc>& s, const C& c) { s.insert(c.begin(), c.end()); }
122 
123 
124 template <class KeyType, class ValueType, class LessType, class Alloc, class C> inline
append(std::map<KeyType,ValueType,LessType,Alloc> & m,const C & c)125 void append(std::map<KeyType, ValueType, LessType, Alloc>& m, const C& c) { m.insert(c.begin(), c.end()); }
126 
127 
128 template <class M, class K, class V> inline
map_add_or_update(M & map,const K & key,const V & value)129 V& map_add_or_update(M& map, const K& key, const V& value) //efficient add or update without "default-constructible" requirement (Effective STL, item 24)
130 {
131     auto it = map.lower_bound(key);
132     if (it != map.end() && !(map.key_comp()(key, it->first)))
133     {
134         it->second = value;
135         return it->second;
136     }
137     else
138         return map.insert(it, typename M::value_type(key, value))->second;
139 }
140 
141 
142 template <class T, class Alloc> inline
removeDuplicates(std::vector<T,Alloc> & v)143 void removeDuplicates(std::vector<T, Alloc>& v)
144 {
145     std::sort(v.begin(), v.end());
146     v.erase(std::unique(v.begin(), v.end()), v.end());
147 }
148 
149 
150 template <class ForwardIterator, class T, typename CompLess> inline
binary_search(ForwardIterator first,ForwardIterator last,const T & value,CompLess less)151 ForwardIterator binary_search(ForwardIterator first, ForwardIterator last, const T& value, CompLess less)
152 {
153     first = std::lower_bound(first, last, value, less);
154     if (first != last && !less(value, *first))
155         return first;
156     else
157         return last;
158 }
159 
160 
161 template <class BidirectionalIterator, class T> inline
find_last(const BidirectionalIterator first,const BidirectionalIterator last,const T & value)162 BidirectionalIterator find_last(const BidirectionalIterator first, const BidirectionalIterator last, const T& value)
163 {
164     for (BidirectionalIterator it = last; it != first;) //reverse iteration: 1. check 2. decrement 3. evaluate
165     {
166         --it; //
167 
168         if (*it == value)
169             return it;
170     }
171     return last;
172 }
173 
174 
175 template <class BidirectionalIterator1, class BidirectionalIterator2> inline
search_last(const BidirectionalIterator1 first1,BidirectionalIterator1 last1,const BidirectionalIterator2 first2,const BidirectionalIterator2 last2)176 BidirectionalIterator1 search_last(const BidirectionalIterator1 first1,       BidirectionalIterator1 last1,
177                                    const BidirectionalIterator2 first2, const BidirectionalIterator2 last2)
178 {
179     const BidirectionalIterator1 itNotFound = last1;
180 
181     //reverse iteration: 1. check 2. decrement 3. evaluate
182     for (;;)
183     {
184         BidirectionalIterator1 it1 = last1;
185         BidirectionalIterator2 it2 = last2;
186 
187         for (;;)
188         {
189             if (it2 == first2) return it1;
190             if (it1 == first1) return itNotFound;
191 
192             --it1;
193             --it2;
194 
195             if (*it1 != *it2) break;
196         }
197         --last1;
198     }
199 }
200 
201 
202 template <class InputIterator1, class InputIterator2> inline
equal(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,InputIterator2 last2)203 bool equal(InputIterator1 first1, InputIterator1 last1,
204            InputIterator2 first2, InputIterator2 last2)
205 {
206     return last1 - first1 == last2 - first2 && std::equal(first1, last1, first2);
207 }
208 
209 
210 #if defined _MSC_VER && _MSC_VER <= 1600
211     static_assert(false, "VS2010 performance bug in std::unordered_set<>: http://drdobbs.com/blogs/cpp/232200410 -> should be fixed in VS11");
212 #endif
213 
214 
215 template <class ByteIterator> inline
hashBytes(ByteIterator first,ByteIterator last)216 size_t hashBytes(ByteIterator first, ByteIterator last)
217 {
218     //FNV-1a: http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
219 #ifdef ZEN_BUILD_32BIT
220     const size_t basis = 2166136261U;
221 #elif defined ZEN_BUILD_64BIT
222     const size_t basis = 14695981039346656037ULL;
223 #endif
224     return hashBytesAppend(basis, first, last);
225 }
226 
227 
228 template <class ByteIterator> inline
hashBytesAppend(size_t hashVal,ByteIterator first,ByteIterator last)229 size_t hashBytesAppend(size_t hashVal, ByteIterator first, ByteIterator last)
230 {
231 #ifdef ZEN_BUILD_32BIT
232     const size_t prime = 16777619U;
233 #elif defined ZEN_BUILD_64BIT
234     const size_t prime = 1099511628211ULL;
235 #endif
236     static_assert(sizeof(typename std::iterator_traits<ByteIterator>::value_type) == 1, "");
237 
238     for (; first != last; ++first)
239     {
240         hashVal ^= static_cast<size_t>(*first);
241         hashVal *= prime;
242     }
243     return hashVal;
244 }
245 }
246 
247 #endif //STL_TOOLS_H_84567184321434
248