1 files changed, 146 insertions, 134 deletions

diff --git a/vppinfra/vppinfra/slist.c b/vppinfra/vppinfra/slist.c
index 435a026a462..892517bbb79 100644
--- a/vppinfra/vppinfra/slist.c
+++ b/vppinfra/vppinfra/slist.c
@@ -27,8 +27,8 @@
  * is always on the "level-0" list. Since most elements are *only* on
  * level 0, we keep the level 0 (and level 1) in the element. For those
  * elements on more than two lists, we switch to a vector. Hence, the
- * "n" union in slib_slist_elt_t. 
- * 
+ * "n" union in slib_slist_elt_t.
+ *
  * The low-order bit of elt->n.next0[0] is 1 for inlined next indices,
  * 0 for vector indices (since the allocator always aligns to at least
  * a 4-byte boundary). We can only represent 2e9 items, but since the
@@ -41,7 +41,7 @@
  * User code is in charge of comparing a supplied key with
  * the key component of a user pool element. The user tells this code
  * to add or delete (opaque key, 32-bit integer) pairs to the skip-list.
- * 
+ *
  * The algorithm adds new elements to one or more lists.
  * For levels greater than zero, the probability of a new element landing on
  * a list is branching_factor**N. Branching_factor = 0.2 seems to work
@@ -49,9 +49,9 @@
  */
 
 clib_error_t *
-clib_slist_init (clib_slist_t *sp, f64 branching_factor, 
-                 clib_slist_key_compare_function_t compare,
-                 format_function_t format_user_element)
+clib_slist_init (clib_slist_t * sp, f64 branching_factor,
+		 clib_slist_key_compare_function_t compare,
+		 format_function_t format_user_element)
 {
   clib_slist_elt_t *head;
   memset (sp, 0, sizeof (sp[0]));
@@ -60,8 +60,8 @@ clib_slist_init (clib_slist_t *sp, f64 branching_factor,
   sp->compare = compare;
   sp->seed = 0xdeaddabe;
   pool_get (sp->elts, head);
-  vec_add1 (head->n.nexts, (u32)~0);
-  head->user_pool_index = (u32)~0;
+  vec_add1 (head->n.nexts, (u32) ~ 0);
+  head->user_pool_index = (u32) ~ 0;
   vec_validate (sp->path, 1);
   vec_validate (sp->occupancy, 0);
 
@@ -72,23 +72,23 @@ clib_slist_init (clib_slist_t *sp, f64 branching_factor,
  * slist_search_internal
  */
 static inline clib_slist_search_result_t
-slist_search_internal (clib_slist_t *sp, void *key, int need_full_path)
+slist_search_internal (clib_slist_t * sp, void *key, int need_full_path)
 {
   int level, comp_result;
   clib_slist_elt_t *search_elt, *head_elt;
 
   sp->ncompares = 0;
-  /* 
-   * index 0 is the magic listhead element which is 
+  /*
+   * index 0 is the magic listhead element which is
    * lexically lighter than / to the left of every element
    */
-  search_elt = head_elt =  pool_elt_at_index (sp->elts, 0);
+  search_elt = head_elt = pool_elt_at_index (sp->elts, 0);
 
-  /* 
+  /*
    * Initial negotiating position, only the head_elt is
    * lighter than the supplied key
    */
-  memset (sp->path, 0, vec_len(head_elt->n.nexts) * sizeof (u32));
+  memset (sp->path, 0, vec_len (head_elt->n.nexts) * sizeof (u32));
 
   /* Walk the fastest lane first */
   level = vec_len (head_elt->n.nexts) - 1;
@@ -99,226 +99,238 @@ slist_search_internal (clib_slist_t *sp, void *key, int need_full_path)
       u32 next_index_this_level;
       clib_slist_elt_t *prefetch_elt;
 
-      /* 
+      /*
        * Prefetching the next element at this level makes a measurable
        * difference, but doesn't fix the dependent read stall problem
        */
-      prefetch_elt = sp->elts + 
-        clib_slist_get_next_at_level (search_elt, level);
+      prefetch_elt = sp->elts +
+	clib_slist_get_next_at_level (search_elt, level);
 
-      CLIB_PREFETCH(prefetch_elt, CLIB_CACHE_LINE_BYTES, READ);
+      CLIB_PREFETCH (prefetch_elt, CLIB_CACHE_LINE_BYTES, READ);
 
       /* Compare the key with the current element */
       comp_result = (search_elt == head_elt) ? 1 :
-        sp->compare (key, search_elt->user_pool_index);
+	sp->compare (key, search_elt->user_pool_index);
 
       sp->ncompares++;
       /* key "lighter" than this element */
-      if (comp_result < 0) 
-        {
-          /* 
-           * Back up to previous item on this list 
-           * and search the next finer-grained list
-           * starting there.
-           */
-          search_elt = pool_elt_at_index (sp->elts, sp->path [level]);
-        next_list:
-          if (level > 0)
-            {
-              level--;
-              continue;
-            }
-          else
-            {
-              return CLIB_SLIST_NO_MATCH;
-            }
-        } 
+      if (comp_result < 0)
+	{
+	  /*
+	   * Back up to previous item on this list
+	   * and search the next finer-grained list
+	   * starting there.
+	   */
+	  search_elt = pool_elt_at_index (sp->elts, sp->path[level]);
+	next_list:
+	  if (level > 0)
+	    {
+	      level--;
+	      continue;
+	    }
+	  else
+	    {
+	      return CLIB_SLIST_NO_MATCH;
+	    }
+	}
       /* Match */
-      if (comp_result == 0) 
-        {
-          /* 
-           * If we're trying to delete an element, we need to
-           * track down all of the elements which point at it.
-           * Otherwise, don't bother with it
-           */
-          if (need_full_path && level > 0)
-            {
-              search_elt = pool_elt_at_index (sp->elts, sp->path [level]);
-              level--;
-              continue;
-            }
-          level = vec_len(head_elt->n.nexts);
-          sp->path[level] = search_elt - sp->elts;
-          _vec_len (sp->path) = level + 1;
-          return CLIB_SLIST_MATCH;
-        }
-      /* 
+      if (comp_result == 0)
+	{
+	  /*
+	   * If we're trying to delete an element, we need to
+	   * track down all of the elements which point at it.
+	   * Otherwise, don't bother with it
+	   */
+	  if (need_full_path && level > 0)
+	    {
+	      search_elt = pool_elt_at_index (sp->elts, sp->path[level]);
+	      level--;
+	      continue;
+	    }
+	  level = vec_len (head_elt->n.nexts);
+	  sp->path[level] = search_elt - sp->elts;
+	  _vec_len (sp->path) = level + 1;
+	  return CLIB_SLIST_MATCH;
+	}
+      /*
        * comp_result positive, key is to the right of
        * this element
-       */ 
+       */
       sp->path[level] = search_elt - sp->elts;
 
       /* Out of list at this level? */
-      next_index_this_level = clib_slist_get_next_at_level (search_elt, level);
-      if (next_index_this_level == (u32)~0) 
-        goto next_list;
+      next_index_this_level =
+	clib_slist_get_next_at_level (search_elt, level);
+      if (next_index_this_level == (u32) ~ 0)
+	goto next_list;
 
       /* No, try the next element */
       search_elt = pool_elt_at_index (sp->elts, next_index_this_level);
     }
-  return 0; /* notreached */
+  return 0;			/* notreached */
 }
 
-u32 clib_slist_search (clib_slist_t *sp, void *key, u32 *ncompares)
+u32
+clib_slist_search (clib_slist_t * sp, void *key, u32 * ncompares)
 {
   clib_slist_search_result_t rv;
 
-  rv = slist_search_internal (sp, key, 0 /* dont need full path */);
+  rv = slist_search_internal (sp, key, 0 /* dont need full path */ );
   if (rv == CLIB_SLIST_MATCH)
     {
       clib_slist_elt_t *elt;
-      elt = pool_elt_at_index (sp->elts, sp->path[vec_len(sp->path)-1]);
+      elt = pool_elt_at_index (sp->elts, sp->path[vec_len (sp->path) - 1]);
       if (ncompares)
-        *ncompares = sp->ncompares;
+	*ncompares = sp->ncompares;
       return elt->user_pool_index;
     }
-  return (u32)~0;
+  return (u32) ~ 0;
 }
 
-void clib_slist_add (clib_slist_t *sp, void *key, u32 user_pool_index)
+void
+clib_slist_add (clib_slist_t * sp, void *key, u32 user_pool_index)
 {
   clib_slist_elt_t *new_elt;
   clib_slist_search_result_t search_result;
   int level;
 
-  search_result = slist_search_internal (sp, key, 
-                                         0 /* don't need full path */);
+  search_result = slist_search_internal (sp, key,
+					 0 /* don't need full path */ );
 
   /* Special case: key exists, just replace user_pool_index */
-  if (PREDICT_FALSE(search_result == CLIB_SLIST_MATCH))
+  if (PREDICT_FALSE (search_result == CLIB_SLIST_MATCH))
     {
       clib_slist_elt_t *elt;
       elt = pool_elt_at_index (sp->elts, sp->path[0]);
       elt->user_pool_index = user_pool_index;
       return;
     }
-    
+
   pool_get (sp->elts, new_elt);
   new_elt->n.nexts = 0;
   new_elt->user_pool_index = user_pool_index;
 
   /* sp->path lists elements to the left of key, by level */
-  for (level = 0; level < vec_len(sp->path); level++)
+  for (level = 0; level < vec_len (sp->path); level++)
     {
       clib_slist_elt_t *prev_elt_this_level;
       u32 prev_elt_next_index_this_level;
 
       /* Add to list at the current level */
       prev_elt_this_level = pool_elt_at_index (sp->elts, sp->path[level]);
-      prev_elt_next_index_this_level = clib_slist_get_next_at_level 
-        (prev_elt_this_level, level);
-                                                                 
-      clib_slist_set_next_at_level (new_elt, prev_elt_next_index_this_level, 
-                                    level);
+      prev_elt_next_index_this_level = clib_slist_get_next_at_level
+	(prev_elt_this_level, level);
+
+      clib_slist_set_next_at_level (new_elt, prev_elt_next_index_this_level,
+				    level);
 
       clib_slist_set_next_at_level (prev_elt_this_level, new_elt - sp->elts,
-                                    level);
+				    level);
       sp->occupancy[level]++;
-      
+
       /* Randomly add to the next-higher level */
       if (random_f64 (&sp->seed) > sp->branching_factor)
-        break;
+	break;
     }
-    {
+  {
     /* Time to add a new ply? */
-      clib_slist_elt_t *head_elt = pool_elt_at_index (sp->elts, 0);
-      int top_level = vec_len(head_elt->n.nexts) - 1;
-      if (((f64)sp->occupancy[top_level]) * sp->branching_factor > 1.0)
-        {
-          vec_add1 (sp->occupancy, 0);
-          vec_add1 (head_elt->n.nexts, (u32)~0);
-          /* full match case returns n+1 items */
-          vec_validate (sp->path, vec_len(head_elt->n.nexts));
-        }
-    }
+    clib_slist_elt_t *head_elt = pool_elt_at_index (sp->elts, 0);
+    int top_level = vec_len (head_elt->n.nexts) - 1;
+    if (((f64) sp->occupancy[top_level]) * sp->branching_factor > 1.0)
+      {
+	vec_add1 (sp->occupancy, 0);
+	vec_add1 (head_elt->n.nexts, (u32) ~ 0);
+	/* full match case returns n+1 items */
+	vec_validate (sp->path, vec_len (head_elt->n.nexts));
+      }
+  }
 }
 
 clib_slist_search_result_t
-clib_slist_del (clib_slist_t *sp, void *key)
+clib_slist_del (clib_slist_t * sp, void *key)
 {
   clib_slist_search_result_t search_result;
   clib_slist_elt_t *del_elt;
   int level;
-  
-  search_result = slist_search_internal (sp, key, 1 /* need full path */);
 
-  if (PREDICT_FALSE(search_result == CLIB_SLIST_NO_MATCH))
+  search_result = slist_search_internal (sp, key, 1 /* need full path */ );
+
+  if (PREDICT_FALSE (search_result == CLIB_SLIST_NO_MATCH))
     return search_result;
 
-  del_elt = pool_elt_at_index (sp->elts, sp->path[vec_len(sp->path)-1]);
-  ASSERT(vec_len(sp->path) > 1);
-  
-  for (level = 0; level < vec_len (sp->path)-1; level++)
+  del_elt = pool_elt_at_index (sp->elts, sp->path[vec_len (sp->path) - 1]);
+  ASSERT (vec_len (sp->path) > 1);
+
+  for (level = 0; level < vec_len (sp->path) - 1; level++)
     {
       clib_slist_elt_t *path_elt;
       u32 path_elt_next_index;
-      
+
       path_elt = pool_elt_at_index (sp->elts, sp->path[level]);
       path_elt_next_index = clib_slist_get_next_at_level (path_elt, level);
-      
+
       /* Splice the item out of the list if it's adjacent to the victim */
       if (path_elt_next_index == del_elt - sp->elts)
-        {
-          sp->occupancy[level]--;
-          path_elt_next_index = clib_slist_get_next_at_level (del_elt, level);
-          clib_slist_set_next_at_level (path_elt, path_elt_next_index, level);
-        }
+	{
+	  sp->occupancy[level]--;
+	  path_elt_next_index = clib_slist_get_next_at_level (del_elt, level);
+	  clib_slist_set_next_at_level (path_elt, path_elt_next_index, level);
+	}
     }
 
   /* If this element is on more than two lists it has a vector of nexts */
-  if (! (del_elt->n.next0[0] & 1))
+  if (!(del_elt->n.next0[0] & 1))
     vec_free (del_elt->n.nexts);
   pool_put (sp->elts, del_elt);
   return CLIB_SLIST_MATCH;
 }
 
-u8 * format_slist (u8 * s, va_list *args)
+u8 *
+format_slist (u8 * s, va_list * args)
 {
   clib_slist_t *sl = va_arg (*args, clib_slist_t *);
   int verbose = va_arg (*args, int);
   int i;
   clib_slist_elt_t *head_elt, *elt;
 
-  s = format (s, "slist 0x%x, %u items, branching_factor %.2f\n", sl, 
-              sl->occupancy ? sl->occupancy[0] : 0, sl->branching_factor);
-      
-  if (pool_elts(sl->elts) == 0)
+  s = format (s, "slist 0x%x, %u items, branching_factor %.2f\n", sl,
+	      sl->occupancy ? sl->occupancy[0] : 0, sl->branching_factor);
+
+  if (pool_elts (sl->elts) == 0)
     return s;
-          
+
   head_elt = pool_elt_at_index (sl->elts, 0);
-  
+
   for (i = 0; i < vec_len (head_elt->n.nexts); i++)
     {
-      s = format (s, "level %d: %d elts\n", i, 
-                  sl->occupancy ? sl->occupancy[i] : 0);
-      
-      if (verbose && head_elt->n.nexts[i] != (u32)~0)
-        {
-          elt = pool_elt_at_index (sl->elts, head_elt->n.nexts[i]);
-          while (elt)
-            {
-              u32 next_index;
-              s = format (s, "%U(%d) ", sl->format_user_element, 
-                          elt->user_pool_index, elt - sl->elts);
-              next_index = clib_slist_get_next_at_level (elt, i);
-              ASSERT(next_index != 0x7fffffff);
-              if (next_index == (u32)~0)
-                break;
-              else
-                elt = pool_elt_at_index (sl->elts, next_index);
-            }
-        }
+      s = format (s, "level %d: %d elts\n", i,
+		  sl->occupancy ? sl->occupancy[i] : 0);
+
+      if (verbose && head_elt->n.nexts[i] != (u32) ~ 0)
+	{
+	  elt = pool_elt_at_index (sl->elts, head_elt->n.nexts[i]);
+	  while (elt)
+	    {
+	      u32 next_index;
+	      s = format (s, "%U(%d) ", sl->format_user_element,
+			  elt->user_pool_index, elt - sl->elts);
+	      next_index = clib_slist_get_next_at_level (elt, i);
+	      ASSERT (next_index != 0x7fffffff);
+	      if (next_index == (u32) ~ 0)
+		break;
+	      else
+		elt = pool_elt_at_index (sl->elts, next_index);
+	    }
+	}
       s = format (s, "\n");
     }
   return s;
 }
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */