[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):

 Now, we have N assigned addresses S_0 through S_(N-1), and N+1 (possibly
 empty) intervals I_0 through I_N, with I_i = {x in Z | S_(i-1) <= x <
 S_i}, mutatis mutandis for I_0 and I_N - that is, implicitly S_(-1) = 0
 and S_N = max_addr.  The problem is then to determine which of the
 intervals I_i that S_x falls in, and the offset within that interval
 corresponding to the chosen address.

 The offset is easy enough: let C_j be the count of unassigned addresses in
 I_j (that is, C_j = S_j - 1 - S_(j-1), mutatis mutandis for C_0 and C_N),
 and then the offset of S_x in I_i is just x adjusted by the C_j of all
 preceding intervals:

 S_x = S_(i-1) + (x - sum(C_j for 0 <= j < i))

 By assumption that S_x falls in I_i, we must have 0 <= (x - sum(C_j for 0
 <= j < i)) < S_i - S_(i-1).  If we picked too large a value of i this will
 be negative and for too small a value it will be past S_i - S_(i-1).
 Thus, if nothing else, we could learn i efficiently by binary search given
 an efficient way of computing sum(C_j for 0 <= j < i).  Fortunately, this
 is easy: keep the assigned addresses in a balanced tree (we need a data
 structure of some sort to test for assignedness anyway), and in addition
 to the assigned address S_i used as the sort key at each node, keep the
 count of assigned nodes in the subtree below that node (which will be easy
 to update on tree rotations when rebalancing).  Then, the number of
 assigned addresses <= S_i is just 1 + count(left subtree at S_i) and so
 the number of unassigned addresses <= S_i (that is, sum(C_j for 0 <= j <
 i)) is just S_i - (1 + count(left subtree at S_i)).

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