classifier.cc

COPE the first practical network coding scheme which is developped on click

 *   back end of 'path'. Current activation == back end of path.
 *
 * - State the activation is in: Three valid states, "BEFORE_YES" (have not
 *   yet made recursive call along yes branch, the initial state), "BEFORE_NO"
 *   (have not yet made recursive call along no branch), "BEFORE_COMBINE"
 *   (after both recursive calls but before return). Stored in 'flags[expr#] &
 *   STATE_FLAG'.
 *
 * - Whether 'yet' is true: Stored in 'flags[expr#] & YET_FLAG'.
 *
 * - Whether the recursive call for the 'yes' branch succeeded: Stored in
 *   'flags[expr#] & YES_OK_FLAG'.
 *
 * - The 'yes_output' and 'no_output' arrays: Stored in 'output'. Say that an
 *   activation starts with 'output.size() == X'. Then the iterative
 *   activation, like the recursive activation, will return having appended
 *   some vector (possibly empty) to 'output'. However, there is a difference.
 *   The recursive version passes new vectors to recursive calls. Here, we
 *   simply tack more data on to the single 'output' vector, and use indexes
 *   to tell how long the recursive vectors would have been. Specifically, in
 *   the "BEFORE_COMBINE" state, the vector 'yes_answer' is stored in 'output'
 *   indices 'YES_OUTPUT(flags[expr#]) <= i < NO_OUTPUT(flags[expr#])', and
 *   the vector 'no_answer' is stored in 'output' indices
 *   'NO_OUTPUT(flags[expr#]) <= i < output.size()'. Before "BEFORE_COMBINE"
 *   returns, it moves data around, and probably shrinks the 'output' vector,
 *   so that its return value is as required.
 *
 * The return value for the most recently completed activation record is
 * stored in 'bool result'.
 * */

bool
Classifier::check_path_iterative(Vector<int> &output,
				 int interested, int eventual) const
{
  Vector<int> flags(_exprs.size(), 0);
  Vector<int> path;
  path.reserve(_exprs.size() + 1);
  path.push_back(0);

  bool result = false;		// result of last check_path execution

  // loop until path is empty
  while (path.size()) {

    int ei = path.back();
    int flag = flags[ei];
    bool yet = (flag & YET_FLAG) != 0;
    int state = (flag & STATE_FLAG);

    switch (state) {

     case BEFORE_YES: {
       // check for early breakout
       result = false;
       if (ei > interested && ei != eventual && !yet)
	 goto back_up;
       if (yet)
	 output.push_back(ei);
       assert(ei >= 0);
       assert(!(flag & YES_OK_FLAG) && YES_OUTPUT(flag) == 0);

       // store 'YES_OUTPUT'
       flags[ei] = flag = flag | MK_YES_OUTPUT(output.size());

       const Expr &e = _exprs[ei];
       for (int i = 0; i < path.size() - 1; i++) {
	 const Expr &old = _exprs[path[i]];
	 bool yes = (old.yes == path[i+1]);
	 if ((yes && old.implies_not(e)) || (!yes && old.not_implies_not(e)))
	   goto yes_dead;
       }

       // if we get here, must check `yes' branch
       flags[ei] = (flag & ~STATE_FLAG) | BEFORE_NO;       
       if (ei == interested && e.yes == eventual)
	 yet = true;
       ei = e.yes;
       goto step_forward;
     }

     yes_dead:
     case BEFORE_NO: {
       // store 'NO_OUTPUT'
       flags[ei] = flag = flag | MK_NO_OUTPUT(output.size()) | (result ? YES_OK_FLAG : 0);
       result = false;

       const Expr &e = _exprs[ei];
       for (int i = 0; i < path.size() - 1; i++) {
	 const Expr &old = _exprs[path[i]];
	 bool yes = (old.yes == path[i+1]);
	 if ((yes && old.implies(e)) || (!yes && old.not_implies(e)))
	   goto no_dead;
       }

       // if we get here, must check no branch
       flags[ei] = (flag & ~STATE_FLAG) | BEFORE_COMBINE;
       if (ei == interested && e.no == eventual)
	 yet = true;
       ei = e.no;
       goto step_forward;
     }

     step_forward: {
       // move to 'ei'; check for output port rather than internal node
       if (ei <= 0) {
	 if (yet)
	   output.push_back(ei);
	 result = yet;
	 /* do not move forward */
       } else {
	 flags[ei] = BEFORE_YES | (yet ? YET_FLAG : 0);
	 path.push_back(ei);
       }
       break;
     }
     
     no_dead:
     case BEFORE_COMBINE: {
       const Expr &e = _exprs[ei];
       bool yes_ok = ((flag & YES_OK_FLAG) != 0);
       bool no_ok = result;
       
       if (ei == interested) {
	 if (e.yes == eventual)
	   move_path(output, YES_OUTPUT(flag), YES_OUTPUT(flag), NO_OUTPUT(flag));
	 else
	   move_path(output, YES_OUTPUT(flag), NO_OUTPUT(flag), output.size());
	 result = (e.yes == eventual ? yes_ok : no_ok);
	 
       } else if (yes_ok && no_ok) {
	 common_paths(output, YES_OUTPUT(flag), NO_OUTPUT(flag));
	 result = true;
	 
       } else if (!yes_ok && !no_ok)
	 result = false;
       
       else if (yes_ok) {
	 move_path(output, YES_OUTPUT(flag), YES_OUTPUT(flag), NO_OUTPUT(flag));
	 result = true;

       } else {			// no_ok
	 move_path(output, YES_OUTPUT(flag), NO_OUTPUT(flag), output.size());
	 result = true;
       }

       goto back_up;
     }

     back_up: {
       path.pop_back();
       break;
     }

     default:
      assert(0);
      
    }
  }

  return result;
}

#else /* !CLASSIFIER_ITERATIVE */

static void
common_paths(const Vector<int> &a, const Vector<int> &b, Vector<int> &out)
{
  int ai = 0, bi = 0;
  while (ai < a.size() && bi < b.size()) {
    if (a[ai] == b[bi]) {
      out.push_back(a[ai]);
      ai++;
      bi++;
    }
    // cast to unsigned so that outputs and FAILURE are bigger than
    // internal nodes
    while (ai < a.size() && bi < b.size() && (unsigned)a[ai] < (unsigned)b[bi])
      ai++;
    while (ai < a.size() && bi < b.size() && (unsigned)a[ai] > (unsigned)b[bi])
      bi++;
  }
}

bool
Classifier::check_path(const Vector<int> &path, Vector<int> &output,
		       int ei, int interested, int eventual,
		       bool first, bool yet) const
{
  if (ei > interested && ei != eventual && !yet)
    return false;
  if (yet)
    output.push_back(ei);
  if (ei < 0 || (ei == 0 && !first))
    return yet;

  const Expr &e = _exprs[ei];
  Vector<int> new_path(path);
  new_path.push_back(ei);

  Vector<int> yes_answer;
  bool yes_ok = false;
  for (int i = 0; i < new_path.size() - 1; i++) {
    const Expr &old = _exprs[new_path[i]];
    bool yes = (old.yes == new_path[i+1]);
    if ((yes && old.implies_not(e)) || (!yes && old.not_implies_not(e)))
      goto yes_dead;
  }
  yes_ok = check_path(new_path, yes_answer, e.yes, interested, eventual, false,
		      yet || (ei == interested && e.yes == eventual));

 yes_dead:
  Vector<int> no_answer;
  bool no_ok = false;
  for (int i = 0; i < new_path.size() - 1; i++) {
    const Expr &old = _exprs[new_path[i]];
    bool yes = (old.yes == new_path[i+1]);
    if ((yes && old.implies(e)) || (!yes && old.not_implies(e)))
      goto no_dead;
  }
  no_ok = check_path(new_path, no_answer, e.no, interested, eventual, false,
		     yet || (ei == interested && e.no == eventual));

 no_dead:
  //fprintf(stderr, "      ");
  //for (int i=0; i<new_path.size(); i++) fprintf(stderr, " %d", new_path[i]);
  //fprintf(stderr, "%s -> \n", (yet?"*":""));
  
  if (ei == interested) {
    const Vector<int> &v = (e.yes == eventual ? yes_answer : no_answer);
    for (int i = 0; i < v.size(); i++)
      output.push_back(v[i]);
    return (e.yes == eventual ? yes_ok : no_ok);
    
  } else if (yes_ok && no_ok) {
    common_paths(yes_answer, no_answer, output);
    return true;
    
  } else if (!yes_ok && !no_ok)
    return false;
  
  else {
    const Vector<int> &v = (yes_ok ? yes_answer : no_answer);
    for (int i = 0; i < v.size(); i++)
      output.push_back(v[i]);
    return true;
  }
}

#endif /* CLASSIFIER_ITERATIVE */

int
Classifier::check_path(int ei, bool yes) const
{
  int next_ei = (yes ? _exprs[ei].yes : _exprs[ei].no);
  //fprintf(stderr, "%d.%s -> %d\n", ei, yes?"y":"n", next_ei);
  if (next_ei > 0) {
    Vector<int> x;
#if CLASSIFIER_ITERATIVE
    check_path_iterative(x, ei, next_ei);
#else
    check_path(Vector<int>(), x, 0, ei, next_ei, true, false);
#endif
    next_ei = (x.size() ? x.back() : FAILURE);
  }
  // next_ei = check_path(Vector<int>(), 0, ei, next_ei, true, false);
  //fprintf(stderr, "   -> %d\n", next_ei);
  return next_ei;
}

void
Classifier::drift_expr(int ei)
{
  Expr &e = _exprs[ei];
  // only do it once; repetitions without other changes to the dag would be
  // redundant
  e.yes = check_path(ei, true);
  e.no = check_path(ei, false);
  //{ String sxxx = program_string(this, 0); click_chatter("%s", sxxx.cc()); }
}
#endif

#if 0
void
Classifier::sort_and_expr_subtree(int from, int success, int failure)
{
  // This function checks the last subtree in _exprs, from `from' to the end
  // of _exprs, to see if it is an AND subtree. Such a subtree can be divided
  // into N sections, where all links inside each section K satisfy the
  // following properties:
  //
  // -- Each "yes" link either remains within section K, or jumps to the
  //    beginning of section K + 1, or (if there is no section K + 1) jumps
  //    to `success'.
  // -- Each "no" link either remains within section K or jumps to `failure'.
  //
  // The sections within such a subtree can be arbitrarily reordered without
  // affecting the subtree's semantics. This function finds such subtrees and
  // sorts them by offset of the first expr in each section. (Thus, the offset
  // of the first expr in section 0 <= the offset of the first expr in section
  // 1, and so forth.) This improves the action of later optimizations.
  
  int nexprs = _exprs.size();
  // 'id' identifies section equivalence classes: if id[i] == id[j], then i
  // and j are in the same section
  Vector<int> id(nexprs, 0);
  for (int i = from; i < nexprs; i++)
    id[i] = i;

  // determine equivalence classes (the sections)
  bool changed;
  do {
    changed = false;
    for (int i = from; i < nexprs; i++) {
      const Expr &e = _exprs[i];
      if (e.no != failure && e.no > 0 && id[i] != id[e.no]) {
	for (int j = i + 1; j <= e.no; j++)
	  id[j] = id[i];
	changed = true;
      } else if (e.yes > 0 && id[i] != id[e.yes - 1]) {
	for (int j = i + 1; j < e.yes; j++)
	  id[j] = id[i];
	changed = true;
      } else if ((e.no <= 0 && e.no != failure) || (e.yes <= 0 && e.yes != success))
	return;
    }
  } while (changed);

  // check for bad branches that would invalidate the transformation
  for (int i = from; id[i] < id.back(); i++) {
    const Expr &e = _exprs[i];
    if (e.yes == success)
      return;
  }
  
  //{ StringAccum sa;
  //sa << success << " -- " << failure << "\n";
  //for (int i = from; i < nexprs; i++) {
  //  sa << (i < 10 ? ">> " : ">>") << i << " [" << (id[i] < 10 ? " " : "") << id[i] << "] " << _exprs[i] << "\n";
  //}
  //click_chatter("%s", sa.cc()); }

  // extract equivalence classes from 'id' array
  Vector<int> equiv_classes;
  for (int i = from, c = -1; i < nexprs; i++)
    if (id[i] != c) {
      equiv_classes.push_back(i);
      c = id[i];
    }
  if (equiv_classes.size() <= 1)
    return;

  // sort equivalence classes
  bool sorted = true;
  Vector<int> sort_equiv_class(equiv_classes.size(), 0);
  for (int i = 0; i < equiv_classes.size(); i++) {
    int c = equiv_classes[i];
    int j = 0;
    for (; j < i
	   && _exprs[sort_equiv_class[j]].offset <= _exprs[c].offset; j++)
      /* nada */;
    if (j == i)
      sort_equiv_class[i] = c;
    else {
      memmove(&sort_equiv_class[j+1], &sort_equiv_class[j], (i - j) * sizeof(int));
      sort_equiv_class[j] = c;
      sorted = false;
    }
  }

  // return early if already sorted
  if (sorted)
    return;

  // sort the actual exprs
  equiv_classes.push_back(nexprs);
  Vector<Expr> newe;
  for (int i = 0; i < sort_equiv_class.size(); i++) {
    int c = sort_equiv_class[i];
    int new_c = from + newe.size();
    int classno;
    for (classno = 0; equiv_classes[classno] != c; classno++) ;
    int next = (classno == equiv_classes.size() - 2 ? success : equiv_classes[classno+1]);
    int new_next = (i == sort_equiv_class.size() - 1 ? success : new_c + equiv_classes[classno+1] - c);
    for (int j = c; j < nexprs && id[j] == c; j++) {
      Expr e = _exprs[j];
      if (e.yes == next)
	e.yes = new_next;
      else if (e.yes > 0) {
	assert(e.yes >= c && (next <= 0 || e.yes < next));
	e.yes += new_c - c;
      }
      if (e.no > 0) {
	assert(e.no >= c && (next <= 0 || e.no < next));
	e.no += new_c - c;
      } else
	assert(e.no == failure);
      newe.push_back(e);
    }
  }

  memcpy(&_exprs[from], &newe[0], newe.size() * sizeof(Expr));
  
  //{ StringAccum sa;
  //for (int i = from; i < nexprs; i++) {
  //  sa << (i < 10 ? " " : "") << i << " " << _exprs[i] << "\n";
  //}
  //click_chatter("%s", sa.cc()); }
}
#endif


ELEMENT_REQUIRES(AlignmentInfo)
EXPORT_ELEMENT(Classifier)
ELEMENT_MT_SAFE(Classifier)

// generate Vector template instance
#include <click/vector.cc>
#if EXPLICIT_TEMPLATE_INSTANCES
template class Vector<Classifier::Expr>;
#endif
CLICK_ENDDECLS