123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081 |
- typedef UA_UInt32 hash_t;
- static hash_t mod(hash_t h, hash_t size) { return h % size; }
- static hash_t mod2(hash_t h, hash_t size) { return 1 + (h % (size - 2)); }
- /* Based on Murmur-Hash 3 by Austin Appleby (public domain, freely usable) */
- static hash_t hash_array(const UA_Byte *data, UA_UInt32 len, UA_UInt32 seed) {
- if(data == NULL)
- return 0;
- const int32_t nblocks = (int32_t)(len / 4);
- const uint32_t *blocks;
- static const uint32_t c1 = 0xcc9e2d51;
- static const uint32_t c2 = 0x1b873593;
- static const uint32_t r1 = 15;
- static const uint32_t r2 = 13;
- static const uint32_t m = 5;
- static const uint32_t n = 0xe6546b64;
- hash_t hash = seed;
- /* Somce compilers emit a warning when casting from a byte array to ints. */
- #if ((__GNUC__ == 4 && __GNUC_MINOR__ >= 6) || __GNUC__ > 4 || defined(__clang__))
- #pragma GCC diagnostic push
- #pragma GCC diagnostic ignored "-Wcast-align"
- #endif
- blocks = (const uint32_t *)data;
- #if ((__GNUC__ == 4 && __GNUC_MINOR__ >= 6) || __GNUC__ > 4 || defined(__clang__))
- #pragma GCC diagnostic pop
- #endif
- for(int32_t i = 0;i < nblocks;i++) {
- uint32_t k = blocks[i];
- k *= c1;
- k = (k << r1) | (k >> (32 - r1));
- k *= c2;
- hash ^= k;
- hash = ((hash << r2) | (hash >> (32 - r2))) * m + n;
- }
- const uint8_t *tail = (const uint8_t *)(data + nblocks * 4);
- uint32_t k1 = 0;
- switch(len & 3) {
- case 3:
- k1 ^= (uint32_t)(tail[2] << 16);
- case 2:
- k1 ^= (uint32_t)(tail[1] << 8);
- case 1:
- k1 ^= tail[0];
- k1 *= c1;
- k1 = (k1 << r1) | (k1 >> (32 - r1));
- k1 *= c2;
- hash ^= k1;
- }
- hash ^= len;
- hash ^= (hash >> 16);
- hash *= 0x85ebca6b;
- hash ^= (hash >> 13);
- hash *= 0xc2b2ae35;
- hash ^= (hash >> 16);
- return hash;
- }
- static hash_t hash(const UA_NodeId *n) {
- switch(n->identifierType) {
- case UA_NODEIDTYPE_NUMERIC:
- /* Knuth's multiplicative hashing */
- return (hash_t)((n->identifier.numeric + n->namespaceIndex) * 2654435761); // mod(2^32) is implicit
- case UA_NODEIDTYPE_STRING:
- return hash_array(n->identifier.string.data, (UA_UInt32)n->identifier.string.length,
- n->namespaceIndex);
- case UA_NODEIDTYPE_GUID:
- return hash_array((const UA_Byte*)&(n->identifier.guid), sizeof(UA_Guid), n->namespaceIndex);
- case UA_NODEIDTYPE_BYTESTRING:
- return hash_array((const UA_Byte*)n->identifier.byteString.data,
- (UA_UInt32)n->identifier.byteString.length, n->namespaceIndex);
- default:
- UA_assert(false);
- return 0;
- }
- }
|