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