1 /* 2 * Author: Armon Dadgar 3 * 4 * Header for the Heap functions and data definitions 5 */ 6 7 #ifndef HEAP_H 8 #define HEAP_H 9 10 // Structure for a single heap entry 11 typedef struct heap_entry { 12 void* key; // Key for this entry 13 void* value; // Value for this entry 14 } heap_entry; 15 16 17 // Main struct for representing the heap 18 typedef struct heap { 19 int (*compare_func)(void*, void*); // The key comparison function to use 20 int active_entries; // The number of entries in the heap 21 int minimum_pages; // The minimum number of pages to maintain, based on the initial cap. 22 int allocated_pages; // The number of pages in memory that are allocated 23 heap_entry* table; // Pointer to the table, which maps to the pages 24 } heap; 25 26 // Functions 27 28 /** 29 * Creates a new heap 30 * @param h Pointer to a heap structure that is initialized 31 * @param initial_size What should the initial size of the heap be. If <= 0, then it will be set to the minimum 32 * permissable size, of 1 page (512 entries on 32bit system with 4K pages). 33 * @param comp_func A pointer to a function that can be used to compare the keys. If NULL, it will be set 34 * to a function which treats keys as signed ints. This function must take two keys, given as pointers and return an int. 35 * It should return -1 if key 1 is smaller, 0 if they are equal, and 1 if key 2 is smaller. 36 */ 37 void heap_create(heap* h, int initial_size, int (*comp_func)(void*,void*)); 38 39 /** 40 * Returns the size of the heap 41 * @param h Pointer to a heap structure 42 * @return The number of entries in the heap. 43 */ 44 int heap_size(heap* h); 45 46 /** 47 * Inserts a new element into a heap. 48 * @param h The heap to insert into 49 * @param key The key of the new entry 50 * @param value The value of the new entry 51 */ 52 void heap_insert(heap* h, void* key, void* value); 53 54 /** 55 * Returns the element with the smallest key in the heap. 56 * @param h Pointer to the heap structure 57 * @param key A pointer to a pointer, to set to the minimum key 58 * @param value Set to the value corresponding with the key 59 * @return 1 if the minimum element exists and is set, 0 if there are no elements. 60 */ 61 int heap_min(heap* h, void** key, void** value); 62 63 /** 64 * Deletes the element with the smallest key from the heap. 65 * @param h Pointer to the heap structure 66 * @param key A pointer to a pointer, to set to the minimum key 67 * @param valu Set to the value corresponding with the key 68 * @return 1if the minimum element exists and is deleted, 0 if there are no elements. 69 */ 70 int heap_delmin(heap* h, void** key, void** value); 71 72 /** 73 * Calls a function for each entry in the heap. 74 * @param h The heap to iterate over 75 * @param func The function to call on each entry. Should take a void* key and value. 76 */ 77 void heap_foreach(heap* h, void (*func)(void*,void*)); 78 79 /** 80 * Destroys and cleans up a heap. 81 * @param h The heap to destroy. 82 */ 83 void heap_destroy(heap* h); 84 85 #endif 86 87