You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by jp...@apache.org on 2015/02/23 18:37:06 UTC
trafficserver git commit: TS-3400: Use common FNV hash code everywhere
Repository: trafficserver
Updated Branches:
refs/heads/master be237ea7e -> d08db5d46
TS-3400: Use common FNV hash code everywhere
Remove 3 implementations of the FNV hashing algorithm in preference
to the copy we have in libts. Add simple case-insensitive hashing
support to the common implementation (using toupper so we remain
compatible).
Coverity CID #1021863
Project: http://git-wip-us.apache.org/repos/asf/trafficserver/repo
Commit: http://git-wip-us.apache.org/repos/asf/trafficserver/commit/d08db5d4
Tree: http://git-wip-us.apache.org/repos/asf/trafficserver/tree/d08db5d4
Diff: http://git-wip-us.apache.org/repos/asf/trafficserver/diff/d08db5d4
Branch: refs/heads/master
Commit: d08db5d46a979ec9dd4a4d00fa560858096579d6
Parents: be237ea
Author: James Peach <jp...@apache.org>
Authored: Thu Jan 29 11:14:27 2015 -0800
Committer: James Peach <jp...@apache.org>
Committed: Mon Feb 23 09:34:15 2015 -0800
----------------------------------------------------------------------
CHANGES | 4 +++-
iocore/hostdb/I_HostDBProcessor.h | 21 ++++++++------------
lib/ts/Hash.h | 9 +++++++++
lib/ts/HashFNV.cc | 29 ++--------------------------
lib/ts/HashFNV.h | 35 ++++++++++++++++++++++++++++++++--
proxy/hdrs/HdrToken.cc | 15 ++++-----------
proxy/logstats.cc | 10 ++++------
7 files changed, 63 insertions(+), 60 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/d08db5d4/CHANGES
----------------------------------------------------------------------
diff --git a/CHANGES b/CHANGES
index a286ec5..ea982c8 100644
--- a/CHANGES
+++ b/CHANGES
@@ -1,6 +1,8 @@
-*- coding: utf-8 -*-
Changes with Apache Traffic Server 5.3.0
-
+
+ *) [TS-3400] Use common FNV hash code everywhere.
+
*) [TS-3334] Restore default for proxy.config.proxy_name.
*) [TS-3345] cacheurl plugin: Better error handling on config problems.
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/d08db5d4/iocore/hostdb/I_HostDBProcessor.h
----------------------------------------------------------------------
diff --git a/iocore/hostdb/I_HostDBProcessor.h b/iocore/hostdb/I_HostDBProcessor.h
index c26a403..ab1f3ed 100644
--- a/iocore/hostdb/I_HostDBProcessor.h
+++ b/iocore/hostdb/I_HostDBProcessor.h
@@ -64,20 +64,15 @@ static inline unsigned int
makeHostHash(const char *string)
{
ink_assert(string && *string);
- if (!string || *string == 0)
- return 0;
-
- const uint32_t InitialFNV = 2166136261U;
- const int32_t FNVMultiple = 16777619;
-
- uint64_t hash = InitialFNV;
- uint32_t *p = (uint32_t *) &hash;
- while(*string) {
- p[0] = p[0] ^ (toupper(*string));
- hash = (p[1] ^ p[0]) * FNVMultiple;
- ++string;
+
+ if (string && *string) {
+ ATSHash32FNV1a fnv;
+ fnv.update(string, strlen(string), ATSHash::nocase());
+ fnv.final();
+ return fnv.get();
}
- return (p[1] ^ p[0]);
+
+ return 0;
}
//
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/d08db5d4/lib/ts/Hash.h
----------------------------------------------------------------------
diff --git a/lib/ts/Hash.h b/lib/ts/Hash.h
index bd67e2c..2306389 100644
--- a/lib/ts/Hash.h
+++ b/lib/ts/Hash.h
@@ -24,6 +24,7 @@
#include <cstddef>
#include <stdint.h>
+#include <ctype.h>
struct ATSHashBase
{
@@ -35,6 +36,14 @@ struct ATSHashBase
struct ATSHash:ATSHashBase
{
+ struct nullxfrm {
+ uint8_t operator() (uint8_t byte) const { return byte; }
+ };
+
+ struct nocase {
+ uint8_t operator() (uint8_t byte) const { return toupper(byte); }
+ };
+
virtual const void *get(void) const = 0;
virtual size_t size(void) const = 0;
virtual bool operator==(const ATSHash &) const;
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/d08db5d4/lib/ts/HashFNV.cc
----------------------------------------------------------------------
diff --git a/lib/ts/HashFNV.cc b/lib/ts/HashFNV.cc
index 36042a9..c4897bb 100644
--- a/lib/ts/HashFNV.cc
+++ b/lib/ts/HashFNV.cc
@@ -9,8 +9,8 @@
#include "HashFNV.h"
-#define FNV_INIT_32 ((uint32_t)0x811c9dc5)
-#define FNV_INIT_64 ((uint64_t)0xcbf29ce484222325ULL)
+static const uint32_t FNV_INIT_32 = 0x811c9dc5u;
+static const uint64_t FNV_INIT_64 = 0xcbf29ce484222325ull;
// FNV-1a 64bit
ATSHash32FNV1a::ATSHash32FNV1a(void)
@@ -19,18 +19,6 @@ ATSHash32FNV1a::ATSHash32FNV1a(void)
}
void
-ATSHash32FNV1a::update(const void *data, size_t len)
-{
- uint8_t *bp = (uint8_t *) data;
- uint8_t *be = bp + len;
-
- while (bp < be) {
- hval ^= (uint32_t) *bp++;
- hval += (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24);
- }
-}
-
-void
ATSHash32FNV1a::final(void)
{
}
@@ -52,19 +40,6 @@ ATSHash64FNV1a::ATSHash64FNV1a(void)
{
this->clear();
}
-
-void
-ATSHash64FNV1a::update(const void *data, size_t len)
-{
- uint8_t *bp = (uint8_t *) data;
- uint8_t *be = bp + len;
-
- while (bp < be) {
- hval ^= (uint64_t) *bp++;
- hval += (hval << 1) + (hval << 4) + (hval << 5) + (hval << 7) + (hval << 8) + (hval << 40);
- }
-}
-
void
ATSHash64FNV1a::final(void)
{
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/d08db5d4/lib/ts/HashFNV.h
----------------------------------------------------------------------
diff --git a/lib/ts/HashFNV.h b/lib/ts/HashFNV.h
index 9fec580..4467b7a 100644
--- a/lib/ts/HashFNV.h
+++ b/lib/ts/HashFNV.h
@@ -34,7 +34,10 @@
struct ATSHash32FNV1a:ATSHash32
{
ATSHash32FNV1a(void);
- void update(const void *data, size_t len);
+
+ template <typename Transform> void update(const void *data, size_t len, Transform xfrm);
+ void update(const void *data, size_t len) { update(data, len, ATSHash::nullxfrm()); }
+
void final(void);
uint32_t get(void) const;
void clear(void);
@@ -43,10 +46,25 @@ private:
uint32_t hval;
};
+template <typename Transform> void
+ATSHash32FNV1a::update(const void *data, size_t len, Transform xfrm)
+{
+ uint8_t *bp = (uint8_t *) data;
+ uint8_t *be = bp + len;
+
+ for (; bp < be; ++bp) {
+ hval ^= (uint32_t) xfrm(*bp);
+ hval += (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24);
+ }
+}
+
struct ATSHash64FNV1a:ATSHash64
{
ATSHash64FNV1a(void);
- void update(const void *data, size_t len);
+
+ template <typename Transform> void update(const void *data, size_t len, Transform xfrm);
+ void update(const void *data, size_t len) { update(data, len, ATSHash::nullxfrm()); }
+
void final(void);
uint64_t get(void) const;
void clear(void);
@@ -55,4 +73,17 @@ private:
uint64_t hval;
};
+
+template <typename Transform> void
+ATSHash64FNV1a::update(const void *data, size_t len, Transform xfrm)
+{
+ uint8_t *bp = (uint8_t *) data;
+ uint8_t *be = bp + len;
+
+ for (; bp < be; ++bp) {
+ hval ^= (uint64_t) xfrm(*bp);
+ hval += (hval << 1) + (hval << 4) + (hval << 5) + (hval << 7) + (hval << 8) + (hval << 40);
+ }
+}
+
#endif
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/d08db5d4/proxy/hdrs/HdrToken.cc
----------------------------------------------------------------------
diff --git a/proxy/hdrs/HdrToken.cc b/proxy/hdrs/HdrToken.cc
index 4bcf956..9f012e6 100644
--- a/proxy/hdrs/HdrToken.cc
+++ b/proxy/hdrs/HdrToken.cc
@@ -368,17 +368,10 @@ hash_to_slot(uint32_t hash)
inline uint32_t
hdrtoken_hash(const unsigned char *string, unsigned int length)
{
- static const uint32_t InitialFNV = 2166136261U;
- static const int32_t FNVMultiple = 16777619;
-
- uint32_t hash = InitialFNV;
-
- for (size_t i = 0; i < length; i++) {
- hash = hash ^ (toupper(string[i]));
- hash = hash * FNVMultiple;
- }
-
- return hash;
+ ATSHash32FNV1a fnv;
+ fnv.update(string, length, ATSHash::nocase());
+ fnv.final();
+ return fnv.get();
}
/*-------------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/d08db5d4/proxy/logstats.cc
----------------------------------------------------------------------
diff --git a/proxy/logstats.cc b/proxy/logstats.cc
index fdd4417..92cbe7c 100644
--- a/proxy/logstats.cc
+++ b/proxy/logstats.cc
@@ -329,16 +329,14 @@ struct eqstr
struct hash_fnv32 {
inline uint32_t operator()(const char* s) const
{
- uint32_t hval = (uint32_t)0x811c9dc5; /* FNV1_32_INIT */
+ ATSHash32FNV1a fnv;
if (s) {
- while (*s) {
- hval ^= (uint32_t)*s++;
- hval *= (uint32_t)0x01000193; /* FNV_32_PRIME */
- }
+ fnv.update(s, strlen(s));
}
- return hval;
+ fnv.final();
+ return fnv.get();
}
};