summaryrefslogtreecommitdiffstats
path: root/src/vppinfra/sparse_vec.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/vppinfra/sparse_vec.h')
-rw-r--r--src/vppinfra/sparse_vec.h244
1 files changed, 244 insertions, 0 deletions
diff --git a/src/vppinfra/sparse_vec.h b/src/vppinfra/sparse_vec.h
new file mode 100644
index 00000000000..ec8f0a1c4bf
--- /dev/null
+++ b/src/vppinfra/sparse_vec.h
@@ -0,0 +1,244 @@
+/*
+ * Copyright (c) 2015 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.
+ */
+/*
+ Copyright (c) 2005 Eliot Dresselhaus
+
+ Permission is hereby granted, free of charge, to any person obtaining
+ a copy of this software and associated documentation files (the
+ "Software"), to deal in the Software without restriction, including
+ without limitation the rights to use, copy, modify, merge, publish,
+ distribute, sublicense, and/or sell copies of the Software, and to
+ permit persons to whom the Software is furnished to do so, subject to
+ the following conditions:
+
+ The above copyright notice and this permission notice shall be
+ included in all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+ LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+ OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+ WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+*/
+
+#ifndef included_sparse_vec_h
+#define included_sparse_vec_h
+
+#include <vppinfra/vec.h>
+#include <vppinfra/bitops.h>
+
+/* Sparsely indexed vectors. Basic idea taken from Hacker's delight.
+ Eliot added ranges. */
+typedef struct
+{
+ /* Bitmap one for each sparse index. */
+ uword *is_member_bitmap;
+
+ /* member_counts[i] = total number of members with j < i. */
+ u16 *member_counts;
+
+#define SPARSE_VEC_IS_RANGE (1 << 0)
+#define SPARSE_VEC_IS_VALID_RANGE (1 << 1)
+ u8 *range_flags;
+} sparse_vec_header_t;
+
+always_inline sparse_vec_header_t *
+sparse_vec_header (void *v)
+{
+ return vec_header (v, sizeof (sparse_vec_header_t));
+}
+
+/* Index 0 is always used to mark indices that are not valid in
+ sparse vector. For example, you look up V[0x1234] and 0x1234 is not
+ known you'll get 0 back as an index. */
+#define SPARSE_VEC_INVALID_INDEX (0)
+
+always_inline void *
+sparse_vec_new (uword elt_bytes, uword sparse_index_bits)
+{
+ void *v;
+ sparse_vec_header_t *h;
+ word n;
+
+ ASSERT (sparse_index_bits <= 16);
+
+ v = _vec_resize (0,
+ /* length increment */ 8,
+ /* data bytes */ 8 * elt_bytes,
+ /* header bytes */ sizeof (h[0]),
+ /* data align */ 0);
+
+ /* Make space for invalid entry (entry 0). */
+ _vec_len (v) = 1;
+
+ h = sparse_vec_header (v);
+
+ n = sparse_index_bits - min_log2 (BITS (uword));
+ if (n < 0)
+ n = 0;
+ n = 1ULL << n;
+ vec_resize (h->is_member_bitmap, n);
+ vec_resize (h->member_counts, n);
+
+ return v;
+}
+
+always_inline uword
+sparse_vec_index_internal (void *v,
+ uword sparse_index,
+ uword maybe_range, u32 * insert)
+{
+ sparse_vec_header_t *h;
+ uword i, b, d, w;
+ u8 is_member;
+
+ 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]));
+
+ 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;
+ if (maybe_range)
+ {
+ u8 r = h->range_flags[d];
+ u8 is_range, is_valid_range;
+
+ is_range = maybe_range & (r & SPARSE_VEC_IS_RANGE);
+ is_valid_range = (r & SPARSE_VEC_IS_VALID_RANGE) != 0;
+
+ is_member = is_range ? is_valid_range : is_member;
+ }
+
+ if (insert)
+ {
+ *insert = !is_member;
+ if (!is_member)
+ {
+ uword j;
+ w |= b;
+ h->is_member_bitmap[i] = w;
+ for (j = i + 1; j < vec_len (h->member_counts); j++)
+ h->member_counts[j] += 1;
+ }
+
+ return 1 + d;
+ }
+
+ d = is_member ? d : 0;
+
+ return is_member + d;
+}
+
+always_inline uword
+sparse_vec_index (void *v, uword sparse_index)
+{
+ return sparse_vec_index_internal (v, sparse_index,
+ /* maybe range */ 0,
+ /* insert? */ 0);
+}
+
+always_inline void
+sparse_vec_index2 (void *v,
+ u32 si0, u32 si1, u32 * i0_return, u32 * i1_return)
+{
+ sparse_vec_header_t *h;
+ uword b0, b1, w0, w1, v0, v1;
+ u32 i0, i1, d0, d1;
+ u8 is_member0, is_member1;
+
+ h = sparse_vec_header (v);
+
+ 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]));
+
+ ASSERT (i0 < vec_len (h->is_member_bitmap));
+ ASSERT (i1 < vec_len (h->is_member_bitmap));
+
+ ASSERT (i0 < vec_len (h->member_counts));
+ ASSERT (i1 < vec_len (h->member_counts));
+
+ w0 = h->is_member_bitmap[i0];
+ w1 = h->is_member_bitmap[i1];
+
+ v0 = w0 & (b0 - 1);
+ v1 = w1 & (b1 - 1);
+
+ /* Speculate that masks will have zero or one bits set. */
+ d0 = h->member_counts[i0] + (v0 != 0);
+ d1 = h->member_counts[i1] + (v1 != 0);
+
+ /* Validate speculation. */
+ if (PREDICT_FALSE (!is_pow2 (v0) || !is_pow2 (v1)))
+ {
+ d0 += count_set_bits (v0) - (v0 != 0);
+ d1 += count_set_bits (v1) - (v1 != 0);
+ }
+
+ is_member0 = (w0 & b0) != 0;
+ is_member1 = (w1 & b1) != 0;
+
+ d0 = is_member0 ? d0 : 0;
+ d1 = is_member1 ? d1 : 0;
+
+ *i0_return = is_member0 + d0;
+ *i1_return = is_member1 + d1;
+}
+
+#define sparse_vec_free(v) vec_free(v)
+
+#define sparse_vec_elt_at_index(v,i) \
+ vec_elt_at_index ((v), sparse_vec_index ((v), (i)))
+
+#define sparse_vec_validate(v,i) \
+({ \
+ uword _i; \
+ u32 _insert; \
+ \
+ if (! (v)) \
+ (v) = sparse_vec_new (sizeof ((v)[0]), BITS (u16)); \
+ \
+ _i = sparse_vec_index_internal ((v), (i), \
+ /* maybe range */ 0, \
+ /* insert? */ &_insert); \
+ if (_insert) \
+ vec_insert_ha ((v), 1, _i, \
+ /* header size */ sizeof (sparse_vec_header_t), \
+ /* align */ 0); \
+ \
+ /* Invalid index is 0. */ \
+ ASSERT (_i > 0); \
+ \
+ (v) + _i; \
+})
+
+#endif /* included_sparse_vec_h */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */