2 * Copyright (c) 2000-2001
3 * The Regents of the University of California. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the University nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36 enum uf_type
{uf_ecr
,uf_link
};
37 typedef enum uf_type uf_type
;
44 struct uf_element
*link
;
47 struct uf_element
*new_uf_element(region r
, void *info
)
49 struct uf_element
*result
;
51 result
= ralloc(r
, struct uf_element
);
53 result
->type
= uf_ecr
;
61 static struct uf_element
*find(struct uf_element
*e
)
64 if (e
->type
== uf_ecr
)
67 else if (e
->link
->type
== uf_link
)
69 struct uf_element
*temp
= e
->link
;
71 e
->link
= e
->link
->link
;
80 bool uf_union(struct uf_element
*a
, struct uf_element
*b
)
82 struct uf_element
*e1
= find(a
);
83 struct uf_element
*e2
= find(b
);
88 else if (e1
->rank
< e2
->rank
)
96 else if (e1
->rank
> e2
->rank
)
116 bool uf_unify(combine_fn_ptr combine
,
117 struct uf_element
*a
, struct uf_element
*b
)
119 struct uf_element
*e1
= find(a
);
120 struct uf_element
*e2
= find(b
);
125 else if (e1
->rank
< e2
->rank
)
127 e2
->info
= combine(e2
->info
,e1
->info
);
134 else if (e1
->rank
> e2
->rank
)
136 e1
->info
= combine(e1
->info
,e2
->info
);
145 e2
->info
= combine(e2
->info
, e1
->info
);
157 void *uf_get_info(struct uf_element
*e
)
159 return find(e
)->info
;
163 bool uf_eq(struct uf_element
*e1
,struct uf_element
*e2
)
165 return (find(e1
) == find(e2
));
168 void uf_update(struct uf_element
*e
,uf_info i
)