Well yeah I've fired my debugger and looked at what heap->items is pointing to...so far I haven't caught anything fishy
If you have the patience to look over the code, here it is (at least the relevant parts):
The tester:
Code:
int main() {
int memory_used;
Table *heap;
mcheck_pedantic(NULL);
heap= create(); /* code posted in my initial post */
insert(&heap, 1, 100);
delete(&heap, 1);
printf("Size: %d\n", size(heap));
insert(&heap, 2, 200);
if (delete(&heap, 3) == 1)
printf("removed a non-existent key\n");
else printf("Size: %d\n", size(heap));
clear(&heap);
mcheck_check_all();
the insert function
Code:
Data insert(Table **table, Key key, Data item)
{
Table *t = *table;
Item new_item;
Item *exists = contains(t, key), *new_item_pntr = NULL,
*new_item_parent_pntr = NULL;
Item * first_item = t->items; /* should be read-only! */
int index = 0;
if (table == NULL)
return 0;
new_item.key = key;
new_item.data = item;
/* case where key already exists in table */
if (exists != NULL)
{
exists->data = item;
return exists->data;
}
/* case where key doesn't exist in table */
if (t->size == t->max) /* need to make table bigger*/
{
int new_max = (t->max*2) + 1;
Item *items = realloc(t->items, new_max);
HANDLE_OUT_OF_MEM(items);
t->items = items;
t->max = new_max;
/* update first_item variable */
first_item = t->items;
}
/*
* add new_item into table
*/
index = t->size;
new_item_pntr = first_item + GET_RELATIVE_MEM_ADDR_OF_INDEX(index);
*new_item_pntr = new_item;
memcpy(new_item_pntr, &new_item, sizeof(Item));
printf("Adding %d, %d to %d\n", key, item, (int)new_item_pntr);
/*
* if it is first item to be inserted, so no need to bother
* bubbling up the item
*/
if (t->size == 0) /* using == 0 because size isn't updated yet*/
{
++(t->size);
*table = t;
return new_item_pntr->data;
}
index = GET_PARENT_OF_INDEX(index);
new_item_parent_pntr = first_item +
GET_RELATIVE_MEM_ADDR_OF_INDEX(index);
/* bubble new_item up */
while (new_item_pntr->key < new_item_parent_pntr->key)
{
item_memswap(new_item_pntr, new_item_parent_pntr);
index = GET_PARENT_OF_INDEX(index);
new_item_pntr = new_item_parent_pntr;
new_item_parent_pntr = first_item +
GET_RELATIVE_MEM_ADDR_OF_INDEX(index);
}
++(t->size);
*table = t;
return new_item_pntr->data; /* could just return data, but this
serves as a debugging statement
also */
}
the delete
Code:
int delete(Table **table, Key key)
{
Item * to_remove, *last, *temp, *first;
Table * t;
int index = 0, direction = 0;
if (table == NULL || (*table)->size == 0)
return 0;
t = *table;
first = t->items;
to_remove = contains(t, key);
if (to_remove == NULL)
return 0;
last = first + GET_RELATIVE_MEM_ADDR_OF_INDEX((t->size)-1);
index = get_item_index(t, to_remove->key);
if (t->size > 1)
item_memswap(last, to_remove);
temp = last;
last = to_remove;
to_remove = temp;
--(t->size); /* this is the removal part, the next item
to be inserted will overwrite the last element
which was to be removed anyways */
/* bubble last up or down */
direction = 0; /* direction 1 means bubble up, 0 means
bubble down */
if (last->key < (first + GET_RELATIVE_MEM_ADDR_OF_INDEX (
GET_PARENT_OF_INDEX(index)
))->key)
direction = 1;
if (t->size > 1)
{
if (direction) /* bubble up */
{
Item * parent = first + GET_RELATIVE_MEM_ADDR_OF_INDEX (
GET_PARENT_OF_INDEX(index)
);
while (last->key < parent->key)
{
item_memswap(last, parent);
index = GET_PARENT_OF_INDEX(index);
last = parent;
parent = first + GET_RELATIVE_MEM_ADDR_OF_INDEX(index);
}
}
else /* bubble down */
{
Item *right_child, *left_child, *changed = NULL;
right_child = first + GET_RELATIVE_MEM_ADDR_OF_INDEX (
GET_RIGHT_CHILD_OF_INDEX(index)
);
left_child = first + GET_RELATIVE_MEM_ADDR_OF_INDEX (
GET_LEFT_CHILD_OF_INDEX(index)
);
while (last->key > right_child->key ||
last->key > left_child->key )
{
if (right_child->key > left_child->key)
changed = right_child;
else
changed = left_child;
item_memswap(last, changed);
index = get_item_index(t, changed->key);
last = changed;
right_child = first + GET_RELATIVE_MEM_ADDR_OF_INDEX (
GET_RIGHT_CHILD_OF_INDEX(index)
);
left_child = first + GET_RELATIVE_MEM_ADDR_OF_INDEX (
GET_LEFT_CHILD_OF_INDEX(index)
);
}
}
}
/* update the capacity of the table */
if ((double)size(t)/(double)capacity(t) < 0.25)
{
int new_max = ((t->size)-1)/2;
Item *items = realloc(t->items, new_max*sizeof(Item));
HANDLE_OUT_OF_MEM(items);
t->items = items;
printf("new items at %d\n", (int)(t->items));
t->max = new_max;
}
*table = t;
return 1;
}
and finally the clear
Code:
void clear(Table **table)
{
if (table != NULL && *table != NULL)
{
printf("table at %d\n", (int)(*table));
printf("Items at %d\n", (int)((*table)->items));
free(((*table)->items));
(*table)->size = 0;
(*table)->max = 0;
free(*table);
}
}