aboutsummaryrefslogtreecommitdiffstats
path: root/hicn-light/src/hicn/base
diff options
context:
space:
mode:
Diffstat (limited to 'hicn-light/src/hicn/base')
-rw-r--r--hicn-light/src/hicn/base/CMakeLists.txt38
-rw-r--r--hicn-light/src/hicn/base/bitmap.h55
-rw-r--r--hicn-light/src/hicn/base/common.h62
-rw-r--r--hicn-light/src/hicn/base/hash.h250
-rw-r--r--hicn-light/src/hicn/base/khash.h627
-rw-r--r--hicn-light/src/hicn/base/loop.c355
-rw-r--r--hicn-light/src/hicn/base/loop.h104
-rw-r--r--hicn-light/src/hicn/base/pool.c88
-rw-r--r--hicn-light/src/hicn/base/pool.h104
-rw-r--r--hicn-light/src/hicn/base/vector.c54
-rw-r--r--hicn-light/src/hicn/base/vector.h70
11 files changed, 1807 insertions, 0 deletions
diff --git a/hicn-light/src/hicn/base/CMakeLists.txt b/hicn-light/src/hicn/base/CMakeLists.txt
new file mode 100644
index 000000000..5b2677ed1
--- /dev/null
+++ b/hicn-light/src/hicn/base/CMakeLists.txt
@@ -0,0 +1,38 @@
+# Copyright (c) 2017-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.
+
+cmake_minimum_required(VERSION 3.5 FATAL_ERROR)
+
+list(APPEND HEADER_FILES
+ ${CMAKE_CURRENT_SOURCE_DIR}/bitmap.h
+ ${CMAKE_CURRENT_SOURCE_DIR}/common.h
+ ${CMAKE_CURRENT_SOURCE_DIR}/khash.h
+ ${CMAKE_CURRENT_SOURCE_DIR}/loop.h
+ ${CMAKE_CURRENT_SOURCE_DIR}/pool.h
+ ${CMAKE_CURRENT_SOURCE_DIR}/vector.h
+)
+
+list(APPEND SOURCE_FILES
+ ${CMAKE_CURRENT_SOURCE_DIR}/loop.c
+ ${CMAKE_CURRENT_SOURCE_DIR}/pool.c
+ ${CMAKE_CURRENT_SOURCE_DIR}/vector.c
+)
+
+set(SOURCE_FILES ${SOURCE_FILES} PARENT_SCOPE)
+set(HEADER_FILES ${HEADER_FILES} PARENT_SCOPE)
+
+set(TO_INSTALL_HEADER_FILES
+ ${TO_INSTALL_HEADER_FILES}
+ ${HEADER_FILES}
+ PARENT_SCOPE
+)
diff --git a/hicn-light/src/hicn/base/bitmap.h b/hicn-light/src/hicn/base/bitmap.h
new file mode 100644
index 000000000..df94b8039
--- /dev/null
+++ b/hicn-light/src/hicn/base/bitmap.h
@@ -0,0 +1,55 @@
+/*
+ * Copyright (c) 2020 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 <string.h>
+#include "common.h"
+
+#define BITMAP_WIDTH(bitmap) (sizeof((bitmap)[0]) * 8)
+
+#define bitmap_init(bitmap, size) \
+ vector_init(bitmap, next_pow2(size / BITMAP_WIDTH(bitmap)))
+
+#define bitmap_ensure_pos(bitmap, pos) vector_ensure_pos(bitmap, pos / BITMAP_WIDTH(bitmap))
+
+#define bitmap_get(bitmap, i) ((bitmap)[(i) / BITMAP_WIDTH(bitmap)] & (1 << ((i) % BITMAP_WIDTH(bitmap))))
+
+#define bitmap_is_set(bitmap, i) (bitmap_get((bitmap), (i)) == 1)
+
+#define bitmap_is_unset(bitmap, i) (bitmap_get((bitmap), (i)) == 0)
+
+#define bitmap_set(bitmap, i) bitmap[(i) / BITMAP_WIDTH(bitmap)] |= 1 << ((i) % BITMAP_WIDTH(bitmap))
+
+#define bitmap_unset(bitmap, i) bitmap[(i) / BITMAP_WIDTH(bitmap)] &= ~ (1 << ((i) % BITMAP_WIDTH(bitmap)))
+
+#define bitmap_set_to(bitmap, pos) \
+do { \
+ size_t offset = (pos / BITMAP_WIDTH(bitmap) + 1); \
+ memset(bitmap, 0xFF, pos * sizeof(bitmap[0])); \
+ size_t set_bits = offset * BITMAP_WIDTH(bitmap); \
+ for (unsigned i = pos; i < set_bits; i++) \
+ bitmap_unset(bitmap, i); \
+} while(0);
+
+#endif /* UTIL_BITMAP_H */
diff --git a/hicn-light/src/hicn/base/common.h b/hicn-light/src/hicn/base/common.h
new file mode 100644
index 000000000..996050308
--- /dev/null
+++ b/hicn-light/src/hicn/base/common.h
@@ -0,0 +1,62 @@
+/*
+ * Copyright (c) 2020 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 array.h
+ * \brief Fixed-size pool allocator
+ */
+
+#ifndef UTIL_COMMON_H
+#define UTIL_COMMON_H
+
+#define round_pow2(x, pow2) ((x + pow2 - 1) & ~(pow2 - 1))
+
+#define _SIZEOF_ALIGNED(x, size) round_pow2(sizeof(x), size)
+#define SIZEOF_ALIGNED(x) _SIZEOF_ALIGNED(x, sizeof(void*))
+
+/* Definitions for builtins unavailable on MSVC */
+#if defined(_MSC_VER) && !defined(__clang__)
+#include <intrin.h>
+
+uint32_t __inline __builtin_ctz(uint32_t value) {
+ uint32_t trailing_zero = 0;
+ if (_BitScanForward(&trailing_zero, value))
+ return trailing_zero;
+ else
+ return 32;
+}
+
+uint32_t __inline __builtin_clz(uint32_t value) {
+ uint32_t leading_zero = 0;
+ if (_BitScanReverse(&leading_zero, value))
+ return 31 - leading_zero;
+ else
+ return 32;
+}
+
+uint32_t __inline __builtin_clzll(uint64_t value) {
+ uint32_t leading_zero = 0;
+ if (_BitScanReverse64(&leading_zero, value))
+ return 63 - leading_zero;
+ else
+ return 64;
+}
+
+#define __builtin_clzl __builtin_clzll
+#endif
+
+#define next_pow2(x) (x == 1 ? 1 : 1<<(64-__builtin_clzl(x-1)))
+
+#endif /* UTIL_COMMON_H */
diff --git a/hicn-light/src/hicn/base/hash.h b/hicn-light/src/hicn/base/hash.h
new file mode 100644
index 000000000..0b6a659bd
--- /dev/null
+++ b/hicn-light/src/hicn/base/hash.h
@@ -0,0 +1,250 @@
+/*
+ * Copyright (c) 2017-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.
+ */
+
+/*
+ * \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
+
+#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/hicn-light/src/hicn/base/khash.h b/hicn-light/src/hicn/base/khash.h
new file mode 100644
index 000000000..f75f3474c
--- /dev/null
+++ b/hicn-light/src/hicn/base/khash.h
@@ -0,0 +1,627 @@
+/* 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)
+
+#endif /* __AC_KHASH_H */
diff --git a/hicn-light/src/hicn/base/loop.c b/hicn-light/src/hicn/base/loop.c
new file mode 100644
index 000000000..fecab9c5f
--- /dev/null
+++ b/hicn-light/src/hicn/base/loop.c
@@ -0,0 +1,355 @@
+/*
+ * Copyright (c) 2017-2020 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 loop.c
+ * @brief Implementation of event loop based on libevent
+ */
+
+#include <assert.h>
+#include <event2/event.h>
+#include <event2/thread.h>
+#include <fcntl.h> // fcntl
+#ifdef WITH_THREAD
+#include <pthread.h>
+#endif /* WITH_THREAD */
+#include <stdlib.h>
+#include <sys/timerfd.h>
+#include <unistd.h> // fcntl
+
+#include <hicn/util/log.h>
+#include <hicn/util/map.h>
+
+#include "loop.h"
+
+loop_t * MAIN_LOOP = NULL;
+
+/**
+ * \brief Holds all callback parameters
+ */
+typedef struct {
+ void * owner;
+ fd_callback_t callback;
+ void * data;
+} cb_wrapper_args_t;
+
+TYPEDEF_MAP_H(event_map, int, struct event *);
+TYPEDEF_MAP(event_map, int, struct event *, int_cmp, int_snprintf, generic_snprintf);
+
+/* Map that associates timer fds with their associated cb_wrapper_args_t */
+TYPEDEF_MAP_H(timer_fd_map, int, cb_wrapper_args_t *);
+TYPEDEF_MAP(timer_fd_map, int, cb_wrapper_args_t *, int_cmp, int_snprintf, generic_snprintf);
+
+struct loop_s {
+ struct event_base * event_base;
+ event_map_t * event_map;
+ timer_fd_map_t * timer_fd_map;
+#ifdef WITH_THREAD
+ pthread_t thread;
+#endif /* WITH_THREAD */
+};
+
+loop_t *
+loop_create()
+{
+ loop_t * loop = malloc(sizeof(loop_t));
+ if (!loop) {
+ ERROR("[loop_create] Failed to allocate memory");
+ goto ERR_MALLOC;
+ }
+
+#ifdef WITH_THREAD
+ evthread_use_pthreads();
+#endif /* WITH_THREAD */
+
+ loop->event_base = event_base_new();
+ if (!loop)
+ goto ERR_EVENT;
+
+ loop->event_map = event_map_create();
+ if (!loop->event_map) {
+ ERROR("[loop_create] Failed to create event_map");
+ goto ERR_EVENT_MAP;
+ }
+
+ loop->timer_fd_map = timer_fd_map_create();
+ if (!loop->timer_fd_map) {
+ ERROR("[loop_create] Failed to create timer_fd_map");
+ goto ERR_TIMER_FD_MAP;
+ }
+
+ event_set_log_callback(NULL);
+
+ return loop;
+
+ timer_fd_map_free(loop->timer_fd_map);
+ERR_TIMER_FD_MAP:
+ event_map_free(loop->event_map);
+ERR_EVENT_MAP:
+ event_base_free(loop->event_base);
+ERR_EVENT:
+ free(loop);
+ERR_MALLOC:
+ return NULL;
+}
+
+void
+loop_free(loop_t * loop)
+{
+ /*
+ * Release all timer cb_wrapper_args_t
+ *
+ * We need to stop all timers, this should release associated fd events at
+ * the same time... for that reason, this code has to be called before
+ * releasing events
+ */
+
+ int * timer_fd_map_array;
+ int n = timer_fd_map_get_key_array(loop->timer_fd_map, &timer_fd_map_array);
+ if (n < 0) {
+ ERROR("[loop_free] Could not get event map array");
+ } else {
+ for (unsigned i = 0; i < n; i++) {
+ int fd = timer_fd_map_array[i];
+ if (loop_unregister_timer(loop, fd) < 0) {
+ ERROR("[loop_free] Could not unregister timer");
+ }
+ }
+ free(timer_fd_map_array);
+ }
+ timer_fd_map_free(loop->timer_fd_map);
+
+ /* Release all events */
+
+ int * event_map_array;
+ n = event_map_get_key_array(loop->event_map, &event_map_array);
+ if (n < 0) {
+ ERROR("[loop_free] Could not get event map array");
+ } else {
+ for (unsigned i = 0; i < n; i++) {
+ int fd = event_map_array[i];
+ if (loop_unregister_fd(loop, fd) < 0) {
+ ERROR("[loop_free] Could not unregister fd");
+ }
+ }
+ free(event_map_array);
+ }
+ event_map_free(loop->event_map);
+
+ event_base_free(loop->event_base);
+
+ free(loop);
+}
+
+int
+loop_dispatch(loop_t * loop)
+{
+#ifdef WITH_THREAD
+ if (pthread_create(&loop->thread, NULL, (void * (*)(void *))event_base_dispatch, loop->event_base)) {
+ fprintf(stderr, "Error creating thread\n");
+ return -1;
+ }
+#else
+ event_base_dispatch(loop->event_base);
+#endif /* WITH_THREAD */
+ return 0;
+}
+
+int
+loop_undispatch(loop_t * loop)
+{
+#ifdef WITH_THREAD
+ DEBUG("Waiting for loop to terminate...");
+ if(pthread_join(loop->thread, NULL)) {
+ fprintf(stderr, "Error joining thread\n");
+ return -1;
+ }
+ DEBUG("Loop terminated !");
+#endif /* WITH_THREAD */
+ return 0;
+}
+
+void
+loop_break(loop_t * loop)
+{
+ event_base_loopbreak(loop->event_base);
+}
+
+void cb_wrapper(evutil_socket_t fd, short what, void * arg) {
+ cb_wrapper_args_t * cb_wrapper_args = arg;
+ cb_wrapper_args->callback(cb_wrapper_args->owner, fd, cb_wrapper_args->data);
+}
+
+int
+loop_register_fd(loop_t * loop, int fd, void * callback_owner,
+ fd_callback_t callback, void * callback_data)
+{
+ /* This will be freed with the event */
+ cb_wrapper_args_t * cb_wrapper_args = malloc(sizeof(cb_wrapper_args_t));
+ *cb_wrapper_args = (cb_wrapper_args_t) {
+ .owner = callback_owner,
+ .callback = callback,
+ .data = callback_data,
+ };
+
+ evutil_make_socket_nonblocking(fd);
+ struct event * event = event_new(loop->event_base, fd, EV_READ | EV_PERSIST, cb_wrapper, cb_wrapper_args);
+ if (!event) {
+ ERROR("[loop_register_fd] event_new");
+ goto ERR_EVENT_NEW;
+ }
+
+ if (event_add(event, NULL) < 0) {
+ ERROR("[loop_register_fd] event_add");
+ goto ERR_EVENT_ADD;
+ }
+
+ if (event_map_add(loop->event_map, fd, event) < 0) {
+ ERROR("[loop_register_fd] event_map_add");
+ goto ERR_EVENT_MAP;
+ }
+
+ return 0;
+
+ERR_EVENT_MAP:
+ERR_EVENT_ADD:
+ event_free(event);
+ERR_EVENT_NEW:
+ return -1;
+}
+
+int
+loop_unregister_fd(loop_t * loop, int fd)
+{
+ struct event * event = NULL;
+
+ if (event_map_remove(loop->event_map, fd, &event) < 0) {
+ ERROR("[loop_unregister_fd] Error removing event associated to fd");
+ return -1;
+ }
+
+ assert(event);
+
+ cb_wrapper_args_t * cb_wrapper_args = event_get_callback_arg(event);
+ free(cb_wrapper_args);
+
+ event_del(event);
+ event_free(event);
+
+ return 0;
+}
+
+int
+loop_timer_callback(loop_t * loop, int fd, void * data)
+{
+ char buf[1024]; /* size is not important */
+ cb_wrapper_args_t * cb_wrapper_args = data;
+ while (read(fd, &buf, sizeof(buf)) > 0)
+ ;
+
+ int rc = cb_wrapper_args->callback(cb_wrapper_args->owner, fd,
+ cb_wrapper_args->data);
+
+ return rc;
+}
+
+int
+_loop_register_timer(loop_t * loop, unsigned delay_ms, void * owner,
+ fd_callback_t callback, void * data)
+{
+ int fd = timerfd_create(CLOCK_MONOTONIC, 0);
+ if (fd == -1) {
+ perror("timerfd_create");
+ return -1;
+ }
+
+ if (fcntl(fd, F_SETFL, O_NONBLOCK) < 0) {
+ perror("fcntl");
+ return -1;
+ }
+
+ struct itimerspec ts = {
+ .it_interval = {
+ .tv_sec = delay_ms / 1000,
+ .tv_nsec = (delay_ms % 1000) * 1000000,
+ },
+ .it_value = {
+ .tv_sec = delay_ms / 1000,
+ .tv_nsec = (delay_ms % 1000) * 1000000,
+ }
+ };
+
+ if (timerfd_settime(fd, 0, &ts, NULL) == -1) {
+ perror("timerfd_settime");
+ return -1;
+ }
+
+ /* This should be freed together with the timer release */
+ cb_wrapper_args_t * cb_wrapper_args = malloc(sizeof(cb_wrapper_args_t));
+ *cb_wrapper_args = (cb_wrapper_args_t) {
+ .owner = owner,
+ .callback = callback,
+ .data = data,
+ };
+
+ if (timer_fd_map_add(loop->timer_fd_map, fd, cb_wrapper_args) < 0) {
+ ERROR("[loop_register_timer] Could not add cb_wrapper to timer map");
+ return -1;
+ }
+
+ if (loop_register_fd(loop, fd, loop,
+ (fd_callback_t) loop_timer_callback, cb_wrapper_args) < 0) {
+ ERROR("[loop_register_timer] Error registering fd to event loop");
+ return -1;
+ }
+
+ return fd;
+}
+
+int
+loop_unregister_timer(loop_t * loop, int fd)
+{
+ struct itimerspec ts = {
+ .it_interval = {
+ .tv_sec = 0,
+ .tv_nsec = 0,
+ },
+ .it_value = { /* This value disables the timer */
+ .tv_sec = 0,
+ .tv_nsec = 0,
+ }
+ };
+ ts.it_value.tv_sec = 0;
+
+ if (timerfd_settime(fd, 0, &ts, NULL) == -1) {
+ perror("timerfd_settime");
+ return -1;
+ }
+
+ cb_wrapper_args_t * cb_wrapper_args;
+ if (timer_fd_map_remove(loop->timer_fd_map, fd, &cb_wrapper_args) < 0) {
+ ERROR("[loop_unregister_timer] Could not remove cb_wrapper from timer map");
+ return -1;
+ }
+ assert(cb_wrapper_args);
+ free(cb_wrapper_args);
+
+ if (loop_unregister_fd(loop, fd) < 0) {
+ ERROR("[loop_unregister_timer] Error unregistering fd from event loop");
+ return -1;
+ }
+
+ return 0;
+}
diff --git a/hicn-light/src/hicn/base/loop.h b/hicn-light/src/hicn/base/loop.h
new file mode 100644
index 000000000..b73d91738
--- /dev/null
+++ b/hicn-light/src/hicn/base/loop.h
@@ -0,0 +1,104 @@
+/*
+ * Copyright (c) 2017-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.
+ */
+
+/**
+ * \file loop.h
+ * \brief Face manager main loop
+ */
+
+#ifndef FACEMGR_LOOP_H
+#define FACEMGR_LOOP_H
+
+/* fd & timer callbacks */
+
+typedef int (*fd_callback_t)(void * owner, int fd, void * data);
+
+typedef struct {
+ int fd;
+ void *owner;
+ fd_callback_t callback;
+ //int (*callback)(void * owner, int fd, void * data);
+ void *data;
+} fd_callback_data_t;
+
+/* loop */
+
+typedef struct loop_s loop_t;
+
+/* Global loop to be used in single threaded applications */
+extern loop_t * MAIN_LOOP;
+
+/**
+ * \brief Creates a main loop
+ * \return Pointer to the newly created loop, or NULL in case of error
+ */
+loop_t * loop_create();
+
+/**
+ * \brief Releases a loop instance and frees all associated memory
+ * \param [in] loop - Pointer to the loop instance to free
+ */
+void loop_free(loop_t * loop);
+
+/**
+ * \brief Runs the loop instance to process events
+ * \param [in] loop - Pointer to the loop instance
+ * \return 0 if successful, -1 otherwise
+ */
+int loop_dispatch(loop_t * loop);
+
+/**
+ * \brief Terminates the dispatching of events
+ * \param [in] loop - Pointer to the loop instance
+ */
+int loop_undispatch(loop_t * loop);
+
+/**
+ * \brief Breaks out of the loop
+ * \param [in] loop - Pointer to the loop instance
+ */
+void loop_break(loop_t * loop);
+
+/**
+ * \brief Registers a new file descriptor to the event loop
+ * \param [in] fd - File descriptor to register
+ * \param [in] callback_owner - Pointer to the owner of the callack (first
+ * parameter of callback function)
+ * \param [in] callback - Callback function
+ * \param [in] callback_data - User data to pass alongside callback invocation
+ * \return 0 in case of success, -1 otherwise
+ */
+int
+loop_register_fd(loop_t * loop, int fd, void * callback_owner,
+ fd_callback_t callback, void * callback_data);
+
+/**
+ * \brief Unregisters a file descriptor from the event loop
+ * \param [in] fd - File descriptor to unregister
+ * \return 0 in case of success, -1 otherwise
+ */
+int
+loop_unregister_fd(loop_t * loop, int fd);
+
+int _loop_register_timer(loop_t * loop, unsigned delay_ms, void * owner,
+ fd_callback_t callback, void * data);
+
+#define loop_register_timer(loop, delay_ms, owner, callback, data) \
+ _loop_register_timer(loop, delay_ms, owner, (fd_callback_t) callback, data)
+
+int
+loop_unregister_timer(loop_t * loop, int fd);
+
+#endif /* FACEMGR_LOOP_H */
diff --git a/hicn-light/src/hicn/base/pool.c b/hicn-light/src/hicn/base/pool.c
new file mode 100644
index 000000000..abca86422
--- /dev/null
+++ b/hicn-light/src/hicn/base/pool.c
@@ -0,0 +1,88 @@
+/*
+ * Copyright (c) 2020 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.c
+ * \brief Implementation of fixed-size pool allocator
+ */
+
+#include <stdlib.h> // calloc
+
+#include "common.h"
+#include "pool.h"
+
+
+/**
+ * \brief Initialize the pool data structure
+ * \param [in,out] pool - Pointer to the pool structure storage
+ * \param [in] elt_size - Size of elements in vector
+ * \param [in] max_elts - Maximum size
+ *
+ * Note that an empty pool might be equal to NULL
+ */
+void
+_pool_init(void ** pool_ptr, size_t elt_size, size_t max_elts)
+{
+ pool_hdr_t * ph = calloc(POOL_HDRLEN + elt_size * max_elts, 1);
+ if (!ph)
+ abort();
+
+ /* Free indices */
+ off_t * free_indices;
+ vector_init(free_indices, max_elts);
+
+ uint_fast32_t * fb = ph->free_bitmap;
+ bitmap_init(fb, max_elts);
+ bitmap_set_to(fb, max_elts);
+
+ for(unsigned i = 0; i < max_elts; i++)
+ free_indices[i] = (max_elts - 1) - i;
+ ph->free_indices = free_indices;
+
+ *pool_ptr = (uint8_t*)ph + POOL_HDRLEN;
+}
+
+void
+_pool_free(void ** pool_ptr)
+{
+ free(pool_hdr(*pool_ptr));
+ *pool_ptr = NULL;
+}
+
+void
+_pool_resize(void ** pool_ptr, size_t elt_size)
+{
+ pool_hdr_t * ph = pool_hdr(*pool_ptr);
+ size_t old_elts = ph->max_elts;
+ size_t new_elts = old_elts * 2;
+
+ /* Double pool storage */
+ ph = realloc(ph, POOL_HDRLEN + new_elts * elt_size);
+ if (!ph)
+ abort();
+ ph->max_elts = new_elts;
+
+ /*
+ * After resize, the pool will have old_elts free indices, ranging from
+ * old_elts to (new_elts - 1)
+ */
+ off_t * free_indices = ph->free_indices;
+ vector_ensure_pos(free_indices, old_elts);
+ for (unsigned i = 0; i < old_elts; i++)
+ free_indices[i] = new_elts - 1 - i;
+
+ /* Reassign pool pointer */
+ *pool_ptr = (uint8_t*)ph + POOL_HDRLEN;
+}
diff --git a/hicn-light/src/hicn/base/pool.h b/hicn-light/src/hicn/base/pool.h
new file mode 100644
index 000000000..360dedc5e
--- /dev/null
+++ b/hicn-light/src/hicn/base/pool.h
@@ -0,0 +1,104 @@
+/*
+ * Copyright (c) 2020 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 array.h
+ * \brief Fixed-size pool allocator
+ */
+
+#ifndef UTIL_POOL_H
+#define UTIL_POOL_H
+
+#include <stdint.h>
+
+#include "bitmap.h"
+#include "vector.h"
+
+/** Local variable naming macro. */
+#define _pool_var(v) _pool_##v
+
+
+typedef struct {
+ size_t elt_size;
+ size_t max_elts;
+ uint_fast32_t * free_bitmap;
+ off_t * free_indices; /* vector of free indices */
+} pool_hdr_t;
+
+void _pool_init(void ** pool_ptr, size_t elt_size, size_t max_elts);
+void _pool_free(void ** pool_ptr);
+void _pool_resize(void ** pool_ptr, size_t elt_size);
+
+#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))
+
+// XXX TODO need common naming for cur_len, len, max_len
+#define pool_elts(pool) \
+ (pool_hdr(pool)->max_elts - vector_len((pool_hdr(pool)->free_indices)))
+
+#define pool_init(pool, max_elts) \
+ _pool_init((void**)&pool, sizeof(pool[0]), max_elts);
+
+#define pool_free(pool) \
+ _pool_free((void**)&pool);
+
+#define pool_get(pool, elt) \
+do { \
+ pool_hdr_t * _pool_var(ph) = pool_hdr(pool); \
+ u64 _pool_var(l) = vector_len(_pool_var(ph)->free_indices); \
+ if (_pool_var(l) == 0) \
+ _pool_resize((void**)&(pool), sizeof((pool)[0])); \
+ off_t _pool_var(free_id) = \
+ _pool_var(ph)->free_indices[_pool_var(l) - 1]; \
+ elt = (pool) + _pool_var(free_id); \
+ memset(&elt, 0, sizeof(elt)); \
+} while(0)
+
+#define pool_put(pool, elt) \
+do { \
+ pool_hdr_t * _pool_var(ph) = pool_hdr(pool); \
+ u64 _pool_var(l) = vector_len(_pool_var(ph)->free_indices); \
+ vector_ensure_pos(_pool_var(ph)->free_indices, _pool_var(l)); \
+ _pool_var(ph)->free_indices[_pool_var(l)] = (elt) - (pool); \
+ vector_len(_pool_var(ph)->free_indices)++; \
+ bitmap_set(_pool_var(ph)->free_bitmap, _pool_var(l)); \
+} while(0)
+
+#define pool_validate_id(pool, id) \
+ bitmap_is_unset((pool_hdr(pool))->free_bitmap, (id))
+
+#define pool_enumerate(pool, i, eltp, BODY) \
+do { \
+ pool_hdr_t * _pool_var(ph) = pool_hdr(pool); \
+ uint_fast32_t * _pool_var(fb) = _pool_var(ph)->free_bitmap; \
+ for((i) = 0; (i) < _pool_var(ph)->max_elts; (i)++) { \
+ if (bitmap_is_unset(_pool_var(fb), (i))) \
+ continue; \
+ eltp = (pool) + (i); \
+ do { BODY; } while (0); \
+ } \
+} while(0)
+
+#define pool_foreach(pool, eltp, BODY) \
+do { \
+ unsigned _pool_var(i); \
+ pool_enumerate((pool), _pool_var(i), (eltp), BODY); \
+} while(0)
+
+
+
+#endif /* UTIL_POOL_H */
diff --git a/hicn-light/src/hicn/base/vector.c b/hicn-light/src/hicn/base/vector.c
new file mode 100644
index 000000000..00ed7c305
--- /dev/null
+++ b/hicn-light/src/hicn/base/vector.c
@@ -0,0 +1,54 @@
+/*
+ * Copyright (c) 2020 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.c
+ * \brief Implementation of resizeable static array
+ */
+
+#include <stddef.h> // size_t
+#include <stdlib.h> // calloc
+
+#include "vector.h"
+
+void
+_vector_init(void ** vector_ptr, size_t elt_size, size_t max_elts)
+{
+ vector_hdr_t * vh = calloc(VECTOR_HDRLEN + elt_size * max_elts, 1);
+ *vector_ptr = (uint8_t*)vh - VECTOR_HDRLEN;
+}
+
+void
+_vector_free(void ** vector_ptr)
+{
+ free(vector_hdr(*vector_ptr));
+ *vector_ptr = NULL;
+}
+
+void
+_vector_resize(void ** vector_ptr, size_t elt_size, off_t pos)
+{
+ vector_hdr_t * vh = vector_hdr(*vector_ptr);
+ size_t new_elts = (pos > 0) ? next_pow2(pos) : vh->max_elts * 2;
+
+ /* Double the allocated vector size */
+ vh = realloc(vh, VECTOR_HDRLEN + new_elts * elt_size);
+ if (!vh)
+ abort();
+ vh->max_elts = new_elts;
+
+ /* Reassign vector pointer */
+ *vector_ptr = (uint8_t*) + VECTOR_HDRLEN;
+}
diff --git a/hicn-light/src/hicn/base/vector.h b/hicn-light/src/hicn/base/vector.h
new file mode 100644
index 000000000..9b99ba813
--- /dev/null
+++ b/hicn-light/src/hicn/base/vector.h
@@ -0,0 +1,70 @@
+/*
+ * Copyright (c) 2020 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
+ */
+
+#ifndef UTIL_VECTOR_H
+#define UTIL_VECTOR_H
+
+#include <stddef.h>
+#include <stdint.h>
+#include <sys/types.h>
+
+#include "common.h"
+
+/** Local variable naming macro. */
+#define _vector_var(v) _vector_##v
+
+typedef struct {
+ size_t num_elts;
+ size_t max_elts;
+} vector_hdr_t;
+
+void _vector_init(void ** vector_ptr, size_t elt_size, size_t max_elts);
+void _vector_free(void ** vector_ptr);
+void _vector_resize(void ** vector_ptr, size_t elt_size, off_t pos);
+
+/* 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))
+
+#define vector_init(vector, max_elts) \
+ _vector_init((void**)&vector, sizeof(vector[0]), max_elts)
+
+#define vector_free(vector) \
+ _vector_free(&vector)
+
+#define vector_len(vector) (vector_hdr(vector)->num_elts)
+
+#define vector_resize(vector) _vector_resize((void**)&(vector), sizeof((vector)[0]), 0)
+
+#define vector_ensure_pos(vector, pos) \
+do { \
+ if ((pos) >= vector_len(vector)) \
+ _vector_resize((void**)&(vector), sizeof((vector)[0]), pos); \
+} while(0)
+
+#define vector_push(vector, elt) \
+do { \
+ vector_ensure_pos(vector_len(vector)); \
+ vector[vector_len(vector)++] = elt; \
+} while(0)
+
+#endif /* UTIL_VECTOR_H */