gcc/sparseset.h

   1 /* SparseSet implementation.
   2    Copyright (C) 2007-2022 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 * sizeof (SPARSESET_ELT_TYPE) * 8 * 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_TYPE unsigned int
  87
  88 typedef struct sparseset_def
  89 {
  90   SPARSESET_ELT_TYPE *dense;    /* Dense array.  */
  91   SPARSESET_ELT_TYPE *sparse;   /* Sparse array.  */
  92   SPARSESET_ELT_TYPE members;   /* Number of elements.  */
  93   SPARSESET_ELT_TYPE size;      /* Maximum number of elements.  */
  94   SPARSESET_ELT_TYPE iter;      /* Iterator index.  */
  95   unsigned char iter_inc;       /* Iteration increment amount.  */
  96   bool iterating;
  97   SPARSESET_ELT_TYPE elms[2];   /* Combined dense and sparse arrays.  */
  98 } *sparseset;
  99
 100 #define sparseset_free(MAP)  free(MAP)
 101 extern sparseset sparseset_alloc (SPARSESET_ELT_TYPE n_elms);
 102 extern void sparseset_clear_bit (sparseset, SPARSESET_ELT_TYPE);
 103 extern void sparseset_copy (sparseset, sparseset);
 104 extern void sparseset_and (sparseset, sparseset, sparseset);
 105 extern void sparseset_and_compl (sparseset, sparseset, sparseset);
 106 extern void sparseset_ior (sparseset, sparseset, sparseset);
 107 extern bool sparseset_equal_p (sparseset, sparseset);
 108
 109 /* Operation: S = {}
 110    Clear the set of all elements.  */
 111
 112 static inline void
 113 sparseset_clear (sparseset s)
 114 {
 115   s->members = 0;
 116   s->iterating = false;
 117 }
 118
 119 /* Return the number of elements currently in the set.  */
 120
 121 static inline SPARSESET_ELT_TYPE
 122 sparseset_cardinality (sparseset s)
 123 {
 124   return s->members;
 125 }
 126
 127 /* Return the maximum number of elements this set can hold.  */
 128
 129 static inline SPARSESET_ELT_TYPE
 130 sparseset_size (sparseset s)
 131 {
 132   return s->size;
 133 }
 134
 135 /* Return true if e is a member of the set S, otherwise return false.  */
 136
 137 static inline bool
 138 sparseset_bit_p (sparseset s, SPARSESET_ELT_TYPE e)
 139 {
 140   SPARSESET_ELT_TYPE idx;
 141
 142   gcc_checking_assert (e < s->size);
 143
 144   idx = s->sparse[e];
 145
 146   return idx < s->members && s->dense[idx] == e;
 147 }
 148
 149 /* Low level insertion routine not meant for use outside of sparseset.[ch].
 150    Assumes E is valid and not already a member of the set S.  */
 151
 152 static inline void
 153 sparseset_insert_bit (sparseset s, SPARSESET_ELT_TYPE e, SPARSESET_ELT_TYPE idx)
 154 {
 155   s->sparse[e] = idx;
 156   s->dense[idx] = e;
 157 }
 158
 159 /* Operation: S = S + {e}
 160    Insert E into the set S, if it isn't already a member.  */
 161
 162 static inline void
 163 sparseset_set_bit (sparseset s, SPARSESET_ELT_TYPE e)
 164 {
 165   if (!sparseset_bit_p (s, e))
 166     sparseset_insert_bit (s, e, s->members++);
 167 }
 168
 169 /* Return and remove the last member added to the set S.  */
 170
 171 static inline SPARSESET_ELT_TYPE
 172 sparseset_pop (sparseset s)
 173 {
 174   SPARSESET_ELT_TYPE mem = s->members;
 175
 176   gcc_checking_assert (mem != 0);
 177
 178   s->members = mem - 1;
 179   return s->dense[s->members];
 180 }
 181
 182 static inline void
 183 sparseset_iter_init (sparseset s)
 184 {
 185   s->iter = 0;
 186   s->iter_inc = 1;
 187   s->iterating = true;
 188 }
 189
 190 static inline bool
 191 sparseset_iter_p (sparseset s)
 192 {
 193   if (s->iterating && s->iter < s->members)
 194     return true;
 195   else
 196     return s->iterating = false;
 197 }
 198
 199 static inline SPARSESET_ELT_TYPE
 200 sparseset_iter_elm (sparseset s)
 201 {
 202   return s->dense[s->iter];
 203 }
 204
 205 static inline void
 206 sparseset_iter_next (sparseset s)
 207 {
 208   s->iter += s->iter_inc;
 209   s->iter_inc = 1;
 210 }
 211
 212 #define EXECUTE_IF_SET_IN_SPARSESET(SPARSESET, ITER)                    \
 213   for (sparseset_iter_init (SPARSESET);                                 \
 214        sparseset_iter_p (SPARSESET)                                     \
 215        && (((ITER) = sparseset_iter_elm (SPARSESET)) || 1);             \
 216        sparseset_iter_next (SPARSESET))
 217
 218 #endif /* GCC_SPARSESET_H */