git.ozlabs.org Git - ccan/blob - ccan/dgraph/dgraph.c

   1 /* Licensed under LGPLv2.1+ - see LICENSE file for details */
   2 #include <ccan/dgraph/dgraph.h>
   3 #include <stdlib.h>
   4
   5 void dgraph_init_node(struct dgraph_node *n)
   6 {
   7         tlist_init(&n->edge[DGRAPH_FROM]);
   8         tlist_init(&n->edge[DGRAPH_TO]);
   9 }
  10
  11 static void free_edge(struct dgraph_edge *e)
  12 {
  13         tlist_del_from(&e->n[DGRAPH_FROM]->edge[DGRAPH_FROM],
  14                        e, list[DGRAPH_FROM]);
  15         tlist_del_from(&e->n[DGRAPH_TO]->edge[DGRAPH_TO],
  16                        e, list[DGRAPH_TO]);
  17         free(e);
  18 }
  19
  20 void dgraph_clear_node(struct dgraph_node *n)
  21 {
  22         struct dgraph_edge *e;
  23         unsigned int i;
  24
  25         for (i = DGRAPH_FROM; i <= DGRAPH_TO; i++) {
  26                 while ((e = tlist_top(&n->edge[i], list[i])) != NULL) {
  27                         assert(e->n[i] == n);
  28                         free_edge(e);
  29                 }
  30         }
  31 }
  32
  33 void dgraph_add_edge(struct dgraph_node *from, struct dgraph_node *to)
  34 {
  35         struct dgraph_edge *e = malloc(sizeof(*e));
  36         e->n[DGRAPH_FROM] = from;
  37         e->n[DGRAPH_TO] = to;
  38         tlist_add(&from->edge[DGRAPH_FROM], e, list[DGRAPH_FROM]);
  39         tlist_add(&to->edge[DGRAPH_TO], e, list[DGRAPH_TO]);
  40 }
  41
  42 bool dgraph_del_edge(struct dgraph_node *from, struct dgraph_node *to)
  43 {
  44         struct dgraph_edge *e, *next;
  45
  46         dgraph_for_each_edge_safe(from, e, next, DGRAPH_FROM) {
  47                 if (e->n[DGRAPH_TO] == to) {
  48                         free_edge(e);
  49                         return true;
  50                 }
  51         }
  52         return false;
  53 }
  54
  55 static bool traverse_depth_first(struct dgraph_node *n,
  56                                  enum dgraph_dir dir,
  57                                  bool (*fn)(struct dgraph_node *, void *),
  58                                  const void *data)
  59 {
  60         struct dgraph_edge *e, *next;
  61
  62         dgraph_for_each_edge_safe(n, e, next, dir) {
  63                 if (!traverse_depth_first(e->n[!dir], dir, fn, data))
  64                         return false;
  65         }
  66         return fn(n, (void *)data);
  67 }
  68
  69 void dgraph_traverse(struct dgraph_node *n,
  70                      enum dgraph_dir dir,
  71                      bool (*fn)(struct dgraph_node *, void *),
  72                      const void *data)
  73 {
  74         struct dgraph_edge *e, *next;
  75
  76         dgraph_for_each_edge_safe(n, e, next, dir) {
  77                 if (!traverse_depth_first(e->n[!dir], dir, fn, data))
  78                         break;
  79         }
  80 }