"file." %
(peer_count, k, happy, k))
# Otherwise, if there is an x-happy subset of peers where
- # x >= needed_shares, but x < servers_of_happiness, then
+ # x >= needed_shares, but x < servers_of_happiness, then
# we use this message.
else:
msg = ("shares could be placed on only %d server(s) "
ret.setdefault(peerid, set()).add(shareid)
return ret
-def merge_peers(servermap, used_peers=None):
+def merge_servers(servermap, upload_trackers=None):
"""
- I accept a dict of shareid -> set(peerid) mappings, and optionally a
- set of PeerTrackers. If no set of PeerTrackers is provided, I return
+ I accept a dict of shareid -> set(serverid) mappings, and optionally a
+ set of ServerTrackers. If no set of ServerTrackers is provided, I return
my first argument unmodified. Otherwise, I update a copy of my first
- argument to include the shareid -> peerid mappings implied in the
- set of PeerTrackers, returning the resulting dict.
+ argument to include the shareid -> serverid mappings implied in the
+ set of ServerTrackers, returning the resulting dict.
"""
# Since we mutate servermap, and are called outside of a
# context where it is okay to do that, make a copy of servermap and
# work with it.
servermap = deepcopy(servermap)
- if not used_peers:
+ if not upload_trackers:
return servermap
assert(isinstance(servermap, dict))
- assert(isinstance(used_peers, set))
+ assert(isinstance(upload_trackers, set))
- for peer in used_peers:
- for shnum in peer.buckets:
- servermap.setdefault(shnum, set()).add(peer.peerid)
+ for tracker in upload_trackers:
+ for shnum in tracker.buckets:
+ servermap.setdefault(shnum, set()).add(tracker.get_serverid())
return servermap
def servers_of_happiness(sharemap):
sharemap = shares_by_server(sharemap)
graph = flow_network_for(sharemap)
# This is an implementation of the Ford-Fulkerson method for finding
- # a maximum flow in a flow network applied to a bipartite graph.
- # Specifically, it is the Edmonds-Karp algorithm, since it uses a
+ # a maximum flow in a flow network applied to a bipartite graph.
+ # Specifically, it is the Edmonds-Karp algorithm, since it uses a
# BFS to find the shortest augmenting path at each iteration, if one
- # exists.
- #
- # The implementation here is an adapation of an algorithm described in
- # "Introduction to Algorithms", Cormen et al, 2nd ed., pp 658-662.
+ # exists.
+ #
+ # The implementation here is an adapation of an algorithm described in
+ # "Introduction to Algorithms", Cormen et al, 2nd ed., pp 658-662.
dim = len(graph)
flow_function = [[0 for sh in xrange(dim)] for s in xrange(dim)]
residual_graph, residual_function = residual_network(graph, flow_function)
# is the amount of unused capacity on that edge. Taking the
# minimum of a list of those values for each edge in the
# augmenting path gives us our delta.
- delta = min(map(lambda (u, v): residual_function[u][v], path))
+ delta = min(map(lambda (u, v), rf=residual_function: rf[u][v],
+ path))
for (u, v) in path:
flow_function[u][v] += delta
flow_function[v][u] -= delta
num_servers = len(sharemap)
graph = [] # index -> [index], an adjacency list
# Add an entry at the top (index 0) that has an edge to every server
- # in sharemap
+ # in sharemap
graph.append(sharemap.keys())
# For each server, add an entry that has an edge to every share that it
# contains (or will contain).
for v in graph[i]:
if f[i][v] == 1:
# We add an edge (v, i) with cf[v,i] = 1. This means
- # that we can remove 1 unit of flow from the edge (i, v)
+ # that we can remove 1 unit of flow from the edge (i, v)
new_graph[v].append(i)
cf[v][i] = 1
cf[i][v] = -1
projects / tahoe-lafs / tahoe-lafs.git / blobdiff