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
_cht_get_resize_size(const struct _cht_head * head)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
_cht_need_resize(const struct _cht_head * head)54 _cht_need_resize(const struct _cht_head *head)
55 {
56
57 return (_cht_get_resize_size(head) > 0);
58 }
59
60 #ifndef typeof
61 #define typeof __typeof
62 #endif
63
64 #define CHT_SLIST_NEED_RESIZE(_head) \
65 _cht_need_resize((const struct _cht_head *)(_head))
66 #define CHT_SLIST_GET_RESIZE_BUCKETS(_head) \
67 _cht_get_resize_size((const struct _cht_head *)(_head))
68 #define CHT_SLIST_GET_RESIZE_SIZE(_buckets) ((_buckets) * sizeof(void *))
69
70 #define CHT_SLIST_DEFINE(_HNAME, _ITEM_TYPE) \
71 struct _HNAME##_head { \
72 uint32_t hash_size; \
73 uint32_t items_count; \
74 _ITEM_TYPE **ptr; \
75 }
76
77 #define CHT_SLIST_INIT(_head, _ptr, _num_buckets) \
78 (_head)->hash_size = _num_buckets; \
79 (_head)->items_count = 0; \
80 (_head)->ptr = _ptr;
81
82 /* Default hash method for constant-size keys */
83
84 #define CHT_GET_BUCK(_head, _PX, _key) _PX##_hash_key(_key) & ((_head)->hash_size - 1)
85 #define CHT_GET_BUCK_OBJ(_head, _PX, _obj) _PX##_hash_obj(_obj) & ((_head)->hash_size - 1)
86
87 #define CHT_FIRST(_head, idx) _CHT_FIRST((_head)->ptr, idx)
88 #define _CHT_FIRST(_ptr, idx) (_ptr)[idx]
89
90 #define CHT_SLIST_FIND(_head, _PX, _key, _ret) do { \
91 uint32_t _buck = CHT_GET_BUCK(_head, _PX, _key); \
92 _ret = CHT_FIRST(_head, _buck); \
93 for ( ; _ret != NULL; _ret = _PX##_next(_ret)) { \
94 if (_PX##_cmp(_key, (_ret))) \
95 break; \
96 } \
97 } while(0)
98
99 /*
100 * hash_obj, nhop_cmp
101 */
102 #define CHT_SLIST_FIND_BYOBJ(_head, _PX, _obj, _ret) do { \
103 uint32_t _buck = CHT_GET_BUCK_OBJ(_head, _PX, _obj); \
104 _ret = CHT_FIRST(_head, _buck); \
105 for ( ; _ret != NULL; _ret = _PX##_next(_ret)) { \
106 if (_PX##_cmp(_obj, _ret)) \
107 break; \
108 } \
109 } while(0)
110
111 #define CHT_SLIST_INSERT_HEAD(_head, _PX, _obj) do { \
112 uint32_t _buck = CHT_GET_BUCK_OBJ(_head, _PX, _obj); \
113 _PX##_next(_obj) = CHT_FIRST(_head, _buck); \
114 CHT_FIRST(_head, _buck) = _obj; \
115 (_head)->items_count++; \
116 } while(0)
117
118 #define CHT_SLIST_REMOVE(_head, _PX, _key, _ret) do { \
119 typeof(*(_head)->ptr) _tmp; \
120 uint32_t _buck = CHT_GET_BUCK(_head, _PX, _key); \
121 _ret = CHT_FIRST(_head, _buck); \
122 _tmp = NULL; \
123 for ( ; _ret != NULL; _tmp = _ret, _ret = _PX##_next(_ret)) { \
124 if (_PX##_cmp(_key, _ret)) \
125 break; \
126 } \
127 if (_ret != NULL) { \
128 if (_tmp == NULL) \
129 CHT_FIRST(_head, _buck) = _PX##_next(_ret); \
130 else \
131 _PX##_next(_tmp) = _PX##_next(_ret); \
132 (_head)->items_count--; \
133 } \
134 } while(0)
135
136 #define CHT_SLIST_REMOVE_BYOBJ(_head, _PX, _obj, _ret) do { \
137 typeof(*(_head)->ptr) _tmp; \
138 uint32_t _buck = CHT_GET_BUCK_OBJ(_head, _PX, _obj); \
139 _ret = CHT_FIRST(_head, _buck); \
140 _tmp = NULL; \
141 for ( ; _ret != NULL; _tmp = _ret, _ret = _PX##_next(_ret)) { \
142 if (_PX##_cmp(_obj, _ret)) \
143 break; \
144 } \
145 if (_ret != NULL) { \
146 if (_tmp == NULL) \
147 CHT_FIRST(_head, _buck) = _PX##_next(_ret); \
148 else \
149 _PX##_next(_tmp) = _PX##_next(_ret); \
150 (_head)->items_count--; \
151 } \
152 } while(0)
153
154 #define CHT_SLIST_FOREACH(_head, _PX, _x) \
155 for (uint32_t _i = 0; _i < (_head)->hash_size; _i++) { \
156 for (_x = CHT_FIRST(_head, _i); _x; _x = _PX##_next(_x))
157 #define CHT_SLIST_FOREACH_END }
158
159 #define CHT_SLIST_RESIZE(_head, _PX, _new_void_ptr, _new_hsize) \
160 uint32_t _new_idx; \
161 typeof((_head)->ptr) _new_ptr = (void *)_new_void_ptr; \
162 typeof(*(_head)->ptr) _x, _y; \
163 for (uint32_t _old_idx = 0; _old_idx < (_head)->hash_size; _old_idx++) {\
164 _x = CHT_FIRST(_head, _old_idx); \
165 _y = _x; \
166 while (_y != NULL) { \
167 _y = _PX##_next(_x); \
168 _new_idx = _PX##_hash_obj(_x) & (_new_hsize - 1);\
169 _PX##_next(_x) = _CHT_FIRST(_new_ptr, _new_idx);\
170 _CHT_FIRST(_new_ptr, _new_idx) = _x; \
171 _x = _y; \
172 } \
173 } \
174 (_head)->hash_size = _new_hsize; \
175 _new_void_ptr = (void *)(_head)->ptr; \
176 (_head)->ptr = _new_ptr;
177
178 /* bitmasks */
179
180 struct bitmask_head {
181 uint16_t free_off; /* index of the first potentially free block */
182 uint16_t blocks; /* number of 4/8-byte blocks in the index */
183 uint32_t items_count; /* total number of items */
184 u_long *idx;
185 };
186
187 size_t bitmask_get_size(uint32_t items);
188 uint32_t bitmask_get_resize_items(const struct bitmask_head *nh);
189 int bitmask_should_resize(const struct bitmask_head *bh);
190 void bitmask_swap(struct bitmask_head *bh, void *new_idx, uint32_t new_items, void **pidx);
191 void bitmask_init(struct bitmask_head *bh, void *idx, uint32_t num_items);
192 int bitmask_copy(const struct bitmask_head *bi, void *new_idx, uint32_t new_items);
193 int bitmask_alloc_idx(struct bitmask_head *bi, uint16_t *pidx);
194 int bitmask_free_idx(struct bitmask_head *bi, uint16_t idx);
195
196 #endif
197