Back to index

cell-binutils  2.17cvs20070401
Classes | Typedefs | Functions
fibheap.h File Reference
#include "ansidecl.h"
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  fibheap
struct  fibnode

Typedefs

typedef long fibheapkey_t
typedef struct fibheapfibheap_t
typedef struct fibnodefibnode_t

Functions

fibheap_t fibheap_new (void)
fibnode_t fibheap_insert (fibheap_t, fibheapkey_t, void *)
int fibheap_empty (fibheap_t)
fibheapkey_t fibheap_min_key (fibheap_t)
fibheapkey_t fibheap_replace_key (fibheap_t, fibnode_t, fibheapkey_t)
void * fibheap_replace_key_data (fibheap_t, fibnode_t, fibheapkey_t, void *)
void * fibheap_extract_min (fibheap_t)
void * fibheap_min (fibheap_t)
void * fibheap_replace_data (fibheap_t, fibnode_t, void *)
void * fibheap_delete_node (fibheap_t, fibnode_t)
void fibheap_delete (fibheap_t)
fibheap_t fibheap_union (fibheap_t, fibheap_t)

Class Documentation

struct fibheap

Definition at line 47 of file fibheap.h.

Collaboration diagram for fibheap:
Class Members
struct fibnode * min
size_t nodes
struct fibnode * root
struct fibnode

Definition at line 54 of file fibheap.h.

Collaboration diagram for fibnode:
Class Members
struct fibnode * child
void * data
unsigned int degree: 31
fibheapkey_t key
struct fibnode * left
unsigned int mark: 1
struct fibnode * parent
struct fibnode * right

Typedef Documentation

typedef long fibheapkey_t

Definition at line 45 of file fibheap.h.


Function Documentation

Definition at line 266 of file fibheap.c.

{
  while (heap->min != NULL)
    free (fibheap_extr_min_node (heap));

  free (heap);
}

Here is the call graph for this function:

Definition at line 253 of file fibheap.c.

{
  void *ret = node->data;

  /* To perform delete, we just make it the min key, and extract.  */
  fibheap_replace_key (heap, node, FIBHEAPKEY_MIN);
  fibheap_extract_min (heap);

  return ret;
}

Here is the call graph for this function:

Definition at line 276 of file fibheap.c.

{
  return heap->nodes == 0;
}

Definition at line 178 of file fibheap.c.

{
  fibnode_t z;
  void *ret = NULL;

  /* If we don't have a min set, it means we have no nodes.  */
  if (heap->min != NULL)
    {
      /* Otherwise, extract the min node, free the node, and return the
         node's data.  */
      z = fibheap_extr_min_node (heap);
      ret = z->data;
      free (z);
    }

  return ret;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 98 of file fibheap.c.

{
  fibnode_t node;

  /* Create the new node.  */
  node = fibnode_new ();

  /* Set the node's data.  */
  node->data = data;
  node->key = key;

  /* Insert it into the root list.  */
  fibheap_ins_root (heap, node);

  /* If their was no minimum, or this key is less than the min,
     it's the new min.  */
  if (heap->min == NULL || node->key < heap->min->key)
    heap->min = node;

  heap->nodes++;

  return node;
}

Here is the call graph for this function:

void* fibheap_min ( fibheap_t  )

Definition at line 124 of file fibheap.c.

{
  /* If there is no min, we can't easily return it.  */
  if (heap->min == NULL)
    return NULL;
  return heap->min->data;
}

Definition at line 134 of file fibheap.c.

{
  /* If there is no min, we can't easily return it.  */
  if (heap->min == NULL)
    return 0;
  return heap->min->key;
}
fibheap_t fibheap_new ( void  )

Definition at line 57 of file fibheap.c.

{
  return (fibheap_t) xcalloc (1, sizeof (struct fibheap));
}

Here is the call graph for this function:

void* fibheap_replace_data ( fibheap_t  ,
fibnode_t  ,
void *   
)

Definition at line 237 of file fibheap.c.

{
  return fibheap_replace_key_data (heap, node, node->key, data);
}

Here is the call graph for this function:

Definition at line 244 of file fibheap.c.

{
  int okey = node->key;
  fibheap_replace_key_data (heap, node, key, node->data);
  return okey;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* fibheap_replace_key_data ( fibheap_t  ,
fibnode_t  ,
fibheapkey_t  ,
void *   
)

Definition at line 198 of file fibheap.c.

{
  void *odata;
  fibheapkey_t okey;
  fibnode_t y;

  /* If we wanted to, we could actually do a real increase by redeleting and
     inserting. However, this would require O (log n) time. So just bail out
     for now.  */
  if (fibheap_comp_data (heap, key, data, node) > 0)
    return NULL;

  odata = node->data;
  okey = node->key;
  node->data = data;
  node->key = key;
  y = node->parent;

  if (okey == key)
    return odata;

  /* These two compares are specifically <= 0 to make sure that in the case
     of equality, a node we replaced the data on, becomes the new min.  This
     is needed so that delete's call to extractmin gets the right node.  */
  if (y != NULL && fibheap_compare (heap, node, y) <= 0)
    {
      fibheap_cut (heap, node, y);
      fibheap_cascading_cut (heap, y);
    }

  if (fibheap_compare (heap, node, heap->min) <= 0)
    heap->min = node;

  return odata;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 144 of file fibheap.c.

{
  fibnode_t a_root, b_root, temp;

  /* If one of the heaps is empty, the union is just the other heap.  */
  if ((a_root = heapa->root) == NULL)
    {
      free (heapa);
      return heapb;
    }
  if ((b_root = heapb->root) == NULL)
    {
      free (heapb);
      return heapa;
    }

  /* Merge them to the next nodes on the opposite chain.  */
  a_root->left->right = b_root;
  b_root->left->right = a_root;
  temp = a_root->left;
  a_root->left = b_root->left;
  b_root->left = temp;
  heapa->nodes += heapb->nodes;

  /* And set the new minimum, if it's changed.  */
  if (fibheap_compare (heapa, heapb->min, heapa->min) < 0)
    heapa->min = heapb->min;

  free (heapb);
  return heapa;
}

Here is the call graph for this function: