/* Note that these structures can use up a lot of memory if we don't do something (refcounting, or something)
   the lines so we delete them when they aren't used by any version anymore,
   We could also not copy the text like we do now, and share it
   with whatever handed it to us.
*/

/* These were the structures and functions described to me by someone who
   knows cvs.
   I was told they do backwards blame as follows:

   CVS creates two linevectors, one called "headlines" and one called
   "curlines".
   curlines is initialized to the text of the most recent revision by calling
   linevector_add on the text, and then linevector_copy'ing it ot headlines.
   
   Each reverse diff is then applied, and curlines is updated.  Because
   curlines and headlines share struct line *'s, as the curlines vector is
   updated, all the lines that are really in headlines are also automatically
   updated.  At the end, headlines now contains properly blamed lines.  */
/* One line in a line vector. */


struct line
{
  char *text;
  size_t len;
  const char *version;

};

/* The entire linevector.  */
struct linevector
{
  unsigned int nlines;
  struct line **vector;
};



/* Initialize *VEC to be a linevector with no lines.  */
static void
linevector_init (struct linevector *vec)
{
  vec->nlines = 0;
  vec->vector = NULL;
}

/* Count the number of new lines that will be added to a linevector if we
   insert TEXT into it.  */

static int
count_new_lines (const char *text, size_t len)
{
  /* There is always at least one new line in the text, which is the line that
     starts *at* the beginning of text.  */
  int num = 1;
  int i;
  /* We want every newline but the newline at the very end of the text.  */
  for (i = 0; i < len; i++)
    if (*(text + i) == '\n' && (i + 1) < len)
      num++;
  return num;
}

/* Ensure that our line vector contains enough space for LINES number of
   lines.  Of course, we could just allocate more lines than we need and
   double it every time we ran out or something, but this is a first pass
   implementation.  */

static struct linevector *
ensure_vector_size (struct linevector *vec, size_t lines)
{
  if (vec->nlines < lines)
    {
      vec->vector = realloc (vec->vector,
			     lines * sizeof (struct line));
    }
  return vec;
}
      
/* Add each line of TEXT (of length LEN) to VEC at position POS.
   Each line gets VERSION as it's associated version.  */

static int
linevector_add (struct linevector *vec, const char *text, size_t len, 
		size_t pos, const char * version)	       
{
  const char *textend;
  unsigned int i;
  unsigned int new_lines;
  const char *p;
  const char *nextline_text;
  size_t nextline_len;
  int nextline_newline;
  struct line *line;

  if (len == 0)
    return 1;

  textend = text + len;
  
  new_lines = count_new_lines (text, len);
  
  vec = ensure_vector_size (vec, vec->nlines + new_lines);

  /* Move the part of the line vector we are adding into out of the way.  */
  for (i = vec->nlines + new_lines - 1; i >= pos + new_lines; --i)
    vec->vector[i] = vec->vector[i - new_lines];

  if (pos > vec->nlines)
    return 0;

  /* Actually add the lines, to VEC->VECTOR.  */
  i = pos;
  
  nextline_text = text;
  for (p = text; p < textend; ++p)
    if (*p == '\n')
      {
	/* No need to add another line for the final newline.  */
	if (p + 1 == textend)
	  break;
	nextline_len = p - nextline_text;
	line = malloc (sizeof (struct line));
	line->version = version;
	line->text = malloc (nextline_len);
	line->len = nextline_len;
	memcpy (line->text, nextline_text, nextline_len);
	vec->vector[i++] = line;

	nextline_text = p + 1;
      }
  /* Add the final line.  */
  nextline_len = p - nextline_text;
  line = malloc (sizeof (struct line));
  line->version = version;
  line->text = malloc (nextline_len);
  line->len = nextline_len;
  memcpy (line->text, nextline_text, nextline_len);
  vec->vector[i] = line;

  vec->nlines += new_lines;

  return 1;
}

/* Remove NLINES lines from VEC at position POS (where line 0 is the
   first line).  */

static void
linevector_delete (struct linevector *vec, unsigned int pos,
		   unsigned int nlines)
{
  unsigned int i;

  for (i = pos; i < (vec->nlines - nlines); ++i)
    vec->vector[i] = vec->vector[i + nlines];
  vec->nlines -= nlines;
}


/* Copy FROM to TO, copying the vectors but not the lines pointed to.  */

static void
linevector_copy (struct linevector *to, struct linevector *from)
{
  to = ensure_vector_size (to, from->nlines);

  memcpy (to->vector, from->vector,
	  from->nlines * sizeof (*to->vector));
  to->nlines = from->nlines;
}