/*!@file
  \brief   STON Hash Tables
  \details Aligned general purpose hash functions and memory definitions
           whose columns are provided, and whose rows, and sizes, are derived.

             ht_size = header.ht_columns << header.ht_2pow;
             ht_rows = 0x1 << header.ht_2pow;

           All generic hashtables in henge must have a power-of-two number of
           rows.  An ht_columns value that is also a power-of-two will result in
           a power-of-two sized memory imprint for the structure, making it easy
           to page align.

           Elements in the columns may be of any arbitrary size.

             typedef uint32_t my_ht_type;
             ht_bytes = ht_size * sizeof(my_ht_type);

           implementation covers only 32-bit unit sizes.

  \author  Ken Grimes
  \date    Feb 2017
  ----------------------------------------------------------------------------*/
#ifndef _STON_HT_T_
#define _STON_HT_T_
/* Define STON_NOSTATIC to expose included function symbols */
#ifndef STON_NOSTATIC
#define STON_FUNC_STATIC static
#else
#define STON_FUNC_STATIC
#endif //STON_NOSTATIC
/* If GNUC is detected, uses attributes to stop inlining */
#ifdef  __GNUC__
#define STON_FUNC_NOINLINE __attribute__ ((noinline))
#else
#define STON_FUNC_NOINLINE
#endif //__GNUC__
/* Define STON_NOINLINE to prevent inline compiler hints */
#ifndef STON_NOINLINE
#define STON_FUNC_INLINE inline
#else
#define STON_FUNC_INLINE
#endif //STON_NOINLINE
/* Define STON_FUNC to override the default STON Function attributes */
#ifndef STON_FUNC
#define STON_FUNC STON_FUNC_STATIC STON_FUNC_INLINE
#endif //STON_FUNC
#ifndef STON_NOSTDIO
#include <stdio.h>
#include <string.h> //memcpy
#include <alloca.h>
#endif //STON_NOSTDIO
#include <stdint.h>
/* STON Hashtable Structure
   Hashtables are stored as dynamically sized two dimensional arrays
*/
typedef struct ston_ht_header_t
{ uint16_t ht_columns;
  uint8_t  ht_2pow, ht_flags;
}* ston_ht;

STON_FUNC
size_t    ston_up2pow(size_t);
STON_FUNC_STATIC
STON_FUNC_NOINLINE
ston_ht   ston_ht32_fread(FILE*,long,void*(*)(size_t));
STON_FUNC
ston_ht   ston_ht32_create(uint16_t,size_t,uint8_t,void*(*)(size_t));
STON_FUNC
uint32_t* ston_ht32_row(ston_ht,uint32_t);
STON_FUNC
uint32_t  ston_ht32_insert(ston_ht,uint32_t,uint16_t,uint32_t);

#define   ston_ht32_new(_COL,_N,_F,_FN) ston_ht32_create(_COLS,ston_up2pow(_N << 1),_F,_FN)
#define   ston_ht32_entry(_HT,_KEY,_COL)        (ston_ht32_row(_HT,_KEY) + _COL)
#define   ston_ht32_insertx(_HT,_KEY,_COL,_VAL) *ston_ht32_entry(_HT,_KEY,_COL) = _VAL
#define   ston_ht_size(_HT)            ((_HT)->ht_columns << (_HT)->ht_2pow)
#define   ston_ht_rows(_HT)            (0x1 << (_HT)->ht_2pow)
#define   ston_ht_cols(_HT)            ((_HT)->ht_columns)
#define   ston_ht_start(_HT)           (((uint8_t*)(_HT)) + sizeof(*(_HT)))
#define   ston_ht_keyrow(_HT,_KEY)     ((_KEY) & (ston_ht_rows(ht) - 1))
#define   ston_ht32_start(_HT)         ((uint32_t*)ston_ht_start(_HT))
#define   ston_ht32_end(_HT)           (ston_ht32_start(_HT) + ston_ht_size(_HT))
#define   ston_ht32_size(_HT)          (ston_ht_size(_HT) * sizeof(uint32_t))

/** @see http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 */
STON_FUNC
size_t ston_up2pow
( size_t val )
{ val = (val << 1) - 1;
  val |= val >> 1;
  val |= val >> 2;
  val |= val >> 4;
  val |= val >> 8;
  val |= val >> 16;
  return ++val;
}

/* Creates a new hash table, provided a memory allocation function that takes a
   single size_t bytes, a column count, and a row count which determines the
   size of the table.

   use ston_ht32_new to specify the exact or estimated number of unique keys
   held in the table.  With ston_ht32_new, the provided ht_rows is doubled, and
   rounded up to the nearest power of two to create a hash table with minimal
   collisions.
*/
STON_FUNC
ston_ht ston_ht32_create
( uint16_t ht_columns,
  size_t   ht_rows,
  uint8_t  ht_flags,
  void*    (*alloc_fn)(size_t)
)
{ size_t  ht_size = ht_rows * ht_columns * sizeof(uint32_t);
  ston_ht ht = (ston_ht) alloc_fn(sizeof(struct ston_ht_header_t) + ht_size);
  if (ht != NULL)
    { for (ht->ht_2pow = 0; ht_size; ht->ht_2pow++)
	ht_size = ht_size >> 1;
      ht->ht_columns = ht_columns;
      ht->ht_flags = ht_flags;
    }
  return ht;
}

#ifndef STON_NO_STDIO
/* Reads a 32-bit hash table out of the provided file at the provide fpos, into
   a buffer allocated by alloc_fn.  Memory is allocated to the stack until the
   entire structure is verified, and all file operations are finished.  
   Returns NULL with properly set errno on failure.
*/
STON_FUNC_STATIC
STON_FUNC_NOINLINE
ston_ht ston_ht32_fread
( FILE* file,
  long  fpos,
  void* (*alloc_fn)(size_t)
)
{ struct ston_ht_header_t header;
  ston_ht                 stack_ht, ht;
  long                    fpos_start;
  size_t                  table_size, alloc_size;
  int                     errno_local;
  if ((fpos_start = ftell(file)) == -1)
    return NULL;
  if (fread(&header, sizeof(header), 1, file) != 1)
    goto fail_seekback;
  table_size = ston_ht32_size(&header);
  alloc_size = sizeof(header) + table_size;
  stack_ht = (ston_ht) alloca(alloc_size);
  memcpy(stack_ht, &header, sizeof(header));
  if (fread(stack_ht + sizeof(header), table_size, 1, file) != 1)
    goto fail_seekback;
  if (fseek(file, fpos_start, SEEK_SET) != 0)
    return NULL;
  ht = (ston_ht) alloc_fn(alloc_size);
  if (ht != NULL)
    memcpy(ht, stack_ht, alloc_size);
  return ht;
 fail_seekback:
  /* Try to seek the file back to origin without clobbering errno */
  errno_local = errno;
  fseek(file, fpos_start, SEEK_SET);
  errno = errno_local;
  return NULL;
}
#endif

/* Returns a pointer to the row of data in the hashtable containing the provided
   key, inserts if not found.  Returns NULL on overflow.
*/
STON_FUNC
uint32_t* ston_ht32_row
( struct ston_ht_header_t* ht,
  uint32_t                key
)
{ uint32_t* row;
  uint32_t* row_start = ston_ht32_start(ht);
  uint32_t* row_end = ston_ht32_end(ht);
  uint16_t  ht_cols = ston_ht_cols(ht);
  size_t    row_number = ston_ht_keyrow(ht,key);
  uint8_t   looped = 0;
  row = row_start + (row_number * ht_cols);
 next_row:
  if (row[0] != 0)
    goto populated;
 write_position:
  row[0] = key;
  return row;
 populated:
  if (row[0] == key)
    goto write_position;
  if (row < row_end)
    row += ht_cols;
  else if (looped)
      return NULL;
  else
    { looped++;
      row = row_start;
    }
  goto next_row;
}

/* Inserts a value into a hashtable at the specified column, returning the
   previous value */
STON_FUNC
uint32_t ston_ht32_insert
( struct ston_ht_header_t* ht,
  uint32_t                key,
  uint16_t                column,
  uint32_t                value
)
{ uint32_t* value_location, old_value;
  value_location = ston_ht32_entry(ht,key,column);
  old_value = *value_location;
  *value_location = value;
  return old_value;
}

#ifndef STON_DHT_SIZE
#define STON_DHT_SIZE 4096
#endif

/* STON Dynamic Hashtable Structure
   A dynamic form of the generic hashtable implementation above which uses
   external allocation.
*/
typedef struct ston_dht_header_t
{ uint16_t  ht_columns;
  uint8_t   ht_2pow, ht_flags;
  void*     (*ht_alloc)(size_t);
  void      (*ht_free)(void*);
  void**    page_head;
}* ston_dht;
#define   STON_DHT_HEADERSIZE (sizeof(struct ston_dht_header_t))

STON_FUNC
ston_dht  ston_dht32_create(uint16_t,size_t,uint8_t,void*(*)(size_t),void(*)(void*));
STON_FUNC
uint32_t* ston_dht32_row(ston_dht,uint32_t);
STON_FUNC
uint32_t  ston_dht32_insert(ston_dht,uint32_t,uint16_t,uint32_t);
STON_FUNC
void      ston_dht32_free(ston_dht);

#define   ston_dht32_new(_COL,_N,_F,_FN)         ston_dht32_create(_COLS,ston_up2pow(_N << 1),_F,_FN)
#define   ston_dht32_entry(_HT,_KEY,_COL)        (ston_dht32_row(_HT,_KEY) + _COL)
#define   ston_dht32_insertx(_HT,_KEY,_COL,_VAL) *ston_dht32_col(_HT,_KEY,_COL) = _VAL
#define   ston_dht_size(_HT)           (ston_ht_size(_HT))
#define   ston_dht_rows(_HT)           (ston_ht_rows(_HT))
#define   ston_dht_cols(_HT)           (ston_ht_cols(_HT))
#define   ston_dht_keyrow(_HT,_KEY)    (ston_ht_keyrow(_HT,_KEY))
#define   ston_dht_pagestart(_HT)      ((void**)(((uint8_t*)(_HT)) + STON_DHT_HEADERSIZE))
#define   ston_dht_pagehead(_HT)       ((_HT)->page_head)
#define   ston_dht_pagemax(_HT)        ((void**)((uint8_t*)(_HT) + STON_DHT_SIZE - sizeof(void**)))
#define   ston_dht_start(_HT,_DEPTH)   ((uint8_t*)*(ston_dht_pagestart(_HT) + _DEPTH))
#define   ston_dht32_start(_HT,_DEPTH) ((uint32_t*)ston_dht_start(_HT,_DEPTH))
#define   ston_dht32_end(_HT,_DEPTH)   (ston_ht32_start(_HT,_DEPTH) + ston_ht_size(_HT))
#define   ston_dht32_size(_HT)         (ston_dht_size(_HT) * sizeof(uint32_t))
#define   ston_dht32_pagepush(_HT)     ((*(++((_HT)->page_head)) = (_HT)->ht_alloc(ston_dht32_size(_HT))))
#define   ston_dht32_pagepop(_HT)      ((_HT)->ht_free((_HT)->page_head--))

/* Creates a new bucketted hash table, provided a memory allocation function
   that takes a single size_t bytes, a memory free function, a column count, and
   a row count which determines the size of the buckets.
*/
STON_FUNC
ston_dht ston_dht32_create
( uint16_t ht_columns,
  size_t   ht_rows,
  uint8_t  ht_flags,
  void*   (*ht_alloc)(size_t),
  void    (*ht_free)(void*)
)
{ size_t   ht_size = ht_rows * ht_columns * sizeof(uint32_t);
  ston_dht ht = (ston_dht) ht_alloc(STON_DHT_SIZE);
  if (ht != NULL)
    { for (ht->ht_2pow = 0; ht_size; ht->ht_2pow++)
	ht_size = ht_size >> 1;
      ht->ht_columns = ht_columns;
      ht->ht_flags = ht_flags;
      ht->ht_alloc = ht_alloc;
      ht->ht_free = ht_free;
      ht->page_head = ston_dht_pagestart(ht);
      if ((*(ht->page_head) = ht->ht_alloc(ston_dht_size(ht))) == NULL)
	ht_free(ht);
    }
  return ht;
}

/* Returns a pointer to the row of data in the hashtable containing the provided
   key, inserts if not found.  Returns NULL on overflow.
*/
STON_FUNC
uint32_t* ston_dht32_row
( struct ston_dht_header_t* ht,
  uint32_t                  key
)
{ uint16_t   ht_cols = ston_dht_cols(ht);
  size_t     row_number = ston_dht_keyrow(ht,key);
  uint32_t** page = (uint32_t**)ston_dht_pagestart(ht);
  uint32_t** pagemax = (uint32_t**)ston_dht_pagemax(ht);
  uint8_t    loop_x = 0;
  uint8_t    loop_y = 0;
  uint32_t*  row,* row_end;
 next_page:
  row = *page + (row_number * ht_cols);
  row_end = *page + (ston_dht_size(ht) - 1);
 next_row:
  if (row[0] != 0)
    goto populated;
 write_position:
  row[0] = key;
  return row;
 populated:
  if (row[0] == key)
    goto write_position;
  if (!loop_x)
    { if (page < pagemax)
	{ if (page == (uint32_t**)ston_dht_pagehead(ht))
	    if (ston_dht32_pagepush(ht) == NULL)
	      { ston_dht32_free(ht);
		return NULL;
	      }
	  ++page;
	  goto next_row;
	}
      loop_x = 1;
      row_number = (row_number + 1) % ston_dht_rows(ht);
      page = (uint32_t**)ston_dht_pagestart(ht);
      goto next_row;
    }
  if (row < row_end)
    { row += ht_cols;
      goto next_row;
    }
  else if (!loop_y)
    { loop_y = 1;
      row = *page;
      goto next_row;
    }
  if (page < pagemax)
    { loop_y = 0;
      page++;
      goto next_page;
    }
  return NULL;
}

/* Inserts a value into a hashtable at the specified column, returning the
   previous value */
STON_FUNC
uint32_t ston_dht32_insert
( struct ston_dht_header_t* ht,
  uint32_t                  key,
  uint16_t                  column,
  uint32_t                  value
)
{ uint32_t* value_location, old_value;
  value_location = ston_dht32_entry(ht,key,column);
  old_value = *value_location;
  *value_location = value;
  return old_value;
}

/* Free the dynamic hash table */
STON_FUNC
void ston_dht32_free
( struct ston_dht_header_t* ht )
{ void (*ht_free)(void*) = ht->ht_free;
  if (ht_free != NULL)
    { while (ht->page_head >= ston_dht_pagestart(ht))
	ht_free(ht->page_head--);
      ht_free(ht);
    }
}

#endif //_STON_HT_H_