/*
 * Copyright (c) 2017 Cisco and/or its affiliates.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/*
 * cuckoo hash implementation based on paper
 * 'Algorithmic Improvements for Fast Concurrent Cuckoo Hashing'
 * by Xiaozhou Li, David G. Andersen, Michael Kaminsky, Michael J. Freedman
 * and their libcuckoo implementation (https://github.com/efficient/libcuckoo)
 */

#include <vppinfra/vec.h>
#include <vppinfra/cuckoo_template.h>

int CV (clib_cuckoo_search) (CVT (clib_cuckoo) * h,
			     CVT (clib_cuckoo_kv) * search_v,
			     CVT (clib_cuckoo_kv) * return_v)
{
  CVT (clib_cuckoo_kv) tmp = *search_v;
  int rv = CV (clib_cuckoo_search_inline) (h, &tmp);
  if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
    {
      *return_v = tmp;
    }
  return rv;
}

static
CVT (clib_cuckoo_bucket) *
CV (clib_cuckoo_bucket_at_index) (CVT (clib_cuckoo) * h, uword bucket)
{
  return vec_elt_at_index (h->buckets, bucket);
}

static uword CV (clib_cuckoo_get_nbuckets) (CVT (clib_cuckoo) * h)
{
  return vec_len (h->buckets);
}

static inline uword
CV (clib_cuckoo_elt_in_bucket_to_offset) (CVT (clib_cuckoo_bucket) * b,
					  CVT (clib_cuckoo_kv) * e)
{
  ASSERT (e >= b->elts);
  ASSERT (e <= &b->elts[sizeof (b->elts) / sizeof (b->elts[0]) - 1]);
  return e - b->elts;
}

u8 *CV (format_cuckoo_elt) (u8 * s, va_list * args)
{
  CVT (clib_cuckoo_kv) * elt = va_arg (*args, CVT (clib_cuckoo_kv) *);
  unsigned reduced_hash = va_arg (*args, unsigned);
  if (CV (clib_cuckoo_kv_is_free) (elt))
    {
      s = format (s, "[ -- empty -- ]");
    }
  else
    {
      s = format (s, "[%U, reduced hash: %u]", CV (format_cuckoo_kvp), elt,
		  reduced_hash);
    }
  return s;
}

u8 *CV (format_cuckoo_bucket) (u8 * s, va_list * args)
{
  CVT (clib_cuckoo_bucket) * bucket =
    va_arg (*args, CVT (clib_cuckoo_bucket) *);
  int i = 0;

  /* *INDENT-OFF* */
  clib_cuckoo_bucket_foreach_idx (i)
  {
    CVT (clib_cuckoo_kv) *elt = bucket->elts + i;
    s = format (s, "bucket %p, offset %d: %U\n", bucket, i,
                CV (format_cuckoo_elt), elt, bucket->reduced_hashes[i]);
  }
  /* *INDENT-ON* */
  clib_cuckoo_bucket_aux_t aux = bucket->aux;
  s = format (s, "version: %lld, use count: %d\n",
	      clib_cuckoo_bucket_aux_get_version (aux),
	      clib_cuckoo_bucket_aux_get_use_count (aux));
  return s;
}

#if CLIB_CUCKOO_DEBUG
static void CV (clib_cuckoo_deep_self_check) (CVT (clib_cuckoo) * h)
{
  CVT (clib_cuckoo_bucket) * bucket;
  uword bucket_idx = 0;
  /* *INDENT-OFF* */
  clib_cuckoo_foreach_bucket (bucket, h)
  {
    int i = 0;
    int used = 0;
    clib_cuckoo_bucket_foreach_idx (i)
    {
      CVT (clib_cuckoo_kv) *elt = bucket->elts + i;
      if (!CV (clib_cuckoo_kv_is_free) (elt))
        {
          u64 hash = CV (clib_cuckoo_hash) (elt);
          clib_cuckoo_lookup_info_t lookup = CV (clib_cuckoo_calc_lookup) (
              CV (clib_cuckoo_get_snapshot) (h), hash);
          CVT (clib_cuckoo_kv) kv = *elt;
          int rv = CV (clib_cuckoo_search) (h, &kv, &kv);
          if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
            {
              CLIB_CUCKOO_DBG ("Search for elt `%U' failed!",
                               CV (format_cuckoo_elt), elt,
                               bucket->reduced_hashes[i]);
              CLIB_CUCKOO_DBG ("%U", CV (format_cuckoo), h, 1);
            }
          ASSERT (aux.bucket1 == bucket_idx || aux.bucket2 == bucket_idx);
          ASSERT (CLIB_CUCKOO_ERROR_SUCCESS == rv);
          ++used;
        }
    }
    clib_cuckoo_bucket_aux_t aux = bucket->aux;
    ASSERT (used == clib_cuckoo_bucket_aux_get_use_count (aux));
    ++bucket_idx;
  }
  /* *INDENT-ON* */
  // CLIB_CUCKOO_DBG ("Deep self check passed: %U", CV (format_cuckoo), h);
}

#define CLIB_CUCKOO_DEEP_SELF_CHECK(h) CV (clib_cuckoo_deep_self_check) (h)
#define CLIB_CUCKOO_ASSERT_BUCKET_SORTED(b)                                 \
  do                                                                        \
    {                                                                       \
      int i;                                                                \
      int min_free = CLIB_CUCKOO_KVP_PER_BUCKET;                            \
      int max_used = 0;                                                     \
      clib_cuckoo_bucket_foreach_idx (i)                                    \
      {                                                                     \
        if (!CV (clib_cuckoo_kv_is_free) (b->elts + i))                     \
          {                                                                 \
            max_used = i;                                                   \
          }                                                                 \
        if (CV (clib_cuckoo_kv_is_free) (b->elts +                          \
                        <style>
@media only all and (prefers-color-scheme: dark) {
.highlight .hll { background-color: #49483e }
.highlight .c { color: #75715e } /* Comment */
.highlight .err { color: #960050; background-color: #1e0010 } /* Error */
.highlight .k { color: #66d9ef } /* Keyword */
.highlight .l { color: #ae81ff } /* Literal */
.highlight .n { color: #f8f8f2 } /* Name */
.highlight .o { color: #f92672 } /* Operator */
.highlight .p { color: #f8f8f2 } /* Punctuation */
.highlight .ch { color: #75715e } /* Comment.Hashbang */
.highlight .cm { color: #75715e } /* Comment.Multiline */
.highlight .cp { color: #75715e } /* Comment.Preproc */
.highlight .cpf { color: #75715e } /* Comment.PreprocFile */
.highlight .c1 { color: #75715e } /* Comment.Single */
.highlight .cs { color: #75715e } /* Comment.Special */
.highlight .gd { color: #f92672 } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .gi { color: #a6e22e } /* Generic.Inserted */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #75715e } /* Generic.Subheading */
.highlight .kc { color: #66d9ef } /* Keyword.Constant */
.highlight .kd { color: #66d9ef } /* Keyword.Declaration */
.highlight .kn { color: #f92672 } /* Keyword.Namespace */
.highlight .kp { color: #66d9ef } /* Keyword.Pseudo */
.highlight .kr { color: #66d9ef } /* Keyword.Reserved */
.highlight .kt { color: #66d9ef } /* Keyword.Type */
.highlight .ld { color: #e6db74 } /* Literal.Date */
.highlight .m { color: #ae81ff } /* Literal.Number */
.highlight .s { color: #e6db74 } /* Literal.String */
.highlight .na { color: #a6e22e } /* Name.Attribute */
.highlight .nb { color: #f8f8f2 } /* Name.Builtin */
.highlight .nc { color: #a6e22e } /* Name.Class */
.highlight .no { color: #66d9ef } /* Name.Constant */
.highlight .nd { color: #a6e22e } /* Name.Decorator */
.highlight .ni { color: #f8f8f2 } /* Name.Entity */
.highlight .ne { color: #a6e22e } /* Name.Exception */
.highlight .nf { color: #a6e22e } /* Name.Function */
.highlight .nl { color: #f8f8f2 } /* Name.Label */
.highlight .nn { color: #f8f8f2 } /* Name.Namespace */
.highlight .nx { color: #a6e22e } /* Name.Other */
.highlight .py { color: #f8f8f2 } /* Name.Property */
.highlight .nt { color: #f92672 } /* Name.Tag */
.highlight .nv { color: #f8f8f2 } /* Name.Variable */
.highlight .ow { color: #f92672 } /* Operator.Word */
.highlight .w { color: #f8f8f2 } /* Text.Whitespace */
.highlight .mb { color: #ae81ff } /* Literal.Number.Bin */
.highlight .mf { color: #ae81ff } /* Literal.Number.Float */
.highlight .mh { color: #ae81ff } /* Literal.Number.Hex */
.highlight .mi { color: #ae81ff } /* Literal.Number.Integer */
.highlight .mo { color: #ae81ff } /* Literal.Number.Oct */
.highlight .sa { color: #e6db74 } /* Literal.String.Affix */
.highlight .sb { color: #e6db74 } /* Literal.String.Backtick */
.highlight .sc { color: #e6db74 } /* Literal.String.Char */
.highlight .dl { color: #e6db74 } /* Literal.String.Delimiter */
.highlight .sd { color: #e6db74 } /* Literal.String.Doc */
.highlight .s2 { color: #e6db74 } /* Literal.String.Double */
.highlight .se { color: #ae81ff } /* Literal.String.Escape */
.highlight .sh { color: #e6db74 } /* Literal.String.Heredoc */
.highlight .si { color: #e6db74 } /* Literal.String.Interpol */
.highlight .sx { color: #e6db74 } /* Literal.String.Other */
.highlight .sr { color: #e6db74 } /* Literal.String.Regex */
.highlight .s1 { color: #e6db74 } /* Literal.String.Single */
.highlight .ss { color: #e6db74 } /* Literal.String.Symbol */
.highlight .bp { color: #f8f8f2 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #a6e22e } /* Name.Function.Magic */
.highlight .vc { color: #f8f8f2 } /* Name.Variable.Class */
.highlight .vg { color: #f8f8f2 } /* Name.Variable.Global */
.highlight .vi { color: #f8f8f2 } /* Name.Variable.Instance */
.highlight .vm { color: #f8f8f2 } /* Name.Variable.Magic */
.highlight .il { color: #ae81ff } /* Literal.Number.Integer.Long */
}
@media (prefers-color-scheme: light) {
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */
.highlight .nl { color: #336699; font-style: italic } /* Name.Label */
.highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */
.highlight .py { color: #336699; font-weight: bold } /* Name.Property */
.highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #336699 } /* Name.Variable */
.highlight .ow { color: #008800 } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */
.highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */
.highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */
.highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */
.highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */
.highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */
.highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */
.highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */
.highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */
.highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */
.highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */
.highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */
.highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */
.highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */
.highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */
.highlight .vc { color: #336699 } /* Name.Variable.Class */
.highlight .vg { color: #dd7700 } /* Name.Variable.Global */
.highlight .vi { color: #3333bb } /* Name.Variable.Instance */
.highlight .vm { color: #336699 } /* Name.Variable.Magic */
.highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */
}
</style><div class="highlight"><pre><span></span><span class="cm">/*</span>
<span class="cm"> * Copyright (c) 2017 Intel and/or its affiliates.</span>
<span class="cm"> * Licensed under the Apache License, Version 2.0 (the &quot;License&quot;);</span>
<span class="cm"> * you may not use this file except in compliance with the License.</span>
<span class="cm"> * You may obtain a copy of the License at:</span>
<span class="cm"> *</span>
<span class="cm"> *     http://www.apache.org/licenses/LICENSE-2.0</span>
<span class="cm"> *</span>
<span class="cm"> * Unless required by applicable law or agreed to in writing, software</span>
<span class="cm"> * distributed under the License is distributed on an &quot;AS IS&quot; BASIS,</span>
<span class="cm"> * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.</span>
<span class="cm"> * See the License for the specific language governing permissions and</span>
<span class="cm"> * limitations under the License.</span>
<span class="cm"> */</span>
<span class="n">gtpu_error</span> <span class="p">(</span><span class="n">DECAPSULATED</span><span class="p">,</span> <span class="s">&quot;good packets decapsulated&quot;</span><span class="p">)</span>
<span class="n">gtpu_error</span> <span class="p">(</span><span class="n">NO_SUCH_TUNNEL</span><span class="p">,</span> <span class="s">&quot;no such tunnel packets&quot;</span><span class="p">)</span>
<span class="n">gtpu_error</span> <span class="p">(</span><span class="n">BAD_VER</span><span class="p">,</span> <span class="s">&quot;packets with bad version in gtpu header&quot;</span><span class="p">)</span>
<span class="n">gtpu_error</span> <span class="p">(</span><span class="n">BAD_FLAGS</span><span class="p">,</span> <span class="s">&quot;packets with bad flags field in gtpu header&quot;</span><span class="p">)</span>
</pre></div>
</code></pre></td></tr></table>
</div> <!-- class=content -->
<div id="lfcollabprojects-footer">
  <div class="gray-diagonal">
    <div class="footer-inner">
      <p>
        &copy; 2016 <a href="https://www.fd.io/">FD.io</a> a Linux Foundation
        Collaborative Project. All Rights Reserved.
      </p>
      <p>
        Linux Foundation is a registered trademark of The Linux Foundation.
        Linux is a registered
        <a
          href="http://www.linuxfoundation.org/programs/legal/trademark"
          title="Linux Mark Institute"
          >trademark</a
        >
        of Linus Torvalds.
      </p>
      <p>
        Please see our
        <a href="http://www.linuxfoundation.org/privacy">privacy policy</a> and
        <a href="http://www.linuxfoundation.org/terms">terms of use</a>
      </p>
    </div>
  </div>
</div>
</div> <!-- id=cgit -->
</body>
</html>
v_is_free) (&b->elts[max_used]))
	{
	  --max_used;
	}
      if (min_free < max_used)
	{
	  CV (clib_cuckoo_swap_elts_in_bucket) (b, min_free, max_used);
	  i = min_free + 1;
	  j = max_used - 1;
	}
      else
	{
	  break;
	}
    }
}

static void CV (clib_cuckoo_free_locked_elt) (CVT (clib_cuckoo_kv) * elt)
{
  /*
   * FIXME - improve performance by getting rid of this clib_memset - make all
   * functions in this file not rely on clib_cuckoo_kv_is_free but instead
   * take use_count into account */
  clib_memset (elt, 0xff, sizeof (*elt));
}

static void CV (clib_cuckoo_free_elt_in_bucket) (CVT (clib_cuckoo_bucket) * b,
						 CVT (clib_cuckoo_kv) * elt)
{
  clib_cuckoo_bucket_aux_t aux =
    CV (clib_cuckoo_bucket_version_bump_and_lock) (b);
  int use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
  int offset = elt - b->elts;
  ASSERT (offset < use_count);
  CV (clib_cuckoo_free_locked_elt) (elt);
  if (offset != use_count - 1)
    {
      CV (clib_cuckoo_bucket_tidy) (b);
    }
  aux = clib_cuckoo_bucket_aux_set_use_count (aux, use_count - 1);
  CV (clib_cuckoo_bucket_unlock) (b, aux);
}

static void CV (clib_cuckoo_set_locked_elt) (CVT (clib_cuckoo_bucket) * b,
					     CVT (clib_cuckoo_kv) * elt,
					     CVT (clib_cuckoo_kv) * kvp,
					     u8 reduced_hash)
{
  int offset = CV (clib_cuckoo_elt_in_bucket_to_offset) (b, elt);
  clib_memcpy (elt, kvp, sizeof (*elt));
  b->reduced_hashes[offset] = reduced_hash;
  CLIB_CUCKOO_DBG ("Set bucket %p, offset %d, %U", b, offset,
		   CV (format_cuckoo_elt), elt, b->reduced_hashes[offset]);
}

static void CV (clib_cuckoo_set_elt) (CVT (clib_cuckoo_bucket) * b,
				      CVT (clib_cuckoo_kv) * elt,
				      CVT (clib_cuckoo_kv) * kvp,
				      u8 reduced_hash)
{
  clib_cuckoo_bucket_aux_t aux =
    CV (clib_cuckoo_bucket_version_bump_and_lock) (b);
  CV (clib_cuckoo_set_locked_elt) (b, elt, kvp, reduced_hash);
  CV (clib_cuckoo_bucket_unlock) (b, aux);
}

static int CV (clib_cuckoo_add_slow) (CVT (clib_cuckoo) * h,
				      CVT (clib_cuckoo_kv) * kvp,
				      clib_cuckoo_lookup_info_t * lookup,
				      u8 reduced_hash)
{
  uword path_idx;
  uword empty_bucket_idx;
  CVT (clib_cuckoo_kv) * empty_elt;
  int rv = CV (clib_cuckoo_find_empty_slot_bfs) (h, lookup, &path_idx,
						 &empty_bucket_idx,
						 &empty_elt);
  if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
    {
      uword buckets[CLIB_CUCKOO_BFS_MAX_PATH_LENGTH];
      uword offsets[CLIB_CUCKOO_BFS_MAX_PATH_LENGTH];
      clib_cuckoo_path_walk (h, path_idx, buckets, offsets);
      /*
       * walk back the path, moving the free element forward to one of our
       * buckets ...
       */
      clib_cuckoo_path_t *path = pool_elt_at_index (h->paths, path_idx);
      CVT (clib_cuckoo_bucket) * empty_bucket =
	CV (clib_cuckoo_bucket_at_index) (h, empty_bucket_idx);
      int i;
      for (i = path->length - 1; i >= 0; --i)
	{
	  /* copy the key-value in path to the bucket with empty element */
	  CVT (clib_cuckoo_bucket) * b =
	    CV (clib_cuckoo_bucket_at_index) (h, buckets[i]);
	  CVT (clib_cuckoo_kv) * elt = b->elts + offsets[i];
	  clib_cuckoo_bucket_aux_t empty_aux =
	    CV (clib_cuckoo_bucket_version_bump_and_lock) (empty_bucket);
	  CV (clib_cuckoo_set_locked_elt)
	    (empty_bucket, empty_elt, elt, b->reduced_hashes[elt - b->elts]);
	  if (i == path->length - 1)
	    {
	      /* we only need to increase the use count for the bucket with
	       * free element - all other buckets' use counts won't change */
	      empty_aux = clib_cuckoo_bucket_aux_set_use_count (empty_aux,
								clib_cuckoo_bucket_aux_get_use_count
								(empty_aux) +
								1);
	    }
	  CV (clib_cuckoo_bucket_unlock) (empty_bucket, empty_aux);
	  /*
	   * the element now exists in both places - in the previously empty
	   * element and in its original bucket - we can now safely overwrite
	   * the element in the original bucket with previous element in path
	   * without loosing data (and we don't need to modify the use count)
	   */
	  empty_bucket = b;
	  empty_elt = elt;
	}
      /* now we have a place to put the kvp in ... */
      CV (clib_cuckoo_set_elt) (empty_bucket, empty_elt, kvp, reduced_hash);
      CLIB_CUCKOO_DBG ("Slow insert success, bucket: %p\n%U", empty_bucket,
		       CV (format_cuckoo_bucket), empty_bucket);
#if CLIB_CUCKOO_DEBUG_COUNTERS
      ++h->slow_adds;
#endif
    }
  return rv;
}

static int CV (clib_cuckoo_add_fast) (CVT (clib_cuckoo) * h,
				      clib_cuckoo_lookup_info_t * lookup,
				      CVT (clib_cuckoo_kv) * kvp,
				      u8 reduced_hash)
{
  CVT (clib_cuckoo_kv) * elt;
  CVT (clib_cuckoo_bucket) * bucket1 =
    CV (clib_cuckoo_bucket_at_index) (h, lookup->bucket1);
  if ((elt = CV (clib_cuckoo_bucket_find_empty) (bucket1)))
    {
      clib_cuckoo_bucket_aux_t aux =
	CV (clib_cuckoo_bucket_version_bump_and_lock) (bucket1);
      CV (clib_cuckoo_set_locked_elt) (bucket1, elt, kvp, reduced_hash);
      aux =
	clib_cuckoo_bucket_aux_set_use_count (aux,
					      clib_cuckoo_bucket_aux_get_use_count
					      (aux) + 1);
      CV (clib_cuckoo_bucket_unlock) (bucket1, aux);
#if CLIB_CUCKOO_DEBUG_COUNTERS
      ++h->fast_adds;
#endif
      return CLIB_CUCKOO_ERROR_SUCCESS;
    }
  CVT (clib_cuckoo_bucket) * bucket2 =
    CV (clib_cuckoo_bucket_at_index) (h, lookup->bucket2);
  if ((elt =
       CV (clib_cuckoo_bucket_find_empty) (CV (clib_cuckoo_bucket_at_index)
					   (h, lookup->bucket2))))
    {
      clib_cuckoo_bucket_aux_t aux =
	CV (clib_cuckoo_bucket_version_bump_and_lock) (bucket2);
      CV (clib_cuckoo_set_locked_elt) (bucket2, elt, kvp, reduced_hash);
      aux =
	clib_cuckoo_bucket_aux_set_use_count (aux,
					      clib_cuckoo_bucket_aux_get_use_count
					      (aux) + 1);
      CV (clib_cuckoo_bucket_unlock) (bucket2, aux);
#if CLIB_CUCKOO_DEBUG_COUNTERS
      ++h->fast_adds;
#endif
      return CLIB_CUCKOO_ERROR_SUCCESS;
    }
  return CLIB_CUCKOO_ERROR_AGAIN;
}

/**
 * perform garbage collection
 *
 * this function assumes there is no other thread touching the cuckoo hash,
 * not even a reader, it's meant to be called from main thread
 * in a stop-the-world situation
 */
void CV (clib_cuckoo_garbage_collect) (CVT (clib_cuckoo) * h)
{
  CLIB_MEMORY_BARRIER ();
  CVT (clib_cuckoo_bucket) * *b;
  /* *INDENT-OFF* */
  vec_foreach (b, h->to_be_freed)
  {
    if (*b == h->buckets)
      {
        continue;
      }
#if CLIB_CUCKOO_DEBUG_GC
    fformat (stdout, "gc: free %p\n", *b);
#endif
    vec_free (*b);
  }
  /* *INDENT-ON* */
  vec_free (h->to_be_freed);
  CLIB_MEMORY_BARRIER ();
}

/**
 * expand and rehash a cuckoo hash
 *
 * 1. double the size of the hash table
 * 2. move items to new locations derived from the new size
 */
static void CV (clib_cuckoo_rehash) (CVT (clib_cuckoo) * h)
{
  CVT (clib_cuckoo_bucket) * old = h->buckets;
  uword old_nbuckets = vec_len (old);
  uword new_nbuckets = 2 * old_nbuckets;
  CVT (clib_cuckoo_bucket) * new =
    vec_dup_aligned (old, CLIB_CACHE_LINE_BYTES);
  /* allocate space */
  vec_validate_aligned (new, new_nbuckets - 1, CLIB_CACHE_LINE_BYTES);
  ASSERT (new_nbuckets == vec_len (new));
  /* store old pointer in to-be-freed list */
  vec_add1 (h->to_be_freed, old);
  /* mark new elements as free */
  CVT (clib_cuckoo_bucket) * bucket;
  for (bucket = new + old_nbuckets; bucket < vec_end (new); ++bucket)
    {
      clib_memset (bucket->elts, 0xff, sizeof (bucket->elts));
    }
  /*
   * this for loop manipulates the new (unseen) memory, so no locks
   * are required here
   */
  uword old_bucket_idx;
  for (old_bucket_idx = 0; old_bucket_idx < old_nbuckets; ++old_bucket_idx)
    {
      /* items in old bucket might be moved to new bucket */
      uword new_bucket_idx = old_bucket_idx + old_nbuckets;
      CVT (clib_cuckoo_bucket) * old_bucket = new + old_bucket_idx;
      CVT (clib_cuckoo_bucket) * new_bucket = new + new_bucket_idx;
      int i = 0;
      int moved = 0;
      clib_cuckoo_bucket_aux_t aux = old_bucket->aux;
      for (i = 0; i < clib_cuckoo_bucket_aux_get_use_count (aux); ++i)
	{
	  CVT (clib_cuckoo_kv) * elt = old_bucket->elts + i;
	  u64 hash = CV (clib_cuckoo_hash) (elt);
	  clib_cuckoo_lookup_info_t old_lookup =
	    CV (clib_cuckoo_calc_lookup) (old, hash);
	  clib_cuckoo_lookup_info_t new_lookup =
	    CV (clib_cuckoo_calc_lookup) (new, hash);
	  if ((old_bucket_idx == old_lookup.bucket1 &&
	       new_bucket_idx == new_lookup.bucket1) ||
	      (old_bucket_idx == old_lookup.bucket2 &&
	       new_bucket_idx == new_lookup.bucket2))
	    {
	      /* move the item to new bucket */
	      CVT (clib_cuckoo_kv) * empty_elt = new_bucket->elts + moved;
	      ASSERT (empty_elt);
	      CV (clib_cuckoo_set_locked_elt)
		(new_bucket, empty_elt, elt, old_bucket->reduced_hashes[i]);
	      CV (clib_cuckoo_free_locked_elt) (elt);
	      ++moved;
	    }
	}
      if (moved)
	{
	  CV (clib_cuckoo_bucket_tidy) (old_bucket);
	  aux =
	    clib_cuckoo_bucket_aux_set_use_count (aux,
						  clib_cuckoo_bucket_aux_get_use_count
						  (aux) - moved);
	  old_bucket->aux = aux;
	  aux = new_bucket->aux;
	  aux =
	    clib_cuckoo_bucket_aux_set_use_count (aux,
						  clib_cuckoo_bucket_aux_get_use_count
						  (aux) + moved);
	  new_bucket->aux = aux;
	}
    }
  h->buckets = new;
#if CLIB_CUCKOO_DEBUG_COUNTERS
  ++h->rehashes;
#endif
  h->garbage_callback (h, h->garbage_ctx);
}

static int CV (clib_cuckoo_bucket_search_internal) (CVT (clib_cuckoo) * h,
						    uword bucket,
						    CVT (clib_cuckoo_kv) *
						    kvp,
						    CVT (clib_cuckoo_kv) *
						    *found)
{
  CVT (clib_cuckoo_bucket) * b = CV (clib_cuckoo_bucket_at_index) (h, bucket);
  int i;
  /* *INDENT-OFF* */
  clib_cuckoo_bucket_foreach_idx_unrolled (i, {
    CVT (clib_cuckoo_kv) *elt = &b->elts[i];
    if (CV (clib_cuckoo_key_compare) (elt->key, kvp->key))
      {
        *found = elt;
        return CLIB_CUCKOO_ERROR_SUCCESS;
      }
  });
  /* *INDENT-ON* */
  return CLIB_CUCKOO_ERROR_NOT_FOUND;
}

int CV (clib_cuckoo_add_del) (CVT (clib_cuckoo) * h,
			      CVT (clib_cuckoo_kv) * kvp, int is_add)
{
  CLIB_CUCKOO_DBG ("%s %U", is_add ? "Add" : "Del", CV (format_cuckoo_kvp),
		   kvp);
  clib_cuckoo_lookup_info_t lookup;
  u64 hash = CV (clib_cuckoo_hash) (kvp);
  clib_spinlock_lock (&h->writer_lock);
  u8 reduced_hash = clib_cuckoo_reduce_hash (hash);
restart:
  lookup = CV (clib_cuckoo_calc_lookup) (h->buckets, hash);
  CVT (clib_cuckoo_bucket) * b =
    CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket1);
  CVT (clib_cuckoo_kv) * found;
  int rv =
    CV (clib_cuckoo_bucket_search_internal) (h, lookup.bucket1, kvp, &found);
  if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
    {
      ASSERT (CLIB_CUCKOO_ERROR_NOT_FOUND == rv);
      b = CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket2);
      rv = CV (clib_cuckoo_bucket_search_internal) (h, lookup.bucket2, kvp,
						    &found);
    }
  if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
    {
      if (is_add)
	{
	  /* prevent readers reading this bucket while we switch the values */
	  clib_cuckoo_bucket_aux_t aux =
	    CV (clib_cuckoo_bucket_version_bump_and_lock) (b);
	  clib_memcpy (&found->value, &kvp->value, sizeof (found->value));
	  CLIB_CUCKOO_DBG ("Replaced existing %U", CV (format_cuckoo_elt),
			   found, b->reduced_hashes[found - b->elts]);
	  CV (clib_cuckoo_bucket_unlock) (b, aux);
	}
      else
	{
	  CV (clib_cuckoo_free_elt_in_bucket) (b, found);
	}
      rv = CLIB_CUCKOO_ERROR_SUCCESS;
      CLIB_CUCKOO_DEEP_SELF_CHECK (h);
      goto unlock;
    }
  if (!is_add)
    {
      CLIB_CUCKOO_DBG ("%U not present in table", CV (format_cuckoo_kvp),
		       kvp);
      rv = CLIB_CUCKOO_ERROR_NOT_FOUND;
      goto unlock;
    }
  /* from this point on, it's add code only */
  ASSERT (CLIB_CUCKOO_ERROR_NOT_FOUND == rv);
  /* fast path: try to search for unoccupied slot in one of the buckets */
  rv = CV (clib_cuckoo_add_fast) (h, &lookup, kvp, reduced_hash);
  CLIB_CUCKOO_DEEP_SELF_CHECK (h);
  if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
    {
    CLIB_CUCKOO_DBG ("Fast insert failed, bucket 1: %wu, bucket 2: %wu\n%U%U", aux.bucket1, aux.bucket2, CV (format_cuckoo_bucket), CV (clib_cuckoo_bucindent: Standaindent: Standard input: 903: Error: Unmatched 'else' rd input: 865: Error:Unmatched 'else' ket_at_index) (h, aux.bucket1),
		       CV (format_cuckoo_bucket),
		       CV (clib_cuckoo_bucket_at_index) (h, aux.bucket2));
      /* slow path */
      rv = CV (clib_cuckoo_add_slow) (h, kvp, &lookup, reduced_hash);
      CLIB_CUCKOO_DEEP_SELF_CHECK (h);
      if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
	{
	  CLIB_CUCKOO_DBG ("Slow insert failed, rehash required:\n%U",
			   CV (format_cuckoo), h, 1);
	  /* ultra slow path */
	  CV (clib_cuckoo_rehash) (h);
	  CLIB_CUCKOO_DEEP_SELF_CHECK (h);
	  CLIB_CUCKOO_DBG ("Restarting add after rehash...");
	  goto restart;
	}
    }
unlock:
  clib_spinlock_unlock (&h->writer_lock);
  return rv;
}

u8 *CV (format_cuckoo) (u8 * s, va_list * args)
{
  CVT (clib_cuckoo) * h = va_arg (*args, CVT (clib_cuckoo) *);
  int verbose = va_arg (*args, int);

  s = format (s, "Hash table %s\n", h->name ? h->name : "(unnamed)");

  uword free = 0;
  uword used = 0;
  uword use_count_total = 0;
  float load_factor;
  CVT (clib_cuckoo_bucket) * b;
  /* *INDENT-OFF* */
  clib_cuckoo_foreach_bucket (b, h, {
    if (verbose)
      {
        s = format (s, "%U", CV (format_cuckoo_bucket), b);
      }
    int i;
    clib_cuckoo_bucket_foreach_idx (i)
    {
      CVT (clib_cuckoo_kv) *elt = &b->elts[i];
      if (CV (clib_cuckoo_kv_is_free) (elt))
        {
          ++free;
        }
      else
        {
          ++used;
        }
    }
    clib_cuckoo_bucket_aux_t aux = b->aux;
    use_count_total += clib_cuckoo_bucket_aux_get_use_count (aux);
  });
  /* *INDENT-ON* */
  s = format (s, "Used slots: %wu\n", used);
  s = format (s, "Use count total: %wu\n", use_count_total);
  s = format (s, "Free slots: %wu\n", free);
  if (free + used != 0)
    load_factor = ((float) used) / ((float) (free + used));
  else
    load_factor = 0.0;
  s = format (s, "Load factor: %.2f\n", load_factor);
#if CLIB_CUCKOO_DEBUG_COUNTERS
  s = format (s, "BFS attempts limited by max steps: %lld\n",
	      h->steps_exceeded);
  s = format (s, "BFS cutoffs due to empty queue: %lld\n",
	      h->bfs_queue_emptied);
  s = format (s, "Fast adds: %lld\n", h->fast_adds);
  s = format (s, "Slow adds: %lld\n", h->slow_adds);
  s = format (s, "Rehashes: %lld\n", h->rehashes);
#endif
  return s;
}

float CV (clib_cuckoo_calculate_load_factor) (CVT (clib_cuckoo) * h)
{
  uword nonfree = 0;
  uword all = 0;
  CVT (clib_cuckoo_bucket) * bucket;
  /* *INDENT-OFF* */
  clib_cuckoo_foreach_bucket (bucket, h, {
    int i;
    clib_cuckoo_bucket_foreach_idx (i)
    {
      CVT (clib_cuckoo_kv) *elt = bucket->elts + i;
      ++all;
      if (!CV (clib_cuckoo_kv_is_free) (elt))
        {
          ++nonfree;
        }
    }
  });
  /* *INDENT-ON* */
  if (all)
    return (float) nonfree / (float) all;
  else
    return 0.0;
}

/** @endcond */

/*
 * fd.io coding-style-patch-verification: ON
 *
 * Local Variables:
 * eval: (c-set-style "gnu")
 * End:
 */
