PoeMac/C workers/heap.c
int heap_delmin(heap* h, void** key, void** value) {
    // Check there is a minimum
    if (h->active_entries == 0)
        return 0;

    // Load in the map table
    heap_entry* table = h->table;

    // Get the root element
    int current_index = 0;
    heap_entry* current = GET_ENTRY(current_index, table);

    // Store the outputs
    if (key) *key = current->key;
    if (value) *value = current->value;

    // Reduce the number of active entries
    h->active_entries--;

    // Get the active entries
    int entries = h->active_entries;

    // If there are any other nodes, we may need to move them up
    if (h->active_entries > 0) {
        // Move the last element to the root
        heap_entry* last = GET_ENTRY(entries,table);
        current->key = last->key;
        current->value = last->value;

        // Loop variables
        heap_entry* left_child;
        heap_entry* right_child;

        // Load the comparison function
        int (*cmp_func)(void*,void*) = h->compare_func;

        // Store the left index
        int left_child_index;

			while ((void)(left_child_index = LEFT_CHILD(current_index)), left_child_index < entries)  {
            // Load the left child
            left_child = GET_ENTRY(left_child_index, table);

            // We have a left + right child
            if (left_child_index+1 < entries) {
                // Load the right child
                right_child = GET_ENTRY((left_child_index+1), table);

                // Find the smaller child
                if (cmp_func(left_child->key, right_child->key) <= 0) {

                    // Swap with the left if it is smaller
                    if (cmp_func(current->key, left_child->key) == 1) {
                        SWAP_ENTRIES(current,left_child);
                        current_index = left_child_index;
                        current = left_child;

                    // Otherwise, the current is smaller
                    } else
                        break;

                // Right child is smaller
                } else {

                    // Swap with the right if it is smaller
                    if (cmp_func(current->key, right_child->key) == 1) {
                        SWAP_ENTRIES(current,right_child);
                        current_index = left_child_index+1;
                        current = right_child;

                    // Current is smaller
                    } else
                        break;

                }


            // We only have a left child, only do something if the left is smaller
            } else if (cmp_func(current->key, left_child->key) == 1) {
                SWAP_ENTRIES(current,left_child);
                current_index = left_child_index;
                current = left_child;

            // Done otherwise
            }  else
                break;

        }
    }

    // Check if we should release a page of memory
    int used_pages = entries / ENTRIES_PER_PAGE + ((entries % ENTRIES_PER_PAGE > 0) ? 1 : 0);

    // Allow one empty page, but not two
    if (h->allocated_pages / 2 > used_pages + 1 && h->allocated_pages / 2 >= h->minimum_pages) {
        // Get the new number of entries we need
        int new_size = h->allocated_pages / 2;

        // Map in a new table
        heap_entry* new_table = map_in_pages(new_size);

        // Copy the old entries, copy the entire pages
        memcpy(new_table, h->table, used_pages*MEM_PAGE_SIZE);

        // Cleanup the old table
        map_out_pages(h->table, h->allocated_pages);

        // Switch to the new table
        h->table = new_table;
        h->allocated_pages = new_size;
    }

    // Success
    return 1;
}
// Deletes the minimum entry in the heap
Deletes the minimum entry in the heap
Deletes the minimum entry in the heap
int heap_delmin(heap* h, void** key, void** value) {
    if (h->active_entries == 0)
        return 0;
    heap_entry* table = h->table;
    int current_index = 0;
    heap_entry* current = GET_ENTRY(current_index, table);
    if (key) *key = current->key;
    if (value) *value = current->value;
    h->active_entries--;
    int entries = h->active_entries;
    if (h->active_entries > 0) {
        heap_entry* last = GET_ENTRY(entries,table);
        current->key = last->key;
        current->value = last->value;
        heap_entry* left_child;
        heap_entry* right_child;
        int (*cmp_func)(void*,void*) = h->compare_func;
        int left_child_index;
			while ((void)(left_child_index = LEFT_CHILD(current_index)), left_child_index < entries)  {
            left_child = GET_ENTRY(left_child_index, table);
            if (left_child_index+1 < entries) {
                right_child = GET_ENTRY((left_child_index+1), table);
                if (cmp_func(left_child->key, right_child->key) <= 0) {
                    if (cmp_func(current->key, left_child->key) == 1) {
                        SWAP_ENTRIES(current,left_child);
                        current_index = left_child_index;
                        current = left_child;
                    } else
                        break;
                } else {
                    if (cmp_func(current->key, right_child->key) == 1) {
                        SWAP_ENTRIES(current,right_child);
                        current_index = left_child_index+1;
                        current = right_child;
                    } else
                        break;
                }
            } else if (cmp_func(current->key, left_child->key) == 1) {
                SWAP_ENTRIES(current,left_child);
                current_index = left_child_index;
                current = left_child;
            }  else
                break;
        }
    }
    int used_pages = entries / ENTRIES_PER_PAGE + ((entries % ENTRIES_PER_PAGE > 0) ? 1 : 0);
    if (h->allocated_pages / 2 > used_pages + 1 && h->allocated_pages / 2 >= h->minimum_pages) {
        int new_size = h->allocated_pages / 2;
        heap_entry* new_table = map_in_pages(new_size);
        memcpy(new_table, h->table, used_pages*MEM_PAGE_SIZE);
        map_out_pages(h->table, h->allocated_pages);
        h->table = new_table;
        h->allocated_pages = new_size;
    }
    return 1;
}
int heap_delmin ( heap * h , void * * key , void * * value ) { if ( h -> active_entries == 0 ) return 0 ; heap_entry * table = h -> table ; int current_index = 0 ; heap_entry * current = GET_ENTRY ( current_index , table ) ; if ( key ) * key = current -> key ; if ( value ) * value = current -> value ; h -> active_entries -- ; int entries = h -> active_entries ; if ( h -> active_entries > 0 ) { heap_entry * last = GET_ENTRY ( entries , table ) ; current -> key = last -> key ; current -> value = last -> value ; heap_entry * left_child ; heap_entry * right_child ; int ( * cmp_func ) ( void * , void * ) = h -> compare_func ; int left_child_index ; while ( ( void ) ( left_child_index = LEFT_CHILD ( current_index ) ) , left_child_index < entries ) { left_child = GET_ENTRY ( left_child_index , table ) ; if ( left_child_index + 1 < entries ) { right_child = GET_ENTRY ( ( left_child_index + 1 ) , table ) ; if ( cmp_func ( left_child -> key , right_child -> key ) <= 0 ) { if ( cmp_func ( current -> key , left_child -> key ) == 1 ) { SWAP_ENTRIES ( current , left_child ) ; current_index = left_child_index ; current = left_child ; } else break ; } else { if ( cmp_func ( current -> key , right_child -> key ) == 1 ) { SWAP_ENTRIES ( current , right_child ) ; current_index = left_child_index + 1 ; current = right_child ; } else break ; } } else if ( cmp_func ( current -> key , left_child -> key ) == 1 ) { SWAP_ENTRIES ( current , left_child ) ; current_index = left_child_index ; current = left_child ; } else break ; } } int used_pages = entries / ENTRIES_PER_PAGE + ( ( entries % ENTRIES_PER_PAGE > 0 ) ? 1 : 0 ) ; if ( h -> allocated_pages / 2 > used_pages + 1 && h -> allocated_pages / 2 >= h -> minimum_pages ) { int new_size = h -> allocated_pages / 2 ; heap_entry * new_table = map_in_pages ( new_size ) ; memcpy ( new_table , h -> table , used_pages * MEM_PAGE_SIZE ) ; map_out_pages ( h -> table , h -> allocated_pages ) ; h -> table = new_table ; h -> allocated_pages = new_size ; } return 1 ; }
Deletes the minimum entry in the heap
Deletes the minimum entry in the heap
// Check there is a minimum // Load in the map table // Get the root element // Store the outputs // Reduce the number of active entries // Get the active entries // If there are any other nodes, we may need to move them up // Move the last element to the root // Loop variables // Load the comparison function // Store the left index // Load the left child // We have a left + right child // Load the right child // Find the smaller child // Swap with the left if it is smaller // Otherwise, the current is smaller // Right child is smaller // Swap with the right if it is smaller // Current is smaller // We only have a left child, only do something if the left is smaller // Done otherwise // Check if we should release a page of memory // Allow one empty page, but not two // Get the new number of entries we need // Map in a new table // Copy the old entries, copy the entire pages // Cleanup the old table // Switch to the new table // Success