[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Re: [tor-bugs] #7571 [Tor]: Make AutomapHostsOnResolve work with IPv6
#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
_______________________________________________
tor-bugs mailing list
tor-bugs@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs