#include <u.h>
#include <libc.h>
#include <fcall.h>
#include "common.h"
#include "debug.h"
#include "utils.h"
#include "string.h"
#include "function.h"
#include "collection.h"
#include "array.h"
#include "set.h"
#include "dictionary.h"
#include "qidgenerator.h"

enum { DEBUG_QIDGENERATOR = false };


typedef struct RefDir
{
  uint count;
  Dir *d;
} RefDir;


RefDir *refdir_new(Dir *d)
{
  RefDir *result;
  assert_valid(d);
  result = (RefDir *)emallocz_fs(sizeof(*result)); 
  result->count = 1;
  result->d = d;
  return result;
}


void refdir_free(RefDir *self)
{
  if(self == nil)
  {
    return;
  }

  dir_free(self->d);
  free(self);
}


void refdir_ref(RefDir *self)
{
  ++(self->count);
}


uint refdir_deref(RefDir *self)
{
  assert_valid(self);
  assert(self->count > 0);
  --(self->count);
  if(self->count == 0)
  {
    refdir_free(self);
    return 0;
  }
  return self->count;
}

void refdir_void_deref(RefDir *self)
{
  assert_valid(self);
  refdir_deref(self);
}


typedef struct RefString
{
  uint count;
  char *str;
} RefString;

void refstring_init(RefString *self, char *str)
{
  assert_valid(self);
  assert_valid(str);
  self->count = 1;
  self->str = str;
}

RefString *refstring_new(char *str)
{
  RefString *result;
  assert_valid(str);

  result = (RefString *)emallocz_fs(sizeof(RefString));
  refstring_init(result, str);
  return result;
}

void refstring_free(RefString *self)
{
  if(self == nil)
  {
    return;
  }
  free(self->str);
  free(self);
}

void refstring_ref(RefString *self)
{
  ++(self->count);
}

uint refstring_deref(RefString *self)
{
  assert_valid(self);
  assert(self->count > 0);
  --(self->count);
  if(self->count == 0)
  {
    refstring_free(self);
    return 0;
  }
  return self->count;
}

void refstring_void_deref(RefString *self)
{
  assert_valid(self);
  refstring_deref(self);
}

bool refstring_isequal(void *p1, void *p2)
{
  RefString *self = (RefString *)p1;
  RefString *r = (RefString *)p2;
  assert_valid(self);
  assert_valid(r);

  return string_isequal(self->str, r->str);
}

uint refstring_hash(void *p)
{
  RefString *self = (RefString *)p;
  assert_valid(self);
  return string_hash(self->str);
}


static bool qidpath_isequal(void *p1, void *p2)
{
  uvlong *self = (uvlong *)p1;
  uvlong *v = (uvlong *)p2;
  assert_valid(self);
  assert_valid(v);

  return *self == *v;
}

static uint qidpath_hash(void *p)
{
  uvlong *self = (uvlong *)p;
  uint result;
  assert_valid(self);

  NOISE(DEBUG_QIDGENERATOR, "qidpath hash upper half: %ulld", 
    *self >> (sizeof(uint) * 8));
  result = (*self >> (sizeof(uint) * 8)) ^ (*self);
  NOISE(DEBUG_QIDGENERATOR, "qidpath hash %ulld to %ud", *self, result);
  return result;
}

static bool dir_isequal(void *p1, void *p2)
{
  Dir *self = (Dir *)p1;
  Dir *d = (Dir *)p2;
  assert_valid(self);
  assert_valid(d);

  return 
    (self->qid.path == d->qid.path) && 
    (self->qid.type == d->qid.type) &&
    (self->dev == d->dev) && 
    (self->type == d->type);
}

static uint dir_hash(void *p)
{
  uint result;
  Dir *self = (Dir *)p;
  assert_valid(self);
  result = 
    self->type + self->dev + self->qid.type + qidpath_hash(&(self->qid.path));
  NOISE(DEBUG_QIDGENERATOR, "dir_hash result: %ud", result);
  return result;
}


static bool dirs_areequal(void *p1, void *p2)
{
  int i;
  Array *a1 = (Array *)p1;
  Array *a2 = (Array *)p2;
  assert_valid(a1);
  assert_valid(a2);

  if(array_size(a1) != array_size(a2))
  {
    return false;
  }

  for(i = 0; i < array_size(a1); ++i)
  {
    if(!dir_isequal(array_at(a1, i), array_at(a2, i)))
    {
      return false;
    }
  }

  return true;
}

static collection_do_ret dirs_hash_each(void *p, void *arg)
{
  Dir *d = (Dir *)p;
  uint *hash = (uint *)arg;
  assert_valid(d);
  assert_valid(hash);

  *hash += dir_hash(d);
  return COLLECTION_DO_CONTINUE;
}

static uint dirs_hash(void *p)
{
  uint result = 0;
  Array *self = (Array *)p;
  assert_valid(self);

  array_do(self, dirs_hash_each, &result);
  NOISE(DEBUG_QIDGENERATOR, "dirs_hash result: %ud", result);
  return result;
}

struct QidGenerator
{
  Set *qidpaths;
  Dictionary *dirs2refdir;
  Dictionary *name2dirs;
  uvlong probebits;
};

QidGenerator *qidgenerator_new(void)
{
  QidGenerator *result = (QidGenerator *)malloc(sizeof(QidGenerator));
  result->qidpaths = set_new(qidpath_isequal, qidpath_hash);
  result->dirs2refdir = dictionary_new(dirs_areequal, dirs_hash);
  result->name2dirs = dictionary_new(refstring_isequal, refstring_hash);
  result->probebits = 0;
  return result;
}

static void dirs_free(Array *self)
{
  if(self == nil)
  {
    return;
  }

  array_free_with(self, (functionunary)dir_free);
}

void qidgenerator_free(QidGenerator *self)
{
  if(self == nil)
  {
    return;
  }

  dictionary_free_with(self->dirs2refdir, 
    (functionunary)dirs_free, (functionunary)refdir_void_deref);
  dictionary_free_with(self->name2dirs, 
    (functionunary)refstring_void_deref, nil);
  set_free(self->qidpaths);
  free(self);
}

/** @todo keep a counter to make sure we never end in infinite loop */
static void qidgenerator_new_qid(QidGenerator *self, Array *dirs, Dir *d)
{
  enum { PROBED_BYTES = 2,  UNPROBED_BYTES = (sizeof(uvlong) - PROBED_BYTES)};

  uvlong *path;
  assert_valid(self);
  assert_valid(dirs);
  assert_valid(d);

  path = &(d->qid.path);
  while(set_includes(self->qidpaths, path))
  {
    INFO(DEBUG_QIDGENERATOR, "qidgnerator_new_qid detects collision with %ulld",
      *path);
    ++(self->probebits);
    if(self->probebits >= (1 << (PROBED_BYTES * 8)))
    {
      INFO(DEBUG_QIDGENERATOR, "qidgenerator_new_qid probebits wrap around");
      self->probebits = 1;
    }

    *path |= self->probebits << (UNPROBED_BYTES * 8);
    INFO(DEBUG_QIDGENERATOR, "qidgenerator_new_qid generating new path: %ulld",
      *path);
  }

  INFO(DEBUG_QIDGENERATOR, "qidgenerator_new_qid adding path: %ulld", *path);
  set_add(self->qidpaths, path);
}


static void dirs_deref(Array *self, QidGenerator *qidgen)
{
  bool result;
  RefDir *ref;
  uvlong path;
  assert_valid(self);
  assert_valid(qidgen);

  result = dictionary_get(qidgen->dirs2refdir, self, &ref);
  assert(result);

  path = ref->d->qid.path;
  if(refdir_deref(ref) == 0)
  {
    dictionary_remove(qidgen->dirs2refdir, self);
    dirs_free(self);
    set_remove(qidgen->qidpaths, &path);
  }
}

static char *dir_updatename(char *self, char *new)
{
  assert_valid(self);
  assert_valid(new);

  if(strcmp(self, new) == 0)
  {
    return self;
  }

  if(strlen(self) > strlen(new))
  {
    return strcpy(self, new);
  }

  free(self);
  return estrdup_fs(new);
}

static bool dir_update(Dir *self, Dir *new)
{
  bool ischanged;
  char *name;
  char *uid;
  char *gid;
  char *muid;
  assert_valid(self);
  assert_valid(new);
  assert(dir_isequal(self, new));

  ischanged = 
    (self->qid.vers != new->qid.vers) ||
    (self->mode != new->mode) ||
    // (self->atime != new->atime) ||
    (self->mtime != new->mtime) ||
    (self->length != new->length);

  name = self->name;
  uid = self->uid;
  gid = self->gid;
  muid = self->muid;

  memcpy(self, new, sizeof(Dir));
  self->name = dir_updatename(name, new->name);
  self->uid = dir_updatename(uid, new->uid);
  self->gid = dir_updatename(gid, new->gid);
  self->muid = dir_updatename(muid, new->muid);

  ischanged = 
    ischanged ||
    (name != self->name) ||
    (uid != self->uid) ||
    (gid != self->gid) ||
    (muid != self->muid);
  return ischanged;
}

/* @todo get the latest time */
static void qidgenerator_update_dir(Array *dirs, Dir *d, bool ischanged)
{
  Dir *source;
  assert_valid(dirs);
  assert_valid(d);
  assert(array_size(dirs) > 0);

  source = array_at(dirs, 0);
  if(ischanged)
  {
    ++(d->qid.vers);
  }
  d->mode = source->mode;
  d->atime = source->atime;
  d->mtime = source->mtime;
  d->length = source->length;
  d->name = dir_updatename(d->name, source->name);
  d->uid = dir_updatename(d->uid, source->uid);
  d->gid = dir_updatename(d->gid, source->gid);
  d->muid = dir_updatename(d->muid, source->muid);
}

static Dir *qidgenerator_new_dir(QidGenerator *self, Array *dirs)
{
  Dir *result;
  assert_valid(self);
  assert_valid(dirs);
  assert(array_size(dirs) > 0);

  result = (Dir *)emallocz_fs(sizeof(*result));
  dir_copy((Dir *)array_at(dirs, 0), result);
  qidgenerator_update_dir(dirs, result, false);
  /** @todo need to get the latest time */
  return result;
}


/** @todo need to check any changes and update refresult's vers accordingly */
static void dirs_update(Array *self, Array *new, Dictionary *dirs2refdir)
{
  bool result;
  bool ischanged = false;
  int i;
  RefDir *ref = nil;
  assert_valid(self);
  assert_valid(new);
  assert_valid(dirs2refdir);
  assert(array_size(self) == array_size(new));

  for(i = 0; i < array_size(self); ++i)
  {
    ischanged = 
      ischanged ||
      dir_update(array_at(self, i), array_at(new, i));
  }

  result = dictionary_get(dirs2refdir, self, (void **)&ref);
  assert(result);
  assert_valid(ref);

  qidgenerator_update_dir(self, ref->d, ischanged);
}



static collection_do_ret dirs_copy_each(void *p, void *arg)
{
  Dir *d;
  assert_valid(p);
  assert_valid(arg);

  d = (Dir *)emallocz_fs(sizeof(*d));
  dir_copy((Dir *)p, d);
  array_add((Array *)arg, d);
  return COLLECTION_DO_CONTINUE;
}

static Array *dirs_copy(Array *self)
{
  Array *result;
  assert_valid(self);

  result = array_new_size(array_size(self));
  array_do(self, dirs_copy_each, result);
  return result;
}

RefDir *qidgenerator_add_dirs(
  QidGenerator *self, RefString *reffilename, Array *dirs)
{
  RefDir *result;
  Array *newdirs;
  assert_valid(self);
  assert_valid(reffilename);
  assert_valid(dirs);
  
  NOISE(DEBUG_QIDGENERATOR, "entering qidgenerator_add_dirs");
  result = refdir_new(qidgenerator_new_dir(self, dirs));

  NOISE(DEBUG_QIDGENERATOR, "qidgenerator_add_dirs generating qid");
  qidgenerator_new_qid(self, dirs, result->d);

  NOISE(DEBUG_QIDGENERATOR, "qidgenerator_add_dirs copying dirs");
  newdirs = dirs_copy(dirs);

  NOISE(DEBUG_QIDGENERATOR, "qidgenerator_add_dirs updating dirs2refdir");
  dictionary_add(self->dirs2refdir, newdirs, result);

  NOISE(DEBUG_QIDGENERATOR, "qidgenerator_add_dirs updating name2dirs");
  dictionary_add(self->name2dirs, reffilename, newdirs);

  NOISE(DEBUG_QIDGENERATOR, "leaving qidgenerator_add_dirs with result: %uX",
    result);
  return result;
}

Dir *qidgenerator_get(QidGenerator *self, char *filename, Array *dirs)
{
  Array *d = nil;
  Array *old = dirs;
  RefDir *refresult = nil;
  RefString refstring;
  assert_valid(self);
  assert_valid(filename);
  assert_valid(dirs);
  assert(array_size(dirs) > 0);
  
  refstring_init(&refstring, filename);
  NOISE(DEBUG_QIDGENERATOR, 
    "entering qidgenerator_get with filename: %s", filename);
  if(dictionary_get(self->name2dirs, &refstring, &d))
  {
    /* if dirs == d, then update dirs
     * else 
     *
     *   if found dirs in dirs2refdir, 
     *    increase ref, update filename -> dirs , and update dirs
     *   else 
     *    free d=>refdir
     *    create new qid
     */

    NOISE(DEBUG_QIDGENERATOR, "qidgenerator_get got %s Dir", filename);
    if(dirs_areequal(d, dirs))
    {
      NOISE(DEBUG_QIDGENERATOR, "qidgenerator_get dirs equal");
      dirs_update(d, dirs, self->dirs2refdir);
      dictionary_get(self->dirs2refdir, d, (void **)&refresult);
    }
    else
    {
      if(dictionary_get_key_value(self->dirs2refdir, &old, (void **)&refresult))
      {
        NOISE(DEBUG_QIDGENERATOR, "qidgenerator_get dirs exists from others");
        refdir_ref(refresult);
        dirs_update(old, dirs, self->dirs2refdir);
        dictionary_add(self->name2dirs, &refstring, old);
      }
      else
      {
        NOISE(DEBUG_QIDGENERATOR, "qidgenerator_get dirs does not exist");
        refresult = qidgenerator_add_dirs(self, &refstring, dirs);
      }

      NOISE(DEBUG_QIDGENERATOR, "qidgenerator_get dereffing old dirs");
      dirs_deref(d, self);
    }
  }
  else if(dictionary_get_key_value(
    self->dirs2refdir, &old, (void **)&refresult))
  {
    /* increase ref, and add filename -> dirs */
    NOISE(DEBUG_QIDGENERATOR, 
      "qidgenerator_get new mapping dirs exists from others");
    refdir_ref(refresult);
    dirs_update(old, dirs, self->dirs2refdir);
    dictionary_add(self->name2dirs, 
      refstring_new(estrdup_fs(filename)), old);
  }
  else
  {
    NOISE(DEBUG_QIDGENERATOR, "qidgenerator_get new mapping generating");
    refresult = qidgenerator_add_dirs(self, 
      refstring_new(estrdup_fs(filename)), dirs);
  }

  NOISE(DEBUG_QIDGENERATOR, "qidgenerator_get about to return");
  return dir_clone(refresult->d);
}

void qidgenerator_file_ref(QidGenerator *self, char *filename)
{
  bool result;
  RefString refstring;
  RefString *key = &refstring;
  assert_valid(self);
  assert_valid(filename);

  NOISE(DEBUG_QIDGENERATOR, "entering qidgenerator_file_ref with: %s",
    filename);
  refstring_init(key, filename);
  result = dictionary_get_key_value(self->name2dirs, (void **)&key, nil);

  NOISE(DEBUG_QIDGENERATOR, "qidgenerator_file_ref finding name result: %d",
    result);
  assert(result);
  refstring_ref(key);
}

void qidgenerator_file_deref(QidGenerator *self, char *filename)
{
  bool result;
  RefString refstring;
  RefString *key = &refstring;
  Array *value = nil;
  assert_valid(self);
  assert_valid(filename);

  NOISE(DEBUG_QIDGENERATOR, "entering qidgenerator_file_deref with: %s",
    filename);
  refstring_init(key, filename);
  result = dictionary_get_key_value(
    self->name2dirs, (void **)&key, (void **)&value);

  NOISE(DEBUG_QIDGENERATOR, "qidgenerator_file_deref finding name result: %d",
    result);
  assert(result);

  if(refstring_deref(key) == 0)
  {
    NOISE(DEBUG_QIDGENERATOR, "qidgenerator_file_deref deleting");
    key = &refstring;
    result = dictionary_remove(self->name2dirs, key);
    assert(result);
    dirs_deref(value, self);
  }
}