3rdparty/lock_free_map/map_traits.h

0001 /*------------------------------------------------------------------------
0002   Junction: Concurrent data structures in C++
0003   Copyright (c) 2016 Jeff Preshing
0004   Distributed under the Simplified BSD License.
0005   Original location: https://github.com/preshing/junction
0006   This software is distributed WITHOUT ANY WARRANTY; without even the
0007   implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
0008   See the LICENSE file for more information.
0009 ------------------------------------------------------------------------*/
0010
0011 #ifndef MAPTRAITS_H
0012 #define MAPTRAITS_H
0013
0014 #include <QtCore>
0015
0016 inline quint64 roundUpPowerOf2(quint64 v)
0017 {
0018     v--;
0019     v |= v >> 1;
0020     v |= v >> 2;
0021     v |= v >> 4;
0022     v |= v >> 8;
0023     v |= v >> 16;
0024     v |= v >> 32;
0025     v++;
0026     return v;
0027 }
0028
0029 inline bool isPowerOf2(quint64 v)
0030 {
0031     return (v & (v - 1)) == 0;
0032 }
0033
0034 inline quint32 avalanche(quint32 h)
0035 {
0036     h ^= h >> 16;
0037     h *= 0x85ebca6b;
0038     h ^= h >> 13;
0039     h *= 0xc2b2ae35;
0040     h ^= h >> 16;
0041     return h;
0042 }
0043
0044 inline quint32 deavalanche(quint32 h)
0045 {
0046     h ^= h >> 16;
0047     h *= 0x7ed1b41d;
0048     h ^= (h ^ (h >> 13)) >> 13;
0049     h *= 0xa5cb9243;
0050     h ^= h >> 16;
0051     return h;
0052 }
0053
0054 template <class T>
0055 struct DefaultKeyTraits {
0056     typedef T Key;
0057     typedef quint32 Hash;
0058     static const Key NullKey = Key(0);
0059     static const Hash NullHash = Hash(0);
0060
0061     static Hash hash(T key)
0062     {
0063         return avalanche(Hash(key));
0064     }
0065
0066     static Key dehash(Hash hash)
0067     {
0068         return (T) deavalanche(hash);
0069     }
0070 };
0071
0072 template <class T>
0073 struct DefaultValueTraits {
0074     typedef T Value;
0075     typedef std::intptr_t IntType;
0076     static const IntType NullValue = 0;
0077     static const IntType Redirect = 1;
0078 };
0079
0080 #endif // MAPTRAITS_H