diff options
| author | Renato Westphal <renato@opensourcerouting.org> | 2016-12-04 00:14:44 +0100 |
|---|---|---|
| committer | Renato Westphal <renato@opensourcerouting.org> | 2017-01-04 01:07:13 +0100 |
| commit | d3e1887ad6b5ae2199710b3278c277838e6ef913 (patch) | |
| tree | 36470ff324cefc0af07208863ec81f5e805f48c6 /ldpd/lde.h | |
| parent | build/ldpd: auto-generate ldp_vty_cmds.c from ldp_vty.xml (diff) | |
| download | frr-d3e1887ad6b5ae2199710b3278c277838e6ef913.tar.xz frr-d3e1887ad6b5ae2199710b3278c277838e6ef913.zip | |
ldpd: use red-black trees to store 'lde_map' elements
Using red-black trees instead of linked lists brings the following
benefits:
1 - Elements are naturally ordered (no need to reorder anything before
outputting data to the user);
2 - Faster lookups/deletes: O(log n) time complexity against O(n).
The insert operation with red-black trees is more expensive though,
but that's not a big issue since lookups are much more frequent.
Signed-off-by: Renato Westphal <renato@opensourcerouting.org>
Diffstat (limited to 'ldpd/lde.h')
| -rw-r--r-- | ldpd/lde.h | 9 |
1 files changed, 6 insertions, 3 deletions
diff --git a/ldpd/lde.h b/ldpd/lde.h index 5f5d37def..fe90b2c85 100644 --- a/ldpd/lde.h +++ b/ldpd/lde.h @@ -62,10 +62,13 @@ struct lde_req { /* mapping entries */ struct lde_map { struct fec fec; - LIST_ENTRY(lde_map) entry; + struct lde_map_head *head; /* fec_node's upstream/downstream */ + RB_ENTRY(lde_map) entry; struct lde_nbr *nexthop; struct map map; }; +RB_HEAD(lde_map_head, lde_map); +RB_PROTOTYPE(lde_map_head, lde_map, entry, lde_map_cmp); /* withdraw entries */ struct lde_wdraw { @@ -112,8 +115,8 @@ struct fec_node { struct fec fec; LIST_HEAD(, fec_nh) nexthops; /* fib nexthops */ - LIST_HEAD(, lde_map) downstream; /* recv mappings */ - LIST_HEAD(, lde_map) upstream; /* sent mappings */ + struct lde_map_head downstream; /* recv mappings */ + struct lde_map_head upstream; /* sent mappings */ uint32_t local_label; void *data; /* fec specific data */ |