1/* SparseSet implementation. 2 Copyright (C) 2007 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#include <assert.h> 25 26#define SPARSESET_ELT_BITS ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT) 27#define SPARSESET_ELT_TYPE unsigned int 28 29/* Data Structure used for the SparseSet representation. */ 30 31typedef struct sparseset_def 32{ 33 SPARSESET_ELT_TYPE *dense; /* Dense array. */ 34 SPARSESET_ELT_TYPE *sparse; /* Sparse array. */ 35 SPARSESET_ELT_TYPE members; /* Number of elements. */ 36 SPARSESET_ELT_TYPE size; /* Maximum number of elements. */ 37 SPARSESET_ELT_TYPE iter; /* Iterator index. */ 38 unsigned char iter_inc; /* Iteration increment amount. */ 39 bool iterating; 40 SPARSESET_ELT_TYPE elms[2]; /* Combined dense and sparse arrays. */ 41} *sparseset; 42 43#define sparseset_free(MAP) free(MAP) 44extern sparseset sparseset_alloc (SPARSESET_ELT_TYPE n_elms); 45extern void sparseset_clear_bit (sparseset, SPARSESET_ELT_TYPE); 46extern void sparseset_copy (sparseset, sparseset); 47extern void sparseset_and (sparseset, sparseset, sparseset); 48extern void sparseset_and_compl (sparseset, sparseset, sparseset); 49extern void sparseset_ior (sparseset, sparseset, sparseset); 50extern bool sparseset_equal_p (sparseset, sparseset); 51 52/* Operation: S = {} 53 Clear the set of all elements. */ 54 55static inline void 56sparseset_clear (sparseset s) 57{ 58 s->members = 0; 59 s->iterating = false; 60} 61 62/* Return the number of elements currently in the set. */ 63 64static inline SPARSESET_ELT_TYPE 65sparseset_cardinality (sparseset s) 66{ 67 return s->members; 68} 69 70/* Return the maximum number of elements this set can hold. */ 71 72static inline SPARSESET_ELT_TYPE 73sparseset_size (sparseset s) 74{ 75 return s->size; 76} 77 78/* Return true if e is a member of the set S, otherwise return false. */ 79 80static inline bool 81sparseset_bit_p (sparseset s, SPARSESET_ELT_TYPE e) 82{ 83 SPARSESET_ELT_TYPE idx; 84 85 gcc_assert (e < s->size); 86 87 idx = s->sparse[e]; 88 89 return idx < s->members && s->dense[idx] == e; 90} 91 92/* Low level insertion routine not meant for use outside of sparseset.[ch]. 93 Assumes E is valid and not already a member of the set S. */ 94 95static inline void 96sparseset_insert_bit (sparseset s, SPARSESET_ELT_TYPE e, SPARSESET_ELT_TYPE idx) 97{ 98 s->sparse[e] = idx; 99 s->dense[idx] = e; 100} 101 102/* Operation: S = S + {e} 103 Insert E into the set S, if it isn't already a member. */ 104 105static inline void 106sparseset_set_bit (sparseset s, SPARSESET_ELT_TYPE e) 107{ 108 if (!sparseset_bit_p (s, e)) 109 sparseset_insert_bit (s, e, s->members++); 110} 111 112/* Return and remove an arbitrary element from the set S. */ 113 114static inline SPARSESET_ELT_TYPE 115sparseset_pop (sparseset s) 116{ 117 SPARSESET_ELT_TYPE mem = s->members; 118 119 gcc_assert (mem != 0); 120 121 s->members = mem - 1; 122 return s->dense[mem]; 123} 124 125static inline void 126sparseset_iter_init (sparseset s) 127{ 128 s->iter = 0; 129 s->iter_inc = 1; 130 s->iterating = true; 131} 132 133static inline bool 134sparseset_iter_p (sparseset s) 135{ 136 if (s->iterating && s->iter < s->members) 137 return true; 138 else 139 return s->iterating = false; 140} 141 142static inline SPARSESET_ELT_TYPE 143sparseset_iter_elm (sparseset s) 144{ 145 return s->dense[s->iter]; 146} 147 148static inline void 149sparseset_iter_next (sparseset s) 150{ 151 s->iter += s->iter_inc; 152 s->iter_inc = 1; 153} 154 155#define EXECUTE_IF_SET_IN_SPARSESET(SPARSESET, ITER) \ 156 for (sparseset_iter_init (SPARSESET); \ 157 sparseset_iter_p (SPARSESET) \ 158 && (((ITER) = sparseset_iter_elm (SPARSESET)) || 1); \ 159 sparseset_iter_next (SPARSESET)) 160 161#endif /* GCC_SPARSESET_H */ 162