Changeset View
Changeset View
Standalone View
Standalone View
sys/net/route/nhop_utils.h
- This file was added.
Property | Old Value | New Value |
---|---|---|
svn:eol-style | null | native \ No newline at end of property |
svn:keywords | null | FreeBSD=%H \ No newline at end of property |
svn:mime-type | null | text/plain \ No newline at end of property |
/*- | |||||
* SPDX-License-Identifier: BSD-2-Clause-FreeBSD | |||||
* | |||||
* 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. | |||||
* | |||||
* $FreeBSD$ | |||||
*/ | |||||
#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, _key, _ret) do { \ | |||||
typeof(*(_head)->ptr) _tmp; \ | |||||
uint32_t _buck = CHT_GET_BUCK(_head, _PX, _key); \ | |||||
_ret = CHT_FIRST(_head, _buck); \ | |||||
_tmp = NULL; \ | |||||
for ( ; _ret != NULL; _tmp = _ret, _ret = _PX##_next(_ret)) { \ | |||||
if (_PX##_cmp(_key, _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(_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 (_PX##_cmp(_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_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_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 | |||||