vppinfra/vppinfra/slist.h

   1 /*
   2   Copyright (c) 2012 Cisco and/or its affiliates.
   3
   4   * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15 */
  16
  17 #ifndef included_slist_h
  18 #define included_slist_h
  19
  20 #include <stdarg.h>
  21 #include <vppinfra/clib.h>
  22 #include <vppinfra/vec.h>
  23 #include <vppinfra/pool.h>
  24 #include <vppinfra/error.h>
  25 #include <vppinfra/format.h>
  26 #include <vppinfra/cache.h>
  27
  28 typedef word (clib_slist_key_compare_function_t)
  29   (void *key, u32 elt_pool_index);
  30
  31 typedef enum
  32 {
  33   CLIB_SLIST_MATCH = 0,
  34   CLIB_SLIST_NO_MATCH
  35 } clib_slist_search_result_t;
  36
  37 typedef struct
  38 {
  39   /* Vector of next elements. Every valid instance has at least one */
  40   union
  41   {
  42     u32 next0[2];
  43     u32 *nexts;
  44   } n;
  45
  46   /* Index of item in user's pool */
  47   u32 user_pool_index;
  48   /* $$$ pad to even divisor of cache line */
  49 } clib_slist_elt_t;
  50
  51 static inline u32
  52 clib_slist_get_next_at_level (clib_slist_elt_t * elt, int level)
  53 {
  54   if (elt->n.next0[0] & 1)
  55     {
  56       ASSERT (level < 2);
  57       if (level == 1)
  58         return elt->n.next0[1];
  59       /* preserve ~0 (end of list) */
  60       return (elt->n.next0[0] == (u32) ~ 0) ? elt->n.next0[0] :
  61         (elt->n.next0[0] >> 1);
  62     }
  63   else
  64     {
  65       ASSERT (level < vec_len (elt->n.nexts));
  66       return elt->n.nexts[level];
  67     }
  68 }
  69
  70 static inline void
  71 clib_slist_set_next_at_level (clib_slist_elt_t * elt, u32 index, int level)
  72 {
  73   u32 old_level0_value[2];
  74   /* level0 and not a vector */
  75   if (level < 2 && (elt->n.next0[0] == 0 || elt->n.next0[0] & 1))
  76     {
  77       if (level == 0)
  78         {
  79           elt->n.next0[0] = (index << 1) | 1;
  80           return;
  81         }
  82       elt->n.next0[1] = index;
  83       return;
  84     }
  85   /* have to save old level0 values? */
  86   if (elt->n.next0[0] & 1)
  87     {
  88       old_level0_value[0] = (elt->n.next0[0] == (u32) ~ 0) ?
  89         elt->n.next0[0] : elt->n.next0[0] >> 1;
  90       old_level0_value[1] = elt->n.next0[1];
  91       elt->n.nexts = 0;
  92       vec_add1 (elt->n.nexts, old_level0_value[0]);
  93       vec_add1 (elt->n.nexts, old_level0_value[1]);
  94     }
  95   vec_validate (elt->n.nexts, level);
  96   elt->n.nexts[level] = index;
  97 }
  98
  99
 100 typedef struct
 101 {
 102   /* pool of skip-list elements */
 103   clib_slist_elt_t *elts;
 104
 105   /* last search path */
 106   u32 *path;
 107
 108   /* last search number of compares */
 109   u32 ncompares;
 110
 111   /* occupancy stats */
 112   u32 *occupancy;
 113
 114   /* Comparison function */
 115   clib_slist_key_compare_function_t *compare;
 116
 117   /* Format function */
 118   format_function_t *format_user_element;
 119
 120   /* items appear in successive plies with Pr (1 / branching_factor) */
 121   f64 branching_factor;
 122
 123   /* random seed */
 124   u32 seed;
 125 } clib_slist_t;
 126
 127 clib_error_t *clib_slist_init (clib_slist_t * sp, f64 branching_factor,
 128                                clib_slist_key_compare_function_t compare,
 129                                format_function_t format_user_element);
 130
 131 format_function_t format_slist;
 132
 133 void clib_slist_add (clib_slist_t * sp, void *key, u32 user_pool_index);
 134 clib_slist_search_result_t clib_slist_del (clib_slist_t * sp, void *key);
 135 u32 clib_slist_search (clib_slist_t * sp, void *key, u32 * ncompares);
 136
 137 #endif /* included_slist_h */
 138
 139 /*
 140  * fd.io coding-style-patch-verification: ON
 141  *
 142  * Local Variables:
 143  * eval: (c-set-style "gnu")
 144  * End:
 145  */