llvm/ADT/IntEqClasses.h

0001 //===-- llvm/ADT/IntEqClasses.h - Equiv. Classes of Integers ----*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 /// \file
0010 /// Equivalence classes for small integers. This is a mapping of the integers
0011 /// 0 .. N-1 into M equivalence classes numbered 0 .. M-1.
0012 ///
0013 /// Initially each integer has its own equivalence class. Classes are joined by
0014 /// passing a representative member of each class to join().
0015 ///
0016 /// Once the classes are built, compress() will number them 0 .. M-1 and prevent
0017 /// further changes.
0018 ///
0019 //===----------------------------------------------------------------------===//
0020
0021 #ifndef LLVM_ADT_INTEQCLASSES_H
0022 #define LLVM_ADT_INTEQCLASSES_H
0023
0024 #include "llvm/ADT/SmallVector.h"
0025
0026 namespace llvm {
0027
0028 class IntEqClasses {
0029   /// EC - When uncompressed, map each integer to a smaller member of its
0030   /// equivalence class. The class leader is the smallest member and maps to
0031   /// itself.
0032   ///
0033   /// When compressed, EC[i] is the equivalence class of i.
0034   SmallVector<unsigned, 8> EC;
0035
0036   /// NumClasses - The number of equivalence classes when compressed, or 0 when
0037   /// uncompressed.
0038   unsigned NumClasses = 0;
0039
0040 public:
0041   /// IntEqClasses - Create an equivalence class mapping for 0 .. N-1.
0042   IntEqClasses(unsigned N = 0) { grow(N); }
0043
0044   /// grow - Increase capacity to hold 0 .. N-1, putting new integers in unique
0045   /// equivalence classes.
0046   /// This requires an uncompressed map.
0047   void grow(unsigned N);
0048
0049   /// clear - Clear all classes so that grow() will assign a unique class to
0050   /// every integer.
0051   void clear() {
0052     EC.clear();
0053     NumClasses = 0;
0054   }
0055
0056   /// Join the equivalence classes of a and b. After joining classes,
0057   /// findLeader(a) == findLeader(b). This requires an uncompressed map.
0058   /// Returns the new leader.
0059   unsigned join(unsigned a, unsigned b);
0060
0061   /// findLeader - Compute the leader of a's equivalence class. This is the
0062   /// smallest member of the class.
0063   /// This requires an uncompressed map.
0064   unsigned findLeader(unsigned a) const;
0065
0066   /// compress - Compress equivalence classes by numbering them 0 .. M.
0067   /// This makes the equivalence class map immutable.
0068   void compress();
0069
0070   /// getNumClasses - Return the number of equivalence classes after compress()
0071   /// was called.
0072   unsigned getNumClasses() const { return NumClasses; }
0073
0074   /// operator[] - Return a's equivalence class number, 0 .. getNumClasses()-1.
0075   /// This requires a compressed map.
0076   unsigned operator[](unsigned a) const {
0077     assert(NumClasses && "operator[] called before compress()");
0078     return EC[a];
0079   }
0080
0081   /// uncompress - Change back to the uncompressed representation that allows
0082   /// editing.
0083   void uncompress();
0084 };
0085
0086 } // End llvm namespace
0087
0088 #endif