contrib/llvm/lib/Support/IntEqClasses.cpp

   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
  23 using namespace llvm;
  24
  25 void 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
  32 unsigned 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;
  42       b = ecb;
  43       ecb = EC[b];
  44     } else {
  45       EC[a] = ecb;
  46       a = eca;
  47       eca = EC[a];
  48     }
  49
  50   return eca;
  51 }
  52
  53 unsigned IntEqClasses::findLeader(unsigned a) const {
  54   assert(NumClasses == 0 && "findLeader() called after compress().");
  55   while (a != EC[a])
  56     a = EC[a];
  57   return a;
  58 }
  59
  60 void IntEqClasses::compress() {
  61   if (NumClasses)
  62     return;
  63   for (unsigned i = 0, e = EC.size(); i != e; ++i)
  64     EC[i] = (EC[i] == i) ? NumClasses++ : EC[EC[i]];
  65 }
  66
  67 void IntEqClasses::uncompress() {
  68   if (!NumClasses)
  69     return;
  70   SmallVector<unsigned, 8> Leader;
  71   for (unsigned i = 0, e = EC.size(); i != e; ++i)
  72     if (EC[i] < Leader.size())
  73       EC[i] = Leader[EC[i]];
  74     else
  75       Leader.push_back(EC[i] = i);
  76   NumClasses = 0;
  77 }