[HICN-272] new hicn-light fib

Change-Id: Id0f13d6aebecc724556a80d3b3d57e8e06b6b262
Signed-off-by: michele papalini <micpapal@cisco.com>

8 files changed, 417 insertions, 447 deletions

diff --git a/hicn-light/src/hicn/core/mapMe.c b/hicn-light/src/hicn/core/mapMe.c
index 865841f67..0f86dfd7e 100644
--- a/hicn-light/src/hicn/core/mapMe.c
+++ b/hicn-light/src/hicn/core/mapMe.c
@@ -583,7 +583,7 @@ static bool mapMe_onSpecialInterest(const MapMe *mapme,
 #else
     fibEntry = fibEntry_Create(name, fwdStrategy);
 #endif /* WITH_POLICY */
-    FibEntry *lpm = fib_LPM(fib, name);
+    FibEntry *lpm = fib_MatchName(fib, name);
     mapMe_CreateTFIB(fibEntry);
     fib_Add(fib, fibEntry);
     if (!lpm) {
@@ -755,7 +755,7 @@ void mapMe_onSpecialInterestAck(const MapMe *mapme, const uint8_t *msgBuffer,
 
   const Name * name =
       name_CreateFromPacket(msgBuffer, MessagePacketType_ContentObject);
-  name_setLen(name, prefix->len);
+  name_setLen((Name*) name, prefix->len);
   char * name_str = name_ToString(name);
   INFO(mapme, "[MAP-Me] Received ack for name prefix=%s seq=%d on conn id=%d",
           name_str, params->seq, conn_in_id);
diff --git a/hicn-light/src/hicn/core/name.c b/hicn-light/src/hicn/core/name.c
index 8cf8dacbc..f4ea7dbca 100644
--- a/hicn-light/src/hicn/core/name.c
+++ b/hicn-light/src/hicn/core/name.c
@@ -162,6 +162,24 @@ Name *name_Acquire(const Name *original) {
   return copy;
 }
 
+Name *name_Copy(const Name *original) {
+  parcAssertNotNull(original, "Parameter must be non-null");
+  Name *copy = parcMemory_AllocateAndClear(sizeof(Name));
+  parcAssertNotNull(copy, "parcMemory_AllocateAndClear(%zu) returned NULL",
+                    sizeof(Name));
+
+  copy->content_name = nameBitvector_Copy(original->content_name);
+  copy->segment = original->segment;
+  copy->name_hash = original->name_hash;
+
+  copy->refCountPtr = parcMemory_Allocate(sizeof(unsigned));
+  parcAssertNotNull(copy->refCountPtr, "parcMemory_Allocate(%zu) returned NULL",
+                    sizeof(unsigned));
+  *copy->refCountPtr = 1;
+
+  return copy;
+}
+
 uint32_t name_HashCode(const Name *name) {
   parcAssertNotNull(name, "Parameter must be non-null");
   return name->name_hash;
@@ -211,13 +229,6 @@ int name_Compare(const Name *a, const Name *b) {
   }
 }
 
-bool name_StartsWith(const Name *name, const Name *prefix) {
-  parcAssertNotNull(name, "Parameter name must be non-null");
-  parcAssertNotNull(prefix, "Parameter prefix must be non-null");
-
-  return nameBitvector_StartsWith(name->content_name, prefix->content_name);
-}
-
 char *name_ToString(const Name *name) {
   char *output = malloc(128);
 
@@ -231,8 +242,9 @@ char *name_ToString(const Name *name) {
   return output;
 }
 
-void name_setLen(const Name *name, uint8_t len) {
+void name_setLen(Name *name, uint8_t len) {
   nameBitvector_setLen(name->content_name, len);
+  name->name_hash = _computeHash(name);
 }
 
 #ifdef WITH_POLICY
diff --git a/hicn-light/src/hicn/core/name.h b/hicn-light/src/hicn/core/name.h
index 4eb80cf36..f2ae1f64e 100644
--- a/hicn-light/src/hicn/core/name.h
+++ b/hicn-light/src/hicn/core/name.h
@@ -48,6 +48,11 @@ void name_Release(Name **namePtr);
 Name *name_Acquire(const Name *original);
 
 /**
+ * returns a copy of the name
+ */
+Name *name_Copy(const Name *original);
+
+/**
  * A hash value for use in hash tables
  *
  */
@@ -71,17 +76,6 @@ bool name_Equals(const Name *a, const Name *b);
 int name_Compare(const Name *a, const Name *b);
 
 /**
- * @function metsName_StartsWith
- * @abstract Checks if name starts with prefix
- * @discussion
- *   Byte-by-byte prefix comparison
- *
- * @return True if the name is equal to or begins with prefix
- */
-
-bool name_StartsWith(const Name *name, const Name *prefix);
-
-/**
  * return the name in string format (bitvector + segment number)
  *
  */
@@ -93,7 +87,7 @@ char *name_ToString(const Name *name);
  * @param [in] message - Interest message
  * @param [in] len - Name length
  */
-void name_setLen(const Name *name, uint8_t len);
+void name_setLen(Name *name, uint8_t len);
 
 /**
  * Creates a name from a Address
diff --git a/hicn-light/src/hicn/core/nameBitvector.c b/hicn-light/src/hicn/core/nameBitvector.c
index 8078778e3..ad6884d02 100644
--- a/hicn-light/src/hicn/core/nameBitvector.c
+++ b/hicn-light/src/hicn/core/nameBitvector.c
@@ -27,24 +27,21 @@
 
 #include <hicn/utils/commands.h>
 
-#define BLOCKS 2
+#define NAME_LEN 2
 
-const uint64_t BLOCK_SIZE = 64;
+const uint64_t BV_SIZE = 64;
 const uint64_t WIDTH = 128;
-const uint64_t BLOCK_ONE = 0x1;
-
-// the bits are encoded in the following order:
-// 00100101001---101010  00100011---110100100
-// [bits[0] (uint64_t)]  [bits[1] (uint64_t)]
-// ^                  ^  ^                  ^
-// 0                 63 64                127
-// address  2200::0011 is encoded as:
-//   1000 1000 0000 0010 00000 ....0100 0100
-//   ^                                     ^
-//   0                                   127
+const uint64_t ONE = 0x1;
+
+// address b000:0000:0000:0001:c000:0000:0000:0001 is encodend as follow
+// [bits[0] uint64_t       ] [bits[1] unit64_t       ]
+// ^                       ^ ^                       ^
+// 63                      0 127                     64
+// [1000 0000 ... 0000 1101] [1000 0000 ... 0000 0011] //binary
+//    1                  b     1                  c    //hex
 
 struct name_bitvector {
-  uint64_t bits[BLOCKS];
+  uint64_t bits[NAME_LEN];
   uint8_t len;
   uint8_t IPversion;
 };
@@ -62,11 +59,11 @@ NameBitvector *nameBitvector_CreateFromInAddr(uint32_t addr, uint8_t len) {
   uint8_t addr_3 = (addr & 0x0000ff00) >> 8;
   uint8_t addr_4 = (addr & 0x000000ff);
 
-  bitvector->bits[1] = (bitvector->bits[1] | addr_4) << 8;
-  bitvector->bits[1] = (bitvector->bits[1] | addr_3) << 8;
-  bitvector->bits[1] = (bitvector->bits[1] | addr_2) << 8;
-  bitvector->bits[1] = (bitvector->bits[1] | addr_1);
-  bitvector->bits[1] = bitvector->bits[1] << 32;
+  bitvector->bits[0] = (bitvector->bits[0] | addr_4) << 8;
+  bitvector->bits[0] = (bitvector->bits[0] | addr_3) << 8;
+  bitvector->bits[0] = (bitvector->bits[0] | addr_2) << 8;
+  bitvector->bits[0] = (bitvector->bits[0] | addr_1);
+  bitvector->bits[0] = bitvector->bits[0] << 32;
 
   bitvector->len = len;
 
@@ -87,11 +84,11 @@ NameBitvector *nameBitvector_CreateFromIn6Addr(struct in6_addr *addr,
   bitvector->bits[1] = 0;
 
   for (int i = 0; i < 8; ++i) {
-    bitvector->bits[1] = (bitvector->bits[1] << 8) | addr->s6_addr[i];
+    bitvector->bits[0] = (bitvector->bits[0] << 8) | addr->s6_addr[i];
   }
 
   for (int i = 8; i < 16; ++i) {
-    bitvector->bits[0] = (bitvector->bits[0] << 8) | addr->s6_addr[i];
+    bitvector->bits[1] = (bitvector->bits[1] << 8) | addr->s6_addr[i];
   }
 
   bitvector->len = len;
@@ -191,38 +188,13 @@ int nameBitvector_Compare(const NameBitvector *a, const NameBitvector *b) {
   }
 }
 
-bool nameBitvector_StartsWith(const NameBitvector *name,
-                              const NameBitvector *prefix) {
-  parcAssertNotNull(name, "name cannot be NULL");
-  parcAssertNotNull(prefix, "prefix cannot be NULL");
-  parcAssertTrue(prefix->len > 0, "prefix length can not be 0");
-
-  if (prefix->len > BLOCK_SIZE)
-    return (name->bits[1] == prefix->bits[1]) &&
-           ((name->bits[0] ^ prefix->bits[0]) >>
-                (BLOCK_SIZE - (prefix->len - BLOCK_SIZE)) ==
-            0);
-
-  return ((name->bits[1] ^ prefix->bits[1]) >> (BLOCK_SIZE - prefix->len) == 0);
-}
-
-bool nameBitvector_testBit(const NameBitvector *name, uint8_t pos) {
-  if (pos == WIDTH) pos = 127;
-
-  uint8_t final_pos = (uint8_t)(WIDTH - name->len);
-
-  // the bit to test is inside the name/prefix len
-  if (pos > final_pos) {
-    return (name->bits[pos / BLOCK_SIZE] & (BLOCK_ONE << (pos % BLOCK_SIZE)));
-  }
+int nameBitvector_testBit(const NameBitvector *name, uint8_t pos, bool *bit) {
+  if(pos >= name->len  || pos > (WIDTH -1))
+    return -1;
 
-  // the bit to test is outside the name/prefix len
-  if (pos < final_pos) {
-    return false;
-  }
+  *bit = (name->bits[pos / BV_SIZE] & (ONE << ((BV_SIZE - 1) - (pos % BV_SIZE))));
 
-  // pos is equal to the name/prefix len
-  return true;
+  return 0;
 }
 
 uint64_t _diff_bit_log2(uint64_t val) {
@@ -257,31 +229,38 @@ uint64_t _diff_bit_log2(uint64_t val) {
   return result;
 }
 
-uint8_t nameBitvector_firstDiff(const NameBitvector *a,
-                                const NameBitvector *b) {
-  uint8_t res = 0;
-  uint64_t diff = a->bits[1] ^ b->bits[1];
-  if (diff)
-    res = (uint8_t)(64 + _diff_bit_log2(diff));
-  else
-    res = (uint8_t)_diff_bit_log2(a->bits[0] ^ b->bits[0]);
-
-  // res is computed over the bitvector which is composed by 128 bit all the
-  // times however the prefixes may be diffrent just because the have different
-  // lengths example: prefix 1: 0::/30 prefix 2: 0::/20 at this point of the
-  // function res would be 0 since both the bitvectors are composed by 0s but
-  // the function will return 127-20, which is the position at which the two
-  // prefix are different, since prefix 2 has only 20 bits
-
-  uint8_t len_diff;
+uint32_t nameBitvector_lpm(const NameBitvector *a,
+                          const NameBitvector *b) {
+  uint32_t limit;
+  uint32_t prefix_len;
   if (a->len < b->len)
-    len_diff = (uint8_t)(WIDTH - a->len);
+    limit = a->len;
   else
-    len_diff = (uint8_t)(WIDTH - b->len);
+    limit = b->len;
+
+  uint64_t diff = a->bits[0] ^ b->bits[0];
+  if(diff){
+    prefix_len = BV_SIZE - (_diff_bit_log2(diff) + 1);
+    //printf("if 1 diff = %lu plen = %d\n", diff, prefix_len);
+  }else{
+    prefix_len = BV_SIZE;
+    diff = a->bits[1] ^ b->bits[1];
+    if(diff){
+      prefix_len +=  (BV_SIZE - (_diff_bit_log2(diff) + 1));
+      //printf("if 2 diff = %lu plen = %d\n", diff, prefix_len);
+    }else{
+      prefix_len += BV_SIZE;
+    }
+  }
 
-  if (len_diff > res) res = len_diff;
+  if(prefix_len < limit)
+    return prefix_len;
+  return limit;
+}
 
-  return res;
+void nameBitvector_clear(NameBitvector *a, uint8_t start_from){
+  for(uint8_t pos = start_from; pos < WIDTH; pos++)
+      a->bits[pos / BV_SIZE] &= ~(ONE << ((BV_SIZE - 1) - (pos % BV_SIZE)));
 }
 
 int nameBitvector_ToIPAddress(const NameBitvector *name,
@@ -291,7 +270,7 @@ int nameBitvector_ToIPAddress(const NameBitvector *name,
     ip_address->family = AF_INET;
     ip_address->prefix_len = IPV4_ADDR_LEN_BITS;
 
-    uint32_t tmp_addr = name->bits[1] >> 32ULL;
+    uint32_t tmp_addr = name->bits[0] >> 32ULL;
     uint8_t addr_1 = (tmp_addr & 0xff000000) >> 24;
     uint8_t addr_2 = (tmp_addr & 0x00ff0000) >> 16;
     uint8_t addr_3 = (tmp_addr & 0x0000ff00) >> 8;
@@ -309,12 +288,12 @@ int nameBitvector_ToIPAddress(const NameBitvector *name,
     ip_address->prefix_len = name->len;  // IPV6_ADDR_LEN_BITS;
 
     for (int i = 0; i < 8; i++) {
-      addr->s6_addr[i] = (uint8_t)((name->bits[1] >> 8 * (7 - i)) & 0xFF);
+      addr->s6_addr[i] = (uint8_t)((name->bits[0] >> 8 * (7 - i)) & 0xFF);
     }
 
     int x = 0;
     for (int i = 8; i < 16; ++i) {
-      addr->s6_addr[i] = (uint8_t)((name->bits[0] >> 8 * (7 - x)) & 0xFF);
+      addr->s6_addr[i] = (uint8_t)((name->bits[1] >> 8 * (7 - x)) & 0xFF);
       x++;
     }
   }
@@ -329,7 +308,7 @@ Address *nameBitvector_ToAddress(const NameBitvector *name) {
     addr.sin_family = AF_INET;
     addr.sin_port = htons(1234);
 
-    uint32_t tmp_addr = name->bits[1] >> 32ULL;
+    uint32_t tmp_addr = name->bits[0] >> 32ULL;
     uint8_t addr_1 = (tmp_addr & 0xff000000) >> 24;
     uint8_t addr_2 = (tmp_addr & 0x00ff0000) >> 16;
     uint8_t addr_3 = (tmp_addr & 0x0000ff00) >> 8;
@@ -354,13 +333,13 @@ Address *nameBitvector_ToAddress(const NameBitvector *name) {
 
     for (int i = 0; i < 8; i++) {
       addr.sin6_addr.s6_addr[i] =
-          (uint8_t)((name->bits[1] >> 8 * (7 - i)) & 0xFF);
+          (uint8_t)((name->bits[0] >> 8 * (7 - i)) & 0xFF);
     }
 
     int x = 0;
     for (int i = 8; i < 16; ++i) {
       addr.sin6_addr.s6_addr[i] =
-          (uint8_t)((name->bits[0] >> 8 * (7 - x)) & 0xFF);
+          (uint8_t)((name->bits[1] >> 8 * (7 - x)) & 0xFF);
       x++;
     }
 
@@ -380,4 +359,4 @@ char *nameBitvector_ToString(const NameBitvector *name) {
   addressDestroy(&packetAddr);
 
   return output;
-}
\ No newline at end of file
+}
diff --git a/hicn-light/src/hicn/core/nameBitvector.h b/hicn-light/src/hicn/core/nameBitvector.h
index 6ff859e3b..44cc45662 100644
--- a/hicn-light/src/hicn/core/nameBitvector.h
+++ b/hicn-light/src/hicn/core/nameBitvector.h
@@ -30,9 +30,6 @@ NameBitvector *nameBitvector_CreateFromInAddr(uint32_t addr, uint8_t len);
 NameBitvector *nameBitvector_CreateFromIn6Addr(struct in6_addr *addr,
                                                uint8_t len);
 
-NameBitvector *nameBitvector_CreateFromAddress(const Address *prefix,
-                                               uint8_t len);
-
 NameBitvector *nameBitvector_Copy(const NameBitvector *original);
 
 void nameBitvector_Destroy(NameBitvector **bitvectorPtr);
@@ -45,12 +42,11 @@ bool nameBitvector_Equals(const NameBitvector *a, const NameBitvector *b);
 
 int nameBitvector_Compare(const NameBitvector *a, const NameBitvector *b);
 
-bool nameBitvector_StartsWith(const NameBitvector *name,
-                              const NameBitvector *prefix);
+int nameBitvector_testBit(const NameBitvector *name, uint8_t pos, bool *bit);
 
-bool nameBitvector_testBit(const NameBitvector *name, uint8_t pos);
+uint32_t nameBitvector_lpm(const NameBitvector *a, const NameBitvector *b);
 
-uint8_t nameBitvector_firstDiff(const NameBitvector *a, const NameBitvector *b);
+void nameBitvector_clear(NameBitvector *a, uint8_t start_from);
 
 int nameBitvector_ToIPAddress(const NameBitvector *name,
                               ip_address_t *ip_address);
diff --git a/hicn-light/src/hicn/processor/fib.c b/hicn-light/src/hicn/processor/fib.c
index 7cb94d4ba..6489e59e2 100644
--- a/hicn-light/src/hicn/processor/fib.c
+++ b/hicn-light/src/hicn/processor/fib.c
@@ -16,6 +16,7 @@
 #include <hicn/hicn-light/config.h>
 #include <stdio.h>
 
+#include <hicn/core/forwarder.h>
 #include <hicn/processor/fib.h>
 
 #include <parc/algol/parc_Memory.h>
@@ -23,9 +24,6 @@
 
 #include <parc/assert/parc_Assert.h>
 
-#define NULL_POS 128
-#define MSB_POS 127
-
 struct node;
 typedef struct node FibNode;
 
@@ -33,10 +31,11 @@ struct node {
   FibNode *left;
   FibNode *right;
   FibEntry *entry;
-  unsigned pos;
+  bool is_used;
 };
 
 struct fib {
+  Forwarder *forwarder;
   FibNode *root;
   unsigned size;
 };
@@ -45,7 +44,7 @@ struct fib {
 // Public API
 
 FibNode *_createNode(FibNode *left, FibNode *right, FibEntry *entry,
-                     unsigned pos) {
+                     bool is_used) {
   FibNode *n = parcMemory_AllocateAndClear(sizeof(FibNode));
   parcAssertNotNull(n, "parcMemory_AllocateAndClear(%zu) returned NULL",
                     sizeof(FibNode));
@@ -53,22 +52,18 @@ FibNode *_createNode(FibNode *left, FibNode *right, FibEntry *entry,
   n->left = left;
   n->right = right;
   n->entry = entry;
-  n->pos = pos;
+  n->is_used = is_used;
 
   return n;
 }
 
-FIB *fib_Create() {
+FIB *fib_Create(Forwarder *forwarder) {
   FIB *hicnFib = parcMemory_AllocateAndClear(sizeof(FIB));
   parcAssertNotNull(hicnFib, "parcMemory_AllocateAndClear(%zu) returned NULL",
                     sizeof(FIB));
 
-  hicnFib->root =
-      _createNode(NULL, NULL, NULL,
-                  NULL_POS);  // the pos will decrease going down in the trie
-  hicnFib->root->left = hicnFib->root;
-  hicnFib->root->right = hicnFib->root;
-
+  hicnFib->forwarder = forwarder;
+  hicnFib->root = NULL;
   hicnFib->size = 0;
 
   return hicnFib;
@@ -80,9 +75,12 @@ void _destroyNode(FibNode *n) {
   n = NULL;
 }
 
-void _destroyFib(FIB *fib) {
-  // to be done
-  return;
+void _destroyFib(FibNode *n) {
+  if(n != NULL){
+    _destroyFib(n->right);
+    _destroyFib(n->left);
+    _destroyNode(n);
+  }
 }
 
 void fib_Destroy(FIB **fibPtr) {
@@ -90,8 +88,8 @@ void fib_Destroy(FIB **fibPtr) {
   parcAssertNotNull(*fibPtr, "Parameter must dereference to non-null pointer");
 
   FIB *fib = *fibPtr;
+  _destroyFib(fib->root);
 
-  _destroyFib(fib);
   parcMemory_Deallocate((void **)&fib);
   *fibPtr = NULL;
 }
@@ -100,239 +98,319 @@ void fib_Add(FIB *fib, FibEntry *entry) {
   parcAssertNotNull(fib, "Parameter must be non-null");
   parcAssertNotNull(entry, "Parameter must be non-null");
 
-  NameBitvector *name = name_GetContentName(fibEntry_GetPrefix(entry));
+  NameBitvector *new_prefix = name_GetContentName(fibEntry_GetPrefix(entry));
+  uint32_t new_prefix_len = nameBitvector_GetLength(new_prefix);
+  FibNode * curr =  fib->root;
+  FibNode * last =  NULL;
 
-  //if the name len is 0, we add this entry on the root
-  if(nameBitvector_GetLength(name) == 0){
-    fib->size++;
-    fib->root->entry = entry;
-    return;
-  }
+  NameBitvector *curr_name;
+  uint32_t curr_prefix_len;
+  uint32_t match_len;
 
-  // search the name
-  FibNode *prev = fib->root;
-  FibNode *curr;
+  while(curr != NULL){
+    curr_name = name_GetContentName(fibEntry_GetPrefix(curr->entry));
 
-  if (nameBitvector_testBit(name, MSB_POS)) {
-    curr = fib->root->right;
-  } else {
-    curr = fib->root->left;
-  }
+    match_len =  nameBitvector_lpm(new_prefix, curr_name);
+    curr_prefix_len = nameBitvector_GetLength(curr_name);
 
-  while (prev->pos > curr->pos) {
-    prev = curr;
-    if (nameBitvector_testBit(name, curr->pos)) {
+    if(curr_prefix_len != match_len || //the new entry does not match the curr
+        curr_prefix_len >= new_prefix_len) //in this case we cannot procede anymore
+          break;
+
+    last = curr;
+    bool bit;
+    int res = nameBitvector_testBit(new_prefix, curr_prefix_len, &bit);
+    parcAssertFalse(res < 0, "error testing name bit (fib_add)");
+    if(bit)
       curr = curr->right;
-    } else {
+    else
       curr = curr->left;
-    }
   }
 
-  if (curr->entry != NULL && curr->pos != NULL_POS &&
-      nameBitvector_Equals(
-          name, name_GetContentName(fibEntry_GetPrefix(curr->entry)))) {
-    // there is already an entry with this name
-    // do nothing. Before call ADD we should check
-    // if the node exists, and, in that case update it
+  //this is the root (empty trie) or an empty child
+  if(curr == NULL){
+    FibNode * new_node = _createNode(NULL, NULL, entry, true);
+    if(last == NULL){
+      fib->root =  new_node;
+    }else{
+      uint32_t last_prefix_len = nameBitvector_GetLength(
+                      name_GetContentName(fibEntry_GetPrefix(last->entry)));
+      bool bit;
+      int res = nameBitvector_testBit(new_prefix, last_prefix_len, &bit);
+      parcAssertFalse(res < 0, "error testing name bit (fib_add)");
+      if(bit)
+        last->right = new_node;
+      else
+        last->left = new_node;
+    }
+    fib->size++;
     return;
   }
 
-  // if the name is not in the FIB search for the first different bit between
-  // the new name to add and the node found in the trie
-  uint8_t pos = MSB_POS;
-  if (curr->entry != NULL && curr->pos != NULL_POS){
-    pos = nameBitvector_firstDiff(
-        name, name_GetContentName(fibEntry_GetPrefix(curr->entry)));
+  //curr is not null
+
+  //the node already exist
+  //if is not in use we turn it on and we set the rigth fib entry
+  if(curr_prefix_len == match_len && new_prefix_len == match_len){
+    if(!curr->is_used){
+      curr->is_used = true;
+      curr->entry = entry;
+      fib->size++;
+      return;
+    }else{
+      //this case should never happen beacuse of the way we add
+      //entries in the fib
+      const NumberSet * next_hops = fibEntry_GetNexthops(entry);
+      unsigned size = (unsigned)fibEntry_NexthopCount(entry);
+      for(unsigned i = 0; i < size; i++)
+        fibEntry_AddNexthop(curr->entry,numberSet_GetItem(next_hops, i));
+    }
   }
 
-  // reset pointer and search the insertion point
-  prev = fib->root;
-  if (nameBitvector_testBit(name, MSB_POS))
-    curr = fib->root->right;
-  else
-    curr = fib->root->left;
-
-  while (prev->pos > curr->pos && curr->pos > pos) {
-    prev = curr;
-    if (nameBitvector_testBit(name, curr->pos)) {
-      curr = curr->right;
-    } else {
-      curr = curr->left;
+  //key is prefix of the curr node (so new_prefix_len < curr_prefix_len)
+  if(new_prefix_len == match_len){
+    FibNode * new_node = _createNode(NULL, NULL, entry, true);
+    if(last == NULL){
+      fib->root = new_node;
+    }else{
+      uint32_t last_prefix_len = nameBitvector_GetLength(
+                      name_GetContentName(fibEntry_GetPrefix(last->entry)));
+
+      bool bit;
+      int res = nameBitvector_testBit(new_prefix, last_prefix_len, &bit);
+      parcAssertFalse(res < 0, "error testing name bit (fib_add)");
+      if(bit)
+        last->right =  new_node;
+      else
+        last->left = new_node;
     }
+    bool bit;
+    int res = nameBitvector_testBit(curr_name, match_len, &bit);
+    parcAssertFalse(res < 0, "error testing name bit (fib_add)");
+    if(bit)
+      new_node->right = curr;
+    else
+      new_node->left = curr;
+    fib->size++;
+    return;
   }
 
-  // insert the node
-  fib->size++;
-  FibNode *n = _createNode(NULL, NULL, entry, pos);
-
-  if (nameBitvector_testBit(name, pos)) {
-    n->left = curr;
-    n->right = n;
-  } else {
-    n->left = n;
-    n->right = curr;
+  //in the last case we need to add an inner node
+  Name * inner_prefix = name_Copy(fibEntry_GetPrefix(entry));
+  nameBitvector_clear(name_GetContentName(inner_prefix), match_len);
+  name_setLen(inner_prefix,  match_len);
+
+  FibEntry * inner_entry = fibEntry_Create(inner_prefix, SET_STRATEGY_LOADBALANCER,
+            fib->forwarder);
+
+  FibNode * inner_node = _createNode(NULL, NULL, inner_entry, false);
+  FibNode * new_node = _createNode(NULL, NULL, entry, true);
+
+  if(last == NULL){
+    //we need to place the inner_node at the root
+    fib->root = inner_node;
+  }else{
+    uint32_t last_prefix_len = nameBitvector_GetLength(
+                      name_GetContentName(fibEntry_GetPrefix(last->entry)));
+    bool bit;
+    int res = nameBitvector_testBit(name_GetContentName(inner_prefix),
+                                                last_prefix_len, &bit);
+    parcAssertFalse(res < 0, "error testing name bit (fib_add)");
+    if(bit)
+      last->right =  inner_node;
+    else
+      last->left = inner_node;
   }
 
-  uint8_t new_pos = prev->pos;
-  if (new_pos == NULL_POS) new_pos = MSB_POS;
+  bool bit;
+  int res = nameBitvector_testBit(new_prefix, match_len, &bit);
+  parcAssertFalse(res < 0, "error testing name bit (fib_add)");
 
-  if (nameBitvector_testBit(name, new_pos)) {
-    prev->right = n;
-  } else {
-    prev->left = n;
+  if(bit){
+    inner_node -> left = curr;
+    inner_node ->right = new_node;
+  }else{
+    inner_node -> left = new_node;
+    inner_node ->right = curr;
   }
+  fib->size ++;
 }
 
 FibEntry *fib_Contains(const FIB *fib, const Name *prefix) {
   parcAssertNotNull(fib, "Parameter must be non-null");
   parcAssertNotNull(prefix, "Parameter must be non-null");
 
-  NameBitvector *name = name_GetContentName(prefix);
+  NameBitvector *key_name = name_GetContentName(prefix);
+  uint32_t key_prefix_len = nameBitvector_GetLength(key_name);
 
-  //if prefix len is 0 it must be stored in the root.
-  //if the root entry is null we need to create it, otherwise
-  //we just need to add an other nexthop
-  if(nameBitvector_GetLength(name) == 0){
-    return fib->root->entry;
-  }
+  FibNode * curr = fib->root;
 
-  // this is the same as the first part of the add function
-  // we cannnot call this function inside the add because
-  // we need the pointer prev and curr for the insertion
+  while(curr != NULL){
+    NameBitvector *curr_name =
+          name_GetContentName(fibEntry_GetPrefix(curr->entry));
+    uint32_t match_len = nameBitvector_lpm(key_name, curr_name);
+    uint32_t curr_prefix_len = nameBitvector_GetLength(curr_name);
 
-  FibNode *prev = fib->root;
-  FibNode *curr;
+    if(match_len < curr_prefix_len){
+      //the current node does not match completelly the key, so
+      //the key is not in the trie
+      //this implies curr_prefix_len > key_prefix_len
+      return NULL;
+    }
 
-  if (nameBitvector_testBit(name, MSB_POS))
-    curr = fib->root->right;
-  else
-    curr = fib->root->left;
+    if(curr_prefix_len == key_prefix_len){ //== match_len
+        //this is an exact match
+        if(curr->is_used){
+          //we found the key
+          return curr->entry;
+        }else{
+          //the key does not exists
+          return NULL;
+        }
+    }
 
-  while (prev->pos > curr->pos) {
-    prev = curr;
+    bool bit;
+    int res = nameBitvector_testBit(key_name, curr_prefix_len, &bit);
+    parcAssertFalse(res < 0, "error testing name bit (fib_contains)");
 
-    if (nameBitvector_testBit(name, curr->pos)) {
+    if(bit)
       curr = curr->right;
-    } else {
+    else
       curr = curr->left;
-    }
   }
 
-  if (curr->entry != NULL && curr->pos != NULL_POS &&
-      nameBitvector_Equals(
-          name, name_GetContentName(fibEntry_GetPrefix(curr->entry)))) {
-    return curr->entry;
-  } else {
-    return NULL;
-  }
+  return NULL;
 }
 
-void _removeNode(FIB *fib, const Name *prefix) {
+void _removeNode(FIB *fib, const Name *prefix){
   parcAssertNotNull(fib, "Parameter must be non-null");
   parcAssertNotNull(prefix, "Parameter must be non-null");
 
-  FibNode *grand = NULL;  // grandparent
-  FibNode *prev =
-      fib->root;  // parent: it will points to curr of the next hop in the trie
-  FibNode *curr;  // current node: the node to remove
+  NameBitvector *key_name = name_GetContentName(prefix);
+  uint32_t key_prefix_len = nameBitvector_GetLength(key_name);
 
-  NameBitvector *name = name_GetContentName(prefix);
+  FibNode * curr = fib->root;
+  FibNode * parent = NULL;
+  FibNode * grandpa = NULL;
 
-  if (nameBitvector_testBit(name, MSB_POS)) {
-    curr = fib->root->right;
-  } else {
-    curr = fib->root->left;
-  }
+  uint32_t match_len;
+  uint32_t curr_prefix_len;
+  while(curr != NULL){
+    NameBitvector *curr_name =
+          name_GetContentName(fibEntry_GetPrefix(curr->entry));
+    match_len = nameBitvector_lpm(key_name, curr_name);
+    curr_prefix_len = nameBitvector_GetLength(curr_name);
+
+    if(match_len < curr_prefix_len ||
+        curr_prefix_len == key_prefix_len){
+      break;
+    }
 
-  // in the first loop we always search the node to remove
-  while (prev->pos > curr->pos) {
-    grand = prev;
-    prev = curr;
+    grandpa = parent;
+    parent = curr;
 
-    if (nameBitvector_testBit(name, curr->pos)) {
+    bool bit;
+    int res = nameBitvector_testBit(key_name, curr_prefix_len, &bit);
+    parcAssertFalse(res < 0, "error testing name bit (_removeNode)");
+
+    if(bit)
       curr = curr->right;
-    } else {
+    else
       curr = curr->left;
-    }
   }
 
-  if (!nameBitvector_Equals(
-          name, name_GetContentName(fibEntry_GetPrefix(curr->entry)))) {
-    // the node does not exists
+  if(curr == NULL ||
+     !curr->is_used ||
+     (curr_prefix_len != key_prefix_len)){
+     //the node does not exists
     return;
   }
 
-  // search for the real parent of curr (*tmpPrev)
-  // prev points to curr or next node in the trie
-  // this is because of the loopback links
-
-  FibNode *tmpPrev = fib->root;
-  FibNode *tmpCurr;
-
-  if (nameBitvector_testBit(name, MSB_POS)) {
-    tmpCurr = fib->root->right;
-  } else {
-    tmpCurr = fib->root->left;
-  }
-
-  // here we compare pointer so we are sure to stop at the right potion
-  while (tmpCurr != curr) {
-    tmpPrev = tmpCurr;
-
-    if (nameBitvector_testBit(name, tmpCurr->pos)) {
-      tmpCurr = tmpCurr->right;
-    } else {
-      tmpCurr = tmpCurr->left;
-    }
+  //curr has 2 children, leave it there and mark it as inner
+  if(curr->right != NULL && curr->left != NULL){
+    curr->is_used = false;
+    fib->size--;
+    return;
   }
 
-  // now curr is the node to remove and tmpPrev is the real parent of curr
-
-  if (curr == prev) {
-    // this is the case where curr is a leaf node
-    FibNode *next;  // child of curr (the loopback)
-
-    if (nameBitvector_testBit(name, curr->pos)) {
-      next = curr->left;
-    } else {
-      next = curr->right;
+  //curr has no children
+  if(curr->right == NULL && curr->left == NULL){
+    if (parent == NULL){
+      //curr is the root and is the only node in the fib
+      fib->root = NULL;
+      fib->size--;
+      _destroyNode(curr);
+      return;
     }
-
-    if (nameBitvector_testBit(name, tmpPrev->pos)) {
-      tmpPrev->right = next;
-    } else {
-      tmpPrev->left = next;
+    if(grandpa == NULL){
+      //parent is the root
+      if(fib->root->left == curr)
+        fib->root->left = NULL;
+      else
+        fib->root->right = NULL;
+      fib->size--;
+      _destroyNode(curr);
+      return;
     }
+    if(!parent->is_used){
+      //parent is an inner node
+      //remove curr and inner_node (parent), connect the other child
+      //of the parent to the grandpa
+      FibNode * tmp;
+      if(parent->right == curr)
+        tmp = parent->left;
+      else
+        tmp = parent->right;
+
+      if(grandpa->right == parent)
+        grandpa->right = tmp;
+      else
+        grandpa->left = tmp;
 
-  } else {
-    // curr is an internal node
-    FibNode *next;  // child of prev (loopback)
-
-    if (nameBitvector_testBit(name, prev->pos)) {
-      next = prev->left;
-    } else {
-      next = prev->right;
+      fib->size--;
+      _destroyNode(curr);
+      _destroyNode(parent);
+      return;
     }
+    //parent is node not an inner_node
+    //just remove curr the node
+    if(parent->right == curr)
+      parent->right = NULL;
+    else
+       parent->left = NULL;
+    fib->size--;
+    _destroyNode(curr);
+    return;
+  }
 
-    if (nameBitvector_testBit(name, grand->pos)) {
-      grand->right = next;
-    } else {
-      grand->left = next;
+  //curr has one child
+  if(curr->right != NULL || curr->left != NULL){
+    if(parent == NULL){
+      //curr is the root
+      if(fib->root->right != NULL)
+        fib->root = fib->root->right;
+      else
+        fib->root = fib->root->left;
+      fib->size--;
+      _destroyNode(curr);
+      return;
     }
+    //attach the child of curr to parent
+    FibNode * tmp;
+    if(curr->right != NULL)
+      tmp = curr->right;
+    else
+      tmp = curr->left;
 
-    if (nameBitvector_testBit(name, tmpPrev->pos)) {
-      tmpPrev->right = prev;
-    } else {
-      tmpPrev->left = prev;
-    }
+    if(parent->right == curr)
+      parent->right = tmp;
+    else
+      parent->left = tmp;
 
-    prev->left = curr->left;
-    prev->right = curr->right;
-    prev->pos = curr->pos;
+    fib->size--;
+    _destroyNode(curr);
+    return;
   }
-
-  fib->size--;
-  _destroyNode(curr);
 }
 
 void fib_Remove(FIB *fib, const Name *name, unsigned connId) {
@@ -346,60 +424,34 @@ void fib_Remove(FIB *fib, const Name *name, unsigned connId) {
   }
 
   fibEntry_RemoveNexthopByConnectionId(entry, connId);
-  if (fibEntry_NexthopCount(entry) == 0) {
-    //if the len is 0, just release the fibEntry on the root node
-    if(nameBitvector_GetLength(
-              name_GetContentName(fibEntry_GetPrefix(entry))) == 0){
-      parcAssertTrue(entry == fib->root->entry,
-          "prefix len == 0, entry is not in the FIB root");
-      fib->size--;
-      fibEntry_Release(&entry);
-      fib->root->entry = NULL;
-    } else {
-      _removeNode(fib, name);
-    }
-  }
+  if (fibEntry_NexthopCount(entry) == 0)
+    _removeNode(fib, name);
+
 }
 
-void _removeConnectionId(FibNode *n, unsigned pos, unsigned connectionId,
+void _removeConnectionId(FibNode *n, unsigned connectionId,
                          FibEntryList *list) {
-  if (n->pos < pos) {
-    fibEntry_RemoveNexthopByConnectionId(n->entry, connectionId);
-    if (fibEntry_NexthopCount(n->entry) == 0) {
-      fibEntryList_Append(list, n->entry);
+  if(n != NULL){
+    if(n->is_used){
+      fibEntry_RemoveNexthopByConnectionId(n->entry, connectionId);
+      if (fibEntry_NexthopCount(n->entry) == 0) {
+        fibEntryList_Append(list, n->entry);
+      }
     }
-    _removeConnectionId(n->left, n->pos, connectionId, list);
-    _removeConnectionId(n->right, n->pos, connectionId, list);
+    _removeConnectionId(n->right, connectionId, list);
+    _removeConnectionId(n->left, connectionId, list);
   }
 }
 
 void fib_RemoveConnectionId(FIB *fib, unsigned connectionId) {
   parcAssertNotNull(fib, "Parameter must be non-null");
 
-  // 0 - remove the connection id from the root
-  // 1 - we vist the tree to remove the connection id
-  // 2 - during the visit we collect the fib entry with 0 nexthop
-  // 3 - after the visit we remove this entries
-
-  if(fib->root->entry){
-    fibEntry_RemoveNexthopByConnectionId(fib->root->entry, connectionId);
-    if(fibEntry_NexthopCount(fib->root->entry) == 0){
-      fib->size--;
-      fibEntry_Release(&fib->root->entry);
-      fib->root->entry = NULL;
-    }
-  }
-
-  FibEntryList *list = fibEntryList_Create();
-
-  _removeConnectionId(fib->root->left, fib->root->pos, connectionId, list);
-  _removeConnectionId(fib->root->right, fib->root->pos, connectionId, list);
+   FibEntryList *list = fibEntryList_Create();
+   _removeConnectionId(fib->root, connectionId, list);
 
   for (int i = 0; i < fibEntryList_Length(list); i++) {
     _removeNode(fib, fibEntry_GetPrefix(fibEntryList_Get(list, i)));
   }
-
-  fibEntryList_Destroy(&list);
 }
 
 size_t fib_Length(const FIB *fib) {
@@ -407,143 +459,82 @@ size_t fib_Length(const FIB *fib) {
   return fib->size;
 }
 
-FibEntry *fib_Match(const FIB *fib, const Message *interestMessage) {
+FibEntry *fib_MatchMessage(const FIB *fib, const Message *interestMessage) {
   parcAssertNotNull(fib, "Parameter must be non-null");
   parcAssertNotNull(interestMessage, "Parameter must be non-null");
+  return fib_MatchBitvector(fib, name_GetContentName(
+                  message_GetName(interestMessage)));
+}
 
-  NameBitvector *name = name_GetContentName(message_GetName(interestMessage));
-
-  FibNode *prev = fib->root;
-  FibNode *curr;
-
-  FibNode *match = NULL;
-  unsigned len = 0;
-
-  if (nameBitvector_testBit(name, MSB_POS))
-    curr = fib->root->right;
-  else
-    curr = fib->root->left;
-
-  while (prev->pos > curr->pos) {
-    prev = curr;
-
-    if (curr->entry != NULL && curr->pos != NULL_POS) {
-      if (nameBitvector_StartsWith(
-              name, name_GetContentName(fibEntry_GetPrefix(curr->entry))) &&
-          nameBitvector_GetLength(
-              name_GetContentName(fibEntry_GetPrefix(curr->entry))) > len) {
-        match = curr;
-        len = nameBitvector_GetLength(
-            name_GetContentName(fibEntry_GetPrefix(curr->entry)));
-      }
-    }
-
-    if (nameBitvector_testBit(name, curr->pos))
-      curr = curr->right;
-    else
-      curr = curr->left;
-  }
-
-  if (curr->entry != NULL && curr->pos != NULL_POS) {
-    if (nameBitvector_StartsWith(
-            name, name_GetContentName(fibEntry_GetPrefix(curr->entry))) &&
-        nameBitvector_GetLength(
-            name_GetContentName(fibEntry_GetPrefix(curr->entry))) > len) {
-      match = curr;
-      len = nameBitvector_GetLength(
-          name_GetContentName(fibEntry_GetPrefix(curr->entry)));
-    }
-  }
-
-  if (match != NULL && match->entry != NULL) {
-    return match->entry;
-  } else {
-    //if there is a  default route, return it.
-    //the dafualt route is in the route
-    return fib->root->entry;
-  }
+FibEntry *fib_MatchName(const FIB *fib, const Name *name) {
+  parcAssertNotNull(fib, "Parameter must be non-null");
+  parcAssertNotNull(name, "Parameter must be non-null");
+  return fib_MatchBitvector(fib, name_GetContentName(name));
 }
 
-#ifdef WITH_MAPME
 
-FibEntry *fib_LPM(const FIB *fib, const Name * prefix) {
+FibEntry *fib_MatchBitvector(const FIB *fib, const NameBitvector *name){
   parcAssertNotNull(fib, "Parameter must be non-null");
-  parcAssertNotNull(prefix, "Parameter must be non-null");
+  parcAssertNotNull(name, "Parameter must be non-null");
 
-  NameBitvector *name = name_GetContentName(prefix);
+  uint32_t key_prefix_len = nameBitvector_GetLength(name);
 
-  FibNode *prev = fib->root;
-  FibNode *curr;
+  FibNode * curr = fib->root;
+  FibNode * candidate = NULL;
 
-  FibNode *match = NULL;
-  unsigned len = 0;
+  while(curr != NULL){
+    NameBitvector *curr_name =
+          name_GetContentName(fibEntry_GetPrefix(curr->entry));
+    uint32_t match_len = nameBitvector_lpm(name, curr_name);
+    uint32_t curr_prefix_len = nameBitvector_GetLength(curr_name);
 
-  if (nameBitvector_testBit(name, MSB_POS))
-    curr = fib->root->right;
-  else
-    curr = fib->root->left;
+    if(match_len < curr_prefix_len){
+      //the current node does not match completelly the key, so
+      //return the parent of this node (saved in candidate)
+      break;
+    }
 
-  while (prev->pos > curr->pos) {
-    prev = curr;
+    if(curr->is_used)
+      candidate = curr;
 
-    if (curr->entry != NULL && curr->pos != NULL_POS) {
-      if (nameBitvector_StartsWith(
-              name, name_GetContentName(fibEntry_GetPrefix(curr->entry))) &&
-          nameBitvector_GetLength(
-              name_GetContentName(fibEntry_GetPrefix(curr->entry))) > len) {
-        match = curr;
-        len = nameBitvector_GetLength(
-            name_GetContentName(fibEntry_GetPrefix(curr->entry)));
-      }
+    //if we are here match_len == curr_prefix_len (can't be larger)
+    //so this node is actually a good candidate for a match
+    if(curr_prefix_len == key_prefix_len){
+      //this an exact match, do not continue
+      break;
     }
 
-    if (nameBitvector_testBit(name, curr->pos))
+    bool bit;
+    int res = nameBitvector_testBit(name, curr_prefix_len, &bit);
+    parcAssertFalse(res < 0, "error testing name bit (fib_MatchBitvector)");
+
+    if(bit)
       curr = curr->right;
     else
       curr = curr->left;
   }
 
-  if (curr->entry != NULL && curr->pos != NULL_POS) {
-    if (nameBitvector_StartsWith(
-            name, name_GetContentName(fibEntry_GetPrefix(curr->entry))) &&
-        nameBitvector_GetLength(
-            name_GetContentName(fibEntry_GetPrefix(curr->entry))) > len) {
-      match = curr;
-      len = nameBitvector_GetLength(
-          name_GetContentName(fibEntry_GetPrefix(curr->entry)));
-    }
+  if(candidate != NULL){
+    return candidate->entry;
   }
 
-  if (match != NULL && match->entry != NULL) {
-    return match->entry;
-  } else {
-    //if there is a  default route, return it.
-    //the dafualt route is in the route
-    return fib->root->entry;
-  }
+  return NULL;
 }
 
-#endif /* WITH_MAPME */
-
-void _collectFibEntries(FibNode *n, int pos, FibEntryList *list) {
-  if (n->pos < (unsigned)pos) {
-    fibEntryList_Append(list, n->entry);
-    _collectFibEntries(n->left, n->pos, list);
-    _collectFibEntries(n->right, n->pos, list);
+void _collectFibEntries(FibNode *n, FibEntryList *list){
+  if(n != NULL){
+    if(n->is_used)
+      fibEntryList_Append(list, n->entry);
+    _collectFibEntries(n->right, list);
+    _collectFibEntries(n->left, list);
   }
 }
 
 FibEntryList *fib_GetEntries(const FIB *fib) {
   parcAssertNotNull(fib, "Parameter must be non-null");
-
   FibEntryList *list = fibEntryList_Create();
 
-  if(fib->root->entry){
-    fibEntryList_Append(list, fib->root->entry);
-  }
-
-  _collectFibEntries(fib->root->left, fib->root->pos, list);
-  _collectFibEntries(fib->root->right, fib->root->pos, list);
+  _collectFibEntries(fib->root, list);
 
   return list;
 }
diff --git a/hicn-light/src/hicn/processor/fib.h b/hicn-light/src/hicn/processor/fib.h
index 8c03537fe..7507bb85c 100644
--- a/hicn-light/src/hicn/processor/fib.h
+++ b/hicn-light/src/hicn/processor/fib.h
@@ -35,11 +35,9 @@ void fib_Remove(FIB *fib, const Name *prefix, unsigned connId);
 
 void fib_RemoveConnectionId(FIB *fib, unsigned connectionId);
 
-FibEntry *fib_Match(const FIB *fib, const Message *interestMessage);
-
-#ifdef WITH_MAPME
-FibEntry *fib_LPM(const FIB *fib, const Name * name);
-#endif /* WITH_MAPME */
+FibEntry *fib_MatchMessage(const FIB *fib, const Message *interestMessage);
+FibEntry *fib_MatchName(const FIB *fib, const Name *name);
+FibEntry *fib_MatchBitvector(const FIB *fib, const NameBitvector *name);
 
 size_t fib_Length(const FIB *fib);
 
diff --git a/hicn-light/src/hicn/processor/messageProcessor.c b/hicn-light/src/hicn/processor/messageProcessor.c
index 7b43543a3..456618269 100644
--- a/hicn-light/src/hicn/processor/messageProcessor.c
+++ b/hicn-light/src/hicn/processor/messageProcessor.c
@@ -576,7 +576,7 @@ static bool messageProcessor_ForwardViaFib(MessageProcessor *processor,
 static bool messageProcessor_ForwardViaFib(MessageProcessor *processor,
                                            Message *interestMessage) {
 #endif /* WITH_POLICY */
-  FibEntry *fibEntry = fib_Match(processor->fib, interestMessage);
+  FibEntry *fibEntry = fib_MatchMessage(processor->fib, interestMessage);
   if (fibEntry == NULL) {
     return false;
   }