/****************************************************************************
**  SIONLIB     http://www.fz-juelich.de/jsc/sionlib                       **
*****************************************************************************
**  Copyright (c) 2008-2019                                                **
**  Forschungszentrum Juelich, Juelich Supercomputing Centre               **
**                                                                         **
**  See the file COPYRIGHT in the package base directory for details       **
****************************************************************************/

#define _XOPEN_SOURCE 700

#include <stdio.h>
#include <stdlib.h>

#include "sion_const.h"
#include "sion_debug.h"
#include "sion_error_handler.h"
#include "sion_keyvalue_table.h"

typedef enum {
  KEYVALUE_TABLE_ENTRY_STATE_USED,
  KEYVALUE_TABLE_ENTRY_STATE_FREE,
  KEYVALUE_TABLE_ENTRY_STATE_UNKNOWN
} sion_keyvalue_table_entry_state_t;

struct _sion_keyvalue_table_entry_struct;

typedef struct _sion_keyvalue_table_entry_struct _sion_keyvalue_table_entry;

struct _sion_keyvalue_table_struct {
  int used;
  int size;
  int num_added_entries;

  /* for iterator by index */
  int iterator_lastreadindex;
  _sion_keyvalue_table_entry *iterator_lastreadentry;

  /* for iterator by store orde */
  _sion_keyvalue_table_entry *iterator_next;
  _sion_keyvalue_table_entry *iterator_head;
  _sion_keyvalue_table_entry *iterator_tail;

  _sion_keyvalue_table_entry *entries;
};

struct _sion_keyvalue_table_entry_struct {
  sion_keyvalue_table_entry_state_t state;
  sion_table_key_t key;
  _sion_keyvalue_table_entry *iterator_next;
  _sion_keyvalue_table_entry *next;
  void *data;
};

#define HASH_FCT_SIMPLE_not
#define HASH_FCT_SPLIT

#define DFUNCTION "_sion_keyvalue_table_hash_fct"
unsigned int _sion_keyvalue_table_hash_fct(sion_table_key_t key, int tab_size)
{
  unsigned int index = 0;

#if defined(HASH_FCT_SIMPLE)
  /* simple modulo */
  {
    index = (unsigned int)key % tab_size;
  }
#elif defined(HASH_FCT_SPLIT)
  {
    /* split modulo */
    uint32_t upper = (uint32_t)(key >> 32);
    uint32_t lower = (uint32_t)(key & 0xffffffff);
    DPRINTFP((2, DFUNCTION, -1, "key %ld -> %d %d \n", (long)key, (int)upper, (int)lower));
    index = (unsigned int)((unsigned int)upper % tab_size + (unsigned int)lower % tab_size) % tab_size;
  }
#endif

  return index;
}
#undef DFUNCTION

#define DFUNCTION "_sion_keyvalue_table_init"
_sion_keyvalue_table *_sion_keyvalue_table_init(int size)
{
  _sion_keyvalue_table *table = NULL;
  _sion_keyvalue_table_entry *entries = NULL;
  int i;

  DPRINTFP((2, DFUNCTION, -1, "enter init size=%d\n", size));

  table = malloc(sizeof(_sion_keyvalue_table));
  if (table == NULL) {
    _sion_errorprint(0, _SION_ERROR_RETURN, "cannot allocate internal keyvalue table of size %lu , aborting ...\n",
      (unsigned long)sizeof(_sion_keyvalue_table));
    return NULL;
  }

  entries = malloc(size * sizeof(_sion_keyvalue_table_entry));
  if (entries == NULL) {
    _sion_errorprint(
      0, _SION_ERROR_RETURN, "cannot allocate internal keyvalue table entries of size %lu , aborting ...\n", (unsigned long)size);
    free(table);
    return NULL;
  }
  table->entries = entries;

  table->size = size;
  table->used = 0;
  table->num_added_entries = 0;
  table->iterator_lastreadindex = -1;
  table->iterator_lastreadentry = NULL;
  table->iterator_next = NULL;
  table->iterator_head = NULL;
  table->iterator_tail = NULL;
  for (i = 0; i < table->size; i++) {
    table->entries[i].state = KEYVALUE_TABLE_ENTRY_STATE_FREE;
    table->entries[i].key = 0;
    table->entries[i].iterator_next = NULL;
    table->entries[i].next = NULL;
    table->entries[i].data = NULL;
  }

  DPRINTFP((2, DFUNCTION, -1, "leave\n"));
  return table;
}
#undef DFUNCTION

#define DFUNCTION "_sion_keyvalue_table_destroy"
int _sion_keyvalue_table_destroy(_sion_keyvalue_table **table)
{
  size_t rc = SION_SUCCESS;
  int i;
  _sion_keyvalue_table_entry *entry, *next_entry;

  DPRINTFP((2, DFUNCTION, -1, "enter\n"));
  if ((*table)->entries) {
    for (i = 0; i < (*table)->size; i++) {
      /* free entry data */
      if (((*table)->entries[i].state != KEYVALUE_TABLE_ENTRY_STATE_FREE) && ((*table)->entries[i].data != NULL)) {
        free((*table)->entries[i].data);
      }
      /* free linked list */
      entry = (*table)->entries[i].next;
      while (entry != NULL) {
        if ((entry->state != KEYVALUE_TABLE_ENTRY_STATE_FREE) && (entry->data != NULL)) {
          free(entry->data);
        }
        next_entry = entry->next;
        free(entry);
        entry = next_entry;
      }
    }

    free((*table)->entries);
    (*table)->entries = NULL;
  }
  free(*table);
  *table = NULL;

  DPRINTFP((2, DFUNCTION, -1, "leave rc=%d\n", rc));
  return rc;
}
#undef DFUNCTION

#define DFUNCTION "_sion_keyvalue_table_store"
int _sion_keyvalue_table_store(_sion_keyvalue_table *table, sion_table_key_t key, void *data)
{
  size_t rc = SION_SUCCESS;
  unsigned int index;
  _sion_keyvalue_table_entry *new_entry;

  DPRINTFP((2, DFUNCTION, -1, "enter\n"));

  index = _sion_keyvalue_table_hash_fct(key, table->size);
  DPRINTFP((2, DFUNCTION, -1, "store entry with key %ld index=%d\n", (long)key, index));

  new_entry = &table->entries[index];
  if (new_entry->state != KEYVALUE_TABLE_ENTRY_STATE_FREE) {
    while (new_entry->next != NULL) {
      new_entry = new_entry->next;
    }
    new_entry->next = malloc(sizeof(_sion_keyvalue_table_entry));
    if (new_entry->next == NULL) {
      return _sion_errorprint(
        SION_NOT_SUCCESS, _SION_ERROR_RETURN, "cannot allocate internal keyvalue table entry, aborting ...\n");
    }
    DPRINTFP((2, DFUNCTION, -1, "add new entry to next list\n"));
    table->num_added_entries++;
    new_entry = new_entry->next;
  }
  table->used++;

  new_entry->state = KEYVALUE_TABLE_ENTRY_STATE_USED;
  new_entry->key = key;
  new_entry->data = data;
  new_entry->next = NULL;
  new_entry->iterator_next = NULL;

  if ((table->iterator_head == NULL) && (table->iterator_tail == NULL)) {
    /* first entry */
    table->iterator_next = table->iterator_head = table->iterator_tail = new_entry;
  } else {
    table->iterator_tail->iterator_next = new_entry;
    table->iterator_tail = table->iterator_tail->iterator_next; /* advance tail */
  }

  DPRINTFP((2, DFUNCTION, -1, "new entry successfully added (key %ld index=%d)\n", (long)key, index));
  DPRINTFP((2, DFUNCTION, -1, "TABLE[slots %d of %d, +%d, total %d] \n", table->used - table->num_added_entries, table->size,
    table->num_added_entries, table->used));

  DPRINTFP((2, DFUNCTION, -1, "leave rc=%d\n", rc));
  return rc;
}
#undef DFUNCTION

#define DFUNCTION "_sion_keyvalue_table_lookup"
void *_sion_keyvalue_table_lookup(_sion_keyvalue_table *table, sion_table_key_t key)
{
  unsigned int index;
  _sion_keyvalue_table_entry *entry;

  DPRINTFP((2, DFUNCTION, -1, "enter\n"));

  index = _sion_keyvalue_table_hash_fct(key, table->size);
  DPRINTFP((2, DFUNCTION, -1, "lookup entry with key %ld index=%d\n", (long)key, index));

  entry = &(table->entries[index]);
  while (entry != NULL) {
    DPRINTFP((2, DFUNCTION, -1, "search: state=%ld\n", (long)entry->state));

    if (entry->state == KEYVALUE_TABLE_ENTRY_STATE_USED) {
      if (entry->key == key) {
        DPRINTFP((2, DFUNCTION, -1, "key found %ld in key list\n", (long)entry->key));
        return entry->data;
      } else {
        DPRINTFP((2, DFUNCTION, -1, "skip this key another key found %ld in list\n", (long)entry->key));
        entry = entry->next;
      }
    } else {
      /* slot is empty */
      return NULL;
    }
  }
  DPRINTFP((2, DFUNCTION, -1, "leave:entry not found\n"));
  return NULL;
}
#undef DFUNCTION

#define DFUNCTION "_sion_keyvalue_table_iterator_reset"
int _sion_keyvalue_table_iterator_reset(_sion_keyvalue_table *table)
{
  int rc = SION_SUCCESS;

  DPRINTFP((2, DFUNCTION, -1, "enter\n"));
  table->iterator_lastreadindex = -1;
  table->iterator_lastreadentry = NULL;
  table->iterator_next = table->iterator_head;
  DPRINTFP((2, DFUNCTION, -1, "leave\n"));

  return rc;
}
#undef DFUNCTION

#define DFUNCTION "_sion_keyvalue_table_iterator_next_in_store_order"
int _sion_keyvalue_table_iterator_next_in_store_order(_sion_keyvalue_table *table, sion_table_key_t *key, void **data)
{
  _sion_keyvalue_table_entry *entry;

  DPRINTFP((2, DFUNCTION, -1, "enter\n"));
  if (table->used == 0) {
    return SION_NOT_SUCCESS;
  }
  entry = table->iterator_next;

  if (entry != NULL) {
    *key = entry->key;
    *data = entry->data;
    DPRINTFP((2, DFUNCTION, -1, "found entry with key %ld\n", (long)*key));
    table->iterator_next = entry->iterator_next; /* move forward in iterator list */
    return SION_SUCCESS;
  } else {
    return SION_NOT_SUCCESS;
  }
}
#undef DFUNCTION

#define DFUNCTION "_sion_keyvalue_table_iterator_next"
int _sion_keyvalue_table_iterator_next(_sion_keyvalue_table *table, sion_table_key_t *key, void **data)
{
  DPRINTFP((2, DFUNCTION, -1, "enter\n"));
  if (table->used == 0) {
    return SION_NOT_SUCCESS;
  }
  if (table->iterator_lastreadindex == -1) {
    /* search first entry which must be there (used>0) */
    DPRINTFP((2, DFUNCTION, -1, "start first\n"));
    table->iterator_lastreadindex++;
    while (table->iterator_lastreadindex < table->size) {
      if (table->entries[table->iterator_lastreadindex].state == KEYVALUE_TABLE_ENTRY_STATE_USED) {
        table->iterator_lastreadentry = &table->entries[table->iterator_lastreadindex];
        break;
      }
      table->iterator_lastreadindex++;
    }
    DPRINTFP((2, DFUNCTION, -1, "start first, found entry at index %d\n", table->iterator_lastreadindex));

  } else {
    /* another entry in list? */
    if (table->iterator_lastreadentry->next != NULL) {
      table->iterator_lastreadentry = table->iterator_lastreadentry->next;
      DPRINTFP((2, DFUNCTION, -1, "found another entry in list at index %d\n", table->iterator_lastreadindex));
    } else {
      /* search forward */
      table->iterator_lastreadindex++;
      while (table->iterator_lastreadindex < table->size) {
        if (table->entries[table->iterator_lastreadindex].state == KEYVALUE_TABLE_ENTRY_STATE_USED) {
          table->iterator_lastreadentry = &table->entries[table->iterator_lastreadindex];
          DPRINTFP((2, DFUNCTION, -1, "found entry at another index %d\n", table->iterator_lastreadindex));
          break;
        }
        table->iterator_lastreadindex++;
      }
    }
  }
  if (table->iterator_lastreadindex < table->size) {
    *key = table->iterator_lastreadentry->key;
    *data = table->iterator_lastreadentry->data;
    DPRINTFP((2, DFUNCTION, -1, "leave: entry found\n"));
    return SION_SUCCESS;
  } else {
    DPRINTFP((2, DFUNCTION, -1, "leave: next entry not found\n"));
    return SION_NOT_SUCCESS;
  }
}
#undef DFUNCTION

#define DFUNCTION "_sion_keyvalue_table_get_size"
int _sion_keyvalue_table_get_size(_sion_keyvalue_table *table)
{
  size_t help_bytes, bytes = 0;
  int i;
  _sion_keyvalue_table_entry *entry;

  DPRINTFP((2, DFUNCTION, -1, "enter\n"));

  help_bytes = sizeof(_sion_keyvalue_table);
  DPRINTFP((2, DFUNCTION, -1, " sizeof key_table=          %5d\n", help_bytes));
  bytes += help_bytes;

  if (table->entries) {
    help_bytes = table->size * sizeof(_sion_keyvalue_table_entry);
    DPRINTFP((2, DFUNCTION, -1, " sizeof key_entries=        %5d\n", help_bytes));
    bytes += help_bytes;

    help_bytes = 0;
    for (i = 0; i < table->size; i++) {
      entry = table->entries[i].next;
      while (entry != NULL) {
        help_bytes += sizeof(_sion_keyvalue_table_entry);
        entry = entry->next;
      }
    }

    DPRINTFP((2, DFUNCTION, -1, " sizeof key_addentries=     %5d\n", help_bytes));
    bytes += help_bytes;
  }

  DPRINTFP((2, DFUNCTION, -1, "leave bytes=%d\n", bytes));
  return bytes;
}
#undef DFUNCTION
