Hex Artifact Content
Not logged in

Artifact 655a10483cee34e70ecc925f0e083b40197e6bd9:


0000: 2f 2a 0a 20 2a 20 43 6f 70 79 72 69 67 68 74 20  /*. * Copyright 
0010: 28 63 29 20 32 30 30 33 2d 32 30 30 35 20 4a 69  (c) 2003-2005 Ji
0020: 6e 79 61 6e 67 20 4c 69 0a 20 2a 20 20 20 20 20  nyang Li. *     
0030: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 4d                 M
0040: 61 73 73 61 63 68 75 73 65 74 74 73 20 49 6e 73  assachusetts Ins
0050: 74 69 74 75 74 65 20 6f 66 20 54 65 63 68 6e 6f  titute of Techno
0060: 6c 6f 67 79 0a 20 2a 20 0a 20 2a 20 50 65 72 6d  logy. * . * Perm
0070: 69 73 73 69 6f 6e 20 69 73 20 68 65 72 65 62 79  ission is hereby
0080: 20 67 72 61 6e 74 65 64 2c 20 66 72 65 65 20 6f   granted, free o
0090: 66 20 63 68 61 72 67 65 2c 20 74 6f 20 61 6e 79  f charge, to any
00a0: 20 70 65 72 73 6f 6e 20 6f 62 74 61 69 6e 69 6e   person obtainin
00b0: 67 0a 20 2a 20 61 20 63 6f 70 79 20 6f 66 20 74  g. * a copy of t
00c0: 68 69 73 20 73 6f 66 74 77 61 72 65 20 61 6e 64  his software and
00d0: 20 61 73 73 6f 63 69 61 74 65 64 20 64 6f 63 75   associated docu
00e0: 6d 65 6e 74 61 74 69 6f 6e 20 66 69 6c 65 73 20  mentation files 
00f0: 28 74 68 65 0a 20 2a 20 22 53 6f 66 74 77 61 72  (the. * "Softwar
0100: 65 22 29 2c 20 74 6f 20 64 65 61 6c 20 69 6e 20  e"), to deal in 
0110: 74 68 65 20 53 6f 66 74 77 61 72 65 20 77 69 74  the Software wit
0120: 68 6f 75 74 20 72 65 73 74 72 69 63 74 69 6f 6e  hout restriction
0130: 2c 20 69 6e 63 6c 75 64 69 6e 67 0a 20 2a 20 77  , including. * w
0140: 69 74 68 6f 75 74 20 6c 69 6d 69 74 61 74 69 6f  ithout limitatio
0150: 6e 20 74 68 65 20 72 69 67 68 74 73 20 74 6f 20  n the rights to 
0160: 75 73 65 2c 20 63 6f 70 79 2c 20 6d 6f 64 69 66  use, copy, modif
0170: 79 2c 20 6d 65 72 67 65 2c 20 70 75 62 6c 69 73  y, merge, publis
0180: 68 2c 0a 20 2a 20 64 69 73 74 72 69 62 75 74 65  h,. * distribute
0190: 2c 20 73 75 62 6c 69 63 65 6e 73 65 2c 20 61 6e  , sublicense, an
01a0: 64 2f 6f 72 20 73 65 6c 6c 20 63 6f 70 69 65 73  d/or sell copies
01b0: 20 6f 66 20 74 68 65 20 53 6f 66 74 77 61 72 65   of the Software
01c0: 2c 20 61 6e 64 20 74 6f 0a 20 2a 20 70 65 72 6d  , and to. * perm
01d0: 69 74 20 70 65 72 73 6f 6e 73 20 74 6f 20 77 68  it persons to wh
01e0: 6f 6d 20 74 68 65 20 53 6f 66 74 77 61 72 65 20  om the Software 
01f0: 69 73 20 66 75 72 6e 69 73 68 65 64 20 74 6f 20  is furnished to 
0200: 64 6f 20 73 6f 2c 20 73 75 62 6a 65 63 74 20 74  do so, subject t
0210: 6f 0a 20 2a 20 74 68 65 20 66 6f 6c 6c 6f 77 69  o. * the followi
0220: 6e 67 20 63 6f 6e 64 69 74 69 6f 6e 73 3a 0a 20  ng conditions:. 
0230: 2a 20 0a 20 2a 20 54 68 65 20 61 62 6f 76 65 20  * . * The above 
0240: 63 6f 70 79 72 69 67 68 74 20 6e 6f 74 69 63 65  copyright notice
0250: 20 61 6e 64 20 74 68 69 73 20 70 65 72 6d 69 73   and this permis
0260: 73 69 6f 6e 20 6e 6f 74 69 63 65 20 73 68 61 6c  sion notice shal
0270: 6c 20 62 65 0a 20 2a 20 69 6e 63 6c 75 64 65 64  l be. * included
0280: 20 69 6e 20 61 6c 6c 20 63 6f 70 69 65 73 20 6f   in all copies o
0290: 72 20 73 75 62 73 74 61 6e 74 69 61 6c 20 70 6f  r substantial po
02a0: 72 74 69 6f 6e 73 20 6f 66 20 74 68 65 20 53 6f  rtions of the So
02b0: 66 74 77 61 72 65 2e 0a 20 2a 20 0a 20 2a 20 54  ftware.. * . * T
02c0: 48 45 20 53 4f 46 54 57 41 52 45 20 49 53 20 50  HE SOFTWARE IS P
02d0: 52 4f 56 49 44 45 44 20 22 41 53 20 49 53 22 2c  ROVIDED "AS IS",
02e0: 20 57 49 54 48 4f 55 54 20 57 41 52 52 41 4e 54   WITHOUT WARRANT
02f0: 59 20 4f 46 20 41 4e 59 20 4b 49 4e 44 2c 0a 20  Y OF ANY KIND,. 
0300: 2a 20 45 58 50 52 45 53 53 20 4f 52 20 49 4d 50  * EXPRESS OR IMP
0310: 4c 49 45 44 2c 20 49 4e 43 4c 55 44 49 4e 47 20  LIED, INCLUDING 
0320: 42 55 54 20 4e 4f 54 20 4c 49 4d 49 54 45 44 20  BUT NOT LIMITED 
0330: 54 4f 20 54 48 45 20 57 41 52 52 41 4e 54 49 45  TO THE WARRANTIE
0340: 53 20 4f 46 0a 20 2a 20 4d 45 52 43 48 41 4e 54  S OF. * MERCHANT
0350: 41 42 49 4c 49 54 59 2c 20 46 49 54 4e 45 53 53  ABILITY, FITNESS
0360: 20 46 4f 52 20 41 20 50 41 52 54 49 43 55 4c 41   FOR A PARTICULA
0370: 52 20 50 55 52 50 4f 53 45 20 41 4e 44 0a 20 2a  R PURPOSE AND. *
0380: 20 4e 4f 4e 49 4e 46 52 49 4e 47 45 4d 45 4e 54   NONINFRINGEMENT
0390: 2e 20 49 4e 20 4e 4f 20 45 56 45 4e 54 20 53 48  . IN NO EVENT SH
03a0: 41 4c 4c 20 54 48 45 20 41 55 54 48 4f 52 53 20  ALL THE AUTHORS 
03b0: 4f 52 20 43 4f 50 59 52 49 47 48 54 20 48 4f 4c  OR COPYRIGHT HOL
03c0: 44 45 52 53 20 42 45 0a 20 2a 20 4c 49 41 42 4c  DERS BE. * LIABL
03d0: 45 20 46 4f 52 20 41 4e 59 20 43 4c 41 49 4d 2c  E FOR ANY CLAIM,
03e0: 20 44 41 4d 41 47 45 53 20 4f 52 20 4f 54 48 45   DAMAGES OR OTHE
03f0: 52 20 4c 49 41 42 49 4c 49 54 59 2c 20 57 48 45  R LIABILITY, WHE
0400: 54 48 45 52 20 49 4e 20 41 4e 20 41 43 54 49 4f  THER IN AN ACTIO
0410: 4e 0a 20 2a 20 4f 46 20 43 4f 4e 54 52 41 43 54  N. * OF CONTRACT
0420: 2c 20 54 4f 52 54 20 4f 52 20 4f 54 48 45 52 57  , TORT OR OTHERW
0430: 49 53 45 2c 20 41 52 49 53 49 4e 47 20 46 52 4f  ISE, ARISING FRO
0440: 4d 2c 20 4f 55 54 20 4f 46 20 4f 52 20 49 4e 20  M, OUT OF OR IN 
0450: 43 4f 4e 4e 45 43 54 49 4f 4e 0a 20 2a 20 57 49  CONNECTION. * WI
0460: 54 48 20 54 48 45 20 53 4f 46 54 57 41 52 45 20  TH THE SOFTWARE 
0470: 4f 52 20 54 48 45 20 55 53 45 20 4f 52 20 4f 54  OR THE USE OR OT
0480: 48 45 52 20 44 45 41 4c 49 4e 47 53 20 49 4e 20  HER DEALINGS IN 
0490: 54 48 45 20 53 4f 46 54 57 41 52 45 2e 0a 20 2a  THE SOFTWARE.. *
04a0: 2f 0a 0a 23 69 6e 63 6c 75 64 65 20 20 22 63 68  /..#include  "ch
04b0: 6f 72 64 6f 6e 65 68 6f 70 2e 68 22 0a 23 69 6e  ordonehop.h".#in
04c0: 63 6c 75 64 65 20 3c 73 74 64 69 6f 2e 68 3e 0a  clude <stdio.h>.
04d0: 23 69 6e 63 6c 75 64 65 20 3c 69 6f 73 74 72 65  #include <iostre
04e0: 61 6d 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 61 6c  am>.#include <al
04f0: 67 6f 72 69 74 68 6d 3e 0a 75 73 69 6e 67 20 6e  gorithm>.using n
0500: 61 6d 65 73 70 61 63 65 20 73 74 64 3b 0a 65 78  amespace std;.ex
0510: 74 65 72 6e 20 62 6f 6f 6c 20 73 74 61 74 69 63  tern bool static
0520: 5f 73 69 6d 3b 0a 0a 43 68 6f 72 64 4f 6e 65 48  _sim;..ChordOneH
0530: 6f 70 3a 3a 43 68 6f 72 64 4f 6e 65 48 6f 70 28  op::ChordOneHop(
0540: 49 50 41 64 64 72 65 73 73 20 69 2c 20 41 72 67  IPAddress i, Arg
0550: 73 20 26 61 29 3a 20 43 68 6f 72 64 28 69 2c 20  s &a): Chord(i, 
0560: 61 29 0a 7b 0a 7d 0a 0a 43 68 6f 72 64 4f 6e 65  a).{.}..ChordOne
0570: 48 6f 70 3a 3a 7e 43 68 6f 72 64 4f 6e 65 48 6f  Hop::~ChordOneHo
0580: 70 28 29 0a 7b 0a 7d 0a 0a 76 6f 69 64 0a 43 68  p().{.}..void.Ch
0590: 6f 72 64 4f 6e 65 48 6f 70 3a 3a 69 6e 69 74 5f  ordOneHop::init_
05a0: 73 74 61 74 65 28 76 65 63 74 6f 72 3c 49 44 4d  state(vector<IDM
05b0: 61 70 3e 20 69 64 73 29 0a 7b 0a 20 20 66 6f 72  ap> ids).{.  for
05c0: 20 28 75 69 6e 74 20 69 20 3d 20 30 3b 20 69 20   (uint i = 0; i 
05d0: 3c 20 69 64 73 2e 73 69 7a 65 28 29 3b 20 69 2b  < ids.size(); i+
05e0: 2b 29 20 7b 0a 20 20 20 20 6c 6f 63 74 61 62 6c  +) {.    loctabl
05f0: 65 2d 3e 61 64 64 5f 6e 6f 64 65 28 69 64 73 5b  e->add_node(ids[
0600: 69 5d 29 3b 0a 20 20 7d 0a 20 20 70 72 69 6e 74  i]);.  }.  print
0610: 66 28 22 25 73 20 69 6e 69 74 5f 73 74 61 74 65  f("%s init_state
0620: 20 25 64 20 65 6e 74 72 69 65 73 5c 6e 22 2c 20   %d entries\n", 
0630: 74 73 28 29 2c 20 6c 6f 63 74 61 62 6c 65 2d 3e  ts(), loctable->
0640: 73 69 7a 65 28 29 29 3b 0a 7d 0a 76 6f 69 64 0a  size());.}.void.
0650: 43 68 6f 72 64 4f 6e 65 48 6f 70 3a 3a 72 65 73  ChordOneHop::res
0660: 63 68 65 64 75 6c 65 5f 62 61 73 69 63 5f 73 74  chedule_basic_st
0670: 61 62 69 6c 69 7a 65 72 28 76 6f 69 64 20 2a 78  abilizer(void *x
0680: 29 0a 7b 0a 20 20 61 73 73 65 72 74 28 21 73 74  ).{.  assert(!st
0690: 61 74 69 63 5f 73 69 6d 29 3b 0a 20 20 70 72 69  atic_sim);.  pri
06a0: 6e 74 66 28 22 25 73 20 73 74 61 72 74 20 73 74  ntf("%s start st
06b0: 61 62 69 6c 69 7a 69 6e 67 5c 6e 22 2c 74 73 28  abilizing\n",ts(
06c0: 29 29 3b 0a 20 20 69 66 20 28 21 61 6c 69 76 65  ));.  if (!alive
06d0: 28 29 29 20 7b 0a 20 20 20 20 5f 73 74 61 62 5f  ()) {.    _stab_
06e0: 62 61 73 69 63 5f 72 75 6e 6e 69 6e 67 20 3d 20  basic_running = 
06f0: 66 61 6c 73 65 3b 0a 20 20 20 20 72 65 74 75 72  false;.    retur
0700: 6e 3b 0a 20 20 7d 0a 0a 20 20 5f 73 74 61 62 5f  n;.  }..  _stab_
0710: 62 61 73 69 63 5f 72 75 6e 6e 69 6e 67 20 3d 20  basic_running = 
0720: 74 72 75 65 3b 0a 20 20 69 66 20 28 5f 73 74 61  true;.  if (_sta
0730: 62 5f 62 61 73 69 63 5f 6f 75 74 73 74 61 6e 64  b_basic_outstand
0740: 69 6e 67 20 3e 20 30 29 20 7b 0a 20 20 7d 65 6c  ing > 0) {.  }el
0750: 73 65 7b 0a 20 20 20 20 5f 73 74 61 62 5f 62 61  se{.    _stab_ba
0760: 73 69 63 5f 6f 75 74 73 74 61 6e 64 69 6e 67 2b  sic_outstanding+
0770: 2b 3b 0a 20 20 20 20 73 74 61 62 69 6c 69 7a 65  +;.    stabilize
0780: 28 29 3b 0a 20 20 20 20 5f 73 74 61 62 5f 62 61  ();.    _stab_ba
0790: 73 69 63 5f 6f 75 74 73 74 61 6e 64 69 6e 67 2d  sic_outstanding-
07a0: 2d 3b 0a 20 20 20 20 61 73 73 65 72 74 28 5f 73  -;.    assert(_s
07b0: 74 61 62 5f 62 61 73 69 63 5f 6f 75 74 73 74 61  tab_basic_outsta
07c0: 6e 64 69 6e 67 20 3d 3d 20 30 29 3b 0a 20 20 7d  nding == 0);.  }
07d0: 0a 20 20 64 65 6c 61 79 63 62 28 5f 73 74 61 62  .  delaycb(_stab
07e0: 5f 62 61 73 69 63 5f 74 69 6d 65 72 2c 20 26 43  _basic_timer, &C
07f0: 68 6f 72 64 4f 6e 65 48 6f 70 3a 3a 72 65 73 63  hordOneHop::resc
0800: 68 65 64 75 6c 65 5f 62 61 73 69 63 5f 73 74 61  hedule_basic_sta
0810: 62 69 6c 69 7a 65 72 2c 20 28 76 6f 69 64 20 2a  bilizer, (void *
0820: 29 20 30 29 3b 0a 7d 0a 0a 76 6f 69 64 0a 43 68  ) 0);.}..void.Ch
0830: 6f 72 64 4f 6e 65 48 6f 70 3a 3a 73 74 61 62 69  ordOneHop::stabi
0840: 6c 69 7a 65 28 29 0a 7b 0a 20 20 2f 2f 63 6f 6d  lize().{.  //com
0850: 70 6c 65 74 65 6c 79 20 64 69 66 66 65 72 65 6e  pletely differen
0860: 74 20 73 74 61 62 69 6c 69 7a 65 72 0a 0a 20 20  t stabilizer..  
0870: 2f 2f 70 69 6e 67 20 73 75 63 63 65 73 73 6f 72  //ping successor
0880: 0a 20 20 49 44 4d 61 70 20 73 75 63 63 20 3d 20  .  IDMap succ = 
0890: 6c 6f 63 74 61 62 6c 65 2d 3e 73 75 63 63 28 6d  loctable->succ(m
08a0: 65 2e 69 64 20 2b 20 31 29 3b 0a 20 20 61 73 73  e.id + 1);.  ass
08b0: 65 72 74 28 73 75 63 63 2e 69 70 29 3b 0a 20 20  ert(succ.ip);.  
08c0: 2f 2f 72 65 63 6f 72 64 5f 73 74 61 74 28 29 3b  //record_stat();
08d0: 20 0a 20 20 62 6f 6f 6c 20 6f 6b 3b 0a 20 20 6f   .  bool ok;.  o
08e0: 6b 20 3d 20 64 6f 52 50 43 28 73 75 63 63 2e 69  k = doRPC(succ.i
08f0: 70 2c 20 26 43 68 6f 72 64 3a 3a 6e 75 6c 6c 5f  p, &Chord::null_
0900: 68 61 6e 64 6c 65 72 2c 20 28 76 6f 69 64 20 2a  handler, (void *
0910: 29 4e 55 4c 4c 2c 20 26 73 75 63 63 29 3b 0a 0a  )NULL, &succ);..
0920: 20 20 69 66 20 28 21 6f 6b 29 20 7b 20 2f 2f 6e    if (!ok) { //n
0930: 6f 74 69 66 79 20 74 68 65 20 77 68 6f 6c 65 20  otify the whole 
0940: 77 6f 72 6c 64 0a 20 20 20 20 6c 6f 63 74 61 62  world.    loctab
0950: 6c 65 2d 3e 64 65 6c 5f 6e 6f 64 65 28 73 75 63  le->del_node(suc
0960: 63 29 3b 0a 20 20 20 20 76 65 63 74 6f 72 3c 43  c);.    vector<C
0970: 68 6f 72 64 3a 3a 49 44 4d 61 70 3e 20 76 20 3d  hord::IDMap> v =
0980: 20 6c 6f 63 74 61 62 6c 65 2d 3e 67 65 74 5f 61   loctable->get_a
0990: 6c 6c 28 29 3b 0a 0a 20 20 20 20 64 65 6c 61 64  ll();..    delad
09a0: 64 5f 61 72 67 73 20 64 61 3b 0a 20 20 20 20 64  d_args da;.    d
09b0: 61 2e 6e 20 3d 20 73 75 63 63 3b 0a 0a 20 20 20  a.n = succ;..   
09c0: 20 75 6e 73 69 67 6e 65 64 20 72 70 63 20 3d 20   unsigned rpc = 
09d0: 30 3b 0a 20 20 20 20 52 50 43 53 65 74 20 72 70  0;.    RPCSet rp
09e0: 63 73 65 74 3b 0a 0a 20 20 20 20 66 6f 72 20 28  cset;..    for (
09f0: 75 69 6e 74 20 69 20 3d 20 30 3b 20 69 20 3c 20  uint i = 0; i < 
0a00: 76 2e 73 69 7a 65 28 29 3b 20 69 2b 2b 29 20 7b  v.size(); i++) {
0a10: 0a 20 20 20 20 20 20 69 66 20 28 76 5b 69 5d 2e  .      if (v[i].
0a20: 69 70 20 3d 3d 20 6d 65 2e 69 70 29 20 63 6f 6e  ip == me.ip) con
0a30: 74 69 6e 75 65 3b 0a 20 20 20 20 20 20 2f 2f 72  tinue;.      //r
0a40: 65 63 6f 72 64 5f 73 74 61 74 28 29 3b 0a 20 20  ecord_stat();.  
0a50: 20 20 20 20 2f 2f 63 61 6e 63 65 6c 52 50 43 28      //cancelRPC(
0a60: 61 73 79 6e 63 52 50 43 28 76 5b 69 5d 2e 69 70  asyncRPC(v[i].ip
0a70: 2c 20 26 43 68 6f 72 64 4f 6e 65 48 6f 70 3a 3a  , &ChordOneHop::
0a80: 64 65 6c 5f 68 61 6e 64 6c 65 72 2c 20 0a 20 20  del_handler, .  
0a90: 20 20 20 20 2f 2f 26 64 61 2c 20 28 76 6f 69 64      //&da, (void
0aa0: 20 2a 29 4e 55 4c 4c 29 29 3b 20 0a 20 20 20 20   *)NULL)); .    
0ab0: 20 20 72 70 63 20 3d 20 61 73 79 6e 63 52 50 43    rpc = asyncRPC
0ac0: 28 76 5b 69 5d 2e 69 70 2c 20 26 43 68 6f 72 64  (v[i].ip, &Chord
0ad0: 4f 6e 65 48 6f 70 3a 3a 64 65 6c 5f 68 61 6e 64  OneHop::del_hand
0ae0: 6c 65 72 2c 20 26 64 61 2c 20 28 76 6f 69 64 20  ler, &da, (void 
0af0: 2a 29 4e 55 4c 4c 29 3b 20 0a 20 20 20 20 20 20  *)NULL); .      
0b00: 61 73 73 65 72 74 28 72 70 63 29 3b 0a 20 20 20  assert(rpc);.   
0b10: 20 20 20 72 70 63 73 65 74 2e 69 6e 73 65 72 74     rpcset.insert
0b20: 28 72 70 63 29 3b 0a 20 20 20 20 20 20 2f 2f 64  (rpc);.      //d
0b30: 6f 52 50 43 28 76 5b 69 5d 2e 69 70 2c 20 26 43  oRPC(v[i].ip, &C
0b40: 68 6f 72 64 4f 6e 65 48 6f 70 3a 3a 64 65 6c 5f  hordOneHop::del_
0b50: 68 61 6e 64 6c 65 72 2c 20 26 64 61 2c 20 28 76  handler, &da, (v
0b60: 6f 69 64 20 2a 29 4e 55 4c 4c 29 3b 20 0a 20 20  oid *)NULL); .  
0b70: 20 20 7d 0a 0a 20 20 20 20 2f 2f 69 20 6d 75 73    }..    //i mus
0b80: 74 20 72 65 63 65 69 76 65 20 74 68 65 73 65 20  t receive these 
0b90: 52 50 43 73 2c 20 6f 74 68 65 72 77 69 73 65 2c  RPCs, otherwise,
0ba0: 20 61 61 20 67 6f 74 20 64 65 61 6c 6c 6f 63 61   aa got dealloca
0bb0: 74 65 64 20 0a 20 20 20 20 2f 2f 61 6e 64 20 72  ted .    //and r
0bc0: 65 63 65 69 76 65 72 73 20 77 69 6c 6c 20 67 65  eceivers will ge
0bd0: 74 20 67 61 72 62 61 67 65 0a 20 20 20 20 75 69  t garbage.    ui
0be0: 6e 74 20 6f 75 74 73 74 61 6e 64 69 6e 67 20 3d  nt outstanding =
0bf0: 20 72 70 63 73 65 74 2e 73 69 7a 65 28 29 3b 0a   rpcset.size();.
0c00: 20 20 20 20 77 68 69 6c 65 20 28 6f 75 74 73 74      while (outst
0c10: 61 6e 64 69 6e 67 20 3e 20 30 29 20 7b 0a 20 20  anding > 0) {.  
0c20: 20 20 20 20 2f 2f 20 75 6e 73 69 67 6e 65 64 20      // unsigned 
0c30: 64 6f 6e 65 72 70 63 20 3d 20 72 63 76 52 50 43  donerpc = rcvRPC
0c40: 28 26 72 70 63 73 65 74 29 3b 0a 20 20 20 20 20  (&rpcset);.     
0c50: 20 6f 75 74 73 74 61 6e 64 69 6e 67 2d 2d 3b 0a   outstanding--;.
0c60: 20 20 20 20 20 20 61 73 73 65 72 74 28 6f 75 74        assert(out
0c70: 73 74 61 6e 64 69 6e 67 20 3d 3d 20 72 70 63 73  standing == rpcs
0c80: 65 74 2e 73 69 7a 65 28 29 29 3b 0a 20 20 20 20  et.size());.    
0c90: 7d 0a 20 20 7d 20 0a 0a 7d 0a 0a 76 6f 69 64 0a  }.  } ..}..void.
0ca0: 43 68 6f 72 64 4f 6e 65 48 6f 70 3a 3a 64 65 6c  ChordOneHop::del
0cb0: 5f 68 61 6e 64 6c 65 72 28 64 65 6c 61 64 64 5f  _handler(deladd_
0cc0: 61 72 67 73 20 2a 61 72 67 73 2c 20 76 6f 69 64  args *args, void
0cd0: 20 2a 72 65 74 29 0a 7b 0a 20 20 6c 6f 63 74 61   *ret).{.  locta
0ce0: 62 6c 65 2d 3e 64 65 6c 5f 6e 6f 64 65 28 61 72  ble->del_node(ar
0cf0: 67 73 2d 3e 6e 29 3b 0a 7d 0a 0a 76 6f 69 64 0a  gs->n);.}..void.
0d00: 43 68 6f 72 64 4f 6e 65 48 6f 70 3a 3a 61 64 64  ChordOneHop::add
0d10: 5f 68 61 6e 64 6c 65 72 28 64 65 6c 61 64 64 5f  _handler(deladd_
0d20: 61 72 67 73 20 2a 61 72 67 73 2c 20 76 6f 69 64  args *args, void
0d30: 20 2a 72 65 74 29 0a 7b 0a 20 20 6c 6f 63 74 61   *ret).{.  locta
0d40: 62 6c 65 2d 3e 61 64 64 5f 6e 6f 64 65 28 61 72  ble->add_node(ar
0d50: 67 73 2d 3e 6e 29 3b 0a 7d 0a 0a 76 6f 69 64 0a  gs->n);.}..void.
0d60: 43 68 6f 72 64 4f 6e 65 48 6f 70 3a 3a 67 65 74  ChordOneHop::get
0d70: 6c 6f 63 74 61 62 6c 65 5f 68 61 6e 64 6c 65 72  loctable_handler
0d80: 28 76 6f 69 64 20 2a 61 72 67 73 2c 20 67 65 74  (void *args, get
0d90: 5f 70 72 65 64 73 75 63 63 5f 72 65 74 20 2a 72  _predsucc_ret *r
0da0: 65 74 29 0a 7b 0a 20 20 72 65 74 2d 3e 76 20 3d  et).{.  ret->v =
0db0: 20 6c 6f 63 74 61 62 6c 65 2d 3e 67 65 74 5f 61   loctable->get_a
0dc0: 6c 6c 28 29 3b 0a 20 20 61 73 73 65 72 74 28 72  ll();.  assert(r
0dd0: 65 74 2d 3e 76 2e 73 69 7a 65 28 29 20 3c 20 32  et->v.size() < 2
0de0: 30 30 30 29 3b 0a 7d 0a 0a 76 6f 69 64 0a 43 68  000);.}..void.Ch
0df0: 6f 72 64 4f 6e 65 48 6f 70 3a 3a 6a 6f 69 6e 28  ordOneHop::join(
0e00: 41 72 67 73 20 2a 61 72 67 73 29 0a 7b 0a 0a 20  Args *args).{.. 
0e10: 20 5f 69 6e 69 74 65 64 20 3d 20 74 72 75 65 3b   _inited = true;
0e20: 0a 20 20 49 44 4d 61 70 20 77 6b 6e 3b 0a 20 20  .  IDMap wkn;.  
0e30: 77 6b 6e 2e 69 70 20 3d 20 61 72 67 73 2d 3e 6e  wkn.ip = args->n
0e40: 67 65 74 3c 49 50 41 64 64 72 65 73 73 3e 28 22  get<IPAddress>("
0e50: 77 65 6c 6c 6b 6e 6f 77 6e 22 29 3b 0a 20 20 61  wellknown");.  a
0e60: 73 73 65 72 74 20 28 77 6b 6e 2e 69 70 29 3b 0a  ssert (wkn.ip);.
0e70: 20 20 77 6b 6e 2e 69 64 20 3d 20 43 6f 6e 73 69    wkn.id = Consi
0e80: 73 74 65 6e 74 48 61 73 68 3a 3a 69 70 32 63 68  stentHash::ip2ch
0e90: 69 64 28 77 6b 6e 2e 69 70 29 3b 0a 20 20 6c 6f  id(wkn.ip);.  lo
0ea0: 63 74 61 62 6c 65 2d 3e 61 64 64 5f 6e 6f 64 65  ctable->add_node
0eb0: 28 77 6b 6e 29 3b 0a 0a 20 20 67 65 74 5f 70 72  (wkn);..  get_pr
0ec0: 65 64 73 75 63 63 5f 72 65 74 20 67 72 3b 0a 20  edsucc_ret gr;. 
0ed0: 20 2f 2f 72 65 63 6f 72 64 5f 73 74 61 74 28 29   //record_stat()
0ee0: 3b 0a 0a 20 20 62 6f 6f 6c 20 6f 6b 20 3d 20 64  ;..  bool ok = d
0ef0: 6f 52 50 43 28 77 6b 6e 2e 69 70 2c 20 26 43 68  oRPC(wkn.ip, &Ch
0f00: 6f 72 64 4f 6e 65 48 6f 70 3a 3a 67 65 74 6c 6f  ordOneHop::getlo
0f10: 63 74 61 62 6c 65 5f 68 61 6e 64 6c 65 72 2c 20  ctable_handler, 
0f20: 28 76 6f 69 64 20 2a 29 4e 55 4c 4c 2c 20 26 67  (void *)NULL, &g
0f30: 72 29 3b 0a 20 20 61 73 73 65 72 74 28 6f 6b 29  r);.  assert(ok)
0f40: 3b 0a 0a 20 20 66 6f 72 20 28 75 69 6e 74 20 69  ;..  for (uint i
0f50: 20 3d 20 30 3b 20 69 20 3c 20 67 72 2e 76 2e 73   = 0; i < gr.v.s
0f60: 69 7a 65 28 29 3b 20 69 2b 2b 29 20 7b 0a 20 20  ize(); i++) {.  
0f70: 20 20 6c 6f 63 74 61 62 6c 65 2d 3e 61 64 64 5f    loctable->add_
0f80: 6e 6f 64 65 28 67 72 2e 76 5b 69 5d 29 3b 0a 20  node(gr.v[i]);. 
0f90: 20 7d 0a 20 20 70 72 69 6e 74 66 28 22 25 73 20   }.  printf("%s 
0fa0: 68 61 68 61 20 67 65 74 20 6c 6f 63 74 61 62 6c  haha get loctabl
0fb0: 65 20 73 69 7a 65 20 25 64 20 6e 65 77 20 6c 6f  e size %d new lo
0fc0: 63 74 61 62 6c 65 20 73 69 7a 65 20 25 64 5c 6e  ctable size %d\n
0fd0: 22 2c 0a 20 20 20 20 20 20 74 73 28 29 2c 20 67  ",.      ts(), g
0fe0: 72 2e 76 2e 73 69 7a 65 28 29 2c 20 6c 6f 63 74  r.v.size(), loct
0ff0: 61 62 6c 65 2d 3e 73 69 7a 65 28 29 29 3b 0a 0a  able->size());..
1000: 20 20 64 65 6c 61 64 64 5f 61 72 67 73 20 61 61    deladd_args aa
1010: 3b 0a 20 20 61 61 2e 6e 20 20 3d 20 6d 65 3b 0a  ;.  aa.n  = me;.
1020: 20 20 76 65 63 74 6f 72 3c 43 68 6f 72 64 3a 3a    vector<Chord::
1030: 49 44 4d 61 70 3e 20 76 20 3d 20 6c 6f 63 74 61  IDMap> v = locta
1040: 62 6c 65 2d 3e 67 65 74 5f 61 6c 6c 28 29 3b 0a  ble->get_all();.
1050: 0a 20 20 75 6e 73 69 67 6e 65 64 20 72 70 63 20  .  unsigned rpc 
1060: 3d 20 30 3b 0a 20 20 52 50 43 53 65 74 20 72 70  = 0;.  RPCSet rp
1070: 63 73 65 74 3b 0a 20 20 72 70 63 73 65 74 2e 63  cset;.  rpcset.c
1080: 6c 65 61 72 28 29 3b 0a 20 20 75 6e 73 69 67 6e  lear();.  unsign
1090: 65 64 20 74 6f 74 61 6c 20 3d 20 30 3b 0a 0a 20  ed total = 0;.. 
10a0: 20 66 6f 72 20 28 75 69 6e 74 20 69 20 3d 20 30   for (uint i = 0
10b0: 3b 20 69 20 3c 20 76 2e 73 69 7a 65 28 29 3b 20  ; i < v.size(); 
10c0: 69 2b 2b 29 20 7b 0a 20 20 20 20 69 66 20 28 76  i++) {.    if (v
10d0: 5b 69 5d 2e 69 70 20 3d 3d 20 6d 65 2e 69 70 29  [i].ip == me.ip)
10e0: 20 63 6f 6e 74 69 6e 75 65 3b 0a 20 20 20 20 2f   continue;.    /
10f0: 2f 72 65 63 6f 72 64 5f 73 74 61 74 28 29 3b 0a  /record_stat();.
1100: 20 20 20 20 61 73 73 65 72 74 28 76 5b 69 5d 2e      assert(v[i].
1110: 69 70 29 3b 0a 20 20 20 20 2f 2f 63 61 6e 63 65  ip);.    //cance
1120: 6c 52 50 43 28 61 73 79 6e 63 52 50 43 28 76 5b  lRPC(asyncRPC(v[
1130: 69 5d 2e 69 70 2c 20 26 43 68 6f 72 64 4f 6e 65  i].ip, &ChordOne
1140: 48 6f 70 3a 3a 61 64 64 5f 68 61 6e 64 6c 65 72  Hop::add_handler
1150: 2c 20 0a 09 2f 2f 09 26 61 61 2c 20 28 76 6f 69  , ..//.&aa, (voi
1160: 64 20 2a 29 4e 55 4c 4c 29 29 3b 20 0a 20 20 20  d *)NULL)); .   
1170: 20 72 70 63 20 3d 20 61 73 79 6e 63 52 50 43 28   rpc = asyncRPC(
1180: 76 5b 69 5d 2e 69 70 2c 20 26 43 68 6f 72 64 4f  v[i].ip, &ChordO
1190: 6e 65 48 6f 70 3a 3a 61 64 64 5f 68 61 6e 64 6c  neHop::add_handl
11a0: 65 72 2c 20 26 61 61 2c 20 28 76 6f 69 64 20 2a  er, &aa, (void *
11b0: 29 4e 55 4c 4c 29 3b 20 0a 20 20 20 20 61 73 73  )NULL); .    ass
11c0: 65 72 74 28 72 70 63 29 3b 0a 20 20 20 20 72 70  ert(rpc);.    rp
11d0: 63 73 65 74 2e 69 6e 73 65 72 74 28 72 70 63 29  cset.insert(rpc)
11e0: 3b 0a 20 20 20 20 61 73 73 65 72 74 28 61 61 2e  ;.    assert(aa.
11f0: 6e 2e 69 70 20 3d 3d 20 6d 65 2e 69 70 29 3b 0a  n.ip == me.ip);.
1200: 20 20 20 20 74 6f 74 61 6c 2b 2b 3b 0a 20 20 20      total++;.   
1210: 20 2f 2f 64 6f 52 50 43 28 76 5b 69 5d 2e 69 70   //doRPC(v[i].ip
1220: 2c 20 26 43 68 6f 72 64 4f 6e 65 48 6f 70 3a 3a  , &ChordOneHop::
1230: 61 64 64 5f 68 61 6e 64 6c 65 72 2c 20 26 61 61  add_handler, &aa
1240: 2c 20 28 76 6f 69 64 20 2a 29 4e 55 4c 4c 29 3b  , (void *)NULL);
1250: 20 0a 20 20 7d 0a 20 20 61 73 73 65 72 74 28 74   .  }.  assert(t
1260: 6f 74 61 6c 20 3d 3d 20 72 70 63 73 65 74 2e 73  otal == rpcset.s
1270: 69 7a 65 28 29 29 3b 0a 20 20 2f 2f 69 20 6d 75  ize());.  //i mu
1280: 73 74 20 72 65 63 65 69 76 65 20 74 68 65 73 65  st receive these
1290: 20 52 50 43 73 2c 20 6f 74 68 65 72 77 69 73 65   RPCs, otherwise
12a0: 2c 20 61 61 20 67 6f 74 20 64 65 61 6c 6c 6f 63  , aa got dealloc
12b0: 61 74 65 64 20 0a 20 20 2f 2f 61 6e 64 20 72 65  ated .  //and re
12c0: 63 65 69 76 65 72 73 20 77 69 6c 6c 20 67 65 74  ceivers will get
12d0: 20 67 61 72 62 61 67 65 0a 20 20 75 69 6e 74 20   garbage.  uint 
12e0: 6f 75 74 73 74 61 6e 64 69 6e 67 20 3d 20 72 70  outstanding = rp
12f0: 63 73 65 74 2e 73 69 7a 65 28 29 3b 0a 20 20 77  cset.size();.  w
1300: 68 69 6c 65 20 28 6f 75 74 73 74 61 6e 64 69 6e  hile (outstandin
1310: 67 20 3e 20 30 29 20 7b 0a 20 20 20 20 2f 2f 20  g > 0) {.    // 
1320: 75 6e 73 69 67 6e 65 64 20 64 6f 6e 65 72 70 63  unsigned donerpc
1330: 20 3d 20 72 63 76 52 50 43 28 26 72 70 63 73 65   = rcvRPC(&rpcse
1340: 74 29 3b 0a 20 20 20 20 6f 75 74 73 74 61 6e 64  t);.    outstand
1350: 69 6e 67 2d 2d 3b 0a 20 20 20 20 61 73 73 65 72  ing--;.    asser
1360: 74 28 6f 75 74 73 74 61 6e 64 69 6e 67 20 3d 3d  t(outstanding ==
1370: 20 72 70 63 73 65 74 2e 73 69 7a 65 28 29 29 3b   rpcset.size());
1380: 0a 20 20 20 20 61 73 73 65 72 74 28 61 61 2e 6e  .    assert(aa.n
1390: 2e 69 70 20 3d 3d 20 6d 65 2e 69 70 29 3b 0a 20  .ip == me.ip);. 
13a0: 20 7d 0a 0a 7d 0a 0a 76 65 63 74 6f 72 3c 43 68   }..}..vector<Ch
13b0: 6f 72 64 3a 3a 49 44 4d 61 70 3e 0a 43 68 6f 72  ord::IDMap>.Chor
13c0: 64 4f 6e 65 48 6f 70 3a 3a 66 69 6e 64 5f 73 75  dOneHop::find_su
13d0: 63 63 65 73 73 6f 72 73 28 43 48 49 44 20 6b 2c  ccessors(CHID k,
13e0: 20 75 69 6e 74 20 6d 2c 20 75 69 6e 74 20 61 6c   uint m, uint al
13f0: 6c 2c 20 62 6f 6f 6c 20 69 73 5f 6c 6f 6f 6b 75  l, bool is_looku
1400: 70 29 0a 7b 0a 20 20 76 65 63 74 6f 72 3c 43 68  p).{.  vector<Ch
1410: 6f 72 64 3a 3a 49 44 4d 61 70 3e 20 76 3b 0a 20  ord::IDMap> v;. 
1420: 20 76 2e 63 6c 65 61 72 28 29 3b 0a 0a 20 20 75   v.clear();..  u
1430: 69 6e 74 20 74 69 6d 65 6f 75 74 20 3d 20 30 3b  int timeout = 0;
1440: 0a 20 20 49 44 4d 61 70 20 73 75 63 63 3b 0a 20  .  IDMap succ;. 
1450: 20 62 6f 6f 6c 20 6f 6b 3b 0a 0a 20 20 2f 2f 67   bool ok;..  //g
1460: 6f 20 64 69 72 65 63 74 6c 79 20 74 6f 20 74 68  o directly to th
1470: 65 20 73 75 63 63 65 73 73 6f 72 0a 20 20 77 68  e successor.  wh
1480: 69 6c 65 20 28 31 29 20 7b 0a 20 20 20 20 73 75  ile (1) {.    su
1490: 63 63 20 3d 20 6c 6f 63 74 61 62 6c 65 2d 3e 73  cc = loctable->s
14a0: 75 63 63 28 6b 29 3b 0a 20 20 20 20 2f 2f 72 65  ucc(k);.    //re
14b0: 63 6f 72 64 5f 73 74 61 74 28 69 73 5f 6c 6f 6f  cord_stat(is_loo
14c0: 6b 75 70 3f 31 3a 30 29 3b 0a 20 20 20 20 6f 6b  kup?1:0);.    ok
14d0: 20 3d 20 64 6f 52 50 43 28 73 75 63 63 2e 69 70   = doRPC(succ.ip
14e0: 2c 20 26 43 68 6f 72 64 3a 3a 6e 75 6c 6c 5f 68  , &Chord::null_h
14f0: 61 6e 64 6c 65 72 2c 20 28 76 6f 69 64 20 2a 29  andler, (void *)
1500: 4e 55 4c 4c 2c 20 26 73 75 63 63 29 3b 0a 20 20  NULL, &succ);.  
1510: 20 20 69 66 20 28 28 21 6f 6b 29 20 26 26 20 28    if ((!ok) && (
1520: 61 6c 69 76 65 28 29 29 29 20 7b 0a 20 20 20 20  alive())) {.    
1530: 20 20 74 69 6d 65 6f 75 74 2b 2b 3b 0a 20 20 20    timeout++;.   
1540: 20 20 20 6c 6f 63 74 61 62 6c 65 2d 3e 64 65 6c     loctable->del
1550: 5f 6e 6f 64 65 28 73 75 63 63 29 3b 0a 20 20 20  _node(succ);.   
1560: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 76 2e   }else{.      v.
1570: 70 75 73 68 5f 62 61 63 6b 28 73 75 63 63 29 3b  push_back(succ);
1580: 0a 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20  .      break;.  
1590: 20 20 7d 0a 20 20 7d 0a 0a 20 20 69 66 20 28 69    }.  }..  if (i
15a0: 73 5f 6c 6f 6f 6b 75 70 29 20 7b 0a 20 20 20 20  s_lookup) {.    
15b0: 70 72 69 6e 74 66 20 28 22 66 69 6e 64 5f 73 75  printf ("find_su
15c0: 63 63 65 73 73 6f 72 20 66 6f 72 20 28 69 64 20  ccessor for (id 
15d0: 25 71 78 2c 20 6b 65 79 20 25 71 78 29 22 2c 20  %qx, key %qx)", 
15e0: 6d 65 2e 69 64 2c 20 6b 29 3b 0a 20 20 20 20 70  me.id, k);.    p
15f0: 72 69 6e 74 66 20 28 22 69 73 20 28 25 75 2c 20  rintf ("is (%u, 
1600: 25 71 78 29 20 68 6f 70 73 20 32 20 74 69 6d 65  %qx) hops 2 time
1610: 6f 75 74 20 25 64 5c 6e 22 2c 20 76 5b 30 5d 2e  out %d\n", v[0].
1620: 69 70 2c 20 76 5b 30 5d 2e 69 64 2c 74 69 6d 65  ip, v[0].id,time
1630: 6f 75 74 29 3b 0a 20 20 7d 0a 20 20 72 65 74 75  out);.  }.  retu
1640: 72 6e 20 76 3b 0a 7d 0a                          rn v;.}.