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