fheap

fheap.c (5123B)

---

 #include "fheap.h"
 
 void fnode_init(fnode_t *node, const uint64_t value, void *data) {
   node->children = NULL;
   node->parent = NULL;
   node->left = node;
   node->right = node;
   node->nchildren = 0;
   node->marked = 0;
 
   node->value = value;
   node->data = data;
 }
 
 void fnode_clear(fnode_t *node) {
   // clear children recursively
   fnode_t *c, *d;
   size_t n = node->nchildren;
   c = node->children;
   size_t i;
   for (i = 0; i < n; i++) {
     d = c->right;
     fnode_clear(c);
     c = d;
   }
 
   free(node);
 }
 
 void fheap_init(fheap_t *heap) {
   heap->min = NULL;
   heap->head = NULL;
   heap->n = 0;
 }
 
 void fheap_clear(fheap_t *heap) {
   fnode_t *c = heap->head;
   fnode_t *d = c->right;
 
   while (d != c) {
     fnode_t *t = d->right;
     fnode_clear(d);
     d = t;
   }
   fnode_clear(c);
 
   heap->min = NULL;
   heap->head = NULL;
   heap->n = 0;
 }
 
 static inline void insert_leftof(fnode_t *x, fnode_t *y) {
   fnode_t *x_left = x->left;
   x->left = y;
   y->parent = x->parent;
   y->right = x;
   y->left = x_left;
   x_left->right = y;
 }
 
 fnode_t *fheap_insert(fheap_t *heap, const uint64_t value, void *data) {
   assert(value != UINT64_MAX || data != NULL);
 
   fnode_t *nnode = malloc(sizeof(*nnode));
 
   fnode_init(nnode, value, data);
 
   if (heap->min == NULL) {
     heap->head = nnode;
     heap->min = nnode;
   } else {
     insert_leftof(heap->head, nnode);
     if (nnode->value < (heap->min)->value) {
       heap->min = nnode;
     }
   }
 
   heap->n++;
 
   return nnode;
 }
 
 static inline void remove_node(fnode_t *x) {
   (x->left)->right = x->right;
   (x->right)->left = x->left;
 }
 
 static inline void fheap_link(fheap_t *heap, fnode_t *y, fnode_t *x) {
   remove_node(y);
   if (heap->head == y)
     heap->head = y->right;
   if (x->children != NULL) {
     insert_leftof(x->children, y);
   } else {
     x->children = y;
     y->parent = x;
     y->left = y;
     y->right = y;
     x->nchildren = 0;
   }
   x->nchildren++;
   y->marked = 0;
 }
 
 static inline void consolidate(fheap_t *heap) {
   size_t i, deg;
   fnode_t *a[heap->n];
 
   for (i = 0; i < heap->n; i++)
     a[i] = NULL;
 
   fnode_t *c = heap->head;
   fnode_t *head_list[heap->n];
   size_t nheads = 0;
   do {
     head_list[nheads] = c;
     nheads++;
     c = c->right;
   } while (c != heap->head);
 
   size_t max_deg = 0;
 
   fnode_t *x, *y;
   for (i = 0; i < nheads; i++) {
     c = head_list[i];
 
     deg = c->nchildren;
     x = c;
     while (a[deg] != NULL) {
       if (x->value > a[deg]->value) {
         y = x;
         x = a[deg];
       } else {
         y = a[deg];
       }
 
       fheap_link(heap, y, x);
 
       a[deg] = NULL;
       deg++;
     }
 
     a[deg] = x;
 
     if (deg > max_deg)
       max_deg = deg;
   }
 
   heap->head = NULL;
   heap->min = NULL;
   for (i = 0; i < max_deg + 1; i++) {
     if (a[i] != NULL) {
       if (heap->head == NULL) {
         heap->head = a[i];
         heap->min = a[i];
         a[i]->left = a[i];
         a[i]->right = a[i];
       } else {
         insert_leftof(heap->head, a[i]);
         if (a[i]->value < (heap->min)->value)
           heap->min = a[i];
       }
     }
   }
 }
 
 fnode_t *fheap_extract_min_node(fheap_t *heap) {
   fnode_t *z = heap->min;
   fnode_t *c, *d;
   if (z != NULL) {
     if (z->nchildren > 0) {
       c = z->children;
       do {
         d = c->right;
         c->parent = NULL;
         insert_leftof(heap->head, c);
         c = d;
       } while (c != z->children);
       z->children = NULL;
     }
 
     remove_node(z);
 
     if (z == z->right) {
       heap->min = NULL;
       heap->head = NULL;
     } else {
       heap->min = z->right;
       if (heap->head == z)
         heap->head = z->right;
       consolidate(heap);
     }
 
     heap->n--;
   }
 
   return z;
 }
 
 uint64_t fheap_extract_min(void **data, fheap_t *heap) {
   fnode_t *z = fheap_extract_min_node(heap);
 
   if (z == NULL) {
     *data = NULL;
     return UINT64_MAX;
   }
 
   uint64_t value = z->value;
   *data = z->data;
 
   z->nchildren = 0;
   z->children = NULL;
   fnode_clear(z);
 
   return value;
 }
 
 static inline void fheap_cut(fheap_t *heap, fnode_t *x, fnode_t *y) {
   remove_node(x);
   if (y->children == x) {
     if (x->right == x) {
       y->children = NULL;
     } else {
       y->children = x->right;
     }
   }
   y->nchildren--;
 
   insert_leftof(heap->head, x);
   x->parent = NULL;
   x->marked = 0;
 }
 
 static void fheap_cascading_cut(fheap_t *heap, fnode_t *y) {
   fnode_t *z = y->parent;
   if (z != NULL) {
     if (y->marked == 0) {
       y->marked = 1;
     } else {
       fheap_cut(heap, y, z);
       fheap_cascading_cut(heap, z);
     }
   }
 }
 
 void fheap_decrease_value(fheap_t *heap, fnode_t *node, const uint64_t value) {
   node->value = value;
   fnode_t *y = node->parent;
   if (y != NULL && node->value < y->value) {
     fheap_cut(heap, node, y);
     fheap_cascading_cut(heap, y);
   }
 
   if (node->value < (heap->min)->value)
     heap->min = node;
 }
 
 void fheap_delete(fheap_t *heap, fnode_t *node) {
   node->value = 0; // at least tied minimum
 
   fnode_t *y = node->parent;
   if (y != NULL) {
     fheap_cut(heap, node, y);
     fheap_cascading_cut(heap, y);
   }
 
   heap->min = node;
   void* _throwaway;
   fheap_extract_min(&_throwaway, heap);
 }