³ò ô=£Cc @sÞddklZddkTddkTddkZddkZddklZl Z l Z l Z l Z ddk lZdd d„ƒYZddd „ƒYZddkZd eifd „ƒYZed joeiƒndS(iÿÿÿÿ(tbttime(t*N(tKt HASH_LENGTHtNULL_IDt MAX_FAILUREStMIN_PING_INTERVAL(tNodetKTablecBszeZdZd„Zd„Zd„Zed„Zd„Zd„Z de d„Z d „Z d „Z d „Zd „ZRS( s>local routing table for a kademlia like distributed hash tablecCs6||_tgddtƒg|_|i|ƒdS(Nll(tnodetKBucketRtbucketst insertNode(tselfR ((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyt__init__s cCst|i|ƒS(s,the index of the bucket that should hold int(t bisect_leftR (R tnum((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyt_bucketIndexForIntscCs|i|i|ƒS(N(R R(R R((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyt bucketForInt sc Cs2t|tƒoti|ƒ}nQt|tƒo |i}n4t|tƒpt|tƒo |}n td‚g}|i |ƒ}y|i |i |ƒ}Wnt j on X|gS||i |i }|p3g}|D]}|ip ||qåqå~}nt|ƒtjo÷|d} |d} xàt|ƒtjoÈ| djp| t|i ƒjo¥| djo||i | i }n| t|i ƒjo||i | i }n| d} | d} |p3g} |D]}|ip | |qæqæ~ }q7q7Wn|i|d„ƒ|t S(sN return K nodes in our own local table closest to the ID. s*findNodes requires an int, string, or NodeiicSst||iA||iAƒS((tcmpR(tatbR((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pytOs(t isinstancetstrthashtintifyRRtinttlongt TypeErrorRR tgetNodeWithIntt ValueErrortltinvalidtlenRtsort( R tidR!RtnodestiR t_[1]Rtmintmaxt_[2]((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyt findNodes#s@    3  6   <cCs°|i|id}tg|i||iƒ}|ii|ii|iƒd|ƒ|i||_xC|iD]7}|i|ijo|i|ƒ|i |ƒqqqqWdS(Nii( R)R(R R tinserttindexR Rt removeNodetaddNode(R RtdiffRtanode((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyt _splitBucketRs&  cCsš|i|iƒ}|i|i|ƒo|i|i|ƒn|o/|i|i|ƒo|i|i|ƒn |o|i|i|ƒndS(stthis is used by clients to replace a node returned by insertNode after it fails to respond to a Pong messageN(RRR thasNodeR.tseenNodeR/(R tstaletnewR&((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pytreplaceStaleNode]sicCsZ|itjp|i|iijodSn|o|iƒn|i|iƒ}|i|i|ƒo§|i|ii |iƒ}|i|i|}|o$|i |_ |i|i |ƒnE|i djo4|i |i jo!|i|ijo|iƒndSn|i|iƒp|i|i|ƒdSntƒ}d„}g} |i|iiƒD]} | io | | qpqp~ } t| ƒoÄ| o¼| i|ƒxJ| oB|i|i| dƒ o&|i|i| di=| d} q¹W| o4| di djo | ditjo | dSqe| o|i| d|ƒdSqeng} |i|iD]%} || i tjo | | qzqz~ }t|ƒo!| o|i|ƒ|dSn|i|i|ijo|i|ijnpdSnt|iƒtjo dGHdSn|i|i|ƒ|i||ƒS(sF this insert the node, returning None if successful, returns the oldest node in the bucket if it's full the caller responsible for pinging the returned node and calling replaceStaleNode if it is found to be stale!! contacted means that yes, we contacted THEM and we know the node is reachable NicSs:|i|ijodSn|i|ijodSndS(Niiÿÿÿÿi(tlastSeen(RR((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pytlsŒs is Hash Table is FULL! Increase K!(R$RR tupdateLastSeenRRR R3R R-tageR4R8tportthostt bucketFullR/ttimeR!tvaluesR"R#tfailsRR7RR(R)RR2R (R R t contactedtnocheckR&tittxnodettR9R'txR!R*tnR5((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyR ksT& 6  ? #/  C  5cCsky|i|ƒd}Wntj o dSn8X|i}|iƒ|i|iƒ}|i|ƒ|SdS(sfcall this any time you get a message from a node it will update it in the table if it's there iN(R+t IndexErrortNoneR8R:RRR4(R R$RHttstamptbucket((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyt justSeenNode³s    cCs2t|_|i|iƒ|_|ii|ƒdS(sR forget about node n - use when you know that node is invalid N(tTrueR!RRRLtinvalidateNode(R RH((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyROÁs cCs_y|i|iƒd}Wntj o dSn)X|iƒtijo|i|ƒndS(sN call this when a node fails to respond to a message, to invalidate that node iN(R+RRIRJt msgFailedtconstRRO(R R RH((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyt nodeFailedÉs  cCsddt|iƒdS(s7 estimated number of connectable nodes in global table iii(R"R (R ((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pytnumPeersÓs(t__name__t __module__t__doc__RRRRNR+R2R7tFalseR RMRORRRS(((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyRs    / H   R cBs°eZdZd„Zd„Zd„Zd„Zd„Zd„Zd „Z d „Z d „Z d „Z d „Z d„Zd„Zd„Zd„Zd„Zd„Zd„ZRS(R(R)t lastAccessedcCs=||_h|_h|_||_||_tƒ|_dS(N(R R-R!R(R)R?RX(R tcontentsR(R)((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyRÙs      cCstƒ|_dS(N(R?RX(R ((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyttoucháscCs:|i|ijodSn|i|ijodSndS(Niiÿÿÿÿi(R8(R RR((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pytlacmpäs cCs|ii|iƒdS(N(R R#R[(R ((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyR#ëscCs1y|i|}Wntj o t‚nX|S(N(R-tKeyErrorR(R RR ((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyRîs  cCsjt|iƒtjodSn|ii|iƒodSn|ii|ƒ||i|i<|iƒdS(N(R"R RR-thas_keyRtappendRZ(R R ((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyR/õscCsx|ii|iƒpt‚|i|ii|iƒ=|i|i=y|i|i=Wntj onX|iƒdS(N(R-R]RtAssertionErrorR R!R\RZ(R R ((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyR.þs cCs||i|iscCs dt|iƒ|i|ifS(Ns(R"R R(R)(R ((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyt__repr__scCs*t|tƒo |i}n|i|jS(N(RRRR)(R R((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyt__lt__!s cCs*t|tƒo |i}n|i|jS(N(RRRR((R R((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyt__le__$s cCs*t|tƒo |i}n|i|jS(N(RRRR((R R((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyt__gt__'s cCs*t|tƒo |i}n|i|jS(N(RRRR)(R R((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyt__ge__*s cCs:t|tƒo |i}n|i|jo |i|jS(N(RRRR(R)(R R((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyt__eq__-s cCs:t|tƒo |i}n|i|jp |i|jS(N(RRRR(R)(R R((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyt__ne__0s (sminsmaxs lastAccessed(RTRUt __slots__RRZR[R#RR/R.ROR4R3R>R`RaRbRcRdReRf(((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyR ×s&              t TestKTablecBs,eZd„Zd„Zd„Zd„ZRS(cCs7tƒitiƒddƒ|_t|iƒ|_dS(Nt localhostiÒ(RtinitRtnewIDRRRF(R ((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pytsetUp9s!cCstƒitiƒddƒ|_|ii|iƒ|it|ii di ƒdƒ|i|ii di d|iƒdS(NRiiÓii( RRjRRkRRFR t assertEqualR"R R (R ((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyt testAddNode=s!#cCsD|iƒ|ii|iƒ|it|iidiƒdƒdS(Ni(RnRFRORRmR"R R (R ((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyt testRemoveCs cCs¼|iƒxuttidƒD]`}|ii|iƒ|it|ii di ƒdƒ|i|ii di d|iƒqW|ii|iƒ|it|ii di ƒdƒdS(Nii( RntrangeRQRRFRRRRmR"R R (R R&((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyttestFailHs #((RTRURlRnRoRq(((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pyRh8s   t__main__(((tBitTorrent.platformRR?tbisectttypestkhashRRQRRRRRR RRR tunittesttTestCaseRhRTtmain(((sT/afs/sipb.mit.edu/project/outland/src/BitTorrent/BitTorrent-4.2.2/khashmir/ktable.pys s    (Ã_