dist/libiberty/fibheap.c

63 /* Create a new fibonacci heap node.  */
67   fibnode_t node;
69   node = (fibnode_t) xcalloc (1, sizeof *node);
70   node->left = node;
71   node->right = node;
73   return node;
101   fibnode_t node;
103   /* Create the new node.  */
104   node = fibnode_new ();
106   /* Set the node's data.  */
107   node->data = data;
108   node->key = key;
111   fibheap_ins_root (heap, node);
115   if (heap->min == NULL || node->key < heap->min->key)
116     heap->min = node;
120   return node;
123 /* Return the data of the minimum node (if we know it).  */
133 /* Return the key of the minimum node (if we know it).  */
177 /* Extract the data of the minimum node from HEAP.  */
187       /* Otherwise, extract the min node, free the node, and return the
188          node's data.  */
199 fibheap_replace_key_data (fibheap_t heap, fibnode_t node,
209   if (fibheap_comp_data (heap, key, data, node) > 0)
212   odata = node->data;
213   okey = node->key;
214   node->data = data;
215   node->key = key;
216   y = node->parent;
219      do anything.  Except if we're trying to force the new node to
225      of equality, a node we replaced the data on, becomes the new min.  This
226      is needed so that delete's call to extractmin gets the right node.  */
227   if (y != NULL && fibheap_compare (heap, node, y) <= 0)
229       fibheap_cut (heap, node, y);
233   if (fibheap_compare (heap, node, heap->min) <= 0)
234     heap->min = node;
241 fibheap_replace_data (fibheap_t heap, fibnode_t node, void *data)
243   return fibheap_replace_key_data (heap, node, node->key, data);
248 fibheap_replace_key (fibheap_t heap, fibnode_t node, fibheapkey_t key)
250   int okey = node->key;
251   fibheap_replace_key_data (heap, node, key, node->data);
257 fibheap_delete_node (fibheap_t heap, fibnode_t node)
259   void *ret = node->data;
262   fibheap_replace_key (heap, node, FIBHEAPKEY_MIN);
263   if (node != heap->min)
290 /* Extract the minimum node of the heap.  */
297   /* Attach the child list of the minimum node to the root list of the heap.
328 fibheap_ins_root (fibheap_t heap, fibnode_t node)
330   /* If the heap is currently empty, the new node becomes the singleton
334       heap->root = node;
335       node->left = node;
336       node->right = node;
341      and it's right node.  */
342   fibnode_insert_after (heap->root, node);
347 fibheap_rem_root (fibheap_t heap, fibnode_t node)
349   if (node->left == node)
352     heap->root = fibnode_remove (node);
405               fibnode_t node, fibnode_t parent)
408     parent->child = node;
410     fibnode_insert_before (parent->child, node);
411   node->parent = parent;
413   node->mark = 0;
418 fibheap_cut (fibheap_t heap, fibnode_t node, fibnode_t parent)
420   fibnode_remove (node);
422   fibheap_ins_root (heap, node);
423   node->parent = NULL;
424   node->mark = 0;
467 fibnode_remove (fibnode_t node)
471   if (node == node->left)
474     ret = node->left;
476   if (node->parent != NULL && node->parent->child == node)
477     node->parent->child = ret;
479   node->right->left = node->left;
480   node->left->right = node->right;
482   node->parent = NULL;
483   node->left = node;
484   node->right = node;