Logo Search packages:      
Sourcecode: maria version File versions

BufferType.C

Go to the documentation of this file.
// Buffer type class -*- c++ -*-

#include "snprintf.h"

#ifdef __GNUC__
# pragma implementation
#endif // __GNUC__
#include "BufferType.h"
#include "BufferValue.h"
#include "Constraint.h"
#include "Printer.h"

#include <string.h>

/** @file BufferType.C
 * Variable-length queue or stack with maximum length
 */

/* Copyright © 1999-2002 Marko Mäkelä (msmakela@tcs.hut.fi).

   This file is part of MARIA, a reachability analyzer and model checker
   for high-level Petri nets.

   MARIA is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   MARIA is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   The GNU General Public License is often shipped with GNU software, and
   is generally kept in a file called COPYING or LICENSE.  If you do not
   have a copy of the license, write to the Free Software Foundation,
   59 Temple Place, Suite 330, Boston, MA 02111 USA. */

00039 BufferType::BufferType (const class Type& itemType, card_t size,
                  bool stack) :
  Type (),
  myItemType (&itemType), mySize (size), myStack (stack)
{
  assert (myItemType && size);
  if (!myItemType->isOrdered ()) flagUnordered ();
}

00048 BufferType::BufferType (const class BufferType& old) :
  Type (old),
  myItemType (old.myItemType), mySize (old.mySize),
  myStack (old.myStack)
{
}

00055 BufferType::~BufferType ()
{
}

class Value&
00060 BufferType::getFirstValue () const
{
  if (myConstraint)
    return *myConstraint->getFirstValue ().copy ();
  return *new class BufferValue (*this);
}

class Value&
00068 BufferType::getLastValue () const
{
  if (myConstraint)
    return *myConstraint->getLastValue ().copy ();
  else {
    class BufferValue& w = *new class BufferValue (*this);
    w.top ();
    return w;
  }
}

bool
00080 BufferType::isAssignable (const class Type& type) const
{
  if (&type == this)
    return true;

  if (type.getKind () != getKind ())
    return Type::isAssignable (type);

  const class BufferType& v = static_cast<const class BufferType&>(type);

  return
    myItemType->isAssignable (*v.myItemType);
}

bool
00095 BufferType::isAlwaysAssignable (const class Type& type) const
{
  if (&type == this)
    return true;

  if (type.getKind () != getKind ())
    return false;

  const class BufferType& v = static_cast<const class BufferType&>(type);

  return
    mySize == v.mySize &&
    myItemType->isAlwaysAssignable (*v.myItemType);
}

bool
00111 BufferType::isConstrained (const class Value& value) const
{
  assert (value.getType ().isAssignable (*this));
  const class BufferValue& b = static_cast<const class BufferValue&>(value);

  for (card_t i = 0; i < getSize () && b[i]; i++)
    if (!myItemType->isConstrained (*b[i]))
      return false;

  return Type::isConstrained (value);
}

card_t
00124 BufferType::do_getNumValues () const
{
  assert (!myConstraint);
  card_t numValues = 1;
  const card_t numItemValues = myItemType->getNumValues ();

  if (numItemValues == CARD_T_MAX)
    return CARD_T_MAX;

  for (card_t i = 1; i <= mySize; i++) {
    card_t product = 1;
    for (card_t j = 0; j < i; j++) {
      if (numItemValues < CARD_T_MAX / product)
      product *= numItemValues;
      else
      return CARD_T_MAX;
    }
    if (product < CARD_T_MAX - numValues)
      numValues += product;
    else
      return CARD_T_MAX;
  }

  return numValues;
}

card_t
00151 BufferType::convert (const class Value& value) const
{
  assert (value.getKind () == Value::vBuffer);
  assert (isConstrained (value));
  assert (getNumValues () < CARD_T_MAX);
  if (myConstraint)
    return Type::convert (value);

  card_t number = 0;
  const class BufferValue& v = static_cast<const class BufferValue&>(value);

  card_t numItemValues = myItemType->getNumValues ();
  card_t offset = 0, i = 0;
  for (card_t mult = 1; i < mySize && v[i]; mult *= numItemValues, i++)
    offset += mult;

  while (i--)
    (number *= numItemValues) += myItemType->convert (*v[i]);

  number += offset;
  assert (number < getNumValues ());
  return number;
}

class Value*
00176 BufferType::convert (card_t number) const
{
  assert (number < getNumValues ());
  assert (getNumValues () < CARD_T_MAX);

  if (myConstraint)
    return Type::convert (number);
  class BufferValue* value = new class BufferValue (*this);
  if (!number)
    return value;

  card_t numItemValues = myItemType->getNumValues ();
  card_t size = 0;
  for (card_t mult = 1; number >= mult; size++, mult *= numItemValues)
    number -= mult;

  for (card_t i = 0; i < size; i++) {
    card_t num = number % numItemValues;
    number /= numItemValues;

    (*value)[i] = myItemType->convert (num);
  }

  assert (isConstrained (*value));
  return value;
}

#ifdef EXPR_COMPILE
# include "CExpression.h"
# include "util.h"
# include <stdio.h>

void
BufferType::compile (class StringBuffer& out)
{
  const_cast<class Type*>(myItemType)->compile (out);
  Type::compile (out);
}

void
BufferType::compileDefinition (class StringBuffer& out,
                         unsigned indent) const
{
  out.indent (indent), out.append ("struct {\n");
  out.indent (indent + 2), out.append ("unsigned s;\n");
  out.indent (indent + 2), myItemType->appendName (out);
  out.append (" a[");
  out.append (mySize);
  out.append ("];\n");
  out.indent (indent), out.append ("}");
}

void
BufferType::compileExtraDefinitions (class StringBuffer& out,
                             unsigned indent,
                             bool interface) const
{
  if (getNumValues () < CARD_T_MAX) {
    // offsets for value<->number conversions
    out.indent (indent);
    if (interface) out.append ("extern ");
    out.append ("const card_t o"), appendIndex (out);
    out.append ("[]");
    if (!interface) {
      out.append (" = { 0");
      card_t numItemValues = myItemType->getNumValues ();
      card_t offset = 0, i = 0;
      for (card_t mult = 1; i < mySize; mult *= numItemValues, i++) {
      offset += mult;
      out.append (", "), out.append (offset);
      }
      out.append (" }");
    }
    out.append (";\n");
  }
  Type::compileExtraDefinitions (out, indent, interface);
}

bool
BufferType::compileEqual (class StringBuffer& out,
                    unsigned indent,
                    const char* left,
                    const char* right,
                    bool equal,
                    bool first,
                    bool last,
                    bool backslash) const
{
  size_t llen = strlen (left), rlen = strlen (right);
  char* l = new char[llen + 25];
  char* r = new char[rlen + 25];
  memcpy (l, left, llen);
  memcpy (r, right, rlen);

  if (!first)
    out.indent (indent);
  out.append (left), out.append (".s");
  out.append (equal ? "==" : "!=");
  out.append (right), out.append (".s");
  if (myItemType->getNumValues () != 1) {
    out.append (backslash
            ? (equal ? "&&\\\n" : "||\\\n")
            : (equal ? "&&\n" : "||\n"));

    for (card_t i = getSize (); i--; ) {
      out.indent (indent);
      out.append ("(");
      out.append (left), out.append (".s");
      out.append (equal ? "<=" : ">");
      out.append (i);
      out.append (backslash
              ? (equal ? "||\\\n" : "&&\\\n")
              : (equal ? "||\n" : "&&\n"));
      out.indent (indent + 1);
      out.append ("(");

      snprintf (l + llen, 25, ".a[%u]", i);
      snprintf (r + rlen, 25, ".a[%u]", i);
      if (!myItemType->compileEqual (out, indent + 2, l, r,
                             equal, true, true, backslash))
      out.append (equal ? "1" : "0");
      out.append ("))");
      if (i || !last)
      out.append (backslash
                ? (equal ? "&&\\\n" : "||\\\n")
                : (equal ? "&&\n" : "||\n"));
    }
  }
  else if (!last)
    out.append (backslash
            ? (equal ? "&&\\\n" : "||\\\n")
            : (equal ? "&&\n" : "||\n"));

  delete[] l; delete[] r;
  return true;
}

void
BufferType::compileCompare3 (class StringBuffer& out,
                       const char* condition,
                       const char* component) const
{
  const size_t len = strlen (component);
  char* const newcomp = new char[len + 25];
  char* const offset = newcomp + len;
  memcpy (newcomp, component, len);
  memcpy (offset, ".s", 3);
  compileLeafCompare3 (out, condition, newcomp);

  const size_t condlen = condition ? strlen (condition) : 0;
  char* const newcond = new char[condlen ? len + condlen + 27 : len + 25];
  char* const coffset = condlen
    ? newcond + condlen + len + 3
    : newcond + len + 1;
  if (condlen) {
    memcpy (newcond, condition, condlen);
    memcpy (newcond + condlen, "&&l", 3);
  }
  else
    *newcond = 'l';

  memcpy (&newcond[condlen ? condlen + 3 : 1], component, len);

  for (card_t i = mySize; i--; ) {
    snprintf (coffset, 24, ".s>%u", i);
    snprintf (offset, 25, ".a[%u]", i);
    myItemType->compileCompare3 (out, newcond, newcomp);
  }
  delete[] newcond;
  delete[] newcomp;
}

void
BufferType::do_compileSuccessor (class StringBuffer& out,
                         unsigned indent,
                         const char* lvalue,
                         const char* rvalue,
                         const char* wrap) const
{
  size_t llen = strlen (lvalue), rlen = strlen (rvalue);
  char* lval = new char[llen + 25];
  char* rval = new char[rlen + 25];
  memcpy (lval, lvalue, llen);
  memcpy (rval, rvalue, rlen);
  memcpy (lval + llen, ".a[0]", 6);

  out.indent (indent);
  out.append ("do {\n");
  if (!wrap) {
    wrap = "wrap";
    out.indent (indent + 2);
    out.append ("bool_t ");
    out.append (wrap);
    out.append ("=0;\n");
  }

  out.indent (indent + 2);
  out.append (lvalue), out.append (".s=");
  out.append (rvalue), out.append (".s;\n");

  for (card_t i = 0;; ) {
    snprintf (rval + rlen, 25, ".a[%u]", i);

    out.indent (indent + 2);
    out.append ("if ("), out.append (lvalue), out.append (".s==");
    out.append (i), out.append (") {\n");
    out.indent (indent + 4);
    out.append (lvalue), out.append (".s++;\n");
    snprintf (lval + llen, 25, ".a[%u]", i);
    myItemType->compileBottom (out, indent + 4, lval);
    out.indent (indent + 4);
    out.append ("continue;\n");
    out.indent (indent + 2);
    out.append ("}\n");

    myItemType->compileSuccessor (out, indent + 2, lval, rval, wrap);
    if (++i < mySize) {
      out.indent (indent + 2);
      out.append ("if (!");
      out.append (wrap);
      out.append (") {\n");
      if (lvalue != rvalue && strcmp (lvalue, rvalue)) {
      for (card_t j = i; j < getSize (); j++) {
        out.indent (indent + 4);
        out.append (lvalue);
        out.append (".a[");
        out.append (j);
        out.append ("]=");
        out.append (rvalue);
        out.append (".a[");
        out.append (j);
        out.append ("];\n");
      }
      }
      out.indent (indent + 4);
      out.append ("continue;\n");
      out.indent (indent + 2);
      out.append ("}\n");
      out.indent (indent + 2);
      out.append (wrap);
      out.append ("=0;\n");
    }
    else
      break;
  }

  out.indent (indent);
  out.append ("} while (0);\n");

  delete[] lval;
  delete[] rval;
}

void
BufferType::do_compilePredecessor (class StringBuffer& out,
                         unsigned indent,
                         const char* lvalue,
                         const char* rvalue,
                         const char* wrap) const
{
  size_t llen = strlen (lvalue), rlen = strlen (rvalue);
  char* lval = new char[llen + 25];
  char* rval = new char[rlen + 25];
  memcpy (lval, lvalue, llen);
  memcpy (rval, rvalue, rlen);

  out.indent (indent);
  out.append ("do {\n");
  if (!wrap) {
    wrap = "wrap";
    out.indent (indent + 2);
    out.append ("bool_t ");
    out.append (wrap);
    out.append ("=0;\n");
  }

  out.indent (indent + 2);
  out.append (lvalue), out.append (".s=");
  out.append (rvalue), out.append (".s;\n");

  for (card_t i = 0; i < mySize; i++) {
    snprintf (lval + llen, 25, ".a[%u]", i);
    snprintf (rval + rlen, 25, ".a[%u]", i);
    myItemType->compilePredecessor (out, indent + 2, lval, rval, wrap);
    out.indent (indent + 2);
    out.append ("if (!");
    out.append (wrap);
    out.append (") {\n");
    if (lvalue != rvalue && strcmp (lvalue, rvalue)) {
      for (card_t j = i + 1; j < getSize (); j++) {
      out.indent (indent + 4);
      out.append (lvalue);
      out.append (".a[");
      out.append (j);
      out.append ("]=");
      out.append (rvalue);
      out.append (".a[");
      out.append (j);
      out.append ("];\n");
      }
    }
    out.indent (indent + 4);
    out.append ("continue;\n");
    out.indent (indent + 2);
    out.append ("}\n");
    out.indent (indent + 2);
    out.append (wrap);
    out.append ("=0;\n");

    out.indent (indent + 2);
    out.append ("if (");
    out.append (lvalue);
    out.append (".s==");
    out.append (i + 1);
    out.append (") {\n");
    out.indent (indent + 4);
    out.append (lvalue);
    out.append (".s--;\n");
    out.indent (indent + 4);
    out.append ("continue;\n");
    out.indent (indent + 2);
    out.append ("}\n");
  }

  out.indent (indent);
  out.append ("} while (0);\n");

  delete[] lval;
  delete[] rval;
}

void
BufferType::compileCast (class CExpression& cexpr,
                   unsigned indent,
                   const class Type& target,
                   const char* lvalue,
                   const char* rvalue) const
{
  assert (isAssignable (target));
  if (target.getKind () != Type::tBuffer)
    Type::compileCast (cexpr, indent, target, lvalue, rvalue);
  else {
    class StringBuffer& out = cexpr.getOut ();
    const class BufferType& bt = static_cast<const class BufferType&>(target);
    out.indent (indent);
    out.append (lvalue);
    out.append (".s=");
    out.append (rvalue);
    out.append (".s;\n");
    card_t i = getSize ();
    if (i > bt.getSize ()) {
      i = bt.getSize ();
      out.indent (indent);
      out.append ("if (");
      out.append (lvalue);
      out.append (".s>");
      out.append (bt.getSize ());
      out.append (")\n");
      cexpr.compileError (indent + 2, errConst);
    }
    size_t llen = strlen (lvalue);
    size_t rlen = strlen (rvalue);
    char* lval = new char[llen + 25];
    char* rval = new char[llen + 25];
    memcpy (lval, lvalue, llen);
    memcpy (rval, rvalue, rlen);
    while (i--) {
      snprintf (lval + llen, 25, ".a[%u]", i);
      snprintf (rval + rlen, 25, ".a[%u]", i);
      myItemType->compileCast (cexpr, indent, *bt.myItemType, lval, rval);
    }
    delete[] lval;
    delete[] rval;
    if (const class Constraint* c = target.getConstraint ())
      c->compileCheck (cexpr, indent, lvalue);
  }
}

void
BufferType::do_compileConversion (class StringBuffer& out,
                          unsigned indent,
                          const char* value,
                          const char* number,
                          bool add) const
{
  card_t i = getSize ();
  assert (getNumValues () < CARD_T_MAX && i);
  size_t length = strlen (value);
  char* val = new char[length + 25];
  char* offset = val + length;
  memcpy (val, value, length);

  const char* num = number;
  if (add) {
    out.indent (indent), out.append ("{\n");
    out.indent (indent += 2), out.append ("card_t ");
    length = strlen (number);
    char* nbr = new char[length + 2];
    memcpy (nbr, number, length);
    memcpy (nbr + length, "_", 2);
    num = nbr;
    out.append (num), out.append ("=0;\n");
  }
  else
    out.indent (indent), out.append (num), out.append ("=0;\n");

  const card_t numValues = myItemType->getNumValues ();
  for (bool next = false; i--; next = true) {
    out.indent (indent);
    out.append ("if ("), out.append (value), out.append (".s");
    if (i)
      out.append (">"), out.append (i);
    out.append (") {\n");
    snprintf (offset, 25, ".a[%u]", i);
    myItemType->compileConversion (out, indent + 2, val, num, next);
    if (i) {
      out.indent (indent + 2), out.append (num), out.append ("*=");
      out.append (numValues), out.append (";\n");
    }
    out.indent (indent);
    out.append ("}\n");
  }

  out.indent (indent), out.append (num);
  out.append ("+=o"), appendIndex (out);
  out.append ("["), out.append (value), out.append (".s];\n");

  if (add) {
    out.indent (indent), out.append (number), out.append ("+=");
    out.append (num), out.append (";\n");
    out.indent (indent -= 2), out.append ("}\n");
    delete[] num;
  }

  delete[] val;
}

void
BufferType::compileReverseConversion (class StringBuffer& out,
                              unsigned indent,
                              const char* number,
                              const char* value) const
{
  if (myConstraint)
    Type::compileReverseConversion (out, indent, number, value);
  else if (getNumValues () == 1)
    compileBottom (out, indent, value);
  else {
    size_t length = strlen (value);
    char* val = new char[length + 25];
    char* offset = val + length;
    memcpy (val, value, length);

    out.indent (indent);
    out.append ("for ("), out.append (value);
    out.append (".s="), out.append (getSize ());
    out.append ("; ");
    out.append (number), out.append ("<o"), appendIndex (out);
    out.append ("["), out.append (value), out.append (".s]; ");
    out.append (value), out.append (".s--);\n");

    out.indent (indent);
    out.append (number), out.append ("-=o"), appendIndex (out);
    out.append ("["), out.append (value), out.append (".s];\n");

    length = strlen (number);
    char* num = new char[length + 2];
    memcpy (num, number, length);
    memcpy (num + length, "_", 2);

    out.indent (indent), out.append ("do {\n");
    out.indent (indent + 2);
    out.append ("card_t "), out.append (num), out.append (";\n");

    card_t numValues = myItemType->getNumValues ();
    for (card_t i = 0; i < getSize (); i++) {
      out.indent (indent + 2);
      out.append ("if ("), out.append (value), out.append (".s==");
      out.append (i), out.append (") continue;\n");
      snprintf (offset, 25, ".a[%u]", i);
      out.indent (indent + 2);
      out.append (num), out.append ("="), out.append (number);
      out.append ("%"), out.append (numValues);
      out.append (", ");
      out.append (number), out.append ("/=");
      out.append (numValues);
      out.append (";\n");
      myItemType->compileReverseConversion (out, indent + 2, num, val);
    }

    out.indent (indent), out.append ("} while (0);\n");
    delete[] num;
    delete[] val;
  }
}

void
BufferType::compileEncoder (class CExpression& cexpr,
                      unsigned indent,
                      const char* func,
                      const char* value) const
{
  if (getNumValues () < CARD_T_MAX)
    Type::compileEncoder (cexpr, indent, func, value);
  else {
    size_t length = strlen (value);
    char* val = new char[length + 6];
    memcpy (val, value, length);
    memcpy (val + length, ".a[i]", 6);

    class StringBuffer& out = cexpr.getOut ();
    out.indent (indent);
    out.append (func);
    out.append (" (");
    out.append (value), out.append (".s, ");
    out.append (log2 (getSize () + 1));
    out.append (");\n");

    out.indent (indent);
    out.append ("{\n");
    out.indent (indent + 2);
    out.append ("card_t i;\n");

    out.indent (indent + 2);
    out.append ("for (i=");
    out.append (value);
    out.append (".s; i--; ) {\n");

    myItemType->compileEncoder (cexpr, indent + 4, func, val);

    out.indent (indent + 2);
    out.append ("}\n");
    out.indent (indent);
    out.append ("}\n");

    delete[] val;
  }
}

void
BufferType::compileDecoder (class CExpression& cexpr,
                      unsigned indent,
                      const char* func,
                      const char* value) const
{
  if (getNumValues () < CARD_T_MAX)
    Type::compileDecoder (cexpr, indent, func, value);
  else {
    size_t length = strlen (value);
    char* val = new char[length + 6];
    memcpy (val, value, length);
    memcpy (val + length, ".a[i]", 6);

    class StringBuffer& out = cexpr.getOut ();
    out.indent (indent);
    out.append (value);
    out.append (".s = ");
    out.append (func);
    out.append (" (");
    out.append (log2 (getSize () + 1));
    out.append (");\n");

    out.indent (indent);
    out.append ("{\n");
    out.indent (indent + 2);
    out.append ("card_t i;\n");

    out.indent (indent + 2);
    out.append ("for (i=");
    out.append (value);
    out.append (".s; i--; ) {\n");

    myItemType->compileDecoder (cexpr, indent + 4, func, val);

    out.indent (indent + 2);
    out.append ("}\n");
    out.indent (indent);
    out.append ("}\n");

    delete[] val;
  }
}

#endif // EXPR_COMPILE

void
00762 BufferType::display (const class Printer& printer) const
{
  if (const char* name = myItemType->getName ())
    printer.print (name);
  else
    myItemType->display (printer);
  printer.delimiter ('[');
  printer.printRaw (myStack ? "stack" : "queue");
  printer.delimiter (' ');
  printer.print (mySize);
  printer.delimiter (']');

  if (myConstraint)
    myConstraint->display (printer);
}

Generated by  Doxygen 1.6.0   Back to index