naive implementation of set difference

[dtaht]

This is the core of the xroute import problem. It's also similar to the resend problem. In both cases,
we could use a way better structure to deal with it, and probably the same kind. rb_tree?
I think avl would be better.

https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Set_operations_and_bulk_operations

https://github.com/dtaht/rabeld/blob/master/xroute.c#L355

[dtaht]

kernel rbtree is "augmented". Looks useful. It's GPL.

[dtaht]

this where resend goes nuts > 5k routes and desperately needs to not be a singly linked list. 36 byte compare too....

https://github.com/dtaht/babeld/blob/master/resend.c#L67

and the whole congestion control #11 and other issues #26 #20 with doing too much busty work would be better handled with a timer wheel.

[dtaht]

https://lkml.org/lkml/2005/10/19/46 was good

[dtaht]

I was not particularly happy with the overhead of an rbtree in these cases. So, reaching
back into prehistory, I went looking at various tries.

"Hardware/Software IP Lookups with Incremental Updates" was good reading:

http://cseweb.ucsd.edu/~varghese/PAPERS/ccr2004.pdf

with some example code here: https://github.com/xnhp0320/prefix_lookup_mc

[dtaht]

The uthash version seems performant.