/* lines.c - Don Yang (uguu.org)

   12/27/05
                                                                           */
/*@ -branchstate -compdef -mustfreeonly -nullstate @*/
/*@ -unqualifiedtrans -usereleased @*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "lines.h"

#define MIN_CAPACITY       2
#define MAX_LINE_LENGTH    0x40000000

/* Create a string list */
/*@only@*/StringList *StringList_create(size_t capacity)
{
   StringList *s;

   if( (s = (StringList*)malloc(sizeof(StringList))) == NULL )
      abort();
   s->size = 0;
   s->capacity = (capacity > MIN_CAPACITY) ? capacity : MIN_CAPACITY;
   if( (s->list = (char**)malloc(s->capacity * sizeof(char*))) == NULL )
      abort();
   return s;
}

/* Load file */
/*@only@*/StringList *StringList_from_file(FILE *infile)
{
   /*@only@*/StringList *s;
   /*@only@*/char *buffer;
   /*@dependent@*/char *p, *q;
   char *tmp;
   size_t read_size, max_size, partial_line;

   s = StringList_create(16);
   if( (buffer = (char*)malloc(1 + (max_size = 0x100))) == NULL )
      abort();
   buffer[max_size] = '\0';
   for(partial_line = 0;;)
   {
      /* Read block to memory */
      read_size = fread(
         buffer + partial_line, 1, max_size - partial_line, infile);
      if( (read_size += partial_line) == 0 )
         break;

      /* Tokenize lines */
      for(p = q = buffer; p != buffer + read_size; p = q)
      {
         if( (q = strpbrk(p, "\r\n")) == NULL )
            break;
         if( *q == '\r' )
         {
            if( q[1] == '\n' )
               *q++ = '\0';      /* Drop CR */
         }
         *q++ = '\0';   /* Drop LF */
         (void)StringList_append(s, p);
      }

      if( q != NULL )
      {
         /* Last line was complete, read next block at full size */
         partial_line = 0;
      }
      else
      {
         /* Last line was incomplete... */
         partial_line = read_size - ((size_t)p - (size_t)buffer);
         if( p != buffer )
         {
            /* Shift data and try again */
            memmove(buffer, p, partial_line);
         }
         else
         {
            /* Increase buffer size and try again */
            if( max_size >= MAX_LINE_LENGTH ) abort();
            if( (tmp = (char*)malloc(max_size *= 2)) == NULL ) abort();
            memcpy(tmp, buffer, partial_line);
            free(buffer);
            buffer = tmp;
         }
      }
   }

   free(buffer);
   return s;
}

/* Free string list */
void StringList_destroy(/*@only@*//*@notnull@*/StringList *s) /*@releases s@*/
{
   size_t i;
   for(i = 0; i < s->size; i++)
      free(s->list[i]);
   free(s->list);
   free(s);
}

/* Make copy of string and append to list */
/*@dependent@*/char *StringList_append(StringList *s, /*@observer@*/char *str)
{
   char *d;
   if( (d = (char*)malloc(strlen(str) + 1)) == NULL )
      abort();
   return StringList_append_alloc(s, strcpy(d, str));
}

/* Append allocated string to list, string becomes owned by list */
/*@dependent@*/char *StringList_append_alloc(StringList *s,
                                             /*@only@*/char *str)
{
   char **tmp;

   if( s->size == s->capacity )
   {
      s->capacity *= 2;
      if( (tmp = (char**)malloc(s->capacity * sizeof(char*))) == NULL )
         abort();
      memcpy(tmp, s->list, s->size * sizeof(char*));
      free(s->list);
      s->list = tmp;
   }
   return s->list[s->size++] = str;
}

/* Sort list */
static int QsortCmp(const void *a, const void *b)
{
   return strcmp(*(char**)a, *(char**)b);
}
void StringList_sort(StringList *s)
{
   qsort(s->list, (size_t)s->size, sizeof(char*), QsortCmp);
}

/* Remove duplicates in sorted list */
void StringList_uniq(StringList *s)
{
   /*@observer@*/char *last;
   char **r, **w, **end;

   if( s->size == 0 )
      return;

   last = *(s->list);
   end = s->list + s->size;
   for(r = s->list + 1; r != end; r++)
   {
      if( strcmp(*r, last) == 0 )
      {
         free(*r);
         *r = NULL;
         s->size--;
      }
      else
      {
         last = *r;
      }
   }
   for(r = w = s->list; r != end;)
   {
      if( *r == NULL )
         r++;
      else
         *(w++) = *(r++);
   }
}