Mercurial > hg > CbC > CbC_gcc
annotate gcc/ebitmap.c @ 67:f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
| author | nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 22 Mar 2011 17:18:12 +0900 |
| parents | b7f97abdc517 |
| children |
| rev | line source |
|---|---|
| 0 | 1 /* Sparse array-based bitmaps. |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2 Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc. |
| 0 | 3 Contributed by Daniel Berlin <dberlin@dberlin.org> |
| 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 #include "config.h" | |
| 22 #include "system.h" | |
| 23 #include "coretypes.h" | |
| 24 #include "ebitmap.h" | |
| 25 | |
| 26 /* The ebitmap data structure is a sparse bitmap structure that works | |
| 27 by having two pieces: | |
| 28 1. An array of all nonzero words in the structures, organized as | |
| 29 an array of HOST_WIDE_INT's. | |
| 30 2. A non-sparse bitmap saying which bitmap words are present in the | |
| 31 array. | |
| 32 | |
| 33 As a consequence of this representation, testing whether a bit | |
| 34 exists in the bitmap is faster than linked-list bitmaps. For bits | |
| 35 in words that are all zero, the time to test is O(1). For bits in | |
| 36 words that exist, it requires O(n/sizeof(word)) time to perform the | |
| 37 test (ignoring the one element cache). It also has much better | |
| 38 locality than linked-list bitmaps. | |
| 39 | |
| 40 To test whether a bit exists, we do the following: | |
| 41 1. Test whether the word the bit would appear in exists in the | |
| 42 bitmap (O(1) check of the mask). If not, fail. | |
| 43 | |
| 44 2. Population count the mask up to the word containing the bit, to | |
| 45 find the place in the array the word would be (popcount is cached, | |
| 46 but this is just as slow as the linked-list bitmap) | |
| 47 3. Test the word to see if the bit exists. | |
| 48 | |
| 49 Just like linked-list bitmaps, we cache the last element that has | |
| 50 been tested in order to speed up common access patterns. | |
| 51 | |
| 52 Most of the other speedups are simply due to better locality of the | |
| 53 single contiguous array. | |
| 54 | |
| 55 As would be expected in a structure like this, insertion into an | |
| 56 empty word in the middle requires moving bits to make room for the | |
| 57 new word. As most operations that perform sets perform them in | |
| 58 order, this is rarely a problem. We also take advantage of the | |
| 59 same element cache to make repeated sets to the same word O(1). | |
| 60 | |
| 61 Operations on the entire bitmap are also more efficient than linked | |
| 62 list bitmaps, as they are all operating on contiguous memory, and | |
| 63 can be easily vectorized. They are all O(number of words) + | |
| 64 O(number of bits that may end up in the destination), as the | |
| 65 appropriate operation is first performed on the word mask, and then | |
| 66 only those elements that may generate results are touched. | |
| 67 | |
| 68 Memory wise, the ebitmap starts out using less memory than the | |
| 69 linked-list bitmap, but its size in memory is technically bounded | |
| 70 by ((index of the highest bit set) / (size of a word) + (index of | |
| 71 the highest bit set) / ((size of a word) * (size of a word))) This | |
| 72 is because the mask is non-sparse. The mask could be transformed | |
| 73 into a sparse bitmap at the cost of making bit testing | |
| 74 *theoretically* slower (real world numbers have not been computed | |
| 75 yet as to whether it matters or not). */ | |
| 76 | |
| 77 /* #define EBITMAP_DEBUGGING */ | |
| 78 | |
| 79 /* Find the last set bit in ebitmap MAP. */ | |
| 80 | |
| 81 int | |
| 82 ebitmap_last_set_bit (ebitmap map) | |
| 83 { | |
| 84 unsigned int i = 0; | |
| 85 ebitmap_iterator ebi; | |
| 86 bool foundbit = false; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
87 |
| 0 | 88 /* This is not the fastest way to do this, we could simply look for |
| 89 the popcount, and start there, but this function is not used | |
| 90 anywhere speed critical. */ | |
| 91 EXECUTE_IF_SET_IN_EBITMAP (map, 0, i, ebi) | |
| 92 { | |
| 93 foundbit = true; | |
| 94 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
95 |
| 0 | 96 |
| 97 if (foundbit) | |
| 98 return i; | |
| 99 return -1; | |
| 100 } | |
| 101 | |
| 102 /* Grow or shrink the internal word array for MAP to NEWSIZE | |
| 103 elements. */ | |
| 104 | |
| 105 static inline void | |
| 106 ebitmap_array_grow (ebitmap map, unsigned int newsize) | |
| 107 { | |
| 108 if (newsize <= map->n_elts) | |
| 109 { | |
| 110 map->n_elts = newsize; | |
| 111 return; | |
| 112 } | |
| 113 | |
| 114 newsize += newsize / 4; | |
| 115 | |
| 116 map->n_elts = newsize; | |
| 117 map->elts = XRESIZEVEC (EBITMAP_ELT_TYPE, map->elts, newsize); | |
| 118 } | |
| 119 | |
| 120 /* Grow the internal word array for MAP so it is at least SIZE | |
| 121 elements. Will not shrink the array if it is already big | |
| 122 enough. */ | |
| 123 | |
| 124 static inline void | |
| 125 ebitmap_array_maybe_grow (ebitmap map, unsigned int size) | |
| 126 { | |
| 127 if (size >= map->n_elts) | |
| 128 ebitmap_array_grow (map, size + 1); | |
| 129 } | |
| 130 | |
| 131 /* Retrieve the IDX'th element from the word array for MAP. */ | |
| 132 | |
| 133 static inline EBITMAP_ELT_TYPE | |
| 134 ebitmap_array_get (ebitmap map, unsigned int idx) | |
| 135 { | |
| 136 gcc_assert (idx < map->n_elts); | |
| 137 return map->elts[idx]; | |
| 138 } | |
| 139 | |
| 140 /* Retrieve a pointer to the IDX'th element from the word array for | |
| 141 MAP. If the element index is greater than the size of the array, | |
| 142 the array will be grown to the correct size. */ | |
| 143 | |
| 144 static inline EBITMAP_ELT_TYPE * | |
| 145 ebitmap_array_grow_get (ebitmap map, unsigned int idx) | |
| 146 { | |
| 147 if (idx >= map->n_elts) | |
| 148 ebitmap_array_grow (map, idx + 1); | |
| 149 return &map->elts[idx]; | |
| 150 } | |
| 151 | |
| 152 /* Initialize the internal word array for MAP, so that it is SIZE | |
| 153 elements. */ | |
| 154 | |
| 155 static inline void | |
| 156 ebitmap_array_init (ebitmap map, unsigned int size) | |
| 157 { | |
| 158 if (size > 0) | |
| 159 { | |
| 160 map->elts = XNEWVEC (EBITMAP_ELT_TYPE, size); | |
| 161 map->n_elts = size; | |
| 162 } | |
| 163 else | |
| 164 { | |
| 165 map->n_elts = 0; | |
| 166 map->elts = NULL; | |
| 167 } | |
| 168 } | |
| 169 | |
| 170 /* Free the internal word array for MAP. */ | |
| 171 | |
| 172 static inline void | |
| 173 ebitmap_array_clear (ebitmap map) | |
| 174 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
175 if (map->elts) |
| 0 | 176 { |
| 177 free (map->elts); | |
| 178 map->elts = NULL; | |
| 179 } | |
| 180 map->n_elts = 0; | |
| 181 } | |
| 182 | |
| 183 /* Clear ebitmap MAP. */ | |
| 184 | |
| 185 void | |
| 186 ebitmap_clear (ebitmap map) | |
| 187 { | |
| 188 ebitmap_array_clear (map); | |
| 189 sbitmap_zero (map->wordmask); | |
| 190 map->wordmask = sbitmap_resize (map->wordmask, 1, 0); | |
| 191 map->numwords = 0; | |
| 192 map->cache = NULL; | |
| 193 map->cacheindex = 0; | |
| 194 } | |
| 195 | |
| 196 /* Allocate an ebitmap with enough room for SIZE bits to start out. */ | |
| 197 | |
| 198 ebitmap | |
| 199 ebitmap_alloc (unsigned int size) | |
| 200 { | |
| 201 ebitmap ret = XNEW (struct ebitmap_def); | |
| 202 if (size == 0) | |
| 203 size = EBITMAP_ELT_BITS; | |
| 204 ebitmap_array_init (ret, (size + EBITMAP_ELT_BITS - 1) / EBITMAP_ELT_BITS); | |
| 205 ret->wordmask = sbitmap_alloc_with_popcount (size); | |
| 206 sbitmap_zero (ret->wordmask); | |
| 207 ret->numwords = 0; | |
| 208 ret->cache = NULL; | |
| 209 ret->cacheindex = 0; | |
| 210 | |
| 211 return ret; | |
| 212 } | |
| 213 | |
| 214 /* Clear BIT from ebitmap MAP. */ | |
| 215 | |
| 216 void | |
| 217 ebitmap_clear_bit (ebitmap map, unsigned int bit) | |
| 218 { | |
| 219 unsigned int wordindex = bit / EBITMAP_ELT_BITS; | |
| 220 unsigned int eltwordindex = 0; | |
| 221 unsigned int bitindex, shift; | |
| 222 bool have_eltwordindex = false; | |
| 223 EBITMAP_ELT_TYPE *elt_ptr; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
224 |
| 0 | 225 /* If the bit can't exist in our bitmap, just return. */ |
| 226 if (map->numwords == 0) | |
| 227 return; | |
| 228 | |
| 229 if (wordindex >= map->wordmask->n_bits | |
| 230 || !TEST_BIT (map->wordmask, wordindex)) | |
| 231 return; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
232 |
| 0 | 233 if (map->cache != NULL && map->cacheindex == wordindex) |
| 234 elt_ptr = map->cache; | |
| 235 else | |
| 236 { | |
| 237 eltwordindex = sbitmap_popcount (map->wordmask, wordindex); | |
| 238 elt_ptr = &map->elts[eltwordindex]; | |
| 239 have_eltwordindex = true; | |
| 240 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
241 |
| 0 | 242 bitindex = bit % EBITMAP_ELT_BITS; |
| 243 shift = bitindex; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
244 |
| 0 | 245 *(elt_ptr) &= ~(((EBITMAP_ELT_TYPE)1) << shift); |
| 246 | |
| 247 /* Clear out the empty words. */ | |
| 248 if (*(elt_ptr) == 0) | |
| 249 { | |
| 250 if (!have_eltwordindex) | |
| 251 eltwordindex = sbitmap_popcount (map->wordmask, wordindex); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
252 |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
253 if (map->cache != NULL) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
254 { |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
255 if (map->cacheindex == wordindex) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
256 map->cache = NULL; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
257 else if (map->cacheindex > wordindex) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
258 map->cache = map->cache - 1; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
259 } |
| 0 | 260 |
| 261 RESET_BIT (map->wordmask, wordindex); | |
| 262 | |
| 263 memmove(&map->elts[eltwordindex], &map->elts[eltwordindex + 1], | |
| 264 sizeof (EBITMAP_ELT_TYPE) * (map->numwords - eltwordindex)); | |
| 265 map->numwords--; | |
| 266 } | |
| 267 } | |
| 268 | |
| 269 /* Set BIT in ebitmap MAP. */ | |
| 270 | |
| 271 void | |
| 272 ebitmap_set_bit (ebitmap map, unsigned int bit) | |
| 273 { | |
| 274 unsigned int wordindex = bit / EBITMAP_ELT_BITS; | |
| 275 unsigned int eltwordindex; | |
| 276 unsigned int bitindex = bit % EBITMAP_ELT_BITS; | |
| 277 | |
| 278 /* If we have this element cached, just set the bit in it. */ | |
| 279 if (map->cache && map->cacheindex == wordindex) | |
| 280 { | |
| 281 (*map->cache) |= (EBITMAP_ELT_TYPE)1 << bitindex; | |
| 282 return; | |
| 283 } | |
| 284 | |
| 285 /* Resize the wordmask if necessary. */ | |
| 286 if (wordindex >= map->wordmask->n_bits) | |
| 287 map->wordmask = sbitmap_resize (map->wordmask, wordindex + 1, 0); | |
| 288 | |
| 289 /* Allocate a new word in the array and move whatever is in it's | |
| 290 place, if necessary. */ | |
| 291 if (!TEST_BIT (map->wordmask, wordindex)) | |
| 292 { | |
| 293 unsigned long count; | |
| 294 unsigned int i; | |
| 295 | |
| 296 SET_BIT (map->wordmask, wordindex); | |
| 297 count = sbitmap_popcount (map->wordmask, wordindex); | |
| 298 gcc_assert (count <= map->numwords); | |
| 299 | |
| 300 for (i = map->numwords; i > count; i--) | |
| 301 { | |
| 302 EBITMAP_ELT_TYPE *newelt; | |
| 303 newelt = ebitmap_array_grow_get (map, i); | |
| 304 *newelt = ebitmap_array_get (map, i - 1); | |
| 305 } | |
| 306 map->numwords++; | |
| 307 eltwordindex = count; | |
| 308 ebitmap_array_maybe_grow (map, eltwordindex); | |
| 309 map->elts[eltwordindex] = 0; | |
| 310 } | |
| 311 else | |
| 312 { | |
| 313 eltwordindex = sbitmap_popcount (map->wordmask, wordindex); | |
| 314 } | |
| 315 | |
| 316 /* Set the actual bit. */ | |
| 317 bitindex = bit % EBITMAP_ELT_BITS; | |
| 318 | |
| 319 map->elts[eltwordindex] |= (EBITMAP_ELT_TYPE)1 << bitindex; | |
| 320 map->cache = &map->elts[eltwordindex]; | |
| 321 map->cacheindex = wordindex; | |
| 322 } | |
| 323 | |
| 324 | |
| 325 /* Return true if MAP contains BIT. */ | |
| 326 | |
| 327 bool | |
| 328 ebitmap_bit_p (ebitmap map, unsigned int bit) | |
| 329 { | |
| 330 unsigned int wordindex = bit / EBITMAP_ELT_BITS; | |
| 331 unsigned int bitindex= bit % EBITMAP_ELT_BITS; | |
| 332 | |
| 333 /* Trivial empty ebitmap case. */ | |
| 334 if (map->numwords == 0) | |
| 335 return false; | |
| 336 | |
| 337 if (map->cache && map->cacheindex == wordindex) | |
| 338 return ((*map->cache) >> bitindex) & 1; | |
| 339 | |
| 340 /* If the wordindex is greater than the size of the wordmask, *or* | |
| 341 it's not set in the wordmask, this bit can't exist in our | |
| 342 ebitmap. */ | |
| 343 if (wordindex >= map->wordmask->n_bits | |
| 344 || !TEST_BIT (map->wordmask, wordindex)) | |
| 345 return false; | |
| 346 | |
| 347 /* Find the bit and test it. */ | |
| 348 map->cacheindex = wordindex; | |
| 349 wordindex = sbitmap_popcount (map->wordmask, wordindex); | |
| 350 map->cache = &map->elts[wordindex]; | |
| 351 | |
| 352 return (map->elts[wordindex] >> bitindex) & 1; | |
| 353 } | |
| 354 | |
| 355 /* Copy ebitmap SRC to DST. */ | |
| 356 | |
| 357 void | |
| 358 ebitmap_copy (ebitmap dst, ebitmap src) | |
| 359 { | |
| 360 /* Blow away any existing wordmask, and copy the new one. */ | |
| 361 sbitmap_free (dst->wordmask); | |
| 362 dst->wordmask = sbitmap_alloc_with_popcount (src->wordmask->n_bits); | |
| 363 sbitmap_copy (dst->wordmask, src->wordmask); | |
| 364 | |
| 365 /* Make sure our destination array is big enough, and then copy the | |
| 366 actual words. */ | |
| 367 ebitmap_array_grow (dst, src->numwords); | |
| 368 memcpy (dst->elts, src->elts, | |
| 369 src->numwords * sizeof (EBITMAP_ELT_TYPE)); | |
| 370 dst->numwords = src->numwords; | |
| 371 dst->cache = NULL; | |
| 372 } | |
| 373 | |
| 374 /* Dump ebitmap BMAP to FILE. */ | |
| 375 | |
| 376 void | |
| 377 dump_ebitmap (FILE *file, ebitmap bmap) | |
| 378 { | |
| 379 unsigned int pos; | |
| 380 unsigned int i; | |
| 381 int res; | |
| 382 unsigned int size; | |
| 383 | |
| 384 res = sbitmap_last_set_bit (bmap->wordmask); | |
| 385 if (res == -1) | |
| 386 size = 0; | |
| 387 else | |
| 388 size = (res + 1) * EBITMAP_ELT_BITS; | |
| 389 | |
| 390 fprintf (file, "n_words = %d, set = {", bmap->numwords); | |
| 391 | |
| 392 for (pos = 30, i = 0; i < size; i++) | |
| 393 if (ebitmap_bit_p (bmap, i)) | |
| 394 { | |
| 395 if (pos > 70) | |
| 396 { | |
| 397 fprintf (file, "\n "); | |
| 398 pos = 0; | |
| 399 } | |
| 400 | |
| 401 pos += fprintf (file, "%d ", i); | |
| 402 } | |
| 403 | |
| 404 fprintf (file, "}\n"); | |
| 405 } | |
| 406 | |
| 407 /* Dump ebitmap BMAP to stderr. */ | |
| 408 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
409 DEBUG_FUNCTION void |
| 0 | 410 debug_ebitmap (ebitmap bmap) |
| 411 { | |
| 412 dump_ebitmap (stderr, bmap); | |
| 413 } | |
| 414 | |
| 415 /* Perform the operation DST &= SRC. */ | |
| 416 | |
| 417 void | |
| 418 ebitmap_and_into (ebitmap dst, ebitmap src) | |
| 419 { | |
| 420 sbitmap_iterator sbi; | |
| 421 unsigned int i; | |
| 422 unsigned int neweltindex = 0; | |
| 423 unsigned int dsteltindex = 0; | |
| 424 unsigned int srceltindex = 0; | |
| 425 | |
| 426 gcc_assert (dst != src); | |
| 427 | |
| 428 dst->cache = NULL; | |
| 429 | |
| 430 /* Short circuit the empty bitmap cases. */ | |
| 431 if (src->numwords == 0 || dst->numwords == 0) | |
| 432 { | |
| 433 ebitmap_clear (dst); | |
| 434 return; | |
| 435 } | |
| 436 | |
| 437 /* AND the masks, then walk the words that may actually appear in | |
| 438 the result, AND'ing them. */ | |
| 439 sbitmap_a_and_b (dst->wordmask, dst->wordmask, src->wordmask); | |
| 440 | |
| 441 EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi) | |
| 442 { | |
| 443 EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++); | |
| 444 tmpword &= ebitmap_array_get (dst, dsteltindex++); | |
| 445 if (tmpword != 0) | |
| 446 { | |
| 447 EBITMAP_ELT_TYPE *dstplace; | |
| 448 dstplace = ebitmap_array_grow_get (dst, neweltindex++); | |
| 449 *dstplace = tmpword; | |
| 450 } | |
| 451 else | |
| 452 RESET_BIT (dst->wordmask, i); | |
| 453 } | |
| 454 #ifdef EBITMAP_DEBUGGING | |
| 455 { | |
| 456 unsigned int i; | |
| 457 | |
| 458 for (i = 0; i < dst->numwords; i++) | |
| 459 gcc_assert (dst->elts[i] != 0); | |
| 460 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
461 sbitmap_verify_popcount (dst->wordmask); |
| 0 | 462 gcc_assert (sbitmap_popcount (dst->wordmask, |
| 463 dst->wordmask->n_bits) == dst->numwords); | |
| 464 } | |
| 465 #endif | |
| 466 dst->numwords = neweltindex; | |
| 467 } | |
| 468 | |
| 469 /* Perform the operation DST = SRC1 & SRC2. */ | |
| 470 | |
| 471 void | |
| 472 ebitmap_and (ebitmap dst, ebitmap src1, ebitmap src2) | |
| 473 { | |
| 474 sbitmap_iterator sbi; | |
| 475 unsigned int i; | |
| 476 unsigned int neweltindex = 0; | |
| 477 unsigned int src1eltindex = 0; | |
| 478 unsigned int src2eltindex = 0; | |
| 479 | |
| 480 dst->cache = NULL; | |
| 481 if (src1->numwords == 0 || src2->numwords == 0) | |
| 482 { | |
| 483 ebitmap_clear (dst); | |
| 484 return; | |
| 485 } | |
| 486 | |
| 487 dst->wordmask | |
| 488 = sbitmap_resize (dst->wordmask, | |
| 489 MIN (src1->wordmask->n_bits, src2->wordmask->n_bits), | |
| 490 0); | |
| 491 sbitmap_a_and_b (dst->wordmask, src1->wordmask, src2->wordmask); | |
| 492 | |
| 493 EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi) | |
| 494 { | |
| 495 bool src1hasword, src2hasword; | |
| 496 | |
| 497 src1hasword = TEST_BIT (src1->wordmask, i); | |
| 498 src2hasword = TEST_BIT (src2->wordmask, i); | |
| 499 | |
| 500 if (src1hasword && src2hasword) | |
| 501 { | |
| 502 EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src1, src1eltindex++); | |
| 503 tmpword &= ebitmap_array_get (src2, src2eltindex++); | |
| 504 if (tmpword != 0) | |
| 505 { | |
| 506 EBITMAP_ELT_TYPE *dstplace; | |
| 507 dstplace = ebitmap_array_grow_get (dst, neweltindex++); | |
| 508 *dstplace = tmpword; | |
| 509 } | |
| 510 else | |
| 511 RESET_BIT (dst->wordmask, i); | |
| 512 } | |
| 513 else if (src1hasword) | |
| 514 src1eltindex++; | |
| 515 else | |
| 516 src2eltindex++; | |
| 517 } | |
| 518 #ifdef EBITMAP_DEBUGGING | |
| 519 { | |
| 520 ebitmap_iterator ebi; | |
| 521 unsigned int i; | |
| 522 | |
| 523 for (i = 0; i < dst->numwords; i++) | |
| 524 gcc_assert (dst->elts[i] != 0); | |
| 525 | |
| 526 EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi) | |
| 527 if (ebitmap_bit_p (src2, i)) | |
| 528 gcc_assert (ebitmap_bit_p (dst, i)); | |
| 529 | |
| 530 for (i = 0; i < dst->numwords; i++) | |
| 531 gcc_assert (dst->elts[i] != 0); | |
| 532 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
533 sbitmap_verify_popcount (dst->wordmask); |
| 0 | 534 gcc_assert (sbitmap_popcount (dst->wordmask, |
| 535 dst->wordmask->n_bits) == dst->numwords); | |
| 536 } | |
| 537 #endif | |
| 538 dst->numwords = neweltindex; | |
| 539 } | |
| 540 | |
| 541 /* Perform the operation DST |= SRC. Return true if any bits in DST | |
| 542 changed. */ | |
| 543 | |
| 544 bool | |
| 545 ebitmap_ior_into (ebitmap dst, ebitmap src) | |
| 546 { | |
| 547 unsigned int dstsize = dst->wordmask->n_bits; | |
| 548 unsigned int srcsize = src->wordmask->n_bits; | |
| 549 sbitmap_iterator sbi; | |
| 550 unsigned int i; | |
| 551 sbitmap tempmask; | |
| 552 unsigned int neweltindex = 0; | |
| 553 unsigned int dsteltindex = 0; | |
| 554 unsigned int srceltindex = 0; | |
| 555 bool changed = false; | |
| 556 EBITMAP_ELT_TYPE *newarray; | |
| 557 unsigned int newarraysize; | |
| 558 #ifdef EBITMAP_DEBUGGING | |
| 559 ebitmap dstcopy = ebitmap_alloc (1); | |
| 560 ebitmap_copy (dstcopy, dst); | |
| 561 #endif | |
| 562 | |
| 563 dst->cache = NULL; | |
| 564 if (dst == src) | |
| 565 return false; | |
| 566 | |
| 567 if (dst->numwords == 0 && src->numwords != 0) | |
| 568 { | |
| 569 ebitmap_copy (dst, src); | |
| 570 return true; | |
| 571 } | |
| 572 else if (src->numwords == 0) | |
| 573 return false; | |
| 574 | |
| 575 /* We can do without the temp mask if it's faster, but it would mean | |
| 576 touching more words in the actual dense vector. */ | |
| 577 tempmask = sbitmap_alloc (MAX (srcsize, dstsize)); | |
| 578 sbitmap_zero (tempmask); | |
| 579 if (srcsize == dstsize) | |
| 580 { | |
| 581 sbitmap_a_or_b (tempmask, dst->wordmask, src->wordmask); | |
| 582 } | |
| 583 else | |
| 584 { | |
| 585 dst->wordmask = sbitmap_resize (dst->wordmask, MAX (srcsize, dstsize), | |
| 586 0); | |
| 587 if (srcsize >= dstsize) | |
| 588 { | |
| 589 sbitmap_copy_n (tempmask, dst->wordmask, dst->wordmask->size); | |
| 590 sbitmap_a_or_b (tempmask, tempmask, src->wordmask); | |
| 591 } | |
| 592 else | |
| 593 { | |
| 594 sbitmap_copy_n (tempmask, src->wordmask, src->wordmask->size); | |
| 595 sbitmap_a_or_b (tempmask, tempmask, dst->wordmask); | |
| 596 } | |
| 597 } | |
| 598 newarraysize = src->numwords + dst->numwords; | |
| 599 newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize); | |
| 600 | |
| 601 EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi) | |
| 602 { | |
| 603 bool dsthasword, srchasword; | |
| 604 | |
| 605 dsthasword = (i < dst->wordmask->n_bits | |
| 606 && TEST_BIT (dst->wordmask, i)); | |
| 607 srchasword = (i < src->wordmask->n_bits | |
| 608 && TEST_BIT (src->wordmask, i)); | |
| 609 | |
| 610 if (dsthasword && srchasword) | |
| 611 { | |
| 612 EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++); | |
| 613 tmpword |= ebitmap_array_get (dst, dsteltindex); | |
| 614 if (!changed) | |
| 615 changed |= tmpword != ebitmap_array_get (dst, dsteltindex); | |
| 616 dsteltindex++; | |
| 617 newarray[neweltindex++] = tmpword; | |
| 618 } | |
| 619 else if (dsthasword) | |
| 620 { | |
| 621 newarray [neweltindex++] = ebitmap_array_get (dst, dsteltindex++); | |
| 622 } | |
| 623 else | |
| 624 { | |
| 625 newarray [neweltindex++] = ebitmap_array_get (src, srceltindex++); | |
| 626 gcc_assert (i < dst->wordmask->n_bits); | |
| 627 SET_BIT (dst->wordmask, i); | |
| 628 changed |= true; | |
| 629 } | |
| 630 } | |
| 631 | |
| 632 sbitmap_free (tempmask); | |
| 633 if (changed) | |
| 634 { | |
| 635 dst->numwords = neweltindex; | |
| 636 free (dst->elts); | |
| 637 dst->elts = newarray; | |
| 638 dst->n_elts = newarraysize; | |
| 639 } | |
| 640 else | |
| 641 free (newarray); | |
| 642 | |
| 643 #ifdef EBITMAP_DEBUGGING | |
| 644 { | |
| 645 ebitmap_iterator ebi; | |
| 646 unsigned int i; | |
| 647 | |
| 648 for (i = 0; i < dst->numwords; i++) | |
| 649 gcc_assert (dst->elts[i] != 0); | |
| 650 | |
| 651 EXECUTE_IF_SET_IN_EBITMAP (src, 0, i, ebi) | |
| 652 gcc_assert (ebitmap_bit_p (dst, i)); | |
| 653 EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi) | |
| 654 gcc_assert (ebitmap_bit_p (dst, i)); | |
| 655 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
656 sbitmap_verify_popcount (dst->wordmask); |
| 0 | 657 gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy)); |
| 658 gcc_assert (sbitmap_popcount (dst->wordmask, | |
| 659 dst->wordmask->n_bits) == dst->numwords); | |
| 660 } | |
| 661 #endif | |
| 662 return changed; | |
| 663 } | |
| 664 | |
| 665 /* Perform the operation DST = SRC1 | SRC2. Return true if any bit | |
| 666 in DST has changed. */ | |
| 667 | |
| 668 bool | |
| 669 ebitmap_ior (ebitmap dst, ebitmap src1, ebitmap src2) | |
| 670 { | |
| 671 unsigned int src1size = src1->wordmask->n_bits; | |
| 672 unsigned int src2size = src2->wordmask->n_bits; | |
| 673 sbitmap_iterator sbi; | |
| 674 unsigned int i; | |
| 675 sbitmap tempmask; | |
| 676 unsigned int neweltindex = 0; | |
| 677 unsigned int src1eltindex = 0; | |
| 678 unsigned int src2eltindex = 0; | |
| 679 bool changed = false; | |
| 680 EBITMAP_ELT_TYPE *newarray; | |
| 681 unsigned int newarraysize; | |
| 682 #ifdef EBITMAP_DEBUGGING | |
| 683 ebitmap dstcopy = ebitmap_alloc (1); | |
| 684 ebitmap_copy (dstcopy, dst); | |
| 685 #endif | |
| 686 | |
| 687 dst->cache = NULL; | |
| 688 tempmask = sbitmap_alloc_with_popcount (MAX (src1size, src2size)); | |
| 689 sbitmap_zero (tempmask); | |
| 690 if (src1size == src2size) | |
| 691 { | |
| 692 sbitmap_a_or_b (tempmask, src1->wordmask, src2->wordmask); | |
| 693 } | |
| 694 else | |
| 695 { | |
| 696 if (src1size >= src2size) | |
| 697 { | |
| 698 sbitmap_copy_n (tempmask, src2->wordmask, src2->wordmask->size); | |
| 699 sbitmap_a_or_b (tempmask, tempmask, src1->wordmask); | |
| 700 } | |
| 701 else | |
| 702 { | |
| 703 sbitmap_copy_n (tempmask, src1->wordmask, src1->wordmask->size); | |
| 704 sbitmap_a_or_b (tempmask, tempmask, src2->wordmask); | |
| 705 } | |
| 706 } | |
| 707 newarraysize = src1->numwords + src2->numwords; | |
| 708 newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize); | |
| 709 | |
| 710 EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi) | |
| 711 { | |
| 712 bool src1hasword, src2hasword; | |
| 713 EBITMAP_ELT_TYPE tmpword; | |
| 714 src1hasword = (i < src1->wordmask->n_bits | |
| 715 && TEST_BIT (src1->wordmask, i)); | |
| 716 src2hasword = (i < src2->wordmask->n_bits | |
| 717 && TEST_BIT (src2->wordmask, i)); | |
| 718 | |
| 719 if (src1hasword && src2hasword) | |
| 720 { | |
| 721 tmpword = (ebitmap_array_get (src1, src1eltindex++) | |
| 722 | ebitmap_array_get (src2, src2eltindex++)); | |
| 723 newarray[neweltindex++] = tmpword; | |
| 724 } | |
| 725 else if (src1hasword) | |
| 726 { | |
| 727 tmpword = ebitmap_array_get (src1, src1eltindex++); | |
| 728 newarray [neweltindex++] = tmpword; | |
| 729 } | |
| 730 else | |
| 731 { | |
| 732 tmpword = ebitmap_array_get (src2, src2eltindex++); | |
| 733 newarray [neweltindex++] = tmpword; | |
| 734 } | |
| 735 | |
| 736 if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i)) | |
| 737 { | |
| 738 changed = true; | |
| 739 } | |
| 740 else if (!changed) | |
| 741 { | |
| 742 unsigned int count = sbitmap_popcount (dst->wordmask, i); | |
| 743 changed |= ebitmap_array_get (dst, count) != tmpword; | |
| 744 } | |
| 745 } | |
| 746 | |
| 747 if (changed) | |
| 748 { | |
| 749 sbitmap_free (dst->wordmask); | |
| 750 dst->wordmask = tempmask; | |
| 751 dst->numwords = neweltindex; | |
| 752 free (dst->elts); | |
| 753 dst->elts = newarray; | |
| 754 dst->n_elts = newarraysize; | |
| 755 } | |
| 756 else | |
| 757 { | |
| 758 sbitmap_free (tempmask); | |
| 759 free (newarray); | |
| 760 } | |
| 761 | |
| 762 #ifdef EBITMAP_DEBUGGING | |
| 763 { | |
| 764 ebitmap_iterator ebi; | |
| 765 unsigned int i; | |
| 766 | |
| 767 for (i = 0; i < dst->numwords; i++) | |
| 768 gcc_assert (dst->elts[i] != 0); | |
| 769 | |
| 770 EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi) | |
| 771 gcc_assert (ebitmap_bit_p (dst, i)); | |
| 772 | |
| 773 EXECUTE_IF_SET_IN_EBITMAP (src2, 0, i, ebi) | |
| 774 gcc_assert (ebitmap_bit_p (dst, i)); | |
| 775 } | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
776 sbitmap_verify_popcount (dst->wordmask); |
| 0 | 777 gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy)); |
| 778 gcc_assert (sbitmap_popcount (dst->wordmask, | |
| 779 dst->wordmask->n_bits) == dst->numwords); | |
| 780 #endif | |
| 781 | |
| 782 return changed; | |
| 783 } | |
| 784 | |
| 785 /* Perform the operation DST &= ~SRC. Return true if any bit in DST | |
| 786 has changed. */ | |
| 787 | |
| 788 bool | |
| 789 ebitmap_and_compl_into (ebitmap dst, ebitmap src) | |
| 790 { | |
| 791 bool changed = false; | |
| 792 unsigned int i; | |
| 793 unsigned int neweltindex = 0; | |
| 794 unsigned int dsteltindex = 0; | |
| 795 sbitmap_iterator sbi; | |
| 796 #ifdef EBITMAP_DEBUGGING | |
| 797 ebitmap dstcopy = ebitmap_alloc (1); | |
| 798 ebitmap_copy (dstcopy, dst); | |
| 799 #endif | |
| 800 | |
| 801 gcc_assert (dst != src); | |
| 802 dst->cache = NULL; | |
| 803 if (src->numwords == 0) | |
| 804 return false; | |
| 805 | |
| 806 EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi) | |
| 807 { | |
| 808 bool srchasword; | |
| 809 | |
| 810 srchasword = (i < src->wordmask->n_bits | |
| 811 && TEST_BIT (src->wordmask, i)); | |
| 812 | |
| 813 if (srchasword) | |
| 814 { | |
| 815 unsigned int srccount = sbitmap_popcount (src->wordmask, i); | |
| 816 EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (dst, dsteltindex); | |
| 817 tmpword &= ~(ebitmap_array_get (src, srccount)); | |
| 818 if (!changed) | |
| 819 changed |= ebitmap_array_get (dst, dsteltindex) != tmpword; | |
| 820 dsteltindex++; | |
| 821 if (tmpword != 0) | |
| 822 { | |
| 823 EBITMAP_ELT_TYPE *dstplace; | |
| 824 dstplace = ebitmap_array_grow_get (dst, neweltindex++); | |
| 825 *dstplace = tmpword; | |
| 826 } | |
| 827 else | |
| 828 RESET_BIT (dst->wordmask, i); | |
| 829 } | |
| 830 else | |
| 831 { | |
| 832 dsteltindex++; | |
| 833 neweltindex++; | |
| 834 } | |
| 835 } | |
| 836 #ifdef EBITMAP_DEBUGGING | |
| 837 { | |
| 838 unsigned int i; | |
| 839 ebitmap_iterator ebi; | |
| 840 | |
| 841 EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi) | |
| 842 { | |
| 843 if (!ebitmap_bit_p (src, i)) | |
| 844 gcc_assert (ebitmap_bit_p (dst, i)); | |
| 845 } | |
| 846 | |
| 847 for (i = 0; i < dst->numwords; i++) | |
| 848 gcc_assert (dst->elts[i] != 0); | |
| 849 | |
| 850 gcc_assert (sbitmap_popcount (dst->wordmask, | |
| 851 dst->wordmask->n_bits) == neweltindex); | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
852 sbitmap_verify_popcount (dst->wordmask); |
| 0 | 853 gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy)); |
| 854 gcc_assert (sbitmap_popcount (dst->wordmask, | |
| 855 dst->wordmask->n_bits) == dst->numwords); | |
| 856 } | |
| 857 #endif | |
| 858 dst->numwords = neweltindex; | |
| 859 /* sbitmap_popcount (dst->wordmask, -1); */ | |
| 860 | |
| 861 return changed; | |
| 862 } | |
| 863 | |
| 864 /* Perform the operation DST = SRC1 & ~SRC2. Return true if any bit | |
| 865 in DST has changed. */ | |
| 866 | |
| 867 bool | |
| 868 ebitmap_and_compl (ebitmap dst, ebitmap src1, ebitmap src2) | |
| 869 { | |
| 870 unsigned int src1size = src1->wordmask->n_bits; | |
| 871 sbitmap_iterator sbi; | |
| 872 unsigned int i; | |
| 873 sbitmap tempmask; | |
| 874 unsigned int neweltindex = 0; | |
| 875 unsigned int src1eltindex = 0; | |
| 876 bool changed = false; | |
| 877 EBITMAP_ELT_TYPE *newarray; | |
| 878 unsigned int newarraysize; | |
| 879 | |
| 880 /* XXX: Optimize like the into version. */ | |
| 881 dst->cache = NULL; | |
| 882 tempmask = sbitmap_alloc_with_popcount (src1size); | |
| 883 sbitmap_zero (tempmask); | |
| 884 sbitmap_copy (tempmask, src1->wordmask); | |
| 885 | |
| 886 newarraysize = src1->numwords; | |
| 887 newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize); | |
| 888 | |
| 889 EXECUTE_IF_SET_IN_SBITMAP (src1->wordmask, 0, i, sbi) | |
| 890 { | |
| 891 bool src2hasword; | |
| 892 EBITMAP_ELT_TYPE tmpword; | |
| 893 | |
| 894 src2hasword = (i < src2->wordmask->n_bits | |
| 895 && TEST_BIT (src2->wordmask, i)); | |
| 896 | |
| 897 if (src2hasword) | |
| 898 { | |
| 899 unsigned int src2count = sbitmap_popcount (src2->wordmask, i); | |
| 900 tmpword = ebitmap_array_get (src1, src1eltindex++) | |
| 901 & ~(ebitmap_array_get (src2, src2count)); | |
| 902 if (tmpword) | |
| 903 { | |
| 904 newarray[neweltindex++] = tmpword; | |
| 905 } | |
| 906 else | |
| 907 RESET_BIT (tempmask, i); | |
| 908 | |
| 909 } | |
| 910 else | |
| 911 { | |
| 912 tmpword = ebitmap_array_get (src1, src1eltindex++); | |
| 913 gcc_assert (tmpword != 0); | |
| 914 newarray[neweltindex++] = tmpword; | |
| 915 } | |
| 916 | |
| 917 if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i)) | |
| 918 { | |
| 919 changed = true; | |
| 920 } | |
| 921 else if (!changed) | |
| 922 { | |
| 923 unsigned int count = sbitmap_popcount (dst->wordmask, i); | |
| 924 changed |= ebitmap_array_get (dst, count) != tmpword; | |
| 925 } | |
| 926 } | |
| 927 if (changed) | |
| 928 { | |
| 929 sbitmap_free (dst->wordmask); | |
| 930 dst->wordmask = tempmask; | |
| 931 dst->numwords = neweltindex; | |
| 932 free (dst->elts); | |
| 933 dst->elts = newarray; | |
| 934 dst->n_elts = newarraysize; | |
| 935 } | |
| 936 else | |
| 937 { | |
| 938 free (tempmask); | |
| 939 free (newarray); | |
| 940 } | |
| 941 #ifdef EBITMAP_DEBUGGING | |
| 942 { | |
| 943 unsigned int i; | |
| 944 ebitmap_iterator ebi; | |
| 945 | |
| 946 EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi) | |
| 947 { | |
| 948 if (!ebitmap_bit_p (src2, i)) | |
| 949 gcc_assert (ebitmap_bit_p (dst, i)); | |
| 950 } | |
| 951 for (i = 0; i < dst->numwords; i++) | |
| 952 gcc_assert (dst->elts[i] != 0); | |
| 953 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
954 sbitmap_verify_popcount (dst->wordmask); |
| 0 | 955 gcc_assert (sbitmap_popcount (dst->wordmask, |
| 956 dst->wordmask->n_bits) == dst->numwords); | |
| 957 } | |
| 958 #endif | |
| 959 return changed; | |
| 960 } | |
| 961 | |
| 962 /* Perform the operation DST = A | (B & ~C). */ | |
| 963 | |
| 964 bool | |
| 965 ebitmap_ior_and_compl (ebitmap dst, ebitmap a, ebitmap b, ebitmap c) | |
| 966 { | |
| 967 bool changed; | |
| 968 ebitmap temp = ebitmap_alloc (1); | |
| 969 #ifdef EBITMAP_DEBUGGING | |
| 970 ebitmap dstcopy = ebitmap_alloc (1); | |
| 971 ebitmap_copy (dstcopy, dst); | |
| 972 #endif | |
| 973 | |
| 974 dst->cache = NULL; | |
| 975 ebitmap_and_compl (temp, b, c); | |
| 976 changed = ebitmap_ior (dst, a, temp); | |
| 977 #ifdef EBITMAP_DEBUGGING | |
| 978 { | |
| 979 ebitmap_iterator ebi; | |
| 980 unsigned int i; | |
| 981 | |
| 982 EXECUTE_IF_SET_IN_EBITMAP (a, 0, i, ebi) | |
| 983 gcc_assert (ebitmap_bit_p (dst, i)); | |
| 984 | |
| 985 EXECUTE_IF_SET_IN_EBITMAP (b, 0, i, ebi) | |
| 986 if (!ebitmap_bit_p (c, i)) | |
| 987 gcc_assert (ebitmap_bit_p (dst, i)); | |
| 988 gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy)); | |
| 989 } | |
| 990 #endif | |
| 991 ebitmap_free (temp); | |
| 992 | |
| 993 return changed; | |
| 994 } | |
| 995 | |
| 996 /* Return true if ebitmap DST is equal to ebitmap SRC. */ | |
| 997 | |
| 998 bool | |
| 999 ebitmap_equal_p (ebitmap dst, ebitmap src) | |
| 1000 { | |
| 1001 unsigned int which = MIN (dst->wordmask->size, src->wordmask->size); | |
| 1002 | |
| 1003 if (dst->numwords != src->numwords) | |
| 1004 return false; | |
| 1005 | |
| 1006 /* sbitmap_equal compares up to the size of the first argument, so | |
| 1007 if the two sbitmaps are not equally sized, we need to pass the | |
| 1008 smaller one as the first argument, or it will crash. */ | |
| 1009 if (which == dst->wordmask->size | |
| 1010 && !sbitmap_equal (dst->wordmask, src->wordmask)) | |
| 1011 return false; | |
| 1012 else if (which == src->wordmask->size | |
| 1013 && !sbitmap_equal (src->wordmask, dst->wordmask)) | |
| 1014 return false; | |
| 1015 | |
| 1016 return memcmp (dst->elts, src->elts, | |
| 1017 dst->numwords * sizeof (EBITMAP_ELT_TYPE)) == 0; | |
| 1018 return true; | |
| 1019 } |