binutils/libiberty/fibheap.c

1 /* A Fibonacci heap datatype.
56 /* Create a new fibonacci heap.  */
63 /* Create a new fibonacci heap node.  */
77 fibheap_compare (fibheap_t heap ATTRIBUTE_UNUSED, fibnode_t a, fibnode_t b)
87 fibheap_comp_data (fibheap_t heap, fibheapkey_t key, void *data, fibnode_t b)
94   return fibheap_compare (heap, &a, b);
99 fibheap_insert (fibheap_t heap, fibheapkey_t key, void *data)
111   fibheap_ins_root (heap, node);
115   if (heap->min == NULL || node->key < heap->min->key)
116     heap->min = node;
118   heap->nodes++;
125 fibheap_min (fibheap_t heap)
128   if (heap->min == NULL)
130   return heap->min->data;
135 fibheap_min_key (fibheap_t heap)
138   if (heap->min == NULL)
140   return heap->min->key;
143 /* Union HEAPA and HEAPB into a new heap.  */
149   /* If one of the heaps is empty, the union is just the other heap.  */
179 fibheap_extract_min (fibheap_t heap)
185   if (heap->min != NULL)
189       z = fibheap_extr_min_node (heap);
199 fibheap_replace_key_data (fibheap_t heap, fibnode_t node,
209   if (fibheap_comp_data (heap, key, data, node) > 0)
224   if (y != NULL && fibheap_compare (heap, node, y) <= 0)
226       fibheap_cut (heap, node, y);
227       fibheap_cascading_cut (heap, y);
230   if (fibheap_compare (heap, node, heap->min) <= 0)
231     heap->min = node;
238 fibheap_replace_data (fibheap_t heap, fibnode_t node, void *data)
240   return fibheap_replace_key_data (heap, node, node->key, data);
245 fibheap_replace_key (fibheap_t heap, fibnode_t node, fibheapkey_t key)
248   fibheap_replace_key_data (heap, node, key, node->data);
254 fibheap_delete_node (fibheap_t heap, fibnode_t node)
259   fibheap_replace_key (heap, node, FIBHEAPKEY_MIN);
260   fibheap_extract_min (heap);
267 fibheap_delete (fibheap_t heap)
269   while (heap->min != NULL)
270     free (fibheap_extr_min_node (heap));
272   free (heap);
277 fibheap_empty (fibheap_t heap)
279   return heap->nodes == 0;
282 /* Extract the minimum node of the heap.  */
284 fibheap_extr_min_node (fibheap_t heap)
286   fibnode_t ret = heap->min;
289   /* Attach the child list of the minimum node to the root list of the heap.
297       fibheap_ins_root (heap, x);
301   fibheap_rem_root (heap, ret);
302   heap->nodes--;
305   if (heap->nodes == 0)
306     heap->min = NULL;
311       heap->min = ret->right;
312       fibheap_consolidate (heap);
320 fibheap_ins_root (fibheap_t heap, fibnode_t node)
322   /* If the heap is currently empty, the new node becomes the singleton
324   if (heap->root == NULL)
326       heap->root = node;
334   fibnode_insert_after (heap->root, node);
339 fibheap_rem_root (fibheap_t heap, fibnode_t node)
342     heap->root = NULL;
344     heap->root = fibnode_remove (node);
347 /* Consolidate the heap.  */
349 fibheap_consolidate (fibheap_t heap)
363   while ((w = heap->root) != NULL)
366       fibheap_rem_root (heap, w);
371 	  if (fibheap_compare (heap, x, y) > 0)
378 	  fibheap_link (heap, y, x);
384   heap->min = NULL;
388 	fibheap_ins_root (heap, a[i]);
389 	if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0)
390 	  heap->min = a[i];
396 fibheap_link (fibheap_t heap ATTRIBUTE_UNUSED,
410 fibheap_cut (fibheap_t heap, fibnode_t node, fibnode_t parent)
414   fibheap_ins_root (heap, node);
420 fibheap_cascading_cut (fibheap_t heap, fibnode_t y)
433 	  fibheap_cut (heap, y, z);