Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 14 | pmbaty | 1 | //===-- llvm/ADT/IntEqClasses.h - Equiv. Classes of Integers ----*- C++ -*-===// |
| 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 | /// \file |
||
| 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 | #ifndef LLVM_ADT_INTEQCLASSES_H |
||
| 22 | #define LLVM_ADT_INTEQCLASSES_H |
||
| 23 | |||
| 24 | #include "llvm/ADT/SmallVector.h" |
||
| 25 | |||
| 26 | namespace llvm { |
||
| 27 | |||
| 28 | class IntEqClasses { |
||
| 29 | /// EC - When uncompressed, map each integer to a smaller member of its |
||
| 30 | /// equivalence class. The class leader is the smallest member and maps to |
||
| 31 | /// itself. |
||
| 32 | /// |
||
| 33 | /// When compressed, EC[i] is the equivalence class of i. |
||
| 34 | SmallVector<unsigned, 8> EC; |
||
| 35 | |||
| 36 | /// NumClasses - The number of equivalence classes when compressed, or 0 when |
||
| 37 | /// uncompressed. |
||
| 38 | unsigned NumClasses = 0; |
||
| 39 | |||
| 40 | public: |
||
| 41 | /// IntEqClasses - Create an equivalence class mapping for 0 .. N-1. |
||
| 42 | IntEqClasses(unsigned N = 0) { grow(N); } |
||
| 43 | |||
| 44 | /// grow - Increase capacity to hold 0 .. N-1, putting new integers in unique |
||
| 45 | /// equivalence classes. |
||
| 46 | /// This requires an uncompressed map. |
||
| 47 | void grow(unsigned N); |
||
| 48 | |||
| 49 | /// clear - Clear all classes so that grow() will assign a unique class to |
||
| 50 | /// every integer. |
||
| 51 | void clear() { |
||
| 52 | EC.clear(); |
||
| 53 | NumClasses = 0; |
||
| 54 | } |
||
| 55 | |||
| 56 | /// Join the equivalence classes of a and b. After joining classes, |
||
| 57 | /// findLeader(a) == findLeader(b). This requires an uncompressed map. |
||
| 58 | /// Returns the new leader. |
||
| 59 | unsigned join(unsigned a, unsigned b); |
||
| 60 | |||
| 61 | /// findLeader - Compute the leader of a's equivalence class. This is the |
||
| 62 | /// smallest member of the class. |
||
| 63 | /// This requires an uncompressed map. |
||
| 64 | unsigned findLeader(unsigned a) const; |
||
| 65 | |||
| 66 | /// compress - Compress equivalence classes by numbering them 0 .. M. |
||
| 67 | /// This makes the equivalence class map immutable. |
||
| 68 | void compress(); |
||
| 69 | |||
| 70 | /// getNumClasses - Return the number of equivalence classes after compress() |
||
| 71 | /// was called. |
||
| 72 | unsigned getNumClasses() const { return NumClasses; } |
||
| 73 | |||
| 74 | /// operator[] - Return a's equivalence class number, 0 .. getNumClasses()-1. |
||
| 75 | /// This requires a compressed map. |
||
| 76 | unsigned operator[](unsigned a) const { |
||
| 77 | assert(NumClasses && "operator[] called before compress()"); |
||
| 78 | return EC[a]; |
||
| 79 | } |
||
| 80 | |||
| 81 | /// uncompress - Change back to the uncompressed representation that allows |
||
| 82 | /// editing. |
||
| 83 | void uncompress(); |
||
| 84 | }; |
||
| 85 | |||
| 86 | } // End llvm namespace |
||
| 87 | |||
| 88 | #endif |