/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/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 | 2.41M | 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.80M | void clear() { |

52 | 2.80M | EC.clear(); |

53 | 2.80M | NumClasses = 0; |

54 | 2.80M | } |

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 | 23.2M | unsigned getNumClasses() const { return NumClasses; } |

73 | ||

74 | /// operator[] - Return a's equivalence class number, 0 .. getNumClasses()-1. | |

75 | /// This requires a compressed map. | |

76 | 400M | unsigned operator[](unsigned a) const { |

77 | 400M | assert(NumClasses && "operator[] called before compress()"); |

78 | 400M | return EC[a]; |

79 | 400M | } |

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 |