#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <fcntl.h>
#include <unistd.h>
#include <pthread.h>

#define HT_SIZE 256
#define NTHREADS 4
#define MAT_SIZE 10

int size = -1;
double ** A = NULL;
double ** B = NULL;
double ** C = NULL;

/* a ht_entry counts the number of memory access to an address */
struct ht_entry {
  // uintptr_t is an address (void*) whose comparison operators (<, >, ...) are valid
  uintptr_t addr;
  _Atomic int nb_access;
  struct ht_entry* next;
};

/* a hashtable contains an array of list
 */
struct hashtable {
  pthread_mutex_t mutexes[HT_SIZE];
  struct ht_entry *entrys[HT_SIZE];
};

struct hashtable ht;


/* compute the hash of an pointer */
uint8_t hash(uintptr_t value) {
  uint8_t res = 0;
  for(int i = 0; i< sizeof(uintptr_t); i++) {
    int bits = i*8;
    uint8_t b = (value & ((uintptr_t)0xff << bits))  >>  bits;
    res ^= b;
  }

  return res;
}

/* Initialize a hashtable */
void ht_init(struct hashtable *ht) {
  for(int i = 0; i<HT_SIZE; i++) {
    ht->entrys[i] = NULL;
    pthread_mutex_init(&ht->mutexes[i], NULL);
  }
    
}

//#define DEBUG 1
/* Allocate a new hashtable entry */
struct ht_entry * alloc_entry(uintptr_t addr) {
  struct ht_entry* n = malloc(sizeof(struct ht_entry));
  n->addr = (uintptr_t) addr;
  n->nb_access = 1;
  n->next = NULL;

#if DEBUG
  printf("New entry: %lx (hash:%d, nb_access: %d)\n", addr, hash(addr), n->nb_access);
#endif
  return n;
}

/* Update a hashtable entry */
void update_ht_entry(struct ht_entry* e) {
  e->nb_access++;

#if DEBUG
  printf("Hit %lx (hash:%x, nb_access: %d)\n", e->addr, hash(e->addr), e->nb_access);
#endif
}

void print_list(struct hashtable *ht, int index) {
  printf("\tChecking list %d:\n", index);
  struct ht_entry* cur = ht->entrys[index];
  while(cur) {
    printf("{%p, %d} ", (void*)cur->addr, cur->nb_access);
    cur= cur->next;
  }
  printf("\n");
}

/* Insert an address to the hashtable. If the address already is in the hashtable,
   increment its number of accesses */
void ht_insert(struct hashtable *ht, void* addr) {
  uintptr_t addr_value = (uintptr_t)addr;

  /* The address is inserted in the ht->entry[index].
   * The index is computed based on the hash of the address.
   */
  int index = hash(addr_value);

  pthread_mutex_lock(&ht->mutexes[index]);
  if(ht->entrys[index] == NULL){
    /* no entry with this hash. Create one */
    ht->entrys[index] = alloc_entry(addr_value);
    goto out;
  }

  /* There's at least one entry whose hash is index.
   * Now we need to find the entry whose addr is addr.
   */

  if(ht->entrys[index]->addr == addr_value) {
    /* addr is the first entry */
    update_ht_entry(ht->entrys[index]);
    goto out;
  }

  /* now, search the addr in the entry list */
  struct ht_entry* cur = ht->entrys[index];
  struct ht_entry* next = cur->next;

  /* We sort the entry list using the addr. As soon as we find an
     address greater than addr, we can stop. */
  while(next && next->addr > addr_value) {
    next = next->next;
    cur = cur->next;
  }

  if(next)
    if(next->addr == addr_value) {
      /* we found the entry corresponding to addr */
      update_ht_entry(next);
      goto out;
    }

  /* addr was not found. allocate a new entry */
  struct ht_entry* new_entry = alloc_entry(addr_value);
  new_entry->next = cur->next;
  cur->next = new_entry;
 out:
  pthread_mutex_unlock(&ht->mutexes[index]);
  //if(index == 4)
  //  print_list(ht, index);
}


/* store a memory access and read a value */
double get_value(double* d){
  ht_insert(&ht, d);
  return *d;
}

/* matrix multiply
 * perform A = B*C where A, B, and C are (size x size) matrices
 */
void mat_mul(double** A, double **B, double **C, int size, int thread_id) {
  int low_i = (size/NTHREADS)*thread_id;
  int high_i = (size/NTHREADS)*(thread_id + 1);
  if(thread_id == NTHREADS-1)
    high_i = size;

  for(int i=low_i; i < high_i; i++) {
    for(int j=0; j<size; j++) {
      A[i][j] = 0;
      for(int k=0; k<size; k++) {
	A[i][k] = get_value(&A[i][k]) + (get_value(&B[i][k]) * get_value(&C[j][k]));
      }
    }
  }
}


void* thread_function(void* arg) {
  static _Atomic int nb_threads = 0;
  int thread_id = nb_threads++;

  mat_mul(A, B, C, size, thread_id);

  return NULL;
}

/* allocate a (size x size) matrix */
double** alloc_mat(int size, int value) {
  double**res = malloc(sizeof(double*)*size);
  for(int i = 0; i<size; i++) {
    res[i] = malloc(sizeof(double)*size);
    for(int j = 0; j<size; j++) {
      res[i][j] = value;
    }
  }
  return res;
}

/* write the content of the hashtable in a file */
void dump_stats(struct hashtable* ht, const char* filename) {
  int fd = open(filename, O_WRONLY|O_CREAT|O_TRUNC,  S_IWUSR|S_IRUSR);
  if(fd<0) {
    perror("open failed\n");
    exit(EXIT_FAILURE);
  }

  int nb_entries = 0;
  for(int i=0;i<HT_SIZE; i++) {
    struct ht_entry* h = ht->entrys[i];
    while(h) {
#define DEBUG 1
#if DEBUG
      nb_entries++;
      printf("%p: %d\n", (void*)h->addr, h->nb_access);
#endif
      write(fd, &h->addr, sizeof(uintptr_t));
      write(fd, &h->nb_access, sizeof(int));
      h = h->next;
    }
  }
  close(fd);
#if DEBUG
  printf("There are %d entries in the hashtable\n", nb_entries);
#endif
}

int main(int argc, char**argv) {
  if(argc < 2) {
    fprintf(stderr, "Usage: %s filename\n", argv[0]);
    return EXIT_FAILURE;
  }
  ht_init(&ht);

  size = MAT_SIZE;
  A = alloc_mat(size, 0);
  B = alloc_mat(size, 1);
  C = alloc_mat(size, 2);

  pthread_t tid[NTHREADS];
  for(int i=0; i<NTHREADS; i++) {
    pthread_create(&tid[i], NULL, thread_function, NULL);
  }

  for(int i=0; i<NTHREADS; i++) {
    pthread_join(tid[i], NULL);
  }

  dump_stats(&ht, argv[1]);

  return EXIT_SUCCESS;
}