nsz Git - libfirm/blob - ir/be/grgen/uf_mpq.h

   1 #ifndef _EXT_GRS_UF_MPQ_H_
   2 #define _EXT_GRS_UF_MPQ_H_
   3
   4 /*
   5  * Project:     libFIRM/extension module/GRS-matcher
   6  * File name:   ext/grs/uf_mpq.h
   7  * Purpose:     provides a union find structure (uf) (disjoint sets)
   8  *              and a meldable priority queue implementation (mpq)
   9  *              for pattern edges (note: in case of the uf edges are
  10  *              represented by their edge ids. This is because a
  11  *              disjoint integer set implementation is used.)
  12  *                              @note The uf-concept used in this impl allows
  13  *                                    only elems greater than zero, but there are
  14  *                                    elems greater or EQUAL zero supported!
  15  * Author:      Veit Batz
  16  * Created:             7. June 2005
  17  * CVS-ID:      $Id$
  18  * Copyright:   (c) 2005 Universität Karlsruhe
  19  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  20  */
  21
  22 #include <stdlib.h>
  23
  24
  25 #include "array.h"
  26 #include "common_t.h"
  27 #include "action_t.h"
  28
  29
  30
  31
  32 #undef MAX
  33 #define MAX(a,b) ( (a)>=(b) ? (a) : (b) )
  34
  35
  36
  37 typedef double uf_value_t;
  38
  39 static int *uf_parent;
  40 static uf_value_t *uf_value;
  41 static uf_value_t *uf_update;
  42
  43 static int uf_current_size = 1000;
  44 static int uf_max_size = 0;
  45 static int uf_already_used = 0;
  46
  47 /** initialize the union find structure */
  48 void ext_grs_uf_init(int max_elem) {
  49
  50         int max_size = max_elem + 1;
  51
  52         if (uf_already_used == 0) {
  53                 uf_current_size = MAX(max_size, 1000);
  54                 uf_parent = NEW_ARR_F(int, uf_current_size);
  55                 uf_value = NEW_ARR_F(uf_value_t, uf_current_size);
  56                 uf_update = NEW_ARR_F(uf_value_t, uf_current_size);
  57                 uf_already_used = 1;
  58         }
  59
  60         if (max_size > uf_current_size) {
  61                 uf_current_size = max_size;
  62                 ARR_RESIZE(*uf_parent, uf_parent, uf_current_size);
  63                 ARR_RESIZE(*uf_value, uf_value, uf_current_size);
  64                 ARR_RESIZE(*uf_update, uf_update, uf_current_size);
  65         }
  66
  67         memset(uf_parent, 0, max_size * sizeof(*uf_parent));
  68         memset(uf_value, 0, max_size * sizeof(*uf_value));
  69         memset(uf_update, 0, max_size * sizeof(*uf_update));
  70
  71         uf_max_size = max_size;
  72 }
  73
  74 /** find the value of the given elem */
  75 uf_value_t ext_grs_uf_find_value(int elem) {
  76
  77         int old_parent = uf_parent[elem];
  78         int new_root;
  79         uf_value_t eff_parent_update = 0;
  80         uf_value_t new_update = 0;
  81
  82         /* check wether the given elem is in range */
  83         assert (elem < uf_max_size && "union find elem out of bounds");
  84
  85         /* if elem is a root... */
  86         if (old_parent <= 0) {
  87                 /* ...simply return the elems effective value */
  88                 return uf_value[elem] + uf_update[elem];
  89         }
  90
  91         /* if the old parent is a root... */
  92         if (uf_parent[old_parent] <= 0) {
  93                 /* ...simply return the elems effective value */
  94                 return uf_value[elem] + uf_update[elem] + uf_update[old_parent];
  95         }
  96
  97         /* otherwise get effective parental update recursively */
  98         eff_parent_update = ext_grs_uf_find_value(old_parent) - uf_value[old_parent];
  99
 100         /* do path compression: */
 101         /* let the old parents parent be the new parent, which must be the
 102          * current root (by returning from recursion this has been set up by
 103          * the recusrsive ascend to the root) */
 104         new_root = uf_parent[old_parent];
 105         uf_parent[elem] = new_root;
 106
 107         /* adapt the update vaule */
 108         new_update = uf_update[elem] + eff_parent_update - uf_update[new_root];
 109         uf_update[elem] = new_update;
 110
 111         /* return the effective value of the elem */
 112         return uf_value[elem] + new_update;
 113 }
 114
 115 /** find the root of the set <code>elem</code> belongs to */
 116 int ext_grs_uf_find(int elem) {
 117
 118         /* check wether the given elem is in range */
 119         assert (elem < uf_max_size && "union find elem out of bounds");
 120
 121         /* if elem is a root... */
 122         if (uf_parent[elem] <= 0) {
 123                 /* ...simply return the elems effective value */
 124                 return elem;
 125         }
 126
 127         /* otherwise call find_value() for the elem (which performs path
 128          * compression for the elem) */
 129         ext_grs_uf_find_value(elem);
 130
 131         /* after path compression the parrent of elem has to be a root */
 132         assert(uf_parent[uf_parent[elem]] <= 0 && "after path compression the parent should be a root");
 133         return uf_parent[elem];
 134 }
 135
 136 /** unite the sets given by the roots <code>root1</code> and <code>root2</code> */
 137 int ext_grs_uf_unite(int root1, int root2) {
 138
 139         /* check wether the given elements are roots */
 140         assert (uf_parent[root1] <= 0 && uf_parent[root2] <= 0 && "not a root element");
 141
 142         /* check wether the given elem is in range */
 143         assert (root1 < uf_max_size && root2 < uf_max_size &&
 144                 "union find elem out of bounds");
 145
 146         /* the less deeper set is connected to the more deeper set */
 147         if (uf_parent[root1] < uf_parent[root2]) {
 148                 uf_parent[root2] = root1;
 149                 uf_update[root2] -= uf_update[root1];
 150                 return root1;
 151         }
 152
 153         uf_parent[root1] = root2;
 154         uf_update[root1] -= uf_update[root2];
 155         if (uf_parent[root1] == uf_parent[root2])
 156                 uf_parent[root2]--;
 157         return root2;
 158 }
 159
 160
 161
 162
 163
 164
 165 /* Folgende Funktion FALSCH????? */
 166
 167
 168 /** add the given value <code>a</code> to the values of all
 169  *  elements of the set given by <code>root</code> */
 170 void ext_grs_uf_change_value(int root, uf_value_t a) {
 171
 172         /* check wether the given elem is in range */
 173         assert (root < uf_max_size && "union find elem out of bounds");
 174
 175         assert (uf_parent[root] <= 0 && "not a root element");
 176         uf_update[root] += a;
 177 }
 178
 179
 180
 181
 182
 183
 184
 185
 186
 187
 188 /* the meldable priority queue implementation */
 189
 190
 191
 192
 193 /**
 194  * iterate over a list starting with <code>pos</code> up to the lists end
 195  * */
 196 #define list_for_each_from(pos, head) \
 197         for ( ; pos != (head); pos = pos->next )
 198
 199 #define GET_ACTUAL_EDGE_COST(e) \
 200         ((e)->cost - ext_grs_uf_find_value((e)->arg->aiid + 1))
 201
 202
 203
 204 /** a priority queue of edges */
 205 typedef lc_list_t ext_grs_mpq_t;
 206
 207
 208
 209
 210
 211 static struct obstack obst;
 212 static int obst_already_initlzd = 0;
 213
 214
 215 /** initialize the meldable priority queue inplementation */
 216 void ext_grs_mpq_init(void)
 217 {
 218         if (! obst_already_initlzd) {
 219                 obstack_init(&obst);
 220         }
 221         else {
 222                 obstack_free(&obst, NULL);
 223                 obstack_init(&obst);
 224         }
 225         obst_already_initlzd = 1;
 226 }
 227
 228 /** create a new empty priority queue */
 229 ext_grs_mpq_t *ext_grs_mpq_create(void)
 230 {
 231         ext_grs_mpq_t *mpq = obstack_alloc(&obst, sizeof(*mpq));
 232
 233         assert(obst_already_initlzd = 1 && "mpq structure not initialized yet");
 234
 235
 236         LC_INIT_LIST_HEAD(mpq);
 237         return mpq;
 238 }
 239
 240 /** insert the given elem in the given priority queue */
 241 void ext_grs_mpq_insert(ext_grs_mpq_t *pq, ext_grs_edge_t *e)
 242 {
 243         lc_list_t *pos;
 244         ext_grs_edge_t *edge;
 245
 246         assert (pq != NULL && "NULL pointer is not a valid priority queue");
 247
 248         if (lc_list_empty(pq)) {
 249                 lc_list_add(& e->mpq_list, pq);
 250                 return;
 251         }
 252
 253         /* go through pq untill the appropriate position is reached */
 254         lc_list_for_each(pos, pq) {
 255                 edge = lc_list_entry(pos, ext_grs_edge_t, mpq_list);
 256                 if (GET_ACTUAL_EDGE_COST(e) <= GET_ACTUAL_EDGE_COST(edge)) {
 257                         lc_list_add_tail( & e->mpq_list, & edge->mpq_list );
 258                         return;
 259                 }
 260         }
 261
 262         lc_list_add( & e->mpq_list, & edge->mpq_list );
 263
 264 }
 265
 266 /** get the an item with a minimal prio or NULL if <code>pq</code> is empty */
 267 ext_grs_edge_t *ext_grs_mpq_find_min(ext_grs_mpq_t *pq)
 268 {
 269         assert (pq != NULL && "NULL pointer is not a valid priority queue");
 270
 271         /* return NULL if pq is empty */
 272         if (lc_list_empty(pq)) return NULL;
 273
 274         /* return first item otherwise */
 275         return lc_list_entry(pq->next, ext_grs_edge_t, mpq_list);
 276 }
 277
 278 /** Remove and return an item with a minimal prio, if <code>pq</code> is empty
 279  *  return NULL.
 280  *  @note       The member <code>list</code> of the returned item
 281  *                      is in an undefined state. */
 282 ext_grs_edge_t *ext_grs_mpq_delete_min(ext_grs_mpq_t *pq)
 283 {
 284         ext_grs_edge_t *first_edge;
 285
 286         assert (pq != NULL && "NULL pointer is not a vaild priority queue");
 287
 288         /* return NULL if pq is empty */
 289         if (lc_list_empty(pq)) return NULL;
 290
 291         /* otherwise remove and return the first item */
 292         first_edge = lc_list_entry(pq->next, ext_grs_edge_t, mpq_list);
 293         lc_list_del(& first_edge->mpq_list);
 294         return first_edge;
 295 }
 296
 297 void ext_grs_mpq_dump(ext_grs_mpq_t *pq);
 298
 299 /** Meld two item disjoint priority queues <code>pq1</code> and <code>pq2</code>.
 300  *  ATTENTION: The given priority queues will be <b>destroyed!</b> */
 301 ext_grs_mpq_t *ext_grs_mpq_meld(ext_grs_mpq_t *pq1, ext_grs_mpq_t *pq2)
 302 {
 303         lc_list_t *pos1, *pos2, *n;
 304         ext_grs_edge_t *e1, *e2;
 305         int last = 1; /* tells wether that pq1 has been iteratied till the end and never breaked */
 306
 307         assert (pq1 != NULL && pq2 != NULL && "NULL pointer is not a vaild priority queue");
 308         assert (pq1 != pq2 && "cannot meld an pq with itself");
 309
 310 #ifdef EXT_GRS_DEBUG
 311         printf("pq1:\n");
 312         ext_grs_mpq_dump(pq1);
 313         printf("pq2:\n");
 314         ext_grs_mpq_dump(pq2);
 315 #endif
 316
 317
 318         /* if pq1 is empty return pq2 */
 319         if (lc_list_empty(pq1)) return pq2;
 320
 321         /* insert the items of pq2 into pq1 (at appropriate positions) */
 322         pos1 = pq1->next; /* start walking pq1 from beginning */
 323         lc_list_for_each_safe (pos2, n, pq2) {
 324                 e2 = lc_list_entry(pos2, ext_grs_edge_t, mpq_list);
 325                 list_for_each_from (pos1, pq1) {
 326                         e1 = lc_list_entry(pos1, ext_grs_edge_t, mpq_list);
 327                         if (GET_ACTUAL_EDGE_COST(e2) <= GET_ACTUAL_EDGE_COST(e1)) {
 328                                 last = 0;
 329                                 break;
 330                         }
 331                 }
 332
 333                 if (last) {
 334                         /* pq1 has been iterated till the end */
 335                         /* insert item2 before the curent position in pq1 */
 336                         lc_list_move(& e2->mpq_list, & e1->mpq_list);
 337                         e1 = e2;
 338                 }
 339                 else {
 340                         /* insert item2 before the curent position in pq1 */
 341                         lc_list_move_tail(& e2->mpq_list, & e1->mpq_list);
 342                         /* continue in pq1 with the current item */
 343                         pos1 = & e1->mpq_list;
 344                         /* maybe next time the end of pq1 is reached */
 345                         last = 1;
 346                 }
 347         }
 348
 349 #ifdef EXT_GRS_DEBUG
 350         printf("Result queue:\n");
 351         ext_grs_mpq_dump(pq1);
 352         printf("\n");
 353 #endif
 354
 355         return pq1;
 356 }
 357
 358
 359 /** Remove the given item from the given priority queue.
 360  *  @note The list of the deleted item is in an undifind state afterwards. */
 361 void ext_grs_mpq_delete(ext_grs_edge_t *e)
 362 {
 363         /* remove the item from its priority queue */
 364         lc_list_del(& e->mpq_list);
 365 }
 366
 367
 368 void ext_grs_mpq_dump(ext_grs_mpq_t *pq) {
 369         lc_list_t *pos;
 370
 371         printf("{\n");
 372         lc_list_for_each(pos, pq) {
 373                 ext_grs_edge_t *edge = lc_list_entry(pos, ext_grs_edge_t, mpq_list);
 374                 printf("\t(name, cost, actual cost) =  (%s, %lf, %lf)\n",
 375                         edge->name, edge->cost, GET_ACTUAL_EDGE_COST(edge));
 376         }
 377         printf("}\n");
 378 }
 379
 380
 381
 382 #endif /*_UF_MPQ_H_*/