1 | /* SparseSet implementation. |
---|---|

2 | Copyright (C) 2007-2017 Free Software Foundation, Inc. |

3 | Contributed by Peter Bergner <bergner@vnet.ibm.com> |

4 | |

5 | This file is part of GCC. |

6 | |

7 | GCC is free software; you can redistribute it and/or modify it under |

8 | the terms of the GNU General Public License as published by the Free |

9 | Software Foundation; either version 3, or (at your option) any later |

10 | version. |

11 | |

12 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |

13 | WARRANTY; without even the implied warranty of MERCHANTABILITY or |

14 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |

15 | for more details. |

16 | |

17 | You should have received a copy of the GNU General Public License |

18 | along with GCC; see the file COPYING3. If not see |

19 | <http://www.gnu.org/licenses/>. */ |

20 | |

21 | #ifndef GCC_SPARSESET_H |

22 | #define GCC_SPARSESET_H |

23 | |

24 | /* Implementation of the Briggs and Torczon sparse set representation. |

25 | The sparse set representation was first published in: |

26 | |

27 | "An Efficient Representation for Sparse Sets", |

28 | ACM LOPLAS, Vol. 2, Nos. 1-4, March-December 1993, Pages 59-69. |

29 | |

30 | The sparse set representation is suitable for integer sets with a |

31 | fixed-size universe. Two vectors are used to store the members of |

32 | the set. If an element I is in the set, then sparse[I] is the |

33 | index of I in the dense vector, and dense[sparse[I]] == I. The dense |

34 | vector works like a stack. The size of the stack is the cardinality |

35 | of the set. |

36 | |

37 | The following operations can be performed in O(1) time: |

38 | |

39 | * clear : sparseset_clear |

40 | * cardinality : sparseset_cardinality |

41 | * set_size : sparseset_size |

42 | * member_p : sparseset_bit_p |

43 | * add_member : sparseset_set_bit |

44 | * remove_member : sparseset_clear_bit |

45 | * choose_one : sparseset_pop |

46 | |

47 | Additionally, the sparse set representation supports enumeration of |

48 | the members in O(N) time, where n is the number of members in the set. |

49 | The members of the set are stored cache-friendly in the dense vector. |

50 | This makes it a competitive choice for iterating over relatively sparse |

51 | sets requiring operations: |

52 | |

53 | * forall : EXECUTE_IF_SET_IN_SPARSESET |

54 | * set_copy : sparseset_copy |

55 | * set_intersection : sparseset_and |

56 | * set_union : sparseset_ior |

57 | * set_difference : sparseset_and_compl |

58 | * set_disjuction : (not implemented) |

59 | * set_compare : sparseset_equal_p |

60 | |

61 | NB: It is OK to use remove_member during EXECUTE_IF_SET_IN_SPARSESET. |

62 | The iterator is updated for it. |

63 | |

64 | Based on the efficiency of these operations, this representation of |

65 | sparse sets will often be superior to alternatives such as simple |

66 | bitmaps, linked-list bitmaps, array bitmaps, balanced binary trees, |

67 | hash tables, linked lists, etc., if the set is sufficiently sparse. |

68 | In the LOPLAS paper the cut-off point where sparse sets became faster |

69 | than simple bitmaps (see sbitmap.h) when N / U < 64 (where U is the |

70 | size of the universe of the set). |

71 | |

72 | Because the set universe is fixed, the set cannot be resized. For |

73 | sparse sets with initially unknown size, linked-list bitmaps are a |

74 | better choice, see bitmap.h. |

75 | |

76 | Sparse sets storage requirements are relatively large: O(U) with a |

77 | larger constant than sbitmaps (if the storage requirement for an |

78 | sbitmap with universe U is S, then the storage required for a sparse |

79 | set for the same universe are 2*HOST_BITS_PER_WIDEST_FAST_INT * S). |

80 | Accessing the sparse vector is not very cache-friendly, but iterating |

81 | over the members in the set is cache-friendly because only the dense |

82 | vector is used. */ |

83 | |

84 | /* Data Structure used for the SparseSet representation. */ |

85 | |

86 | #define SPARSESET_ELT_BITS ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT) |

87 | #define SPARSESET_ELT_TYPE unsigned HOST_WIDEST_FAST_INT |

88 | |

89 | typedef struct sparseset_def |

90 | { |

91 | SPARSESET_ELT_TYPE *dense; /* Dense array. */ |

92 | SPARSESET_ELT_TYPE *sparse; /* Sparse array. */ |

93 | SPARSESET_ELT_TYPE members; /* Number of elements. */ |

94 | SPARSESET_ELT_TYPE size; /* Maximum number of elements. */ |

95 | SPARSESET_ELT_TYPE iter; /* Iterator index. */ |

96 | unsigned char iter_inc; /* Iteration increment amount. */ |

97 | bool iterating; |

98 | SPARSESET_ELT_TYPE elms[2]; /* Combined dense and sparse arrays. */ |

99 | } *sparseset; |

100 | |

101 | #define sparseset_free(MAP) free(MAP) |

102 | extern sparseset sparseset_alloc (SPARSESET_ELT_TYPE n_elms); |

103 | extern void sparseset_clear_bit (sparseset, SPARSESET_ELT_TYPE); |

104 | extern void sparseset_copy (sparseset, sparseset); |

105 | extern void sparseset_and (sparseset, sparseset, sparseset); |

106 | extern void sparseset_and_compl (sparseset, sparseset, sparseset); |

107 | extern void sparseset_ior (sparseset, sparseset, sparseset); |

108 | extern bool sparseset_equal_p (sparseset, sparseset); |

109 | |

110 | /* Operation: S = {} |

111 | Clear the set of all elements. */ |

112 | |

113 | static inline void |

114 | sparseset_clear (sparseset s) |

115 | { |

116 | s->members = 0; |

117 | s->iterating = false; |

118 | } |

119 | |

120 | /* Return the number of elements currently in the set. */ |

121 | |

122 | static inline SPARSESET_ELT_TYPE |

123 | sparseset_cardinality (sparseset s) |

124 | { |

125 | return s->members; |

126 | } |

127 | |

128 | /* Return the maximum number of elements this set can hold. */ |

129 | |

130 | static inline SPARSESET_ELT_TYPE |

131 | sparseset_size (sparseset s) |

132 | { |

133 | return s->size; |

134 | } |

135 | |

136 | /* Return true if e is a member of the set S, otherwise return false. */ |

137 | |

138 | static inline bool |

139 | sparseset_bit_p (sparseset s, SPARSESET_ELT_TYPE e) |

140 | { |

141 | SPARSESET_ELT_TYPE idx; |

142 | |

143 | gcc_checking_assert (e < s->size); |

144 | |

145 | idx = s->sparse[e]; |

146 | |

147 | return idx < s->members && s->dense[idx] == e; |

148 | } |

149 | |

150 | /* Low level insertion routine not meant for use outside of sparseset.[ch]. |

151 | Assumes E is valid and not already a member of the set S. */ |

152 | |

153 | static inline void |

154 | sparseset_insert_bit (sparseset s, SPARSESET_ELT_TYPE e, SPARSESET_ELT_TYPE idx) |

155 | { |

156 | s->sparse[e] = idx; |

157 | s->dense[idx] = e; |

158 | } |

159 | |

160 | /* Operation: S = S + {e} |

161 | Insert E into the set S, if it isn't already a member. */ |

162 | |

163 | static inline void |

164 | sparseset_set_bit (sparseset s, SPARSESET_ELT_TYPE e) |

165 | { |

166 | if (!sparseset_bit_p (s, e)) |

167 | sparseset_insert_bit (s, e, s->members++); |

168 | } |

169 | |

170 | /* Return and remove the last member added to the set S. */ |

171 | |

172 | static inline SPARSESET_ELT_TYPE |

173 | sparseset_pop (sparseset s) |

174 | { |

175 | SPARSESET_ELT_TYPE mem = s->members; |

176 | |

177 | gcc_checking_assert (mem != 0); |

178 | |

179 | s->members = mem - 1; |

180 | return s->dense[s->members]; |

181 | } |

182 | |

183 | static inline void |

184 | sparseset_iter_init (sparseset s) |

185 | { |

186 | s->iter = 0; |

187 | s->iter_inc = 1; |

188 | s->iterating = true; |

189 | } |

190 | |

191 | static inline bool |

192 | sparseset_iter_p (sparseset s) |

193 | { |

194 | if (s->iterating && s->iter < s->members) |

195 | return true; |

196 | else |

197 | return s->iterating = false; |

198 | } |

199 | |

200 | static inline SPARSESET_ELT_TYPE |

201 | sparseset_iter_elm (sparseset s) |

202 | { |

203 | return s->dense[s->iter]; |

204 | } |

205 | |

206 | static inline void |

207 | sparseset_iter_next (sparseset s) |

208 | { |

209 | s->iter += s->iter_inc; |

210 | s->iter_inc = 1; |

211 | } |

212 | |

213 | #define EXECUTE_IF_SET_IN_SPARSESET(SPARSESET, ITER) \ |

214 | for (sparseset_iter_init (SPARSESET); \ |

215 | sparseset_iter_p (SPARSESET) \ |

216 | && (((ITER) = sparseset_iter_elm (SPARSESET)) || 1); \ |

217 | sparseset_iter_next (SPARSESET)) |

218 | |

219 | #endif /* GCC_SPARSESET_H */ |

220 |