diff options
author | antirez <antirez@gmail.com> | 2019-08-02 20:24:27 +0200 |
---|---|---|
committer | antirez <antirez@gmail.com> | 2019-08-02 20:24:27 +0200 |
commit | 5e0faf4959169547f5b943639fcf4eab0bb3f3a2 (patch) | |
tree | 4385af42be89ce6ce7db53f1fe519279577bdc46 /utils/tracking_collisions.c | |
parent | a368209b1d92987462e4f359b59443a2cad9ef7d (diff) | |
download | redis-5e0faf4959169547f5b943639fcf4eab0bb3f3a2.tar.gz |
tracking_collisions.c: sha1 + crc64 implemented.
Diffstat (limited to 'utils/tracking_collisions.c')
-rw-r--r-- | utils/tracking_collisions.c | 36 |
1 files changed, 36 insertions, 0 deletions
diff --git a/utils/tracking_collisions.c b/utils/tracking_collisions.c index b996452e7..cd64b36c5 100644 --- a/utils/tracking_collisions.c +++ b/utils/tracking_collisions.c @@ -10,6 +10,11 @@ * And counts the resulting collisons generated in the 24 bits of output * needed for the tracking feature invalidation table (16 millions + entries) * + * Compile with: + * + * cc -O2 ./tracking_collisions.c ../src/crc64.c ../src/sha1.c + * ./a.out + * * -------------------------------------------------------------------------- * * Copyright (C) 2019 Salvatore Sanfilippo @@ -20,16 +25,47 @@ #include <stdint.h> #include <string.h> #include <stdio.h> +#include "../src/crc64.h" +#include "../src/sha1.h" #define TABLE_SIZE (1<<24) int Table[TABLE_SIZE]; +uint64_t crc64Hash(char *key, size_t len) { + return crc64(0,(unsigned char*)key,len); +} + +uint64_t sha1Hash(char *key, size_t len) { + SHA1_CTX ctx; + unsigned char hash[20]; + + SHA1Init(&ctx); + SHA1Update(&ctx,(unsigned char*)key,len); + SHA1Final(hash,&ctx); + uint64_t hash64; + memcpy(&hash64,hash,sizeof(hash64)); + return hash64; +} + /* Test the hashing function provided as callback and return the * number of collisions found. */ unsigned long testHashingFunction(uint64_t (*hash)(char *, size_t)) { unsigned long collisions = 0; memset(Table,0,sizeof(Table)); char *prefixes[] = {"object", "message", "user", NULL}; + for (int i = 0; prefixes[i] != NULL; i++) { + for (int j = 0; j < TABLE_SIZE/2; j++) { + char keyname[128]; + size_t keylen = snprintf(keyname,sizeof(keyname),"%s:%d", + prefixes[i],j); + uint64_t bucket = hash(keyname,keylen) % TABLE_SIZE; + if (Table[bucket]) { + collisions++; + } else { + Table[bucket] = 1; + } + } + } return collisions; } |