diff options
Diffstat (limited to 'libiberty/fibheap.c')
| -rw-r--r-- | libiberty/fibheap.c | 121 |
1 files changed, 38 insertions, 83 deletions
diff --git a/libiberty/fibheap.c b/libiberty/fibheap.c index bcecf80..e1d818c 100644 --- a/libiberty/fibheap.c +++ b/libiberty/fibheap.c @@ -37,32 +37,31 @@ Boston, MA 02111-1307, USA. */ #define FIBHEAPKEY_MIN LONG_MIN -static void fibheap_ins_root PARAMS ((fibheap_t, fibnode_t)); -static void fibheap_rem_root PARAMS ((fibheap_t, fibnode_t)); -static void fibheap_consolidate PARAMS ((fibheap_t)); -static void fibheap_link PARAMS ((fibheap_t, fibnode_t, fibnode_t)); -static void fibheap_cut PARAMS ((fibheap_t, fibnode_t, fibnode_t)); -static void fibheap_cascading_cut PARAMS ((fibheap_t, fibnode_t)); -static fibnode_t fibheap_extr_min_node PARAMS ((fibheap_t)); -static int fibheap_compare PARAMS ((fibheap_t, fibnode_t, fibnode_t)); -static int fibheap_comp_data PARAMS ((fibheap_t, fibheapkey_t, void *, - fibnode_t)); -static fibnode_t fibnode_new PARAMS ((void)); -static void fibnode_insert_after PARAMS ((fibnode_t, fibnode_t)); +static void fibheap_ins_root (fibheap_t, fibnode_t); +static void fibheap_rem_root (fibheap_t, fibnode_t); +static void fibheap_consolidate (fibheap_t); +static void fibheap_link (fibheap_t, fibnode_t, fibnode_t); +static void fibheap_cut (fibheap_t, fibnode_t, fibnode_t); +static void fibheap_cascading_cut (fibheap_t, fibnode_t); +static fibnode_t fibheap_extr_min_node (fibheap_t); +static int fibheap_compare (fibheap_t, fibnode_t, fibnode_t); +static int fibheap_comp_data (fibheap_t, fibheapkey_t, void *, fibnode_t); +static fibnode_t fibnode_new (void); +static void fibnode_insert_after (fibnode_t, fibnode_t); #define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b) -static fibnode_t fibnode_remove PARAMS ((fibnode_t)); +static fibnode_t fibnode_remove (fibnode_t); /* Create a new fibonacci heap. */ fibheap_t -fibheap_new () +fibheap_new (void) { return (fibheap_t) xcalloc (1, sizeof (struct fibheap)); } /* Create a new fibonacci heap node. */ static fibnode_t -fibnode_new () +fibnode_new (void) { fibnode_t node; @@ -74,10 +73,7 @@ fibnode_new () } static inline int -fibheap_compare (heap, a, b) - fibheap_t heap ATTRIBUTE_UNUSED; - fibnode_t a; - fibnode_t b; +fibheap_compare (fibheap_t heap ATTRIBUTE_UNUSED, fibnode_t a, fibnode_t b) { if (a->key < b->key) return -1; @@ -87,11 +83,7 @@ fibheap_compare (heap, a, b) } static inline int -fibheap_comp_data (heap, key, data, b) - fibheap_t heap; - fibheapkey_t key; - void *data; - fibnode_t b; +fibheap_comp_data (fibheap_t heap, fibheapkey_t key, void *data, fibnode_t b) { struct fibnode a; @@ -103,10 +95,7 @@ fibheap_comp_data (heap, key, data, b) /* Insert DATA, with priority KEY, into HEAP. */ fibnode_t -fibheap_insert (heap, key, data) - fibheap_t heap; - fibheapkey_t key; - void *data; +fibheap_insert (fibheap_t heap, fibheapkey_t key, void *data) { fibnode_t node; @@ -132,8 +121,7 @@ fibheap_insert (heap, key, data) /* Return the data of the minimum node (if we know it). */ void * -fibheap_min (heap) - fibheap_t heap; +fibheap_min (fibheap_t heap) { /* If there is no min, we can't easily return it. */ if (heap->min == NULL) @@ -143,8 +131,7 @@ fibheap_min (heap) /* Return the key of the minimum node (if we know it). */ fibheapkey_t -fibheap_min_key (heap) - fibheap_t heap; +fibheap_min_key (fibheap_t heap) { /* If there is no min, we can't easily return it. */ if (heap->min == NULL) @@ -154,9 +141,7 @@ fibheap_min_key (heap) /* Union HEAPA and HEAPB into a new heap. */ fibheap_t -fibheap_union (heapa, heapb) - fibheap_t heapa; - fibheap_t heapb; +fibheap_union (fibheap_t heapa, fibheap_t heapb) { fibnode_t a_root, b_root, temp; @@ -190,8 +175,7 @@ fibheap_union (heapa, heapb) /* Extract the data of the minimum node from HEAP. */ void * -fibheap_extract_min (heap) - fibheap_t heap; +fibheap_extract_min (fibheap_t heap) { fibnode_t z; void *ret = NULL; @@ -211,11 +195,8 @@ fibheap_extract_min (heap) /* Replace both the KEY and the DATA associated with NODE. */ void * -fibheap_replace_key_data (heap, node, key, data) - fibheap_t heap; - fibnode_t node; - fibheapkey_t key; - void *data; +fibheap_replace_key_data (fibheap_t heap, fibnode_t node, + fibheapkey_t key, void *data) { void *odata; fibheapkey_t okey; @@ -253,20 +234,14 @@ fibheap_replace_key_data (heap, node, key, data) /* Replace the DATA associated with NODE. */ void * -fibheap_replace_data (heap, node, data) - fibheap_t heap; - fibnode_t node; - void *data; +fibheap_replace_data (fibheap_t heap, fibnode_t node, void *data) { return fibheap_replace_key_data (heap, node, node->key, data); } /* Replace the KEY associated with NODE. */ fibheapkey_t -fibheap_replace_key (heap, node, key) - fibheap_t heap; - fibnode_t node; - fibheapkey_t key; +fibheap_replace_key (fibheap_t heap, fibnode_t node, fibheapkey_t key) { int okey = node->key; fibheap_replace_key_data (heap, node, key, node->data); @@ -275,9 +250,7 @@ fibheap_replace_key (heap, node, key) /* Delete NODE from HEAP. */ void * -fibheap_delete_node (heap, node) - fibheap_t heap; - fibnode_t node; +fibheap_delete_node (fibheap_t heap, fibnode_t node) { void *ret = node->data; @@ -290,8 +263,7 @@ fibheap_delete_node (heap, node) /* Delete HEAP. */ void -fibheap_delete (heap) - fibheap_t heap; +fibheap_delete (fibheap_t heap) { while (heap->min != NULL) free (fibheap_extr_min_node (heap)); @@ -301,16 +273,14 @@ fibheap_delete (heap) /* Determine if HEAP is empty. */ int -fibheap_empty (heap) - fibheap_t heap; +fibheap_empty (fibheap_t heap) { return heap->nodes == 0; } /* Extract the minimum node of the heap. */ static fibnode_t -fibheap_extr_min_node (heap) - fibheap_t heap; +fibheap_extr_min_node (fibheap_t heap) { fibnode_t ret = heap->min; fibnode_t x, y, orig; @@ -346,9 +316,7 @@ fibheap_extr_min_node (heap) /* Insert NODE into the root list of HEAP. */ static void -fibheap_ins_root (heap, node) - fibheap_t heap; - fibnode_t node; +fibheap_ins_root (fibheap_t heap, fibnode_t node) { /* If the heap is currently empty, the new node becomes the singleton circular root list. */ @@ -367,9 +335,7 @@ fibheap_ins_root (heap, node) /* Remove NODE from the rootlist of HEAP. */ static void -fibheap_rem_root (heap, node) - fibheap_t heap; - fibnode_t node; +fibheap_rem_root (fibheap_t heap, fibnode_t node) { if (node->left == node) heap->root = NULL; @@ -379,8 +345,7 @@ fibheap_rem_root (heap, node) /* Consolidate the heap. */ static void -fibheap_consolidate (heap) - fibheap_t heap; +fibheap_consolidate (fibheap_t heap) { fibnode_t a[1 + 8 * sizeof (long)]; fibnode_t w; @@ -427,10 +392,8 @@ fibheap_consolidate (heap) /* Make NODE a child of PARENT. */ static void -fibheap_link (heap, node, parent) - fibheap_t heap ATTRIBUTE_UNUSED; - fibnode_t node; - fibnode_t parent; +fibheap_link (fibheap_t heap ATTRIBUTE_UNUSED, + fibnode_t node, fibnode_t parent) { if (parent->child == NULL) parent->child = node; @@ -443,10 +406,7 @@ fibheap_link (heap, node, parent) /* Remove NODE from PARENT's child list. */ static void -fibheap_cut (heap, node, parent) - fibheap_t heap; - fibnode_t node; - fibnode_t parent; +fibheap_cut (fibheap_t heap, fibnode_t node, fibnode_t parent) { fibnode_remove (node); parent->degree--; @@ -456,9 +416,7 @@ fibheap_cut (heap, node, parent) } static void -fibheap_cascading_cut (heap, y) - fibheap_t heap; - fibnode_t y; +fibheap_cascading_cut (fibheap_t heap, fibnode_t y) { fibnode_t z; @@ -478,9 +436,7 @@ fibheap_cascading_cut (heap, y) } static void -fibnode_insert_after (a, b) - fibnode_t a; - fibnode_t b; +fibnode_insert_after (fibnode_t a, fibnode_t b) { if (a == a->right) { @@ -499,8 +455,7 @@ fibnode_insert_after (a, b) } static fibnode_t -fibnode_remove (node) - fibnode_t node; +fibnode_remove (fibnode_t node) { fibnode_t ret; |