#include "copyright.h"
/****************************************************************** 
 *
 * clusterclass.c --
 *
 *     Remember clusters of lines of data in such a way that,
 *     regardless of the order in which the lines are inserted,
 *     "full" clusters can be retrieved strictly in the order
 *     of the first timestamp of the first line.
 *
 *
 * Created: 15 July 1998
 * $Author: mstoufer $
 * $Source: /home/g2/src/projects/NetLogger/src/nlv/old/clusterclass.c,v $
 * $RCSfile: clusterclass.c,v $
 * $Revision: 1.1.1.1 $
 * $Locker:  $
 * $Date: 2000/12/05 19:52:33 $
 *
 ****************************************************************** 
 */
static char rcsid[] = "$Id: clusterclass.c,v 1.1.1.1 2000/12/05 19:52:33 mstoufer Exp $";

#include "clusterclass.h"

/*========= EXCEPTIONS ================================================*/

Except_T crNoSuchClient = { "No such client" };
Except_T crClusterFull  = { "Cannot add any more lines to cluster" };

/*========= DATA =====================================================*/

#define FILE_DBG -10 /* Level of debugging in this file (-1..-10) */

#define T Nlv_cr
struct T {
  clusterNode *clist[ NLV_MAX_CLIENTS ][2];
  clusterNode *qhead, *qtail; 
  double epsilon;
  int maxCluster;
};

#define FILE_ERR_CODE 600

/*========= FUNCTIONS =================================================*/

void         Nlv_crAddToCluster( T, clusterNode *ptr, Nlv_LData *d );
clusterNode *Nlv_crNewNode( T, int client, double t );
void         Nlv_crDump( T this );


/*
 *----------------------------------------------------------------------
 *
 * New -- Allocate a new object.
 *
 * Calls    : malloc
 *
 * Algorithm:
 *
 *        epsilon and maxCluster are set to unreasonable values,
 *        in an attempt to force the user to set them explicitly.
 *
 *----------------------------------------------------------------------
 */
T Nlv_crNew()
{
  T this;
  this = (struct Nlv_cr *)malloc( sizeof(struct Nlv_cr) );
  memset( (clusterNode *)(this->clist), 0, 2*NLV_MAX_CLIENTS*sizeof(clusterNode *));
  this->qhead = this->qtail = NULL;
  this->epsilon    = 0.0;
  this->maxCluster = 0;

  return this;
}

/*
 *----------------------------------------------------------------------
 *
 * AddData -- Put a vector of data into a cluster or, if it does not
 *            fall within an existing cluster, create a new cluster
 *            to hold it. The data is assumed to be malloc-ed by
 *            the caller, and is neither allocated nor freed at any
 *            point by cluster functions.
 *
 * Calls    : Nlv_crNewNode, Nlv_crAddtoCluster
 *
 * Algorithm:
 *
 *      Get ptr to client list.
 *      Starting at tail, look for cluster which should contain line.
 *      No such cluster? -> first create one.
 *      Cluster full? -> stop!
 *      Add line to cluster.
 *      If ( cluster is full ) mark it as full.
 *
 *----------------------------------------------------------------------
 */
void Nlv_crAddData( T this, int client, Nlv_LData *d )
{
  clusterNode *ptr;
  double t = d->times[0];

  if ( client < 0 || client >= NLV_MAX_CLIENTS ) {
    RAISE( crNoSuchClient );
  }
  for ( ptr = this->clist[client][1]; ptr; ptr = ptr->prevCl ) {
    if ( fabs( t - ptr->data.time ) < this->epsilon ) break;
  }
  if ( !ptr ) {
    ptr = Nlv_crNewNode( this, client, t );
    ptr->data.time = t;
  }
  else if ( ptr->isFull ) {
    RAISE( crClusterFull );
  }

  Nlv_crAddToCluster( this, ptr, d );
  if ( ptr->size > this->maxCluster )
    ptr->isFull = 1;
  return;
}


/*
 *----------------------------------------------------------------------
 *
 * NewNode -- Create and properly situate a new node, given the
 *            client index and the timestamp.
 *
 * Calls    : 
 *
 * Algorithm:
 *
 *      Get ptr to tail of client array.
 *      Allocate new structure and add to tail.
 *      Add to proper place in queue.
 *      Return ptr to structure.
 *
 *----------------------------------------------------------------------
 */
clusterNode *Nlv_crNewNode( T this, int client, double time )
{
  clusterNode *newPtr, *tailPtr, *headPtr;
  clusterNode *p, *q;
  Nlv_EInfo einfo;
  
  NLV_SET_EINFO( einfo, FILE_DBG, 0 );
  Nlv_errReport( eobj, &einfo, "Adding new cluster to queue/list" );

  tailPtr = this->clist[client][1];
  headPtr = this->clist[client][0];
  newPtr  = (clusterNode *)malloc( sizeof(clusterNode) );
  memset( &(newPtr->data), 0, sizeof(newPtr->data) );
  newPtr->size   = 0;
  newPtr->isFull = 0;
  newPtr->client = client;
  newPtr->prevCl = tailPtr;
  newPtr->nextCl = NULL;
  newPtr->nextQ  = NULL;
  /*
   * Add to list for client 
   */
  if ( !tailPtr ) {
    p = this->qhead;
    tailPtr = headPtr = newPtr;
  }
  else {
    p = tailPtr->nextQ;
    tailPtr->nextCl = newPtr;
    tailPtr = newPtr;
  }
  this->clist[client][1] = tailPtr;
  this->clist[client][0] = headPtr;
  /* 
   * Add to queue 
   */
  q = NULL;
  for ( ; p; q=p, p=p->nextQ ) {
    if ( time <= p->data.time ) break;
  }
  if ( !p ) {
    if ( !q ) {
      this->qhead = this->qtail = newPtr; /* empty list */
    }
    else {
      q->nextQ = newPtr;                  /* tail of list */
    }
  }
  else {
    if ( !q ) {
      newPtr->nextQ = p;                  /* head of list */
      this->qhead   = newPtr;
    }
    else {
      q->nextQ = newPtr;                  /* between 2 */
      newPtr->nextQ = p;
    }
  }
  return newPtr;
}


/*
 *----------------------------------------------------------------------
 *
 * AddToCluster -- Put the indicated data on the end of the cluster
 *                 node data. Increment size.
 *
 * Calls    :
 *
 * Algorithm:
 *
 *         Go to last element of cluster node.
 *         Point at new data.
 *         Increment size of cluster.
 *
 *----------------------------------------------------------------------
 */

void
Nlv_crAddToCluster( T this, clusterNode *ptr, Nlv_LData *d )
{
  if ( ptr->size < NLV_MAX_CLUSTERLINES ) {
    ptr->data.arr[ ptr->size++ ] = d;
  }
  else
    RAISE( crClusterFull );
}


/*
 *----------------------------------------------------------------------
 *
 * RemoveFull -- Remove, from the head of the queue, FULL 
 *               clusters. 
 *
 * Calls    :
 *
 * Algorithm:
 *
 *         Get ptr to head of queue.
 *         if ( cluster there is full )
 *           then: 
 *              - update links in per-client linked list
 *              - return it
 *            else:
 *              - return NULL
 *
 *----------------------------------------------------------------------
 */

clusterNode *Nlv_crRemoveFull( T this )
{
  clusterNode *p;
  Nlv_EInfo einfo;

  if ( this->qhead != NULL &&
       this->qhead->isFull ) {

    NLV_SET_EINFO( einfo, FILE_DBG, 0 );
    Nlv_errReport( eobj, &einfo, "Remove 1 cluster" );

    p = this->qhead;
    this->qhead = this->qhead->nextQ;
    if ( !this->qhead )
      this->qtail = NULL;
    /* 
     * Update client linked-list 
     */
    if ( !(p->prevCl) ) {
      this->clist[p->client][0] = p->nextCl;   /* remove from head */
    }
    else {
      p->prevCl->nextCl = p->nextCl;           /* point prev around it */
      if ( !p->nextCl )              
	this->clist[p->client][1] = p->prevCl; /* prev is new tail */
    }
    if ( !(p->nextCl) ) {
      this->clist[p->client][1] = p->prevCl;   /* remove from tail */
    }
    else {
      p->nextCl->prevCl = p->prevCl;           /* point next around it */
      if ( !p->prevCl )
	this->clist[p->client][0] = p->nextCl; /* next is new head */
    }
  }
  else {
    p = NULL;
  }

  return p;
}


/*
 *----------------------------------------------------------------------
 *
 * Scan -- Walk through the queue marking any out-of-date 
 *         clusters as "full". This allows for expiration of
 *         clusters which, for one reason or another, never get their
 *         full quota of events. The operation should be very rapid,
 *         and could reasonably be performed several times a second.
 *
 * Calls    :
 *
 * Algorithm:
 *
 *        Walk the queue.
 *        Mark any cluster before 'scanTime' as full.
 * 
 *----------------------------------------------------------------------
 */
void Nlv_crScan( T this, double scanTime )
{
  clusterNode *p;

  for ( p = this->qhead; p && p->data.time < scanTime; p=p->nextQ )
    p->isFull = 1;
}


/*
 *----------------------------------------------------------------------
 *
 * Dump -- Debugging hook.
 *
 * Calls   : 
 *
 * Algorithm: (read the code)
 *
 *----------------------------------------------------------------------
 */

void Nlv_crDump( T this )
{
  int i;
  clusterNode *p;

  printf("---By (non-empty) client---\n");
  for ( i=0; i < NLV_MAX_CLIENTS; i++)
    if ( this->clist[i][0] ) {
      printf( "CLIENT %d , T=%lf, SIZE=%d\n", i, this->clist[i][0]->data.time,
	      this->clist[i][0]->size );
    }
  printf("---By queue order (head to tail)---\n");
  for ( p = this->qhead; p; p=p->nextQ )
    printf("CLIENT %d\n", p->client );
}

/*
 *----------------------------------------------------------------------
 *
 * GetMaxCluster -- The maximum # of lines a cluster can handle.
 *
 * Calls    :
 *
 * Algorithm: Accessor.
 *
 *----------------------------------------------------------------------
 */

int Nlv_crGetMaxCluster( T this )
{
  return this->maxCluster;
}

/*
 *----------------------------------------------------------------------
 *
 * GetEpsilon -- The maximum distance a line can be from the
 *               timestamp of the 1st event of the 1st line in a
 *               cluster, and still be _in_ that cluster.
 *
 * Calls    :
 *
 * Algorithm: Accessor.
 *
 *----------------------------------------------------------------------
 */

double Nlv_crGetEpsilon( T this )
{
  return this->epsilon;
}

/*
 *----------------------------------------------------------------------
 *
 * SetMaxCluster -- (see GetMaxCluster)
 *
 * Calls    :
 *
 * Algorithm: Accessor.
 *
 *----------------------------------------------------------------------
 */

void Nlv_crSetMaxCluster( T this, int max )
{
  this->maxCluster = max;
}


/*
 *----------------------------------------------------------------------
 *
 * SetEpsilon -- ( See GetEpsilon ). Retroactive fragmentation or
 *               consolidation of clusters will NOT occur.
 *
 * Calls    :
 *
 * Algorithm: Accessor.
 *
 *----------------------------------------------------------------------
 */

void Nlv_crSetEpsilon( T this, double epsil )
{
  this->epsilon = epsil;
}

#undef T
#undef FILE_DBG
#undef FILE_ERROR_CODE
