lib/Support/IntEqClasses.cpp

   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
  22 using namespace llvm;
  23
  24 void 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
  31 unsigned 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
  52 unsigned 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
  59 void 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
  66 void 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 }