fheap

Fibonacci heap implementation
git clone git://www.tkruger.se/fheap.git
Log | Files | Refs | README
commit 590cd75d85b342a63e26def1478701b31f38a5d5
Author: olikru <olikru@tkruger.se>
Date:   Mon,  8 Jan 2024 15:09:47 +0100

initial

Diffstat:

AMakefile | 40++++++++++++++++++++++++++++++++++++++++


AREADME | 5+++++


ATODO | 2++


Afheap.c | 249+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


Afheap.h | 40++++++++++++++++++++++++++++++++++++++++


Atest_fheap.c | 8++++++++


6 files changed, 344 insertions(+), 0 deletions(-)

diff --git a/Makefile b/Makefile
@@ -0,0 +1,40 @@
+.SUFFIXES: .c .o .so
+CC=clang
+CFLAGS+=-std=c99 -pedantic -Wall -Werror -Wstrict-prototypes
+CFLAGS+=-Wmissing-prototypes -Wmissing-declarations -Wshadow
+CFLAGS+=-Wpointer-arith -Wcast-qual -Wsign-compare
+CFLAGS+=-O2 -g
+CFLAGS+=-fstack-protector-all -Wtype-limits -fno-common
+CFLAGS+=-fno-builtin
+CFLAGS+=-I/usr/local/include
+
+INSTALL_PATH=$(HOME)/.local
+BUILD=build
+
+TEST_SOURCE=test_fheap.c
+HEADER=fheap.h
+OBJS=fheap.o
+SHARED=fheap.so
+LIBSHARED=libfheap.so
+
+all: build $(OBJS) $(SHARED) test
+
+.c.o:
+	$(CC) $(CFLAGS) -c $< -o $(BUILD)/$@
+
+.o.so:
+	$(CC) -shared -fPIC $(BUILD)/$< -o $(BUILD)/$@ $(LFLAGS)
+
+test: $(TEST_SOURCE)
+	$(CC) $(CFLAGS) -o $(BUILD)/test $(TEST_SOURCE) $(BUILD)/$(OBJS) $(LFLAGS)
+
+build:
+	mkdir -p $(BUILD)
+
+install:
+	cp $(BUILD)/$(SHARED) $(INSTALL_PATH)/lib/$(LIBSHARED)
+	chmod 644 $(INSTALL_PATH)/lib/$(LIBSHARED)
+	cp $(HEADER) $(INSTALL_PATH)/include/
+
+clean:
+	rm -rf $(BUILD)
diff --git a/README b/README
@@ -0,0 +1,5 @@
+fheap
+=====
+
+Fibonacci heap implementation (a type of priority queue) that uses
+uint64_t's as "keys"/"values". Based on the CLRS description.
diff --git a/TODO b/TODO
@@ -0,0 +1,2 @@
+* Implement unit tests
+* Documentation
diff --git a/fheap.c b/fheap.c
@@ -0,0 +1,249 @@
+#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) {
+  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);
+
+  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;
+}
diff --git a/fheap.h b/fheap.h
@@ -0,0 +1,40 @@
+#ifndef FHEAP_H
+#define FHEAP_H
+
+#include <assert.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+typedef struct fnode_struct {
+  uint64_t value;
+  void *data;
+
+  struct fnode_struct *parent;
+  struct fnode_struct *children;
+  size_t nchildren;
+  uint64_t marked;
+
+  struct fnode_struct *left;
+  struct fnode_struct *right;
+} fnode_t;
+
+typedef struct {
+  size_t n;
+  fnode_t *min;
+  fnode_t *head;
+} fheap_t;
+
+void fnode_init(fnode_t *node, const uint64_t value, void *data);
+void fnode_clear(fnode_t *node);
+
+void fheap_init(fheap_t *heap);
+void fheap_clear(fheap_t *heap);
+
+fnode_t *fheap_insert(fheap_t *heap, const uint64_t value, void *data);
+fnode_t *fheap_extract_min_node(fheap_t *heap);
+uint64_t fheap_extract_min(void **data, fheap_t *heap);
+
+void fheap_decrease_value(fheap_t *heap, fnode_t *node, const uint64_t value);
+
+#endif
diff --git a/test_fheap.c b/test_fheap.c
@@ -0,0 +1,8 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <assert.h>
+#include "fheap.h"
+
+int main() {
+  printf("test unimplemented\n");
+}