Hi!
I need to create a temporary, sorted array for subsequent binary searching.
I have the following declarations:
typedef struct {
ULong id;
int order;
} sort_element;
sort_element *pp_array;
int sort_count = 0;
int total; // gets set to # of items to sort
ULong add_id;
I then set TOTAL to the correct value, and execute the following:
pp_array = MemPtrNew(total * sizeof(sort_element));
for (i=0; i<total; i++) {
add_id = ...; // get the next value
insertion_sort(pp_array, sort_count, i, add_id);
sort_count++;
}
My insertion sort was the following:
static void insertion_sort(sort_element *array, int count, int i, ULong id)
{
int j;
for (j=count; (j>0) && (id < array[j-1].id); j--) {
MemMove(&(array[j]), &(array[j-1]), sizeof(sort_element));
}
array[j].id = id;
array[j].order = i;
}
The FOR loop moves elements, one at a time, down one slot, until it finds
the slot where the new item should go. It then fills in the new slot with
the passed values, thus keeping the list in sorted order.
While this code works perfectly, I realized that instead of moving array
elements one at a time, I ought to be able to move them in one big chunk,
which should be much faster. So, I changed my insertion sort to look like
this:
static void insertion_sort(sort_element *array, int count, int i, ULong id)
{
int j;
for (j=count; (j>0) && (id < array[j-1].id); j--) { }
if (j != count)
MemMove(&(array[count]), &(array[count-1]),
(ULong) ((ULong) (count-j) * (ULong) sizeof(sort_element)));
array[j].id = id;
array[j].order = i;
}
As before, I find the correct slot, move everything below that down 1 slot,
and the fill in the passed values.
In my test case, TOTAL is 38. On the call to this routine where COUNT = 33,
J is found to be 27, and the MemMove dies with the error message:
"<application> has just written directly to memory manager data structures."
It's trying to move only 36 bytes (sizeof(sort_element) is 6, and count-j is
also 6). Since J is 27, it's trying to move the contents of slots 27 though
32 into slots 28 through 33. All those casts to ULong are in there because I
was trying to figure out what the problem could be, and ULong is what the
doc says for MemMove.
MemMove DOES handle overlapping strings, right? Are there any boundaries
that I need to worry about crossing when using MemMove?
Any ideas on what the problem could be, or how I could track it down?
Thanks for any help you can give me!
Tom Ward
