Here it is:
// zcc +rc2014 -subtype=rom -v -m -SO3 --max-allocs-per-node200000 --c-code-in-asm --list heapsort.c -o heapsort -create-app
//
// -subtype=rom : make uncompressed rom mapped to address 0x0 (see z88dk/lib/config/rc2014.cfg for options this selects)
// -v : tell us what zcc is up to, -vn for quiet
// -m : create a map file of symbols ("timer_start" and "timer_end" defined below will appear in there)
// -SO3 : select the aggressive peephole set
// --max-allocs-per-node200000 : optimization level is set very high
// --c-code-in-asm : intersperse C statements in the .lis file
// --list : generate a .lis file containing asm translation just prior to link step
// -create-app : generate an intex hex file .ihx as well as .rom/.bin raw binary to be loaded at address 0x0
// : the actual compiler output is heapsort_BSS.bin, heapsort_DATA.bin, heapsort_CODE.bin
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <adt/wa_priority_queue.h>
#include <intrinsic.h>
#pragma output CLIB_OPT_PRINTF = 0x202 // enable %u%s only
#pragma output CLIB_OPT_SCANF = 0x2 // enable %u only
#pragma output CLIB_MALLOC_HEAP_SIZE = 5000 // specify a 5k heap
wa_priority_queue_t queue;
// greater than compare for ascending order because we want the priority
// queue to extract largest first and write that to the end of the array
int compare(unsigned int *a, unsigned int *b)
{
return *b - *a;
}
void main(void)
{
static unsigned int i;
static unsigned int num;
static unsigned int *p;
queue.data = NULL;
while (1)
{
// how many numbers are we sorting
printf("\nHow many values do you want to sort? ");
scanf("%u", &num);
// get memory to hold the numbers
free(queue.data);
if ((num == 0) || ((p = malloc(num*sizeof(*p))) == NULL))
{
printf("Can't malloc %u items, try again.\n", num);
continue;
}
// fill array with random numbers
for (i=0; i!=num; ++i)
p[i] = rand();
// print the random numbers generated
printf("\nSORTING SAMPLE OF %u NUMBERS: ", num);
for (i=0; i!=num; ++i)
printf("%u%s", p[i], (i != num-1) ? ", " : "\n");
intrinsic_label(timer_start);
// turn the non-empty random array into a heap
wa_priority_queue_init(&queue, p, num, compare); // queue contains zero items, max capacity = num
wa_priority_queue_resize(&queue, num); // resize to num items, uncovered items in array assumed valid
// sort items by popping them out of the priority queue max number first
// could print them here but let's time it without printf
while (!wa_priority_queue_empty(&queue))
wa_priority_queue_pop(&queue);
intrinsic_label(timer_stop);
// print the result out
printf("\nAFTER SORTING: ");
for (i=0; i!=num; ++i)
printf("%u%s", p[i], (i != num-1) ? ", " : "\n\n");
}
}
The abstract data types are modeled on C++ stl containers so if you know C++ you may recognize the priority queue type. This is C so there are no constructors or destructors but instead *_init and *_destroy. The containers can only hold two types of data :- bytes (8-bit) or words (16-bit) but words can also mean pointers so there is no limitation. The above is using "wa_priority_queue_t" which is a word array priority queue. word = 16-bit items, array = stored in a fixed size array, priority queue = heap. There is a byte variation and a vector variation; vector means the queue can expand dynamically via realloc.
The compile line is at the top, the final output is "heapsort.bin" or "heapsort.ihx" depending on whether you want a raw binary or intel hex format. In both cases the ORG is 0x0.
I inserted two assembly language labels using non-standard function "intrinsic_label(...);". The address corresponding to these two labels can be seen in the heapsort.map file. This will allow timing of the heapsort using TICKS (a command line z80 emulator that comes with z88dk that counts how long a code fragment takes in z80 cycles).
TICKS simulates a z80 computer with 64k ram and nothing else which means we should avoid interactions with hw like printf and scanf if we want TICKS to work. If you comment out the printf and scanf and hard-code the number of items to 500 by setting "num=500;", do another compile and find out what the label addresses are from the map file, we can run TICKS to find out how fast the sort was.
From my compile's map file:
timer_start = 0x0fd3
timer_stop = 0x1004
Then run TICKS on the output binary:
ticks heapsort.bin -start fd3 -stop 1004
The result is 4,842,526 cycles or 657 milliseconds @ 7.372800 MHz.