<div dir="auto"><div>Yes, this on my to-do list.<br><div class="gmail_extra"><br><div class="gmail_quote">On Nov 1, 2017 4:02 PM, "Donald Sharp" <<a href="mailto:sharpd@cumulusnetworks.com">sharpd@cumulusnetworks.com</a>> wrote:<br type="attribution"><blockquote class="quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Jay -<br>
<br>
Conversion of lists over for well used data structures would be<br>
greatly appreciated and in general is on the list of things that need<br>
to be done..  I do know the bgp peers have both a list and a hash( for<br>
o(1) lookup) that was put in about 1.5 years ago and showed some great<br>
improvements in scaling because of not having to traverse a list for<br>
peer lookup.<br>
<font color="#888888"><br>
donald<br>
</font><div class="elided-text"><br>
On Wed, Nov 1, 2017 at 1:28 PM, Jay Chen <<a href="mailto:jchen1@paloaltonetworks.com">jchen1@paloaltonetworks.com</a>> wrote:<br>
> Donald,<br>
><br>
> Cool, indeed it is using an rb already. I was looking at BGP that uses a lot of list for group, peer etc. My code is indeed old too. I am going to update it and try the newest one.<br>
><br>
> Thanks,<br>
> Jay<br>
><br>
> On 11/1/17, 10:04 AM, "Donald Sharp" <<a href="mailto:sharpd@cumulusnetworks.com">sharpd@cumulusnetworks.com</a>> wrote:<br>
><br>
>     Jay -<br>
><br>
>     What version of the code are you looking at?  VRF's use RB trees:<br>
><br>
>     static __inline int vrf_id_compare(const struct vrf *, const struct vrf *);<br>
>     static __inline int vrf_name_compare(const struct vrf *, const struct vrf *);<br>
><br>
>     RB_GENERATE(vrf_id_head, vrf, id_entry, vrf_id_compare);<br>
>     RB_GENERATE(vrf_name_head, vrf, name_entry, vrf_name_compare);<br>
><br>
>     struct vrf_id_head vrfs_by_id = RB_INITIALIZER(&vrfs_by_id);<br>
>     struct vrf_name_head vrfs_by_name = RB_INITIALIZER(&vrfs_by_name);<br>
><br>
>     So do interfaces now as well:<br>
><br>
>     static int if_cmp_func(const struct interface *, const struct interface *);<br>
>     static int if_cmp_index_func(const struct interface *ifp1,<br>
>                                  const struct interface *ifp2);<br>
>     RB_GENERATE(if_name_head, interface, name_entry, if_cmp_func);<br>
>     RB_GENERATE(if_index_head, interface, index_entry, if_cmp_index_func);<br>
><br>
>     We've been trying to intelligently move code over and may have missed<br>
>     something.<br>
><br>
>     donald<br>
><br>
>     On Wed, Nov 1, 2017 at 1:00 PM, Jay Chen <<a href="mailto:jchen1@paloaltonetworks.com">jchen1@paloaltonetworks.com</a>> wrote:<br>
>     > Hi Donald,<br>
>     ><br>
>     > Great, thank you for the clarification.<br>
>     > I noticed that FRR using linked list in both BGP, and OSPF where a red black tree may be better in turn of Big-O. Two questions below:<br>
>     ><br>
>     > A. Is it worth to implement a redblack tree?<br>
>     > B. Any effort is already in progress in implementing an embedded redblack tree and use it in some key places?<br>
>     ><br>
>     > If the answer to A is yes, B is no. I can volunteer to implement a light weight redblack tree (embedded usage), and patch it (I have done a couple of time for another two router companies). I just thought it might be better than search a long linked list.<br>
>     ><br>
>     > Thanks,<br>
>     > Jay<br>
>     ><br>
>     ><br>
>     ><br>
>     > On 11/1/17, 6:15 AM, "Donald Sharp" <<a href="mailto:sharpd@cumulusnetworks.com">sharpd@cumulusnetworks.com</a>> wrote:<br>
>     ><br>
>     >     Jay -<br>
>     ><br>
>     >     There is no hard limit.  Having said that I am not aware of serious<br>
>     >     testing beyond like 64 vrf's.  But that is allot of vrf's to have to<br>
>     >     maintain at one time..<br>
>     ><br>
>     >     donald<br>
>     ><br>
>     >     On Tue, Oct 31, 2017 at 10:39 PM, Jay Chen <<a href="mailto:jchen1@paloaltonetworks.com">jchen1@paloaltonetworks.com</a>> wrote:<br>
>     >     > Is there a limit that the # of vrf can support for a single switch or router<br>
>     >     > by using FRR?<br>
>     >     ><br>
>     >     ><br>
>     >     ><br>
>     >     > Thanks,<br>
>     >     ><br>
>     >     > Jay<br>
>     >     ><br>
>     >     ><br>
>     >     ><br>
>     >     ><br>
>     >     > ______________________________<wbr>_________________<br>
>     >     > dev mailing list<br>
>     >     > <a href="mailto:dev@lists.frrouting.org">dev@lists.frrouting.org</a><br>
>     >     > <a href="https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.frrouting.org_listinfo_dev&d=DwIBaQ&c=V9IgWpI5PvzTw83UyHGVSoW3Uc1MFWe5J8PTfkrzVSo&r=yetdj-aXQpuqTCJGs-93hOpK3740MIRXowfUNLByeos&m=39gFpBpfaetXLzjjR76DUE8_Ju4vRUt7sYRtCAk5gY8&s=1AXFF8MKa7HBFGMglzbyhXAP3TjDeWh9w9xcNn4puxQ&e=" rel="noreferrer" target="_blank">https://urldefense.proofpoint.<wbr>com/v2/url?u=https-3A__lists.<wbr>frrouting.org_listinfo_dev&d=<wbr>DwIBaQ&c=<wbr>V9IgWpI5PvzTw83UyHGVSoW3Uc1MFW<wbr>e5J8PTfkrzVSo&r=yetdj-<wbr>aXQpuqTCJGs-<wbr>93hOpK3740MIRXowfUNLByeos&m=<wbr>39gFpBpfaetXLzjjR76DUE8_<wbr>Ju4vRUt7sYRtCAk5gY8&s=<wbr>1AXFF8MKa7HBFGMglzbyhXAP3TjDeW<wbr>h9w9xcNn4puxQ&e=</a><br>
>     >     ><br>
>     ><br>
>     ><br>
><br>
><br>
<br>
______________________________<wbr>_________________<br>
dev mailing list<br>
<a href="mailto:dev@lists.frrouting.org">dev@lists.frrouting.org</a><br>
<a href="https://lists.frrouting.org/listinfo/dev" rel="noreferrer" target="_blank">https://lists.frrouting.org/<wbr>listinfo/dev</a><br>
</div></blockquote></div><br></div></div></div>