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 #include <stdio.h>
   5
   6 void dgraph_init_node(struct dgraph_node *n)
   7 {
   8         tlist_init(&n->edge[DGRAPH_FROM]);
   9         tlist_init(&n->edge[DGRAPH_TO]);
  10 }
  11
  12 static void free_edge(struct dgraph_edge *e)
  13 {
  14         tlist_del_from(&e->n[DGRAPH_FROM]->edge[DGRAPH_FROM],
  15                        e, list[DGRAPH_FROM]);
  16         tlist_del_from(&e->n[DGRAPH_TO]->edge[DGRAPH_TO],
  17                        e, list[DGRAPH_TO]);
  18         free(e);
  19 }
  20
  21 void dgraph_clear_node(struct dgraph_node *n)
  22 {
  23         struct dgraph_edge *e;
  24         unsigned int i;
  25
  26         (void)dgraph_debug(n);
  27         for (i = DGRAPH_FROM; i <= DGRAPH_TO; i++) {
  28                 while ((e = tlist_top(&n->edge[i], list[i])) != NULL) {
  29                         assert(e->n[i] == n);
  30                         free_edge(e);
  31                 }
  32         }
  33 }
  34
  35 void dgraph_add_edge(struct dgraph_node *from, struct dgraph_node *to)
  36 {
  37         struct dgraph_edge *e = malloc(sizeof(*e));
  38
  39         (void)dgraph_debug(from);
  40         (void)dgraph_debug(to);
  41         e->n[DGRAPH_FROM] = from;
  42         e->n[DGRAPH_TO] = to;
  43         tlist_add(&from->edge[DGRAPH_FROM], e, list[DGRAPH_FROM]);
  44         tlist_add(&to->edge[DGRAPH_TO], e, list[DGRAPH_TO]);
  45 }
  46
  47 bool dgraph_del_edge(struct dgraph_node *from, struct dgraph_node *to)
  48 {
  49         struct dgraph_edge *e, *next;
  50
  51         (void)dgraph_debug(from);
  52         (void)dgraph_debug(to);
  53         dgraph_for_each_edge_safe(from, e, next, DGRAPH_FROM) {
  54                 if (e->n[DGRAPH_TO] == to) {
  55                         free_edge(e);
  56                         return true;
  57                 }
  58         }
  59         return false;
  60 }
  61
  62 static bool traverse_depth_first(struct dgraph_node *n,
  63                                  enum dgraph_dir dir,
  64                                  bool (*fn)(struct dgraph_node *, void *),
  65                                  const void *data)
  66 {
  67         struct dgraph_edge *e, *next;
  68
  69         /* dgraph_for_each_edge_safe, without dgraph_debug() */
  70         tlist_for_each_safe(&n->edge[dir], e, next, list[dir]) {
  71                 if (!traverse_depth_first(e->n[!dir], dir, fn, data))
  72                         return false;
  73         }
  74         return fn(n, (void *)data);
  75 }
  76
  77 void dgraph_traverse(const struct dgraph_node *n,
  78                      enum dgraph_dir dir,
  79                      bool (*fn)(struct dgraph_node *, void *),
  80                      const void *data)
  81 {
  82         struct dgraph_edge *e, *next;
  83
  84         /* dgraph_for_each_edge_safe, without dgraph_debug() */
  85         tlist_for_each_safe(&n->edge[dir], e, next, list[dir]) {
  86                 if (!traverse_depth_first(e->n[!dir], dir, fn, data))
  87                         break;
  88         }
  89 }
  90
  91 struct check_info {
  92         const struct dgraph_node *ret;
  93         const char *abortstr;
  94 };
  95
  96 static bool find_backedge(const struct dgraph_node *from,
  97                           const struct dgraph_node *to,
  98                           enum dgraph_dir dir)
  99 {
 100         struct dgraph_edge *e;
 101
 102         tlist_for_each(&from->edge[dir], e, list[dir]) {
 103                 if (e->n[!dir] == to)
 104                         return true;
 105         }
 106         return false;
 107 }
 108
 109 static bool dgraph_check_node(struct dgraph_node *n, void *info_)
 110 {
 111         struct check_info *info = info_;
 112         unsigned int dir;
 113         struct dgraph_edge *e;
 114
 115         for (dir = DGRAPH_FROM; dir <= DGRAPH_TO; dir++) {
 116                 /* First, check edges list. */
 117                 if (!tlist_check(&n->edge[dir], info->abortstr)) {
 118                         info->ret = NULL;
 119                         return false;
 120                 }
 121
 122                 /* dgraph_for_each_edge() without check! */
 123                 tlist_for_each(&n->edge[dir], e, list[dir]) {
 124                         if (e->n[dir] == n) {
 125                                 if (find_backedge(e->n[!dir], n, !dir))
 126                                         continue;
 127                                 if (info->abortstr) {
 128                                         fprintf(stderr,
 129                                                 "%s: node %p %s edge doesnt"
 130                                                 " point back to %p\n",
 131                                                 info->abortstr, e->n[!dir],
 132                                                 !dir == DGRAPH_FROM
 133                                                 ? "DGRAPH_FROM" : "DGRAPH_TO",
 134                                                 n);
 135                                         abort();
 136                                 }
 137                                 info->ret = NULL;
 138                                 return false;
 139                         }
 140
 141                         if (info->abortstr) {
 142                                 fprintf(stderr,
 143                                         "%s: node %p %s edge %p points"
 144                                         " to %p\n",
 145                                         info->abortstr, n,
 146                                         dir == DGRAPH_FROM
 147                                         ? "DGRAPH_FROM" : "DGRAPH_TO",
 148                                         e, e->n[dir]);
 149                                 abort();
 150                         }
 151                         info->ret = NULL;
 152                         return false;
 153                 }
 154         }
 155
 156         return true;
 157 }
 158
 159 struct dgraph_node *dgraph_check(const struct dgraph_node *n,
 160                                  const char *abortstr)
 161 {
 162         struct check_info info;
 163
 164         /* This gets set to NULL by dgraph_check_node on failure. */
 165         info.ret = n;
 166         info.abortstr = abortstr;
 167
 168         dgraph_check_node((struct dgraph_node *)info.ret, &info);
 169
 170         if (info.ret)
 171                 dgraph_traverse(n, DGRAPH_FROM, dgraph_check_node, &info);
 172         if (info.ret)
 173                 dgraph_traverse(n, DGRAPH_TO, dgraph_check_node, &info);
 174         return (void *)info.ret;
 175 }