1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD 3 * 4 * Copyright (c) 2020 Alexander V. Chernikov 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25 * SUCH DAMAGE. 26 * 27 * $FreeBSD$ 28 */ 29 30 #ifndef _NET_ROUTE_NHOP_UTILS_H_ 31 #define _NET_ROUTE_NHOP_UTILS_H_ 32 33 /* Chained hash table */ 34 struct _cht_head { 35 uint32_t hash_size; 36 uint32_t items_count; 37 void **ptr; 38 }; 39 40 static inline uint32_t 41 _cht_get_resize_size(const struct _cht_head *head) 42 { 43 uint32_t new_size = 0; 44 45 if ((head->items_count * 2 > head->hash_size) && (head->hash_size < 65536)) 46 new_size = head->hash_size * 2; 47 else if ((head->items_count * 4 < head->hash_size) && head->hash_size > 16) 48 new_size = head->hash_size / 2; 49 50 return (new_size); 51 } 52 53 static inline int 54 _cht_need_resize(const struct _cht_head *head) 55 { 56 57 return (_cht_get_resize_size(head) > 0); 58 } 59 60 61 #ifndef typeof 62 #define typeof __typeof 63 #endif 64 65 #define CHT_SLIST_NEED_RESIZE(_head) \ 66 _cht_need_resize((const struct _cht_head *)(_head)) 67 #define CHT_SLIST_GET_RESIZE_BUCKETS(_head) \ 68 _cht_get_resize_size((const struct _cht_head *)(_head)) 69 #define CHT_SLIST_GET_RESIZE_SIZE(_buckets) ((_buckets) * sizeof(void *)) 70 71 #define CHT_SLIST_DEFINE(_HNAME, _ITEM_TYPE) \ 72 struct _HNAME##_head { \ 73 uint32_t hash_size; \ 74 uint32_t items_count; \ 75 _ITEM_TYPE **ptr; \ 76 } 77 78 #define CHT_SLIST_INIT(_head, _ptr, _num_buckets) \ 79 (_head)->hash_size = _num_buckets; \ 80 (_head)->items_count = 0; \ 81 (_head)->ptr = _ptr; 82 83 /* Default hash method for constant-size keys */ 84 85 #define CHT_GET_BUCK(_head, _PX, _key) _PX##_hash_key(_key) & ((_head)->hash_size - 1) 86 #define CHT_GET_BUCK_OBJ(_head, _PX, _obj) _PX##_hash_obj(_obj) & ((_head)->hash_size - 1) 87 88 #define CHT_FIRST(_head, idx) _CHT_FIRST((_head)->ptr, idx) 89 #define _CHT_FIRST(_ptr, idx) (_ptr)[idx] 90 91 #define CHT_SLIST_FIND(_head, _PX, _key, _ret) do { \ 92 uint32_t _buck = CHT_GET_BUCK(_head, _PX, _key); \ 93 _ret = CHT_FIRST(_head, _buck); \ 94 for ( ; _ret != NULL; _ret = _PX##_next(_ret)) { \ 95 if (_PX##_cmp(_key, (_ret))) \ 96 break; \ 97 } \ 98 } while(0) 99 100 /* 101 * hash_obj, nhop_cmp 102 */ 103 #define CHT_SLIST_FIND_BYOBJ(_head, _PX, _obj, _ret) do { \ 104 uint32_t _buck = CHT_GET_BUCK_OBJ(_head, _PX, _obj); \ 105 _ret = CHT_FIRST(_head, _buck); \ 106 for ( ; _ret != NULL; _ret = _PX##_next(_ret)) { \ 107 if (_PX##_cmp(_obj, _ret)) \ 108 break; \ 109 } \ 110 } while(0) 111 112 #define CHT_SLIST_INSERT_HEAD(_head, _PX, _obj) do { \ 113 uint32_t _buck = CHT_GET_BUCK_OBJ(_head, _PX, _obj); \ 114 _PX##_next(_obj) = CHT_FIRST(_head, _buck); \ 115 CHT_FIRST(_head, _buck) = _obj; \ 116 (_head)->items_count++; \ 117 } while(0) 118 119 #define CHT_SLIST_REMOVE(_head, _PX, _key, _ret) do { \ 120 typeof(*(_head)->ptr) _tmp; \ 121 uint32_t _buck = CHT_GET_BUCK(_head, _PX, _key); \ 122 _ret = CHT_FIRST(_head, _buck); \ 123 _tmp = NULL; \ 124 for ( ; _ret != NULL; _tmp = _ret, _ret = _PX##_next(_ret)) { \ 125 if (_PX##_cmp(_key, _ret)) \ 126 break; \ 127 } \ 128 if (_ret != NULL) { \ 129 if (_tmp == NULL) \ 130 CHT_FIRST(_head, _buck) = _PX##_next(_ret); \ 131 else \ 132 _PX##_next(_tmp) = _PX##_next(_ret); \ 133 (_head)->items_count--; \ 134 } \ 135 } while(0) 136 137 #define CHT_SLIST_REMOVE_BYOBJ(_head, _PX, _obj, _ret) do { \ 138 typeof(*(_head)->ptr) _tmp; \ 139 uint32_t _buck = CHT_GET_BUCK_OBJ(_head, _PX, _obj); \ 140 _ret = CHT_FIRST(_head, _buck); \ 141 _tmp = NULL; \ 142 for ( ; _ret != NULL; _tmp = _ret, _ret = _PX##_next(_ret)) { \ 143 if (_PX##_cmp(_obj, _ret)) \ 144 break; \ 145 } \ 146 if (_ret != NULL) { \ 147 if (_tmp == NULL) \ 148 CHT_FIRST(_head, _buck) = _PX##_next(_ret); \ 149 else \ 150 _PX##_next(_tmp) = _PX##_next(_ret); \ 151 (_head)->items_count--; \ 152 } \ 153 } while(0) 154 155 156 #define CHT_SLIST_FOREACH(_head, _PX, _x) \ 157 for (uint32_t _i = 0; _i < (_head)->hash_size; _i++) { \ 158 for (_x = CHT_FIRST(_head, _i); _x; _x = _PX##_next(_x)) 159 160 #define CHT_SLIST_FOREACH_END } 161 162 #define CHT_SLIST_RESIZE(_head, _PX, _new_void_ptr, _new_hsize) \ 163 uint32_t _new_idx; \ 164 typeof((_head)->ptr) _new_ptr = (void *)_new_void_ptr; \ 165 typeof(*(_head)->ptr) _x, _y; \ 166 for (uint32_t _old_idx = 0; _old_idx < (_head)->hash_size; _old_idx++) {\ 167 _x = CHT_FIRST(_head, _old_idx); \ 168 _y = _x; \ 169 while (_y != NULL) { \ 170 _y = _PX##_next(_x); \ 171 _new_idx = _PX##_hash_obj(_x) & (_new_hsize - 1);\ 172 _PX##_next(_x) = _CHT_FIRST(_new_ptr, _new_idx);\ 173 _CHT_FIRST(_new_ptr, _new_idx) = _x; \ 174 _x = _y; \ 175 } \ 176 } \ 177 (_head)->hash_size = _new_hsize; \ 178 _new_void_ptr = (void *)(_head)->ptr; \ 179 (_head)->ptr = _new_ptr; 180 181 /* bitmasks */ 182 183 struct bitmask_head { 184 uint16_t free_off; /* index of the first potentially free block */ 185 uint16_t blocks; /* number of 4/8-byte blocks in the index */ 186 uint32_t items_count; /* total number of items */ 187 u_long *idx; 188 }; 189 190 size_t bitmask_get_size(uint32_t items); 191 uint32_t bitmask_get_resize_items(const struct bitmask_head *nh); 192 int bitmask_should_resize(const struct bitmask_head *bh); 193 void bitmask_swap(struct bitmask_head *bh, void *new_idx, uint32_t new_items, void **pidx); 194 void bitmask_init(struct bitmask_head *bh, void *idx, uint32_t num_items); 195 int bitmask_copy(const struct bitmask_head *bi, void *new_idx, uint32_t new_items); 196 int bitmask_alloc_idx(struct bitmask_head *bi, uint16_t *pidx); 197 int bitmask_free_idx(struct bitmask_head *bi, uint16_t idx); 198 199 #endif 200 201