comparison: ucx/hash_key.c
ucx/hash_key.c
- changeset 112
- c3f2f16fa4b8
- parent 101
- 7b3a3130be44
- child 113
- dde28a806552
equal
deleted
inserted
replaced
| 111:81c4f73236a4 | 112:c3f2f16fa4b8 |
|---|---|
| 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
| 26 * POSSIBILITY OF SUCH DAMAGE. | 26 * POSSIBILITY OF SUCH DAMAGE. |
| 27 */ | 27 */ |
| 28 | 28 |
| 29 #include "cx/hash_key.h" | 29 #include "cx/hash_key.h" |
| 30 #include "cx/compare.h" | |
| 30 #include <string.h> | 31 #include <string.h> |
| 31 | 32 |
| 32 void cx_hash_murmur(CxHashKey *key) { | 33 void cx_hash_murmur(CxHashKey *key) { |
| 33 const unsigned char *data = key->data; | 34 const unsigned char *data = key->data; |
| 34 if (data == NULL) { | 35 if (data == NULL) { |
| 60 } | 61 } |
| 61 | 62 |
| 62 switch (len) { | 63 switch (len) { |
| 63 case 3: | 64 case 3: |
| 64 h ^= (data[i + 2] & 0xFF) << 16; | 65 h ^= (data[i + 2] & 0xFF) << 16; |
| 65 __attribute__((__fallthrough__)); | 66 cx_attr_fallthrough; |
| 66 case 2: | 67 case 2: |
| 67 h ^= (data[i + 1] & 0xFF) << 8; | 68 h ^= (data[i + 1] & 0xFF) << 8; |
| 68 __attribute__((__fallthrough__)); | 69 cx_attr_fallthrough; |
| 69 case 1: | 70 case 1: |
| 70 h ^= (data[i + 0] & 0xFF); | 71 h ^= (data[i + 0] & 0xFF); |
| 71 h *= m; | 72 h *= m; |
| 72 __attribute__((__fallthrough__)); | 73 cx_attr_fallthrough; |
| 73 default: // do nothing | 74 default: // do nothing |
| 74 ; | 75 ; |
| 75 } | 76 } |
| 76 | 77 |
| 77 h ^= h >> 13; | 78 h ^= h >> 13; |
| 78 h *= m; | 79 h *= m; |
| 79 h ^= h >> 15; | 80 h ^= h >> 15; |
| 80 | 81 |
| 81 key->hash = h; | 82 key->hash = h; |
| 83 } | |
| 84 | |
| 85 | |
| 86 uint32_t cx_hash_u32(uint32_t x) { | |
| 87 x = ((x >> 16) ^ x) * 0x45d9f3bu; | |
| 88 x = ((x >> 16) ^ x) * 0x45d9f3bu; | |
| 89 x = (x >> 16) ^ x; | |
| 90 return x; | |
| 91 } | |
| 92 | |
| 93 uint64_t cx_hash_u64(uint64_t x) { | |
| 94 x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9); | |
| 95 x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb); | |
| 96 x = x ^ (x >> 31); | |
| 97 return x; | |
| 82 } | 98 } |
| 83 | 99 |
| 84 CxHashKey cx_hash_key_str(const char *str) { | 100 CxHashKey cx_hash_key_str(const char *str) { |
| 85 CxHashKey key; | 101 CxHashKey key; |
| 86 key.data = str; | 102 key.data = str; |
| 108 key.data = obj; | 124 key.data = obj; |
| 109 key.len = len; | 125 key.len = len; |
| 110 cx_hash_murmur(&key); | 126 cx_hash_murmur(&key); |
| 111 return key; | 127 return key; |
| 112 } | 128 } |
| 129 | |
| 130 CxHashKey cx_hash_key_u32(uint32_t x) { | |
| 131 CxHashKey key; | |
| 132 key.data = NULL; | |
| 133 key.len = 0; | |
| 134 key.hash = cx_hash_u32(x); | |
| 135 return key; | |
| 136 } | |
| 137 | |
| 138 CxHashKey cx_hash_key_u64(uint64_t x) { | |
| 139 CxHashKey key; | |
| 140 key.data = NULL; | |
| 141 key.len = 0; | |
| 142 key.hash = cx_hash_u64(x); | |
| 143 return key; | |
| 144 } | |
| 145 | |
| 146 int cx_hash_key_cmp(const CxHashKey *left, const CxHashKey *right) { | |
| 147 int d; | |
| 148 d = cx_vcmp_uint64(left->hash, right->hash); | |
| 149 if (d != 0) return d; | |
| 150 d = cx_vcmp_size(left->len, right->len); | |
| 151 if (d != 0) return d; | |
| 152 if (left->len == 0) return 0; | |
| 153 return memcmp(left->data, right->data, left->len); | |
| 154 } |
