git.gag.com Git - fw/sdcc/blob - src/pic16/graph.c

   1 /*-------------------------------------------------------------------------
   2
   3   graph.c - implementation of general graphs
   4
   5    Written By -  Raphael Neider <rneider AT web.de> (2005)
   6
   7    This program is free software; you can redistribute it and/or modify it
   8    under the terms of the GNU General Public License as published by the
   9    Free Software Foundation; either version 2, or (at your option) any
  10    later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program; if not, write to the Free Software
  19    Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  20 -------------------------------------------------------------------------*/
  21
  22 /* $Id$ */
  23
  24 #include "graph.h"
  25
  26 /* === helpers ====================================================== */
  27
  28 int default_compare (void *data1, void *data2)
  29 {
  30   return (data1 == data2);
  31 }
  32
  33 /* === GraphEdge ==================================================== */
  34
  35 GraphEdge *newGEdge (GraphNode *src, GraphNode *dest, unsigned int weight) {
  36   GraphEdge *edge = (GraphEdge *)Safe_calloc (1, sizeof (GraphEdge));
  37   edge->src = src;
  38   edge->node = dest;
  39   edge->weight = weight;
  40   return edge;
  41 }
  42
  43 GraphEdge *deleteGEdge (GraphEdge *edge) {
  44   GraphEdge *head;
  45   // remove edge from list
  46   if (edge->next) edge->next->prev = edge->prev;
  47   if (edge->prev) edge->prev->next = edge->next;
  48
  49   if (edge->prev) head = edge->prev; else head = edge->next;
  50   Safe_free (edge);
  51   return head;
  52 }
  53
  54 /* === GraphNode ==================================================== */
  55
  56 GraphNode *newGNode (void *data, hash_t hash) {
  57   GraphNode *node = (GraphNode*)Safe_calloc (1, sizeof (GraphNode));
  58   node->data = data;
  59   node->hash = hash;
  60   return node;
  61 }
  62
  63 GraphNode * deleteGNode (GraphNode *node) {
  64   GraphNode *head;
  65
  66   if (!node) return NULL;
  67
  68   // delete all edges
  69   while (node->edge) {
  70     node->edge = deleteGEdge (node->edge);
  71   } // while
  72
  73   // remove node from list
  74   if (node->next) node->next->prev = node->prev;
  75   if (node->prev) node->prev->next = node->next;
  76
  77   if (node->prev) head = node->prev; else head = node->next;
  78   Safe_free (node);
  79   return head;
  80 }
  81
  82 GraphEdge *addGEdge (GraphNode *from, GraphNode *to, unsigned int weight) {
  83   GraphEdge *edge = getGEdge (from, to);
  84   if (edge == NULL) {
  85     edge = newGEdge (from, to, weight);
  86     // insert edge into list
  87     if (from->edge) from->edge->prev = edge;
  88     edge->next = from->edge;
  89     from->edge = edge;
  90   } else
  91     edge->weight += weight;
  92
  93   assert (edge->src == from && edge->node == to);
  94   return edge;
  95 }
  96
  97 void addGEdge2 (GraphNode *from, GraphNode *to, unsigned int weight, unsigned int weight_back) {
  98   addGEdge (from, to, weight);
  99   addGEdge (to, from, weight_back);
 100 }
 101
 102 void remGEdge (GraphNode *from, GraphNode *to) {
 103   GraphEdge *curr = from->edge;
 104   while (curr && curr->node != to) curr = curr->next;
 105
 106   if (!curr) return;
 107
 108   if (from->edge == curr)
 109     from->edge = deleteGEdge (curr);
 110   else
 111     deleteGEdge (curr);
 112 }
 113
 114 GraphEdge *getGEdge (GraphNode *from, GraphNode *to) {
 115   GraphEdge *curr = from->edge;
 116   while (curr && curr->node != to) {
 117     assert (curr->src == from);
 118     curr = curr->next;
 119   }
 120   return curr;
 121 }
 122
 123 /* === Graph ======================================================== */
 124
 125 Graph *newGraph (Graph_compareData *compare) {
 126   Graph *graph = (Graph*) Safe_calloc (1, sizeof (Graph));
 127   graph->compare = compare;
 128   if (!compare) graph->compare = default_compare;
 129
 130   return graph;
 131 }
 132
 133 void deleteGraph (Graph *graph) {
 134   // remove all nodes
 135   while (graph->node) {
 136     graph->node = deleteGNode (graph->node);
 137   } // while
 138
 139   Safe_free (graph);
 140 }
 141
 142 GraphNode *addGNode (Graph *graph, void *data, hash_t hash) {
 143   GraphNode *node = newGNode (data, hash);
 144   if (graph->node) graph->node->prev = node;
 145   node->next = graph->node;
 146   graph->node = node;
 147   return node;
 148 }
 149
 150 void remGNode (Graph *graph, void *data, hash_t hash) {
 151   GraphNode *curr = graph->node;
 152   while (curr && ((curr->hash != hash) || (!graph->compare(curr->data, data)))) {
 153     curr = curr->next;
 154   } // while
 155
 156   if (!curr) return;
 157
 158   if (graph->node == curr)
 159     graph->node = deleteGNode (curr);
 160   else
 161     deleteGNode (curr);
 162 }
 163
 164 GraphNode *getGNode (Graph *graph, void *data, hash_t hash) {
 165   GraphNode *curr = graph->node;
 166   while (curr && ((curr->hash != hash) || (!graph->compare(curr->data, data)))) {
 167     curr = curr->next;
 168   } // while
 169
 170   return curr;
 171 }
 172
 173 GraphNode *getOrAddGNode (Graph *graph, void *data, hash_t hash) {
 174   GraphNode *curr = getGNode (graph, data, hash);
 175   if (!curr)
 176     curr = addGNode (graph, data, hash);
 177
 178   assert (curr != NULL);
 179   return curr;
 180 }