0. make.log

> make clean && make
rm -f hashtable.o main.o hashtable hashtable-demo hashtable-demo.o
gcc -O0 -g -DDEBUG -std=c99 -Wall -Wextra -pedantic -Wshadow -Wstrict-overflow -Wstrict-prototypes -Wmissing-prototypes -Wno-missing-field-initializers   -c -o hashtable.o hashtable.c
hashtable.c: In function ‘ht_put’:
hashtable.c:46:4: warning: implicit declaration of function ‘strnlen’ [-Wimplicit-function-declaration]
    assert(strnlen(key, 16) < 16);
    ^
hashtable.c: In function ‘ht_del’:
hashtable.c:103:26: warning: unused parameter ‘ht’ [-Wunused-parameter]
 void ht_del(hashtable_t *ht, char *key) {}
                          ^
hashtable.c:103:36: warning: unused parameter ‘key’ [-Wunused-parameter]
 void ht_del(hashtable_t *ht, char *key) {}
                                    ^
gcc -O0 -g -DDEBUG -std=c99 -Wall -Wextra -pedantic -Wshadow -Wstrict-overflow -Wstrict-prototypes -Wmissing-prototypes -Wno-missing-field-initializers   -c -o main.o main.c
main.c:9:5: warning: no previous prototype for ‘print_iter’ [-Wmissing-prototypes]
 int print_iter(char *key, void *val) {
     ^
main.c:14:6: warning: no previous prototype for ‘print_ht_stats’ [-Wmissing-prototypes]
 void print_ht_stats(hashtable_t *ht) {
      ^
main.c:37:6: warning: no previous prototype for ‘eval_tracefile’ [-Wmissing-prototypes]
 void eval_tracefile(char *filename) {
      ^
main.c: In function ‘eval_tracefile’:
main.c:56:10: warning: implicit declaration of function ‘strdup’ [-Wimplicit-function-declaration]
          key = strdup(buf);
          ^
main.c:56:14: warning: assignment makes pointer from integer without a cast
          key = strdup(buf);
              ^
main.c:58:14: warning: assignment makes pointer from integer without a cast
          val = strdup(buf);
              ^
gcc -O0 -g -DDEBUG -std=c99 -Wall -Wextra -pedantic -Wshadow -Wstrict-overflow -Wstrict-prototypes -Wmissing-prototypes -Wno-missing-field-initializers -o hashtable hashtable.o main.o

1. Makefile

#CC      = clang
#CFLAGS  = -O0 -g -DDEBUG \
	     -std=c99 -Wall -Wextra -pedantic -Wshadow \
	     -Wstrict-overflow -Wstrict-prototypes -Wmissing-prototypes -Wno-missing-field-initializers

CC      = gcc
CFLAGS  = -O0 -g -DDEBUG \
	     -std=c99 -Wall -Wextra -pedantic -Wshadow \
	     -Wstrict-overflow -Wstrict-prototypes -Wmissing-prototypes -Wno-missing-field-initializers

SRCS    = hashtable.c main.c
OBJS    = $(SRCS:.c=.o)
HEADS   = hashtable.h
SED     = sed

all: hashtable

hashtable: $(OBJS)
	$(CC) $(CFLAGS) -o hashtable $(OBJS)

demo: hashtable-demo.o main.o
	$(CC) $(CFLAGS) -o hashtable-demo hashtable-demo.o main.o

test01: hashtable
	@./hashtable trace01.txt

test02: hashtable
	@./hashtable trace02.txt

test03: hashtable
	@./hashtable trace03.txt

test04: hashtable
	@./hashtable trace04.txt

test05: hashtable
	@./hashtable trace05.txt

test06: hashtable
	@./hashtable trace06.txt

diff01: hashtable
	@./hashtable trace01.txt | diff -y -W 80 - rtrace01.txt

diff02: hashtable
	@./hashtable trace02.txt | diff -y -W 80 - rtrace02.txt

diff03: hashtable
	@./hashtable trace03.txt | diff -y -W 80 - rtrace03.txt

diff04: hashtable
	@./hashtable trace04.txt | diff -y -W 80 - rtrace04.txt

diff05: hashtable
	@./hashtable trace05.txt | diff -y -W 80 - rtrace05.txt

diff06: hashtable
	@./hashtable trace06.txt | diff -y -W 80 - rtrace06.txt

leakcheck: hashtable
	@valgrind --leak-check=full ./hashtable trace06.txt

clean:
	rm -f $(OBJS) hashtable hashtable-demo hashtable-demo.o

format:
	clang-format -style=file -i $(SRCS) $(HEADS)

2. main.c

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

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-result"

int print_iter(char *key, void *val) {
   printf("%s -> %s\n", key, (char *)val);
   return 1;
}

void print_ht_stats(hashtable_t *ht) {
   bucket_t *b;
   unsigned long idx, len, max_len = 0, num_buckets = 0, num_chains = 0;
   for (idx = 0; idx < ht->size; idx++) {
      b = ht->buckets[idx];
      len = 0;
      while (b) {
         len++;
         num_buckets++;
         b = b->next;
      }
      if (len > 0) {
         num_chains++;
      }
      if (max_len < len) {
         max_len = len;
      }
   }
   printf("Num buckets = %lu\n", num_buckets);
   printf("Max chain length = %lu\n", max_len);
   printf("Avg chain length = %0.2f\n", (float)num_buckets / num_chains);
}

void eval_tracefile(char *filename) {
   FILE *infile;
   int ht_size;
   char buf[80], *key, *val;
   hashtable_t *ht;

   if ((infile = fopen(filename, "r")) == NULL) {
      printf("Error opening tracefile %s\n", filename);
      exit(1);
   }

   fscanf(infile, "%d", &ht_size);
   printf("Creating hashtable of size %d\n", ht_size);
   ht = make_hashtable(ht_size);

   while (fscanf(infile, "%s", buf) != EOF) {
      switch (buf[0]) {
      case 'p':
         fscanf(infile, "%s", buf);
         key = strdup(buf);
         fscanf(infile, "%s", buf);
         val = strdup(buf);
         printf("Inserting %s => %s\n", key, val);
         ht_put(ht, key, val);
         break;
      case 'g':
         fscanf(infile, "%s", buf);
         printf("Looking up key %s\n", buf);
         if ((val = ht_get(ht, buf))) {
            printf("Found value %s\n", val);
         } else {
            printf("Key not found\n");
         }
         break;
      case 'd':
         fscanf(infile, "%s", buf);
         printf("Removing key %s\n", buf);
         ht_del(ht, buf);
         break;
      case 'r':
         fscanf(infile, "%d", &ht_size);
         printf("Rehashing to %d buckets\n", ht_size);
         ht_rehash(ht, ht_size);
         break;
      case 'i':
         printf("Printing hashtable info\n");
         print_ht_stats(ht);
         break;
      default:
         printf("Bad tracefile directive (%c)", buf[0]);
         exit(1);
      }
   }
   free_hashtable(ht);
   fclose(infile);
}

int main(int argc, char *argv[]) {
   if (argc < 2) {
      printf("Usage: %s TRACEFILE_NAME\n", argv[0]);
      exit(0);
   }
   eval_tracefile(argv[1]);
   return 0;
}

#pragma GCC diagnostic pop

3. hashtable.h

#pragma once

typedef struct hashtable hashtable_t;
typedef struct bucket bucket_t;

struct bucket {
   char *key;
   void *val;
   bucket_t *next;
};

struct hashtable {
   unsigned long size;
   bucket_t **buckets;
};

unsigned long hash(char *str);

hashtable_t *make_hashtable(unsigned long size);
void ht_put(hashtable_t *ht, char *key, void *val);
void *ht_get(hashtable_t *ht, char *key);
void ht_del(hashtable_t *ht, char *key);
void ht_iter(hashtable_t *ht, int (*f)(char *, void *));
void ht_rehash(hashtable_t *ht, unsigned long newsize);
void free_hashtable(hashtable_t *ht);

4. hashtable.c

#include "hashtable.h"

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <assert.h>

#ifdef DEBUG
#define DEBUG_PRINT true
#else
#define DEBUG_PRINT false
#endif

#define DPRINTF(fmt, ...)                                                      \
   do {                                                                        \
      if (DEBUG_PRINT)                                                         \
         fprintf(stderr, "%s:%d:%s(): " fmt, __FILE__, __LINE__, __func__,     \
                 __VA_ARGS__);                                                 \
   } while (0)

/* Daniel J. Bernstein's "times 33" string hash function, from comp.lang.C;
   See https://groups.google.com/forum/#!topic/comp.lang.c/lSKWXiuNOAk */
unsigned long hash(char *str) {
   unsigned long hash = 5381;
   int c;

   while ((c = *str++))
      hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

   return hash;
}

hashtable_t *make_hashtable(unsigned long size) {
   hashtable_t *ht = malloc(sizeof(hashtable_t));

   ht->size = size;
   ht->buckets = calloc(size, sizeof(bucket_t *));

   return ht;
}

void ht_put(hashtable_t *ht, char *key, void *val) {
   assert(strnlen(key, 16) < 16);

   unsigned long idx = hash(key) % ht->size;

   bucket_t *b = ht->buckets[idx];
   while (b) {
      if (strncmp(key, b->key, 16) == 0) {
         DPRINTF("Replacing existing value for '%s'\n", key);
         b->val = val;
         return;
      }
      b = b->next;
   }

   DPRINTF("Inserting new value for '%s'\n", key);
   bucket_t *new = malloc(sizeof(bucket_t));

   new->key = key;
   new->val = val;
   new->next = ht->buckets[idx];
   ht->buckets[idx] = new;
}

void *ht_get(hashtable_t *ht, char *key) {
   assert(strnlen(key, 16) < 16);

   unsigned long idx = hash(key) % ht->size;
   bucket_t *b = ht->buckets[idx];

   while (b) {
      if (strcmp(b->key, key) == 0) {
         return b->val;
      }
      b = b->next;
   }
   return NULL;
}

void ht_iter(hashtable_t *ht, int (*f)(char *, void *)) {
   bucket_t *b;
   unsigned long i;
   for (i = 0; i < ht->size; i++) {
      b = ht->buckets[i];
      while (b) {
         if (!f(b->key, b->val)) {
            return; // abort iteration
         }
         b = b->next;
      }
   }
}

void free_hashtable(hashtable_t *ht) {
   free(ht); // FIXME: must free all substructures!
}

/* TODO */
void ht_del(hashtable_t *ht, char *key) {}

void ht_rehash(hashtable_t *ht, unsigned long newsize) {
   hashtable_t *working = make_hashtable(newsize);

   for (unsigned long i = 0; i < ht->size; i++) {
      bucket_t *b = ht->buckets[i];

      while (b) {
         ht_put(working, b->key, b->val);
         b = b->next;
      }
   }

   free_hashtable(ht);
}

5. Vagrantfile

# -*- mode: ruby -*-
# vi: set ft=ruby :

# All Vagrant configuration is done below. The "2" in Vagrant.configure
# configures the configuration version (we support older styles for
# backwards compatibility). Please don't change it unless you know what
# you're doing.
Vagrant.configure(2) do |config|
  # The most common configuration options are documented and commented below.
  # For a complete reference, please see the online documentation at
  # https://docs.vagrantup.com.

  # Every Vagrant development environment requires a box. You can search for
  # boxes at https://atlas.hashicorp.com/search.
  config.vm.box = "hashicorp/precise64"

  # Disable automatic box update checking. If you disable this, then
  # boxes will only be checked for updates when the user runs
  # `vagrant box outdated`. This is not recommended.
  # config.vm.box_check_update = false

  # Create a forwarded port mapping which allows access to a specific port
  # within the machine from a port on the host machine. In the example below,
  # accessing "localhost:8080" will access port 80 on the guest machine.
  # config.vm.network "forwarded_port", guest: 80, host: 8080

  # Create a private network, which allows host-only access to the machine
  # using a specific IP.
  #config.vm.network "private_network", ip: "123.123.123.123"

  # Create a public network, which generally matched to bridged network.
  # Bridged networks make the machine appear as another physical device on
  # your network.
  #config.vm.network "public_network", ip: "192.168.33.10", bridge: [
  #  "en0: Wi-Fi (AirPort)"
  #]

  # Share an additional folder to the guest VM. The first argument is
  # the path on the host to the actual folder. The second argument is
  # the path on the guest to mount the folder. And the optional third
  # argument is a set of non-required options.
  # config.vm.synced_folder "../data", "/vagrant_data"

  # Provider-specific configuration so you can fine-tune various
  # backing providers for Vagrant. These expose provider-specific options.
  # Example for VirtualBox:
  #
  # config.vm.provider "virtualbox" do |vb|
  #   # Display the VirtualBox GUI when booting the machine
  #   vb.gui = true
  #
  #   # Customize the amount of memory on the VM:
  #   vb.memory = "1024"
  # end
  #
  # View the documentation for the provider you are using for more
  # information on available options.

  config.vm.provider "vmware_fusion" do |v|
    v.vmx["memsize"] = "8192"
    v.vmx["numvcpus"] = "4"
   #v.gui = true
  end

  # Define a Vagrant Push strategy for pushing to Atlas. Other push strategies
  # such as FTP and Heroku are also available. See the documentation at
  # https://docs.vagrantup.com/v2/push/atlas.html for more information.
  # config.push.define "atlas" do |push|
  #   push.app = "YOUR_ATLAS_USERNAME/YOUR_APPLICATION_NAME"
  # end

  # Fix for “stdin: is not a tty”
  # /via https://github.com/mitchellh/vagrant/issues/1673#issuecomment-168205206
  config.vm.provision "fix-no-tty", type: "shell" do |s|
    s.privileged = false
    s.inline = "sudo sed -i '/tty/!s/mesg n/tty -s \\&\\& mesg n/' /root/.profile"
  end

  # Enable provisioning with a shell script. Additional provisioners such as
  # Puppet, Chef, Ansible, Salt, and Docker are also available. Please see the
  # documentation for more information about their specific syntax and use.
  config.vm.provision "shell", privileged: true, inline: <<-SHELL
    export DEBIAN_FRONTEND=noninteractive

    apt-get -q -y update

    apt-get -q -y install man-db manpages manpages-dev manpages-posix manpages-posix-dev glibc-doc

    apt-get -q -y install git zsh
  SHELL

  # This mess of B.S., constructed mostly from <http://apt.llvm.org>, is, as far as I can tell, The
  # Right Way to get non-ancient clang installed on Precise. (Why am I using Precise again? 'cuz
  # Vagrant says so? ಠ_ಠ)
  #
  # Yes, non-ancient clang requires slightly-less-ancient gcc to build ... which isn't available on
  # Precise ... so *that* has to be installed manually, *too*. -_-
  config.vm.provision "shell", privileged: true, inline: <<-SHELL
    export DEBIAN_FRONTEND=noninteractive

    apt-get -q -y install python-software-properties                                            2>&1

    add-apt-repository -y ppa:ubuntu-toolchain-r/test
    add-apt-repository -y 'deb http://apt.llvm.org/precise/ llvm-toolchain-precise-3.8 main'
    apt-get -q -y update

    #update-alternatives --remove-all gcc
    apt-get -q -y install gcc-4.9

    update-alternatives --install /usr/bin/gcc gcc /usr/bin/gcc-4.9 10
    update-alternatives --install /usr/bin/cc cc /usr/bin/gcc 30                                2>&1
    update-alternatives --set cc /usr/bin/gcc

    update-alternatives --config gcc

    gpg --keyserver http://apt.llvm.org/llvm-snapshot.gpg.key --recv-keys 15CF4D18AF4F7421      2>&1

    #update-alternatives --remove-all clang
    apt-get -q -y --force-yes install clang-3.8 lldb-3.8

    update-alternatives --install /usr/bin/clang clang /usr/bin/clang-3.8 10
    update-alternatives --install /usr/bin/cc cc /usr/bin/clang 40

    update-alternatives --config clang
  SHELL

  config.vm.provision "shell", privileged: false, inline: <<-SHELL
    ssh-keyscan -H github.com >>~/.ssh/known_hosts 2>&1
    git clone -q https://github.com/ELLIOTTCABLE/System.git ~/.system

    (cd ~/.system && rake)
    cat ~/.ssh~/authorized_keys >> ~/.ssh/authorized_keys

    echo "export SYSTEM='Ubuntu 12.04.1 Precise LTS'" >> ~/.profile.local
    echo "export COLOURIZE_AS='white'" >> ~/.profile.local
    echo "export SYSTEM_REPO=\"$HOME/.system\"" >> ~/.profile.local
  SHELL

  config.vm.provision "shell", privileged: true, inline: "chsh -s /bin/zsh vagrant"
  config.vm.provision "shell", privileged: false, inline: "zsh -ic 'zgen update'"
end