/*--------------------------------------------------------------------*/
/*--- Callgrind                                                    ---*/
/*---                                                   ct_costs.c ---*/
/*--------------------------------------------------------------------*/

/*
   This file is part of Callgrind, a Valgrind tool for call tracing.

   Copyright (C) 2002-2004, Josef Weidendorfer (Josef.Weidendorfer@gmx.de)

   This program 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 of the
   License, or (at your option) any later version.

   This program 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.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
   02111-1307, USA.

   The GNU General Public License is contained in the file COPYING.
*/

#include "ct_include.h" // debugging macros
#include "ct_events.h"
#include "ct_costs.h"

#define MAX_EVENTTYPE 20

static EventType eventtype[MAX_EVENTTYPE];
static Int eventtype_count = 0;

EventType* SK_(register_eventtype)(char* name)
{
  EventType* et;

  if (eventtype_count == MAX_EVENTTYPE) {
    VG_(printf)("\nMore than %d event types used!\n"
		"Increase MAX_EVENTTYPE in ct_events.c and recomile this tool!\n",
		MAX_EVENTTYPE);
    VG_(skin_panic)("Too many event types requested.");
  }

  et = &(eventtype[eventtype_count]);
  et->id = eventtype_count; 
  et->name = (UChar*) VG_(strdup)(name);
  et->description = 0;

  eventtype_count++;

  return et;
}


EventType* SK_(get_eventtype)(char* name)
{
  Int i;

  for(i=0;i<eventtype_count;i++)
    if (VG_(strcmp)(eventtype[i].name, name) == 0)
      return eventtype+i;
  return 0;
}

EventType* SK_(get_eventtype_byindex)(Int id)
{
  if ((id >= 0) && (id < eventtype_count))
    return eventtype+id;
  return 0;
}

/* Allocate space for an event set */
EventSet* SK_(get_eventset)(Char* n, Int capacity)
{
  EventSet* es;

  es = (EventSet*) VG_(malloc)(sizeof(EventSet) +
			       capacity * sizeof(EventSetEntry));
  es->capacity = capacity;
  es->size = 0;
  es->name = n;

  return es;
}

/* Incorporate a event type into a set, get start offset */
Int SK_(add_eventtype)(EventSet* es, EventType* t)
{
  Int offset = es->size;
  if (es->capacity - offset < 1) return -1;

  es->size++;
  es->e[offset].type = t;
  es->e[offset].nextTop = es->size;

  return offset;
}

/* Incorporate one event set into another, get start offset */
Int SK_(add_eventset)(EventSet* dst, EventSet* src)
{
  Int offset = dst->size, i;
  if (!src || (src->size == 0)) return offset;

  if (dst->capacity - offset < src->size) return -1;
  
  for(i=0;i<src->size;i++) {
    dst->e[offset+i].type = src->e[i].type;
    dst->e[offset+i].nextTop = src->e[i].nextTop + offset;
  }
  dst->size += src->size;

  return offset;
}

/* Incorporate two event types into a set, with second < first */
Int SK_(add_dep_event2)(EventSet* es, EventType* e1, EventType* e2)
{
  Int offset = es->size;

  if (es->capacity - offset < 2) return -1;

  es->size += 2;
  es->e[offset].type = e1;
  es->e[offset].nextTop = es->size;
  es->e[offset+1].type = e2;
  es->e[offset+1].nextTop = es->size;
  
  return offset;
}

/* Incorporate 3 event types into a set, with third < second < first */
Int SK_(add_dep_event3)(EventSet* es,
			EventType* e1, EventType* e2, EventType* e3)
{
  Int offset = es->size;

  if (es->capacity - offset < 3) return -1;

  es->size += 3;
  es->e[offset].type = e1;
  es->e[offset].nextTop = es->size;
  es->e[offset+1].type = e2;
  es->e[offset+1].nextTop = es->size;
  es->e[offset+2].type = e3;
  es->e[offset+2].nextTop = es->size;
  
  return offset;
}

/* Returns number of characters written */
Int SK_(sprint_eventset)(Char* buf, EventSet* es)
{
  Int i, pos = 0;

  for(i=0; i< es->size; i++) {
    if (pos>0) buf[pos++] = ' ';
    pos += VG_(sprintf)(buf + pos, es->e[i].type->name);
  }
  buf[pos] = 0;

  return pos;
}

/* Get cost array for an event set */
ULong* SK_(get_eventset_cost)(EventSet* es)
{
  return SK_(get_costarray)(es->capacity);
}

/* Set all costs of an event set to zero */
void SK_(init_cost)(EventSet* es, ULong* cost)
{
  Int i;

  if (!cost) return;

  for(i=0;i<es->capacity;i++)
    cost[i] = 0;
}

/* Set all costs of an event set to zero */
void SK_(init_cost_lz)(EventSet* es, ULong** cost)
{
  Int i;

  CT_ASSERT(cost != 0);
  if (!(*cost))
    *cost = SK_(get_eventset_cost)(es);

  for(i=0;i<es->capacity;i++)
    (*cost)[i] = 0;
}

void SK_(zero_cost)(EventSet* es, ULong* cost)
{
  Int i;

  if (!cost) return;

  for(i=0;i<es->size;i++)
    cost[i] = 0;
}
  
Bool SK_(is_zero_cost)(EventSet* es, ULong* cost)
{
  Int i = 0;

  if (!cost) return True;

  while(i<es->size) {
    if (cost[i] != 0) return False;
    i = es->e[i].nextTop;
  }
  return True;
}

Bool SK_(is_equal_cost)(EventSet* es, ULong* c1, ULong* c2)
{
  Int i = 0;

  if (!c1) return SK_(is_zero_cost)(es,c2);
  if (!c2) return SK_(is_zero_cost)(es,c1);

  while(i<es->size) {
    if (c1[i] != c2[i]) return False;
    if (c1[i] == 0)
      i = es->e[i].nextTop;
    else
      i++;
  }
  return True;
}

void SK_(copy_cost)(EventSet* es, ULong* dst, ULong* src)
{
  Int i;

  if (!src) {
    SK_(zero_cost)(es, dst);
    return;
  }
  CT_ASSERT(dst != 0);
  
  for(i=0;i<es->size;i++)
    dst[i] = src[i];
}

void SK_(copy_cost_lz)(EventSet* es, ULong** pdst, ULong* src)
{
  Int i;
  ULong* dst;

  CT_ASSERT(pdst != 0);

  if (!src) {
    SK_(zero_cost)(es, *pdst);
    return;
  }
  dst = *pdst;
  if (!dst)
    dst = *pdst = SK_(get_eventset_cost)(es);
  
  for(i=0;i<es->size;i++)
    dst[i] = src[i];
}

void SK_(add_cost)(EventSet* es, ULong* dst, ULong* src)
{
  Int i = 0;

  if (!src) return;
  CT_ASSERT(dst != 0);

  while(i<es->size) {
    if (src[i] == 0)
      i = es->e[i].nextTop;
    else {
      dst[i] += src[i];
      i++;
    }
  }
}

void SK_(add_cost_lz)(EventSet* es, ULong** pdst, ULong* src)
{
  Int i;
  ULong* dst;

  if (!src) return;
  CT_ASSERT(pdst != 0);

  dst = *pdst;
  if (!dst) {
    dst = *pdst = SK_(get_eventset_cost)(es);
    SK_(copy_cost)(es,dst,src);
    return;
  }

  i = 0;
  while(i<es->size) {
    if (src[i] == 0)
      i = es->e[i].nextTop;
    else {
      dst[i] += src[i];
      i++;
    }
  }
}

/* Adds src to dst and zeros src. Returns false if nothing changed */
Bool SK_(add_and_zero_cost)(EventSet* es, ULong* dst, ULong* src)
{
  Int i = 0, j = 0;

  if (!src) return False;

  while(i<es->size) {
    if (src[i] == 0)
      i = es->e[i].nextTop;
    else {
      dst[i] += src[i];
      src[i] = 0;
      i++;
      j++;
    }
  }

  return (j>0);
}

/* Adds src to dst and zeros src. Returns false if nothing changed */
Bool SK_(add_and_zero_cost_lz)(EventSet* es, ULong** pdst, ULong* src)
{
  Int i;
  ULong* dst;

  if (!src) return False;

  i = 0;
  while(1) {
    if (i >= es->size) return False;
    if (src[i] != 0) break;
    i = es->e[i].nextTop;
  }

  CT_ASSERT(pdst != 0);
  dst = *pdst;
  if (!dst) {
    dst = *pdst = SK_(get_eventset_cost)(es);
    SK_(copy_cost)(es,dst,src);
    SK_(zero_cost)(es,src);
    return True;
  }

  dst[i] += src[i];
  src[i] = 0;
  i++;

  while(i<es->size) {
    if (src[i] == 0)
      i = es->e[i].nextTop;
    else {
      dst[i] += src[i];
      src[i] = 0;
    }
  }

  return True;
}

/* Adds difference of new and old to dst, and set old to new.
 * Returns false if nothing changed */
Bool SK_(add_diff_cost)(EventSet* es, ULong* dst, ULong* old, ULong* new)
{
  Int i = 0, j = 0;

  while(i<es->size) {
    if (new[i] == old[i])
      i = es->e[i].nextTop;
    else {
      dst[i] += new[i] - old[i];
      old[i] = new[i];
      i++;
      j++;
    }
  }

  return (j>0);
}

/* Adds difference of new and old to dst, and set old to new.
 * Returns false if nothing changed */
Bool SK_(add_diff_cost_lz)(EventSet* es, ULong** pdst, 
			    ULong* old, ULong* new)
{
  Int i;
  ULong* dst;

  if (!old && !new) return False;  
  CT_ASSERT(old && new);

  i = 0;
  while(1) {
    if (i >= es->size) return False;
    if (old[i] != new[i]) break;
    i = es->e[i].nextTop;
  }

  CT_ASSERT(pdst != 0);
  dst = *pdst;
  if (!dst) {
    dst = *pdst = SK_(get_eventset_cost)(es);
    SK_(zero_cost)(es,dst);
  }

  dst[i] += new[i] - old[i];
  old[i] = new[i];
  i++;

  while(i<es->size) {
    if (new[i] == old[i])
      i = es->e[i].nextTop;
    else {
      dst[i] += new[i] - old[i];
      old[i] = new[i];
      i++;
    }
  }

  return True;
}

/* Returns number of characters written */
Int SK_(sprint_cost)(Char* buf, EventSet* es, ULong* c)
{
  Int i, pos, skipped = 0;

  if (!c || es->size==0) return 0;

  /* At least one entry */
  pos = VG_(sprintf)(buf, "%llu", c[0]);
  i = 1;

  while(i<es->size) {
    if (c[i] == 0) {
      skipped  += es->e[i].nextTop - i;
      i = es->e[i].nextTop;
    }
    else {
      while(skipped>0) {
	buf[pos++] = ' ';
	buf[pos++] = '0';
	skipped--;
      }
      buf[pos++] = ' ';
      pos += VG_(sprintf)(buf+pos, "%llu", c[i]);
      i++;
    }
  }

  return pos;
}


/* Allocate space for an event mapping */
EventMapping* SK_(get_eventmapping)(EventSet* es)
{
  EventMapping* em;

  CT_ASSERT(es != 0);

  em = (EventMapping*) VG_(malloc)(sizeof(EventMapping) +
				   es->capacity * sizeof(Int));
  em->capacity = es->capacity;
  em->size = 0;
  em->set = es;

  return em;
}

void SK_(append_event)(EventMapping* em, char* n)
{
  Int i;

  CT_ASSERT(em != 0);

  for(i=0; i<em->set->size; i++)
    if (VG_(strcmp)(n, em->set->e[i].type->name)==0)
      break;
  
  if (i == em->set->size) return;

  CT_ASSERT(em->capacity > em->size);

  em->index[em->size] = i;
  em->size++;
}


/* Returns number of characters written */
Int SK_(sprint_eventmapping)(Char* buf, EventMapping* em)
{
  Int i, pos = 0;

  CT_ASSERT(em != 0);

  for(i=0; i< em->size; i++) {
    if (pos>0) buf[pos++] = ' ';
    pos += VG_(sprintf)(buf + pos, em->set->e[em->index[i]].type->name);
  }
  buf[pos] = 0;

  return pos;
}

/* Returns number of characters written */
Int SK_(sprint_mappingcost)(Char* buf, EventMapping* em, ULong* c)
{
  Int i, pos, skipped = 0;

  if (!c || em->size==0) return 0;

    /* At least one entry */
  pos = VG_(sprintf)(buf, "%llu", c[em->index[0]]);
  i = 1;

  while(i<em->size) {
    if (c[em->index[i]] == 0) {
      skipped++;
      i++;
    }
    else {
      while(skipped>0) {
	buf[pos++] = ' ';
	buf[pos++] = '0';
	skipped--;
      }
      buf[pos++] = ' ';
      pos += VG_(sprintf)(buf+pos, "%llu", c[em->index[i]]);
      i++;
    }
  }

  return pos;
}