#include <glib.h>
#include <stdlib.h>
#include <string.h>
#include <sys/times.h>
#include <unistd.h>

#define ITERS 10

#define TOLOWER(c) \
  (((c) >= 'A' && (c) <= 'Z') ? (c) - 'A' + 'a' : (c))

static GString *output;

static gint
original_strcasecmp (const gchar *s1,
		     const gchar *s2)
{
  gint c1, c2;

  g_return_val_if_fail (s1 != NULL, 0);
  g_return_val_if_fail (s2 != NULL, 0);

  while (*s1 && *s2)
    {
      c1 = (gint)(guchar) g_ascii_tolower (*s1);
      c2 = (gint)(guchar) g_ascii_tolower (*s2);
      if (c1 != c2)
	return (c1 - c2);
      s1++; s2++;
    }

  return (((gint)(guchar) *s1) - ((gint)(guchar) *s2));
}

static gint
mortenw_strcasecmp (const gchar *s1,
		    const gchar *s2)
{
  gint c1, c2;

  g_return_val_if_fail (s1 != NULL, 0);
  g_return_val_if_fail (s2 != NULL, 0);

  while (*s1 && *s2)
    {
      if (*s1 != *s2)
	{
	  c1 = (gint)(guchar) g_ascii_tolower (*s1);
	  c2 = (gint)(guchar) g_ascii_tolower (*s2);
	  if (c1 != c2)
	    return (c1 - c2);
	}
      s1++; s2++;
    }

  return (((gint)(guchar) *s1) - ((gint)(guchar) *s2));
}

static gint
inlined_strcasecmp (const gchar *s1,
		    const gchar *s2)
{
  gint c1, c2;

  g_return_val_if_fail (s1 != NULL, 0);
  g_return_val_if_fail (s2 != NULL, 0);

  while (*s1 && *s2)
    {
      c1 = (gint)(guchar) TOLOWER (*s1);
      c2 = (gint)(guchar) TOLOWER (*s2);
      if (c1 != c2)
	return (c1 - c2);
      s1++; s2++;
    }

  return (((gint)(guchar) *s1) - ((gint)(guchar) *s2));
}

static gint
both_strcasecmp (const gchar *s1,
		 const gchar *s2)
{
  gint c1, c2;

  g_return_val_if_fail (s1 != NULL, 0);
  g_return_val_if_fail (s2 != NULL, 0);

  while (*s1 && *s2)
    {
      if (*s1 != *s2)
	{
	  c1 = (gint)(guchar) TOLOWER (*s1);
	  c2 = (gint)(guchar) TOLOWER (*s2);
	  if (c1 != c2)
	    return (c1 - c2);
	}
      s1++; s2++;
    }

  return (((gint)(guchar) *s1) - ((gint)(guchar) *s2));
}

static gboolean
original_equal (gconstpointer a, gconstpointer b)
{
  const char *stra = (const char *)a;
  const char *strb = (const char *)b;

  return original_strcasecmp (stra, strb) == 0;
}

static int
original_compare (gconstpointer a, gconstpointer b)
{
  const char *stra = *(const char * const*)a;
  const char *strb = *(const char * const*)b;

  return original_strcasecmp (stra, strb);
}

static  gboolean
mortenw_equal (gconstpointer a, gconstpointer b)
{
  const char *stra = (const char *)a;
  const char *strb = (const char *)b;

  return mortenw_strcasecmp (stra, strb) == 0;
}

static int
mortenw_compare (gconstpointer a, gconstpointer b)
{
  const char *stra = *(const char * const*)a;
  const char *strb = *(const char * const*)b;

  return mortenw_strcasecmp (stra, strb);
}

static  gboolean
inlined_equal (gconstpointer a, gconstpointer b)
{
  const char *stra = (const char *)a;
  const char *strb = (const char *)b;

  return inlined_strcasecmp (stra, strb) == 0;
}

static int
inlined_compare (gconstpointer a, gconstpointer b)
{
  const char *stra = *(const char * const*)a;
  const char *strb = *(const char * const*)b;

  return inlined_strcasecmp (stra, strb);
}

static  gboolean
both_equal (gconstpointer a, gconstpointer b)
{
  const char *stra = (const char *)a;
  const char *strb = (const char *)b;

  return both_strcasecmp (stra, strb) == 0;
}

static int
both_compare (gconstpointer a, gconstpointer b)
{
  const char *stra = *(const char * const*)a;
  const char *strb = *(const char * const*)b;

  return both_strcasecmp (stra, strb);
}

static guint
case_insensitive_hash (const char *key)
{
  const char *p = key;
  guint h = TOLOWER (*p);

  if (h)
    {
      for (p += 1; *p != '\0'; p++)
	h = (h << 5) - h + TOLOWER (*p);
    }

  return h;
}

GPtrArray *
ptr_array_copy (GPtrArray *orig)
{
  GPtrArray *result;
  
  result = g_ptr_array_sized_new (orig->len);
  result->len = orig->len;
  memcpy (result->pdata, orig->pdata,
	  result->len * sizeof (gpointer));

  return result;
}

static void
do_bench (GPtrArray   *orig_words,
	  char        *name,
	  GEqualFunc   equal_func,
	  GCompareFunc array_compare_func)
{
  GPtrArray *words;
  GHashTable *hash;
  GTimer *timer;
  int i, j;
  double wall_elapsed;
  double utime_elapsed;
  int clocks_per_second = sysconf(_SC_CLK_TCK);
  struct tms start_times;
  struct tms end_times;
  
  timer = g_timer_new ();

  wall_elapsed = 0;
  utime_elapsed = 0;

  words = ptr_array_copy (orig_words);

  for (j = 0; j < ITERS; j++)
    {
      hash = g_hash_table_new ((GHashFunc) case_insensitive_hash, equal_func);
  
      times (&start_times);
      g_timer_start (timer);
      
      for (i = 0; i < words->len; i++)
	g_hash_table_insert (hash, words->pdata[i], GUINT_TO_POINTER (1));
      for (i = 0; i < words->len; i++)
	g_hash_table_lookup (hash, words->pdata[i]);

      g_timer_stop (timer);
      times (&end_times);

      g_hash_table_destroy (hash);

      utime_elapsed += (double)(end_times.tms_utime - start_times.tms_utime) / clocks_per_second;
      wall_elapsed += g_timer_elapsed (timer, NULL);
    }

  g_ptr_array_free (words, TRUE);

  g_string_append_printf (output, "%s: Hash, wall: %.2fs user: %.2fs\n", name, wall_elapsed, utime_elapsed);

  wall_elapsed = 0;
  utime_elapsed = 0;
  
  for (j = 0; j < ITERS; j++)
    {
      words = ptr_array_copy (orig_words);
      
      times (&start_times);
      g_timer_start (timer);
      g_ptr_array_sort (words, array_compare_func);
      g_timer_stop (timer);
      times (&end_times);

      g_ptr_array_free (words, TRUE);

      utime_elapsed += (double)(end_times.tms_utime - start_times.tms_utime) / clocks_per_second;
      wall_elapsed += g_timer_elapsed (timer, NULL);
    }

  g_string_append_printf (output, "%s: Sort, wall: %.2fs user: %.2fs\n", name, wall_elapsed, utime_elapsed);
  
  g_timer_destroy (timer);
}

static void
die (char *msg, GError *error)
{
  g_printerr ("%s: %s\n", msg, error->message);
  exit (1);
}

int main (int argc, char **argv)
{
  GPtrArray *words;
  GIOChannel *channel;
  GIOStatus status;
  GError *error = NULL;
  int i;

  words = g_ptr_array_new ();
  
  channel = g_io_channel_new_file ("/usr/share/dict/words", "r", &error);
  if (!channel)
    die ("Cannot open words file", error);

  while (TRUE)
    {
      char *word;
      char *lowercase;
      char *to_insert;
      size_t terminator_pos;
      
      status = g_io_channel_read_line (channel, &word, NULL, &terminator_pos, &error);
      switch (status)
	{
	case G_IO_STATUS_NORMAL:
	  word[terminator_pos] = '\0';
	  lowercase = g_ascii_strdown (word, -1);
	  switch (g_random_int_range (0, 3))
	    {
	    case 0:
	      to_insert = g_strdup (lowercase);
	      break;
	    case 1:
	      to_insert = g_ascii_strup (word, -1);
	      break;
	    default: /* 2 */
	      to_insert = g_strdup (lowercase);
	      if (to_insert[0])
		to_insert[0] = g_ascii_toupper (to_insert[0]);
	      break;
	    }

	  g_ptr_array_add (words, to_insert);
	  g_free (lowercase);
	  g_free (word);
	  break;
	case G_IO_STATUS_ERROR:
	  die ("Error reading words file", error);
	  break;
	case G_IO_STATUS_AGAIN:
	  g_assert_not_reached();
	  break;
	case G_IO_STATUS_EOF:
	  goto done;
	}
    }
 done:
  g_io_channel_unref (channel);

  /* Shuffle the words in the array */
  for (i = 0; i < words->len; i++)
    {
      char *tmp;
      int new_pos = i + g_random_int_range (0, words->len - i);
      
      tmp = words->pdata[new_pos];
      words->pdata[new_pos] = words->pdata[i];
      words->pdata[i] = tmp;
    }

  output = g_string_new (NULL);

  g_string_append_printf (output, "%d words, %d iterations\n", words->len, ITERS);
  
  do_bench (words, "Original", original_equal, original_compare);
  do_bench (words, "MortenW ", mortenw_equal, mortenw_compare);
  do_bench (words, "Inlined ", inlined_equal, inlined_compare);
  do_bench (words, "Both    ", both_equal, both_compare);

  g_print ("%s\n", output->str);
  
  return 0;
}

