/* -----------------------------------------------------------------------------
 *
 * Copyright (c) 2010-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.
 *
 * -----------------------------------------------------------------------------
 */


#ifdef __cplusplus
extern "C" {
#endif


////


/* (1) for 2-heap, (2) for 4-heap, (3) for 8-heap, (4) for 16-heap */
#define MM_HEAP_SHIFT (4)

#define MM_HEAP_WIDTH (1<<MM_HEAP_SHIFT)
#define MM_HEAP_MASK (MM_HEAP_WIDTH-1)
#define MM_HEAP_OFFSET (MM_HEAP_WIDTH-2)

#if defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__clang__)
 #if MM_HEAP_WIDTH >= 8
  #define MM_HEAP_ALIGN __attribute__((aligned(32)))
  #define MM_HEAP_ALIGNED(p) __builtin_assume_aligned(p,32)
 #elif MM_HEAP_WIDTH >= 4
  #define MM_HEAP_ALIGN __attribute__((aligned(16)))
  #define MM_HEAP_ALIGNED(p) __builtin_assume_aligned(p,16)
 #else
  #define MM_HEAP_ALIGN
  #define MM_HEAP_ALIGNED(p) (p)
 #endif
#elif defined(_MSC_VER)
 #if MM_HEAP_WIDTH >= 8
  #define MM_HEAP_ALIGN __declspec(align(32))
  #define MM_HEAP_ALIGNED(p) (p)
 #elif MM_HEAP_WIDTH >= 4
  #define MM_HEAP_ALIGN __declspec(align(16))
  #define MM_HEAP_ALIGNED(p) (p)
 #else
  #define MM_HEAP_ALIGN
  #define MM_HEAP_ALIGNED(p) (p)
 #endif
#else
 #define MM_HEAP_ALIGN
 #define MM_HEAP_ALIGNED(p) (p)
#endif


/////


typedef struct MM_HEAP_ALIGN
{
  uint32_t MM_HEAP_ALIGN value[MM_HEAP_WIDTH];
  void MM_HEAP_ALIGN *p[MM_HEAP_WIDTH];
} mmHeap32Unit;

typedef struct
{
  size_t size;
  size_t alloc;
  mmHeap32Unit *array;
} mmHeap32;

void mmHeap32Init( mmHeap32 *heap, size_t sizehint );
void mmHeap32Free( mmHeap32 *heap );
void *mmHeap32GetFirst( mmHeap32 *heap, uint32_t *retvalue );
void mmHeap32Insert( mmHeap32 *heap, void *p, uint32_t value );
void mmHeap32DeleteFirst( mmHeap32 *heap );
size_t mmHeap32GetCount( mmHeap32 *heap );

void mmHeap32Merge( mmHeap32 *dst, mmHeap32 *src );

void mmHeap32Debug( mmHeap32 *heap, int verbose );


/////


typedef struct MM_HEAP_ALIGN
{
  uint64_t MM_HEAP_ALIGN value[MM_HEAP_WIDTH];
  void MM_HEAP_ALIGN *p[MM_HEAP_WIDTH];
} mmHeap64Unit;

typedef struct
{
  size_t size;
  size_t alloc;
  mmHeap64Unit *array;
} mmHeap64;

void mmHeap64Init( mmHeap64 *heap, size_t sizehint );
void mmHeap64Free( mmHeap64 *heap );
void *mmHeap64GetFirst( mmHeap64 *heap, uint64_t *retvalue );
void mmHeap64Insert( mmHeap64 *heap, void *p, uint64_t value );
void mmHeap64DeleteFirst( mmHeap64 *heap );
size_t mmHeap64GetCount( mmHeap64 *heap );

void mmHeap64Debug( mmHeap64 *heap );


/////


/* 'Heap64sb': Signed 64bits bare (just values) heap */

typedef struct MM_HEAP_ALIGN
{
  int64_t MM_HEAP_ALIGN value[MM_HEAP_WIDTH];
} mmHeap64sbUnit;

typedef struct
{
  size_t size;
  size_t alloc;
  mmHeap64sbUnit *array;
} mmHeap64sb;

void mmHeap64sbInit( mmHeap64sb *heap, size_t sizehint );
void mmHeap64sbFree( mmHeap64sb *heap );
int mmHeap64sbGetFirst( mmHeap64sb *heap, int64_t *retvalue );
void mmHeap64sbInsert( mmHeap64sb *heap, int64_t value );
void mmHeap64sbDeleteFirst( mmHeap64sb *heap );
size_t mmHeap64sbGetCount( mmHeap64sb *heap );

/* Only use to build initial heap with already sorted values */
void mmHeap64sbSortedPush( mmHeap64sb *heap, int64_t value );

// void mmHeap64sbDebug( mmHeap64sb *heap );
void mmHeap64sbDebug( mmHeap64sb *heap, int verbose );


/////


typedef struct MM_HEAP_ALIGN
{
  float MM_HEAP_ALIGN value[MM_HEAP_WIDTH];
  void MM_HEAP_ALIGN *p[MM_HEAP_WIDTH];
} mmHeapfUnit;

typedef struct
{
  size_t size;
  size_t alloc;
  mmHeapfUnit *array;
} mmHeapf;

void mmHeapfInit( mmHeapf *heap, size_t sizehint );
void mmHeapfFree( mmHeapf *heap );
void *mmHeapfGetFirst( mmHeapf *heap, float *retvalue );
void mmHeapfInsert( mmHeapf *heap, void *p, float value );
void mmHeapfDeleteFirst( mmHeapf *heap );
size_t mmHeapfGetCount( mmHeapf *heap );

void mmHeapfDebug( mmHeapf *heap, int verbose );


////


#ifdef __cplusplus
}
#endif