[prev in list] [next in list] [prev in thread] [next in thread] 

List:       quagga-dev
Subject:    [quagga-dev 8204] Re: [PATCH 1/3] Better hashing of string values
From:       Balaji G <balajig81 () gmail ! com>
Date:       2010-08-28 16:53:15
Message-ID: AANLkTi=NgECXczhC2dOYYdpOWOuLRgdafNCZsCA5HN=9 () mail ! gmail ! com
[Download RAW message or body]

[Attachment #2 (multipart/alternative)]


Hi Stephen

Applied, Thanks

Cheers,
  - Balaji


On Sat, Aug 28, 2010 at 2:41 AM, Stephen Hemminger <shemminger@vyatta.com>wrote:

> Replace simple additive hash with a hash function with better
> distribution.  For more information on hash functions see:
>   http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
>
> Signed-off-by: Stephen Hemminger <shemminger@vyatta.com>
> ---
> This patch is NOT in latest Vyatta release, but has passed
> regression test for next release.
>
>  lib/distribute.c |   13 ++++---------
>  lib/hash.c       |   11 +++++++++++
>  lib/hash.h       |    2 ++
>  lib/if_rmap.c    |    9 ++-------
>  4 files changed, 19 insertions(+), 16 deletions(-)
>
> diff --git a/lib/distribute.c b/lib/distribute.c
> index 242a225..420849d 100644
> --- a/lib/distribute.c
> +++ b/lib/distribute.c
> @@ -114,16 +114,11 @@ distribute_get (const char *ifname)
>  }
>
>  static unsigned int
> -distribute_hash_make (struct distribute *dist)
> +distribute_hash_make (void *arg)
>  {
> -  unsigned int i, key;
> +  const struct distribute *dist = arg;
>
> -  key = 0;
> -  if (dist->ifname)
> -    for (i = 0; i < strlen (dist->ifname); i++)
> -      key += dist->ifname[i];
> -
> -  return key;
> +  return dist->ifname ? string_hash_make (dist->ifname) : 0;
>  }
>
>  /* If two distribute-list have same value then return 1 else return
> @@ -763,7 +758,7 @@ distribute_list_reset ()
>  void
>  distribute_list_init (int node)
>  {
> -  disthash = hash_create ((unsigned int (*) (void *))
> distribute_hash_make,
> +  disthash = hash_create (distribute_hash_make,
>                           (int (*) (const void *, const void *))
> distribute_cmp);
>
>   if(node==RIP_NODE) {
> diff --git a/lib/hash.c b/lib/hash.c
> index 672327e..6db79ea 100644
> --- a/lib/hash.c
> +++ b/lib/hash.c
> @@ -101,6 +101,17 @@ hash_lookup (struct hash *hash, void *data)
>   return hash_get (hash, data, NULL);
>  }
>
> +/* Simple Bernstein hash which is simple and fast for common case */
> +unsigned int string_hash_make (const char *str)
> +{
> +  unsigned int hash = 0;
> +
> +  while (*str)
> +    hash = (hash * 33) ^ (unsigned int) *str++;
> +
> +  return hash;
> +}
> +
>  /* This function release registered value from specified hash.  When
>    release is successfully finished, return the data pointer in the
>    hash backet.  */
> diff --git a/lib/hash.h b/lib/hash.h
> index f4b1c23..4cb772e 100644
> --- a/lib/hash.h
> +++ b/lib/hash.h
> @@ -70,4 +70,6 @@ extern void hash_iterate (struct hash *,
>  extern void hash_clean (struct hash *, void (*) (void *));
>  extern void hash_free (struct hash *);
>
> +extern unsigned int string_hash_make (const char *);
> +
>  #endif /* _ZEBRA_HASH_H */
> diff --git a/lib/if_rmap.c b/lib/if_rmap.c
> index ddc62fd..9774be4 100644
> --- a/lib/if_rmap.c
> +++ b/lib/if_rmap.c
> @@ -109,14 +109,9 @@ if_rmap_get (const char *ifname)
>  static unsigned int
>  if_rmap_hash_make (void *data)
>  {
> -  struct if_rmap *if_rmap = data;
> -  unsigned int i, key;
> +  const struct if_rmap *if_rmap = data;
>
> -  key = 0;
> -  for (i = 0; i < strlen (if_rmap->ifname); i++)
> -    key += if_rmap->ifname[i];
> -
> -  return key;
> +  return string_hash_make (if_rmap->ifname);
>  }
>
>  static int
> --
> 1.7.0.4
>
>

[Attachment #5 (text/html)]

Hi Stephen <br>
<br>
Applied, Thanks<br>
<br>
Cheers,<br>
   - Balaji<br><br><br><div class="gmail_quote">On Sat, Aug 28, 2010 at 2:41 AM, \
Stephen Hemminger <span dir="ltr">&lt;<a \
href="mailto:shemminger@vyatta.com">shemminger@vyatta.com</a>&gt;</span> \
wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; \
border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"> Replace simple \
additive hash with a hash function with better<br> distribution.   For more \
information on hash functions see:<br>  <a \
href="http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx" \
target="_blank">http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx</a><br>
 <br>
Signed-off-by: Stephen Hemminger &lt;<a \
                href="mailto:shemminger@vyatta.com">shemminger@vyatta.com</a>&gt;<br>
---<br>
This patch is NOT in latest Vyatta release, but has passed<br>
regression test for next release.<br>
<br>
  lib/distribute.c |    13 ++++---------<br>
  lib/hash.c          |    11 +++++++++++<br>
  lib/hash.h          |      2 ++<br>
  lib/if_rmap.c      |      9 ++-------<br>
  4 files changed, 19 insertions(+), 16 deletions(-)<br>
<br>
diff --git a/lib/distribute.c b/lib/distribute.c<br>
index 242a225..420849d 100644<br>
--- a/lib/distribute.c<br>
+++ b/lib/distribute.c<br>
@@ -114,16 +114,11 @@ distribute_get (const char *ifname)<br>
  }<br>
<br>
  static unsigned int<br>
-distribute_hash_make (struct distribute *dist)<br>
+distribute_hash_make (void *arg)<br>
  {<br>
-   unsigned int i, key;<br>
+   const struct distribute *dist = arg;<br>
<br>
-   key = 0;<br>
-   if (dist-&gt;ifname)<br>
-      for (i = 0; i &lt; strlen (dist-&gt;ifname); i++)<br>
-         key += dist-&gt;ifname[i];<br>
-<br>
-   return key;<br>
+   return dist-&gt;ifname ? string_hash_make (dist-&gt;ifname) : 0;<br>
  }<br>
<br>
  /* If two distribute-list have same value then return 1 else return<br>
@@ -763,7 +758,7 @@ distribute_list_reset ()<br>
  void<br>
  distribute_list_init (int node)<br>
  {<br>
-   disthash = hash_create ((unsigned int (*) (void *)) distribute_hash_make,<br>
+   disthash = hash_create (distribute_hash_make,<br>
                                        (int (*) (const void *, const void *)) \
distribute_cmp);<br> <br>
    if(node==RIP_NODE) {<br>
diff --git a/lib/hash.c b/lib/hash.c<br>
index 672327e..6db79ea 100644<br>
--- a/lib/hash.c<br>
+++ b/lib/hash.c<br>
@@ -101,6 +101,17 @@ hash_lookup (struct hash *hash, void *data)<br>
    return hash_get (hash, data, NULL);<br>
  }<br>
<br>
+/* Simple Bernstein hash which is simple and fast for common case */<br>
+unsigned int string_hash_make (const char *str)<br>
+{<br>
+   unsigned int hash = 0;<br>
+<br>
+   while (*str)<br>
+      hash = (hash * 33) ^ (unsigned int) *str++;<br>
+<br>
+   return hash;<br>
+}<br>
+<br>
  /* This function release registered value from specified hash.   When<br>
      release is successfully finished, return the data pointer in the<br>
      hash backet.   */<br>
diff --git a/lib/hash.h b/lib/hash.h<br>
index f4b1c23..4cb772e 100644<br>
--- a/lib/hash.h<br>
+++ b/lib/hash.h<br>
@@ -70,4 +70,6 @@ extern void hash_iterate (struct hash *,<br>
  extern void hash_clean (struct hash *, void (*) (void *));<br>
  extern void hash_free (struct hash *);<br>
<br>
+extern unsigned int string_hash_make (const char *);<br>
+<br>
  #endif /* _ZEBRA_HASH_H */<br>
diff --git a/lib/if_rmap.c b/lib/if_rmap.c<br>
index ddc62fd..9774be4 100644<br>
--- a/lib/if_rmap.c<br>
+++ b/lib/if_rmap.c<br>
@@ -109,14 +109,9 @@ if_rmap_get (const char *ifname)<br>
  static unsigned int<br>
  if_rmap_hash_make (void *data)<br>
  {<br>
-   struct if_rmap *if_rmap = data;<br>
-   unsigned int i, key;<br>
+   const struct if_rmap *if_rmap = data;<br>
<br>
-   key = 0;<br>
-   for (i = 0; i &lt; strlen (if_rmap-&gt;ifname); i++)<br>
-      key += if_rmap-&gt;ifname[i];<br>
-<br>
-   return key;<br>
+   return string_hash_make (if_rmap-&gt;ifname);<br>
  }<br>
<br>
  static int<br>
<font color="#888888">--<br>
1.7.0.4<br>
<br>
</font></blockquote></div><br>



_______________________________________________
Quagga-dev mailing list
Quagga-dev@lists.quagga.net
http://lists.quagga.net/mailman/listinfo/quagga-dev


[prev in list] [next in list] [prev in thread] [next in thread]

Configure | About | News | Add a list | Sponsored by KoreLogic