Daily Programmer #191 Easy

main.c

#include <assert.h>
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Longest word to ever appear in literature: Lopadotemachoselachogaleokranioleipsanodrimhypotrimmatosilphioparaomelitokatakechymenokichlepikossyphophattoperisteralektryonoptekephalliokigklopeleiolagoiosiraiobaphetraganopterygon */
#define WSIZE	172
#define HSIZE	8191

struct bucket {
	char *word;
	unsigned int count;
	struct bucket *next;
};

static struct bucket *hash_table[HSIZE];
static unsigned int word_count = 0;

/* Duplicates a string onto the heap. */
static char *duplicate_string(const char *str)
{
	char *p = malloc(strlen(str) + 1);
	assert(p && "out of memory");
	strcpy(p, str);
	return p;
}

/* Returns the next word from stdin removing any non-alpha
 * characters. Returns NULL on EOF. The string is valid until the
 * next call.
 */
static char *next_word_from_stdin(void)
{
	static char buf[WSIZE];
	char *word = buf;

	/* Skip everything not alpha. */
	while (true) {
		*word = fgetc(stdin);
		if (isalpha(*word) || *word == EOF) {
			break;
		}
	}

	if (feof(stdin)) {
		return NULL;
	}

	/* Keep our character. */
	++word;

	while (word - buf < WSIZE - 1) {
		*word = fgetc(stdin);
		if (!isalpha(*word) || *word == EOF) {
			break;
		}
		++word;
	}
	*word = '\0';

	return buf;
}

/* Converts a string to lowercase in place. */
static void string_to_lower(char *str)
{
	while (*str) {
		*str = tolower(*str);
		++str;
	}
}

/* Hash for strings. */
static unsigned int hash(const char *str)
{
        unsigned int h = 5381;
        int c;

	while ((c = *str++)) {
		h = ((h << 5) + h) + c;
	}

        return h % HSIZE;
}

/* Compare function for buckets. */
static int compare_buckets(const void *a, const void *b)
{
	int a_count = 0;
	int b_count = 0;
	if (*(struct bucket **)a) {
		a_count = (*(struct bucket **)a)->count;
	}
	if (*(struct bucket **)b) {
		b_count = (*(struct bucket **)b)->count;
	}
	return a_count - b_count;
}

/* Helper function for creating a bucket. */
static struct bucket *alloc_bucket(const char *str)
{
	struct bucket *b = malloc(sizeof(*b));
	assert(b && "out of memory");
	b->word = duplicate_string(str);
	b->count = 1;
	b->next = NULL;
	return b;
}

/* Add a count to the hash hash_table. */
static void add_count(const char *str)
{
	struct bucket *p;
	struct bucket *b;
	unsigned int h = hash(str);

	b = hash_table[h];

	if (!b) {
		hash_table[h] = alloc_bucket(str);
		word_count++;
	} else {
		while (b && strcmp(b->word, str)) {
			p = b;
			b = b->next;
		}

		if (b) {
			b->count++;
		} else {
			p->next = alloc_bucket(str);
			word_count++;
		}
	}
}

/* Prints all the words in descending order by count. */
static void print_descending(void)
{
	int i, j = 0;
	struct bucket *iter;
	struct bucket **buckets = malloc(sizeof(*buckets) * word_count);
	assert(buckets && "out of memory");

	for (i = 0; i < HSIZE; ++i) {
		iter = hash_table[i];
		while (iter) {
			buckets[j++] = iter;
			iter = iter->next;
		}
	}

	qsort(buckets, word_count, sizeof(*buckets), compare_buckets);

	for (i = word_count - 1; i >= 0; --i) {
		printf("%s: %d\n", buckets[i]->word, buckets[i]->count);
	}

	free(buckets);
}

int main(void)
{
	char *word;

	while (true) {
		word = next_word_from_stdin();
		if (!word) {
			break;
		}
		string_to_lower(word);
		add_count(word);
	}

	print_descending();
	return 0;
}