1//===-- llvm/ADT/IntEqClasses.cpp - Equivalence Classes of Integers -------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// Equivalence classes for small integers. This is a mapping of the integers
11// 0 .. N-1 into M equivalence classes numbered 0 .. M-1.
12//
13// Initially each integer has its own equivalence class. Classes are joined by
14// passing a representative member of each class to join().
15//
16// Once the classes are built, compress() will number them 0 .. M-1 and prevent
17// further changes.
18//
19//===----------------------------------------------------------------------===//
20
21#include "llvm/ADT/IntEqClasses.h"
22
23using namespace llvm;
24
25void IntEqClasses::grow(unsigned N) {
26  assert(NumClasses == 0 && "grow() called after compress().");
27  EC.reserve(N);
28  while (EC.size() < N)
29    EC.push_back(EC.size());
30}
31
32void IntEqClasses::join(unsigned a, unsigned b) {
33  assert(NumClasses == 0 && "join() called after compress().");
34  unsigned eca = EC[a];
35  unsigned ecb = EC[b];
36  // Update pointers while searching for the leaders, compressing the paths
37  // incrementally. The larger leader will eventually be updated, joining the
38  // classes.
39  while (eca != ecb)
40    if (eca < ecb)
41      EC[b] = eca, b = ecb, ecb = EC[b];
42    else
43      EC[a] = ecb, a = eca, eca = EC[a];
44}
45
46unsigned IntEqClasses::findLeader(unsigned a) const {
47  assert(NumClasses == 0 && "findLeader() called after compress().");
48  while (a != EC[a])
49    a = EC[a];
50  return a;
51}
52
53void IntEqClasses::compress() {
54  if (NumClasses)
55    return;
56  for (unsigned i = 0, e = EC.size(); i != e; ++i)
57    EC[i] = (EC[i] == i) ? NumClasses++ : EC[EC[i]];
58}
59
60void IntEqClasses::uncompress() {
61  if (!NumClasses)
62    return;
63  SmallVector<unsigned, 8> Leader;
64  for (unsigned i = 0, e = EC.size(); i != e; ++i)
65    if (EC[i] < Leader.size())
66      EC[i] = Leader[EC[i]];
67    else
68      Leader.push_back(EC[i] = i);
69  NumClasses = 0;
70}
71