diff options
Diffstat (limited to 'lib/includes/hicn/util')
-rw-r--r-- | lib/includes/hicn/util/array.h | 323 | ||||
-rw-r--r-- | lib/includes/hicn/util/bitmap.h | 332 | ||||
-rw-r--r-- | lib/includes/hicn/util/hash.h | 368 | ||||
-rw-r--r-- | lib/includes/hicn/util/ip_address.h | 211 | ||||
-rw-r--r-- | lib/includes/hicn/util/khash.h | 826 | ||||
-rw-r--r-- | lib/includes/hicn/util/log.h | 77 | ||||
-rw-r--r-- | lib/includes/hicn/util/map.h | 444 | ||||
-rw-r--r-- | lib/includes/hicn/util/pool.h | 292 | ||||
-rw-r--r-- | lib/includes/hicn/util/ring.h | 227 | ||||
-rw-r--r-- | lib/includes/hicn/util/set.h | 370 | ||||
-rw-r--r-- | lib/includes/hicn/util/slab.h | 126 | ||||
-rw-r--r-- | lib/includes/hicn/util/sstrncpy.h | 76 | ||||
-rw-r--r-- | lib/includes/hicn/util/token.h | 8 | ||||
-rw-r--r-- | lib/includes/hicn/util/types.h | 56 | ||||
-rw-r--r-- | lib/includes/hicn/util/vector.h | 470 | ||||
-rw-r--r-- | lib/includes/hicn/util/win_portability.h | 88 | ||||
-rw-r--r-- | lib/includes/hicn/util/windows/dlfcn.h | 15 | ||||
-rw-r--r--[-rwxr-xr-x] | lib/includes/hicn/util/windows/windows_utils.h | 326 |
18 files changed, 3721 insertions, 914 deletions
diff --git a/lib/includes/hicn/util/array.h b/lib/includes/hicn/util/array.h index 56cfcad8b..f56c13140 100644 --- a/lib/includes/hicn/util/array.h +++ b/lib/includes/hicn/util/array.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Copyright (c) 2021 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: @@ -23,178 +23,167 @@ #include <assert.h> #include <hicn/util/log.h> -#include <math.h> // log2 +#include <math.h> // log2 #include <string.h> // memmove #define BUFSIZE 1024 -typedef int(*cmp_t)(const void * x, const void * y); - -#define TYPEDEF_ARRAY_H(NAME, T) \ - \ -typedef struct { \ - size_t size; \ - size_t max_size_log; \ - T * elements; \ -} NAME ## _t; \ - \ -int NAME ## _initialize(NAME ## _t * array); \ - \ -int NAME ## _finalize(NAME ## _t * array); \ - \ -NAME ## _t * NAME ## _create(); \ - \ -void NAME ## _free(NAME ## _t * array); \ - \ -int NAME ## _add(NAME ## _t * array, T element); \ - \ -int NAME ## _remove_index(NAME ## _t * array, int index, T * element); \ - \ -int NAME ## _remove(NAME ## _t * array, const T search, T * element); \ - \ -int NAME ## _get(const NAME ## _t * array, const T search, T * element); \ - \ -int NAME ## _get_index(const NAME ## _t * array, int index, T * element); \ - \ -int NAME ## _get_elements(const NAME ## _t * array, T ** elements); \ - \ -size_t NAME ## _len(const NAME ## _t * array); - +#define TYPEDEF_ARRAY_H(NAME, T) \ + \ + typedef struct \ + { \ + size_t size; \ + size_t max_size_log; \ + T *elements; \ + } NAME##_t; \ + \ + int NAME##_initialize (NAME##_t *array); \ + \ + int NAME##_finalize (NAME##_t *array); \ + \ + NAME##_t *NAME##_create (); \ + \ + void NAME##_free (NAME##_t *array); \ + \ + int NAME##_add (NAME##_t *array, T element); \ + \ + int NAME##_remove_index (NAME##_t *array, int index, T *element); \ + \ + int NAME##_remove (NAME##_t *array, const T search, T *element); \ + \ + int NAME##_get (const NAME##_t *array, const T search, T *element); \ + \ + int NAME##_get_index (const NAME##_t *array, int index, T *element); \ + \ + int NAME##_get_elements (const NAME##_t *array, T **elements); \ + \ + size_t NAME##_len (const NAME##_t *array); #define ARRAY_MAX_SIZE_LOG_INIT 0 -#define TYPEDEF_ARRAY(NAME, T, CMP, SNPRINTF) \ -int \ -NAME ## _initialize(NAME ## _t * array) \ -{ \ - array->max_size_log = ARRAY_MAX_SIZE_LOG_INIT; \ - array->size = 0; \ - if (array->max_size_log == 0) { \ - array->elements = NULL; \ - return 0; \ - } \ - array->elements = malloc((1 << array->max_size_log) * sizeof(T)); \ - if (!array->elements) \ - return -1; \ - return 0; \ -} \ - \ -int \ -NAME ## _finalize(NAME ## _t * array) \ -{ \ - for (unsigned i = 0; i < array->size; i++) { \ - NAME ## _remove_index(array, i, NULL); \ - } \ - return 0; \ -} \ - \ -NAME ## _t * \ -NAME ## _create() \ -{ \ - NAME ## _t * array = malloc(sizeof(NAME ## _t)); \ - if (!array) \ - goto ERR_MALLOC; \ - \ - if (NAME ## _initialize(array) < 0) \ - goto ERR_INITIALIZE; \ - \ - return array; \ - \ -ERR_INITIALIZE: \ - free(array); \ -ERR_MALLOC: \ - return NULL; \ -} \ - \ -void \ -NAME ## _free(NAME ## _t * array) \ -{ \ - NAME ## _finalize(array); \ - free(array->elements); \ - free(array); \ -} \ - \ -int \ -NAME ## _add(NAME ## _t * array, T element) \ -{ \ - /* Ensure sufficient space for next addition */ \ - size_t new_size_log = (array->size > 0) ? log2(array->size)+1 : 1; \ - if (new_size_log > array->max_size_log) { \ - array->max_size_log = new_size_log; \ - array->elements = realloc(array->elements, \ - (1 << new_size_log) * sizeof(T)); \ - } \ - \ - if (!array->elements) \ - goto ERR_REALLOC; \ - \ - array->elements[array->size++] = element; \ - return 0; \ - \ -ERR_REALLOC: \ - return -1; \ -} \ - \ -int \ -NAME ## _remove_index(NAME ## _t * array, int index, T * element) \ -{ \ - if (index > NAME ## _len(array)) \ - return -1; \ - if (element) \ - *element = array->elements[index]; \ - if (index < array->size) \ - memmove(array->elements + index, array->elements + index + 1, \ - array->size - index); \ - array->size--; \ - return 0; \ -} \ - \ -int \ -NAME ## _remove(NAME ## _t * array, const T search, T * element) \ -{ \ - for (unsigned i = 0; i < array->size; i++) { \ - if (CMP(search, array->elements[i]) == 0) \ - return facelet_array_remove_index(array, i, element); \ - } \ - /* Not found */ \ - if (element) \ - *element = NULL; \ - return 0; \ -} \ - \ -int \ -NAME ## _get(const NAME ## _t * array, const T search, T * element) \ -{ \ - assert(element); \ - for (unsigned i = 0; i < array->size; i++) \ - if (CMP(search, array->elements[i]) == 0) { \ - *element = array->elements[i]; \ - return 0; \ - } \ - /* Not found */ \ - *element = NULL; \ - return 0; \ -} \ - \ -int \ -NAME ## _get_index(const NAME ## _t * array, int index, T * element) \ -{ \ - assert(element); \ - *element = array->elements[index]; \ - return 0; \ -} \ - \ -int \ -NAME ## _get_elements(const NAME ## _t * array, T ** elements) \ -{ \ - *elements = array->elements; \ - return 0; \ -} \ - \ -size_t \ -NAME ## _len(const NAME ## _t * array) \ -{ \ - return array->size; \ -} +#define TYPEDEF_ARRAY(NAME, T, CMP, SNPRINTF) \ + int NAME##_initialize (NAME##_t *array) \ + { \ + array->max_size_log = ARRAY_MAX_SIZE_LOG_INIT; \ + array->size = 0; \ + if (array->max_size_log == 0) \ + { \ + array->elements = NULL; \ + return 0; \ + } \ + array->elements = malloc ((1 << array->max_size_log) * sizeof (T)); \ + if (!array->elements) \ + return -1; \ + return 0; \ + } \ + \ + int NAME##_finalize (NAME##_t *array) \ + { \ + for (unsigned i = 0; i < array->size; i++) \ + { \ + NAME##_remove_index (array, i, NULL); \ + } \ + return 0; \ + } \ + \ + NAME##_t *NAME##_create () \ + { \ + NAME##_t *array = malloc (sizeof (NAME##_t)); \ + if (!array) \ + goto ERR_MALLOC; \ + \ + if (NAME##_initialize (array) < 0) \ + goto ERR_INITIALIZE; \ + \ + return array; \ + \ + ERR_INITIALIZE: \ + free (array); \ + ERR_MALLOC: \ + return NULL; \ + } \ + \ + void NAME##_free (NAME##_t *array) \ + { \ + NAME##_finalize (array); \ + free (array->elements); \ + free (array); \ + } \ + \ + int NAME##_add (NAME##_t *array, T element) \ + { \ + /* Ensure sufficient space for next addition */ \ + size_t new_size_log = (array->size > 0) ? log2 (array->size) + 1 : 1; \ + if (new_size_log > array->max_size_log) \ + { \ + array->max_size_log = new_size_log; \ + array->elements = \ + realloc (array->elements, (1 << new_size_log) * sizeof (T)); \ + } \ + \ + if (!array->elements) \ + goto ERR_REALLOC; \ + \ + array->elements[array->size++] = element; \ + return 0; \ + \ + ERR_REALLOC: \ + return -1; \ + } \ + \ + int NAME##_remove_index (NAME##_t *array, int index, T *element) \ + { \ + if (index > NAME##_len (array)) \ + return -1; \ + if (element) \ + *element = array->elements[index]; \ + if (index < array->size) \ + memmove (array->elements + index, array->elements + index + 1, \ + array->size - index); \ + array->size--; \ + return 0; \ + } \ + \ + int NAME##_remove (NAME##_t *array, const T search, T *element) \ + { \ + for (unsigned i = 0; i < array->size; i++) \ + { \ + if (CMP (search, array->elements[i]) == 0) \ + return NAME##_remove_index (array, i, element); \ + } \ + /* Not found */ \ + if (element) \ + *element = NULL; \ + return 0; \ + } \ + \ + int NAME##_get (const NAME##_t *array, const T search, T *element) \ + { \ + assert (element); \ + for (unsigned i = 0; i < array->size; i++) \ + if (CMP (search, array->elements[i]) == 0) \ + { \ + *element = array->elements[i]; \ + return 0; \ + } \ + /* Not found */ \ + *element = NULL; \ + return 0; \ + } \ + \ + int NAME##_get_index (const NAME##_t *array, int index, T *element) \ + { \ + assert (element); \ + *element = array->elements[index]; \ + return 0; \ + } \ + \ + int NAME##_get_elements (const NAME##_t *array, T **elements) \ + { \ + *elements = array->elements; \ + return 0; \ + } \ + \ + size_t NAME##_len (const NAME##_t *array) { return array->size; } #endif /* UTIL_ARRAY_H */ diff --git a/lib/includes/hicn/util/bitmap.h b/lib/includes/hicn/util/bitmap.h new file mode 100644 index 000000000..d83c838b7 --- /dev/null +++ b/lib/includes/hicn/util/bitmap.h @@ -0,0 +1,332 @@ +/* + * Copyright (c) 2021 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. + */ + +/** + * \file bitmap.h + * \brief Bitmap + * + * A bitmap is implemented as a wrapper over a vector made of bit elements + */ + +#ifndef UTIL_BITMAP_H +#define UTIL_BITMAP_H + +#include <assert.h> +#include <stdio.h> +#include <string.h> +#include <sys/param.h> // MIN, MAX + +#include <hicn/common.h> +#include <hicn/util/vector.h> + +typedef hicn_uword bitmap_t; + +#define WORD_WIDTH (sizeof (bitmap_t) * 8) + +#define WORD_WIDTH (sizeof (bitmap_t) * 8) +#define BITMAP_WIDTH(bitmap) (sizeof ((bitmap)[0]) * 8) +#define BITMAP_INVALID_INDEX ((uint32_t) (~0)) + +static inline int +hicn_get_lowest_set_bit_index (hicn_uword w) +{ + return hicn_uword_bits > 32 ? __builtin_ctzll (w) : __builtin_ctz (w); +} + +/** + * @brief Allocate and initialize a bitmap + * + * @param[in,out] bitmap Bitmap to allocate and initialize + * @param[in] max_size Bitmap max_size + */ +#define bitmap_init(bitmap, init_size, max_size) \ + vector_init ( \ + bitmap, next_pow2 ((init_size) / BITMAP_WIDTH (bitmap)), \ + max_size == 0 ? 0 : next_pow2 ((max_size) / BITMAP_WIDTH (bitmap))) + +/* + * @brief Ensures a bitmap is sufficiently large to hold an element at the + * given position. + * + * @param[in] bitmap The bitmap for which to validate the position. + * @param[in] pos The position to validate. + * + * NOTE: + * - This function should always be called before writing to a bitmap element + * to eventually make room for it (the bitmap will eventually be resized). + */ +static inline int +bitmap_ensure_pos (bitmap_t **bitmap, off_t pos) +{ + size_t offset = pos / BITMAP_WIDTH (*bitmap); + return vector_ensure_pos (*bitmap, offset); +} + +/** + * @brief Returns the allocated size of a bitmap. + * + * @see listener_table_get_by_id + */ +#define bitmap_get_alloc_size(bitmap) vector_get_alloc_size (bitmap) + +/** + * @brief Retrieve the state of the i-th bit in the bitmap. + * + * @param[in] bitmap The bitmap to access. + * @param[in] i The bit position. + */ +static inline int +_bitmap_get (const bitmap_t *bitmap, off_t i) +{ + size_t offset = i / BITMAP_WIDTH (bitmap); + assert (offset < bitmap_get_alloc_size (bitmap)); + size_t pos = i % BITMAP_WIDTH (bitmap); + return (bitmap[offset] >> pos) & 1; +} + +/** + * @brief Retrieve the state of the i-th bit in the bitmap. + * Does not sanity check the position. + * + * @param[in] bitmap The bitmap to access. + * @param[in] i The bit position. + */ +static inline int +_bitmap_get_no_check (const bitmap_t *bitmap, off_t i) +{ + size_t offset = i / BITMAP_WIDTH (bitmap); + size_t pos = i % BITMAP_WIDTH (bitmap); + return (bitmap[offset] >> pos) & 1; +} + +/* + * @brief Returns whether the i-th bit is set (equal to 1) in a bitmap. + * + * @param[in] bitmap The bitmap to access. + * @param[in] i The bit position. + * + * @return bool + */ +#define bitmap_is_set(bitmap, i) (_bitmap_get ((bitmap), (i)) == 1) +#define bitmap_is_unset(bitmap, i) (_bitmap_get ((bitmap), (i)) == 0) + +#define bitmap_is_set_no_check(bitmap, i) \ + (_bitmap_get_no_check ((bitmap), (i)) == 1) +#define bitmap_is_unset_no_check(bitmap, i) \ + (_bitmap_get_no_check ((bitmap), (i)) == 0) + +static inline int +_bitmap_set_no_check (bitmap_t *bitmap, off_t i) +{ + size_t offset = i / BITMAP_WIDTH (bitmap); + size_t pos = i % BITMAP_WIDTH (bitmap); + bitmap[offset] |= (hicn_uword) (1) << pos; + return 0; +} + +static inline int +_bitmap_set (bitmap_t **bitmap_ptr, off_t i) +{ + if (bitmap_ensure_pos (bitmap_ptr, i) < 0) + return -1; + + bitmap_t *bitmap = *bitmap_ptr; + return _bitmap_set_no_check (bitmap, i); +} + +/* + * @brief Set i-th bit to 1 in a bitmap. Reallocate the vector if the bit + * position is greater than the vector length. + * + * @param[in] bitmap The bitmap to access. + * @param[in] i The bit position. + * + * @return bool + */ +#define bitmap_set(bitmap, i) _bitmap_set ((bitmap_t **) &bitmap, i) + +/* + * @brief Set i-th bit to 1 in a bitmap. Unsafe version, does not check + * boundaries. + * + * @param[in] bitmap The bitmap to access. + * @param[in] i The bit position. + * + * @return bool + */ +#define bitmap_set_no_check(bitmap, i) _bitmap_set_no_check (bitmap, i) + +#define bitmap_unset(bitmap, i) _bitmap_unset (bitmap, i, 1) +#define bitmap_unset_no_check(bitmap, i) _bitmap_unset (bitmap, i, 0) + +static inline int +_bitmap_unset (bitmap_t *bitmap, off_t i, int check) +{ + if (check && bitmap_ensure_pos (&bitmap, i) < 0) + return -1; + size_t offset = i / BITMAP_WIDTH (bitmap); + size_t pos = i % BITMAP_WIDTH (bitmap); + bitmap[offset] &= ~((hicn_uword) (1) << pos); + return 0; +} + +static inline int +bitmap_set_range (bitmap_t *bitmap, off_t from, off_t to) +{ + assert (from <= to); + ssize_t offset_from = from / BITMAP_WIDTH (bitmap); + ssize_t offset_to = to / BITMAP_WIDTH (bitmap); + size_t pos_from = from % BITMAP_WIDTH (bitmap); + size_t pos_to = to % BITMAP_WIDTH (bitmap); + + /* + * First block initialization is needed if <from> is not aligned with the + * bitmap element size or if to is within the same one. + */ + if ((pos_from != 0) || + ((offset_to == offset_from) && (pos_to != BITMAP_WIDTH (bitmap) - 1))) + { + size_t from_end = MIN (to, (offset_from + 1) * BITMAP_WIDTH (bitmap)); + for (size_t k = from; k < from_end; k++) + { + if (bitmap_set (bitmap, k) < 0) + goto END; + } + } + + /* + * Second block is needed if <to> is not aligned with the bitmap element + * size + */ + if ((pos_to != BITMAP_WIDTH (bitmap) - 1) && (offset_to != offset_from)) + { + size_t to_start = MAX (from, offset_to * BITMAP_WIDTH (bitmap)); + for (size_t k = to_start; k < (size_t) to; k++) + { + if (bitmap_set (bitmap, k) < 0) + goto END; + } + } + + if (pos_from != 0) + offset_from += 1; + if (pos_to != BITMAP_WIDTH (bitmap) - 1) + offset_to -= 1; + + /* + * We need to cover both elements at position offset_from and offset_to + * provided that offset_from is not bigger + */ + if (offset_to >= offset_from) + { + memset (&bitmap[offset_from], 0xFF, + (offset_to - offset_from + 1) * sizeof (bitmap[0])); + } + + return 0; + +END: + return -1; +} + +#define bitmap_set_to(bitmap, to) bitmap_set_range ((bitmap), 0, (to)) + +#define bitmap_free(bitmap) vector_free (bitmap) + +static inline hicn_uword +bitmap_next_set_no_check (const bitmap_t *bitmap, hicn_uword i, size_t length) +{ + hicn_uword pos = i / WORD_WIDTH; + hicn_uword offset = i % WORD_WIDTH; + hicn_uword tmp; + hicn_uword mask = ~((1ULL << offset) - 1); + + if (pos < length) + { + // This will zeroes all bits < i + tmp = bitmap[pos] & mask; + if (tmp) + return hicn_get_lowest_set_bit_index (tmp) + pos * WORD_WIDTH; + + for (pos += 1; pos < length; pos++) + { + tmp = bitmap[pos]; + if (tmp) + return hicn_get_lowest_set_bit_index (tmp) + pos * WORD_WIDTH; + } + } + + return BITMAP_INVALID_INDEX; +} + +static inline hicn_uword +bitmap_next_set (const bitmap_t *bitmap, hicn_uword i) +{ + return bitmap_next_set_no_check (bitmap, i, vector_get_alloc_size (bitmap)); +} + +static inline hicn_uword +bitmap_next_unset_no_check (const bitmap_t *bitmap, hicn_uword i, + size_t length) +{ + hicn_uword pos = i / WORD_WIDTH; + hicn_uword offset = i % WORD_WIDTH; + hicn_uword tmp; + hicn_uword mask = ~((1ULL << offset) - 1); + + if (pos < length) + { + // This will zeroes all bits < i + tmp = ~bitmap[pos] & mask; + if (tmp) + return hicn_get_lowest_set_bit_index (tmp) + pos * WORD_WIDTH; + + for (pos += 1; pos < length; pos++) + { + tmp = ~bitmap[pos]; + if (tmp) + return hicn_get_lowest_set_bit_index (tmp) + pos * WORD_WIDTH; + } + } + return BITMAP_INVALID_INDEX; +} + +static inline hicn_uword +bitmap_next_unset (const bitmap_t *bitmap, hicn_uword i) +{ + return bitmap_next_unset_no_check (bitmap, i, + vector_get_alloc_size (bitmap)); +} + +#define bitmap_first_set(bitmap) bitmap_next_set (bitmap, 0) +#define bitmap_first_set_no_check(bitmap, size) \ + bitmap_next_set_no_check (bitmap, 0, size) + +#define bitmap_first_unset(bitmap) bitmap_next_unset (bitmap, 0) +#define bitmap_first_unset_no_check(bitmap, size) \ + bitmap_next_unset_no_check (bitmap, 0, size) + +static inline void +bitmap_print (const bitmap_t *bitmap, size_t n_words) +{ + for (size_t word = 0; word < n_words; word++) + { + for (int bit = sizeof (hicn_uword) - 1; bit >= 0; bit--) + (bitmap_is_set_no_check (&bitmap[word], bit)) ? printf ("1") : + printf ("0"); + } +} + +#endif /* UTIL_BITMAP_H */ diff --git a/lib/includes/hicn/util/hash.h b/lib/includes/hicn/util/hash.h new file mode 100644 index 000000000..8dbe0d680 --- /dev/null +++ b/lib/includes/hicn/util/hash.h @@ -0,0 +1,368 @@ +/* + * Copyright (c) 2021 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. + */ + +/* + * \file hash.h + * \brief Simple non-cryptographic hash implementation. + * + * Two helpers are provided : + * hash(buf, len) : hash a buffer <buf> of length <len> + * hash_struct(buf) : hash a buffer corresponding to an allocated struct + * + * This file consists in excerpts from Jenkins hash (public domain). + * http://www.burtleburtle.net/bob/c/lookup3.c + */ +#ifndef UTIL_HASH_H +#define UTIL_HASH_H + +#include <stdint.h> +#include <stddef.h> // size_t + +#if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \ + __BYTE_ORDER == __LITTLE_ENDIAN) || \ + (defined(i386) || defined(__i386__) || defined(__i486__) || \ + defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL)) +#define HASH_LITTLE_ENDIAN 1 +#define HASH_BIG_ENDIAN 0 +#elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \ + __BYTE_ORDER == __BIG_ENDIAN) || \ + (defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel)) +#define HASH_LITTLE_ENDIAN 0 +#define HASH_BIG_ENDIAN 1 +#else +#define HASH_LITTLE_ENDIAN 0 +#define HASH_BIG_ENDIAN 0 +#endif + +#define hashsize(n) ((uint32_t) 1 << (n)) +#define hashmask(n) (hashsize (n) - 1) +#define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k)))) + +#define mix(a, b, c) \ + { \ + a -= c; \ + a ^= rot (c, 4); \ + c += b; \ + b -= a; \ + b ^= rot (a, 6); \ + a += c; \ + c -= b; \ + c ^= rot (b, 8); \ + b += a; \ + a -= c; \ + a ^= rot (c, 16); \ + c += b; \ + b -= a; \ + b ^= rot (a, 19); \ + a += c; \ + c -= b; \ + c ^= rot (b, 4); \ + b += a; \ + } + +#define final(a, b, c) \ + { \ + c ^= b; \ + c -= rot (b, 14); \ + a ^= c; \ + a -= rot (c, 11); \ + b ^= a; \ + b -= rot (a, 25); \ + c ^= b; \ + c -= rot (b, 16); \ + a ^= c; \ + a -= rot (c, 4); \ + b ^= a; \ + b -= rot (a, 14); \ + c ^= b; \ + c -= rot (b, 24); \ + } + +static inline uint32_t +hashlittle (const void *key, size_t length, uint32_t initval) +{ + uint32_t a, b, c; /* internal state */ + union + { + const void *ptr; + size_t i; + } u; /* needed for Mac Powerbook G4 */ + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + ((uint32_t) length) + initval; + + u.ptr = key; + if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) + { + const uint32_t *k = (const uint32_t *) key; /* read 32-bit chunks */ + + /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) + */ + while (length > 12) + { + a += k[0]; + b += k[1]; + c += k[2]; + mix (a, b, c); + length -= 12; + k += 3; + } + + /*----------------------------- handle the last (probably partial) + * block */ + /* + * "k[2]&0xffffff" actually reads beyond the end of the string, but + * then masks off the part it's not allowed to read. Because the + * string is aligned, the masked-off tail is in the same word as the + * rest of the string. Every machine with memory protection I've seen + * does it on word boundaries, so is OK with this. But VALGRIND will + * still catch it and complain. The masking trick does make the hash + * noticably faster for short strings (like English words). + */ +#ifndef VALGRIND + + switch (length) + { + case 12: + c += k[2]; + b += k[1]; + a += k[0]; + break; + case 11: + c += k[2] & 0xffffff; + b += k[1]; + a += k[0]; + break; + case 10: + c += k[2] & 0xffff; + b += k[1]; + a += k[0]; + break; + case 9: + c += k[2] & 0xff; + b += k[1]; + a += k[0]; + break; + case 8: + b += k[1]; + a += k[0]; + break; + case 7: + b += k[1] & 0xffffff; + a += k[0]; + break; + case 6: + b += k[1] & 0xffff; + a += k[0]; + break; + case 5: + b += k[1] & 0xff; + a += k[0]; + break; + case 4: + a += k[0]; + break; + case 3: + a += k[0] & 0xffffff; + break; + case 2: + a += k[0] & 0xffff; + break; + case 1: + a += k[0] & 0xff; + break; + case 0: + return c; /* zero length strings require no mixing */ + } + +#else /* make valgrind happy */ + + k8 = (const uint8_t *) k; + switch (length) + { + case 12: + c += k[2]; + b += k[1]; + a += k[0]; + break; + case 11: + c += ((uint32_t) k8[10]) << 16; /* fall through */ + case 10: + c += ((uint32_t) k8[9]) << 8; /* fall through */ + case 9: + c += k8[8]; /* fall through */ + case 8: + b += k[1]; + a += k[0]; + break; + case 7: + b += ((uint32_t) k8[6]) << 16; /* fall through */ + case 6: + b += ((uint32_t) k8[5]) << 8; /* fall through */ + case 5: + b += k8[4]; /* fall through */ + case 4: + a += k[0]; + break; + case 3: + a += ((uint32_t) k8[2]) << 16; /* fall through */ + case 2: + a += ((uint32_t) k8[1]) << 8; /* fall through */ + case 1: + a += k8[0]; + break; + case 0: + return c; + } + +#endif /* !valgrind */ + } + else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) + { + const uint16_t *k = (const uint16_t *) key; /* read 16-bit chunks */ + const uint8_t *k8; + + /*--------------- all but last block: aligned reads and different mixing + */ + while (length > 12) + { + a += k[0] + (((uint32_t) k[1]) << 16); + b += k[2] + (((uint32_t) k[3]) << 16); + c += k[4] + (((uint32_t) k[5]) << 16); + mix (a, b, c); + length -= 12; + k += 6; + } + + /*----------------------------- handle the last (probably partial) block + */ + k8 = (const uint8_t *) k; + switch (length) + { + case 12: + c += k[4] + (((uint32_t) k[5]) << 16); + b += k[2] + (((uint32_t) k[3]) << 16); + a += k[0] + (((uint32_t) k[1]) << 16); + break; + case 11: + c += ((uint32_t) k8[10]) << 16; /* fall through */ + case 10: + c += k[4]; + b += k[2] + (((uint32_t) k[3]) << 16); + a += k[0] + (((uint32_t) k[1]) << 16); + break; + case 9: + c += k8[8]; /* fall through */ + case 8: + b += k[2] + (((uint32_t) k[3]) << 16); + a += k[0] + (((uint32_t) k[1]) << 16); + break; + case 7: + b += ((uint32_t) k8[6]) << 16; /* fall through */ + case 6: + b += k[2]; + a += k[0] + (((uint32_t) k[1]) << 16); + break; + case 5: + b += k8[4]; /* fall through */ + case 4: + a += k[0] + (((uint32_t) k[1]) << 16); + break; + case 3: + a += ((uint32_t) k8[2]) << 16; /* fall through */ + case 2: + a += k[0]; + break; + case 1: + a += k8[0]; + break; + case 0: + return c; /* zero length requires no mixing */ + } + } + else + { /* need to read the key one byte at a time */ + const uint8_t *k = (const uint8_t *) key; + + /*--------------- all but the last block: affect some 32 bits of (a,b,c) + */ + while (length > 12) + { + a += k[0]; + a += ((uint32_t) k[1]) << 8; + a += ((uint32_t) k[2]) << 16; + a += ((uint32_t) k[3]) << 24; + b += k[4]; + b += ((uint32_t) k[5]) << 8; + b += ((uint32_t) k[6]) << 16; + b += ((uint32_t) k[7]) << 24; + c += k[8]; + c += ((uint32_t) k[9]) << 8; + c += ((uint32_t) k[10]) << 16; + c += ((uint32_t) k[11]) << 24; + mix (a, b, c); + length -= 12; + k += 12; + } + + /*-------------------------------- last block: affect all 32 bits of (c) + */ + switch (length) /* all the case statements fall through */ + { + case 12: + c += ((uint32_t) k[11]) << 24; + case 11: + c += ((uint32_t) k[10]) << 16; + case 10: + c += ((uint32_t) k[9]) << 8; + case 9: + c += k[8]; + case 8: + b += ((uint32_t) k[7]) << 24; + case 7: + b += ((uint32_t) k[6]) << 16; + case 6: + b += ((uint32_t) k[5]) << 8; + case 5: + b += k[4]; + case 4: + a += ((uint32_t) k[3]) << 24; + case 3: + a += ((uint32_t) k[2]) << 16; + case 2: + a += ((uint32_t) k[1]) << 8; + case 1: + a += k[0]; + break; + case 0: + return c; + } + } + + final (a, b, c); + return c; +} + +/* Helpers */ + +#define HASH_INITVAL 1 +//#define hash(buf, len) (hash_t)hashlittle(buf, len, HASH_INITVAL) +#define hash(buf, len) hashlittle (buf, len, HASH_INITVAL) +#define hash_struct(buf) hash (buf, sizeof (*buf)) + +#define str_hash(str) (hash (str, strlen (str))) +#define str_hash_eq(a, b) (str_hash (b) - str_hash (a)) + +#endif /* UTIL_JENKINS_HASH_H */ diff --git a/lib/includes/hicn/util/ip_address.h b/lib/includes/hicn/util/ip_address.h index 4facd9ad0..979efaa40 100644 --- a/lib/includes/hicn/util/ip_address.h +++ b/lib/includes/hicn/util/ip_address.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Copyright (c) 2021-2022 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: @@ -20,10 +20,9 @@ #ifndef UTIL_IP_ADDRESS_H #define UTIL_IP_ADDRESS_H - #ifdef __APPLE__ #include <libkern/OSByteOrder.h> -#define __bswap_constant_32(x) OSSwapInt32(x) +#define __bswap_constant_32(x) OSSwapInt32 (x) #include <machine/endian.h> #else #ifdef __ANDROID__ @@ -33,10 +32,11 @@ #endif #include <errno.h> +#include <assert.h> #ifndef _WIN32 -#include <netinet/in.h> // struct sockadd -#include <arpa/inet.h> // inet_ntop -#include <netdb.h> // struct addrinfo +#include <netinet/in.h> // struct sockadd +#include <arpa/inet.h> // inet_ntop +#include <netdb.h> // struct addrinfo #endif #include <stdbool.h> #include <stdlib.h> @@ -45,11 +45,12 @@ #include "types.h" -#define bytes_to_bits(x) (x * 8) -#define IPV6_ADDR_LEN 16 /* bytes */ -#define IPV4_ADDR_LEN 4 /* bytes */ -#define IPV6_ADDR_LEN_BITS bytes_to_bits(IPV6_ADDR_LEN) -#define IPV4_ADDR_LEN_BITS bytes_to_bits(IPV4_ADDR_LEN) +#define bytes_to_bits(x) (x * 8) +#define IPV6_ADDR_LEN 16 /* bytes */ +#define IPV4_ADDR_LEN 4 /* bytes */ +#define IPV6_ADDR_LEN_BITS bytes_to_bits (IPV6_ADDR_LEN) +#define IPV4_ADDR_LEN_BITS bytes_to_bits (IPV4_ADDR_LEN) +#define MAX_IPV6_PREFIX_LEN 128 /* Presentation format */ #ifndef INET_ADDRSTRLEN @@ -61,29 +62,47 @@ #endif //#define INET_MAX_ADDRSTRLEN INET6_ADDRSTRLEN -#define IP_MAX_ADDR_LEN IPV6_ADDR_LEN +#define IP_ADDRESS_MAX_LEN IPV6_ADDR_LEN #define DUMMY_PORT 1234 -typedef union { - struct { - u32 pad[3]; - union { - struct in_addr as_inaddr; - u8 buffer[4]; - u8 as_u8[4]; - u16 as_u16[2]; - u32 as_u32; - } v4; - }; - union { - struct in6_addr as_in6addr; - u8 buffer[16]; - u8 as_u8[16]; - u16 as_u16[8]; - u32 as_u32[4]; - u64 as_u64[2]; - } v6; +typedef union +{ + struct in_addr as_inaddr; + u8 buffer[4]; + u8 as_u8[4]; + u16 as_u16[2]; + u32 as_u32; +} ipv4_address_t; + +static_assert (sizeof (ipv4_address_t) == 4, ""); + +typedef union __attribute__ ((__packed__)) +{ + struct in6_addr as_in6addr; + u8 buffer[16]; + u8 as_u8[16]; + u16 as_u16[8]; + u32 as_u32[4]; + u64 as_u64[2]; +} ipv6_address_t; + +static_assert (sizeof (ipv6_address_t) == 16, ""); + +#ifdef HICN_VPP_PLUGIN +#include <vnet/ip/ip46_address.h> +static_assert (sizeof (ipv4_address_t) == sizeof (ip4_address_t), ""); +static_assert (sizeof (ipv6_address_t) == sizeof (ip6_address_t), ""); +#endif + +typedef union +{ + struct + { + u32 pad[3]; + ipv4_address_t v4; + }; + ipv6_address_t v6; #if 0 /* removed as prone to error due to IPv4 padding */ u8 buffer[IP_MAX_ADDR_LEN]; u8 as_u8[IP_MAX_ADDR_LEN]; @@ -91,79 +110,117 @@ typedef union { u32 as_u32[IP_MAX_ADDR_LEN >> 2]; u64 as_u64[IP_MAX_ADDR_LEN >> 3]; #endif -} ip_address_t; +#ifdef HICN_VPP_PLUGIN + ip46_address_t as_ip46; +#endif /* HICN_VPP_PLUGIN */ +} hicn_ip_address_t; + +static_assert (sizeof (hicn_ip_address_t) == 16, ""); + +#define hicn_ip_address_is_v4(ip) \ + (((ip)->pad[0] | (ip)->pad[1] | (ip)->pad[2]) == 0) #define MAXSZ_IP4_ADDRESS_ INET_ADDRSTRLEN - 1 #define MAXSZ_IP6_ADDRESS_ INET6_ADDRSTRLEN - 1 -#define MAXSZ_IP_ADDRESS_ MAXSZ_IP6_ADDRESS_ -#define MAXSZ_IP4_ADDRESS MAXSZ_IP4_ADDRESS_ + 1 -#define MAXSZ_IP6_ADDRESS MAXSZ_IP6_ADDRESS_ + 1 -#define MAXSZ_IP_ADDRESS MAXSZ_IP_ADDRESS_ + 1 +#define MAXSZ_IP_ADDRESS_ MAXSZ_IP6_ADDRESS_ +#define MAXSZ_IP4_ADDRESS MAXSZ_IP4_ADDRESS_ + 1 +#define MAXSZ_IP6_ADDRESS MAXSZ_IP6_ADDRESS_ + 1 +#define MAXSZ_IP_ADDRESS MAXSZ_IP_ADDRESS_ + 1 -typedef struct { +#define IP_ADDRESS_V4_OFFSET_LEN 12 + +typedef struct +{ int family; - ip_address_t address; + hicn_ip_address_t address; u8 len; -} ip_prefix_t; +} hicn_ip_prefix_t; -#define MAXSZ_PREFIX_ MAXSZ_IP_ADDRESS_ + 1 + 3 -#define MAXSZ_PREFIX MAXSZ_PREFIX_ + 1 +#define MAXSZ_IP_PREFIX_ MAXSZ_IP_ADDRESS_ + 1 + 3 +#define MAXSZ_IP_PREFIX MAXSZ_IP_PREFIX_ + 1 -extern const ip_address_t IPV4_LOOPBACK; -extern const ip_address_t IPV6_LOOPBACK; -extern const ip_address_t IPV4_ANY; -extern const ip_address_t IPV6_ANY; -extern const ip_address_t IP_ADDRESS_EMPTY; +extern const hicn_ip_address_t IPV4_LOOPBACK; +extern const hicn_ip_address_t IPV6_LOOPBACK; +extern const hicn_ip_address_t IPV4_ANY; +extern const hicn_ip_address_t IPV6_ANY; -#define IP_ANY(family) (family == AF_INET) ? IPV4_ANY : IPV6_ANY +extern const ipv4_address_t IP4_ADDRESS_EMPTY; +extern const ipv6_address_t IP6_ADDRESS_EMPTY; +extern const hicn_ip_address_t IP_ADDRESS_EMPTY; +#define IP_ANY(family) (family == AF_INET) ? IPV4_ANY : IPV6_ANY -#define MAX_PORT 1 << (8 * sizeof(u16)) -#define IS_VALID_PORT(x) ((x > 0) && ((int)x < MAX_PORT)) +#define MAX_PORT 1 << (8 * sizeof (u16)) +#define IS_VALID_PORT(x) ((x > 0) && ((int) x < MAX_PORT)) #define MAXSZ_PORT_ 5 -#define MAXSZ_PORT MAXSZ_PORT_ + 1 +#define MAXSZ_PORT MAXSZ_PORT_ + 1 #define IS_VALID_FAMILY(x) ((x == AF_INET) || (x == AF_INET6)) /* IP address */ - -int ip_address_get_family (const char * ip_address); -int ip_address_len (int family); -const u8 * ip_address_get_buffer(const ip_address_t * ip_address, int family); -int ip_address_ntop (const ip_address_t * ip_address, char *dst, - const size_t len, int family); -int ip_address_pton (const char *ip_address_str, ip_address_t * ip_address); -int ip_address_snprintf(char * s, size_t size, const ip_address_t * ip_address, - int family); -int ip_address_to_sockaddr(const ip_address_t * ip_address, struct sockaddr *sa, - int family); -int ip_address_cmp(const ip_address_t * ip1, const ip_address_t * ip2, int family); -int ip_address_empty(const ip_address_t * ip); +int hicn_ip_address_get_family (const hicn_ip_address_t *address); +int hicn_ip_address_str_get_family (const char *ip_address); +int hicn_ip_address_len (int family); +int hicn_ip_address_get_len (const hicn_ip_address_t *ip_address); + +int hicn_ip_address_get_len_bits (const hicn_ip_address_t *ip_address); +const u8 *hicn_ip_address_get_buffer (const hicn_ip_address_t *ip_address, + int family); +int hicn_ip_address_ntop (const hicn_ip_address_t *ip_address, char *dst, + const size_t len, int family); +int hicn_ip_address_pton (const char *ip_address_str, + hicn_ip_address_t *ip_address); +int hicn_ip_address_snprintf (char *s, size_t size, + const hicn_ip_address_t *ip_address); +int hicn_ip_address_to_sockaddr (const hicn_ip_address_t *ip_address, + struct sockaddr *sa, int family); +int hicn_ip_address_cmp (const hicn_ip_address_t *ip1, + const hicn_ip_address_t *ip2); +bool hicn_ip_address_equals (const hicn_ip_address_t *ip1, + const hicn_ip_address_t *ip2); +int hicn_ip_address_empty (const hicn_ip_address_t *ip); + +uint8_t hicn_ip_address_get_bit (const hicn_ip_address_t *address, + uint8_t pos); + +bool hicn_ip_address_match_family (const hicn_ip_address_t *address, + int family); + +uint32_t hicn_ip_address_get_hash (const hicn_ip_address_t *address); + +void hicn_ip_address_clear (hicn_ip_address_t *address); /* Prefix */ -int ip_prefix_pton (const char *ip_address_str, ip_prefix_t * ip_prefix); -int ip_prefix_ntop_short (const ip_prefix_t * ip_prefix, char *dst, size_t size); -int ip_prefix_ntop (const ip_prefix_t * ip_prefix, char *dst, size_t size); -int ip_prefix_len (const ip_prefix_t * prefix); -bool ip_prefix_empty (const ip_prefix_t * prefix); -int ip_prefix_to_sockaddr(const ip_prefix_t * prefix, struct sockaddr *sa); -int ip_prefix_cmp(const ip_prefix_t * prefix1, const ip_prefix_t * prefix2); +int hicn_ip_prefix_pton (const char *ip_address_str, + hicn_ip_prefix_t *hicn_ip_prefix); +int hicn_ip_prefix_ntop_short (const hicn_ip_prefix_t *hicn_ip_prefix, + char *dst, size_t size); +int hicn_ip_prefix_ntop (const hicn_ip_prefix_t *hicn_ip_prefix, char *dst, + size_t size); +int hicn_ip_prefix_snprintf (char *s, size_t size, + const hicn_ip_prefix_t *prefix); +int hicn_ip_prefix_len (const hicn_ip_prefix_t *prefix); +bool hicn_ip_prefix_empty (const hicn_ip_prefix_t *prefix); +int hicn_ip_prefix_to_sockaddr (const hicn_ip_prefix_t *prefix, + struct sockaddr *sa); +int hicn_ip_prefix_cmp (const hicn_ip_prefix_t *prefix1, + const hicn_ip_prefix_t *prefix2); /* URL */ #define MAXSZ_PROTO_ 8 /* inetX:// */ -#define MAXSZ_PROTO MAXSZ_PROTO_ + NULLTERM +#define MAXSZ_PROTO MAXSZ_PROTO_ + NULLTERM #define MAXSZ_URL4_ MAXSZ_PROTO_ + MAXSZ_IP4_ADDRESS_ + MAXSZ_PORT_ #define MAXSZ_URL6_ MAXSZ_PROTO_ + MAXSZ_IP6_ADDRESS_ + MAXSZ_PORT_ -#define MAXSZ_URL_ MAXSZ_URL6_ -#define MAXSZ_URL4 MAXSZ_URL4_ + NULLTERM -#define MAXSZ_URL6 MAXSZ_URL6_ + NULLTERM -#define MAXSZ_URL MAXSZ_URL_ + NULLTERM +#define MAXSZ_URL_ MAXSZ_URL6_ +#define MAXSZ_URL4 MAXSZ_URL4_ + NULLTERM +#define MAXSZ_URL6 MAXSZ_URL6_ + NULLTERM +#define MAXSZ_URL MAXSZ_URL_ + NULLTERM -int url_snprintf(char * s, size_t size, int family, - const ip_address_t * ip_address, u16 port); +int url_snprintf (char *s, size_t size, const hicn_ip_address_t *ip_address, + u16 port); #endif /* UTIL_IP_ADDRESS_H */ diff --git a/lib/includes/hicn/util/khash.h b/lib/includes/hicn/util/khash.h new file mode 100644 index 000000000..17401091f --- /dev/null +++ b/lib/includes/hicn/util/khash.h @@ -0,0 +1,826 @@ +/* The MIT License + + Copyright (c) 2008, 2009, 2011 by Attractive Chaos <attractor@live.co.uk> + + 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. +*/ + +/* + An example: + +#include "khash.h" +KHASH_MAP_INIT_INT(32, char) +int main() { + int ret, is_missing; + khiter_t k; + khash_t(32) *h = kh_init(32); + k = kh_put(32, h, 5, &ret); + kh_value(h, k) = 10; + k = kh_get(32, h, 10); + is_missing = (k == kh_end(h)); + k = kh_get(32, h, 5); + kh_del(32, h, k); + for (k = kh_begin(h); k != kh_end(h); ++k) + if (kh_exist(h, k)) kh_value(h, k) = 1; + kh_destroy(32, h); + return 0; +} +*/ + +/* + 2013-05-02 (0.2.8): + + * Use quadratic probing. When the capacity is power of 2, stepping + function i*(i+1)/2 guarantees to traverse each bucket. It is better than + double hashing on cache performance and is more robust than linear probing. + + In theory, double hashing should be more robust than quadratic + probing. However, my implementation is probably not for large hash tables, + because the second hash function is closely tied to the first hash function, + which reduce the effectiveness of double hashing. + + Reference: http://research.cs.vt.edu/AVresearch/hashing/quadratic.php + + 2011-12-29 (0.2.7): + + * Minor code clean up; no actual effect. + + 2011-09-16 (0.2.6): + + * The capacity is a power of 2. This seems to dramatically improve the + speed for simple keys. Thank Zilong Tan for the suggestion. + Reference: + + - http://code.google.com/p/ulib/ + - http://nothings.org/computer/judy/ + + * Allow to optionally use linear probing which usually has better + performance for random input. Double hashing is still the default as + it is more robust to certain non-random input. + + * Added Wang's integer hash function (not used by default). This hash + function is more robust to certain non-random input. + + 2011-02-14 (0.2.5): + + * Allow to declare global functions. + + 2009-09-26 (0.2.4): + + * Improve portability + + 2008-09-19 (0.2.3): + + * Corrected the example + * Improved interfaces + + 2008-09-11 (0.2.2): + + * Improved speed a little in kh_put() + + 2008-09-10 (0.2.1): + + * Added kh_clear() + * Fixed a compiling error + + 2008-09-02 (0.2.0): + + * Changed to token concatenation which increases flexibility. + + 2008-08-31 (0.1.2): + + * Fixed a bug in kh_get(), which has not been tested previously. + + 2008-08-31 (0.1.1): + + * Added destructor +*/ + +#ifndef __AC_KHASH_H +#define __AC_KHASH_H + +/*! + @header + + Generic hash table library. + */ + +#define AC_VERSION_KHASH_H "0.2.8" + +#include <stdlib.h> +#include <string.h> +#include <limits.h> + +/* compiler specific configuration */ + +#if UINT_MAX == 0xffffffffu +typedef unsigned int khint32_t; +#elif ULONG_MAX == 0xffffffffu +typedef unsigned long khint32_t; +#endif + +#if ULONG_MAX == ULLONG_MAX +typedef unsigned long khint64_t; +#else +typedef unsigned long long khint64_t; +#endif + +#ifndef kh_inline +#ifdef _MSC_VER +#define kh_inline __inline +#else +#define kh_inline inline +#endif +#endif /* kh_inline */ + +#ifndef klib_unused +#if (defined __clang__ && __clang_major__ >= 3) || \ + (defined __GNUC__ && __GNUC__ >= 3) +#define klib_unused __attribute__ ((__unused__)) +#else +#define klib_unused +#endif +#endif /* klib_unused */ + +typedef khint32_t khint_t; +typedef khint_t khiter_t; + +#define __ac_isempty(flag, i) ((flag[i >> 4] >> ((i & 0xfU) << 1)) & 2) +#define __ac_isdel(flag, i) ((flag[i >> 4] >> ((i & 0xfU) << 1)) & 1) +#define __ac_iseither(flag, i) ((flag[i >> 4] >> ((i & 0xfU) << 1)) & 3) +#define __ac_set_isdel_false(flag, i) \ + (flag[i >> 4] &= ~(1ul << ((i & 0xfU) << 1))) +#define __ac_set_isempty_false(flag, i) \ + (flag[i >> 4] &= ~(2ul << ((i & 0xfU) << 1))) +#define __ac_set_isboth_false(flag, i) \ + (flag[i >> 4] &= ~(3ul << ((i & 0xfU) << 1))) +#define __ac_set_isdel_true(flag, i) (flag[i >> 4] |= 1ul << ((i & 0xfU) << 1)) + +#define __ac_fsize(m) ((m) < 16 ? 1 : (m) >> 4) + +#ifndef kroundup32 +#define kroundup32(x) \ + (--(x), (x) |= (x) >> 1, (x) |= (x) >> 2, (x) |= (x) >> 4, (x) |= (x) >> 8, \ + (x) |= (x) >> 16, ++(x)) +#endif + +#ifndef kcalloc +#define kcalloc(N, Z) calloc (N, Z) +#endif +#ifndef kmalloc +#define kmalloc(Z) malloc (Z) +#endif +#ifndef krealloc +#define krealloc(P, Z) realloc (P, Z) +#endif +#ifndef kfree +#define kfree(P) free (P) +#endif + +static const double __ac_HASH_UPPER = 0.77; + +#define __KHASH_TYPE(name, khkey_t, khval_t) \ + typedef struct kh_##name##_s \ + { \ + khint_t n_buckets, size, n_occupied, upper_bound; \ + khint32_t *flags; \ + khkey_t *keys; \ + khval_t *vals; \ + } kh_##name##_t; + +#define __KHASH_PROTOTYPES(name, khkey_t, khval_t) \ + extern kh_##name##_t *kh_init_##name (void); \ + extern void kh_destroy_##name (kh_##name##_t *h); \ + extern void kh_clear_##name (kh_##name##_t *h); \ + extern khint_t kh_get_##name (const kh_##name##_t *h, khkey_t key); \ + extern int kh_resize_##name (kh_##name##_t *h, khint_t new_n_buckets); \ + extern khint_t kh_put_##name (kh_##name##_t *h, khkey_t key, int *ret); \ + extern void kh_del_##name (kh_##name##_t *h, khint_t x); + +#define __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, \ + __hash_equal) \ + SCOPE kh_##name##_t *kh_init_##name (void) \ + { \ + return (kh_##name##_t *) kcalloc (1, sizeof (kh_##name##_t)); \ + } \ + SCOPE void kh_destroy_##name (kh_##name##_t *h) \ + { \ + if (h) \ + { \ + kfree ((void *) h->keys); \ + kfree (h->flags); \ + kfree ((void *) h->vals); \ + kfree (h); \ + } \ + } \ + SCOPE void kh_clear_##name (kh_##name##_t *h) \ + { \ + if (h && h->flags) \ + { \ + memset (h->flags, 0xaa, \ + __ac_fsize (h->n_buckets) * sizeof (khint32_t)); \ + h->size = h->n_occupied = 0; \ + } \ + } \ + SCOPE khint_t kh_get_##name (const kh_##name##_t *h, khkey_t key) \ + { \ + if (h->n_buckets) \ + { \ + khint_t k, i, last, mask, step = 0; \ + mask = h->n_buckets - 1; \ + k = __hash_func (key); \ + i = k & mask; \ + last = i; \ + while (!__ac_isempty (h->flags, i) && \ + (__ac_isdel (h->flags, i) || !__hash_equal (h->keys[i], key))) \ + { \ + i = (i + (++step)) & mask; \ + if (i == last) \ + return h->n_buckets; \ + } \ + return __ac_iseither (h->flags, i) ? h->n_buckets : i; \ + } \ + else \ + return 0; \ + } \ + SCOPE int kh_resize_##name (kh_##name##_t *h, khint_t new_n_buckets) \ + { /* This function uses 0.25*n_buckets bytes of \ + working space instead of \ + [sizeof(key_t+val_t)+.25]*n_buckets. */ \ + khint32_t *new_flags = 0; \ + khint_t j = 1; \ + { \ + kroundup32 (new_n_buckets); \ + if (new_n_buckets < 4) \ + new_n_buckets = 4; \ + if (h->size >= (khint_t) (new_n_buckets * __ac_HASH_UPPER + 0.5)) \ + j = 0; /* requested size is too small */ \ + else \ + { /* hash table size to be changed (shrink or expand); rehash */ \ + new_flags = (khint32_t *) kmalloc (__ac_fsize (new_n_buckets) * \ + sizeof (khint32_t)); \ + if (!new_flags) \ + return -1; \ + memset (new_flags, 0xaa, \ + __ac_fsize (new_n_buckets) * sizeof (khint32_t)); \ + if (h->n_buckets < new_n_buckets) \ + { /* expand */ \ + khkey_t *new_keys = (khkey_t *) krealloc ( \ + (void *) h->keys, new_n_buckets * sizeof (khkey_t)); \ + if (!new_keys) \ + { \ + kfree (new_flags); \ + return -1; \ + } \ + h->keys = new_keys; \ + if (kh_is_map) \ + { \ + khval_t *new_vals = (khval_t *) krealloc ( \ + (void *) h->vals, new_n_buckets * sizeof (khval_t)); \ + if (!new_vals) \ + { \ + kfree (new_flags); \ + return -1; \ + } \ + h->vals = new_vals; \ + } \ + } /* otherwise shrink */ \ + } \ + } \ + if (j) \ + { /* rehashing is needed */ \ + for (j = 0; j != h->n_buckets; ++j) \ + { \ + if (__ac_iseither (h->flags, j) == 0) \ + { \ + khkey_t key = h->keys[j]; \ + khval_t val; \ + khint_t new_mask; \ + new_mask = new_n_buckets - 1; \ + if (kh_is_map) \ + val = h->vals[j]; \ + __ac_set_isdel_true (h->flags, j); \ + while (1) \ + { /* kick-out process; sort of like in Cuckoo hashing */ \ + khint_t k, i, step = 0; \ + k = __hash_func (key); \ + i = k & new_mask; \ + while (!__ac_isempty (new_flags, i)) \ + i = (i + (++step)) & new_mask; \ + __ac_set_isempty_false (new_flags, i); \ + if (i < h->n_buckets && __ac_iseither (h->flags, i) == 0) \ + { /* kick out the existing element */ \ + { \ + khkey_t tmp = h->keys[i]; \ + h->keys[i] = key; \ + key = tmp; \ + } \ + if (kh_is_map) \ + { \ + khval_t tmp = h->vals[i]; \ + h->vals[i] = val; \ + val = tmp; \ + } \ + __ac_set_isdel_true ( \ + h->flags, \ + i); /* mark it as deleted in the old hash table */ \ + } \ + else \ + { /* write the element and jump out of the loop */ \ + h->keys[i] = key; \ + if (kh_is_map) \ + h->vals[i] = val; \ + break; \ + } \ + } \ + } \ + } \ + if (h->n_buckets > new_n_buckets) \ + { /* shrink the hash table */ \ + h->keys = (khkey_t *) krealloc ( \ + (void *) h->keys, new_n_buckets * sizeof (khkey_t)); \ + if (kh_is_map) \ + h->vals = (khval_t *) krealloc ( \ + (void *) h->vals, new_n_buckets * sizeof (khval_t)); \ + } \ + kfree (h->flags); /* free the working space */ \ + h->flags = new_flags; \ + h->n_buckets = new_n_buckets; \ + h->n_occupied = h->size; \ + h->upper_bound = (khint_t) (h->n_buckets * __ac_HASH_UPPER + 0.5); \ + } \ + return 0; \ + } \ + SCOPE khint_t kh_put_##name (kh_##name##_t *h, khkey_t key, int *ret) \ + { \ + khint_t x; \ + if (h->n_occupied >= h->upper_bound) \ + { /* update the hash table */ \ + if (h->n_buckets > (h->size << 1)) \ + { \ + if (kh_resize_##name (h, h->n_buckets - 1) < 0) \ + { /* clear "deleted" elements */ \ + *ret = -1; \ + return h->n_buckets; \ + } \ + } \ + else if (kh_resize_##name (h, h->n_buckets + 1) < 0) \ + { /* expand the hash table */ \ + *ret = -1; \ + return h->n_buckets; \ + } \ + } /* TODO: to implement automatically shrinking; resize() already \ + support shrinking */ \ + { \ + khint_t k, i, site, last, mask = h->n_buckets - 1, step = 0; \ + x = site = h->n_buckets; \ + k = __hash_func (key); \ + i = k & mask; \ + if (__ac_isempty (h->flags, i)) \ + x = i; /* for speed up */ \ + else \ + { \ + last = i; \ + while ( \ + !__ac_isempty (h->flags, i) && \ + (__ac_isdel (h->flags, i) || !__hash_equal (h->keys[i], key))) \ + { \ + if (__ac_isdel (h->flags, i)) \ + site = i; \ + i = (i + (++step)) & mask; \ + if (i == last) \ + { \ + x = site; \ + break; \ + } \ + } \ + if (x == h->n_buckets) \ + { \ + if (__ac_isempty (h->flags, i) && site != h->n_buckets) \ + x = site; \ + else \ + x = i; \ + } \ + } \ + } \ + if (__ac_isempty (h->flags, x)) \ + { /* not present at all */ \ + h->keys[x] = key; \ + __ac_set_isboth_false (h->flags, x); \ + ++h->size; \ + ++h->n_occupied; \ + *ret = 1; \ + } \ + else if (__ac_isdel (h->flags, x)) \ + { /* deleted */ \ + h->keys[x] = key; \ + __ac_set_isboth_false (h->flags, x); \ + ++h->size; \ + *ret = 2; \ + } \ + else \ + *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \ + return x; \ + } \ + SCOPE void kh_del_##name (kh_##name##_t *h, khint_t x) \ + { \ + if (x != h->n_buckets && !__ac_iseither (h->flags, x)) \ + { \ + __ac_set_isdel_true (h->flags, x); \ + --h->size; \ + } \ + } + +#define KHASH_DECLARE(name, khkey_t, khval_t) \ + __KHASH_TYPE (name, khkey_t, khval_t) \ + __KHASH_PROTOTYPES (name, khkey_t, khval_t) + +#define KHASH_INIT2(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, \ + __hash_equal) \ + __KHASH_TYPE (name, khkey_t, khval_t) \ + __KHASH_IMPL (name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, \ + __hash_equal) + +#define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, \ + __hash_equal) \ + KHASH_INIT2 (name, static kh_inline klib_unused, khkey_t, khval_t, \ + kh_is_map, __hash_func, __hash_equal) + +/* --- BEGIN OF HASH FUNCTIONS --- */ + +/*! @function + @abstract Integer hash function + @param key The integer [khint32_t] + @return The hash value [khint_t] + */ +#define kh_int_hash_func(key) (khint32_t) (key) +/*! @function + @abstract Integer comparison function + */ +#define kh_int_hash_equal(a, b) ((a) == (b)) +/*! @function + @abstract 64-bit integer hash function + @param key The integer [khint64_t] + @return The hash value [khint_t] + */ +#define kh_int64_hash_func(key) (khint32_t) ((key) >> 33 ^ (key) ^ (key) << 11) +/*! @function + @abstract 64-bit integer comparison function + */ +#define kh_int64_hash_equal(a, b) ((a) == (b)) +/*! @function + @abstract const char* hash function + @param s Pointer to a null terminated string + @return The hash value + */ +static kh_inline khint_t +__ac_X31_hash_string (const char *s) +{ + khint_t h = (khint_t) *s; + if (h) + for (++s; *s; ++s) + h = (h << 5) - h + (khint_t) *s; + return h; +} +/*! @function + @abstract Another interface to const char* hash function + @param key Pointer to a null terminated string [const char*] + @return The hash value [khint_t] + */ +#define kh_str_hash_func(key) __ac_X31_hash_string (key) +/*! @function + @abstract Const char* comparison function + */ +#define kh_str_hash_equal(a, b) (strcmp (a, b) == 0) + +static kh_inline khint_t +__ac_Wang_hash (khint_t key) +{ + key += ~(key << 15); + key ^= (key >> 10); + key += (key << 3); + key ^= (key >> 6); + key += ~(key << 11); + key ^= (key >> 16); + return key; +} +#define kh_int_hash_func2(key) __ac_Wang_hash ((khint_t) key) + +/* --- END OF HASH FUNCTIONS --- */ + +/* Other convenient macros... */ + +/*! + @abstract Type of the hash table. + @param name Name of the hash table [symbol] + */ +#define khash_t(name) kh_##name##_t + +/*! @function + @abstract Initiate a hash table. + @param name Name of the hash table [symbol] + @return Pointer to the hash table [khash_t(name)*] + */ +#define kh_init(name) kh_init_##name () + +/*! @function + @abstract Destroy a hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + */ +#define kh_destroy(name, h) kh_destroy_##name (h) + +/*! @function + @abstract Reset a hash table without deallocating memory. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + */ +#define kh_clear(name, h) kh_clear_##name (h) + +/*! @function + @abstract Resize a hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + @param s New size [khint_t] + */ +#define kh_resize(name, h, s) kh_resize_##name (h, s) + +/*! @function + @abstract Insert a key to the hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + @param k Key [type of keys] + @param r Extra return code: -1 if the operation failed; + 0 if the key is present in the hash table; + 1 if the bucket is empty (never used); 2 if the element in + the bucket has been deleted [int*] + @return Iterator to the inserted element [khint_t] + */ +#define kh_put(name, h, k, r) kh_put_##name (h, k, r) + +/*! @function + @abstract Retrieve a key from the hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + @param k Key [type of keys] + @return Iterator to the found element, or kh_end(h) if the element is + absent [khint_t] + */ +#define kh_get(name, h, k) kh_get_##name (h, k) + +/*! @function + @abstract Remove a key from the hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + @param k Iterator to the element to be deleted [khint_t] + */ +#define kh_del(name, h, k) kh_del_##name (h, k) + +/*! @function + @abstract Test whether a bucket contains data. + @param h Pointer to the hash table [khash_t(name)*] + @param x Iterator to the bucket [khint_t] + @return 1 if containing data; 0 otherwise [int] + */ +#define kh_exist(h, x) (!__ac_iseither ((h)->flags, (x))) + +/*! @function + @abstract Get key given an iterator + @param h Pointer to the hash table [khash_t(name)*] + @param x Iterator to the bucket [khint_t] + @return Key [type of keys] + */ +#define kh_key(h, x) ((h)->keys[x]) + +/*! @function + @abstract Get value given an iterator + @param h Pointer to the hash table [khash_t(name)*] + @param x Iterator to the bucket [khint_t] + @return Value [type of values] + @discussion For hash sets, calling this results in segfault. + */ +#define kh_val(h, x) ((h)->vals[x]) + +/*! @function + @abstract Alias of kh_val() + */ +#define kh_value(h, x) ((h)->vals[x]) + +/*! @function + @abstract Get the start iterator + @param h Pointer to the hash table [khash_t(name)*] + @return The start iterator [khint_t] + */ +#define kh_begin(h) (khint_t) (0) + +/*! @function + @abstract Get the end iterator + @param h Pointer to the hash table [khash_t(name)*] + @return The end iterator [khint_t] + */ +#define kh_end(h) ((h)->n_buckets) + +/*! @function + @abstract Get the number of elements in the hash table + @param h Pointer to the hash table [khash_t(name)*] + @return Number of elements in the hash table [khint_t] + */ +#define kh_size(h) ((h)->size) + +/*! @function + @abstract Get the number of buckets in the hash table + @param h Pointer to the hash table [khash_t(name)*] + @return Number of buckets in the hash table [khint_t] + */ +#define kh_n_buckets(h) ((h)->n_buckets) + +/*! @function + @abstract Iterate over the entries in the hash table + @param h Pointer to the hash table [khash_t(name)*] + @param kvar Variable to which key will be assigned + @param vvar Variable to which value will be assigned + @param code Block of code to execute + */ +#define kh_foreach(h, kvar, vvar, code) \ + { \ + khint_t __i; \ + for (__i = kh_begin (h); __i != kh_end (h); ++__i) \ + { \ + if (!kh_exist (h, __i)) \ + continue; \ + (kvar) = kh_key (h, __i); \ + (vvar) = kh_val (h, __i); \ + code; \ + } \ + } + +/*! @function + @abstract Iterate over the values in the hash table + @param h Pointer to the hash table [khash_t(name)*] + @param vvar Variable to which value will be assigned + @param code Block of code to execute + */ +#define kh_foreach_value(h, vvar, code) \ + { \ + khint_t __i; \ + for (__i = kh_begin (h); __i != kh_end (h); ++__i) \ + { \ + if (!kh_exist (h, __i)) \ + continue; \ + (vvar) = kh_val (h, __i); \ + code; \ + } \ + } + +/* More convenient interfaces */ + +/*! @function + @abstract Instantiate a hash set containing integer keys + @param name Name of the hash table [symbol] + */ +#define KHASH_SET_INIT_INT(name) \ + KHASH_INIT (name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal) + +/*! @function + @abstract Instantiate a hash map containing integer keys + @param name Name of the hash table [symbol] + @param khval_t Type of values [type] + */ +#define KHASH_MAP_INIT_INT(name, khval_t) \ + KHASH_INIT (name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal) + +/*! @function + @abstract Instantiate a hash set containing 64-bit integer keys + @param name Name of the hash table [symbol] + */ +#define KHASH_SET_INIT_INT64(name) \ + KHASH_INIT (name, khint64_t, char, 0, kh_int64_hash_func, \ + kh_int64_hash_equal) + +/*! @function + @abstract Instantiate a hash map containing 64-bit integer keys + @param name Name of the hash table [symbol] + @param khval_t Type of values [type] + */ +#define KHASH_MAP_INIT_INT64(name, khval_t) \ + KHASH_INIT (name, khint64_t, khval_t, 1, kh_int64_hash_func, \ + kh_int64_hash_equal) + +typedef const char *kh_cstr_t; +/*! @function + @abstract Instantiate a hash map containing const char* keys + @param name Name of the hash table [symbol] + */ +#define KHASH_SET_INIT_STR(name) \ + KHASH_INIT (name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal) + +/*! @function + @abstract Instantiate a hash map containing const char* keys + @param name Name of the hash table [symbol] + @param khval_t Type of values [type] + */ +#define KHASH_MAP_INIT_STR(name, khval_t) \ + KHASH_INIT (name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal) + +/****************************************************************************** + * Custom return codes + ******************************************************************************/ + +// RESET: same as added, but the key was already added in the past +#define foreach_kh_rc \ + _ (REPLACED) \ + _ (ADDED) \ + _ (RESET) \ + _ (NOT_FOUND) \ + _ (FOUND) \ + _ (FAIL) + +typedef enum +{ +#define _(x) KH_##x, + foreach_kh_rc +#undef _ +} kh_rc; + +/****************************************************************************** + * Custom + *high-level interface + ******************************************************************************/ + +#define _kh_var(x) _kh_var_##x + +/** + * @brief Return the value corresponding to a key in the hashtable. + * @return The value associated with the key or null if not found + */ +#define kh_get_val(kname, hashtable, key, default_val) \ + ({ \ + khiter_t _kh_var (k) = kh_get (kname, hashtable, key); \ + (_kh_var (k) != kh_end (hashtable) ? kh_val (hashtable, _kh_var (k)) : \ + default_val); \ + }) + +/** + * @brief Add key/value pair in the hashtable. + * @return 0 if an existing value (corresponding to the provided key) + * has been replaced; 1 if a new key/value pair has been added + * (the key was not already present in the hash table); + * 2 if a new key/value pair has been added in correspondence + * of a key previously deleted key + */ +#define kh_put_val(kname, hashtable, key, val) \ + ({ \ + int _kh_var (ret); \ + khiter_t _kh_var (k) = kh_put (kname, hashtable, key, &_kh_var (ret)); \ + kh_value (hashtable, _kh_var (k)) = val; \ + _kh_var (ret); \ + }) + +/** + * @brief Remove a key/value pair from the hashtable. + * @return void + */ +#define kh_remove_val(kname, hashtable, key) \ + ({ \ + khiter_t _kh_var (k) = kh_get (kname, hashtable, key); \ + if (_kh_var (k) != kh_end (hashtable)) \ + { \ + free ((void *) kh_key (hashtable, _kh_var (k))); \ + kh_del (kname, hashtable, _kh_var (k)); \ + } \ + }) + +/** + * @brief Free the hashtable. + * @return void + */ +#define kh_free(kname, hashtable) \ + ({ \ + const void *_kh_var (key); \ + unsigned _kh_var (val); \ + (void) _kh_var (val); \ + \ + kh_foreach (hashtable, _kh_var (key), _kh_var (val), { \ + free ((void *) _kh_var (key)); \ + }) kh_destroy (kname, hashtable); \ + }) + +#endif /* __AC_KHASH_H */ diff --git a/lib/includes/hicn/util/log.h b/lib/includes/hicn/util/log.h index 6763d464f..b9b7725d6 100644 --- a/lib/includes/hicn/util/log.h +++ b/lib/includes/hicn/util/log.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Copyright (c) 2021 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: @@ -17,53 +17,72 @@ #define UTIL_LOG_H #include <stdarg.h> // va_* -#include <stdio.h> // FILE -#include <time.h> // time, localtime +#include <stdio.h> // FILE +#include <time.h> // time, localtime -#define LOG_FATAL 0 -#define LOG_ERROR 1 -#define LOG_WARN 2 -#define LOG_INFO 3 -#define LOG_DEBUG 4 -#define LOG_TRACE 5 +typedef enum +{ + LOG_FATAL, + LOG_ERROR, + LOG_WARN, + LOG_INFO, + LOG_DEBUG, + LOG_TRACE +} log_level_t; -typedef struct { +typedef struct +{ int log_level; int debug; - FILE * log_file; + FILE *log_file; } log_conf_t; -#define DEFAULT_LOG_CONF { \ - .log_level = LOG_INFO, \ - .debug = 0, \ - .log_file = NULL, \ -}; +#define DEFAULT_LOG_CONF \ + { \ + .log_level = LOG_INFO, \ + .debug = 0, \ + .log_file = NULL, \ + }; extern log_conf_t log_conf; -#define WITH_DEBUG(BLOCK) \ - if (log_conf.log_level >= LOG_DEBUG) \ - BLOCK +#define WITH_ERROR(BLOCK) \ + if (log_conf.log_level >= LOG_ERROR) \ + BLOCK +#define WITH_WARN(BLOCK) \ + if (log_conf.log_level >= LOG_WARN) \ + BLOCK +#define WITH_INFO(BLOCK) \ + if (log_conf.log_level >= LOG_INFO) \ + BLOCK +#define WITH_DEBUG(BLOCK) \ + if (log_conf.log_level >= LOG_DEBUG) \ + BLOCK +#define WITH_TRACE(BLOCK) \ + if (log_conf.log_level >= LOG_TRACE) \ + BLOCK -#define FATAL(fmt, ...) (_log(LOG_FATAL, fmt, ##__VA_ARGS__ )) +#define FATAL(fmt, ...) (_log (LOG_FATAL, fmt, ##__VA_ARGS__)) #ifdef ERROR #undef ERROR #endif -#define ERROR(fmt, ...) (_log(LOG_ERROR, fmt, ##__VA_ARGS__ )) -#define WARN(fmt, ...) (_log(LOG_WARN, fmt, ##__VA_ARGS__ )) -#define INFO(fmt, ...) (_log(LOG_INFO, fmt, ##__VA_ARGS__ )) -#define DEBUG(fmt, ...) (_log(LOG_DEBUG, fmt, ##__VA_ARGS__ )) -#define TRACE(fmt, ...) (_log(LOG_TRACE, fmt, ##__VA_ARGS__ )) +#define ERROR(fmt, ...) (_log (LOG_ERROR, fmt, ##__VA_ARGS__)) +#define WARN(fmt, ...) (_log (LOG_WARN, fmt, ##__VA_ARGS__)) +#define INFO(fmt, ...) (_log (LOG_INFO, fmt, ##__VA_ARGS__)) +#define DEBUG(fmt, ...) (_log (LOG_DEBUG, fmt, ##__VA_ARGS__)) +#define TRACE(fmt, ...) (_log (LOG_TRACE, fmt, ##__VA_ARGS__)) -void _log_va(int level, const char *fmt, va_list ap); +void _log_va (int level, const char *fmt, va_list ap); -void _log(int level, const char *fmt, ...); +void _log (int level, const char *fmt, ...); -void fatal(char *fmt, ...); +void fatal (char *fmt, ...); + +int loglevel_from_str (const char *loglevel); #ifdef HAVE_BACKTRACE #include <execinfo.h> -void print_trace(void); +void print_trace (void); #endif #endif // UTIL_LOG_H diff --git a/lib/includes/hicn/util/map.h b/lib/includes/hicn/util/map.h index 01195865e..6e23f222f 100644 --- a/lib/includes/hicn/util/map.h +++ b/lib/includes/hicn/util/map.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Copyright (c) 2021 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: @@ -20,231 +20,227 @@ #include "set.h" -#define ERR_MAP_EXISTS -2 +#define ERR_MAP_EXISTS -2 #define ERR_MAP_NOT_FOUND -3 -#define TYPEDEF_MAP_H(NAME, KEY_T, VAL_T) \ - \ -typedef struct { \ - KEY_T key; \ - VAL_T value; \ -} NAME ## _pair_t; \ - \ -NAME ## _pair_t * NAME ## _pair_create(KEY_T key, VAL_T value); \ - \ -void NAME ## _pair_free(NAME ## _pair_t * pair); \ - \ -int NAME ## _pair_cmp(const NAME ## _pair_t * p1, const NAME ## _pair_t * p2); \ - \ -TYPEDEF_SET_H(NAME ## _pair_set, NAME ## _pair_t *) \ - \ -typedef struct NAME ## _s { \ - NAME ## _pair_set_t pair_set; \ -} NAME ## _t; \ - \ -int NAME ## _initialize(NAME ## _t * map); \ - \ -int NAME ## _finalize(NAME ## _t * map); \ - \ -NAME ## _t * NAME ## _create(); \ - \ -void NAME ## _free(NAME ## _t * map); \ - \ -int NAME ## _add(NAME ## _t * map, KEY_T key, VAL_T value); \ - \ -int NAME ## _remove(NAME ## _t * map, KEY_T key, VAL_T * value); \ - \ -int NAME ## _get(NAME ## _t * map, KEY_T key, VAL_T * value); \ - \ -void NAME ## _dump(NAME ## _t * map); +#define TYPEDEF_MAP_H(NAME, KEY_T, VAL_T) \ + \ + typedef struct \ + { \ + KEY_T key; \ + VAL_T value; \ + } NAME##_pair_t; \ + \ + NAME##_pair_t *NAME##_pair_create (KEY_T key, VAL_T value); \ + \ + void NAME##_pair_free (NAME##_pair_t *pair); \ + \ + int NAME##_pair_cmp (const NAME##_pair_t *p1, const NAME##_pair_t *p2); \ + \ + TYPEDEF_SET_H (NAME##_pair_set, NAME##_pair_t *) \ + \ + typedef struct NAME##_s \ + { \ + NAME##_pair_set_t pair_set; \ + } NAME##_t; \ + \ + int NAME##_initialize (NAME##_t *map); \ + \ + int NAME##_finalize (NAME##_t *map); \ + \ + NAME##_t *NAME##_create (); \ + \ + void NAME##_free (NAME##_t *map); \ + \ + int NAME##_add (NAME##_t *map, KEY_T key, VAL_T value); \ + \ + int NAME##_remove (NAME##_t *map, KEY_T key, VAL_T *value); \ + \ + int NAME##_get (NAME##_t *map, KEY_T key, VAL_T *value); \ + \ + void NAME##_dump (NAME##_t *map); \ + \ + int NAME##_get_key_array (NAME##_t *map, KEY_T **array); \ + \ + int NAME##_get_value_array (NAME##_t *map, VAL_T **array); - - - -#define TYPEDEF_MAP(NAME, KEY_T, VAL_T, CMP, KEY_SNPRINTF, VALUE_SNPRINTF) \ - \ -NAME ## _pair_t * NAME ## _pair_create(KEY_T key, VAL_T value) \ -{ \ - /* Create pair */ \ - NAME ## _pair_t * pair = malloc(sizeof(NAME ## _pair_t)); \ - if (!pair) \ - return NULL; \ - \ - pair->key = key; \ - pair->value = value; \ - \ - return pair; \ -} \ - \ -void NAME ## _pair_free(NAME ## _pair_t * pair) \ -{ \ - free(pair); \ -} \ - \ -int \ -NAME ## _pair_cmp(const NAME ## _pair_t * p1, const NAME ## _pair_t * p2) \ -{ \ - return (CMP(p1->key, p2->key)); \ -} \ - \ -int \ -NAME ## _pair_snprintf(char * buf, size_t size, const NAME ## _pair_t * pair) { \ - int rc; \ - rc = KEY_SNPRINTF(buf, BUFSIZE/2, (KEY_T)pair->key); \ - if (rc < 0) \ - return rc; \ - rc = VALUE_SNPRINTF(buf+rc, BUFSIZE/2, (VAL_T)pair->value); \ - return (int)rc; \ -} \ - \ -TYPEDEF_SET(NAME ## _pair_set, NAME ## _pair_t *, NAME ## _pair_cmp, NAME ## _pair_snprintf); \ - \ -int \ -NAME ## _initialize(NAME ## _t * map) \ -{ \ - return NAME ## _pair_set_initialize(&map->pair_set); \ -} \ - \ -int \ -NAME ## _finalize(NAME ## _t * map) \ -{ \ - NAME ## _pair_t ** array; \ - int n = NAME ## _pair_set_get_array(&map->pair_set, &array); \ - if (n < 0) \ - return -1; \ - for (unsigned i = 0; i < n; i++) { \ - NAME ## _pair_t * pair = array[i]; \ - NAME ## _pair_set_remove(&map->pair_set, pair, NULL); \ - NAME ## _pair_free(pair); \ - } \ - free(array); \ - return NAME ## _pair_set_finalize(&map->pair_set); \ -} \ - \ -NAME ## _t * \ -NAME ## _create() \ -{ \ - NAME ## _t * map = malloc(sizeof(NAME ## _t)); \ - if (!map) \ - goto ERR_MALLOC; \ - \ - if (NAME ## _initialize(map) < 0) \ - goto ERR_INITIALIZE; \ - \ - return map; \ - \ -ERR_INITIALIZE: \ - free(map); \ -ERR_MALLOC: \ - return NULL; \ -} \ - \ -void \ -NAME ## _free(NAME ## _t * map) \ -{ \ - NAME ## _finalize(map); \ - free(map); \ -} \ - \ -int \ -NAME ## _add(NAME ## _t * map, KEY_T key, VAL_T value) \ -{ \ - int rc; \ - NAME ## _pair_t * found = NULL; \ - \ - NAME ## _pair_t * pair = NAME ## _pair_create(key, value); \ - if (!pair) \ - return -1; \ - \ - rc = NAME ## _pair_set_get(&map->pair_set, pair, &found); \ - if (rc < 0) \ - return -1; \ - if (found) { \ - NAME ## _pair_free(pair); \ - return ERR_MAP_EXISTS; \ - } \ - \ - rc = NAME ## _pair_set_add(&map->pair_set, pair); \ - if (rc < 0) { \ - NAME ## _pair_free(pair); \ - return -1; \ - } \ - return 0; \ -} \ - \ -int \ -NAME ## _remove(NAME ## _t * map, KEY_T key, VAL_T * value) \ -{ \ - NAME ## _pair_t * found = NULL; \ - NAME ## _pair_t search = { .key = key }; \ - int rc = NAME ## _pair_set_remove(&map->pair_set, &search, &found); \ - if (rc < 0) \ - return ERR_MAP_NOT_FOUND; \ - if (value) \ - *value = found->value; \ - NAME ## _pair_free(found); \ - return 0; \ -} \ - \ -int \ -NAME ## _get(NAME ## _t * map, KEY_T key, VAL_T * value) \ -{ \ - NAME ## _pair_t * found = NULL, search = { .key = key }; \ - int rc = NAME ## _pair_set_get(&map->pair_set, &search, &found); \ - if (rc < 0) \ - return -1; \ - if (found) \ - *value = found->value; \ - return 0; \ -} \ - \ -void \ -NAME ## _dump(NAME ## _t * map) { \ - NAME ## _pair_set_dump(&map->pair_set); \ -} \ - \ -int \ -NAME ## _get_key_array(NAME ## _t * map, KEY_T **array) { \ - NAME ## _pair_t ** pair_array; \ - int n = NAME ## _pair_set_get_array(&map->pair_set, &pair_array); \ - if (n < 0) \ - return -1; \ - if (!array) \ - goto END; \ - /* Allocate result array */ \ - *array = malloc(n * sizeof(KEY_T)); \ - if (!array) { \ - free(pair_array); \ - return -1; \ - } \ - /* Copy keys */ \ - for (int i = 0; i < n; i++) \ - (*array)[i] = pair_array[i]->key; \ - free(pair_array); \ -END: \ - return n; \ -} \ - \ -int \ -NAME ## _get_value_array(NAME ## _t * map, VAL_T **array) { \ - NAME ## _pair_t ** pair_array; \ - int n = NAME ## _pair_set_get_array(&map->pair_set, &pair_array); \ - if (n < 0) \ - return -1; \ - if (!array) \ - goto END; \ - /* Allocate result array */ \ - *array = malloc(n * sizeof(VAL_T)); \ - if (!array) { \ - free(pair_array); \ - return -1; \ - } \ - /* Copy values */ \ - for (int i = 0; i < n; i++) \ - (*array)[i] = pair_array[i]->value; \ - free(pair_array); \ -END: \ - return n; \ -} +#define TYPEDEF_MAP(NAME, KEY_T, VAL_T, CMP, KEY_SNPRINTF, VALUE_SNPRINTF) \ + \ + NAME##_pair_t *NAME##_pair_create (KEY_T key, VAL_T value) \ + { \ + /* Create pair */ \ + NAME##_pair_t *pair = malloc (sizeof (NAME##_pair_t)); \ + if (!pair) \ + return NULL; \ + \ + pair->key = key; \ + pair->value = value; \ + \ + return pair; \ + } \ + \ + void NAME##_pair_free (NAME##_pair_t *pair) { free (pair); } \ + \ + int NAME##_pair_cmp (const NAME##_pair_t *p1, const NAME##_pair_t *p2) \ + { \ + return (CMP (p1->key, p2->key)); \ + } \ + \ + int NAME##_pair_snprintf (char *buf, size_t size, \ + const NAME##_pair_t *pair) \ + { \ + int rc; \ + rc = KEY_SNPRINTF (buf, BUFSIZE / 2, (KEY_T) pair->key); \ + if (rc < 0) \ + return rc; \ + rc = VALUE_SNPRINTF (buf + rc, BUFSIZE / 2, (VAL_T) pair->value); \ + return (int) rc; \ + } \ + \ + TYPEDEF_SET (NAME##_pair_set, NAME##_pair_t *, NAME##_pair_cmp, \ + NAME##_pair_snprintf); \ + \ + int NAME##_initialize (NAME##_t *map) \ + { \ + return NAME##_pair_set_initialize (&map->pair_set); \ + } \ + \ + int NAME##_finalize (NAME##_t *map) \ + { \ + NAME##_pair_t **array; \ + int n = NAME##_pair_set_get_array (&map->pair_set, &array); \ + if (n < 0) \ + return -1; \ + for (unsigned i = 0; i < n; i++) \ + { \ + NAME##_pair_t *pair = array[i]; \ + NAME##_pair_set_remove (&map->pair_set, pair, NULL); \ + NAME##_pair_free (pair); \ + } \ + free (array); \ + return NAME##_pair_set_finalize (&map->pair_set); \ + } \ + \ + NAME##_t *NAME##_create () \ + { \ + NAME##_t *map = malloc (sizeof (NAME##_t)); \ + if (!map) \ + goto ERR_MALLOC; \ + \ + if (NAME##_initialize (map) < 0) \ + goto ERR_INITIALIZE; \ + \ + return map; \ + \ + ERR_INITIALIZE: \ + free (map); \ + ERR_MALLOC: \ + return NULL; \ + } \ + \ + void NAME##_free (NAME##_t *map) \ + { \ + NAME##_finalize (map); \ + free (map); \ + } \ + \ + int NAME##_add (NAME##_t *map, KEY_T key, VAL_T value) \ + { \ + int rc; \ + NAME##_pair_t *found = NULL; \ + \ + NAME##_pair_t *pair = NAME##_pair_create (key, value); \ + if (!pair) \ + return -1; \ + \ + rc = NAME##_pair_set_get (&map->pair_set, pair, &found); \ + if (rc < 0) \ + return -1; \ + if (found) \ + { \ + NAME##_pair_free (pair); \ + return ERR_MAP_EXISTS; \ + } \ + \ + rc = NAME##_pair_set_add (&map->pair_set, pair); \ + if (rc < 0) \ + { \ + NAME##_pair_free (pair); \ + return -1; \ + } \ + return 0; \ + } \ + \ + int NAME##_remove (NAME##_t *map, KEY_T key, VAL_T *value) \ + { \ + NAME##_pair_t *found = NULL; \ + NAME##_pair_t search = { .key = key }; \ + int rc = NAME##_pair_set_remove (&map->pair_set, &search, &found); \ + if (rc < 0) \ + return ERR_MAP_NOT_FOUND; \ + if (value) \ + *value = found->value; \ + NAME##_pair_free (found); \ + return 0; \ + } \ + \ + int NAME##_get (NAME##_t *map, KEY_T key, VAL_T *value) \ + { \ + NAME##_pair_t *found = NULL, search = { .key = key }; \ + int rc = NAME##_pair_set_get (&map->pair_set, &search, &found); \ + if (rc < 0) \ + return -1; \ + if (found) \ + *value = found->value; \ + return 0; \ + } \ + \ + void NAME##_dump (NAME##_t *map) { NAME##_pair_set_dump (&map->pair_set); } \ + \ + int NAME##_get_key_array (NAME##_t *map, KEY_T **array) \ + { \ + NAME##_pair_t **pair_array; \ + int n = NAME##_pair_set_get_array (&map->pair_set, &pair_array); \ + if (n < 0) \ + return -1; \ + if (!array) \ + goto END; \ + /* Allocate result array */ \ + *array = malloc (n * sizeof (KEY_T)); \ + if (!array) \ + { \ + free (pair_array); \ + return -1; \ + } \ + /* Copy keys */ \ + for (int i = 0; i < n; i++) \ + (*array)[i] = pair_array[i]->key; \ + free (pair_array); \ + END: \ + return n; \ + } \ + \ + int NAME##_get_value_array (NAME##_t *map, VAL_T **array) \ + { \ + NAME##_pair_t **pair_array; \ + int n = NAME##_pair_set_get_array (&map->pair_set, &pair_array); \ + if (n < 0) \ + return -1; \ + if (!array) \ + goto END; \ + /* Allocate result array */ \ + *array = malloc (n * sizeof (VAL_T)); \ + if (!array) \ + { \ + free (pair_array); \ + return -1; \ + } \ + /* Copy values */ \ + for (int i = 0; i < n; i++) \ + (*array)[i] = pair_array[i]->value; \ + free (pair_array); \ + END: \ + return n; \ + } #endif /* UTIL_MAP_H */ diff --git a/lib/includes/hicn/util/pool.h b/lib/includes/hicn/util/pool.h new file mode 100644 index 000000000..b8acadc44 --- /dev/null +++ b/lib/includes/hicn/util/pool.h @@ -0,0 +1,292 @@ +/* + * Copyright (c) 2021 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. + */ + +/** + * \file pool.h + * \brief Fixed-size pool allocator. + * + * This memory pool allocates a single block of memory that is used to + * efficiently allocate/deallocate fixed-size blocks for high churn data + * structures. + * + * Internally this data structure leverages a vector for managing elements (and + * it thus resizeable if needed), as well as a list of free indices (in the + * form of another vector) and a bitmap marking free indices also (for fast + * iteration). + * + * The internal API manipulates a pointer to the vector that that is can be + * seamlessly resized, and a more convenient user interface is provided through + * macros. + * + * The vector of free indices is managed as a stack where elements indices are + * retrieved from and put back to the end of the vector. In the bitmap, + * available elements are set to 1, and unset to 0 when in use. + * + * The pool is not currently resized down when releasing elements. + * + * It is freely inspired (and simplified) from the VPP infra infrastructure + * library. + */ + +#ifndef UTIL_POOL_H +#define UTIL_POOL_H + +#include <stdint.h> +#include <stdbool.h> + +#include "bitmap.h" +#include <hicn/util/vector.h> +#include "../common.h" + +/* Pool header */ + +typedef struct +{ + size_t elt_size; + size_t alloc_size; + size_t max_size; + bitmap_t *free_bitmap; /* bitmap of free indices */ + off_t *free_indices; /* vector of free indices */ +} pool_hdr_t; + +#define POOL_HDRLEN SIZEOF_ALIGNED (pool_hdr_t) + +/* This header actually prepends the actual content of the pool. */ +#define pool_hdr(pool) ((pool_hdr_t *) ((uint8_t *) (pool) -POOL_HDRLEN)) + +/******************************************************************************/ +/* Helpers */ + +/** Local variable naming macro. */ +#define _pool_var(v) _pool_##v + +/** + * @brief Allocate and initialize a pool data structure (helper). + * + * @param[in,out] pool_ptr Pointer to the pool data structure. + * @param[in] elt_size Size of elements in vector. + * @param[in] max_size Maximum size. + * + * NOTE: that an empty pool might be equal to NULL. + */ +void _pool_init (void **pool_ptr, size_t elt_size, size_t init_size, + size_t max_size); + +/** + * @brief Free a pool data structure (helper). + * + * @param[in] pool_ptr Pointer to the pool data structure. + */ +void _pool_free (void **pool_ptr); + +/** + * @brief Resize a pool data structure (helper). + * + * @param pool_ptr Pointer to the pool data structure. + * + * This function should only be called internally, as the resize is implicitly + * done (if allowed by the maximum size) when the user tries to get a new slot. + */ +void _pool_resize (void **pool_ptr, size_t elt_size); + +/** + * @brief Get a free element from the pool data structure (helper). + * + * @param[in] pool Pointer to the pool data structure to use. + * @param[in,out] elt Pointer to an empty element that will be used to return + * the allocated one from the pool. + * + * NOTES: + * - The memory chunk is cleared upon attribution + */ +off_t _pool_get (void **pool, void **elt, size_t elt_size); + +/** + * @brief Put an element back into the pool data structure (helper). + * + * @param[in] pool_ptr Pointer to the pool data structure to use. + * @param[in] elt Pointer to the pool element to put back. + */ +void _pool_put (void **pool, void **elt, size_t elt_size); + +/** + * @brief Validate a pool element by index (helper). + * + * @param[in] pool The pool data structure to use. + * @param[in] id The index of the element to validate. + * + * @return bool A flag indicating whether the index is valid or not. + */ +bool _pool_validate_id (void **pool_ptr, off_t id); +/******************************************************************************/ +/* Public API */ + +/** + * @brief Allocate and initialize a pool data structure. + * + * @param[in,out] pool Pointer to the pool data structure. + * @param[in] elt_size Size of elements in pool. + * @param[in] max_size Maximum size. + * + * NOTE: that an empty pool might be equal to NULL. + */ +#define pool_init(pool, init_size, max_size) \ + _pool_init ((void **) &pool, sizeof (pool[0]), init_size, max_size); + +/** + * @brief Free a pool data structure. + * + * @param[in] pool The pool data structure to free. + */ +#define pool_free(pool) _pool_free ((void **) &pool); + +/** + * @brief Get a free element from the pool data structure. + * + * @param[in] pool The pool data structure to use. + * @param[in,out] elt An empty element that will be used to return the + * allocated one from the pool. + * + * NOTES: + * - The memory chunk is cleared upon attribution + */ +#define pool_get(pool, elt) \ + _pool_get ((void **) &pool, (void **) &elt, sizeof (*elt)) + +/** + * @brief Put an element back into the pool data structure. + * + * @param[in] pool The pool data structure to use. + * @param[in] elt The pool element to put back. + */ +#define pool_put(pool, elt) \ + _pool_put ((void **) &pool, (void **) &elt, sizeof (*elt)) + +/** + * @brief Validate a pool element by index. + * + * @param[in] pool The pool data structure to use. + * @param[in] id The index of the element to validate. + * + * @return bool A flag indicating whether the index is valid or not. + */ +#define pool_validate_id(pool, id) _pool_validate_id ((void **) &pool, (id)) + +#define pool_get_free_indices_size(pool) \ + vector_len (pool_hdr (pool)->free_indices) + +/** + * @brief Returns the current length of the pool. + * + * @param[in] pool The pool data structure for which to return the length. + * + * @return size_t The current length of the pool. + * + * NOTE: + * - The pool length corresponds to the number of allocated elements, not the + * size of the pool. + */ +#define pool_len(pool) \ + (pool_hdr (pool)->alloc_size - pool_get_free_indices_size (pool)) + +/** + * @brief Enumerate elements from a pool. + * + * @param[in] pool The pool data structure to enumerate. + * @param[in, out] i An integer that will be used for enumeration. + * @param[in, out] eltp A pointer to the element type that will be used for + * enumeration. + * @param[in] BODY Block to execute during enumeration. + * + * Enumeration will iteratively execute BODY with (i, eltp) corresponding + * respectively to the index and element found in the pool. + * + * NOTE: i stars at 0. + */ +#define pool_enumerate(pool, i, eltp, BODY) \ + do \ + { \ + pool_hdr_t *_pool_var (ph) = pool_hdr (pool); \ + bitmap_t *_pool_var (fb) = _pool_var (ph)->free_bitmap; \ + for ((i) = 0; (i) < _pool_var (ph)->alloc_size; (i)++) \ + { \ + if (bitmap_is_set (_pool_var (fb), (i))) \ + continue; \ + eltp = (pool) + (i); \ + do \ + { \ + BODY; \ + } \ + while (0); \ + } \ + } \ + while (0) + +#define pool_enumerate_typed(pool, i, TYPE, ELTP, BODY) \ + do \ + { \ + pool_hdr_t *_pool_var (ph) = pool_hdr (pool); \ + bitmap_t *_pool_var (fb) = _pool_var (ph)->free_bitmap; \ + TYPE ELTP = NULL; \ + for ((i) = 0; (i) < _pool_var (ph)->alloc_size; (i)++) \ + { \ + if (bitmap_is_set (_pool_var (fb), (i))) \ + continue; \ + ELTP = (pool) + (i); \ + do \ + { \ + BODY; \ + } \ + while (0); \ + } \ + } \ + while (0) + +/** + * @brief Iterate over elements in a pool. + * + * @param[in] pool The pool data structure to iterate over. + * @param[in,out] eltp A pointer to the element type that will be used for + * iteration. + * @param[in] BODY Block to execute during iteration. + * + * Iteration will execute BODY with eltp corresponding successively to all + * elements found in the pool. It is implemented using the more generic + * enumeration function. + */ +#define pool_foreach(pool, eltp, BODY) \ + do \ + { \ + unsigned _pool_var (i); \ + pool_enumerate ((pool), _pool_var (i), (eltp), BODY); \ + } \ + while (0) + +#define pool_get_alloc_size(pool) pool_hdr (pool)->alloc_size + +#define pool_foreach_typed(pool, TYPE, ELTP, BODY) \ + do \ + { \ + unsigned _pool_var (i); \ + pool_enumerate_typed ((pool), _pool_var (i), TYPE, ELTP, BODY); \ + } \ + while (0) + +#ifdef WITH_TESTS +#define pool_get_free_indices(pool) pool_hdr (pool)->free_indices +#define pool_get_free_bitmap(pool) pool_hdr (pool)->free_bitmap +#endif /* WITH_TESTS */ + +#endif /* UTIL_POOL_H */ diff --git a/lib/includes/hicn/util/ring.h b/lib/includes/hicn/util/ring.h new file mode 100644 index 000000000..9510672b3 --- /dev/null +++ b/lib/includes/hicn/util/ring.h @@ -0,0 +1,227 @@ +/* + * Copyright (c) 2021 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. + */ + +/** + * \file ring.h + * \brief Fixed-size pool allocator. + */ + +#ifndef UTIL_RING_H +#define UTIL_RING_H + +#include <assert.h> +#include <stdint.h> +#include <string.h> +#include <sys/param.h> // MIN +#include <sys/types.h> + +#include <stdio.h> // XXX debug + +#include "../common.h" + +/******************************************************************************/ +/* Ring header */ + +typedef struct +{ + size_t roff; + size_t woff; + size_t size; + size_t max_size; +} ring_hdr_t; + +/* Make sure elements following the header are aligned */ +#define RING_HDRLEN SIZEOF_ALIGNED (ring_hdr_t) + +/* This header actually prepends the actual content of the vector */ +#define ring_hdr(ring) ((ring_hdr_t *) ((uint8_t *) ring - RING_HDRLEN)) + +/******************************************************************************/ +/* Helpers */ + +/** Local variable naming macro. */ +#define _ring_var(v) _ring_##v + +/** + * @brief Allocate and initialize a ring data structure (helper function). + * + * @param[in,out] ring_ptr Ring buffer to allocate and initialize. + * @param[in] elt_size Size of a ring element. + * @param[in] max_size Maximum vector size (O = unlimited). + */ +void _ring_init (void **ring_ptr, size_t elt_size, size_t max_size); + +/** + * @brief Free a ring data structure. + * + * @param ring_ptr[in] Pointer to the ring data structure to free. + */ +void _ring_free (void **ring_ptr); + +static inline int +_ring_add (void **ring_ptr, size_t elt_size, void *eltp) +{ + assert (*ring_ptr); + ring_hdr_t *rh = ring_hdr (*ring_ptr); + + /* We always write ! */ + memcpy ((uint8_t *) *ring_ptr + rh->woff * elt_size, eltp, elt_size); + rh->woff++; + if (rh->woff == rh->max_size) + rh->woff = 0; + if (rh->size < rh->max_size) + { + rh->size++; + } + else + { + /* One packet was dropped */ + rh->roff++; + if (rh->roff == rh->max_size) + rh->roff = 0; + } + return 0; +} + +static inline unsigned +_ring_get_fullness (void **ring_ptr) +{ + assert (*ring_ptr); + ring_hdr_t *rh = ring_hdr (*ring_ptr); + return (unsigned int) (rh->size * 100 / rh->max_size); +} + +static inline unsigned +_ring_is_full (void **ring_ptr) +{ + assert (*ring_ptr); + ring_hdr_t *rh = ring_hdr (*ring_ptr); + return rh->size == rh->max_size; +} + +static inline size_t +_ring_get_size (void **ring_ptr) +{ + assert (*ring_ptr); + ring_hdr_t *rh = ring_hdr (*ring_ptr); + return rh->size; +} + +static inline int +_ring_advance (void **ring_ptr, unsigned n) +{ + assert (*ring_ptr); + ring_hdr_t *rh = ring_hdr (*ring_ptr); + assert (n <= rh->size); + + rh->roff += n; + rh->size -= n; + while (rh->roff >= rh->max_size) + rh->roff -= rh->max_size; + return 0; +} + +static inline int +_ring_get (void **ring_ptr, size_t elt_size, unsigned i, void *eltp) +{ + assert (*ring_ptr); + ring_hdr_t *rh = ring_hdr (*ring_ptr); + assert (i <= rh->size); + size_t pos = rh->roff + i; + if (pos >= rh->max_size) + pos -= rh->max_size; + memcpy (eltp, (uint8_t *) *ring_ptr + pos * elt_size, elt_size); + return 0; +} + +/******************************************************************************/ +/* Public API */ + +/** + * @brief Allocate and initialize a ring data structure. + * + * @param[in,out] ring Ring to allocate and initialize. + * @param[in] max_size Maximum ring size (nonzero). + * + * NOTE: + * - Allocated memory is set to 0 (used by bitmap) + */ + +#define ring_init(RING, MAX_SIZE) \ + _ring_init ((void **) &(RING), sizeof ((RING)[0]), (MAX_SIZE)) + +#define ring_free(RING) _ring_free ((void **) &(RING)) + +#define ring_get_fullness(RING) _ring_get_fullness ((void **) &(RING)) + +#define ring_is_full(RING) _ring_is_full ((void **) &(RING)) + +#define ring_get_size(RING) _ring_get_size ((void **) &(RING)) + +#define ring_add(RING, ELT) \ + _ring_add ((void **) &(RING), sizeof (RING[0]), ELT) + +#define ring_add_value(RING, VALUE) \ + do \ + { \ + typeof (VALUE) _ring_var (v) = VALUE; \ + _ring_add ((void **) &(RING), sizeof (RING[0]), &_ring_var (v)); \ + } \ + while (0) + +#define ring_advance(RING, N) _ring_advance ((void **) &(RING), (N)) + +#define ring_get(RING, I, ELTP) \ + _ring_get ((void **) &RING, sizeof (RING[0]), (I), (ELTP)) + +/** + * @brief Helper function used by ring_foreach(). + */ +#define ring_enumerate_n(RING, I, ELTP, COUNT, BODY) \ + ({ \ + for ((I) = 0; (I) < MIN (ring_get_size (RING), (COUNT)); (I)++) \ + { \ + ring_get ((RING), (I), (ELTP)); \ + { \ + BODY; \ + } \ + } \ + }) + +#define ring_enumerate(ring, i, eltp, BODY) \ + ring_enumerate_n ((ring), (i), (eltp), 1, (BODY)) + +/** + * @brief Iterate over elements in a ring. + * + * @param[in] pool The ring data structure to iterate over + * @param[in, out] eltp A pointer to the element that will be used for + * iteration + * @param[in] BODY Block to execute during iteration + * + * @note Iteration will execute BODY with eltp corresponding successively to + * all elements found in the ring. It is implemented using the more generic + * enumeration function. + */ +#define ring_foreach_n(ring, eltp, count, BODY) \ + ({ \ + unsigned _ring_var (i); \ + ring_enumerate_n ((ring), _ring_var (i), (eltp), (count), BODY); \ + }) + +#define ring_foreach(ring, eltp, BODY) \ + ring_foreach_n ((ring), (eltp), 1, (BODY)) + +#endif /* UTIL_RING_H */ diff --git a/lib/includes/hicn/util/set.h b/lib/includes/hicn/util/set.h index bc2e3caac..0a5ff6777 100644 --- a/lib/includes/hicn/util/set.h +++ b/lib/includes/hicn/util/set.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Copyright (c) 2021 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: @@ -25,214 +25,196 @@ #define thread_local _Thread_local //#endif /* ! __ANDROID__ */ -#define ERR_SET_EXISTS -2 +#define ERR_SET_EXISTS -2 #define ERR_SET_NOT_FOUND -3 /* FIXME: buffer overflow when this is too small... investigate */ #define BUFSIZE 1024 -static inline -int -int_cmp(const int x, const int y) +static inline int +int_cmp (const int x, const int y) { - return x - y; + return x - y; } -static inline -int -int_snprintf(char * buf, size_t size, int value) { - return snprintf(buf, size, "%d", value); +static inline int +int_snprintf (char *buf, size_t size, int value) +{ + return snprintf (buf, size, "%d", value); } -static inline -int -string_snprintf(char * buf, size_t size, const char * s) { - return snprintf(buf, size, "%s", s); +static inline int +string_snprintf (char *buf, size_t size, const char *s) +{ + return snprintf (buf, size, "%s", s); } -static inline -int -generic_snprintf(char * buf, size_t size, const void * value) { - return snprintf(buf, BUFSIZE, "%p", value); +static inline int +generic_snprintf (char *buf, size_t size, const void *value) +{ + return snprintf (buf, BUFSIZE, "%p", value); } -typedef int(*cmp_t)(const void * x, const void * y); - -#define TYPEDEF_SET_H(NAME, T) \ - \ -typedef struct { \ - size_t size; \ - void * root; \ -} NAME ## _t; \ - \ -int NAME ## _initialize(NAME ## _t * set); \ - \ -int NAME ## _finalize(NAME ## _t * set); \ - \ -NAME ## _t * NAME ## _create(); \ - \ -void NAME ## _free(NAME ## _t * set); \ - \ -int NAME ## _add(NAME ## _t * set, const T element); \ - \ -int NAME ## _remove(NAME ## _t * set, const T search, T * element); \ - \ -int NAME ## _clear(NAME ## _t * set); \ - \ -int NAME ## _get(const NAME ## _t * set, const T search, T * element); \ - \ -int NAME ## _get_array(const NAME ## _t * set, T ** element); \ - \ -void NAME ## _dump(NAME ## _t * set); +typedef int (*cmp_t) (const void *x, const void *y); +#define TYPEDEF_SET_H(NAME, T) \ + \ + typedef struct \ + { \ + size_t size; \ + void *root; \ + } NAME##_t; \ + \ + int NAME##_initialize (NAME##_t *set); \ + \ + int NAME##_finalize (NAME##_t *set); \ + \ + NAME##_t *NAME##_create (); \ + \ + void NAME##_free (NAME##_t *set); \ + \ + int NAME##_add (NAME##_t *set, const T element); \ + \ + int NAME##_remove (NAME##_t *set, const T search, T *element); \ + \ + int NAME##_clear (NAME##_t *set); \ + \ + int NAME##_get (const NAME##_t *set, const T search, T *element); \ + \ + int NAME##_get_array (const NAME##_t *set, T **element); \ + \ + void NAME##_dump (NAME##_t *set); - - -#define TYPEDEF_SET(NAME, T, CMP, SNPRINTF) \ -int \ -NAME ## _initialize(NAME ## _t * set) \ -{ \ - set->root = NULL; \ - set->size = 0; \ - return 0; \ -} \ - \ -int \ -NAME ## _finalize(NAME ## _t * set) \ -{ \ - return NAME ## _clear(set); \ -} \ - \ -NAME ## _t * \ -NAME ## _create() \ -{ \ - NAME ## _t * set = malloc(sizeof(NAME ## _t)); \ - if (!set) \ - goto ERR_MALLOC; \ - \ - if (NAME ## _initialize(set) < 0) \ - goto ERR_INITIALIZE; \ - \ - return set; \ - \ -ERR_INITIALIZE: \ - free(set); \ -ERR_MALLOC: \ - return NULL; \ -} \ - \ -void \ -NAME ## _free(NAME ## _t * set) \ -{ \ - NAME ## _finalize(set); \ - free(set); \ -} \ - \ -int \ -NAME ## _add(NAME ## _t * set, const T element) \ -{ \ - T * found = tfind(element, &set->root, (cmp_t)CMP); \ - void * ptr = tsearch(element, &set->root, (cmp_t)CMP); \ - if (!ptr) \ - return -1; \ - if (!found) \ - set->size++; \ - return 0; \ -} \ - \ -int \ -NAME ## _remove(NAME ## _t * set, const T search, T * element) \ -{ \ - T * found = tfind(search, &set->root, (cmp_t)CMP); \ - if (!found) \ - return ERR_SET_NOT_FOUND; \ - if (element) \ - *element = *found; \ - tdelete(search, &set->root, (cmp_t)CMP); \ - set->size--; \ - return 0; \ -} \ - \ -int \ -NAME ## _clear(NAME ## _t * set) \ -{ \ - T * array; \ - int n = NAME ## _get_array(set, &array); \ - if (n < 0) \ - return -1; \ - for (unsigned i = 0; i < n; i++) { \ - T element = array[i]; \ - NAME ## _remove(set, element, NULL); \ - } \ - free(array); \ - return 0; \ -} \ - \ -int \ -NAME ## _get(const NAME ## _t * set, const T search, T * element) \ -{ \ - T * found = tfind(search, &set->root, (cmp_t)CMP); \ - if (element) \ - *element = found ? *found : NULL; \ - return 0; \ -} \ - \ -static void \ -NAME ## _dump_node(const void *nodep, const VISIT which, \ - const int depth) \ -{ \ - char buf[BUFSIZE]; \ - switch (which) { \ - case preorder: \ - case endorder: \ - break; \ - case postorder: \ - case leaf: \ - SNPRINTF(buf, BUFSIZE, *(T*)nodep); \ - INFO("%s", buf); \ - break; \ - } \ -} \ - \ -void \ -NAME ## _dump(NAME ## _t * set) { \ - twalk(set->root, NAME ## _dump_node); \ -} \ - \ -thread_local \ -T * NAME ## _array_pos = NULL; \ - \ -static void \ -NAME ## _add_node_to_array(const void *nodep, const VISIT which, \ - const int depth) \ -{ \ - if (!NAME ## _array_pos) \ - return; \ - switch (which) { \ - case preorder: \ - case endorder: \ - break; \ - case postorder: \ - case leaf: \ - *NAME ## _array_pos = *(T*)nodep; \ - NAME ## _array_pos++; \ - break; \ - } \ -} \ - \ -int \ -NAME ## _get_array(const NAME ## _t * set, T ** element) \ -{ \ - if (!element) \ - goto END; \ - *element = malloc(set->size * sizeof(T)); \ - if (!*element) \ - return -1; \ - NAME ## _array_pos = *element; \ - twalk(set->root, NAME ## _add_node_to_array); \ - NAME ## _array_pos = NULL; \ -END: \ - return (int)(set->size); \ -} +#define TYPEDEF_SET(NAME, T, CMP, SNPRINTF) \ + int NAME##_initialize (NAME##_t *set) \ + { \ + set->root = NULL; \ + set->size = 0; \ + return 0; \ + } \ + \ + int NAME##_finalize (NAME##_t *set) { return NAME##_clear (set); } \ + \ + NAME##_t *NAME##_create () \ + { \ + NAME##_t *set = malloc (sizeof (NAME##_t)); \ + if (!set) \ + goto ERR_MALLOC; \ + \ + if (NAME##_initialize (set) < 0) \ + goto ERR_INITIALIZE; \ + \ + return set; \ + \ + ERR_INITIALIZE: \ + free (set); \ + ERR_MALLOC: \ + return NULL; \ + } \ + \ + void NAME##_free (NAME##_t *set) \ + { \ + NAME##_finalize (set); \ + free (set); \ + } \ + \ + int NAME##_add (NAME##_t *set, const T element) \ + { \ + T *found = tfind (element, &set->root, (cmp_t) CMP); \ + void *ptr = tsearch (element, &set->root, (cmp_t) CMP); \ + if (!ptr) \ + return -1; \ + if (!found) \ + set->size++; \ + return 0; \ + } \ + \ + int NAME##_remove (NAME##_t *set, const T search, T *element) \ + { \ + T *found = tfind (search, &set->root, (cmp_t) CMP); \ + if (!found) \ + return ERR_SET_NOT_FOUND; \ + if (element) \ + *element = *found; \ + tdelete (search, &set->root, (cmp_t) CMP); \ + set->size--; \ + return 0; \ + } \ + \ + int NAME##_clear (NAME##_t *set) \ + { \ + T *array; \ + int n = NAME##_get_array (set, &array); \ + if (n < 0) \ + return -1; \ + for (unsigned i = 0; i < n; i++) \ + { \ + T element = array[i]; \ + NAME##_remove (set, element, NULL); \ + } \ + free (array); \ + return 0; \ + } \ + \ + int NAME##_get (const NAME##_t *set, const T search, T *element) \ + { \ + T *found = tfind (search, &set->root, (cmp_t) CMP); \ + if (element) \ + *element = found ? *found : NULL; \ + return 0; \ + } \ + \ + static void NAME##_dump_node (const void *nodep, const VISIT which, \ + const int depth) \ + { \ + char buf[BUFSIZE]; \ + switch (which) \ + { \ + case preorder: \ + case endorder: \ + break; \ + case postorder: \ + case leaf: \ + SNPRINTF (buf, BUFSIZE, *(T *) nodep); \ + INFO ("%s", buf); \ + break; \ + } \ + } \ + \ + void NAME##_dump (NAME##_t *set) { twalk (set->root, NAME##_dump_node); } \ + \ + thread_local T *NAME##_array_pos = NULL; \ + \ + static void NAME##_add_node_to_array (const void *nodep, const VISIT which, \ + const int depth) \ + { \ + if (!NAME##_array_pos) \ + return; \ + switch (which) \ + { \ + case preorder: \ + case endorder: \ + break; \ + case postorder: \ + case leaf: \ + *NAME##_array_pos = *(T *) nodep; \ + NAME##_array_pos++; \ + break; \ + } \ + } \ + \ + int NAME##_get_array (const NAME##_t *set, T **element) \ + { \ + if (!element) \ + goto END; \ + *element = calloc (set->size, sizeof (T)); \ + if (!*element) \ + return -1; \ + NAME##_array_pos = *element; \ + twalk (set->root, NAME##_add_node_to_array); \ + NAME##_array_pos = NULL; \ + END: \ + return (int) (set->size); \ + } #endif /* UTIL_SET_H */ diff --git a/lib/includes/hicn/util/slab.h b/lib/includes/hicn/util/slab.h new file mode 100644 index 000000000..2c6546add --- /dev/null +++ b/lib/includes/hicn/util/slab.h @@ -0,0 +1,126 @@ +/* + * Copyright (c) 2022 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. + */ + +/** + * @brief The slab is used to store elements of the same size. + * + * The slab contains blocks of contiguous memory. Each block contains multiple + * chunks. An element is stored inside a chunk and the chunk has a header with + * a pointer to the block it belongs to. + * + * Blocks are stored in two doubly-linked lists: 'full' for blocks that + * are already full, 'partial_or_empty' for blocks with available chunks. When + * a block becomes full it is moved into the 'full' list and vice versa. + * + * When allocationg an element, a block is taken from the 'partial_or_empty' + * list if such list is not empty. If empty, a new block of contiguous memory + * is created and put in the 'partial_or_empty' list. Then, a chunk is taken + * from the block. When releasing an element, the block it belongs to is + * retrieved from the chunk header and used to release the chunk. + * + * Blocks are created with increasing capacity (i.e. number of chunks they + * contain) such that every new block allocaion doubles the total number of + * chunks stored in the slab. + */ + +#ifndef UTIL_SLAB_H +#define UTIL_SLAB_H + +#include <stddef.h> + +#define SLAB_INIT_SIZE 32 + +/* CHUNK */ + +typedef struct block_s block_t; +typedef struct +{ + block_t *block; // Pointer to the block that contains the chunk +} chunk_hdr_t; + +#define CHUNK_HDRLEN SIZEOF_ALIGNED (chunk_hdr_t) +#define chunk_hdr(chunk) ((chunk_hdr_t *) ((uint8_t *) (chunk) -CHUNK_HDRLEN)) + +/* BLOCK */ + +struct block_s +{ + void *pool; + block_t *prev; + block_t *next; +}; + +/* SLAB */ + +typedef struct +{ + size_t num_chunks; // Total number of chunks (from all blocks) currently + // stored in the slab + size_t chunk_size; + block_t *full; + block_t *partial_or_empty; +} slab_t; + +/* Internal API */ + +slab_t *_slab_create (size_t elt_size, size_t num_elts); +void *_slab_get (slab_t *slab); +void _slab_put (slab_t *slab, void *elt); + +/* Public API */ + +/** + * @brief Create a slab able to store elements of type 'TYPE'. + * + * @param[in] TYPE Type of the elements to store in the slab. + * @param[in] SIZE Initial size of the slab, i.e. size of the initial block. + * @return slab_t* The slab created, NULL if error. + */ +#define slab_create(TYPE, SIZE) _slab_create (sizeof (TYPE), SIZE) + +/** + * @brief Free a slab. + * + * @param[in] slab Slab to free. + */ +void slab_free (slab_t *slab); + +/** + * @brief Get an element from the slab. + * + * @param[in] TYPE Type of the elements stored in the slab. + * @param[in] SLAB Slab to take the element from. + * @return TYPE* Element retrieved from the slab + */ +#define slab_get(TYPE, SLAB) (TYPE *) _slab_get (SLAB) + +/** + * @brief Same as 'slab_get' but with a different signature, to avoid passing + * the type that is instead inferred from the element. + * + * @param[in] SLAB Slab to take the element from. + * @param[in, out] ELT Element retrieved from the slab. + */ +#define slab_get2(SLAB, ELT) ELT = (typeof (*(ELT)) *) _slab_get (SLAB) + +/** + * @brief Put an element back into the slab. + * + * @param[in] SLAB Slab to return the element to. + * @param[in] ELT Element to put in the slab. + */ +#define slab_put(SLAB, ELT) _slab_put (SLAB, (void *) ELT) + +#endif /* UTIL_SLAB_H */ diff --git a/lib/includes/hicn/util/sstrncpy.h b/lib/includes/hicn/util/sstrncpy.h new file mode 100644 index 000000000..0b397c26b --- /dev/null +++ b/lib/includes/hicn/util/sstrncpy.h @@ -0,0 +1,76 @@ +/* + * Copyright (c) 2021 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. + */ + +#ifndef UTIL_SSTRNCPY_H +#define UTIL_SSTRNCPY_H + +#ifndef __STDC_WANT_LIB_EXT1__ +#define __STDC_WANT_LIB_EXT1__ 1 +#endif + +#include <errno.h> +#include <string.h> + +#ifdef __STDC_LIB_EXT1__ +// If safe string functions already available in the system, use them +#elif ENABLE_SAFEC +// If safe string functions not available and SafeC is enabled, +// use SafeC +#include <safe_string.h> +#else +// Use custom safe string functions +typedef int errno_t; +#define EOK 0 + +#ifndef HICN_VPP_PLUGIN +/* This function is already defined in vppinfra/string.h */ + +/** + * @brief This function assures a null byte at the end of the buffer. + */ +static inline errno_t +strcpy_s (char *dst, size_t n, const char *src) +{ + if (!dst || !src || !n) + { + fprintf (stderr, "[strncpy] invalid input received"); + return EINVAL; + } + + dst[n - 1] = 0; + strncpy (dst, src, n); + + if (dst[n - 1] != 0) + { + fprintf (stderr, "[strncpy] '%s' has been trucated\n", src); + dst[n - 1] = 0; + return EINVAL; + } + + return EOK; +} + +static inline size_t +strnlen_s (const char *s, size_t maxlen) +{ + if (s == NULL) + return 0; + + return strnlen (s, maxlen); +} +#endif /* HICN_VPP_PLUGIN */ + +#endif /* __STDC_LIB_EXT1__ */ +#endif /* UTIL_SSTRNCPY_H */ diff --git a/lib/includes/hicn/util/token.h b/lib/includes/hicn/util/token.h index 43e0a77b2..c62c294bc 100644 --- a/lib/includes/hicn/util/token.h +++ b/lib/includes/hicn/util/token.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Copyright (c) 2021 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: @@ -19,12 +19,12 @@ * Concatenate preprocessor tokens A and B without expanding macro definitions * (however, if invoked from a macro, macro arguments are expanded). */ -#define PPCAT_NX(A, B) A ## B +#define PPCAT_NX(A, B) A##B /* * Concatenate preprocessor tokens A and B after macro-expanding them. */ -#define PPCAT(A, B) PPCAT_NX(A, B) +#define PPCAT(A, B) PPCAT_NX (A, B) /* Token stringification */ @@ -37,4 +37,4 @@ /* * Turn A into a string literal after macro-expanding it. */ -#define STRINGIZE(A) STRINGIZE_NX(A) +#define STRINGIZE(A) STRINGIZE_NX (A) diff --git a/lib/includes/hicn/util/types.h b/lib/includes/hicn/util/types.h index 017e85b72..a883b8220 100644 --- a/lib/includes/hicn/util/types.h +++ b/lib/includes/hicn/util/types.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Copyright (c) 2021-2022 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: @@ -19,21 +19,63 @@ #include <hicn/util/windows/windows_Utils.h> #endif +/* Standard types. */ +#include <stdint.h> + typedef uint8_t u8; typedef uint16_t u16; typedef uint32_t u32; typedef uint64_t u64; -/* Helper for avoiding warnings about type-punning */ -#define UNION_CAST(x, destType) \ - (((union {__typeof__(x) a; destType b;})x).b) +typedef int8_t i8; +typedef int16_t i16; +typedef int32_t i32; +typedef int64_t i64; + +typedef double f64; +typedef float f32; + +/* Architecture-dependent uword size */ +#if INTPTR_MAX == INT64_MAX +#define hicn_log2_uword_bits 6 +#elif INTPTR_MAX == INT32_MAX +#define hicn_log2_uword_bits 5 +#else +#error "Impossible to detect architecture" +#endif + +#define _hicn_uword_bits (1 << hicn_log2_uword_bits) -//typedef unsigned int hash_t; +/* Word types. */ +#if _hicn_uword_bits == 64 +/* 64 bit word machines. */ +typedef u64 hicn_uword; +#define hicn_uword_bits 64 +#else +/* 32 bit word machines. */ +typedef u32 hicn_uword; +#define hicn_uword_bits 32 +#endif + +typedef hicn_uword hicn_ip_csum_t; + +/* Helper for avoiding warnings about type-punning */ +#define UNION_CAST(x, destType) \ + (((union { \ + __typeof__ (x) a; \ + destType b; \ + }) x) \ + .b) -typedef int (*cmp_t)(const void *, const void *); +typedef int (*cmp_t) (const void *, const void *); /* Enums */ -#define IS_VALID_ENUM_TYPE(NAME, x) ((x > NAME ## _UNDEFINED) && (x < NAME ## _N)) +#define IS_VALID_ENUM_TYPE(NAME, x) ((x > NAME##_UNDEFINED) && (x < NAME##_N)) + +/* Float */ + +uint32_t htonf (float f); +float ntohf (uint32_t i); #endif /* UTIL_TYPES */ diff --git a/lib/includes/hicn/util/vector.h b/lib/includes/hicn/util/vector.h new file mode 100644 index 000000000..e693df9e3 --- /dev/null +++ b/lib/includes/hicn/util/vector.h @@ -0,0 +1,470 @@ +/* + * Copyright (c) 2021 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. + */ + +/** + * \file vector.h + * \brief Resizeable static array + * + * A vector is a resizeable area of contiguous memory that contains elements of + * fixed size. It is mostly useful to serve as the basis for more advanced data + * structures such as memory pools. + * + * The internal API manipulates a pointer to the vector so that it can be + * seamlessly resized, and a more convenient user interface is provided through + * macros. + * + * A vector starts at index 0, and is typed according to the elements it + * contains. For that matter, the data structure header precedes the returned + * pointer which corresponds to the storage area. + * + * A vector is by default used as a stack where an end marker is maintained and + * new elements are pushed right after this end marker (an indication of + * the size of the vector) after ensuring the vector is sufficiently large. + * + * A user should not store any pointer to vector elements as this might change + * during reallocations, but should use indices instead. + * + * NOTE: a maximum size is currently not implemented. + * + * It is freely inspired (and simplified) from the VPP infra infrastructure + * library. + */ + +#ifndef UTIL_VECTOR_H +#define UTIL_VECTOR_H + +#include <stdint.h> +#include <stddef.h> +#include <stdint.h> +#include <string.h> +#include <sys/types.h> +#include <stdbool.h> + +#include "../common.h" + +/******************************************************************************/ +/* Vector header */ + +typedef struct +{ + size_t cur_size; /** Vector current size (corresponding to the highest used + element). */ + size_t alloc_size; /** The currently allocated size. */ + size_t max_size; /** The maximum allowed size (0 = no limit) */ +} vector_hdr_t; + +/* Make sure elements following the header are aligned */ +#define VECTOR_HDRLEN SIZEOF_ALIGNED (vector_hdr_t) + +/* This header actually prepends the actual content of the vector */ +#define vector_hdr(vector) \ + ((vector_hdr_t *) ((uint8_t *) vector - VECTOR_HDRLEN)) + +/******************************************************************************/ +/* Helpers */ + +/** Local variable naming macro. */ +#define _vector_var(v) _vector_##v + +/** + * @brief Allocate and initialize a vector data structure (helper function). + * + * @param[in,out] vector_ptr Vector to allocate and initialize. + * @param[in] elt_size Size of a vector element. + * @param[in] init_size Initial vector size. + * @param[in] max_size Maximum vector size (O = unlimited). + * @return int 0 if successful, -1 otherwise + */ +int _vector_init (void **vector_ptr, size_t elt_size, size_t init_size, + size_t max_size); + +/** + * @brief Free a vector data structure. + * + * @param vector_ptr[in] Pointer to the vector data structure to free. + */ +void _vector_free (void **vector_ptr); + +/** + * @brief Resize a vector data structure. + * + * @param[in] vector_ptr A pointer to the vector data structure to resize. + * @param[in] elt_size The size of a vector element. + * @param[in] pos The position at which the vector should be able to hold an + * element. + * + * @return int Flag indicating whether the vector has been correctly resized. + * + * NOTE: + * - The resize operation does not specify the final size of the vector but + * instead ensure that it is large enough to hold an element at the specified + * position. This allows the caller not to care about doing successive calls to + * this API while the vector is growing in size. + */ +int _vector_resize (void **vector_ptr, size_t elt_size, off_t pos); + +/** + * @brief Ensures a vector is sufficiently large to hold an element at the + * given position. + * + * @param[in] vector_ptr A pointer to the vector data structure to resize. + * @param[in] elt_size The size of a vector element. + * @param[in] pos The position to validate. + * + * @return int Flag indicating whether the vector is available. + * + * NOTE: + * - This function should always be called before writing to a vector element + * to eventually make room for it (the vector will eventually be resized). + * - This function can fail if the vector is full and for any reason it cannot + * be resized. + */ +static inline int +_vector_ensure_pos (void **vector_ptr, size_t elt_size, off_t pos) +{ + vector_hdr_t *vh = vector_hdr (*vector_ptr); + if (pos >= (off_t) vh->alloc_size) + return _vector_resize (vector_ptr, elt_size, pos + 1); + return 0; +} + +/** + * @brief Push an element at the end of a vector. + * + * @param[in] vector_ptr A pointer to the vector data structure to resize. + * @param[in] elt_size The size of a vector element. + * @param[in] elt The element to insert. + * + * NOTE: + * - This function ensures there is sufficient room for inserting the element, + * and evenutually resizes the vector to make room for it (if allowed by + * maximum size). + */ +static inline int +_vector_push (void **vector_ptr, size_t elt_size, void *elt) +{ + vector_hdr_t *vh = vector_hdr (*vector_ptr); + if (_vector_ensure_pos (vector_ptr, elt_size, vh->cur_size) < 0) + return -1; + + /* Always get header after a potential resize */ + vh = vector_hdr (*vector_ptr); + memcpy ((uint8_t *) *vector_ptr + vh->cur_size * elt_size, elt, elt_size); + vh = vector_hdr (*vector_ptr); + vh->cur_size++; + return 0; +} + +/** + * @brief Remove all the occurrencies of an element from the vector. + * The order of the elements is NOT maintained. + * + * @param[in, out] vector The vector data structure to resize + * @param[in] elt_size The size of a vector element + * @param[in] elt The element to remove + * @return int Number of elemets (equal to 'elt') removed from the vector + */ +static inline int +_vector_remove_unordered (void *vector, size_t elt_size, void *elt) +{ + size_t num_removed = 0; + vector_hdr_t *vh = vector_hdr (vector); + for (size_t i = 0; i < vector_hdr (vector)->cur_size; i++) + { + if (memcmp ((uint8_t *) vector + i * elt_size, elt, elt_size) == 0) + { + vh->cur_size--; + // Copy last element to current position (hence order is not + // maintained) + memcpy ((uint8_t *) vector + i * elt_size, + (uint8_t *) vector + vh->cur_size * elt_size, elt_size); + num_removed++; + } + } + return (int) num_removed; +} + +/** + * @brief Get the element at the specified position and store in 'elt'. + * + * @param[in] vector Pointer to the vector data structure to use + * @param[in] pos Position of the element to retrieve + * @param[in] elt_size The size of a vector element + * @param[in] elt The element where the result is stored + * @return int 0 if successful, -1 otherwise + */ +static inline int +_vector_get (void *vector, off_t pos, size_t elt_size, void *elt) +{ + vector_hdr_t *vh = vector_hdr (vector); + if ((size_t) pos >= vh->alloc_size) + return -1; + + memcpy (elt, (uint8_t *) vector + pos * elt_size, elt_size); + return 0; +} + +/** + * @brief Check if specified element is present in vector. + * + * @param[in] vector Pointer to the vector data structure to use + * @param[in] elt_size The size of a vector element + * @param[in] elt The element to search for + * @return true If specified element is contained in the vector + * @return false + */ +static inline bool +_vector_contains (void *vector, size_t elt_size, void *elt) +{ + for (size_t i = 0; i < vector_hdr (vector)->cur_size; i++) + { + if (memcmp ((uint8_t *) vector + i * elt_size, elt, elt_size) == 0) + return true; + } + + return false; +} + +/** + * @brief Remove the element at the specified position from the vector. + * Relative element order is preserved by shifting left the elements after the + * target. + * + * @param[in, out] vector Pointer to the vector data structure to use + * @param[in] elt_size The size of a vector element + * @param[in] pos Position of the element to remove + * @return int 0 if successful, -1 otherwise + */ +static inline int +_vector_remove_at (void **vector_ptr, size_t elt_size, off_t pos) +{ + vector_hdr_t *vh = vector_hdr (*vector_ptr); + if ((size_t) pos >= vh->cur_size) + return -1; + + // Shift backward by one position all the elements after the one specified + memmove ((uint8_t *) (*vector_ptr) + pos * elt_size, + (uint8_t *) (*vector_ptr) + (pos + 1) * elt_size, + (vh->cur_size - 1 - pos) * elt_size); + vh->cur_size--; + + return 0; +} + +/******************************************************************************/ +/* Public API */ + +/** + * @brief Allocate and initialize a vector data structure. + * + * @param[in,out] vector Vector to allocate and initialize. + * @param[in] init_size Initial vector size. + * @param[in] max_size Maximum vector size (nonzero). + * + * NOTE: + * - Allocated memory is set to 0 (used by bitmap) + */ + +#define vector_init(vector, init_size, max_size) \ + _vector_init ((void **) &vector, sizeof (vector[0]), init_size, max_size) + +/** + * @brief Free a vector data structure. + * + * @param[in] vector The vector data structure to free. + */ +#define vector_free(vector) _vector_free ((void **) &vector) + +/** + * @brief Resize a vector data structure. + * + * @param[in] vector The vector data structure to resize. + * @param[in] pos The position at which the vector should be able to hold an + * element. + * + * @return int Flag indicating whether the vector has been correctly resized. + * + * NOTE: + * - The resize operation does not specify the final size of the vector but + * instead ensure that it is large enough to hold an element at the specified + * position. This allows the caller not to care about doing successive calls to + * this API while the vector is growing in size. + * - If the new size is smaller than the current size, the content of the + * vector will be truncated. + * - Newly allocated memory is set to 0 (used by bitmap) + */ +#define vector_resize(vector) \ + _vector_resize ((void **) &(vector), sizeof ((vector)[0]), 0) + +/** + * @brief Ensures a vector is sufficiently large to hold an element at the + * given position. + * + * @param[in] vector The vector for which to validate the position. + * @param[in] pos The position to validate. + * + * NOTE: + * - This function should always be called before writing to a vector element + * to eventually make room for it (the vector will eventually be resized). + */ +#define vector_ensure_pos(vector, pos) \ + _vector_ensure_pos ((void **) &(vector), sizeof ((vector)[0]), pos); + +/** + * @brief Push an element at the end of a vector. + * + * @param[in] vector The vector in which to insert the element. + * @param[in] elt The element to insert. + * + * NOTE: + * - This function ensures there is sufficient room for inserting the element, + * and evenutually resizes the vector to make room for it (if allowed by + * maximum size). + */ +#define vector_push(vector, elt) \ + ({ \ + typeof (elt) _vector_var (x) = elt; \ + _vector_push ((void **) &(vector), sizeof ((vector)[0]), \ + (void *) (&_vector_var (x))); \ + }) + +#define vector_at(vector, pos) \ + ({ \ + assert ((size_t) pos < vector_hdr (vector)->cur_size); \ + (vector)[(pos)]; \ + }) + +#define vector_set(vector, pos, elt) \ + ({ \ + assert (pos < vector_hdr (vector)->cur_size); \ + (vector)[(pos)] = elt; \ + }) + +/** + * @brief Clear the vector content, i.e. new pushes will insert starting from + * position 0. + * + * @param[in, out] vector The vector to reset + */ +#define vector_reset(vector) (vector_len (vector) = 0) + +/** + * @brief Get the element at the specified position and store in 'elt'. + * + * @param[in] vector The vector data structure to use + * @param[in] pos Position of the element to retrieve + * @param[in] elt The element where the result is stored + * @return int 0 if successful, -1 otherwise + */ +#define vector_get(vector, pos, elt) \ + _vector_get ((void *) (vector), (pos), sizeof ((vector)[0]), \ + (void *) (&elt)); + +/** + * @brief Check if specified element is present in vector. + * + * @param[in] vector The vector data structure to use + * @param[in] elt The element to search for + * @return true If specified element is contained in the vector + * @return false + */ +#define vector_contains(vector, elt) \ + ({ \ + typeof (elt) _vector_var (x) = elt; \ + _vector_contains ((void *) (vector), sizeof ((vector)[0]), \ + (void *) (&_vector_var (x))); \ + }) + +/** + * @brief Remove the element at the specified position from the vector. + * Relative element order is preserved by shifting left the elements after the + * target. + * + * @param[in, out] vector The vector data structure to use + * @param[in] pos Position of the element to remove + * @return int 0 if successful, -1 otherwise + */ +#define vector_remove_at(vector, pos) \ + _vector_remove_at ((void **) &(vector), sizeof ((vector)[0]), (pos)) + +/** + * @brief Remove all the occurrencies of an element from the vector. + * The order of the elements is NOT maintained. + * + * @param[in, out] vector The vector data structure to resize + * @param[in] elt The element to remove + * @return int Number of elemets (equal to 'elt') removed from the vector + */ +#define vector_remove_unordered(vector, elt) \ + ({ \ + typeof (elt) x = elt; \ + _vector_remove_unordered ((void *) (vector), sizeof ((vector)[0]), \ + (void *) (&x)); \ + }) + +/** + * @brief Returns the length of a vector. + * + * @param[in] vector The vector from which to get the size. + * + * @see vector_ensure_pos + * + * NOTE: + * - The size of the vector corresponds to the highest accessed index (for + * example as specified in the resize operation) and not the currently + * allocated size which will typically be bigger to amortize allocations. + * - A user should always call vector_ensure_pos to ensure the vector is + * sufficiently large to hold an element at the specified position. + */ +#define vector_len(vector) vector_hdr (vector)->cur_size + +/** + * @brief Returns the allocated size of a vector. + */ +#define vector_get_alloc_size(vector) vector_hdr (vector)->alloc_size + +/** + * @brief Iterate over elements in a vector. + * + * @param[in] pool The vector data structure to iterate over + * @param[in, out] eltp A pointer to the element that will be used for + * iteration + * @param[in] BODY Block to execute during iteration + * + * @note Iteration will execute BODY with eltp corresponding successively to + * all elements found in the vector. It is implemented using the more generic + * enumeration function. + */ +#define vector_foreach(vector, eltp, BODY) \ + ({ \ + unsigned _vector_var (i); \ + vector_enumerate ((vector), _vector_var (i), (eltp), BODY); \ + }) + +/** + * @brief Helper function used by vector_foreach(). + */ +#define vector_enumerate(vector, i, eltp, BODY) \ + ({ \ + for ((i) = 0; (i) < vector_len (vector); (i)++) \ + { \ + eltp = (vector) + (i); \ + { \ + BODY; \ + } \ + } \ + }) + +#endif /* UTIL_VECTOR_H */ diff --git a/lib/includes/hicn/util/win_portability.h b/lib/includes/hicn/util/win_portability.h index 5f30cfbb2..609203afc 100644 --- a/lib/includes/hicn/util/win_portability.h +++ b/lib/includes/hicn/util/win_portability.h @@ -1,45 +1,45 @@ -/*
- * Copyright (c) 2019 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.
- */
-
-#pragma once
-#include <hicn/util/windows/windows_Utils.h>
-#include <afunix.h>
-#include <io.h>
-#include <iphlpapi.h>
-#include <process.h>
-#include <stdio.h>
-#pragma comment(lib, "IPHLPAPI.lib")
-
-#ifndef in_port_t
-#define in_port_t uint16_t
-#endif
-
-#ifndef in_addr_t
-#define in_addr_t uint32_t
-#endif
-
-#ifndef strncasecmp
-#define strncasecmp _strnicmp
-#endif
-
-#ifndef strcasecmp
-#define strcasecmp _stricmp
-#endif
-
-#define HAVE_STRUCT_TIMESPEC
-
-#ifndef getline
-int getline(char **lineptr, size_t *n, FILE *stream);
+/* + * Copyright (c) 2021 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. + */ + +#pragma once +#include <hicn/util/windows/windows_Utils.h> +#include <afunix.h> +#include <io.h> +#include <iphlpapi.h> +#include <process.h> +#include <stdio.h> +#pragma comment(lib, "IPHLPAPI.lib") + +#ifndef in_port_t +#define in_port_t uint16_t +#endif + +#ifndef in_addr_t +#define in_addr_t uint32_t +#endif + +#ifndef strncasecmp +#define strncasecmp _strnicmp +#endif + +#ifndef strcasecmp +#define strcasecmp _stricmp +#endif + +#define HAVE_STRUCT_TIMESPEC + +#ifndef getline +int getline (char **lineptr, size_t *n, FILE *stream); #endif
\ No newline at end of file diff --git a/lib/includes/hicn/util/windows/dlfcn.h b/lib/includes/hicn/util/windows/dlfcn.h index 7775226cd..f1457964e 100644 --- a/lib/includes/hicn/util/windows/dlfcn.h +++ b/lib/includes/hicn/util/windows/dlfcn.h @@ -5,8 +5,8 @@ #define RTLD_GLOBAL 0x100 /* do not hide entries in this module */ #define RTLD_LOCAL 0x000 /* hide entries in this module */ -#define RTLD_LAZY 0x000 /* accept unresolved externs */ -#define RTLD_NOW 0x001 /* abort if module has unresolved externs */ +#define RTLD_LAZY 0x000 /* accept unresolved externs */ +#define RTLD_NOW 0x001 /* abort if module has unresolved externs */ /* How to call in Windows: @@ -16,15 +16,16 @@ */ #ifdef __cplusplus -extern "C" { +extern "C" +{ #endif - void *dlopen (const char *filename, int flag); - int dlclose (void *handle); + void *dlopen (const char *filename, int flag); + int dlclose (void *handle); - void *dlsym (void *handle, const char *name); + void *dlsym (void *handle, const char *name); -const char *dlerror (void); + const char *dlerror (void); #ifdef __cplusplus } diff --git a/lib/includes/hicn/util/windows/windows_utils.h b/lib/includes/hicn/util/windows/windows_utils.h index d24aaadbf..e15c0d752 100755..100644 --- a/lib/includes/hicn/util/windows/windows_utils.h +++ b/lib/includes/hicn/util/windows/windows_utils.h @@ -1,162 +1,166 @@ -/*
- * Copyright (c) 2019 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.
- */
-
-#ifndef WINDOWS_UTILS_H
-#define WINDOWS_UTILS_H
-#define WIN32_LEAN_AND_MEAN
-#define HAVE_STRUCT_TIMESPEC
-#ifndef NOMINMAX
-#define NOMINMAX
-#endif
-#include <Windows.h>
-#include <stdint.h>
-#include <io.h>
-#include <stdlib.h>
-#include <winsock2.h>
-#include <WS2tcpip.h>
-#include "dlfcn.h"
-
-#ifndef IOVEC
-#define IOVEC
-struct iovec {
- void* iov_base;
- size_t iov_len;
-};
-#endif
-
-typedef uint16_t in_port_t;
-
-#ifndef SLEEP
-#define SLEEP
-#define sleep Sleep
-#endif
-
-#ifndef USLEEP
-#define USLEEP
-void usleep(__int64 usec);
-#endif
-
-#ifndef S_ISDIR
-#define S_ISDIR(mode) (((mode) & S_IFMT) == S_IFDIR)
-#endif
-
-#define PARCLibrary_DISABLE_ATOMICS
-#include <BaseTsd.h>
-typedef SSIZE_T ssize_t;
-
-#ifndef __ATTRIBUTE__
-#define __ATTRIBUTE__
-#define __attribute__(A)
-#endif
-
-#ifndef RESTRICT
-#define RESTRICT
-#define restrict __restrict
-#endif
-
-#ifndef GETTIMEOFDAY
-#define GETTIMEOFDAY
-int gettimeofday(struct timeval * tp, struct timezone * tzp);
-#endif
-
-#ifndef timersub
-#define timersub(a, b, result) \
- do { \
- (result)->tv_sec = (a)->tv_sec - (b)->tv_sec; \
- (result)->tv_usec = (a)->tv_usec - (b)->tv_usec; \
- if ((result)->tv_usec < 0) { \
- --(result)->tv_sec; \
- (result)->tv_usec += 1000000; \
- } \
- } while (0)
-#endif // timersub
-
-#ifndef dup
-#define dup _dup
-#endif
-
-#ifndef access
-#define access _access
-#endif
-
-#ifndef __cplusplus
-
-#ifndef read
-#define read _read
-#endif
-
-#ifndef close
-#define close _close
-#endif
-
-#ifndef write
-#define write _write
-#endif
-
-#ifndef open
-#define open _open
-#endif
-
-#endif
-
-#ifndef unlink
-#define unlink _unlink
-#endif
-
-#ifndef strcasecmp
-#define strncasecmp _strnicmp
-#endif
-
-#ifndef strcasecmp
-
-#define strcasecmp _stricmp
-#endif
-
-#ifndef S_ISREG
-#define S_ISREG(mode) (((mode) & S_IFMT) == S_IFREG)
-#endif
-#ifndef R_OK
-#define R_OK 4 /* Test for read permission. */
-#endif
-#ifndef W_OK
-#define W_OK 2 /* Test for write permission. */
-#endif
-#ifndef F_OK
-#define F_OK 0
-#endif
-
-#ifndef STDIN_FILENO
-#define STDIN_FILENO _fileno(stdin)
-#endif
-
-#ifndef STDOUT_FILENO
-#define STDOUT_FILENO _fileno(stdout)
-#endif
-
-#ifndef STDERR_FILENO
-#define STDERR_FILENO _fileno(stderr)
-#endif
-
-#endif
-
-#ifndef __bswap_constant_32
-#define __bswap_constant_32(x) \
- ((((x) & 0xff000000u) >> 24) | (((x) & 0x00ff0000u) >> 8) \
- | (((x) & 0x0000ff00u) << 8) | (((x) & 0x000000ffu) << 24))
-#endif
-
-#ifndef bzero
-#define bzero(b,len) (memset((b), '\0', (len)), (void) 0)
+/* + * Copyright (c) 2021 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. + */ + +#ifndef WINDOWS_UTILS_H +#define WINDOWS_UTILS_H +#define WIN32_LEAN_AND_MEAN +#define HAVE_STRUCT_TIMESPEC +#ifndef NOMINMAX +#define NOMINMAX +#endif +#include <Windows.h> +#include <stdint.h> +#include <io.h> +#include <stdlib.h> +#include <winsock2.h> +#include <WS2tcpip.h> +#include "dlfcn.h" + +#ifndef IOVEC +#define IOVEC +struct iovec +{ + void *iov_base; + size_t iov_len; +}; +#endif + +typedef uint16_t in_port_t; + +#ifndef SLEEP +#define SLEEP +#define sleep Sleep +#endif + +#ifndef USLEEP +#define USLEEP +void usleep (__int64 usec); +#endif + +#ifndef S_ISDIR +#define S_ISDIR(mode) (((mode) &S_IFMT) == S_IFDIR) +#endif + +#define PARCLibrary_DISABLE_ATOMICS +#include <BaseTsd.h> +typedef SSIZE_T ssize_t; + +#ifndef __ATTRIBUTE__ +#define __ATTRIBUTE__ +#define __attribute__(A) +#endif + +#ifndef RESTRICT +#define RESTRICT +#define restrict __restrict +#endif + +#ifndef GETTIMEOFDAY +#define GETTIMEOFDAY +int gettimeofday (struct timeval *tp, struct timezone *tzp); +#endif + +#ifndef timersub +#define timersub(a, b, result) \ + do \ + { \ + (result)->tv_sec = (a)->tv_sec - (b)->tv_sec; \ + (result)->tv_usec = (a)->tv_usec - (b)->tv_usec; \ + if ((result)->tv_usec < 0) \ + { \ + --(result)->tv_sec; \ + (result)->tv_usec += 1000000; \ + } \ + } \ + while (0) +#endif // timersub + +#ifndef dup +#define dup _dup +#endif + +#ifndef access +#define access _access +#endif + +#ifndef __cplusplus + +#ifndef read +#define read _read +#endif + +#ifndef close +#define close _close +#endif + +#ifndef write +#define write _write +#endif + +#ifndef open +#define open _open +#endif + +#endif + +#ifndef unlink +#define unlink _unlink +#endif + +#ifndef strcasecmp +#define strncasecmp _strnicmp +#endif + +#ifndef strcasecmp + +#define strcasecmp _stricmp +#endif + +#ifndef S_ISREG +#define S_ISREG(mode) (((mode) &S_IFMT) == S_IFREG) +#endif +#ifndef R_OK +#define R_OK 4 /* Test for read permission. */ +#endif +#ifndef W_OK +#define W_OK 2 /* Test for write permission. */ +#endif +#ifndef F_OK +#define F_OK 0 +#endif + +#ifndef STDIN_FILENO +#define STDIN_FILENO _fileno (stdin) +#endif + +#ifndef STDOUT_FILENO +#define STDOUT_FILENO _fileno (stdout) +#endif + +#ifndef STDERR_FILENO +#define STDERR_FILENO _fileno (stderr) +#endif + +#endif + +#ifndef __bswap_constant_32 +#define __bswap_constant_32(x) \ + ((((x) &0xff000000u) >> 24) | (((x) &0x00ff0000u) >> 8) | \ + (((x) &0x0000ff00u) << 8) | (((x) &0x000000ffu) << 24)) +#endif + +#ifndef bzero +#define bzero(b, len) (memset ((b), '\0', (len)), (void) 0) #endif
\ No newline at end of file |