From 15ad172a847fa667c57a4594ef4158405db9a984 Mon Sep 17 00:00:00 2001 From: Angelo Mantellini Date: Tue, 31 Mar 2020 17:50:43 +0200 Subject: [HICN-554] hicn-light refactoring MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Change-Id: I36f2d393741d4502ce14d3791158e43e3e9cd4cf Signed-off-by: Jordan Augé --- hicn-light/src/hicn/processor/fib.c | 548 ------------------------------------ 1 file changed, 548 deletions(-) delete mode 100644 hicn-light/src/hicn/processor/fib.c (limited to 'hicn-light/src/hicn/processor/fib.c') diff --git a/hicn-light/src/hicn/processor/fib.c b/hicn-light/src/hicn/processor/fib.c deleted file mode 100644 index 8822134fe..000000000 --- a/hicn-light/src/hicn/processor/fib.c +++ /dev/null @@ -1,548 +0,0 @@ -/* - * 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. - */ - -#include -#include - -#include -#include - -#include -#include - -#include - -struct node; -typedef struct node FibNode; - -struct node { - FibNode *left; - FibNode *right; - FibEntry *entry; - bool is_used; -}; - -struct fib { - Forwarder *forwarder; - FibNode *root; - unsigned size; -}; - -// ===================================================== -// Public API - -FibNode *_createNode(FibNode *left, FibNode *right, FibEntry *entry, - bool is_used) { - FibNode *n = parcMemory_AllocateAndClear(sizeof(FibNode)); - parcAssertNotNull(n, "parcMemory_AllocateAndClear(%zu) returned NULL", - sizeof(FibNode)); - - n->left = left; - n->right = right; - n->entry = entry; - n->is_used = is_used; - - return n; -} - -FIB *fib_Create(Forwarder *forwarder) { - FIB *hicnFib = parcMemory_AllocateAndClear(sizeof(FIB)); - parcAssertNotNull(hicnFib, "parcMemory_AllocateAndClear(%zu) returned NULL", - sizeof(FIB)); - - hicnFib->forwarder = forwarder; - hicnFib->root = NULL; - hicnFib->size = 0; - - return hicnFib; -} - -void _destroyNode(FibNode *n) { - fibEntry_Release(&n->entry); - parcMemory_Deallocate((void **)&n); - n = NULL; -} - -void _destroyFib(FibNode *n) { - if(n != NULL){ - _destroyFib(n->right); - _destroyFib(n->left); - _destroyNode(n); - } -} - -void fib_Destroy(FIB **fibPtr) { - parcAssertNotNull(fibPtr, "Parameter must be non-null double pointer"); - parcAssertNotNull(*fibPtr, "Parameter must dereference to non-null pointer"); - - FIB *fib = *fibPtr; - _destroyFib(fib->root); - - parcMemory_Deallocate((void **)&fib); - *fibPtr = NULL; -} - -void fib_Add(FIB *fib, FibEntry *entry) { - parcAssertNotNull(fib, "Parameter must be non-null"); - parcAssertNotNull(entry, "Parameter must be non-null"); - - NameBitvector *new_prefix = name_GetContentName(fibEntry_GetPrefix(entry)); - uint32_t new_prefix_len = nameBitvector_GetLength(new_prefix); - FibNode * curr = fib->root; - FibNode * last = NULL; - - NameBitvector *curr_name; - uint32_t curr_prefix_len; - uint32_t match_len; - - while(curr != NULL){ - curr_name = name_GetContentName(fibEntry_GetPrefix(curr->entry)); - - match_len = nameBitvector_lpm(new_prefix, curr_name); - curr_prefix_len = nameBitvector_GetLength(curr_name); - - 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 - curr = curr->left; - } - - //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; - } - - //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)); - } - } - - //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; - } - - //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); - - //this is an inner node, we don't want an acctive strategy - //like low_latency that sends probes in this node - 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; - } - - bool bit; - int res = nameBitvector_testBit(new_prefix, match_len, &bit); - parcAssertFalse(res < 0, "error testing name bit (fib_add)"); - - 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 *key_name = name_GetContentName(prefix); - uint32_t key_prefix_len = nameBitvector_GetLength(key_name); - - FibNode * curr = fib->root; - - 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); - - 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(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; - } - } - - bool bit; - int res = nameBitvector_testBit(key_name, curr_prefix_len, &bit); - parcAssertFalse(res < 0, "error testing name bit (fib_contains)"); - - if(bit) - curr = curr->right; - else - curr = curr->left; - } - - return NULL; -} - -void _removeNode(FIB *fib, const Name *prefix){ - parcAssertNotNull(fib, "Parameter must be non-null"); - parcAssertNotNull(prefix, "Parameter must be non-null"); - - NameBitvector *key_name = name_GetContentName(prefix); - uint32_t key_prefix_len = nameBitvector_GetLength(key_name); - - FibNode * curr = fib->root; - FibNode * parent = NULL; - FibNode * grandpa = NULL; - - 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; - } - - grandpa = parent; - parent = curr; - - 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 - curr = curr->left; - } - - if(curr == NULL || - !curr->is_used || - (curr_prefix_len != key_prefix_len)){ - //the node does not exists - return; - } - - //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; - } - - //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(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; - - 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; - } - - //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(parent->right == curr) - parent->right = tmp; - else - parent->left = tmp; - - fib->size--; - _destroyNode(curr); - return; - } -} - -void fib_Remove(FIB *fib, const Name *name, unsigned connId) { - parcAssertNotNull(fib, "Parameter must be non-null"); - parcAssertNotNull(name, "Parameter must be non-null"); - - FibEntry *entry = fib_Contains(fib, name); - - if (entry == NULL) { - return; - } - - fibEntry_RemoveNexthopByConnectionId(entry, connId); -#ifndef WITH_MAPME - if (fibEntry_NexthopCount(entry) == 0) - _removeNode(fib, name); -#endif /* WITH_MAPME */ - -} - -void _removeConnectionId(FibNode *n, unsigned connectionId, - FibEntryList *list) { - if(n != NULL){ - if(n->is_used){ - fibEntry_RemoveNexthopByConnectionId(n->entry, connectionId); -#ifndef WITH_MAPME - if (fibEntry_NexthopCount(n->entry) == 0) { - fibEntryList_Append(list, n->entry); - } -#endif /* WITH_MAPME */ - } - _removeConnectionId(n->right, connectionId, list); - _removeConnectionId(n->left, connectionId, list); - } -} - -void fib_RemoveConnectionId(FIB *fib, unsigned connectionId) { - parcAssertNotNull(fib, "Parameter must be non-null"); - - 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) { - parcAssertNotNull(fib, "Parameter must be non-null"); - return fib->size; -} - -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))); -} - -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)); -} - - -FibEntry *fib_MatchBitvector(const FIB *fib, const NameBitvector *name){ - parcAssertNotNull(fib, "Parameter must be non-null"); - parcAssertNotNull(name, "Parameter must be non-null"); - - uint32_t key_prefix_len = nameBitvector_GetLength(name); - - FibNode * curr = fib->root; - FibNode * candidate = NULL; - - 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(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; - } - - if(curr->is_used) - candidate = curr; - - //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; - } - - 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(candidate != NULL){ - return candidate->entry; - } - - return NULL; -} - -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(); - - _collectFibEntries(fib->root, list); - - return list; -} -- cgit 1.2.3-korg