#ifndef included_sparse_vec_h
#define included_sparse_vec_h
+#include <vppinfra/clib.h>
#include <vppinfra/vec.h>
-#include <vppinfra/bitops.h>
/* Sparsely indexed vectors. Basic idea taken from Hacker's delight.
Eliot added ranges. */
always_inline sparse_vec_header_t *
sparse_vec_header (void *v)
{
- return vec_header (v, sizeof (sparse_vec_header_t));
+ return vec_header (v);
}
/* Index 0 is always used to mark indices that are not valid in
void *v;
sparse_vec_header_t *h;
word n;
+ vec_attr_t va = { .elt_sz = elt_bytes, .hdr_sz = sizeof (h[0]) };
ASSERT (sparse_index_bits <= 16);
- v = _vec_resize ((void *) 0,
- /* length increment */ 8,
- /* data bytes */ 8 * elt_bytes,
- /* header bytes */ sizeof (h[0]),
- /* data align */ 0);
+ v = _vec_alloc_internal (/* data bytes */ 8, &va);
/* Make space for invalid entry (entry 0). */
- _vec_len (v) = 1;
+ _vec_set_len (v, 1, elt_bytes);
h = sparse_vec_header (v);
h = sparse_vec_header (v);
i = sparse_index / BITS (h->is_member_bitmap[0]);
- b = (uword) 1 << (uword) (sparse_index % BITS (h->is_member_bitmap[0]));
+ b = sparse_index % BITS (h->is_member_bitmap[0]);
ASSERT (i < vec_len (h->is_member_bitmap));
ASSERT (i < vec_len (h->member_counts));
w = h->is_member_bitmap[i];
- d = h->member_counts[i] + count_set_bits (w & (b - 1));
- is_member = (w & b) != 0;
+ /* count_trailing_zeros(0) == 0, take care of that case */
+ if (PREDICT_FALSE (maybe_range == 0 && insert == 0 && w == 0))
+ return 0;
+
+ if (PREDICT_TRUE (maybe_range == 0 && insert == 0 &&
+ count_trailing_zeros (w) == b))
+ return h->member_counts[i] + 1;
+
+ d = h->member_counts[i] + count_set_bits (w & ((1ULL << b) - 1));
+ is_member = (w & (1ULL << b)) != 0;
+
if (maybe_range)
{
u8 r = h->range_flags[d];
if (!is_member)
{
uword j;
- w |= b;
+ w |= 1ULL << b;
h->is_member_bitmap[i] = w;
for (j = i + 1; j < vec_len (h->member_counts); j++)
h->member_counts[j] += 1;
i0 = si0 / BITS (h->is_member_bitmap[0]);
i1 = si1 / BITS (h->is_member_bitmap[0]);
- b0 = (uword) 1 << (uword) (si0 % BITS (h->is_member_bitmap[0]));
- b1 = (uword) 1 << (uword) (si1 % BITS (h->is_member_bitmap[0]));
+ b0 = si0 % BITS (h->is_member_bitmap[0]);
+ b1 = si1 % BITS (h->is_member_bitmap[0]);
ASSERT (i0 < vec_len (h->is_member_bitmap));
ASSERT (i1 < vec_len (h->is_member_bitmap));
w0 = h->is_member_bitmap[i0];
w1 = h->is_member_bitmap[i1];
- v0 = w0 & (b0 - 1);
- v1 = w1 & (b1 - 1);
+ if (PREDICT_TRUE ((count_trailing_zeros (w0) == b0) +
+ (count_trailing_zeros (w1) == b1) == 2))
+ {
+ *i0_return = h->member_counts[i0] + 1;
+ *i1_return = h->member_counts[i1] + 1;
+ return;
+ }
+
+ v0 = w0 & ((1ULL << b0) - 1);
+ v1 = w1 & ((1ULL << b1) - 1);
/* Speculate that masks will have zero or one bits set. */
d0 = h->member_counts[i0] + (v0 != 0);
d1 += count_set_bits (v1) - (v1 != 0);
}
- is_member0 = (w0 & b0) != 0;
- is_member1 = (w1 & b1) != 0;
+ is_member0 = (w0 & (1ULL << b0)) != 0;
+ is_member1 = (w1 & (1ULL << b1)) != 0;
d0 = is_member0 ? d0 : 0;
d1 = is_member1 ? d1 : 0;
*i1_return = is_member1 + d1;
}
-#define sparse_vec_free(v) vec_free(v)
+#define sparse_vec_free(V) \
+ do \
+ { \
+ if (V) \
+ { \
+ sparse_vec_header_t *_h = sparse_vec_header (V); \
+ vec_free (_h->is_member_bitmap); \
+ vec_free (_h->member_counts); \
+ clib_mem_free (_h); \
+ V = 0; \
+ } \
+ } \
+ while (0)
#define sparse_vec_elt_at_index(v,i) \
vec_elt_at_index ((v), sparse_vec_index ((v), (i)))