vis.c

基于chord算法的p2p文件系统。A p2p file system based on chord.

/*
 * Copyright (c) 2003-2005 [NAMES_GO_HERE]
 *                    Massachusetts Institute of Technology
 * 
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 * 
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#include "protocols/chord.h"
#include "gtk/gtk.h"
#include "math.h"
#include <stdio.h>
#include <iostream>
using namespace std;

#define WINX 700
#define WINY 700
#define PI 3.14159

#define NELEM(x)	(sizeof (x)/ sizeof ((x)[0]))

// Interesting things to draw and their handlers.
static const unsigned int DRAW_IMMED_SUCC = 1 << 0;
static const unsigned int DRAW_SUCC_LIST  = 1 << 1;
static const unsigned int DRAW_IMMED_PRED = 1 << 2;
static const unsigned int DRAW_DEBRUIJN   = 1 << 3;
static const unsigned int DRAW_FINGERS    = 1 << 4;
static const unsigned int DRAW_TOES       = 1 << 5;

struct handler_info {
  unsigned int flag;
  char *name;
  GtkWidget *widget;
  GtkSignalFunc handler;
};
void draw_toggle_cb (GtkWidget *widget, gpointer data);
// widgets will be initialized later, by initgraf.
static handler_info handlers[] = {
  { DRAW_IMMED_SUCC, "immed. succ", NULL, GTK_SIGNAL_FUNC (draw_toggle_cb) },
  { DRAW_SUCC_LIST,  "succ. list",  NULL, GTK_SIGNAL_FUNC (draw_toggle_cb) },
  { DRAW_DEBRUIJN,  "debruijn",  NULL, GTK_SIGNAL_FUNC (draw_toggle_cb) },
  { DRAW_IMMED_PRED, "immed. pred", NULL, GTK_SIGNAL_FUNC (draw_toggle_cb) },
  { DRAW_FINGERS,    "fingers",     NULL, GTK_SIGNAL_FUNC (draw_toggle_cb) },
  { DRAW_TOES,       "neighbors",   NULL, GTK_SIGNAL_FUNC (draw_toggle_cb) }
};

unsigned int check_get_state (void);
void check_set_state (unsigned int newstate);

static GdkPixmap *pixmap = NULL;
static GtkWidget *window = NULL;
static GtkWidget *drawing_area = NULL;
static GtkWidget *drawing_area_r = NULL;
static GdkGC *draw_gc = NULL;
static GdkColormap *cmap = NULL;
static GdkFont *courier10 = NULL;
static GtkAdjustment *bar = NULL;
static GtkWidget *scroll;
static GdkColor red;
static GdkColor search_color;

static GtkWidget *last_clicked;
static GtkWidget *total_nodes;

static short interval = 1;
static char *color_file;
static bool drawids = false;

static ifstream in;

static GdkGCValues GCValues;

static float zoomx = 1.0;
static float zoomy = 1.0;
static float centerx = 0.0;
static float centery = 0.0;
static int radius = 2;

static bool ggeo = false;
static bool displaysearch = false;

static ulong begin = 0;
static ulong endofsim = 1000;
static ulong curtime;

struct color_pair {
  GdkColor c;
  unsigned long lat;
};

vector<color_pair> lat_map;

struct f_node {
  ConsistentHash::CHID id;
  vector<float> coords;
  ConsistentHash::CHID pred;
  ConsistentHash::CHID succ;
  ConsistentHash::CHID debruijn;
  ConsistentHash::CHID key;
  vector<ConsistentHash::CHID> succlist;
  vector<ConsistentHash::CHID> dfingers;
  vector<ConsistentHash::CHID> search;
  vector<ConsistentHash::CHID> isearch;
  unsigned int draw;
  bool selected;
  bool highlight;
  
  f_node (ConsistentHash::CHID n) : id (n), selected(false), highlight(false) {
    draw = check_get_state ();
    pred = n;
    succ = n;
  };
  ~f_node () {};
};

vector<f_node> nodes;

void initgraf ();
void init_color_list (char *filename);
void draw_arrow (int fromx, int fromy, 
		 int tox, int toy, GdkGC *draw_gc);
void draw_arc (ConsistentHash::CHID from, ConsistentHash::CHID to, GdkGC *draw_gc);

static gint configure_event (GtkWidget *widget, GdkEventConfigure *event);
static gint expose_event (GtkWidget *widget, GdkEventExpose *event);
static gint delete_event (GtkWidget *widget, GdkEvent *event, gpointer data);
static gint key_release_event (GtkWidget *widget,
			       GdkEventKey *event,
			       gpointer data);
static gint button_down_event (GtkWidget *widget,
			       GdkEventButton *event,
			       gpointer data);
void select_all_cb (GtkWidget *widget, gpointer data);
void select_none_cb (GtkWidget *widget, gpointer data);
void draw_nothing_cb (GtkWidget *widget, gpointer data);

void run_cb (GtkWidget *widget, gpointer data);
void step_cb (GtkWidget *widget, gpointer data);
void scroll_cb (GtkAdjustment *adj, gpointer data);

void quit_cb (GtkWidget *widget, gpointer data);
void redraw_cb (GtkWidget *widget, gpointer data);
void search_cb (GtkWidget *widget, gpointer data);
void zoom_in_cb (GtkWidget *widget, gpointer data);
void geo_cb (GtkWidget *widget, gpointer data);
void dump_cb (GtkWidget *widget, gpointer data);
void gtk_poll ();
void draw_ring ();

uint
find (ConsistentHash::CHID n) {
  for (uint i = 0; nodes.size (); i++) {
    if (nodes[i].id == n) {
      return i;
    }
  }
  assert (0);
  return 0;
}

void 
print ()
{
  for (uint i = 0; i < nodes.size (); i++) {
    printf ("node %u is %16qx\n", i, nodes[i].id);
  }
}

void
add_node (ConsistentHash::CHID n) {
  for (uint i = 0; i < nodes.size (); i++) {
    if (nodes[i].id > n) {
      nodes.insert (nodes.begin() + i, f_node(n));
      return;
    }
  }
  nodes.push_back (f_node(n));
}


// --- drawing ----------------------------------------------------------------
double 
ID_to_angle (ConsistentHash::CHID ID)
{
  int z = ID >> (NBCHID - 16);
  return (z/65535.0) * 2 * 3.14159;
}

void
ID_to_xy (ConsistentHash::CHID ID, int *x, int *y)
{
  if (ggeo) {
    assert (0);
  } else {
    double angle = ID_to_angle (ID);
    double radius = (WINX - 60)/2;
    *x = (int)(WINX/2 + sin (angle)*radius);
    *y = (int)(WINY/2 - cos (angle)*radius);
  }
}

ConsistentHash::CHID
xy_to_ID (int sx, int sy)
{
  int min = RAND_MAX;
  ConsistentHash::CHID closest = nodes[0].id;
  for (uint i = 0; i < nodes.size (); i++) {
    int x,y;
    ID_to_xy (nodes[i].id, &x, &y);
    int dist = (sx - x)*(sx - x) + (sy - y)*(sy - y);
    if (dist < min) {
      closest = nodes[i].id;
      min = dist;
    }
  }
  return closest;
}


void
redraw() 
{
  GdkRectangle update_rect;
  
  update_rect.x = 0;
  update_rect.y = 0;
  update_rect.width = WINX;
  update_rect.height = WINY;

  gtk_widget_draw(drawing_area, &update_rect);
  gtk_widget_show(scroll);
}

void
draw_arrow (int fromx, int fromy, 
	    int tox, int toy, GdkGC *draw_gc)
{
  gdk_draw_line (pixmap,
		 draw_gc,
		 fromx,fromy,
		 tox,toy);

  float t = std::atan2 ((float) (tox - fromx), (float) (toy - fromy));
  float phi = PI/4 - t;
  float theta = PI/4 + t;
  float l = 10.0;

  float px = l*sin (phi) + tox;
  float py = -l*cos (phi) + toy;
  float p2y = toy - l*cos (theta);
  float p2x = tox - l*sin (theta);  

  GdkPoint head[4];
  head[0].x = (gint)px;
  head[0].y = (gint)py;
  head[1].x = (gint)tox;
  head[1].y = (gint)toy;
  head[2].x = (gint)p2x;
  head[2].y = (gint)p2y;

  gdk_draw_polygon (pixmap, draw_gc, true, head, 3);
}

void
draw_fingers (f_node *iter, bool all)
{
  int x, y;

  ID_to_xy (iter->id, &x, &y);

  if (all || ((iter->draw & DRAW_IMMED_PRED) == DRAW_IMMED_PRED)) {
    int a,b;
    ID_to_xy (iter->pred, &a, &b);
    draw_arrow (x, y, a, b, draw_gc);
  }

  if (all || ((iter->draw & DRAW_IMMED_SUCC) == DRAW_IMMED_SUCC)) {
    int a,b;
    ID_to_xy (iter->succ, &a, &b);
    draw_arrow (x, y, a, b, draw_gc);
  }

  if (all || ((iter->draw & DRAW_SUCC_LIST) == DRAW_SUCC_LIST)) {
    for (uint j = 0; j < iter->succlist.size (); j++) {
      int a,b;
      ID_to_xy (iter->succlist[j], &a, &b);
      draw_arrow (x, y, a, b, draw_gc);
    }
  }

  if (all || ((iter->draw & DRAW_DEBRUIJN) == DRAW_DEBRUIJN)) {
    // int a, b;
    //    ID_to_xy (iter->debruijn, &a, &b);

    gdk_gc_set_foreground (draw_gc, &red);
    //    draw_arrow (x, y, a, b,  draw_gc);

    for (uint j = 0; j < iter->dfingers.size (); j++) {
      int a, b;
      ID_to_xy (iter->dfingers[j], &a, &b);
      draw_arrow (x, y, a, b, draw_gc);
    }
    gdk_gc_set_foreground (draw_gc, &GCValues.foreground);

  }

}

void
draw_node (f_node *iter)
{
  int x, y;
  int rad = radius + 2;

  ID_to_xy (iter->id, &x, &y);

  gdk_draw_arc (pixmap, draw_gc, FALSE, x - rad, y - rad, 2*rad, 
		2*rad, (gint16)0, (gint16)64*360);

  if (drawids) {
    char ids[128];
    sprintf (ids, "%16qx", iter->id);
    int fudge = -10;
    if (x < WINX/2) fudge = 0;
    gdk_draw_string (pixmap, courier10, drawing_area->style->black_gc, 
		     x + fudge, y, ids);
  }

  draw_fingers (iter, false);
}


void
draw_ring ()
{
  int x, y;
  GtkWidget *widget = drawing_area;

  gdk_draw_rectangle (pixmap, widget->style->white_gc, TRUE, 0, 0, WINX, WINY);
  gdk_draw_rectangle (pixmap, widget->style->black_gc, FALSE, 0, 0, 
		      WINX - 1, WINY - 1);

  for (vector<f_node>::iterator iter = nodes.begin (); iter != nodes.end (); 
       ++iter) {

    ID_to_xy (iter->id, &x, &y);

    gdk_draw_arc (pixmap, draw_gc, TRUE, x - radius, y - radius,
		  2*radius, 2*radius, (gint16)0, (gint16)64*360);

    if (iter->selected) {
      f_node fx = *iter;
      draw_node(&fx);
    }

    if (iter->search.size () > 0) {
      int k, l;
      ID_to_xy (iter->key, &k, &l);
      int rad = radius + 2;

      gdk_gc_set_foreground (draw_gc, &red);

      gdk_draw_arc (pixmap, draw_gc, FALSE, k - rad, l - rad,
		    2*rad, 2*rad, (gint16)0, (gint16)64*360);

      gdk_gc_set_foreground (draw_gc, &search_color);

      for (uint j = 0; j < iter->isearch.size (); j++) {
	int a, b;
	ID_to_xy (iter->isearch[j], &a, &b);
	gdk_draw_arc (pixmap, draw_gc, FALSE, a - rad, b - rad,
		      2*rad, 2*rad, (gint16)0, (gint16)64*360);
      }

      for (uint j = 0; j < iter->search.size (); j++) {
	int a, b;
	ID_to_xy (iter->search[j], &a, &b);
	draw_arrow (x, y, a, b, draw_gc);
	x = a;
	y = b;
      }

      gdk_gc_set_foreground (draw_gc, &GCValues.foreground);

      uint i = find(iter->search.back ());
      draw_fingers (&(nodes[i]), true);
    }

  }
  
  redraw ();
}

void
recenter ()
{
  float minx=RAND_MAX, miny=RAND_MAX;
  float maxx=-RAND_MAX, maxy=-RAND_MAX;

  for (uint i = 0; i < nodes.size (); i++) {
    if (nodes[i].coords.size () > 0) {
      float x = nodes[i].coords[0];
      float y = nodes[i].coords[1];
      minx = (x < minx) ? x : minx;
      miny = (y < miny) ? y : miny;
      maxx = (x > maxx) ? x : maxx;
      maxy = (y > maxy) ? y : maxy;
    }
  }

  centerx = (maxx + minx)/2.0;
  centery = (maxy + miny)/2.0;
  
  zoomx = maxx - minx;
  zoomy = maxy - miny;

  zoomx *= 1.3;
  zoomy *= 1.3;

  if (zoomx > zoomy) zoomy = zoomx;
  if (zoomy > zoomx) zoomx = zoomy;
}

void
update () 
{
}

// --- process events ----------------------------------------------------------

vector<string>
split(string line, string delims)
{
  string::size_type bi, ei;
  vector<string> words;

  bi = line.find_first_not_of(delims);
  while(bi != string::npos) {
    ei = line.find_first_of(delims, bi);
    if(ei == string::npos)
      ei = line.length();
    words.push_back(line.substr(bi, ei-bi));
    bi = line.find_first_not_of(delims, ei);
  }

  return words;
}

bool
doevent (ulong t)
{
  string line;
  ulong ts = curtime;
  bool step = false;

  if ((ts >= t) || (curtime >= endofsim)) {
    return (step);
  }

  while (getline (in, line)) {
    vector <string> words = split (line);

    if (words.empty () || (words[0] != "vis")) 
      continue;

    ulong ts1 = atoi(words[1].c_str ());

    assert (ts1 >= ts);
    ts = ts1;

    if (words[2] == "node") {
      ConsistentHash::CHID id = strtoull (words[3].c_str (), NULL, 16);
      add_node (id);
    }

    if (words[2] == "join") {
      ConsistentHash::CHID id = strtoull (words[3].c_str (), NULL, 16);
      uint i = find (id);
      nodes[i].selected = true;
    }

    if (words[2] == "succ") {
      ConsistentHash::CHID id = strtoull (words[3].c_str (), NULL, 16);
      ConsistentHash::CHID s = strtoull (words[4].c_str (), NULL, 16);
      uint i = find (id);
      nodes[i].succ = s;
    }

    if (words[2] == "pred") {
      ConsistentHash::CHID id = strtoull (words[3].c_str (), NULL, 16);
      ConsistentHash::CHID p = strtoull (words[4].c_str (), NULL, 16);
      uint i = find (id);
      nodes[i].pred = p;
    }

    if (words[2] == "succlist") {
      ConsistentHash::CHID id = strtoull (words[3].c_str (), NULL, 16);
      uint i = find (id);
      nodes[i].succlist.clear ();
      for (uint j = 4; j < words.size (); j++) {
	ConsistentHash::CHID s = strtoull (words[j].c_str (), NULL, 16);
	nodes[i].succlist.push_back(s);
      }
    }

    if (words[2] == "dfingers") {
      ConsistentHash::CHID id = strtoull (words[3].c_str (), NULL, 16);
      ConsistentHash::CHID d = strtoull (words[4].c_str (), NULL, 16);
      uint i = find (id);
      nodes[i].debruijn = d;
      nodes[i].dfingers.clear ();
      for (uint j = 5; j < words.size (); j++) {
	ConsistentHash::CHID s = strtoull (words[j].c_str (), NULL, 16);
	nodes[i].dfingers.push_back(s);
      }
    }

    if (words[2] == "search") {
      ConsistentHash::CHID id = strtoull (words[3].c_str (), NULL, 16);
      uint i = find (id);
      nodes[i].key = strtoull (words[4].c_str (), NULL, 16);
      nodes[i].search.clear ();
      nodes[i].isearch.clear ();
      if (words.size () > 5) {
	ConsistentHash::CHID k = strtoull (words[5].c_str (), NULL, 16);
	nodes[i].isearch.push_back(k);
      }