[tor-bugs] #7571 [Tor]: Make AutomapHostsOnResolve work with IPv6

[Tor Bug Tracker & Wiki]

#7571: Make AutomapHostsOnResolve work with IPv6
-------------------------+--------------------------------------------------
 Reporter:  nickm        |          Owner:                    
     Type:  enhancement  |         Status:  needs_review      
 Priority:  normal       |      Milestone:  Tor: 0.2.4.x-final
Component:  Tor          |        Version:                    
 Keywords:               |         Parent:                    
   Points:               |   Actualpoints:                    
-------------------------+--------------------------------------------------

Comment(by andrea):

 This could be done by binary search in O(log(N)) queries on the tree of
 cost O(log(N)), for a total time complexity of O(log^2(N)), but we can
 just as easily walk down the tree evaluating x - sum(C_j for 0 <= j < i)
 and comparing to 0 and S_i - S_(i-1) as long as we can get S_(i-1) in
 constant time (that is, each node must have a prev pointer as well as
 left/right subtrees), use that to decide whether to pick this interval or
 move to the left or right subtree, and thus determine the correct I_i in
 O(log(N)).

-- 
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/7571#comment:6>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online