/* -----------------------------------------------------------------------------
 *
 * Copyright (c) 2020-2022 Alexis Naveros.
 * Portions developed under contract to the SURVICE Engineering Company.
 *
 * This software is provided 'as-is', without any express or implied
 * warranty. In no event will the authors be held liable for any damages
 * arising from the use of this software.
 *
 * Permission is granted to anyone to use this software for any purpose,
 * including commercial applications, and to alter it and redistribute it
 * freely, subject to the following restrictions:
 *
 * 1. The origin of this software must not be misrepresented; you must not
 * claim that you wrote the original software. If you use this software
 * in a product, an acknowledgment in the product documentation would be
 * appreciated but is not required.
 * 2. Altered source versions must be plainly marked as such, and must not be
 * misrepresented as being the original software.
 * 3. This notice may not be removed or altered from any source distribution.
 *
 * -----------------------------------------------------------------------------
 */

/*

Templates C style!

#include this whole file with the following definitions set:

// Data type for each item of the vector
#define MM_VECTOR_ITEMTYPE uint32_t

// The name of the vector struct typedef
#define MM_VECTOR_TYPENAME glVertexVector

// Prefix for all vector functions (appending "Init", "Push", etc.)
#define MM_VECTOR_PREFIX glVertexVectorPrefix_

// Optional: Fixed count by how much to increase allocation when vector runs out
#define MM_VECTOR_ALLOCINCR (4096)

// Optional: Proportional increase of allocation when vector runs out, unit base 16, newcount = (oldcount*ALLOCFACTOR)>>4;
#define MM_VECTOR_ALLOCFACTOR (24) // count*=1.5;

// Optional: set to non-zero for the vector's items to have a fixed index once allocated, items are never moved
//         : a list of removed items is maintained, new items are inserted in the first free spot
#define MM_VECTOR_OPTION_FIXED (1)

// Optional: the vector's items are strictly ordered with respect to each other
//         : the underlying array can be repacked/memmoved to fill holes if any non-last item is deleted
#define MM_VECTOR_OPTION_ORDERED (1)

*/

#ifndef MM_VECTOR_ITEMTYPE
 #error You must #define MM_VECTOR_ITEMTYPE before including mmvector.h
#endif
#ifndef MM_VECTOR_TYPENAME
 #error You must #define MM_VECTOR_TYPENAME before including mmvector.h
#endif
#ifndef MM_VECTOR_PREFIX
 #error You must #define MM_VECTOR_PREFIX before including mmvector.h
#endif
#if MM_VECTOR_OPTION_FIXED && MM_VECTOR_OPTION_ORDERED
 #error A vector can not have both options MM_VECTOR_OPTION_FIXED and MM_VECTOR_OPTION_ORDERED set
#endif


#if defined(MM_VECTOR_ALLOCINCR) && MM_VECTOR_ALLOCINCR < 256
 #undef MM_VECTOR_ALLOCINCR
 #define MM_VECTOR_ALLOCINCR (256)
#elif !defined(MM_VECTOR_ALLOCINCR)
 #define MM_VECTOR_ALLOCINCR (4096)
#endif

#if defined(MM_VECTOR_ALLOCFACTOR) && MM_VECTOR_ALLOCFACTOR < 16
 #undef MM_VECTOR_ALLOCFACTOR
 #define MM_VECTOR_ALLOCFACTOR (16)
#elif !defined(MM_VECTOR_ALLOCFACTOR)
 #define MM_VECTOR_ALLOCFACTOR (24)
#endif


#define MM_VECTOR_SIZEOFTYPE sizeof(MM_VECTOR_ITEMTYPE)

#if MM_VECTOR_OPTION_FIXED
 #undef MM_VECTOR_SIZEOFTYPE
 /* If fixed ordering is set (keeping a freed list), we need enough storage per element to store an index */
 #define MM_VECTOR_SIZEOFTYPE (sizeof(MM_VECTOR_ITEMTYPE)>=sizeof(size_t)?sizeof(MM_VECTOR_ITEMTYPE):sizeof(size_t))
#endif

#ifndef ADDRESS
 #define ADDRESS(p,o) ((void *)(((char *)p)+(o)))
#endif

#define MM_VECTOR_FUNCX(prefix,suffix) prefix##suffix
#define MM_VECTOR_FUNC(prefix,suffix) MM_VECTOR_FUNCX(prefix,suffix)


////


typedef struct
{
  void *data;
  size_t count;
  size_t alloc;
#if MM_VECTOR_OPTION_FIXED
  size_t firstfree;
  size_t freecount;
#endif
} MM_VECTOR_TYPENAME;


/* Necessary when the vector's memory hasn't been zeroed, otherwise you can write/push right away */
static inline void MM_VECTOR_FUNC(MM_VECTOR_PREFIX,Init)( MM_VECTOR_TYPENAME *vector, size_t initreserve )
{
#if MM_VECTOR_OPTION_DEBUG_CALLS
  printf( "DEBUG: %s(%p)\n", __func__, vector );
  fflush( stdout );
#endif
  vector->data = 0;
  vector->count = 0;
  vector->alloc = initreserve;
  if( initreserve )
  {
    vector->data = malloc( initreserve * MM_VECTOR_SIZEOFTYPE );
#if MM_VECTOR_OPTION_DEBUG_CALLS
    printf( "       %s, vector resized to %ld items\n", __func__, (long)vector->alloc );
    fflush( stdout );
#endif
  }
#if MM_VECTOR_OPTION_FIXED
  vector->firstfree = -1;
  vector->freecount = 0;
#endif
  return;
}

static inline void MM_VECTOR_FUNC(MM_VECTOR_PREFIX,Clear)( MM_VECTOR_TYPENAME *vector )
{
#if MM_VECTOR_OPTION_DEBUG_CALLS
  printf( "DEBUG: %s(%p)\n", __func__, vector );
  fflush( stdout );
#endif
  free( (void *)vector->data );
  memset( (void *)vector, 0, sizeof(MM_VECTOR_TYPENAME) );
  return;
}

static inline void MM_VECTOR_FUNC(MM_VECTOR_PREFIX,Empty)( MM_VECTOR_TYPENAME *vector )
{
#if MM_VECTOR_OPTION_DEBUG_CALLS
  printf( "DEBUG: %s(%p)\n", __func__, vector );
  fflush( stdout );
#endif
  vector->count = 0;
#if MM_VECTOR_OPTION_FIXED
  vector->firstfree = -1;
  vector->freecount = 0;
#endif
  return;
}


/* Get the pointer to an item, both for reading and writing (preferable to Read()/Write() if the item is a struct) */
static inline MM_VECTOR_ITEMTYPE *MM_VECTOR_FUNC(MM_VECTOR_PREFIX,Access)( MM_VECTOR_TYPENAME *vector, size_t index )
{
#if MM_VECTOR_OPTION_DEBUG_CALLS
  printf( "DEBUG: %s(%p)\n", __func__, vector );
  fflush( stdout );
#endif
  return (MM_VECTOR_ITEMTYPE *)ADDRESS( vector->data, index * MM_VECTOR_SIZEOFTYPE );
}

static inline MM_VECTOR_ITEMTYPE MM_VECTOR_FUNC(MM_VECTOR_PREFIX,Read)( MM_VECTOR_TYPENAME *vector, size_t index )
{
#if MM_VECTOR_OPTION_DEBUG_CALLS
  printf( "DEBUG: %s(%p,%ld) ~ %ld items\n", __func__, vector, (long)index, (long)vector->count );
  fflush( stdout );
#endif
  return *(MM_VECTOR_ITEMTYPE *)ADDRESS( vector->data, index * MM_VECTOR_SIZEOFTYPE );
}

static inline void MM_VECTOR_FUNC(MM_VECTOR_PREFIX,Write)( MM_VECTOR_TYPENAME *vector, size_t index, MM_VECTOR_ITEMTYPE item )
{
#if MM_VECTOR_OPTION_DEBUG_CALLS
  printf( "DEBUG: %s(%p,%ld) ~ %ld items\n", __func__, vector, (long)index, (long)vector->count );
  fflush( stdout );
#endif
  *(MM_VECTOR_ITEMTYPE *)ADDRESS( vector->data, index * MM_VECTOR_SIZEOFTYPE ) = item;
  return;
}

static inline size_t MM_VECTOR_FUNC(MM_VECTOR_PREFIX,GetCount)( MM_VECTOR_TYPENAME *vector )
{
#if MM_VECTOR_OPTION_DEBUG_CALLS
  printf( "DEBUG: %s(%p)\n", __func__, vector );
  fflush( stdout );
#endif
  return vector->count;
}

static inline size_t MM_VECTOR_FUNC(MM_VECTOR_PREFIX,GetUseCount)( MM_VECTOR_TYPENAME *vector )
{
#if MM_VECTOR_OPTION_DEBUG_CALLS
  printf( "DEBUG: %s(%p)\n", __func__, vector );
  fflush( stdout );
#endif
#if MM_VECTOR_OPTION_FIXED
  return vector->count - vector->freecount;
#else
  return vector->count;
#endif
}

static inline size_t MM_VECTOR_FUNC(MM_VECTOR_PREFIX,GetAlloc)( MM_VECTOR_TYPENAME *vector )
{
#if MM_VECTOR_OPTION_DEBUG_CALLS
  printf( "DEBUG: %s(%p)\n", __func__, vector );
  fflush( stdout );
#endif
  return vector->alloc;
}

/* Return index of the new entry in vector */
/* You should then call mmVectorAccess() with the returned index to get the pointer to the item, and write it */
static inline size_t MM_VECTOR_FUNC(MM_VECTOR_PREFIX,Add)( MM_VECTOR_TYPENAME *vector )
{
  size_t index;
#if MM_VECTOR_OPTION_DEBUG_CALLS
  printf( "DEBUG: %s(%p) ~ %ld items, %ld alloc\n", __func__, vector, (long)vector->count, (long)vector->alloc );
  fflush( stdout );
#endif
#if MM_VECTOR_OPTION_FIXED
  if( vector->firstfree != -1 )
  {
    index = vector->firstfree;
    vector->firstfree = *((size_t *)ADDRESS( vector->data, index * MM_VECTOR_SIZEOFTYPE ));
    vector->freecount--;
    return index;
  }
#endif
  if( vector->count >= vector->alloc )
  {
#if MM_VECTOR_ALLOCFACTOR
    vector->alloc = ( (uint64_t)vector->alloc * MM_VECTOR_ALLOCFACTOR ) >> 4;
#endif
    vector->alloc += MM_VECTOR_ALLOCINCR;
    vector->data = realloc( vector->data, vector->alloc * MM_VECTOR_SIZEOFTYPE );
#if MM_VECTOR_OPTION_DEBUG_CALLS
    printf( "       %s, vector resized to %ld items\n", __func__, (long)vector->alloc );
    fflush( stdout );
#endif
  }
  index = vector->count;
  vector->count++;
  return index;
}

/* Store item into array, return index of the new entry in vector */
static inline size_t MM_VECTOR_FUNC(MM_VECTOR_PREFIX,Push)( MM_VECTOR_TYPENAME *vector, MM_VECTOR_ITEMTYPE item )
{
  size_t index;
#if MM_VECTOR_OPTION_DEBUG_CALLS
  printf( "DEBUG: %s(%p)\n", __func__, vector );
  fflush( stdout );
#endif
  index = MM_VECTOR_FUNC(MM_VECTOR_PREFIX,Add)( vector );
  MM_VECTOR_FUNC(MM_VECTOR_PREFIX,Write)( vector, index, item );
  return index;
}

static inline void MM_VECTOR_FUNC(MM_VECTOR_PREFIX,Remove)( MM_VECTOR_TYPENAME *vector, size_t index )
{
#if MM_VECTOR_OPTION_DEBUG_CALLS
  printf( "DEBUG: %s(%p,%ld) ~ %ld items\n", __func__, vector, (long)index, (long)vector->count );
  fflush( stdout );
#endif
#if MM_VECTOR_OPTION_FIXED
  *((size_t *)ADDRESS( vector->data, index * MM_VECTOR_SIZEOFTYPE )) = vector->firstfree;
  vector->firstfree = index;
  vector->freecount++;
#else
  vector->count--;
  if( vector->count != index )
  {
 #if MM_VECTOR_OPTION_ORDERED
    /* Move all items to fill up the hole ~ item ordering is preserved */
    memmove( ADDRESS( vector->data, index * MM_VECTOR_SIZEOFTYPE ), ADDRESS( vector->data, ( index + 1 ) * MM_VECTOR_SIZEOFTYPE ), ( vector->count - ( index + 1 ) ) * MM_VECTOR_SIZEOFTYPE );
 #else
    /* Move the last item to fill up the hole ~ item ordering is not preserved */
    memcpy( ADDRESS( vector->data, index * MM_VECTOR_SIZEOFTYPE ), ADDRESS( vector->data, vector->count * MM_VECTOR_SIZEOFTYPE ), MM_VECTOR_SIZEOFTYPE );
 #endif
  }
#endif
  return;
}

static inline void MM_VECTOR_FUNC(MM_VECTOR_PREFIX,RemoveLast)( MM_VECTOR_TYPENAME *vector )
{
#if MM_VECTOR_OPTION_DEBUG_CALLS
  printf( "DEBUG: %s(%p)\n", __func__, vector );
  fflush( stdout );
#endif
#if MM_VECTOR_OPTION_FIXED
  *((size_t *)ADDRESS( vector->data, index * MM_VECTOR_SIZEOFTYPE )) = vector->firstfree;
  vector->firstfree = index;
  vector->freecount++;
#else
  vector->count--;
#endif
  return;
}

/* Any item with an index >= size is removed */
static inline void MM_VECTOR_FUNC(MM_VECTOR_PREFIX,Resize)( MM_VECTOR_TYPENAME *vector, size_t minsize, size_t maxsize )
{
  size_t size;
#if MM_VECTOR_OPTION_FIXED
  size_t index;
  size_t *readstorage, *writestorage;
#endif
#if MM_VECTOR_OPTION_DEBUG_CALLS
  printf( "DEBUG: %s(%p)\n", __func__, vector );
  fflush( stdout );
#endif
  size = vector->alloc;
  if( size < minsize )
    size = minsize;
  if( size > maxsize )
    size = maxsize;
  if( size == vector->alloc )
    return;
  if( size == 0 )
  {
    MM_VECTOR_FUNC(MM_VECTOR_PREFIX,Clear)( vector );
    return;
  }
#if MM_VECTOR_OPTION_FIXED
  /* Clean up the list of freed items */
  readstorage = &vector->firstfree;
  writestorage = &vector->firstfree;
  for( ; ; )
  {
    index = *readstorage;
    if( index == -1 )
      break;
    readstorage = ((size_t *)ADDRESS( vector->data, index * MM_VECTOR_SIZEOFTYPE ));
    if( index < size )
    {
      *writestorage = index;
      writestorage = ((size_t *)ADDRESS( vector->data, index * MM_VECTOR_SIZEOFTYPE ));
    }
  }
#endif
  vector->alloc = size;
  vector->data = realloc( vector->data, size * MM_VECTOR_SIZEOFTYPE );
#if MM_VECTOR_OPTION_DEBUG_CALLS
  printf( "       %s, vector resized to %ld items\n", __func__, (long)vector->alloc );
  fflush( stdout );
#endif
  if( vector->count >= size )
    vector->count = size;
  return;
}

/* Steal the underlying data storage, pointer zeroed for safety */
static inline MM_VECTOR_ITEMTYPE *MM_VECTOR_FUNC(MM_VECTOR_PREFIX,Steal)( MM_VECTOR_TYPENAME *vector )
{
  void *data;
#if MM_VECTOR_OPTION_DEBUG_CALLS
  printf( "DEBUG: %s(%p)\n", __func__, vector );
  fflush( stdout );
#endif
  data = vector->data;
  memset( (void *)vector, 0, sizeof(MM_VECTOR_TYPENAME) );
  return (MM_VECTOR_ITEMTYPE *)data;
}


////


#undef MM_VECTOR_ITEMTYPE
#undef MM_VECTOR_TYPENAME
#undef MM_VECTOR_PREFIX
#undef MM_VECTOR_ALLOCINCR
#ifdef MM_VECTOR_ALLOCFACTOR
 #undef MM_VECTOR_ALLOCFACTOR
#endif
#ifdef MM_VECTOR_OPTION_FIXED
 #undef MM_VECTOR_OPTION_FIXED
#endif
#ifdef MM_VECTOR_OPTION_DEBUG_CALLS
 #undef MM_VECTOR_OPTION_DEBUG_CALLS
#endif