flower/directed-graph.cc

   1 /*
   2   edge_out.cc -- implement Directed_graph_node
   3
   4   source file FlowerLib
   5
   6   (c) 1997 Han-Wen Nienhuys <hanwen@stack.nl>
   7 */
   8
   9 #include "directed-graph.hh"
  10
  11 #ifdef PARANOID                 // these checks eat huge amounts of time.
  12 #define PARANOID_OK() OK()
  13 #else
  14 #define PARANOID_OK()
  15 #endif
  16
  17
  18 Link_array<Directed_graph_node> const &
  19 Directed_graph_node::get_in_edge_arr() const
  20 {
  21     return edge_in_l_arr_;
  22 }
  23
  24 Link_array<Directed_graph_node> const &
  25 Directed_graph_node::get_out_edge_arr()const
  26 {
  27     return edge_out_l_arr_;
  28 }
  29
  30 /**
  31   Should not copy deps automatically
  32  */
  33 Directed_graph_node::Directed_graph_node(Directed_graph_node const&)
  34 {
  35 }
  36
  37 void
  38 Directed_graph_node::copy_edges_out(Directed_graph_node const &s)
  39 {
  40     for(int i=0; i < s.edge_out_l_arr_.size(); i++)
  41         add(s.edge_out_l_arr_[i]);
  42 }
  43
  44 void
  45 Directed_graph_node::OK() const
  46 {
  47 #ifndef NDEBUG
  48     for (int i=0; i < edge_out_l_arr_.size(); i++) {
  49         assert(edge_out_l_arr_[i]->
  50                edge_in_l_arr_.find_l(this));
  51     }
  52     for (int i=0; i < edge_in_l_arr_.size(); i++)
  53         assert(edge_in_l_arr_[i]->contains_b( this));
  54 #endif
  55 }
  56
  57 bool
  58 Directed_graph_node::contains_b(const Directed_graph_node *d)const
  59 {
  60     return edge_out_l_arr_.find_l((Directed_graph_node*)d);
  61 }
  62
  63 void
  64 Directed_graph_node::remove_edge_out_idx(int i)
  65 {
  66     PARANOID_OK();
  67     Directed_graph_node * d_l = edge_out_l_arr_.get(i);
  68
  69     int j = d_l->edge_in_l_arr_.find_i(this);
  70     assert(j>=0);
  71     d_l->edge_in_l_arr_.del(j);
  72     PARANOID_OK();
  73 }
  74
  75 void
  76 Directed_graph_node::remove_edge_in(Directed_graph_node *d_l)
  77 {
  78     PARANOID_OK();
  79     d_l->remove_edge_out(this);
  80     PARANOID_OK();
  81 }
  82
  83 void
  84 Directed_graph_node::remove_edge_out (Directed_graph_node *d_l)
  85 {
  86     PARANOID_OK();
  87     for (int i=0; i < edge_out_l_arr_.size(); ) {
  88         if (edge_out_l_arr_[i]== d_l)
  89             remove_edge_out_idx(i);
  90         else
  91             i++;
  92     }
  93     PARANOID_OK();
  94 }
  95 bool
  96 Directed_graph_node::linked_b()const
  97 {
  98     return edge_out_l_arr_.size() || edge_in_l_arr_.size();
  99 }
 100
 101 void
 102 Directed_graph_node::junk_links()
 103 {
 104     edge_in_l_arr_.set_size(0);
 105     edge_out_l_arr_.set_size(0);
 106 }
 107
 108
 109 void
 110 Directed_graph_node::unlink()
 111 {
 112 #ifdef PARANOID
 113         PARANOID_OK();
 114
 115         Link_array<Directed_graph_node> t = edge_out_l_arr_;
 116         t.concat(edge_in_l_arr_);
 117 #endif
 118
 119         while ( edge_out_l_arr_.size() )
 120             remove_edge_out_idx(0);
 121
 122         while (edge_in_l_arr_.size() )
 123             remove_edge_in(edge_in_l_arr_[0]);
 124
 125 #ifdef PARANOID
 126         for (int i =0; i < t.size(); i++)
 127             t[i]->OK();
 128 #endif
 129 }
 130
 131 Directed_graph_node::~Directed_graph_node()
 132 {
 133     assert(!linked_b());
 134 }
 135
 136
 137 void
 138 Directed_graph_node::add(Directed_graph_node* dep_l)
 139 {
 140     PARANOID_OK();
 141     if (!dep_l)
 142         return ;
 143     dep_l->edge_in_l_arr_.push(this);
 144     edge_out_l_arr_.push(dep_l);
 145     PARANOID_OK();
 146 }
 147
 148
 149 Directed_graph_node::Directed_graph_node()
 150 {
 151 }
 152