diff options
author | 2020-04-22 10:02:31 -0400 | |
---|---|---|
committer | 2020-04-22 19:58:20 +0000 | |
commit | 053d0935244843199c433e92df666b4f79007727 (patch) | |
tree | 82fa449bd70f36a6d5ac75abcb3b89d8685bc868 /src/vppinfra/fheap.h | |
parent | f932f97d7d8e55ab62aba0f18d59a9622c21efd8 (diff) |
vppinfra: move unused code to extras/deprecated/vppinfra
Type: improvement
Signed-off-by: Dave Barach <dave@barachs.net>
Change-Id: Id28299a188feefa1899d835fd499f018af95d81b
Diffstat (limited to 'src/vppinfra/fheap.h')
-rw-r--r-- | src/vppinfra/fheap.h | 140 |
1 files changed, 0 insertions, 140 deletions
diff --git a/src/vppinfra/fheap.h b/src/vppinfra/fheap.h deleted file mode 100644 index 1dbd52bad76..00000000000 --- a/src/vppinfra/fheap.h +++ /dev/null @@ -1,140 +0,0 @@ -/* - * Copyright (c) 2015 Cisco and/or its affiliates. - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at: - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -#ifndef included_clib_fheap_h -#define included_clib_fheap_h - -/* Fibonacci Heaps Fredman, M. L.; Tarjan (1987). - "Fibonacci heaps and their uses in improved network optimization algorithms" */ - -#include <vppinfra/vec.h> - -typedef struct -{ - /* Node index of parent. */ - u32 parent; - - /* Node index of first child. */ - u32 first_child; - - /* Next and previous nodes in doubly linked list of siblings. */ - u32 next_sibling, prev_sibling; - - /* Key (distance) for this node. Parent always has key - <= than keys of children. */ - u32 key; - - /* Number of children (as opposed to descendents). */ - u32 rank; - - u32 is_marked; - - /* Set to one when node is inserted; zero when deleted. */ - u32 is_valid; -} fheap_node_t; - -#define foreach_fheap_node_sibling(f,ni,first_ni,body) \ -do { \ - u32 __fheap_foreach_first_ni = (first_ni); \ - u32 __fheap_foreach_ni = __fheap_foreach_first_ni; \ - u32 __fheap_foreach_next_ni; \ - fheap_node_t * __fheap_foreach_n; \ - if (__fheap_foreach_ni != ~0) \ - while (1) \ - { \ - __fheap_foreach_n = fheap_get_node ((f), __fheap_foreach_ni); \ - __fheap_foreach_next_ni = __fheap_foreach_n -> next_sibling; \ - (ni) = __fheap_foreach_ni; \ - \ - body; \ - \ - /* End of circular list? */ \ - if (__fheap_foreach_next_ni == __fheap_foreach_first_ni) \ - break; \ - \ - __fheap_foreach_ni = __fheap_foreach_next_ni; \ - \ - } \ -} while (0) - -typedef struct -{ - u32 min_root; - - /* Vector of nodes. */ - fheap_node_t *nodes; - - u32 *root_list_by_rank; - - u32 enable_validate; - - u32 validate_serial; -} fheap_t; - -/* Initialize empty heap. */ -always_inline void -fheap_init (fheap_t * f, u32 n_nodes) -{ - fheap_node_t *save_nodes = f->nodes; - u32 *save_root_list = f->root_list_by_rank; - - clib_memset (f, 0, sizeof (f[0])); - - f->nodes = save_nodes; - f->root_list_by_rank = save_root_list; - - vec_validate (f->nodes, n_nodes - 1); - vec_reset_length (f->root_list_by_rank); - - f->min_root = ~0; -} - -always_inline void -fheap_free (fheap_t * f) -{ - vec_free (f->nodes); - vec_free (f->root_list_by_rank); -} - -always_inline u32 -fheap_find_min (fheap_t * f) -{ - return f->min_root; -} - -always_inline u32 -fheap_is_empty (fheap_t * f) -{ - return f->min_root == ~0; -} - -/* Add/delete nodes. */ -void fheap_add (fheap_t * f, u32 ni, u32 key); -void fheap_del (fheap_t * f, u32 ni); - -/* Delete and return minimum. */ -u32 fheap_del_min (fheap_t * f, u32 * min_key); - -/* Change key value. */ -void fheap_decrease_key (fheap_t * f, u32 ni, u32 new_key); - -#endif /* included_clib_fheap_h */ - -/* - * fd.io coding-style-patch-verification: ON - * - * Local Variables: - * eval: (c-set-style "gnu") - * End: - */ |