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 |
89 | |