<commit_before>#include "chord.h"
#include "succ_list.h"
#include <location.h>
#include <locationtable.h>
#include <id_utils.h>
#include <misc_utils.h>

#include <configurator.h>

/*
 * The idea of the succ_list class is to maintain a list of
 * immediate successors to the current node. The actual number
 * of successors needed is up to nsucc. The location information
 * is maintained in locationtable.
 */
succ_list::succ_list (ptr<vnode> v,
		      ptr<locationtable> locs)
  : myID (v->my_ID ()), myvnode (v), locations (locs)
{
  nnodes = 0;
  
  bool ok = Configurator::only ().get_int ("chord.nsucc", nsucc_);
  assert (ok);
  
  oldsucc = v->my_location ();
  stable_succlist = false;
  stable_succlist2 = false;
  nout_backoff = 0;
  nout_continuous = 0;

  locations->pin (myID, 1);
  locations->pin (myID, nsucc_);
}
   
ptr<location>
succ_list::succ ()
{
  return locations->closestsuccloc (incID (myID));
}

vec<ptr<location> >
succ_list::succs ()
{
  vec<ptr<location> > ret;
  
  ptr<location> cur = succ ();
  ret.push_back (cur);

  for (u_int i = 1; i < num_succ (); i++) {
    cur = locations->closestsuccloc (incID (cur->id ()));
    ret.push_back (cur);
  }
  return ret;
}

unsigned int
succ_list::num_succ ()
{
  int goodnodes = locations->usablenodes () - 1;
  int newnsucc = (nsucc_ > goodnodes) ? goodnodes : nsucc_;
  
  if (newnsucc < 0) {
    warn << "succ_list::num_succ () n:" << newnsucc << " g:" << goodnodes << "\n";
    newnsucc = 0;
  }
  return newnsucc;
}

void
succ_list::print (strbuf &outbuf)
{
  vec<ptr<location> > s = succs ();
  for (u_int i = 0; i < s.size (); i++)
    outbuf << myID << ": succ " << i + 1 << " : " << s[i]->id () << "\n";
}

u_long
succ_list::estimate_nnodes ()
{
  u_long n;
  ptr<location> lastsucc = myvnode->my_location ();
  int nsucc = num_succ ();
  for (int i = 0; i < nsucc; i++)
    lastsucc = locations->closestsuccloc (incID (lastsucc->id ()));
  
  chordID d = diff (myID, lastsucc->id ());
  if ((d > 0) && (nsucc > 0)) {
    chordID s = d / nsucc;
    chordID c = bigint (1) << NBIT;
    chordID q = c / s;
    n = q.getui ();
  } else 
    n = 1;
  return n;
}

void
succ_list::fill_nodelistresext (chord_nodelistextres *res)
{
  // succ[0] is me. the rest are our actual successors.
  int curnsucc = num_succ ();
  ptr<location> cursucc = myvnode->my_location ();
  res->resok->nlist.setsize (curnsucc + 1);
  for (int i = 0; i <= curnsucc; i++) {
    cursucc->fill_node_ext (res->resok->nlist[i]);
    cursucc = locations->closestsuccloc (incID (cursucc->id ()));
  }
}

void
succ_list::fill_nodelistres (chord_nodelistres *res)
{
  // succ[0] is me. the rest are our actual successors.
  int curnsucc = num_succ ();
  ptr<location> cursucc = myvnode->my_location ();
  res->resok->nlist.setsize (curnsucc + 1);
  for (int i = 0; i <= curnsucc; i++) {
    cursucc->fill_node (res->resok->nlist[i]);
    cursucc = locations->closestsuccloc (incID (cursucc->id ()));
  }
}

void
succ_list::stabilize_succlist ()
{
  assert (nout_backoff == 0);
  
  stable_succlist2 = stable_succlist;
  stable_succlist = true;
  
  u_long n = estimate_nnodes ();
  locations->replace_estimate (nnodes, n);
  if (nnodes != n) {
    warnx << myID << ": estimating total number of nodes as "
	  << locations->estimate_nodes () << "\n";
  }
  nnodes = n;

  nout_backoff++;
  ptr<location> s = succ ();
  myvnode->get_succlist
    (s, wrap (this, &succ_list::stabilize_getsucclist_cb, s->id ()));
}

void
succ_list::stabilize_getsucclist_cb (chordID s, vec<chord_node> nlist,
				     chordstat status)
{
  nout_backoff--;
  if (status) {
    warnx << myID << ": stabilize_getsucclist_cb: " << s << " : " 
	  << "failure " << status << "\n";
    stable_succlist = false;
    return;
  }
  assert (s == nlist[0].x);

  // PODC paper says, set our succlist to successors succlist mod last guy
  // We're going to merge his succlist with our succlist and make sure
  // deletions and insertions are accurate from our POV.
  unsigned int i, j;
  vec<ptr<location> > succlist = succs ();
  size_t curnsucc = succlist.size ();

  i = 0; j = 0;
  unsigned int newnsucc = nlist.size () - 1; // drop last guy.
  while ((i < curnsucc) && (j < newnsucc)) {    
    if (succlist[i]->id () == nlist[j].x) { i++; j++; continue; }
    if (between (myID, nlist[j].x, succlist[i]->id ())) {
      // if succlist[i] < nlist[j].x
      // then, maybe someone we knew about is dead now. best be sure.
      nout_backoff++;
      myvnode->ping
	(succlist[i], wrap (this, &succ_list::stabilize_getsucclist_check,
			    s, succlist[i]->id ()));
      i++;
      continue;
    }
    if (between (myID, succlist[i]->id (), nlist[j].x)) {
      // if succlist[i] > nlist[j].x
      // then maybe a new node joined. check it out.
      ptr<location> newsucc = locations->insert (nlist[j]);
      if (!newsucc) {
	warnx << myID << ": stabilize_succlist: received bad successor "
	      << nlist[j].x << " from " << s << "\n";<commit_msg>When receiving updated successor lists, note the new coordinates of known nodes.<commit_after>#include "chord.h"
#include "succ_list.h"
#include <location.h>
#include <locationtable.h>
#include <id_utils.h>
#include <misc_utils.h>

#include <configurator.h>

/*
 * The idea of the succ_list class is to maintain a list of
 * immediate successors to the current node. The actual number
 * of successors needed is up to nsucc. The location information
 * is maintained in locationtable.
 */
succ_list::succ_list (ptr<vnode> v,
		      ptr<locationtable> locs)
  : myID (v->my_ID ()), myvnode (v), locations (locs)
{
  nnodes = 0;
  
  bool ok = Configurator::only ().get_int ("chord.nsucc", nsucc_);
  assert (ok);
  
  oldsucc = v->my_location ();
  stable_succlist = false;
  stable_succlist2 = false;
  nout_backoff = 0;
  nout_continuous = 0;

  locations->pin (myID, 1);
  locations->pin (myID, nsucc_);
}
   
ptr<location>
succ_list::succ ()
{
  return locations->closestsuccloc (incID (myID));
}

vec<ptr<location> >
succ_list::succs ()
{
  vec<ptr<location> > ret;
  
  ptr<location> cur = succ ();
  ret.push_back (cur);

  for (u_int i = 1; i < num_succ (); i++) {
    cur = locations->closestsuccloc (incID (cur->id ()));
    ret.push_back (cur);
  }
  return ret;
}

unsigned int
succ_list::num_succ ()
{
  int goodnodes = locations->usablenodes () - 1;
  int newnsucc = (nsucc_ > goodnodes) ? goodnodes : nsucc_;
  
  if (newnsucc < 0) {
    warn << "succ_list::num_succ () n:" << newnsucc << " g:" << goodnodes << "\n";
    newnsucc = 0;
  }
  return newnsucc;
}

void
succ_list::print (strbuf &outbuf)
{
  vec<ptr<location> > s = succs ();
  for (u_int i = 0; i < s.size (); i++)
    outbuf << myID << ": succ " << i + 1 << " : " << s[i]->id () << "\n";
}

u_long
succ_list::estimate_nnodes ()
{
  u_long n;
  ptr<location> lastsucc = myvnode->my_location ();
  int nsucc = num_succ ();
  for (int i = 0; i < nsucc; i++)
    lastsucc = locations->closestsuccloc (incID (lastsucc->id ()));
  
  chordID d = diff (myID, lastsucc->id ());
  if ((d > 0) && (nsucc > 0)) {
    chordID s = d / nsucc;
    chordID c = bigint (1) << NBIT;
    chordID q = c / s;
    n = q.getui ();
  } else 
    n = 1;
  return n;
}

void
succ_list::fill_nodelistresext (chord_nodelistextres *res)
{
  // succ[0] is me. the rest are our actual successors.
  int curnsucc = num_succ ();
  ptr<location> cursucc = myvnode->my_location ();
  res->resok->nlist.setsize (curnsucc + 1);
  for (int i = 0; i <= curnsucc; i++) {
    cursucc->fill_node_ext (res->resok->nlist[i]);
    cursucc = locations->closestsuccloc (incID (cursucc->id ()));
  }
}

void
succ_list::fill_nodelistres (chord_nodelistres *res)
{
  // succ[0] is me. the rest are our actual successors.
  int curnsucc = num_succ ();
  ptr<location> cursucc = myvnode->my_location ();
  res->resok->nlist.setsize (curnsucc + 1);
  for (int i = 0; i <= curnsucc; i++) {
    cursucc->fill_node (res->resok->nlist[i]);
    cursucc = locations->closestsuccloc (incID (cursucc->id ()));
  }
}

void
succ_list::stabilize_succlist ()
{
  assert (nout_backoff == 0);
  
  stable_succlist2 = stable_succlist;
  stable_succlist = true;
  
  u_long n = estimate_nnodes ();
  locations->replace_estimate (nnodes, n);
  if (nnodes != n) {
    warnx << myID << ": estimating total number of nodes as "
	  << locations->estimate_nodes () << "\n";
  }
  nnodes = n;

  nout_backoff++;
  ptr<location> s = succ ();
  myvnode->get_succlist
    (s, wrap (this, &succ_list::stabilize_getsucclist_cb, s->id ()));
}

void
succ_list::stabilize_getsucclist_cb (chordID s, vec<chord_node> nlist,
				     chordstat status)
{
  nout_backoff--;
  if (status) {
    warnx << myID << ": stabilize_getsucclist_cb: " << s << " : " 
	  << "failure " << status << "\n";
    stable_succlist = false;
    return;
  }
  assert (s == nlist[0].x);

  // PODC paper says, set our succlist to successors succlist mod last guy
  // We're going to merge his succlist with our succlist and make sure
  // deletions and insertions are accurate from our POV.
  unsigned int i, j;
  vec<ptr<location> > succlist = succs ();
  size_t curnsucc = succlist.size ();

  i = 0; j = 0;
  unsigned int newnsucc = nlist.size () - 1; // drop last guy.
  while ((i < curnsucc) && (j < newnsucc)) {    
    if (succlist[i]->id () == nlist[j].x) {
      succlist[i]->set_coords (nlist[j]);
      i++; j++; continue;
    }
    if (between (myID, nlist[j].x, succlist[i]->id ())) {
      // if succlist[i] < nlist[j].x
      // then, maybe someone we knew about is dead now. best be sure.
      nout_backoff++;
      myvnode->ping
	(succlist[i], wrap (this, &succ_list::stabilize_getsucclist_check,
			    s, succlist[i]->id ()));
      i++;
      continue;
    }
    if (between (myID, succlist[i]->id (), nlist[j].x)) {
      // if succlist[i] > nlist[j].x
      // then maybe a new node joined. check it out.
      ptr<location> newsucc = locations->insert (nlist[j]);
      if (!newsucc) {
	warnx << myID << ": stabilize_succlist: received bad successor "
	      << nlist[j].x << " from " << s << "\n";
{'fraction_non_alphanumeric': 0.1660538606777303, 'fraction_numerical': 0.005564940872503229, 'mean_word_length': 3.1828761429758936, 'pattern_counts': {'":': 8, '<': 183, '<?xml version=': 0, '>': 136, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4286868', 'n_tokens_mistral': 4084, 'n_tokens_neox': 3820, 'n_words': 966}