graph.c

#include <stdlib.h>
#include <stddef.h>

component *component_new(uint32_t magic, component *next) {
  component *this = malloc(sizeof(component));
  this->magic = magic; this->next = next;
  return this;
}

component *component_get(component *list, uint32_t magic) {
  for (component *cur = list; cur != 0; cur = cur->next)
    if (cur->magic == magic) return cur;
  return 0;
}

void component_add(component *list, component *new) {
  component *cur = list;
  for (; cur->next != 0; cur = cur->next);
  cur->next = new;
}

component *component_del(component *list, uint32_t magic) {
  for (component *cur = list, *old = 0; cur != 0; cur = cur->next) {
    if (cur->magic == 0) { if (old != 0) old->next = cur->next; return cur; }
    old = cur;
  }
  return 0;
}

node *root_new(component *data) {
  node *this = (node *) malloc(sizeof(node));
  this->parent = this->child = this->prev = this->next = 0;
  this->data = data;
  
  return this;
}

node *child_new(node *prnt, component *data) {
  node *this = (node *) malloc(sizeof(node));
  this->parent = prnt;
  this->child = this->prev = this->next = 0;
  
  for (node *cur = prnt->child; cur != 0; cur = cur->next) this->prev = cur;
  if (this->prev != 0) this->prev->next = this;
  if (prnt->child == 0) prnt->child = this;
  
  return this;
}

node *sibling_new(node *prev, component *data) {
  node *this = (node *) malloc(sizeof(node));
  this->parent = prev->parent;
  this->prev = prev; this->next = 0; prev->next = this;
  
  return this;
}

void node_free(node *this) {
  free(this);
}

void node_free_recurse(node *root) {
  for (node *cur = root->child; cur != 0; node_free((cur = cur->next)->prev))
    node_free_recurse(cur);
  
  node_free(root);
}

void node_traverse(node *tree, cb_traverse cb) {
  for (node *cur = tree->child; cur != 0; cur = cur->next)
    if (cb(cur)) node_traverse(cur, cb);
}

void node_add_child(node *this, node *child) {
  if (this->child == 0) this->child = child;
  else node_get_child(this, node_num_children(this)-1)->next = child;
}

void node_add_sibling(node *this, node *sibling) {
  if (this->next == 0) this->next = sibling;
  else node_get_sibling(this, node_num_siblings(this)-1)->next = sibling;
}

node *node_get_child(node *this, int index) {
  node *ret = this->child;
  for (int i = 0; i < index && ret != 0; i++) ret = ret->next;
  return ret;
}

node *node_get_sibling(node *this, int index) {
  int field_offset = (index < 0) ? offsetof(node, prev) : offsetof(node, next);
  int abs_index = (index < 0) ? -(index-1) : index; // -1 = 0 <==, 0 = 0 ==>, etc/
  node *ret = (node *) ((size_t) this + field_offset);
  for (int i = 0; i <= abs_index && ret != 0; i++) ret = (node *) ((size_t) ret + field_offset);
  return ret;
}

node *node_del_sibling(node *this, int index) {
  node *sib = node_get_sibling(this, index);
  if (sib == 0) return 0;
  
  sib->prev->next = sib->next;
  sib->next->prev = sib->prev;

  return sib;
}

node *node_del_child(node *this, int index) {
  node *cld = node_get_child(this, index);
  if (cld == 0) return 0;
  
  cld->prev->next = cld->next;
  cld->next->prev = cld->prev;

  return cld;
}

int node_num_children(node *this) {
  int ret = 0;
  for (node *c = this->child; c != 0; c = c->next) ret++;
  return ret;
}

int node_num_siblings(node *this) {
  int before = 0, after = 0;
  for (node *c = this->prev; c != 0; c = c->prev) before++;
  for (node *c = this->next; c != 0; c = c->next) after ++;
  return before + after;
}

graph.h

#pragma once

#include <stdint.h>
#include <stdbool.h>

#ifdef __cplusplus
extern "C" {
#endif

typedef struct component {
  uint32_t magic;
  struct component *next;
} component;

component *component_new(uint32_t magic, component *next);
component *component_get(component *list, uint32_t magic);
void       component_add(component *list, component *new);
component *component_del(component *list, uint32_t magic);

typedef struct node {
  struct node *parent, *child, *next, *prev;
  component *data;
} node;

node *root_new   (component *data);
node *child_new  (node *prnt, component *data);
node *sibling_new(node *prev, component *data);

void node_free(node *this);
void node_free_recurse(node *root);

typedef bool (*cb_traverse)(node *);
void node_traverse(node *tree, cb_traverse cb);

void  node_add_sibling (node *this, node *sibling);
void  node_add_child   (node *this, node *child);
node *node_get_child   (node *this, int   index);
node *node_get_sibling (node *this, int   index);
node *node_del_sibling (node *this, int   index);
node *node_del_child   (node *this, int   index);
int   node_num_children(node *this);
int   node_num_siblings(node *this);

#ifdef __cplusplus
}
#endif