#include <Inventor/SoInput.h>
#include <Inventor/SoOutput.h>
#include <Inventor/fields/SoField.h>
#include <Inventor/misc/SoChildList.h>
#include <Inventor/errors/SoReadError.h>
#include <string.h> // for memcpy
#include <Inventor/C/tidbits.h> // coin_getenv

#include <Inventor/cve/SbTransactionP.h>
#include <Inventor/cve/SbTransaction.h>
#include <Inventor/cve/SbNetBasicP.h>



static int debugTransactions = -1;

int cve_debugTransactions()
{
  if (debugTransactions != -1)
    return debugTransactions;

  const char *val = coin_getenv("CVE_DEBUG_TRANSACTIONS");
  debugTransactions = val ? atoi(val) : 0;

  return debugTransactions;
}


void encodeBinaryData(SoOutput *out, void *data, size_t size)
{
  size_t size2 = size*2;
  uint8_t *data2 = (uint8_t*)malloc(size2+1);
  uint8_t *i = (uint8_t*)data;
  uint8_t *p = data2;
  uint8_t *e = data2 + size2;
  while (p < e) {
    uint8_t a = ((*i) & 0xf0) >> 4;
    uint8_t b = ((*i) & 0x0f);
    if (a<10)  a+='0';  else  a+='a'-10;
    if (b<10)  b+='0';  else  b+='a'-10;
    *(p++) = a;
    *(p++) = b;
    i++;
  }
  *p = 0;
  out->write((char*)data2);
  free(data2);
}


SbBool decodeBinaryData(SoInput  *in,  void *data, size_t size)
{
  SbString s;
  if (!in->read(s))  return FALSE;
  assert((size_t)s.getLength() == size*2);
  assert('A' < 'a');

  const uint8_t *i = (const uint8_t*)s.getString();
  const uint8_t *e = i + size*2;
  uint8_t *p = (uint8_t*)data;
  while (i < e) {
    uint8_t a = *(i++);
    uint8_t b = *(i++);
    if (a<='9')  a-='0';  else  a-= (a>='a' ? 'a' : 'A') - 10;
    if (b<='9')  b-='0';  else  b-= (b>='a' ? 'a' : 'A') - 10;
    *(p++) = a<<4 | b;
  }

  return TRUE;
}


void SbItemIdentification::write(SoOutput *out)
{
  out->write(connectionId);
  SO_OUTPUT_SPACE(out);
  SO_OUTPUT_SPACE(out);

  int len = path.getLength();
  out->write(len);
  
  if (len>0) // better formating
    SO_OUTPUT_SPACE(out);

  for (int i=0; i<len; i++) {
    SO_OUTPUT_SPACE(out);
    out->write(path[i]);
  }

  SO_OUTPUT_SPACE(out);
  SO_OUTPUT_SPACE(out);
  out->write(fieldIndex);
}


static int validatePath(SoFieldContainer *root, const SbIntList &path, SoField *f)
{
  SoFieldContainer *fc = root;
  int i,c=path.getLength();
  for (i=0; i<c; i++) {
    int index = path[i];
    assert(fc->getTypeId().isDerivedFrom(SoNode::getClassTypeId()) && "Looking for a non-existing"
              " child of container that is not a node. Only nodes are allowed to have children.");
    SoChildList *children = ((SoNode*)fc)->getChildren();
    assert(children && "The node has no children.");
    assert(index>=0 && index<=children->getLength() && "Invalid child index.");
    fc = children->operator[](index);
  }
  assert(fc==f->getContainer() && "Containers differ. Wrong path.");
  return fc->getFieldData()->getIndex(fc, f);
}


void SbItemIdentification::set(SbTransaction *t, 
                               SoFieldContainer *root, const SbIntList &path, SoField *f)
{
  if (root == NULL) {
    
    // If root is NULL, connectionId is stored in this field (in cveStorage->connectionId).
    // If cveStorage is NULL, item->itemId.connectionId is set to 0 (0 = invalid connection).
    
    // get cve storage
    SoCveStorage *cveStorage = f->getCveStorage();

    // connectionId from cveStorage
    if (cveStorage)
      connectionId = cveStorage->connectionId;
    else
      connectionId = 0;
  
    // path
    this->path.truncate(0);

    // field index
    fieldIndex = -1;

  } else {

    // if root is non-NULL, connectionId must be stored in node specified by root

    // connectionId from root
    this->connectionId = t->getDistributionGroup()->pointer2con(root);
    assert(this->connectionId != 0 && "Root is not connected. Use SoDistributionGroup::appendToDict() first.");

    // path
    this->path = path;

    // field index
    SoFieldContainer *fc = f->getContainer();
    fieldIndex = fc->getFieldData()->getIndex(fc, f);

    // verify that the path is correct
    assert(validatePath(root, path, f) == fieldIndex &&
           "SbItemIdentification::set parameter path is not valid.");
  }
}


SoFieldContainer* SbItemIdentification::getContainer(SoDistributionGroup *dg) const
{
  void *p = dg->con2pointer(connectionId);
  assert(p != NULL && "The connectionId has not assigned its object.");
  
  return getContainer(p);
}


SoFieldContainer* SbItemIdentification::getContainer(void *root) const
{
  assert(!pointsDirectlyToAField() && "Wrong function usage.");
  
  SoFieldContainer *c = (SoFieldContainer*)root;
  int j,l;
  l = path.getLength();
  for (j=0; j<l; j++) {
    int k = path[j];
    assert(c->isOfType(SoGroup::getClassTypeId()) && "Wrong path.");
    assert(k >= 0 && k < ((SoGroup*)c)->getNumChildren() && "Wrong child index.");
    c = ((SoGroup*)c)->getChild(k);
  }
  
  return c;
}


SoField* SbItemIdentification::getField(SoDistributionGroup *dg) const
{
  void *p = dg->con2pointer(connectionId);
  assert(p != NULL && "The connectionId has not assigned its object.");
  
  if (pointsDirectlyToAField())
    return (SoField*)p;
  else {
    SoFieldContainer *c = getContainer(p);
    return c->getFieldData()->getField(c, fieldIndex);
  }
}


SbBool SbItemIdentification::read(SoInput *in)
{
  int i,len,v;
  if (!in->read(connectionId) ||
      !in->read(len)) goto error;
  path = SbIntList(len);
  for (i=0; i<len; i++) {
    if (!in->read(v)) goto error;
    path.append(v);
  }
  if (!in->read(fieldIndex)) goto error;
  return TRUE;

error:
  SoReadError::post(in, "Couldn't not read ItemIdentification.");
  return FALSE;
}


void SbReadSetItem::write(SoOutput *out, SoDistributionGroup *dg)
{
  itemId.write(out);
  SO_OUTPUT_LN(out);
  timeStamp.write(out,dg);
}


SbBool SbReadSetItem::read(SoInput *in, SoDistributionGroup *dg, SbTransaction *t)
{
  // read itemId and timeStamp
  if (!itemId.read(in) ||
      !timeStamp.read(in, dg))
    return FALSE;
  
  // set field and transaction
  field = itemId.getField(dg);
  transaction = t;
    
  return TRUE;
}


SbBool SbReadSetItem::updateCommitPredictor()
{
  SoCveStorage *storage = field->getCveStorage();
  assert(storage && "CveStorage is not allocated.");

  SbBool oldPredictor = flags.commitPredictor;

  int wsiIndex = storage->getWriteSetItemIndex(timeStamp);
  // wsiIndex can be lower than zero (see SoCveStorage::SearchResult) for the following reasons:
  // NOT_ARRIVED - The transaction, to whose wsi should belong, does not arrive yet.
  //               This can be avoided by implementation of vector timestamps, if it turns to be necessary.
  //               For now, it is look like it is ok, and we should rely on optimistic presumption
  //               that most of the transactions will be commited.
  //               This state can be detected by: computerLargestTimeStamp < requestedTS.
  // ABORTED - The transaction was aborted.
  //           This means that "our" transaction CAN NOT be commited.
  //           Detection: computerLargestTimeStamp >= requestedTS && transaction is not there.
  // OVERWRITTEN - The transaction was commited and another commit already overwritten its value.
  //               This means that "our" transaction CAN NOT be commited.
  //               Detection: commitTS > requestedTS.
  // COMMITTED - correct value indicating that the value is in committed state just now.

#if CVE_DEBUG
  if (cve_debugTransactions() >= 3) {
    printf("Tra %s 2 READing   (", transaction->getTimeStamp().getString().getString());
    printf("ts: %s, wsiIndex: %s).\n", timeStamp.getString().getString(),
           SoCveStorage::searchResult2string(wsiIndex));
    printf("WriteList during reading: (");
    for (int i=0; i<storage->writeList.getLength(); i++) {
      if (i!=0)  printf(", ");
      printf("%s", storage->writeList[i]->getTransaction()->getTimeStamp().getString().getString());
    }
    printf(").\n");
  }
#endif

  //
  // The purpose of the following code is to set flags.writeArrived and flags.commitPredictor.
  // - OVERWRITTEN and ABORT sets flags.writeArrived to TRUE and flags.commitPredictor to FALSE
  // - values >= 0           sets flags.writeArrived to TRUE and if writeTransactionCP is FALSE sets flags.commitPredictor to FALSE
  // all other cases: COMMITTED, NOT_ARRIVED, and values >= 0 with writeTransactionCP set to TRUE
  // are handled by testing all writes "between" to test against their CP to TRUE:
  // - if transaction with CP set to TRUE exists, flags.commitPredictor is set to FALSE
  // - if no such transaction exists, set flags.commitPredictor to TRUE
  //

  if (wsiIndex < 0) {

    // special handling of negative indexes

    switch (wsiIndex) {
    case SoCveStorage::COMMITTED:   flags.writeArrived = TRUE;  break;
    case SoCveStorage::OVERWRITTEN: flags.writeArrived = TRUE;  flags.commitPredictor = FALSE; return oldPredictor != flags.commitPredictor;
    case SoCveStorage::ABORTED:     flags.writeArrived = TRUE;  flags.commitPredictor = FALSE; return oldPredictor != flags.commitPredictor;
    case SoCveStorage::NOT_ARRIVED: flags.writeArrived = FALSE; break;
    default: assert(0); break;
    }

    // following algorithms requires wsiIndex pointing before the first item
    // or "before" NOT_ARRIVED item
    if (wsiIndex == SoCveStorage::NOT_ARRIVED)
      wsiIndex = storage->getSmallerWriteSetItemIndex(timeStamp);

    if (wsiIndex < -1)
      wsiIndex = -1;

  } else {

    // handlind of positive indexes

    flags.writeArrived = TRUE;

    // check read set refered write transaction predictor to be TRUE
    if (storage->writeList[wsiIndex]->getTransaction()->getCommitPredictor() != TRUE) {
      flags.commitPredictor = FALSE;
      return oldPredictor != flags.commitPredictor;
    }
  }
  
  // verify all following writes with lower TS than our to have predictor set to FALSE
  const int c = storage->writeList.getLength();
  while (TRUE) {
    ++wsiIndex;

    // stop on the end of list and left the loop
    if (wsiIndex >= c) {
      flags.commitPredictor = TRUE; // set CP to TRUE since there is no transaction between with CP set to TRUE
      return oldPredictor != flags.commitPredictor;
    }

    // stop on the transaction with larger timeStamp
    SbTransaction *t = storage->writeList[wsiIndex]->getTransaction();
    if (t->getTimeStamp() >= transaction->getTimeStamp()) { // note: comparing to equal is neccessary to catch "self" here
      flags.commitPredictor = TRUE;
      return oldPredictor != flags.commitPredictor;
    }

    // stop on TRUE predictor
    if (t->getCommitPredictor() == TRUE) {
      flags.commitPredictor = FALSE;
      return oldPredictor != flags.commitPredictor;
    }
  }
}


void SbReadSetItem::propagateCommitPredictor()
{
  // recalculate commitPredictor of readSetItem's transaction;
  // if the predictor changed its value, propagate it.

  transaction->notifyReadSetCommitPredictorChanged(flags.commitPredictor);
}


void SbWriteSetItem::set(SbTransaction *t, SoFieldContainer *root, const SbIntList &path, SoField *f)
{
  field = f;
  transaction = t;
  itemId.set(t,root,path,f);
}


void SbWriteSetItem::write(SoOutput *out)
{
  itemId.write(out);
  SO_OUTPUT_LN(out);
  field->cveWriteValue(out, this);
}


SbWriteSetItem* SbWriteSetItem::read(SoInput *in, SoDistributionGroup *dg, SbTransaction *t)
{
  SbItemIdentification ii;
  SoField *f;
  SbWriteSetItem *wi;
  
  // read SbItemIdentification and find out the pointer to the field
  if (!ii.read(in)) goto error;
  f = ii.getField(dg);
  
  // create SbWriteSetItem and read its value
  wi = f->cveCreateWriteSetItem();
  if (!f->cveReadValue(in, wi)) {
    delete wi;
    goto error;
  }
  
  // set items
  wi->field = f;
  wi->transaction = t;
  wi->itemId = ii;
  
  return wi;

error:
  SoReadError::post(in, "Couldn't read WriteSetItem.");
  return NULL;
}


struct SbPropagRec {
  SoCveStorage *storage;
  SbList<SbReadSetItem*> pendingReads;
  //int currentRsiIndex; // points on a first read on which the propagation has not been applied
  int currentWsiIndex; // points on a write that will stop commitPredictor propagation
                       // (if nextPropagateCommitPredictor has not been called yet)
                       // or points on the write that stopped the propagation
                       // (if nextPropagateCommitPredictor has been called)
  SoField *field;
  const SbTimeStamp *stopTimeStamp; // timeStamp of write pointed by currentWsiIndex 
  
  void updateStopTimeStamp() {
    stopTimeStamp = &storage->writeList[currentWsiIndex]->getTransaction()->getTimeStamp();
  }
  ~SbPropagRec() {
    assert(pendingReads.getLength() == 0 && "SbPropagRec::pendingReads is not empty.");
  }
};


void SbWriteSetItem::propagateCommitPredictor(SbTransaction *t)
{
  // Go through the list of writeSetItems and for each item:
  // - interate through the list of readSetItems of the write item
  //   starting at first read with larger timeStamp than this write
  //   and stopping at the last read with smaller timeStamp than 
  //   any following write at this item with commit predictor set to TRUE;
  //   (Note: Special care must be taken about changing predictors of 
  //   transactions that are changing during the propagation. This
  //   is important, because commitPredictors determines the length
  //   of write notification propagation.)
  //
  //   - if read predictor of readSetItem is:
  //     - same: do nothing
  //     - differs: 
  //       - set it to the new value
  //       - recalculate commitPredictor of readSetItem's transaction;
  //         if the predictor changed its value, propagate it.

  const SbBool commitPredictor = t->getCommitPredictor();

  const SbWriteSetItemList &trWriteList = t->getWriteSetItems();
  SbList<SbPropagRec*> recList;
  int l = 0;

  const int c = trWriteList.getLength();
  int i,j;
  for (i=0; i<c; i++) {
    SbPropagRec *rec = trWriteList[i]->startPropagateCommitPredictor(commitPredictor, t);

    // if propagation finished immediatelly, continue with next writeSetItem
    if (rec == NULL)
      continue;

    // make ordered list of propagationRecords
    for (j=l-1; j>=0; j--)
      if (rec->stopTimeStamp <= recList[j]->stopTimeStamp)
        break;
    recList.insert(rec, j+1);
    l++;
  }

  while ((l=recList.getLength()) > 0) {
    SbPropagRec *rec = recList.pop();
    
    // tr is got from the field's list of transactionWrites.
    // tr timestamp is greater than the one of initiating transaction.
    assert(rec->currentWsiIndex >= 0);
    SbTransaction *tr = rec->storage->writeList[rec->currentWsiIndex]->getTransaction();

    if (tr->getCommitPredictor() == TRUE) {
      
      // remove all remaining pending reads (their transactions should be aborted because
      // of tr that is going to make their readset invalid)
      rec->pendingReads.truncate(0);

      // finish propagation on this dataItem
      delete rec;
    
    } else {
      
      // move to the next writeSetItem
      rec->currentWsiIndex++;
      if (rec->currentWsiIndex == rec->storage->writeList.getLength())
        rec->currentWsiIndex = -1;
      else
        rec->updateStopTimeStamp();

      // propagate through readSetItems
      doPropagateCommitPredictor(rec, commitPredictor, t);

      // check whether we reached the end of writeList
      if (rec->currentWsiIndex < 0) {
        delete rec;
        continue;
      } else {

        // put again into the recList
        for (j=l-1; j>=0; j--)
          if (rec->stopTimeStamp <= recList[j]->stopTimeStamp)
            break;
        recList.insert(rec, j+1);
      }
    }
  }
}


SbPropagRec* SbWriteSetItem::startPropagateCommitPredictor(SbBool commitPredictor, SbTransaction *t)
{
  SoCveStorage *storage = field->getCveStorage();
  assert(storage && "CveStorage is not allocated.");

  // find out index of following write
  // - look through fieldStorage->writeList for this and increase it by one
  // - if this is not found in the list, return -1. It means, this write is the last write.
  int c = storage->writeList.getLength() - 1;
  int i = c;
  for (; i>=0; i--)
    if (storage->writeList[i] == this) {
      if (i != c)
        i++;
      else
        i = -1;
      goto found;
    }
  assert(0 && "SbWriteSetItem not found in the field.");
found:

  // create new record used during the propagation
  SbPropagRec *rec = new SbPropagRec;
  rec->storage = storage;
  rec->currentWsiIndex = i;
  rec->field = field;
  if (rec->currentWsiIndex >= 0) // if we are not at the end of writes, update stopTimeStamp
    rec->updateStopTimeStamp();

  // create pendingReads
  // put all readSetItems whose
  // - transaction's timestamp is greater than "ourTransaction"
  // - read's timestamps are lower or equal to "ourTransaction"
  const SbTimeStamp &ts = t->getTimeStamp();
  c = storage->readList.getLength();
  for(i=0; i<c; i++) {
    SbReadSetItem *rsi = storage->readList[i];
    if (rsi->timeStamp <= ts && // equal must be here since it includes transactions reading this transaction
        rsi->transaction->getTimeStamp() > ts) // equal must not be here to not include this transaction
      rec->pendingReads.append(rsi);
  }
  
  // propagate to the immediate reads (reads before the first write on the dataItems)
  doPropagateCommitPredictor(rec, commitPredictor, t);

  if (rec->currentWsiIndex < 0) { // if we reached the end of writes, finish work
    delete rec;
    return NULL;
  }

  return rec;
}


// Returns FALSE if propagation has finished.
void SbWriteSetItem::doPropagateCommitPredictor(SbPropagRec* rec, SbBool commitPredictor, SbTransaction *t)
{
  int c = rec->pendingReads.getLength();
  const SbTimeStamp &thisTS = t->getTimeStamp();
  int i;

  // "stop writeSetItem" is present in the current field
  for (i=0; i<c; i++) {
    SbReadSetItem *ri = rec->pendingReads[i];
    if (rec->currentWsiIndex < 0 || // <0 means there is not any stop writeSetItem in the current field
        ri->transaction->getTimeStamp() <= *rec->stopTimeStamp) { // this condition makes it stop on following write
      
#if CVE_DEBUG
      if (cve_debugTransactions() >= 3) {
        printf("Tra %s 2 PROPAG_TO (", t->getTimeStamp().getString().getString());
        printf("%s", ri->transaction->getTimeStamp().getString().getString());
        printf(").\n");
      }
#endif
      
      // "positive" propagation - the SbReadSetItem reads what this transaction writes
      if (ri->timeStamp == thisTS) {

        // update readSetComplete
        if (ri->flags.writeArrived == FALSE) {
          ri->flags.writeArrived = TRUE;
          ri->transaction->notifyReadSetWriteArrived();
        }

        // update commitPredictor
        if (ri->flags.commitPredictor != commitPredictor) {
          ri->flags.commitPredictor = commitPredictor;
          ri->propagateCommitPredictor();
        }

      // "negative" propagation
      } else {
        if (ri->updateCommitPredictor())
          ri->propagateCommitPredictor();
      }

      // remove from pendingReads
      rec->pendingReads.removeFast(i);
      i--; c--;
    }
  }
}

  
SoCveStorage::SoCveStorage() : connectionId(0), committedValue(NULL), commitTime(SbTimeStamp::zero())
{
}


SoCveStorage::~SoCveStorage() 
{
  assert(connectionId == 0);
#if !CVE_DEBUG // debugging code; useful when it happens that something remained in the cveStorage
  assert(readList.getLength() == 0);
#else
  if (readList.getLength() != 0) {
    SbReadSetItem *rsi = readList[0];
    printf("TraLast: %i strange read found:  ", readList.getLength());
    printf("referencing to: %s,  ", rsi->timeStamp.getString().getString());
    SbTransaction *t = rsi->transaction;
    t->assertAlive();
    printf("Tra: %p, %s state:%i=%s", t, t->getTimeStamp().getString().getString(),
      t->getState(), t->getState()==SbTransaction::CONSTRUCTING ? "CONSTRUCTING" : (t->getState()==SbTransaction::SCHEDULED ? "SCHEDULED" : "OTHER"));
    printf(").\n");
    flushall();
  }
#endif
  assert(writeList.getLength() == 0);
  assert(unscheduledReads.getLength() == 0);
  assert(unscheduledWrites.getLength() == 0);
  delete committedValue; 
}


void SoCveStorage::orderlyAppendRead(SbReadSetItem *ri)
{
  // make sure transaction is SCHEDULED
  ri->transaction->assertState(SbTransaction::SCHEDULED,
      "Transaction belonging to ri parameter passed to SoCveStorage::orderlyAppendRead is invalid.");

  // Insert SbReadSetItem into the right place in readList.
  // Items are ordered by their transaction's timeStamps (not by read timeStamps).
  // Greater index means greater timestamp.
  int i,c;
  c = readList.getLength();
  const SbTimeStamp &ts = ri->transaction->getTimeStamp();
  for (i=0; i<c; i++)
    if (readList[i]->transaction->getTimeStamp() > ts)
      break;
  readList.insert(ri, i);
}


void SoCveStorage::orderlyAppendWrite(SbWriteSetItem *wi)
{
  // make sure transaction is SCHEDULED
  wi->getTransaction()->assertState(SbTransaction::SCHEDULED, 
      "Transaction belonging to wi parameter passed to SoCveStorage::orderlyAppendWrite is invalid.");

  // insert SbWriteSetItem into the right place in writeList,
  // gerater index means greater timestamp
  int i,c;
  c = writeList.getLength();
  for (i=0; i<c; i++) {
    if (writeList[i]->getTransaction()->getTimeStamp() > wi->getTransaction()->getTimeStamp())
      break;
  }
  writeList.insert(wi, i);
}


void SoCveStorage::abortAllTransactions()
{
  while (writeList.getLength())
    writeList[0]->getTransaction()->abort();

  while (readList.getLength())
    readList[0]->transaction->abort();

  // FIXME: unscheduledWrites and reads should be also invalidated. PCJohn 2005-06-14
}


static char sr2s[] = "0";
const char* SoCveStorage::searchResult2string(const int sr)
{
  if (sr >= 0) {
    // return numerical value
    if (sr >= 10)  sr2s[0] = 'x';
    else  sr2s[0] = '0' + sr;
    return &sr2s[0];
  } else {
    switch (sr) {
    case COMMITTED:   return "COMMITTED";
    case OVERWRITTEN: return "OVERWRITTEN";
    case ABORTED:     return "ABORTED";
    case NOT_ARRIVED: return "NOT_ARRIVED";
    default: assert(0); return "???";
    }
  }
}


int SoCveStorage::getWriteSetItemIndex(const SbTimeStamp &ts)
{
#if 0 // transaction execution debugging code
  {
  printf("getWriteSetItemIndex: commited: %s, ", commitTime.getString().getString());
    int c = writeList.getLength();
  int i;
  for (i=0; i<c; i++) {
    SbWriteSetItem *wi = writeList[i];
    const SbTimeStamp &ts = wi->getTransaction()->getTimeStamp();
    printf("(ts: %s),", ts.getString().getString());
  }
  printf("\n");
  }
#endif

  // ts is larger than largest x => transaction did not arrived yet
  if (ts.getComputer()->getLargestTimeStamp() < ts)
    return NOT_ARRIVED;

  // try to locate appropriate writeSetItem in the list
  const int c = writeList.getLength()-1;
  int i = c;
  for(; i>=0; i--) {
    SbWriteSetItem *wsi = writeList[i];
    const SbTimeStamp &x = wsi->getTransaction()->getTimeStamp();
    if (ts >= x) {
      if (ts == x)
        return i;
      else {
#if CVE_DEBUG
        if (cve_debugTransactions() >= 3)  printf(" Loop ABORT returned at %i. ", i);
#endif
        return ABORTED;
      }
    }
  }

  // try commited writeSetItem
  if (ts >= commitTime) {
    if (commitTime == ts)
      return COMMITTED;
    else
      return ABORTED;
  }

  // timeStamp is lower than commited time
  return OVERWRITTEN;
}


/** Returns index of readSetItem that is the first with larger timeStamp than ts.
 *  Please note: the readSetItems are not ordered by their timeStamps, 
 *  so following reads may have often lower timeStamps than one specified by parameter
 */
int SoCveStorage::getFirstLargerReadSetItemIndex(const SbTimeStamp &ts)
{
  assert(0 && "This function should not be used and shall be removed shortly.");
  // try to locate appropriate readSetItem in the list
  const int c = readList.getLength();
  int i;
  for(i=0; i<c; i++) {
    SbReadSetItem *rsi = readList[i];
    if (rsi->timeStamp > ts)
      return i;
  }

  // no such read was found
  return -1;
}


//! Returns index of writeSetItem that is the first with smaller timeStamp than ts.
int SoCveStorage::getSmallerWriteSetItemIndex(const SbTimeStamp &ts)
{
  // try to locate appropriate writeSetItem in the list
  const int c = writeList.getLength()-1;
  int i = c;
  for(; i>=0; i--) {
    SbWriteSetItem *wsi = writeList[i];
    const SbTimeStamp &x = wsi->getTransaction()->getTimeStamp();
    if (x < ts) {
      return i;
    }
  }

  // timeStamp is lower than any of reads (this is correct situation)
  return NOT_ARRIVED;
}
