/* This benchmark tests a platform's speed
   performing character-based input. It is
   intended to be highly portable to any 
   compliant C compiler.

                Tom Murphy VII
		    3 Jul 2006
*/

/* Using only basic C libraries */
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>

/* Some functions are not widely portable; we provide
   simple replacements here to make sure we are running
   the same code on every platform. */
int wstrlen(const wchar_t * s) {
  int r = 0;
  while (*s++) r++;
  return r;
}

int wstreq(const wchar_t * s1,
	   const wchar_t * s2) {
  int i = 0;
  while (! (i > wstrlen(s1) && i > wstrlen(s2))) {
    if (s1[i] != s2[i]) return 0;
    i ++;
  }
  return 1;
}

#define HASHSIZE 65537
#define MAXWORD 4192

#define isspace(c) (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == '\v')

struct hashentry_t {
  struct hashentry_t * next;
  int freq;
  wchar_t w[0];
};

struct hashentry_t * table[HASHSIZE];
static int num_entries = 0;

static int cmp_hashentry(const void * l, const void * r) {
  wchar_t * s1 = (*(struct hashentry_t**)l)->w;
  wchar_t * s2 = (*(struct hashentry_t**)r)->w;
  int i = 0;
  while (s1[i]) {
    if (!s2[i] || s2[i] < s1[i]) return 1;
    else if (s1[i] < s2[i]) return -1;
    i ++;
  }
  return -!!s2[i];
}

/* rotate x (m bits) left by y bits */
#define ROL(x, y, m) (((x) >> ((m) - (y))) | ((x) << (y)))

int hash (wchar_t * word) {
  int hc = 0xDEADBEEF;
  int i = 0;
  while(word[i] != 0) {
    wchar_t c = ~word[i];
    c = ROL(c, 1, 8 * sizeof(wchar_t));
    hc = hc * 31137;
    hc ^= c;
    i++;
  }

  return hc;
}

void increment(wchar_t * word) {
  int hc = ((unsigned)hash(word)) % HASHSIZE;

  struct hashentry_t ** l = &table[hc];
  
  /* search for entry. as we do, move more
     frequent entries towards the front of the
     list in order to speed up future searches */
  while (*l) {
    if (wstreq((*l)->w, word)) {
      /* found */
      (*l)->freq ++;
      return ;
    }

    if (1 && (*l)->next && (*l)->freq > (*l)->next->freq) {

      /* swap and look again */
      struct hashentry_t * tmp1 = (*l)->next;
      struct hashentry_t * tmp2 = (*l)->next->next;
      (*l)->next->next = *l;
      (*l)->next = tmp2;
      (*l) = tmp1;
      
    } else {
      
      /* advance to next element */
      l = &((*l)->next);
    }
  }
  
  /* never found! add it */
  *l = (struct hashentry_t*) 
	malloc(sizeof(struct hashentry_t) +
	       sizeof(wchar_t) * (1 + wstrlen(word)));
  
  num_entries ++;

  (*l)->next = 0;
  (*l)->freq = 1;
  { 
    int i;
    for(i = 0; i <= wstrlen(word); i ++) (*l)->w[i] = word[i];
  }
}

int main () {
  wchar_t tmp[MAXWORD];
  int c;
  struct hashentry_t ** outputs;

  { 
    int i =0;
    for(i = 0; i < HASHSIZE; i ++) {
      table[i] = 0;
    }
  }

  do {
    /* read a word */
    int i = 0;
    while ((c = getchar()) != -1 &&
	   !isspace(c)) {
      tmp[i++] = (wchar_t)c;
      if (i == (MAXWORD - 1)) {
	fprintf(stderr, "word too long\n");
	abort();
      }
    }
    
    /* null-terminate */
    tmp[i] = 0;

    /* if it's not an empty word */
    if (i) {
      increment(tmp);
    }

    /* continue if not end of file */
  } while (c != -1);

  /* now that we know the number of words, sort the results */
  outputs = (struct hashentry_t **)malloc(num_entries *
					  sizeof (struct hashentry_t *));

  {
    int i, j = 0;
    for (i = 0; i < HASHSIZE; i ++) {
      struct hashentry_t * l = table[i];
      while(l) {
	outputs[j++] = l;
	l = l->next;
      }
    }

    qsort(outputs, num_entries, sizeof (struct hashentry_t *),
	  cmp_hashentry);
  }

  /* finally, print out the frequencies */
  {
    int k, i = 0;
    for(i = 0; i < num_entries; i ++) {
      printf("%d ", outputs[i]->freq);
      for(k = 0; outputs[i]->w[k] != 0; k ++) {
	putchar(outputs[i]->w[k]);
      }
      putchar('\n');
    }
  }

  return 0;
}