libFirm
unionfind.h
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
3  *
4  * This file is part of libFirm.
5  *
6  * This file may be distributed and/or modified under the terms of the
7  * GNU General Public License version 2 as published by the Free Software
8  * Foundation and appearing in the file LICENSE.GPL included in the
9  * packaging of this file.
10  *
11  * Licensees holding valid libFirm Professional Edition licenses may use
12  * this file in accordance with the libFirm Commercial License.
13  * Agreement provided with the Software.
14  *
15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17  * PURPOSE.
18  */
19 
25 #ifndef FIRM_ADT_UNIONFIND_H
26 #define FIRM_ADT_UNIONFIND_H
27 
28 #include <assert.h>
29 
30 #include "../begin.h"
31 
49 static inline void uf_init(int* data, size_t n_elems)
50 {
51  size_t i;
52  for(i = 0; i < n_elems; ++i) {
53  data[i] = -1;
54  }
55 }
56 
66 static inline int uf_union(int* data, int set1, int set2)
67 {
68  int d1;
69  int d2;
70  int newcount;
71 
72  if(set1 == set2)
73  return set1;
74 
75  /* need 2 set representatives */
76  d1 = data[set1];
77  d2 = data[set2];
78  assert(d1 < 0 && d2 < 0);
79 
80  newcount = d1 + d2;
81  if(d1 > d2) {
82  data[set1] = set2;
83  data[set2] = newcount;
84  return set2;
85  } else {
86  data[set2] = set1;
87  data[set1] = newcount;
88  return set1;
89  }
90 }
91 
102 static inline int uf_find(int* data, int e)
103 {
104  /* go through list to find representative */
105  int repr = e;
106  while(data[repr] >= 0) {
107  repr = data[repr];
108  }
109 
110  /* update list to point to new representative (path compression) */
111  while(e != repr) {
112  int next = data[e];
113  data[e] = repr;
114  e = next;
115  }
116 
117  return repr;
118 }
119 
122 #include "../end.h"
123 
124 #endif