src/vppinfra/sparse_vec.h

   1 /*
   2  * Copyright (c) 2015 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 /*
  16   Copyright (c) 2005 Eliot Dresselhaus
  17
  18   Permission is hereby granted, free of charge, to any person obtaining
  19   a copy of this software and associated documentation files (the
  20   "Software"), to deal in the Software without restriction, including
  21   without limitation the rights to use, copy, modify, merge, publish,
  22   distribute, sublicense, and/or sell copies of the Software, and to
  23   permit persons to whom the Software is furnished to do so, subject to
  24   the following conditions:
  25
  26   The above copyright notice and this permission notice shall be
  27   included in all copies or substantial portions of the Software.
  28
  29   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  30   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  31   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  32   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  33   LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  34   OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  35   WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  36 */
  37
  38 #ifndef included_sparse_vec_h
  39 #define included_sparse_vec_h
  40
  41 #include <vppinfra/clib.h>
  42 #include <vppinfra/vec.h>
  43
  44 /* Sparsely indexed vectors.  Basic idea taken from Hacker's delight.
  45    Eliot added ranges. */
  46 typedef struct
  47 {
  48   /* Bitmap one for each sparse index. */
  49   uword *is_member_bitmap;
  50
  51   /* member_counts[i] = total number of members with j < i. */
  52   u16 *member_counts;
  53
  54 #define SPARSE_VEC_IS_RANGE (1 << 0)
  55 #define SPARSE_VEC_IS_VALID_RANGE (1 << 1)
  56   u8 *range_flags;
  57 } sparse_vec_header_t;
  58
  59 always_inline sparse_vec_header_t *
  60 sparse_vec_header (void *v)
  61 {
  62   return vec_header (v);
  63 }
  64
  65 /* Index 0 is always used to mark indices that are not valid in
  66    sparse vector.  For example, you look up V[0x1234] and 0x1234 is not
  67    known you'll get 0 back as an index. */
  68 #define SPARSE_VEC_INVALID_INDEX (0)
  69
  70 always_inline void *
  71 sparse_vec_new (uword elt_bytes, uword sparse_index_bits)
  72 {
  73   void *v;
  74   sparse_vec_header_t *h;
  75   word n;
  76
  77   ASSERT (sparse_index_bits <= 16);
  78
  79   v = _vec_realloc (0, /* data bytes */ 8, elt_bytes,
  80                     /* header bytes */ sizeof (h[0]), /* data align */ 0,
  81                     /* heap */ 0);
  82
  83   /* Make space for invalid entry (entry 0). */
  84   _vec_find (v)->len = 1;
  85
  86   h = sparse_vec_header (v);
  87
  88   n = sparse_index_bits - min_log2 (BITS (uword));
  89   if (n < 0)
  90     n = 0;
  91   n = 1ULL << n;
  92   vec_resize (h->is_member_bitmap, n);
  93   vec_resize (h->member_counts, n);
  94
  95   return v;
  96 }
  97
  98 always_inline uword
  99 sparse_vec_index_internal (void *v,
 100                            uword sparse_index,
 101                            uword maybe_range, u32 * insert)
 102 {
 103   sparse_vec_header_t *h;
 104   uword i, b, d, w;
 105   u8 is_member;
 106
 107   h = sparse_vec_header (v);
 108   i = sparse_index / BITS (h->is_member_bitmap[0]);
 109   b = sparse_index % BITS (h->is_member_bitmap[0]);
 110
 111   ASSERT (i < vec_len (h->is_member_bitmap));
 112   ASSERT (i < vec_len (h->member_counts));
 113
 114   w = h->is_member_bitmap[i];
 115
 116   /* count_trailing_zeros(0) == 0, take care of that case */
 117   if (PREDICT_FALSE (maybe_range == 0 && insert == 0 && w == 0))
 118     return 0;
 119
 120   if (PREDICT_TRUE (maybe_range == 0 && insert == 0 &&
 121                     count_trailing_zeros (w) == b))
 122     return h->member_counts[i] + 1;
 123
 124   d = h->member_counts[i] + count_set_bits (w & ((1ULL << b) - 1));
 125   is_member = (w & (1ULL << b)) != 0;
 126
 127   if (maybe_range)
 128     {
 129       u8 r = h->range_flags[d];
 130       u8 is_range, is_valid_range;
 131
 132       is_range = maybe_range & (r & SPARSE_VEC_IS_RANGE);
 133       is_valid_range = (r & SPARSE_VEC_IS_VALID_RANGE) != 0;
 134
 135       is_member = is_range ? is_valid_range : is_member;
 136     }
 137
 138   if (insert)
 139     {
 140       *insert = !is_member;
 141       if (!is_member)
 142         {
 143           uword j;
 144           w |= 1ULL << b;
 145           h->is_member_bitmap[i] = w;
 146           for (j = i + 1; j < vec_len (h->member_counts); j++)
 147             h->member_counts[j] += 1;
 148         }
 149
 150       return 1 + d;
 151     }
 152
 153   d = is_member ? d : 0;
 154
 155   return is_member + d;
 156 }
 157
 158 always_inline uword
 159 sparse_vec_index (void *v, uword sparse_index)
 160 {
 161   return sparse_vec_index_internal (v, sparse_index,
 162                                     /* maybe range */ 0,
 163                                     /* insert? */ 0);
 164 }
 165
 166 always_inline void
 167 sparse_vec_index2 (void *v,
 168                    u32 si0, u32 si1, u32 * i0_return, u32 * i1_return)
 169 {
 170   sparse_vec_header_t *h;
 171   uword b0, b1, w0, w1, v0, v1;
 172   u32 i0, i1, d0, d1;
 173   u8 is_member0, is_member1;
 174
 175   h = sparse_vec_header (v);
 176
 177   i0 = si0 / BITS (h->is_member_bitmap[0]);
 178   i1 = si1 / BITS (h->is_member_bitmap[0]);
 179
 180   b0 = si0 % BITS (h->is_member_bitmap[0]);
 181   b1 = si1 % BITS (h->is_member_bitmap[0]);
 182
 183   ASSERT (i0 < vec_len (h->is_member_bitmap));
 184   ASSERT (i1 < vec_len (h->is_member_bitmap));
 185
 186   ASSERT (i0 < vec_len (h->member_counts));
 187   ASSERT (i1 < vec_len (h->member_counts));
 188
 189   w0 = h->is_member_bitmap[i0];
 190   w1 = h->is_member_bitmap[i1];
 191
 192   if (PREDICT_TRUE ((count_trailing_zeros (w0) == b0) +
 193                     (count_trailing_zeros (w1) == b1) == 2))
 194     {
 195       *i0_return = h->member_counts[i0] + 1;
 196       *i1_return = h->member_counts[i1] + 1;
 197       return;
 198     }
 199
 200   v0 = w0 & ((1ULL << b0) - 1);
 201   v1 = w1 & ((1ULL << b1) - 1);
 202
 203   /* Speculate that masks will have zero or one bits set. */
 204   d0 = h->member_counts[i0] + (v0 != 0);
 205   d1 = h->member_counts[i1] + (v1 != 0);
 206
 207   /* Validate speculation. */
 208   if (PREDICT_FALSE (!is_pow2 (v0) || !is_pow2 (v1)))
 209     {
 210       d0 += count_set_bits (v0) - (v0 != 0);
 211       d1 += count_set_bits (v1) - (v1 != 0);
 212     }
 213
 214   is_member0 = (w0 & (1ULL << b0)) != 0;
 215   is_member1 = (w1 & (1ULL << b1)) != 0;
 216
 217   d0 = is_member0 ? d0 : 0;
 218   d1 = is_member1 ? d1 : 0;
 219
 220   *i0_return = is_member0 + d0;
 221   *i1_return = is_member1 + d1;
 222 }
 223
 224 #define sparse_vec_free(V)                                                    \
 225   do                                                                          \
 226     {                                                                         \
 227       if (V)                                                                  \
 228         {                                                                     \
 229           clib_mem_free (sparse_vec_header (V));                              \
 230           V = 0;                                                              \
 231         }                                                                     \
 232     }                                                                         \
 233   while (0)
 234
 235 #define sparse_vec_elt_at_index(v,i) \
 236   vec_elt_at_index ((v), sparse_vec_index ((v), (i)))
 237
 238 #define sparse_vec_validate(v,i)                                        \
 239 ({                                                                      \
 240   uword _i;                                                             \
 241   u32 _insert;                                                          \
 242                                                                         \
 243   if (! (v))                                                            \
 244     (v) = sparse_vec_new (sizeof ((v)[0]), BITS (u16));                 \
 245                                                                         \
 246   _i = sparse_vec_index_internal ((v), (i),                             \
 247                                   /* maybe range */ 0,                  \
 248                                   /* insert? */ &_insert);              \
 249   if (_insert)                                                          \
 250     vec_insert_ha ((v), 1, _i,                                          \
 251                    /* header size */ sizeof (sparse_vec_header_t),      \
 252                    /* align */ 0);                                      \
 253                                                                         \
 254   /* Invalid index is 0. */                                             \
 255   ASSERT (_i > 0);                                                      \
 256                                                                         \
 257   (v) + _i;                                                             \
 258 })
 259
 260 #endif /* included_sparse_vec_h */
 261
 262 /*
 263  * fd.io coding-style-patch-verification: ON
 264  *
 265  * Local Variables:
 266  * eval: (c-set-style "gnu")
 267  * End:
 268  */