/* util.c: Utility functions for libRUIN
 * Copyright (C) 2007 Julian Graham
 *
 * libRUIN is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * libRUIN is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with libRUIN; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA 
 */

#include <ctype.h>
#include <libguile.h>
#include <math.h>
#include <pthread.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <sys/time.h>
#include <time.h>

#include "util.h"
#include "window.h"

pthread_mutex_t _ruin_util_id_lock;

int ruin_util_hash_hash (char *k, int table_size) {
  unsigned int a, b, c, len, length;

  len = strlen (k);
  length = len;
  a = b = 0x9e3779b9;
  c = 0;
  
  while (len >= 12) {
    a += (k[0] + ((unsigned int) k[1] << 8) + ((unsigned int) k[2] << 16) +
	  ((unsigned int) k[3] << 24));
    b += (k[4] + ((unsigned int) k[5] << 8) + ((unsigned int) k[6] << 16) +
	  ((unsigned int) k[7] << 24));
    c += (k[8] + ((unsigned int) k[9] << 8) + ((unsigned int) k[10] << 16) +
	  ((unsigned int) k[11] << 24));
    RUIN_UTIL_HASH_MIX (a, b, c);
    k += 12; 
    len -= 12;
  }
  
  c += length;
  switch (len) {              /* all the case statements fall through */
  case 11: c += ((unsigned int) k[10] << 24);
  case 10: c += ((unsigned int) k[9] << 16);
  case 9: c += ((unsigned int) k[8] << 8);
  case 8: b += ((unsigned int) k[7] << 24);
  case 7: b += ((unsigned int) k[6] << 16);
  case 6: b += ((unsigned int) k[5] << 8);
  case 5: b += k[4];
  case 4: a += ((unsigned int) k[3] << 24);
  case 3: a += ((unsigned int) k[2] << 16);
  case 2: a += ((unsigned int) k[1] << 8);
  case 1: a += k[0];
  default:
    break;
  }

  RUIN_UTIL_HASH_MIX (a, b, c);

  return (c & RUIN_UTIL_HASH_MASK ((int) (log ((double) table_size))));
}

void ruin_util_hash_insertion_helper(ruin_util_hash *hash, int index, 
				     char *key, void *value) {
  hash->keys = realloc(hash->keys, sizeof(char *) * ++hash->num_keys);
  hash->values = realloc(hash->values, sizeof(char *) * hash->num_keys);
  hash->keys[hash->num_keys - 1] = strdup(key);
  hash->values[hash->num_keys - 1] = value;
  hash->map[index] = hash->num_keys - 1;
  return;
}

void ruin_util_hash_insert(ruin_util_hash *hash, char *key, void *value) {
  int hashed_index, mapped_index, i, new_table_size = 0;
  int *new_map;
  if (((hash == NULL) || (key == NULL)) || (value == NULL))
    return;
  pthread_mutex_lock(hash->lock);
  hashed_index = ruin_util_hash_hash(key, hash->table_size);
  if (hash->map[hashed_index] == -1) {
    ruin_util_hash_insertion_helper(hash, hashed_index, key, value);
    pthread_mutex_unlock(hash->lock);
    return;
  }
  else {
    mapped_index = hash->map[hashed_index];
    if (strcmp(hash->keys[mapped_index], key) == 0) {
      free(hash->values[mapped_index]);
      hash->values[mapped_index] = value;
      pthread_mutex_unlock(hash->lock);
      return;
    }
    for (i = hashed_index + 1; i < hash->table_size; i++) {
      if (hash->map[i] == -1) {
	ruin_util_hash_insertion_helper(hash, i, key, value);
	pthread_mutex_unlock(hash->lock);
	return;
      }
      else if(strcmp(hash->keys[hash->map[i]], key) == 0) {
	free(hash->values[hash->map[i]]);
	hash->values[hash->map[i]] = value;
	pthread_mutex_unlock(hash->lock);
	return;
      }
    }
    for (i = 0; i < hashed_index; i++) {
      if (hash->map[i] == -1) {
	ruin_util_hash_insertion_helper(hash, i, key, value);
	pthread_mutex_unlock(hash->lock);
	return;
      }
      else if(strcmp(hash->keys[hash->map[i]], key) == 0) {
	free(hash->values[hash->map[i]]);
	hash->values[hash->map[i]] = value;
	pthread_mutex_unlock(hash->lock);
	return;
      }
    }

    /* Uh-oh... time to grow the hash... */
    new_table_size = hash->table_size * RUIN_UTIL_HASH_GROWTH_FACTOR;
    new_map = malloc(sizeof(int) * new_table_size);
    for (i = 0; i < new_table_size; i++)
      new_map[i] = -1;
    for (i = 0; i < hash->num_keys; i++) {
      int new_hashed_index = 
	ruin_util_hash_hash(hash->keys[i], new_table_size);
      if (new_map[new_hashed_index] == -1)
	new_map[new_hashed_index] = i;
      else {
	int j, found_null = FALSE;
	for (j = new_hashed_index + 1; j < new_table_size; j++)
	  if (new_map[j] == -1) {
	    new_map[j] = i;
	    found_null = TRUE;
	    break;
	  }
	if (!found_null) {
	  for (j = 0; j < new_hashed_index; j++)
	    if (new_map[j] == -1) {
	      new_map[j] = i;
	      break;
	    }
	}
      }
    }
    free(hash->map);
    hash->map = new_map;
    hash->table_size = new_table_size;
    pthread_mutex_unlock(hash->lock);
    ruin_util_hash_insert(hash, key, value);
    return;
  }  
}

void *ruin_util_hash_retrieve(ruin_util_hash *hash, char *key) {
  int hashed_index, mapped_index, i, found_null;
  if ((hash == NULL) || (key == NULL))
    return NULL;
  hashed_index = ruin_util_hash_hash(key, hash->table_size);
  pthread_mutex_lock(hash->lock);
  if (hash->map[hashed_index] == -1) {
    pthread_mutex_unlock(hash->lock);
    return NULL;
  }
  mapped_index = hash->map[hashed_index];
  if (strcmp(hash->keys[mapped_index], key) == 0) {
    pthread_mutex_unlock(hash->lock);
    return hash->values[mapped_index];
  }
  found_null = FALSE;
  for (i = hashed_index + 1; i < (hash->table_size - 1); i++) {
    if (hash->map[i] == -1) {
      found_null = TRUE;
      break;
    }
    mapped_index = hash->map[i];
    if (strcmp(hash->keys[mapped_index], key) == 0) {
      pthread_mutex_unlock(hash->lock);
      return hash->values[mapped_index];
    }
  }
  if (found_null) {
    pthread_mutex_unlock(hash->lock);
    return NULL;
  }
  for (i = 0; i < hashed_index; i++) {
    if (hash->map[i] == -1) {
      pthread_mutex_unlock(hash->lock);
      return NULL;
    }
    mapped_index = hash->map[i];
    if (strcmp(hash->keys[mapped_index], key) == 0) {
      pthread_mutex_unlock(hash->lock);
      return hash->values[mapped_index];
    }
  }
  pthread_mutex_unlock(hash->lock);
  return NULL;
}

void _ruin_util_hash_remove(ruin_util_hash *hash, char *key) {
  int i;
  for (i = 0; i < hash->num_keys; i++) {
    if (strcmp(hash->keys[i], key) == 0) {
      int j;
      hash->keys[i] = NULL;
      hash->values[i] = NULL;
      if ((hash->num_keys == 1) || (i == hash->num_keys - 1)) {
	for (j = 0; j < hash->table_size; j++)
	  if (hash->map[j] == i) {
	    hash->map[j] = -1;
	    break;
	  }
	hash->num_keys--;
      }
      else {
	int old_map_index = -1;
	for (j = 0; j < hash->table_size; j++)
	  if (hash->map[j] == hash->num_keys - 1) {
	    old_map_index = j;
	    break;
	  }	
	hash->map[old_map_index] = -1;
	hash->keys[i] = hash->keys[hash->num_keys - 1];
	hash->keys[hash->num_keys - 1] = NULL;
	hash->values[i] = hash->values[hash->num_keys - 1];
	hash->values[hash->num_keys - 1] = NULL;
	hash->num_keys--;
      }
      break;
    }
  }
}

void ruin_util_hash_remove(ruin_util_hash *hash, char *key) {
  if ((hash == NULL) || (key == NULL))
    return;
  pthread_mutex_lock(hash->lock);
  _ruin_util_hash_remove(hash, key);
  pthread_mutex_unlock(hash->lock);
  return;
}

void ruin_util_hash_clear(ruin_util_hash *hash) {
  int i;
  if (hash == NULL)
    return;
  pthread_mutex_lock(hash->lock);
  for (i = 0; i < hash->num_keys; i++) {
    if (hash->keys[i] == NULL)
      continue;
    else {
      _ruin_util_hash_remove(hash, hash->keys[i]);
      i = 0;
    }
  }
  pthread_mutex_unlock(hash->lock);
}

char **ruin_util_hash_get_keys(ruin_util_hash *hash, int *key_count) {
  int i;
  char **key_list;
  if (hash == NULL)
    return NULL;
  pthread_mutex_lock(hash->lock);
  if (key_count != NULL)
    *key_count = hash->num_keys;
  key_list = malloc(sizeof(char *) * hash->num_keys);
  for (i = 0; i < hash->num_keys; i++)
    key_list[i] = strdup(hash->keys[i]);
  pthread_mutex_unlock(hash->lock);
  return key_list;
}

ruin_util_hash *ruin_util_hash_new() {
  int i;
  ruin_util_hash *hash = calloc(1, sizeof(ruin_util_hash));
  hash->lock = malloc(sizeof(pthread_mutex_t));
  pthread_mutex_init(hash->lock, NULL);
  hash->table_size = RUIN_UTIL_HASH_DEFAULT_SIZE;
  hash->num_keys = 0;
  hash->map = malloc(sizeof(int) * hash->table_size);
  for (i = 0; i < hash->table_size; i++)
    hash->map[i] = -1;
  hash->keys = NULL;
  hash->values = NULL;
  return hash;
}

void ruin_util_hash_free(ruin_util_hash *hash) {
  pthread_mutex_lock(hash->lock);
  free(hash->map);
  pthread_mutex_unlock(hash->lock);
  pthread_mutex_destroy(hash->lock);
  return;
}

/* Here are the list functions. */

ruin_util_list *ruin_util_list_new(void *data) {
  ruin_util_list *foo = calloc(1, sizeof(ruin_util_list));
  foo->data = data;
  return foo;
}
 
int ruin_util_list_length(ruin_util_list *list) {
  if (list != NULL)
    return 1 + ruin_util_list_length(list->next);
  return 0;
}

ruin_util_list *ruin_util_list_push_front(ruin_util_list *head,
					  ruin_util_list *new_head) {
  new_head->next = head;
  return new_head;
}

ruin_util_list *ruin_util_list_append(ruin_util_list *head,
				      ruin_util_list *new_tail) {
  if (head == NULL)
    return new_tail;
  if (head->next != NULL)
    (void) ruin_util_list_append(head->next, new_tail);
  else head->next = new_tail;
  return head;
}

ruin_util_list *ruin_util_list_get_ith(ruin_util_list *head, int i) {
  if (head == NULL || i == 0)
    return head;
  return ruin_util_list_get_ith(head->next, i - 1);
}

void ruin_util_list_free(ruin_util_list *head) {
  ruin_util_list *next = head->next;
  free(head);
  if (next != NULL)
    ruin_util_list_free(next);
}

/* And some string conversion functions. */

char *ruin_util_int_to_string (int fd) {
  char *out = NULL;
  int num_digits = 0;
  int i;
  if (fd < 0)
    return NULL;
  if (fd == 0)
    num_digits = 1;
  else for (i = 1;; i *= 10) {
    if (fd >= i)
      num_digits += 1;
    else break;
  }
  out = calloc(1, sizeof(char) * (num_digits + 1));
  (void) snprintf(out, num_digits + 1, "%d", fd);
  out = realloc(out, sizeof(char) * (strlen(out) + 1));
  return out;
}

char *ruin_util_ptr_to_string(void *ptr) {
  int num_digits = (sizeof(void *) * 2) + 2;
  char *out = calloc(1, sizeof(char) * (num_digits + 1));
  (void) snprintf(out, num_digits + 1, "%p", ptr);
  return out;
}

char *ruin_util_long_to_string(long value) {
  char *out = NULL;
  int num_digits = 0;
  int i;
  if (value < 0)
    return NULL;
  if (value == 0)
    num_digits = 1;
  else for (i = 1;; i *= 10) {
    if (value >= i)
      num_digits += 1;
    else break;
  }
  out = malloc(sizeof(char) * (num_digits + 1));
  (void) snprintf(out, num_digits + 1, "%ld", value);
  return out;
}

void *ruin_util_string_to_ptr(char *ptr) {
  void *result;
  if((ptr != NULL) && (sscanf(ptr, "%p", &result) == 1))
    return result;
  return NULL;
}

long ruin_util_generate_id() {
  long return_val;
  static long next_id = 0;
  pthread_mutex_lock(&_ruin_util_id_lock);
  return_val = next_id;
  next_id++;
  pthread_mutex_unlock(&_ruin_util_id_lock);
  return return_val;
}

void ruin_util_log(ruin_window_t *w, char *msg, ...) {
  va_list args;
  va_start(args, msg);
  if (w->log != NULL) {
    fprintf(w->log, "window %ld: ", w->internal_id);
    vfprintf(w->log, msg, args);
    fprintf(w->log, "\n");
    fflush(w->log); 
  }
  va_end(args);
}

/* Somewhat inefficient; refactor to minimize use of realloc()? */

char *ruin_util_arabic_to_roman(int arabic, int use_upper) {
  int i = 0, len = 0;
  char *ret = NULL;
  static int digs[] = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
  static char *strsu[] = 
    { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
  static char *strsl[] =
    { "m", "cm", "d", "cd", "c", "xc", "l", "xl", "x", "ix", "v", "iv", "i" };
  if (arabic > 1000)
    return NULL;
  for (i = 0; i < 13; i++) {
    while (arabic >= digs[i]) {
      int slen = strlen(strsu[i]);
      arabic -= digs[i];
      ret = realloc(ret, len + slen + 1);
      strncpy(ret + len, use_upper ? strsu[i] : strsl[i], slen);
      len += slen;
    }
  }
  ret = realloc(ret, len + 1);
  ret[len] = 0;
  return ret;
}

char *ruin_util_get_parent_directory(char *filename) {
  char *rstr = NULL;
  char *abs_path = malloc(sizeof(char) * PATH_MAX);
  char *ret = NULL;
  realpath(filename, abs_path);
  rstr = strrchr(abs_path, '/');
  ret = calloc(rstr - abs_path + 1, sizeof(char));
  strncat(ret, abs_path, rstr - abs_path);
  free(abs_path);
  return ret;
}

long ruin_util_current_time_millis() {
  struct timeval tv = { 0, 0 };
  (void) gettimeofday(&tv, NULL);
  return (tv.tv_sec * 1000) + (tv.tv_usec / 1000);
}

SCM ruin_util_string2scm(char *str) {
  return scm_mem2string(str, strlen(str));
}