Unsafe max-heap in ATS

// NOTE: based on this code: https://gist.github.com/martinkunev/1365481

(* ****** ****** *)

%{

typedef int type;

typedef struct heap

{

unsigned int size; // Size of the allocated memory (in number of items)

unsigned int count; // Count of the elements in the heap

type *data; // Array with the elements

} heap_t;

#define CMP(a, b) ((a) >= (b))

static const unsigned int base_size = 4;

// Prepares the heap for use

void heap_init(atsrefarg1_type(heap_t) h)

{

*(heap_t*)h = (struct heap){

.size = base_size,

.count = 0,

.data = malloc(sizeof(type) * base_size)

};

if (!((heap_t*)h)->data) _exit(1); // Exit if the memory allocation fails

}

// Inserts element to the heap

void heap_push(atsrefarg1_type(heap_t) h, type value)

{

unsigned int index, parent;

// Resize the heap if it is too small to hold all the data

if (((heap_t*)h)->count == ((heap_t*)h)->size)

{

((heap_t*)h)->size <<= 1;

((heap_t*)h)->data = realloc(((heap_t*)h)->data, sizeof(type) * ((heap_t*)h)->size);

if (!((heap_t*)h)->data) _exit(1); // Exit if the memory allocation fails

}

// Find out where to put the element and put it

for(index = ((heap_t*)h)->count++; index; index = parent)

{

parent = (index - 1) >> 1;

if CMP(((heap_t*)h)->data[parent], value) break;

((heap_t*)h)->data[index] = ((heap_t*)h)->data[parent];

}

((heap_t*)h)->data[index] = value;

}

// Removes the biggest element from the heap

void heap_pop(atsrefarg1_type(heap_t) h)

{

unsigned int index, swap, other;

// Remove the biggest element

type temp = ((heap_t*)h)->data[--((heap_t*)h)->count];

// Resize the heap if it's consuming too much memory

if ((((heap_t*)h)->count <= (((heap_t*)h)->size >> 2)) && (((heap_t*)h)->size > base_size))

{

((heap_t*)h)->size >>= 1;

((heap_t*)h)->data = realloc(((heap_t*)h)->data, sizeof(type) * ((heap_t*)h)->size);

if (!((heap_t*)h)->data) _exit(1); // Exit if the memory allocation fails

}

// Reorder the elements

for(index = 0; 1; index = swap)

{

// Find the child to swap with

swap = (index << 1) + 1;

if (swap >= ((heap_t*)h)->count) break; // If there are no children, the heap is reordered

other = swap + 1;

if ((other < ((heap_t*)h)->count) && CMP(((heap_t*)h)->data[other], ((heap_t*)h)->data[swap])) swap = other;

if CMP(temp, ((heap_t*)h)->data[swap]) break; // If the bigger child is less than or equal to its parent, the heap is reordered

((heap_t*)h)->data[index] = ((heap_t*)h)->data[swap];

}

((heap_t*)h)->data[index] = temp;

}

// Heapifies a non-empty array

void heapify(type* data, unsigned int count)

{

unsigned int item, index, swap, other;

type temp;

// Move every non-leaf element to the right position in its subtree

item = (count >> 1) - 1;

while (1)

{

// Find the position of the current element in its subtree

temp = data[item];

for(index = item; 1; index = swap)

{

// Find the child to swap with

swap = (index << 1) + 1;

if (swap >= count) break; // If there are no children, the current element is positioned

other = swap + 1;

if ((other < count) && CMP(data[other], data[swap])) swap = other;

if CMP(temp, data[swap]) break; // If the bigger child is smaller than or equal to the parent, the heap is reordered

data[index] = data[swap];

}

if (index != item) data[index] = temp;

if (!item) return;

--item;

}

}

// Returns the biggest element in the heap

#define heap_front(h) ( *(h)->data)

// Frees the allocated memory

#define heap_term(h) (free((h)->data))

%}

(* ****** ****** *)

typedef T = int

abst@ype heap = $extype_struct"heap_t" of {size=int, count=int, data= ptr}

extern

fun

heap_init (&heap? >> _): void = "ext#"

extern

fun

heap_push (&heap, T): void = "ext#"

extern

fun

heap_pop (&heap): void = "ext#"

extern

fun

heap_front (&heap): T = "mac#"

extern

fun

heap_term (&heap >> _?): void = "mac#"

extern

fun

heapify {n:int} (&(@[T][n]) >> @[T][n], int n): void = "ext#"

(* ****** ****** *)

implement main0 () = let

var h: heap

val () = heap_init (h)

val () = heap_push (h, 5)

val () = heap_push (h, 4)

val () = heap_push (h, 6)

val () = heap_push (h, 10)

val () = println!("front: ", heap_front(h))

val () = heap_pop (h)

val () = println!("front:", heap_front(h))

val () = heap_pop (h)

val () = println!("front: ", heap_front(h))

val () = heap_pop (h)

val () = println!("front: ", heap_front(h))

val () = heap_pop (h)

val () = heap_term (h)

in

print"Hello World!\n"

end