1/* SparseSet implementation. 2 Copyright (C) 2007-2015 Free Software Foundation, Inc. 3 Contributed by Peter Bergner <bergner@vnet.ibm.com> 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 3, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along 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 89typedef 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) 102extern sparseset sparseset_alloc (SPARSESET_ELT_TYPE n_elms); 103extern void sparseset_clear_bit (sparseset, SPARSESET_ELT_TYPE); 104extern void sparseset_copy (sparseset, sparseset); 105extern void sparseset_and (sparseset, sparseset, sparseset); 106extern void sparseset_and_compl (sparseset, sparseset, sparseset); 107extern void sparseset_ior (sparseset, sparseset, sparseset); 108extern bool sparseset_equal_p (sparseset, sparseset); 109 110/* Operation: S = {} 111 Clear the set of all elements. */ 112 113static inline void 114sparseset_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 122static inline SPARSESET_ELT_TYPE 123sparseset_cardinality (sparseset s) 124{ 125 return s->members; 126} 127 128/* Return the maximum number of elements this set can hold. */ 129 130static inline SPARSESET_ELT_TYPE 131sparseset_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 138static inline bool 139sparseset_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 153static inline void 154sparseset_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 163static inline void 164sparseset_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 172static inline SPARSESET_ELT_TYPE 173sparseset_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 183static inline void 184sparseset_iter_init (sparseset s) 185{ 186 s->iter = 0; 187 s->iter_inc = 1; 188 s->iterating = true; 189} 190 191static inline bool 192sparseset_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 200static inline SPARSESET_ELT_TYPE 201sparseset_iter_elm (sparseset s) 202{ 203 return s->dense[s->iter]; 204} 205 206static inline void 207sparseset_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