diff options
Diffstat (limited to 'vppinfra/vppinfra/sparse_vec.h')
| -rw-r--r-- | vppinfra/vppinfra/sparse_vec.h | 244 |
1 files changed, 0 insertions, 244 deletions
diff --git a/vppinfra/vppinfra/sparse_vec.h b/vppinfra/vppinfra/sparse_vec.h deleted file mode 100644 index ec8f0a1c4bf..00000000000 --- a/vppinfra/vppinfra/sparse_vec.h +++ /dev/null @@ -1,244 +0,0 @@ -/* - * 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: - */ |