[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):
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
_______________________________________________
tor-bugs mailing list
tor-bugs@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs