/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 | // 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 | // Equivalence classes for small integers. This is a mapping of the integers | |

10 | // 0 .. N-1 into M equivalence classes numbered 0 .. M-1. | |

11 | // | |

12 | // Initially each integer has its own equivalence class. Classes are joined by | |

13 | // passing a representative member of each class to join(). | |

14 | // | |

15 | // Once the classes are built, compress() will number them 0 .. M-1 and prevent | |

16 | // further changes. | |

17 | // | |

18 | //===----------------------------------------------------------------------===// | |

19 | ||

20 | #ifndef LLVM_ADT_INTEQCLASSES_H | |

21 | #define LLVM_ADT_INTEQCLASSES_H | |

22 | ||

23 | #include "llvm/ADT/SmallVector.h" | |

24 | ||

25 | namespace llvm { | |

26 | ||

27 | class IntEqClasses { | |

28 | /// EC - When uncompressed, map each integer to a smaller member of its | |

29 | /// equivalence class. The class leader is the smallest member and maps to | |

30 | /// itself. | |

31 | /// | |

32 | /// When compressed, EC[i] is the equivalence class of i. | |

33 | SmallVector<unsigned, 8> EC; | |

34 | ||

35 | /// NumClasses - The number of equivalence classes when compressed, or 0 when | |

36 | /// uncompressed. | |

37 | unsigned NumClasses; | |

38 | ||

39 | public: | |

40 | /// IntEqClasses - Create an equivalence class mapping for 0 .. N-1. | |

41 | 3.28M | IntEqClasses(unsigned N = 0) : NumClasses(0) { grow(N); } |

42 | ||

43 | /// grow - Increase capacity to hold 0 .. N-1, putting new integers in unique | |

44 | /// equivalence classes. | |

45 | /// This requires an uncompressed map. | |

46 | void grow(unsigned N); | |

47 | ||

48 | /// clear - Clear all classes so that grow() will assign a unique class to | |

49 | /// every integer. | |

50 | 3.63M | void clear() { |

51 | 3.63M | EC.clear(); |

52 | 3.63M | NumClasses = 0; |

53 | 3.63M | } |

54 | ||

55 | /// Join the equivalence classes of a and b. After joining classes, | |

56 | /// findLeader(a) == findLeader(b). This requires an uncompressed map. | |

57 | /// Returns the new leader. | |

58 | unsigned join(unsigned a, unsigned b); | |

59 | ||

60 | /// findLeader - Compute the leader of a's equivalence class. This is the | |

61 | /// smallest member of the class. | |

62 | /// This requires an uncompressed map. | |

63 | unsigned findLeader(unsigned a) const; | |

64 | ||

65 | /// compress - Compress equivalence classes by numbering them 0 .. M. | |

66 | /// This makes the equivalence class map immutable. | |

67 | void compress(); | |

68 | ||

69 | /// getNumClasses - Return the number of equivalence classes after compress() | |

70 | /// was called. | |

71 | 25.3M | unsigned getNumClasses() const { return NumClasses; } |

72 | ||

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

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

75 | 417M | unsigned operator[](unsigned a) const { |

76 | 417M | assert(NumClasses && "operator[] called before compress()"); |

77 | 417M | return EC[a]; |

78 | 417M | } |

79 | ||

80 | /// uncompress - Change back to the uncompressed representation that allows | |

81 | /// editing. | |

82 | void uncompress(); | |

83 | }; | |

84 | ||

85 | } // End llvm namespace | |

86 | ||

87 | #endif |