/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/ADT/IntEqClasses.h
Line | Count | Source |
1 | | //===-- llvm/ADT/IntEqClasses.h - Equiv. Classes of Integers ----*- C++ -*-===// |
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 | | #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; |
39 | | |
40 | | public: |
41 | | /// IntEqClasses - Create an equivalence class mapping for 0 .. N-1. |
42 | 1.76M | IntEqClasses(unsigned N = 0) : NumClasses(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 | 2.21M | void clear() { |
52 | 2.21M | EC.clear(); |
53 | 2.21M | NumClasses = 0; |
54 | 2.21M | } |
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 | 30.3M | unsigned getNumClasses() const { return NumClasses; } |
73 | | |
74 | | /// operator[] - Return a's equivalence class number, 0 .. getNumClasses()-1. |
75 | | /// This requires a compressed map. |
76 | 629M | unsigned operator[](unsigned a) const { |
77 | 629M | assert(NumClasses && "operator[] called before compress()"); |
78 | 629M | return EC[a]; |
79 | 629M | } |
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 |