1 files changed, 182 insertions, 0 deletions
diff --git a/sys/net/route/nhop_utils.h b/sys/net/route/nhop_utils.h
new file mode 100644
index 000000000000..17d499b0c706
--- /dev/null
+++ b/sys/net/route/nhop_utils.h
@@ -0,0 +1,182 @@
+/*-
+ * SPDX-License-Identifier: BSD-2-Clause
+ *
+ * Copyright (c) 2020 Alexander V. Chernikov
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#ifndef	_NET_ROUTE_NHOP_UTILS_H_
+#define	_NET_ROUTE_NHOP_UTILS_H_
+
+/* Chained hash table */
+struct _cht_head {
+	uint32_t	hash_size;
+	uint32_t	items_count;
+	void		**ptr;
+};
+
+static inline uint32_t
+_cht_get_resize_size(const struct _cht_head *head)
+{
+	uint32_t new_size = 0;
+
+	if ((head->items_count * 2 > head->hash_size) && (head->hash_size < 65536))
+		new_size = head->hash_size * 2;
+	else if ((head->items_count * 4 < head->hash_size) && head->hash_size > 16)
+		new_size = head->hash_size / 2;
+
+	return (new_size);
+}
+
+static inline int
+_cht_need_resize(const struct _cht_head *head)
+{
+
+	return (_cht_get_resize_size(head) > 0);
+}
+
+#ifndef	typeof
+#define	typeof	__typeof
+#endif
+
+#define	CHT_SLIST_NEED_RESIZE(_head)		\
+	_cht_need_resize((const struct _cht_head *)(_head))
+#define	CHT_SLIST_GET_RESIZE_BUCKETS(_head)	\
+	_cht_get_resize_size((const struct _cht_head *)(_head))
+#define	CHT_SLIST_GET_RESIZE_SIZE(_buckets)	((_buckets) * sizeof(void *))
+
+#define	CHT_SLIST_DEFINE(_HNAME, _ITEM_TYPE)	\
+struct _HNAME##_head {				\
+	uint32_t	hash_size;		\
+	uint32_t	items_count;		\
+	_ITEM_TYPE	**ptr;			\
+}
+
+#define	CHT_SLIST_INIT(_head, _ptr, _num_buckets)	\
+	(_head)->hash_size = _num_buckets;		\
+	(_head)->items_count = 0;			\
+	(_head)->ptr = _ptr;
+
+/* Default hash method for constant-size keys */
+
+#define	CHT_GET_BUCK(_head, _PX, _key)	_PX##_hash_key(_key) & ((_head)->hash_size - 1)
+#define	CHT_GET_BUCK_OBJ(_head, _PX, _obj)	_PX##_hash_obj(_obj) & ((_head)->hash_size - 1)
+
+#define	CHT_FIRST(_head, idx)	_CHT_FIRST((_head)->ptr, idx)
+#define	_CHT_FIRST(_ptr, idx)	(_ptr)[idx]
+
+#define	CHT_SLIST_FIND(_head, _PX, _key, _ret) do {			\
+	uint32_t _buck = CHT_GET_BUCK(_head, _PX, _key);		\
+	_ret = CHT_FIRST(_head, _buck);					\
+	for ( ; _ret != NULL; _ret = _PX##_next(_ret)) {		\
+		if (_PX##_cmp(_key, (_ret)))				\
+			break;						\
+	}								\
+} while(0)
+
+/*
+ * hash_obj, nhop_cmp
+ */
+#define	CHT_SLIST_FIND_BYOBJ(_head, _PX, _obj, _ret) do {		\
+	uint32_t _buck = CHT_GET_BUCK_OBJ(_head, _PX, _obj);		\
+	_ret = CHT_FIRST(_head, _buck);					\
+	for ( ; _ret != NULL; _ret = _PX##_next(_ret)) {		\
+		if (_PX##_cmp(_obj, _ret))				\
+			break;						\
+	}								\
+} while(0)
+
+#define	CHT_SLIST_INSERT_HEAD(_head, _PX, _obj) do {			\
+	uint32_t _buck = CHT_GET_BUCK_OBJ(_head, _PX, _obj);		\
+	_PX##_next(_obj) = CHT_FIRST(_head, _buck);			\
+	CHT_FIRST(_head, _buck) = _obj;					\
+	(_head)->items_count++;						\
+} while(0)
+
+#define	CHT_SLIST_REMOVE(_head, _PX, _obj, _ret) do {			\
+	typeof(*(_head)->ptr) _tmp;					\
+	uint32_t _buck = CHT_GET_BUCK_OBJ(_head, _PX, _obj);		\
+	_ret = CHT_FIRST(_head, _buck);					\
+	_tmp = NULL;							\
+	for ( ; _ret != NULL; _tmp = _ret, _ret = _PX##_next(_ret)) {	\
+		if (_obj == _ret)					\
+			break;						\
+	}								\
+	if (_ret != NULL) {						\
+		if (_tmp == NULL)					\
+			CHT_FIRST(_head, _buck) = _PX##_next(_ret);	\
+		else							\
+			_PX##_next(_tmp) = _PX##_next(_ret);		\
+		(_head)->items_count--;					\
+	}								\
+} while(0)
+#define	CHT_SLIST_REMOVE_BYOBJ	CHT_SLIST_REMOVE
+
+#define	CHT_SLIST_FOREACH(_head, _PX, _x)				\
+	for (uint32_t _i = 0; _i < (_head)->hash_size; _i++) {		\
+		for (_x = CHT_FIRST(_head, _i); _x; _x = _PX##_next(_x))
+#define	CHT_SLIST_FOREACH_END	}
+
+#define	CHT_SLIST_FOREACH_SAFE(_head, _PX, _x, _tmp)			\
+	for (uint32_t _i = 0; _i < (_head)->hash_size; _i++) {		\
+		for (_x = CHT_FIRST(_head, _i); (_tmp = _PX##_next(_x), _x); _x = _tmp)
+#define	CHT_SLIST_FOREACH_SAFE_END	}
+
+#define	CHT_SLIST_RESIZE(_head, _PX, _new_void_ptr, _new_hsize)		\
+	uint32_t _new_idx;						\
+	typeof((_head)->ptr) _new_ptr = (void *)_new_void_ptr;		\
+	typeof(*(_head)->ptr) _x, _y;					\
+	for (uint32_t _old_idx = 0; _old_idx < (_head)->hash_size; _old_idx++) {\
+		_x = CHT_FIRST(_head, _old_idx);			\
+		_y = _x;						\
+		while (_y != NULL) {					\
+			_y = _PX##_next(_x);				\
+			_new_idx = _PX##_hash_obj(_x) & (_new_hsize - 1);\
+			_PX##_next(_x) = _CHT_FIRST(_new_ptr, _new_idx);\
+			_CHT_FIRST(_new_ptr, _new_idx) = _x;		\
+			_x = _y;					\
+		}							\
+	}								\
+	(_head)->hash_size = _new_hsize;				\
+	_new_void_ptr = (void *)(_head)->ptr;				\
+	(_head)->ptr = _new_ptr;
+
+/* bitmasks */
+
+struct bitmask_head {
+	uint16_t	free_off; /* index of the first potentially free block */
+	uint16_t	blocks; /* number of 4/8-byte blocks in the index */
+	uint32_t	items_count; /* total number of items */
+	u_long		*idx;
+};
+
+size_t bitmask_get_size(uint32_t items);
+uint32_t bitmask_get_resize_items(const struct bitmask_head *nh);
+int bitmask_should_resize(const struct bitmask_head *bh);
+void bitmask_swap(struct bitmask_head *bh, void *new_idx, uint32_t new_items, void **pidx);
+void bitmask_init(struct bitmask_head *bh, void *idx, uint32_t num_items);
+int bitmask_copy(const struct bitmask_head *bi, void *new_idx, uint32_t new_items);
+int bitmask_alloc_idx(struct bitmask_head *bi, uint16_t *pidx);
+int bitmask_free_idx(struct bitmask_head *bi, uint16_t idx);
+
+#endif