Mercurial > hg > CbC > CbC_gcc
annotate gcc/bitmap.c @ 128:fe568345ddd5
fix CbC-example
| author | mir3636 |
|---|---|
| date | Wed, 11 Apr 2018 19:32:28 +0900 |
| parents | 04ced10e8804 |
| children | 84e7813d76e9 |
| rev | line source |
|---|---|
| 0 | 1 /* Functions to support general ended bitmaps. |
| 111 | 2 Copyright (C) 1997-2017 Free Software Foundation, Inc. |
| 0 | 3 |
| 4 This file is part of GCC. | |
| 5 | |
| 6 GCC is free software; you can redistribute it and/or modify it under | |
| 7 the terms of the GNU General Public License as published by the Free | |
| 8 Software Foundation; either version 3, or (at your option) any later | |
| 9 version. | |
| 10 | |
| 11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
| 12 WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 14 for more details. | |
| 15 | |
| 16 You should have received a copy of the GNU General Public License | |
| 17 along with GCC; see the file COPYING3. If not see | |
| 18 <http://www.gnu.org/licenses/>. */ | |
| 19 | |
| 20 #include "config.h" | |
| 21 #include "system.h" | |
| 22 #include "coretypes.h" | |
| 23 #include "bitmap.h" | |
| 111 | 24 #include "selftest.h" |
| 0 | 25 |
| 111 | 26 /* Memory allocation statistics purpose instance. */ |
| 27 mem_alloc_description<bitmap_usage> bitmap_mem_desc; | |
| 0 | 28 |
| 29 /* Register new bitmap. */ | |
| 30 void | |
| 31 bitmap_register (bitmap b MEM_STAT_DECL) | |
| 32 { | |
| 111 | 33 bitmap_mem_desc.register_descriptor (b, BITMAP_ORIGIN, false |
| 34 FINAL_PASS_MEM_STAT); | |
| 0 | 35 } |
| 36 | |
| 37 /* Account the overhead. */ | |
| 38 static void | |
| 111 | 39 register_overhead (bitmap b, size_t amount) |
| 0 | 40 { |
| 111 | 41 if (bitmap_mem_desc.contains_descriptor_for_instance (b)) |
| 42 bitmap_mem_desc.register_instance_overhead (amount, b); | |
| 0 | 43 } |
| 44 | |
| 45 /* Global data */ | |
| 46 bitmap_element bitmap_zero_bits; /* An element of all zero bits. */ | |
| 47 bitmap_obstack bitmap_default_obstack; /* The default bitmap obstack. */ | |
| 48 static int bitmap_default_obstack_depth; | |
| 49 static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of | |
| 50 GC'd elements. */ | |
| 51 | |
| 52 static void bitmap_elem_to_freelist (bitmap, bitmap_element *); | |
| 53 static void bitmap_element_free (bitmap, bitmap_element *); | |
| 54 static bitmap_element *bitmap_element_allocate (bitmap); | |
| 55 static int bitmap_element_zerop (const bitmap_element *); | |
| 56 static void bitmap_element_link (bitmap, bitmap_element *); | |
| 57 static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int); | |
| 58 static void bitmap_elt_clear_from (bitmap, bitmap_element *); | |
| 59 static bitmap_element *bitmap_find_bit (bitmap, unsigned int); | |
| 60 | |
| 61 | |
| 62 /* Add ELEM to the appropriate freelist. */ | |
| 63 static inline void | |
| 64 bitmap_elem_to_freelist (bitmap head, bitmap_element *elt) | |
| 65 { | |
| 66 bitmap_obstack *bit_obstack = head->obstack; | |
| 67 | |
| 68 elt->next = NULL; | |
| 111 | 69 elt->indx = -1; |
| 0 | 70 if (bit_obstack) |
| 71 { | |
| 72 elt->prev = bit_obstack->elements; | |
| 73 bit_obstack->elements = elt; | |
| 74 } | |
| 75 else | |
| 76 { | |
| 77 elt->prev = bitmap_ggc_free; | |
| 78 bitmap_ggc_free = elt; | |
| 79 } | |
| 80 } | |
| 81 | |
| 82 /* Free a bitmap element. Since these are allocated off the | |
| 83 bitmap_obstack, "free" actually means "put onto the freelist". */ | |
| 84 | |
| 85 static inline void | |
| 86 bitmap_element_free (bitmap head, bitmap_element *elt) | |
| 87 { | |
| 88 bitmap_element *next = elt->next; | |
| 89 bitmap_element *prev = elt->prev; | |
| 90 | |
| 91 if (prev) | |
| 92 prev->next = next; | |
| 93 | |
| 94 if (next) | |
| 95 next->prev = prev; | |
| 96 | |
| 97 if (head->first == elt) | |
| 98 head->first = next; | |
| 99 | |
| 100 /* Since the first thing we try is to insert before current, | |
| 101 make current the next entry in preference to the previous. */ | |
| 102 if (head->current == elt) | |
| 103 { | |
| 104 head->current = next != 0 ? next : prev; | |
| 105 if (head->current) | |
| 106 head->indx = head->current->indx; | |
| 107 else | |
| 108 head->indx = 0; | |
| 109 } | |
| 111 | 110 |
| 111 if (GATHER_STATISTICS) | |
| 112 register_overhead (head, -((int)sizeof (bitmap_element))); | |
| 113 | |
| 0 | 114 bitmap_elem_to_freelist (head, elt); |
| 115 } | |
| 116 | |
| 117 /* Allocate a bitmap element. The bits are cleared, but nothing else is. */ | |
| 118 | |
| 119 static inline bitmap_element * | |
| 120 bitmap_element_allocate (bitmap head) | |
| 121 { | |
| 122 bitmap_element *element; | |
| 123 bitmap_obstack *bit_obstack = head->obstack; | |
| 124 | |
| 125 if (bit_obstack) | |
| 126 { | |
| 127 element = bit_obstack->elements; | |
| 128 | |
| 129 if (element) | |
| 130 /* Use up the inner list first before looking at the next | |
| 131 element of the outer list. */ | |
| 132 if (element->next) | |
| 133 { | |
| 134 bit_obstack->elements = element->next; | |
| 135 bit_obstack->elements->prev = element->prev; | |
| 136 } | |
| 137 else | |
| 138 /* Inner list was just a singleton. */ | |
| 139 bit_obstack->elements = element->prev; | |
| 140 else | |
| 141 element = XOBNEW (&bit_obstack->obstack, bitmap_element); | |
| 142 } | |
| 143 else | |
| 144 { | |
| 145 element = bitmap_ggc_free; | |
| 146 if (element) | |
| 147 /* Use up the inner list first before looking at the next | |
| 148 element of the outer list. */ | |
| 149 if (element->next) | |
| 150 { | |
| 151 bitmap_ggc_free = element->next; | |
| 152 bitmap_ggc_free->prev = element->prev; | |
| 153 } | |
| 154 else | |
| 155 /* Inner list was just a singleton. */ | |
| 156 bitmap_ggc_free = element->prev; | |
| 157 else | |
| 111 | 158 element = ggc_alloc<bitmap_element> (); |
| 0 | 159 } |
| 160 | |
| 111 | 161 if (GATHER_STATISTICS) |
| 162 register_overhead (head, sizeof (bitmap_element)); | |
| 163 | |
| 0 | 164 memset (element->bits, 0, sizeof (element->bits)); |
| 165 | |
| 166 return element; | |
| 167 } | |
| 168 | |
| 169 /* Remove ELT and all following elements from bitmap HEAD. */ | |
| 170 | |
| 171 void | |
| 172 bitmap_elt_clear_from (bitmap head, bitmap_element *elt) | |
| 173 { | |
| 174 bitmap_element *prev; | |
| 175 bitmap_obstack *bit_obstack = head->obstack; | |
| 176 | |
| 177 if (!elt) return; | |
| 111 | 178 |
| 179 if (GATHER_STATISTICS) | |
| 180 { | |
| 181 int n = 0; | |
| 182 for (prev = elt; prev; prev = prev->next) | |
| 183 n++; | |
| 184 register_overhead (head, -sizeof (bitmap_element) * n); | |
| 185 } | |
| 0 | 186 |
| 187 prev = elt->prev; | |
| 188 if (prev) | |
| 189 { | |
| 190 prev->next = NULL; | |
| 191 if (head->current->indx > prev->indx) | |
| 192 { | |
| 193 head->current = prev; | |
| 194 head->indx = prev->indx; | |
| 195 } | |
| 196 } | |
| 197 else | |
| 198 { | |
| 199 head->first = NULL; | |
| 200 head->current = NULL; | |
| 201 head->indx = 0; | |
| 202 } | |
| 203 | |
| 204 /* Put the entire list onto the free list in one operation. */ | |
| 205 if (bit_obstack) | |
| 206 { | |
| 207 elt->prev = bit_obstack->elements; | |
| 208 bit_obstack->elements = elt; | |
| 209 } | |
| 210 else | |
| 211 { | |
| 212 elt->prev = bitmap_ggc_free; | |
| 213 bitmap_ggc_free = elt; | |
| 214 } | |
| 215 } | |
| 216 | |
| 217 /* Clear a bitmap by freeing the linked list. */ | |
| 218 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
219 void |
| 0 | 220 bitmap_clear (bitmap head) |
| 221 { | |
| 222 if (head->first) | |
| 223 bitmap_elt_clear_from (head, head->first); | |
| 224 } | |
| 225 | |
| 226 /* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize | |
| 227 the default bitmap obstack. */ | |
| 228 | |
| 229 void | |
| 230 bitmap_obstack_initialize (bitmap_obstack *bit_obstack) | |
| 231 { | |
| 232 if (!bit_obstack) | |
| 233 { | |
| 234 if (bitmap_default_obstack_depth++) | |
| 235 return; | |
| 236 bit_obstack = &bitmap_default_obstack; | |
| 237 } | |
| 238 | |
| 239 #if !defined(__GNUC__) || (__GNUC__ < 2) | |
| 240 #define __alignof__(type) 0 | |
| 241 #endif | |
| 242 | |
| 243 bit_obstack->elements = NULL; | |
| 244 bit_obstack->heads = NULL; | |
| 245 obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE, | |
| 246 __alignof__ (bitmap_element), | |
| 247 obstack_chunk_alloc, | |
| 248 obstack_chunk_free); | |
| 249 } | |
| 250 | |
| 251 /* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL, | |
| 252 release the default bitmap obstack. */ | |
| 253 | |
| 254 void | |
| 255 bitmap_obstack_release (bitmap_obstack *bit_obstack) | |
| 256 { | |
| 257 if (!bit_obstack) | |
| 258 { | |
| 259 if (--bitmap_default_obstack_depth) | |
| 260 { | |
| 261 gcc_assert (bitmap_default_obstack_depth > 0); | |
| 262 return; | |
| 263 } | |
| 264 bit_obstack = &bitmap_default_obstack; | |
| 265 } | |
| 266 | |
| 267 bit_obstack->elements = NULL; | |
| 268 bit_obstack->heads = NULL; | |
| 269 obstack_free (&bit_obstack->obstack, NULL); | |
| 270 } | |
| 271 | |
| 272 /* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create | |
| 273 it on the default bitmap obstack. */ | |
| 274 | |
| 275 bitmap | |
| 111 | 276 bitmap_alloc (bitmap_obstack *bit_obstack MEM_STAT_DECL) |
| 0 | 277 { |
| 278 bitmap map; | |
| 279 | |
| 280 if (!bit_obstack) | |
| 281 bit_obstack = &bitmap_default_obstack; | |
| 282 map = bit_obstack->heads; | |
| 283 if (map) | |
| 111 | 284 bit_obstack->heads = (struct bitmap_head *) map->first; |
| 0 | 285 else |
| 286 map = XOBNEW (&bit_obstack->obstack, bitmap_head); | |
| 111 | 287 bitmap_initialize (map, bit_obstack PASS_MEM_STAT); |
| 288 | |
| 289 if (GATHER_STATISTICS) | |
| 290 register_overhead (map, sizeof (bitmap_head)); | |
| 0 | 291 |
| 292 return map; | |
| 293 } | |
| 294 | |
| 295 /* Create a new GCd bitmap. */ | |
| 296 | |
| 297 bitmap | |
| 111 | 298 bitmap_gc_alloc (ALONE_MEM_STAT_DECL) |
| 0 | 299 { |
| 300 bitmap map; | |
| 301 | |
| 111 | 302 map = ggc_alloc<bitmap_head> (); |
| 303 bitmap_initialize (map, NULL PASS_MEM_STAT); | |
| 304 | |
| 305 if (GATHER_STATISTICS) | |
| 306 register_overhead (map, sizeof (bitmap_head)); | |
| 0 | 307 |
| 308 return map; | |
| 309 } | |
| 310 | |
| 311 /* Release an obstack allocated bitmap. */ | |
| 312 | |
| 313 void | |
| 314 bitmap_obstack_free (bitmap map) | |
| 315 { | |
| 316 if (map) | |
| 317 { | |
| 318 bitmap_clear (map); | |
| 319 map->first = (bitmap_element *) map->obstack->heads; | |
| 111 | 320 |
| 321 if (GATHER_STATISTICS) | |
| 322 register_overhead (map, -((int)sizeof (bitmap_head))); | |
| 323 | |
| 0 | 324 map->obstack->heads = map; |
| 325 } | |
| 326 } | |
| 327 | |
| 328 | |
| 329 /* Return nonzero if all bits in an element are zero. */ | |
| 330 | |
| 331 static inline int | |
| 332 bitmap_element_zerop (const bitmap_element *element) | |
| 333 { | |
| 334 #if BITMAP_ELEMENT_WORDS == 2 | |
| 335 return (element->bits[0] | element->bits[1]) == 0; | |
| 336 #else | |
| 337 unsigned i; | |
| 338 | |
| 339 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) | |
| 340 if (element->bits[i] != 0) | |
| 341 return 0; | |
| 342 | |
| 343 return 1; | |
| 344 #endif | |
| 345 } | |
| 346 | |
| 347 /* Link the bitmap element into the current bitmap linked list. */ | |
| 348 | |
| 349 static inline void | |
| 350 bitmap_element_link (bitmap head, bitmap_element *element) | |
| 351 { | |
| 352 unsigned int indx = element->indx; | |
| 353 bitmap_element *ptr; | |
| 354 | |
| 355 /* If this is the first and only element, set it in. */ | |
| 356 if (head->first == 0) | |
| 357 { | |
| 358 element->next = element->prev = 0; | |
| 359 head->first = element; | |
| 360 } | |
| 361 | |
| 362 /* If this index is less than that of the current element, it goes someplace | |
| 363 before the current element. */ | |
| 364 else if (indx < head->indx) | |
| 365 { | |
| 366 for (ptr = head->current; | |
| 367 ptr->prev != 0 && ptr->prev->indx > indx; | |
| 368 ptr = ptr->prev) | |
| 369 ; | |
| 370 | |
| 371 if (ptr->prev) | |
| 372 ptr->prev->next = element; | |
| 373 else | |
| 374 head->first = element; | |
| 375 | |
| 376 element->prev = ptr->prev; | |
| 377 element->next = ptr; | |
| 378 ptr->prev = element; | |
| 379 } | |
| 380 | |
| 381 /* Otherwise, it must go someplace after the current element. */ | |
| 382 else | |
| 383 { | |
| 384 for (ptr = head->current; | |
| 385 ptr->next != 0 && ptr->next->indx < indx; | |
| 386 ptr = ptr->next) | |
| 387 ; | |
| 388 | |
| 389 if (ptr->next) | |
| 390 ptr->next->prev = element; | |
| 391 | |
| 392 element->next = ptr->next; | |
| 393 element->prev = ptr; | |
| 394 ptr->next = element; | |
| 395 } | |
| 396 | |
| 397 /* Set up so this is the first element searched. */ | |
| 398 head->current = element; | |
| 399 head->indx = indx; | |
| 400 } | |
| 401 | |
| 402 /* Insert a new uninitialized element into bitmap HEAD after element | |
| 403 ELT. If ELT is NULL, insert the element at the start. Return the | |
| 404 new element. */ | |
| 405 | |
| 406 static bitmap_element * | |
| 407 bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx) | |
| 408 { | |
| 409 bitmap_element *node = bitmap_element_allocate (head); | |
| 410 node->indx = indx; | |
| 411 | |
| 412 if (!elt) | |
| 413 { | |
| 414 if (!head->current) | |
| 415 { | |
| 416 head->current = node; | |
| 417 head->indx = indx; | |
| 418 } | |
| 419 node->next = head->first; | |
| 420 if (node->next) | |
| 421 node->next->prev = node; | |
| 422 head->first = node; | |
| 423 node->prev = NULL; | |
| 424 } | |
| 425 else | |
| 426 { | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
427 gcc_checking_assert (head->current); |
| 0 | 428 node->next = elt->next; |
| 429 if (node->next) | |
| 430 node->next->prev = node; | |
| 431 elt->next = node; | |
| 432 node->prev = elt; | |
| 433 } | |
| 434 return node; | |
| 435 } | |
| 436 | |
| 437 /* Copy a bitmap to another bitmap. */ | |
| 438 | |
| 439 void | |
| 440 bitmap_copy (bitmap to, const_bitmap from) | |
| 441 { | |
| 442 const bitmap_element *from_ptr; | |
| 443 bitmap_element *to_ptr = 0; | |
| 444 | |
| 445 bitmap_clear (to); | |
| 446 | |
| 447 /* Copy elements in forward direction one at a time. */ | |
| 448 for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next) | |
| 449 { | |
| 450 bitmap_element *to_elt = bitmap_element_allocate (to); | |
| 451 | |
| 452 to_elt->indx = from_ptr->indx; | |
| 453 memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits)); | |
| 454 | |
| 455 /* Here we have a special case of bitmap_element_link, for the case | |
| 456 where we know the links are being entered in sequence. */ | |
| 457 if (to_ptr == 0) | |
| 458 { | |
| 459 to->first = to->current = to_elt; | |
| 460 to->indx = from_ptr->indx; | |
| 461 to_elt->next = to_elt->prev = 0; | |
| 462 } | |
| 463 else | |
| 464 { | |
| 465 to_elt->prev = to_ptr; | |
| 466 to_elt->next = 0; | |
| 467 to_ptr->next = to_elt; | |
| 468 } | |
| 469 | |
| 470 to_ptr = to_elt; | |
| 471 } | |
| 472 } | |
| 111 | 473 |
| 474 /* Move a bitmap to another bitmap. */ | |
| 475 | |
| 476 void | |
| 477 bitmap_move (bitmap to, bitmap from) | |
| 478 { | |
| 479 gcc_assert (to->obstack == from->obstack); | |
| 480 | |
| 481 bitmap_clear (to); | |
| 482 | |
| 483 *to = *from; | |
| 484 | |
| 485 if (GATHER_STATISTICS) | |
| 486 { | |
| 487 size_t sz = 0; | |
| 488 for (bitmap_element *e = to->first; e; e = e->next) | |
| 489 sz += sizeof (bitmap_element); | |
| 490 register_overhead (to, sz); | |
| 491 register_overhead (from, -sz); | |
| 492 } | |
| 493 } | |
| 0 | 494 |
| 495 /* Find a bitmap element that would hold a bitmap's bit. | |
| 496 Update the `current' field even if we can't find an element that | |
| 497 would hold the bitmap's bit to make eventual allocation | |
| 498 faster. */ | |
| 499 | |
| 500 static inline bitmap_element * | |
| 501 bitmap_find_bit (bitmap head, unsigned int bit) | |
| 502 { | |
| 503 bitmap_element *element; | |
| 504 unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS; | |
| 505 | |
| 111 | 506 if (head->current == NULL |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
507 || head->indx == indx) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
508 return head->current; |
| 111 | 509 if (head->current == head->first |
| 510 && head->first->next == NULL) | |
| 511 return NULL; | |
| 512 | |
| 513 /* Usage can be NULL due to allocated bitmaps for which we do not | |
| 514 call initialize function. */ | |
| 515 bitmap_usage *usage = NULL; | |
| 516 if (GATHER_STATISTICS) | |
| 517 usage = bitmap_mem_desc.get_descriptor_for_instance (head); | |
| 518 | |
| 519 /* This bitmap has more than one element, and we're going to look | |
| 520 through the elements list. Count that as a search. */ | |
| 521 if (GATHER_STATISTICS && usage) | |
| 522 usage->m_nsearches++; | |
| 0 | 523 |
| 524 if (head->indx < indx) | |
| 525 /* INDX is beyond head->indx. Search from head->current | |
| 526 forward. */ | |
| 527 for (element = head->current; | |
| 528 element->next != 0 && element->indx < indx; | |
| 529 element = element->next) | |
| 111 | 530 { |
| 531 if (GATHER_STATISTICS && usage) | |
| 532 usage->m_search_iter++; | |
| 533 } | |
| 0 | 534 |
| 535 else if (head->indx / 2 < indx) | |
| 536 /* INDX is less than head->indx and closer to head->indx than to | |
| 537 0. Search from head->current backward. */ | |
| 538 for (element = head->current; | |
| 539 element->prev != 0 && element->indx > indx; | |
| 540 element = element->prev) | |
| 111 | 541 { |
| 542 if (GATHER_STATISTICS && usage) | |
| 543 usage->m_search_iter++; | |
| 544 } | |
| 0 | 545 |
| 546 else | |
| 547 /* INDX is less than head->indx and closer to 0 than to | |
| 548 head->indx. Search from head->first forward. */ | |
| 549 for (element = head->first; | |
| 550 element->next != 0 && element->indx < indx; | |
| 551 element = element->next) | |
| 111 | 552 if (GATHER_STATISTICS && usage) |
| 553 { | |
| 554 usage->m_search_iter++; | |
| 555 } | |
| 0 | 556 |
| 557 /* `element' is the nearest to the one we want. If it's not the one we | |
| 558 want, the one we want doesn't exist. */ | |
| 559 head->current = element; | |
| 560 head->indx = element->indx; | |
| 111 | 561 if (element->indx != indx) |
| 0 | 562 element = 0; |
| 563 | |
| 564 return element; | |
| 565 } | |
| 566 | |
| 567 /* Clear a single bit in a bitmap. Return true if the bit changed. */ | |
| 568 | |
| 569 bool | |
| 570 bitmap_clear_bit (bitmap head, int bit) | |
| 571 { | |
| 572 bitmap_element *const ptr = bitmap_find_bit (head, bit); | |
| 573 | |
| 574 if (ptr != 0) | |
| 575 { | |
| 576 unsigned bit_num = bit % BITMAP_WORD_BITS; | |
| 577 unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; | |
| 578 BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num; | |
| 579 bool res = (ptr->bits[word_num] & bit_val) != 0; | |
| 580 if (res) | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
581 { |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
582 ptr->bits[word_num] &= ~bit_val; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
583 /* If we cleared the entire word, free up the element. */ |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
584 if (!ptr->bits[word_num] |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
585 && bitmap_element_zerop (ptr)) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
586 bitmap_element_free (head, ptr); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
587 } |
| 0 | 588 |
| 589 return res; | |
| 590 } | |
| 591 | |
| 592 return false; | |
| 593 } | |
| 594 | |
| 595 /* Set a single bit in a bitmap. Return true if the bit changed. */ | |
| 596 | |
| 597 bool | |
| 598 bitmap_set_bit (bitmap head, int bit) | |
| 599 { | |
| 600 bitmap_element *ptr = bitmap_find_bit (head, bit); | |
| 601 unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; | |
| 602 unsigned bit_num = bit % BITMAP_WORD_BITS; | |
| 603 BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num; | |
| 604 | |
| 605 if (ptr == 0) | |
| 606 { | |
| 607 ptr = bitmap_element_allocate (head); | |
| 608 ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS; | |
| 609 ptr->bits[word_num] = bit_val; | |
| 610 bitmap_element_link (head, ptr); | |
| 611 return true; | |
| 612 } | |
| 613 else | |
| 614 { | |
| 615 bool res = (ptr->bits[word_num] & bit_val) == 0; | |
| 616 if (res) | |
| 617 ptr->bits[word_num] |= bit_val; | |
| 618 return res; | |
| 619 } | |
| 620 } | |
| 621 | |
| 622 /* Return whether a bit is set within a bitmap. */ | |
| 623 | |
| 624 int | |
| 625 bitmap_bit_p (bitmap head, int bit) | |
| 626 { | |
| 627 bitmap_element *ptr; | |
| 628 unsigned bit_num; | |
| 629 unsigned word_num; | |
| 630 | |
| 631 ptr = bitmap_find_bit (head, bit); | |
| 632 if (ptr == 0) | |
| 633 return 0; | |
| 634 | |
| 635 bit_num = bit % BITMAP_WORD_BITS; | |
| 636 word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; | |
| 637 | |
| 638 return (ptr->bits[word_num] >> bit_num) & 1; | |
| 639 } | |
| 640 | |
| 641 #if GCC_VERSION < 3400 | |
| 642 /* Table of number of set bits in a character, indexed by value of char. */ | |
| 643 static const unsigned char popcount_table[] = | |
| 644 { | |
| 645 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5, | |
| 646 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, | |
| 647 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, | |
| 648 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, | |
| 649 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, | |
| 650 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, | |
| 651 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, | |
| 652 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8, | |
| 653 }; | |
| 654 | |
| 655 static unsigned long | |
| 656 bitmap_popcount (BITMAP_WORD a) | |
| 657 { | |
| 658 unsigned long ret = 0; | |
| 659 unsigned i; | |
| 660 | |
| 661 /* Just do this the table way for now */ | |
| 662 for (i = 0; i < BITMAP_WORD_BITS; i+= 8) | |
| 663 ret += popcount_table[(a >> i) & 0xff]; | |
| 664 return ret; | |
| 665 } | |
| 666 #endif | |
| 111 | 667 |
| 668 /* Count and return the number of bits set in the bitmap word BITS. */ | |
| 669 static unsigned long | |
| 670 bitmap_count_bits_in_word (const BITMAP_WORD *bits) | |
| 671 { | |
| 672 unsigned long count = 0; | |
| 673 | |
| 674 for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | |
| 675 { | |
| 676 #if GCC_VERSION >= 3400 | |
| 677 /* Note that popcountl matches BITMAP_WORD in type, so the actual size | |
| 678 of BITMAP_WORD is not material. */ | |
| 679 count += __builtin_popcountl (bits[ix]); | |
| 680 #else | |
| 681 count += bitmap_popcount (bits[ix]); | |
| 682 #endif | |
| 683 } | |
| 684 return count; | |
| 685 } | |
| 686 | |
| 0 | 687 /* Count the number of bits set in the bitmap, and return it. */ |
| 688 | |
| 689 unsigned long | |
| 690 bitmap_count_bits (const_bitmap a) | |
| 691 { | |
| 692 unsigned long count = 0; | |
| 693 const bitmap_element *elt; | |
| 694 | |
| 695 for (elt = a->first; elt; elt = elt->next) | |
| 111 | 696 count += bitmap_count_bits_in_word (elt->bits); |
| 697 | |
| 698 return count; | |
| 699 } | |
| 700 | |
| 701 /* Count the number of unique bits set in A and B and return it. */ | |
| 702 | |
| 703 unsigned long | |
| 704 bitmap_count_unique_bits (const_bitmap a, const_bitmap b) | |
| 705 { | |
| 706 unsigned long count = 0; | |
| 707 const bitmap_element *elt_a, *elt_b; | |
| 708 | |
| 709 for (elt_a = a->first, elt_b = b->first; elt_a && elt_b; ) | |
| 0 | 710 { |
| 111 | 711 /* If we're at different indices, then count all the bits |
| 712 in the lower element. If we're at the same index, then | |
| 713 count the bits in the IOR of the two elements. */ | |
| 714 if (elt_a->indx < elt_b->indx) | |
| 0 | 715 { |
| 111 | 716 count += bitmap_count_bits_in_word (elt_a->bits); |
| 717 elt_a = elt_a->next; | |
| 718 } | |
| 719 else if (elt_b->indx < elt_a->indx) | |
| 720 { | |
| 721 count += bitmap_count_bits_in_word (elt_b->bits); | |
| 722 elt_b = elt_b->next; | |
| 723 } | |
| 724 else | |
| 725 { | |
| 726 BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; | |
| 727 for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | |
| 728 bits[ix] = elt_a->bits[ix] | elt_b->bits[ix]; | |
| 729 count += bitmap_count_bits_in_word (bits); | |
| 730 elt_a = elt_a->next; | |
| 731 elt_b = elt_b->next; | |
| 0 | 732 } |
| 733 } | |
| 734 return count; | |
| 735 } | |
| 736 | |
| 737 /* Return true if the bitmap has a single bit set. Otherwise return | |
| 738 false. */ | |
| 739 | |
| 740 bool | |
| 741 bitmap_single_bit_set_p (const_bitmap a) | |
| 742 { | |
| 743 unsigned long count = 0; | |
| 744 const bitmap_element *elt; | |
| 745 unsigned ix; | |
| 746 | |
| 747 if (bitmap_empty_p (a)) | |
| 748 return false; | |
| 749 | |
| 750 elt = a->first; | |
| 751 /* As there are no completely empty bitmap elements, a second one | |
| 752 means we have more than one bit set. */ | |
| 753 if (elt->next != NULL) | |
| 754 return false; | |
| 755 | |
| 756 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | |
| 757 { | |
| 758 #if GCC_VERSION >= 3400 | |
| 759 /* Note that popcountl matches BITMAP_WORD in type, so the actual size | |
| 760 of BITMAP_WORD is not material. */ | |
| 761 count += __builtin_popcountl (elt->bits[ix]); | |
| 762 #else | |
| 763 count += bitmap_popcount (elt->bits[ix]); | |
| 764 #endif | |
| 765 if (count > 1) | |
| 766 return false; | |
| 767 } | |
| 768 | |
| 769 return count == 1; | |
| 770 } | |
| 771 | |
| 772 | |
| 773 /* Return the bit number of the first set bit in the bitmap. The | |
| 774 bitmap must be non-empty. */ | |
| 775 | |
| 776 unsigned | |
| 777 bitmap_first_set_bit (const_bitmap a) | |
| 778 { | |
| 779 const bitmap_element *elt = a->first; | |
| 780 unsigned bit_no; | |
| 781 BITMAP_WORD word; | |
| 782 unsigned ix; | |
| 783 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
784 gcc_checking_assert (elt); |
| 0 | 785 bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS; |
| 786 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | |
| 787 { | |
| 788 word = elt->bits[ix]; | |
| 789 if (word) | |
| 790 goto found_bit; | |
| 791 } | |
| 792 gcc_unreachable (); | |
| 793 found_bit: | |
| 794 bit_no += ix * BITMAP_WORD_BITS; | |
| 795 | |
| 796 #if GCC_VERSION >= 3004 | |
| 111 | 797 gcc_assert (sizeof (long) == sizeof (word)); |
| 0 | 798 bit_no += __builtin_ctzl (word); |
| 799 #else | |
| 800 /* Binary search for the first set bit. */ | |
| 801 #if BITMAP_WORD_BITS > 64 | |
| 802 #error "Fill out the table." | |
| 803 #endif | |
| 804 #if BITMAP_WORD_BITS > 32 | |
| 805 if (!(word & 0xffffffff)) | |
| 806 word >>= 32, bit_no += 32; | |
| 807 #endif | |
| 808 if (!(word & 0xffff)) | |
| 809 word >>= 16, bit_no += 16; | |
| 810 if (!(word & 0xff)) | |
| 811 word >>= 8, bit_no += 8; | |
| 812 if (!(word & 0xf)) | |
| 813 word >>= 4, bit_no += 4; | |
| 814 if (!(word & 0x3)) | |
| 815 word >>= 2, bit_no += 2; | |
| 816 if (!(word & 0x1)) | |
| 817 word >>= 1, bit_no += 1; | |
| 818 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
819 gcc_checking_assert (word & 1); |
| 0 | 820 #endif |
| 821 return bit_no; | |
| 822 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
823 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
824 /* Return the bit number of the first set bit in the bitmap. The |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
825 bitmap must be non-empty. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
826 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
827 unsigned |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
828 bitmap_last_set_bit (const_bitmap a) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
829 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
830 const bitmap_element *elt = a->current ? a->current : a->first; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
831 unsigned bit_no; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
832 BITMAP_WORD word; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
833 int ix; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
834 |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
835 gcc_checking_assert (elt); |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
836 while (elt->next) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
837 elt = elt->next; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
838 bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
839 for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 0; ix--) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
840 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
841 word = elt->bits[ix]; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
842 if (word) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
843 goto found_bit; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
844 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
845 gcc_unreachable (); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
846 found_bit: |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
847 bit_no += ix * BITMAP_WORD_BITS; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
848 #if GCC_VERSION >= 3004 |
| 111 | 849 gcc_assert (sizeof (long) == sizeof (word)); |
| 850 bit_no += BITMAP_WORD_BITS - __builtin_clzl (word) - 1; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
851 #else |
| 111 | 852 /* Hopefully this is a twos-complement host... */ |
| 853 BITMAP_WORD x = word; | |
| 854 x |= (x >> 1); | |
| 855 x |= (x >> 2); | |
| 856 x |= (x >> 4); | |
| 857 x |= (x >> 8); | |
| 858 x |= (x >> 16); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
859 #if BITMAP_WORD_BITS > 32 |
| 111 | 860 x |= (x >> 32); |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
861 #endif |
| 111 | 862 bit_no += bitmap_popcount (x) - 1; |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
863 #endif |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
864 |
| 111 | 865 return bit_no; |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
866 } |
| 0 | 867 |
| 868 | |
| 869 /* DST = A & B. */ | |
| 870 | |
| 871 void | |
| 872 bitmap_and (bitmap dst, const_bitmap a, const_bitmap b) | |
| 873 { | |
| 874 bitmap_element *dst_elt = dst->first; | |
| 875 const bitmap_element *a_elt = a->first; | |
| 876 const bitmap_element *b_elt = b->first; | |
| 877 bitmap_element *dst_prev = NULL; | |
| 878 | |
| 879 gcc_assert (dst != a && dst != b); | |
| 880 | |
| 881 if (a == b) | |
| 882 { | |
| 883 bitmap_copy (dst, a); | |
| 884 return; | |
| 885 } | |
| 886 | |
| 887 while (a_elt && b_elt) | |
| 888 { | |
| 889 if (a_elt->indx < b_elt->indx) | |
| 890 a_elt = a_elt->next; | |
| 891 else if (b_elt->indx < a_elt->indx) | |
| 892 b_elt = b_elt->next; | |
| 893 else | |
| 894 { | |
| 895 /* Matching elts, generate A & B. */ | |
| 896 unsigned ix; | |
| 897 BITMAP_WORD ior = 0; | |
| 898 | |
| 899 if (!dst_elt) | |
| 900 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); | |
| 901 else | |
| 902 dst_elt->indx = a_elt->indx; | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
903 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
| 0 | 904 { |
| 905 BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix]; | |
| 906 | |
| 907 dst_elt->bits[ix] = r; | |
| 908 ior |= r; | |
| 909 } | |
| 910 if (ior) | |
| 911 { | |
| 912 dst_prev = dst_elt; | |
| 913 dst_elt = dst_elt->next; | |
| 914 } | |
| 915 a_elt = a_elt->next; | |
| 916 b_elt = b_elt->next; | |
| 917 } | |
| 918 } | |
| 919 /* Ensure that dst->current is valid. */ | |
| 920 dst->current = dst->first; | |
| 921 bitmap_elt_clear_from (dst, dst_elt); | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
922 gcc_checking_assert (!dst->current == !dst->first); |
| 0 | 923 if (dst->current) |
| 924 dst->indx = dst->current->indx; | |
| 925 } | |
| 926 | |
| 111 | 927 /* A &= B. Return true if A changed. */ |
| 0 | 928 |
| 111 | 929 bool |
| 0 | 930 bitmap_and_into (bitmap a, const_bitmap b) |
| 931 { | |
| 932 bitmap_element *a_elt = a->first; | |
| 933 const bitmap_element *b_elt = b->first; | |
| 934 bitmap_element *next; | |
| 111 | 935 bool changed = false; |
| 0 | 936 |
| 937 if (a == b) | |
| 111 | 938 return false; |
| 0 | 939 |
| 940 while (a_elt && b_elt) | |
| 941 { | |
| 942 if (a_elt->indx < b_elt->indx) | |
| 943 { | |
| 944 next = a_elt->next; | |
| 945 bitmap_element_free (a, a_elt); | |
| 946 a_elt = next; | |
| 111 | 947 changed = true; |
| 0 | 948 } |
| 949 else if (b_elt->indx < a_elt->indx) | |
| 950 b_elt = b_elt->next; | |
| 951 else | |
| 952 { | |
| 953 /* Matching elts, generate A &= B. */ | |
| 954 unsigned ix; | |
| 955 BITMAP_WORD ior = 0; | |
| 956 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
957 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
| 0 | 958 { |
| 959 BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix]; | |
| 111 | 960 if (a_elt->bits[ix] != r) |
| 961 changed = true; | |
| 0 | 962 a_elt->bits[ix] = r; |
| 963 ior |= r; | |
| 964 } | |
| 965 next = a_elt->next; | |
| 966 if (!ior) | |
| 967 bitmap_element_free (a, a_elt); | |
| 968 a_elt = next; | |
| 969 b_elt = b_elt->next; | |
| 970 } | |
| 971 } | |
| 111 | 972 |
| 973 if (a_elt) | |
| 974 { | |
| 975 changed = true; | |
| 976 bitmap_elt_clear_from (a, a_elt); | |
| 977 } | |
| 978 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
979 gcc_checking_assert (!a->current == !a->first |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
980 && (!a->current || a->indx == a->current->indx)); |
| 111 | 981 |
| 982 return changed; | |
| 0 | 983 } |
| 984 | |
| 985 | |
| 986 /* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT | |
| 987 if non-NULL. CHANGED is true if the destination bitmap had already been | |
| 988 changed; the new value of CHANGED is returned. */ | |
| 989 | |
| 990 static inline bool | |
| 991 bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev, | |
| 992 const bitmap_element *src_elt, bool changed) | |
| 993 { | |
| 994 if (!changed && dst_elt && dst_elt->indx == src_elt->indx) | |
| 995 { | |
| 996 unsigned ix; | |
| 997 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
998 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
| 0 | 999 if (src_elt->bits[ix] != dst_elt->bits[ix]) |
| 1000 { | |
| 1001 dst_elt->bits[ix] = src_elt->bits[ix]; | |
| 1002 changed = true; | |
| 1003 } | |
| 1004 } | |
| 1005 else | |
| 1006 { | |
| 1007 changed = true; | |
| 1008 if (!dst_elt) | |
| 1009 dst_elt = bitmap_elt_insert_after (dst, dst_prev, src_elt->indx); | |
| 1010 else | |
| 1011 dst_elt->indx = src_elt->indx; | |
| 1012 memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits)); | |
| 1013 } | |
| 1014 return changed; | |
| 1015 } | |
| 1016 | |
| 1017 | |
| 1018 | |
| 1019 /* DST = A & ~B */ | |
| 1020 | |
| 1021 bool | |
| 1022 bitmap_and_compl (bitmap dst, const_bitmap a, const_bitmap b) | |
| 1023 { | |
| 1024 bitmap_element *dst_elt = dst->first; | |
| 1025 const bitmap_element *a_elt = a->first; | |
| 1026 const bitmap_element *b_elt = b->first; | |
| 1027 bitmap_element *dst_prev = NULL; | |
| 1028 bitmap_element **dst_prev_pnext = &dst->first; | |
| 1029 bool changed = false; | |
| 1030 | |
| 1031 gcc_assert (dst != a && dst != b); | |
| 1032 | |
| 1033 if (a == b) | |
| 1034 { | |
| 1035 changed = !bitmap_empty_p (dst); | |
| 1036 bitmap_clear (dst); | |
| 1037 return changed; | |
| 1038 } | |
| 1039 | |
| 1040 while (a_elt) | |
| 1041 { | |
| 1042 while (b_elt && b_elt->indx < a_elt->indx) | |
| 1043 b_elt = b_elt->next; | |
| 1044 | |
| 1045 if (!b_elt || b_elt->indx > a_elt->indx) | |
| 1046 { | |
| 1047 changed = bitmap_elt_copy (dst, dst_elt, dst_prev, a_elt, changed); | |
| 1048 dst_prev = *dst_prev_pnext; | |
| 1049 dst_prev_pnext = &dst_prev->next; | |
| 1050 dst_elt = *dst_prev_pnext; | |
| 1051 a_elt = a_elt->next; | |
| 1052 } | |
| 1053 | |
| 1054 else | |
| 1055 { | |
| 1056 /* Matching elts, generate A & ~B. */ | |
| 1057 unsigned ix; | |
| 1058 BITMAP_WORD ior = 0; | |
| 1059 | |
| 1060 if (!changed && dst_elt && dst_elt->indx == a_elt->indx) | |
| 1061 { | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1062 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
| 0 | 1063 { |
| 1064 BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix]; | |
| 1065 | |
| 1066 if (dst_elt->bits[ix] != r) | |
| 1067 { | |
| 1068 changed = true; | |
| 1069 dst_elt->bits[ix] = r; | |
| 1070 } | |
| 1071 ior |= r; | |
| 1072 } | |
| 1073 } | |
| 1074 else | |
| 1075 { | |
| 1076 bool new_element; | |
| 1077 if (!dst_elt || dst_elt->indx > a_elt->indx) | |
| 1078 { | |
| 1079 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); | |
| 1080 new_element = true; | |
| 1081 } | |
| 1082 else | |
| 1083 { | |
| 1084 dst_elt->indx = a_elt->indx; | |
| 1085 new_element = false; | |
| 1086 } | |
| 1087 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1088 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
| 0 | 1089 { |
| 1090 BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix]; | |
| 1091 | |
| 1092 dst_elt->bits[ix] = r; | |
| 1093 ior |= r; | |
| 1094 } | |
| 1095 | |
| 1096 if (ior) | |
| 1097 changed = true; | |
| 1098 else | |
| 1099 { | |
| 1100 changed |= !new_element; | |
| 1101 bitmap_element_free (dst, dst_elt); | |
| 1102 dst_elt = *dst_prev_pnext; | |
| 1103 } | |
| 1104 } | |
| 1105 | |
| 1106 if (ior) | |
| 1107 { | |
| 1108 dst_prev = *dst_prev_pnext; | |
| 1109 dst_prev_pnext = &dst_prev->next; | |
| 1110 dst_elt = *dst_prev_pnext; | |
| 1111 } | |
| 1112 a_elt = a_elt->next; | |
| 1113 b_elt = b_elt->next; | |
| 1114 } | |
| 1115 } | |
| 1116 | |
| 1117 /* Ensure that dst->current is valid. */ | |
| 1118 dst->current = dst->first; | |
| 1119 | |
| 1120 if (dst_elt) | |
| 1121 { | |
| 1122 changed = true; | |
| 1123 bitmap_elt_clear_from (dst, dst_elt); | |
| 1124 } | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1125 gcc_checking_assert (!dst->current == !dst->first); |
| 0 | 1126 if (dst->current) |
| 1127 dst->indx = dst->current->indx; | |
| 1128 | |
| 1129 return changed; | |
| 1130 } | |
| 1131 | |
| 1132 /* A &= ~B. Returns true if A changes */ | |
| 1133 | |
| 1134 bool | |
| 1135 bitmap_and_compl_into (bitmap a, const_bitmap b) | |
| 1136 { | |
| 1137 bitmap_element *a_elt = a->first; | |
| 1138 const bitmap_element *b_elt = b->first; | |
| 1139 bitmap_element *next; | |
| 1140 BITMAP_WORD changed = 0; | |
| 1141 | |
| 1142 if (a == b) | |
| 1143 { | |
| 1144 if (bitmap_empty_p (a)) | |
| 1145 return false; | |
| 1146 else | |
| 1147 { | |
| 1148 bitmap_clear (a); | |
| 1149 return true; | |
| 1150 } | |
| 1151 } | |
| 1152 | |
| 1153 while (a_elt && b_elt) | |
| 1154 { | |
| 1155 if (a_elt->indx < b_elt->indx) | |
| 1156 a_elt = a_elt->next; | |
| 1157 else if (b_elt->indx < a_elt->indx) | |
| 1158 b_elt = b_elt->next; | |
| 1159 else | |
| 1160 { | |
| 1161 /* Matching elts, generate A &= ~B. */ | |
| 1162 unsigned ix; | |
| 1163 BITMAP_WORD ior = 0; | |
| 1164 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1165 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
| 0 | 1166 { |
| 1167 BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix]; | |
| 1168 BITMAP_WORD r = a_elt->bits[ix] ^ cleared; | |
| 1169 | |
| 1170 a_elt->bits[ix] = r; | |
| 1171 changed |= cleared; | |
| 1172 ior |= r; | |
| 1173 } | |
| 1174 next = a_elt->next; | |
| 1175 if (!ior) | |
| 1176 bitmap_element_free (a, a_elt); | |
| 1177 a_elt = next; | |
| 1178 b_elt = b_elt->next; | |
| 1179 } | |
| 1180 } | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1181 gcc_checking_assert (!a->current == !a->first |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1182 && (!a->current || a->indx == a->current->indx)); |
| 0 | 1183 return changed != 0; |
| 1184 } | |
| 1185 | |
| 1186 /* Set COUNT bits from START in HEAD. */ | |
| 1187 void | |
| 1188 bitmap_set_range (bitmap head, unsigned int start, unsigned int count) | |
| 1189 { | |
| 1190 unsigned int first_index, end_bit_plus1, last_index; | |
| 1191 bitmap_element *elt, *elt_prev; | |
| 1192 unsigned int i; | |
| 1193 | |
| 1194 if (!count) | |
| 1195 return; | |
| 1196 | |
| 111 | 1197 if (count == 1) |
| 1198 { | |
| 1199 bitmap_set_bit (head, start); | |
| 1200 return; | |
| 1201 } | |
| 1202 | |
| 0 | 1203 first_index = start / BITMAP_ELEMENT_ALL_BITS; |
| 1204 end_bit_plus1 = start + count; | |
| 1205 last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS; | |
| 1206 elt = bitmap_find_bit (head, start); | |
| 1207 | |
| 1208 /* If bitmap_find_bit returns zero, the current is the closest block | |
| 1209 to the result. Otherwise, just use bitmap_element_allocate to | |
| 1210 ensure ELT is set; in the loop below, ELT == NULL means "insert | |
| 1211 at the end of the bitmap". */ | |
| 1212 if (!elt) | |
| 1213 { | |
| 1214 elt = bitmap_element_allocate (head); | |
| 1215 elt->indx = first_index; | |
| 1216 bitmap_element_link (head, elt); | |
| 1217 } | |
| 1218 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1219 gcc_checking_assert (elt->indx == first_index); |
| 0 | 1220 elt_prev = elt->prev; |
| 1221 for (i = first_index; i <= last_index; i++) | |
| 1222 { | |
| 1223 unsigned elt_start_bit = i * BITMAP_ELEMENT_ALL_BITS; | |
| 1224 unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS; | |
| 1225 | |
| 1226 unsigned int first_word_to_mod; | |
| 1227 BITMAP_WORD first_mask; | |
| 1228 unsigned int last_word_to_mod; | |
| 1229 BITMAP_WORD last_mask; | |
| 1230 unsigned int ix; | |
| 1231 | |
| 1232 if (!elt || elt->indx != i) | |
| 1233 elt = bitmap_elt_insert_after (head, elt_prev, i); | |
| 1234 | |
| 1235 if (elt_start_bit <= start) | |
| 1236 { | |
| 1237 /* The first bit to turn on is somewhere inside this | |
| 1238 elt. */ | |
| 1239 first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS; | |
| 1240 | |
| 1241 /* This mask should have 1s in all bits >= start position. */ | |
| 1242 first_mask = | |
| 1243 (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1; | |
| 1244 first_mask = ~first_mask; | |
| 1245 } | |
| 1246 else | |
| 1247 { | |
| 1248 /* The first bit to turn on is below this start of this elt. */ | |
| 1249 first_word_to_mod = 0; | |
| 1250 first_mask = ~(BITMAP_WORD) 0; | |
| 1251 } | |
| 1252 | |
| 1253 if (elt_end_bit_plus1 <= end_bit_plus1) | |
| 1254 { | |
| 1255 /* The last bit to turn on is beyond this elt. */ | |
| 1256 last_word_to_mod = BITMAP_ELEMENT_WORDS - 1; | |
| 1257 last_mask = ~(BITMAP_WORD) 0; | |
| 1258 } | |
| 1259 else | |
| 1260 { | |
| 1261 /* The last bit to turn on is inside to this elt. */ | |
| 1262 last_word_to_mod = | |
| 1263 (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS; | |
| 1264 | |
| 1265 /* The last mask should have 1s below the end bit. */ | |
| 1266 last_mask = | |
| 1267 (((BITMAP_WORD) 1) << ((end_bit_plus1 % BITMAP_WORD_BITS))) - 1; | |
| 1268 } | |
| 1269 | |
| 1270 if (first_word_to_mod == last_word_to_mod) | |
| 1271 { | |
| 1272 BITMAP_WORD mask = first_mask & last_mask; | |
| 1273 elt->bits[first_word_to_mod] |= mask; | |
| 1274 } | |
| 1275 else | |
| 1276 { | |
| 1277 elt->bits[first_word_to_mod] |= first_mask; | |
| 1278 if (BITMAP_ELEMENT_WORDS > 2) | |
| 1279 for (ix = first_word_to_mod + 1; ix < last_word_to_mod; ix++) | |
| 1280 elt->bits[ix] = ~(BITMAP_WORD) 0; | |
| 1281 elt->bits[last_word_to_mod] |= last_mask; | |
| 1282 } | |
| 1283 | |
| 1284 elt_prev = elt; | |
| 1285 elt = elt->next; | |
| 1286 } | |
| 1287 | |
| 1288 head->current = elt ? elt : elt_prev; | |
| 1289 head->indx = head->current->indx; | |
| 1290 } | |
| 1291 | |
| 1292 /* Clear COUNT bits from START in HEAD. */ | |
| 1293 void | |
| 1294 bitmap_clear_range (bitmap head, unsigned int start, unsigned int count) | |
| 1295 { | |
| 1296 unsigned int first_index, end_bit_plus1, last_index; | |
| 1297 bitmap_element *elt; | |
| 1298 | |
| 1299 if (!count) | |
| 1300 return; | |
| 1301 | |
| 111 | 1302 if (count == 1) |
| 1303 { | |
| 1304 bitmap_clear_bit (head, start); | |
| 1305 return; | |
| 1306 } | |
| 1307 | |
| 0 | 1308 first_index = start / BITMAP_ELEMENT_ALL_BITS; |
| 1309 end_bit_plus1 = start + count; | |
| 1310 last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS; | |
| 1311 elt = bitmap_find_bit (head, start); | |
| 1312 | |
| 1313 /* If bitmap_find_bit returns zero, the current is the closest block | |
| 1314 to the result. If the current is less than first index, find the | |
| 1315 next one. Otherwise, just set elt to be current. */ | |
| 1316 if (!elt) | |
| 1317 { | |
| 1318 if (head->current) | |
| 1319 { | |
| 1320 if (head->indx < first_index) | |
| 1321 { | |
| 1322 elt = head->current->next; | |
| 1323 if (!elt) | |
| 1324 return; | |
| 1325 } | |
| 1326 else | |
| 1327 elt = head->current; | |
| 1328 } | |
| 1329 else | |
| 1330 return; | |
| 1331 } | |
| 1332 | |
| 1333 while (elt && (elt->indx <= last_index)) | |
| 1334 { | |
| 1335 bitmap_element * next_elt = elt->next; | |
| 1336 unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS; | |
| 1337 unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS; | |
| 1338 | |
| 1339 | |
| 1340 if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1) | |
| 1341 /* Get rid of the entire elt and go to the next one. */ | |
| 1342 bitmap_element_free (head, elt); | |
| 1343 else | |
| 1344 { | |
| 1345 /* Going to have to knock out some bits in this elt. */ | |
| 1346 unsigned int first_word_to_mod; | |
| 1347 BITMAP_WORD first_mask; | |
| 1348 unsigned int last_word_to_mod; | |
| 1349 BITMAP_WORD last_mask; | |
| 1350 unsigned int i; | |
| 1351 bool clear = true; | |
| 1352 | |
| 1353 if (elt_start_bit <= start) | |
| 1354 { | |
| 1355 /* The first bit to turn off is somewhere inside this | |
| 1356 elt. */ | |
| 1357 first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS; | |
| 1358 | |
| 1359 /* This mask should have 1s in all bits >= start position. */ | |
| 1360 first_mask = | |
| 1361 (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1; | |
| 1362 first_mask = ~first_mask; | |
| 1363 } | |
| 1364 else | |
| 1365 { | |
| 1366 /* The first bit to turn off is below this start of this elt. */ | |
| 1367 first_word_to_mod = 0; | |
| 1368 first_mask = 0; | |
| 1369 first_mask = ~first_mask; | |
| 1370 } | |
| 1371 | |
| 1372 if (elt_end_bit_plus1 <= end_bit_plus1) | |
| 1373 { | |
| 1374 /* The last bit to turn off is beyond this elt. */ | |
| 1375 last_word_to_mod = BITMAP_ELEMENT_WORDS - 1; | |
| 1376 last_mask = 0; | |
| 1377 last_mask = ~last_mask; | |
| 1378 } | |
| 1379 else | |
| 1380 { | |
| 1381 /* The last bit to turn off is inside to this elt. */ | |
| 1382 last_word_to_mod = | |
| 1383 (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS; | |
| 1384 | |
| 1385 /* The last mask should have 1s below the end bit. */ | |
| 1386 last_mask = | |
| 1387 (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1; | |
| 1388 } | |
| 1389 | |
| 1390 | |
| 1391 if (first_word_to_mod == last_word_to_mod) | |
| 1392 { | |
| 1393 BITMAP_WORD mask = first_mask & last_mask; | |
| 1394 elt->bits[first_word_to_mod] &= ~mask; | |
| 1395 } | |
| 1396 else | |
| 1397 { | |
| 1398 elt->bits[first_word_to_mod] &= ~first_mask; | |
| 1399 if (BITMAP_ELEMENT_WORDS > 2) | |
| 1400 for (i = first_word_to_mod + 1; i < last_word_to_mod; i++) | |
| 1401 elt->bits[i] = 0; | |
| 1402 elt->bits[last_word_to_mod] &= ~last_mask; | |
| 1403 } | |
| 1404 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) | |
| 1405 if (elt->bits[i]) | |
| 1406 { | |
| 1407 clear = false; | |
| 1408 break; | |
| 1409 } | |
| 1410 /* Check to see if there are any bits left. */ | |
| 1411 if (clear) | |
| 1412 bitmap_element_free (head, elt); | |
| 1413 } | |
| 1414 elt = next_elt; | |
| 1415 } | |
| 1416 | |
| 1417 if (elt) | |
| 1418 { | |
| 1419 head->current = elt; | |
| 1420 head->indx = head->current->indx; | |
| 1421 } | |
| 1422 } | |
| 1423 | |
| 1424 /* A = ~A & B. */ | |
| 1425 | |
| 1426 void | |
| 1427 bitmap_compl_and_into (bitmap a, const_bitmap b) | |
| 1428 { | |
| 1429 bitmap_element *a_elt = a->first; | |
| 1430 const bitmap_element *b_elt = b->first; | |
| 1431 bitmap_element *a_prev = NULL; | |
| 1432 bitmap_element *next; | |
| 1433 | |
| 1434 gcc_assert (a != b); | |
| 1435 | |
| 1436 if (bitmap_empty_p (a)) | |
| 1437 { | |
| 1438 bitmap_copy (a, b); | |
| 1439 return; | |
| 1440 } | |
| 1441 if (bitmap_empty_p (b)) | |
| 1442 { | |
| 1443 bitmap_clear (a); | |
| 1444 return; | |
| 1445 } | |
| 1446 | |
| 1447 while (a_elt || b_elt) | |
| 1448 { | |
| 1449 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) | |
| 1450 { | |
| 1451 /* A is before B. Remove A */ | |
| 1452 next = a_elt->next; | |
| 1453 a_prev = a_elt->prev; | |
| 1454 bitmap_element_free (a, a_elt); | |
| 1455 a_elt = next; | |
| 1456 } | |
| 1457 else if (!a_elt || b_elt->indx < a_elt->indx) | |
| 1458 { | |
| 1459 /* B is before A. Copy B. */ | |
| 1460 next = bitmap_elt_insert_after (a, a_prev, b_elt->indx); | |
| 1461 memcpy (next->bits, b_elt->bits, sizeof (next->bits)); | |
| 1462 a_prev = next; | |
| 1463 b_elt = b_elt->next; | |
| 1464 } | |
| 1465 else | |
| 1466 { | |
| 1467 /* Matching elts, generate A = ~A & B. */ | |
| 1468 unsigned ix; | |
| 1469 BITMAP_WORD ior = 0; | |
| 1470 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1471 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
| 0 | 1472 { |
| 1473 BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix]; | |
| 1474 BITMAP_WORD r = b_elt->bits[ix] ^ cleared; | |
| 1475 | |
| 1476 a_elt->bits[ix] = r; | |
| 1477 ior |= r; | |
| 1478 } | |
| 1479 next = a_elt->next; | |
| 1480 if (!ior) | |
| 1481 bitmap_element_free (a, a_elt); | |
| 1482 else | |
| 1483 a_prev = a_elt; | |
| 1484 a_elt = next; | |
| 1485 b_elt = b_elt->next; | |
| 1486 } | |
| 1487 } | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1488 gcc_checking_assert (!a->current == !a->first |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1489 && (!a->current || a->indx == a->current->indx)); |
| 0 | 1490 return; |
| 1491 } | |
| 1492 | |
| 1493 | |
| 1494 /* Insert an element corresponding to A_ELT | B_ELT after DST_PREV, | |
| 1495 overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap | |
| 1496 had already been changed; the new value of CHANGED is returned. */ | |
| 1497 | |
| 1498 static inline bool | |
| 1499 bitmap_elt_ior (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev, | |
| 1500 const bitmap_element *a_elt, const bitmap_element *b_elt, | |
| 1501 bool changed) | |
| 1502 { | |
| 1503 gcc_assert (a_elt || b_elt); | |
| 1504 | |
| 1505 if (a_elt && b_elt && a_elt->indx == b_elt->indx) | |
| 1506 { | |
| 1507 /* Matching elts, generate A | B. */ | |
| 1508 unsigned ix; | |
| 1509 | |
| 1510 if (!changed && dst_elt && dst_elt->indx == a_elt->indx) | |
| 1511 { | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1512 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
| 0 | 1513 { |
| 1514 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; | |
| 1515 if (r != dst_elt->bits[ix]) | |
| 1516 { | |
| 1517 dst_elt->bits[ix] = r; | |
| 1518 changed = true; | |
| 1519 } | |
| 1520 } | |
| 1521 } | |
| 1522 else | |
| 1523 { | |
| 1524 changed = true; | |
| 1525 if (!dst_elt) | |
| 1526 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); | |
| 1527 else | |
| 1528 dst_elt->indx = a_elt->indx; | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1529 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
| 0 | 1530 { |
| 1531 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; | |
| 1532 dst_elt->bits[ix] = r; | |
| 1533 } | |
| 1534 } | |
| 1535 } | |
| 1536 else | |
| 1537 { | |
| 1538 /* Copy a single element. */ | |
| 1539 const bitmap_element *src; | |
| 1540 | |
| 1541 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) | |
| 1542 src = a_elt; | |
| 1543 else | |
| 1544 src = b_elt; | |
| 1545 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1546 gcc_checking_assert (src); |
| 0 | 1547 changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src, changed); |
| 1548 } | |
| 1549 return changed; | |
| 1550 } | |
| 1551 | |
| 1552 | |
| 1553 /* DST = A | B. Return true if DST changes. */ | |
| 1554 | |
| 1555 bool | |
| 1556 bitmap_ior (bitmap dst, const_bitmap a, const_bitmap b) | |
| 1557 { | |
| 1558 bitmap_element *dst_elt = dst->first; | |
| 1559 const bitmap_element *a_elt = a->first; | |
| 1560 const bitmap_element *b_elt = b->first; | |
| 1561 bitmap_element *dst_prev = NULL; | |
| 1562 bitmap_element **dst_prev_pnext = &dst->first; | |
| 1563 bool changed = false; | |
| 1564 | |
| 1565 gcc_assert (dst != a && dst != b); | |
| 1566 | |
| 1567 while (a_elt || b_elt) | |
| 1568 { | |
| 1569 changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed); | |
| 1570 | |
| 1571 if (a_elt && b_elt && a_elt->indx == b_elt->indx) | |
| 1572 { | |
| 1573 a_elt = a_elt->next; | |
| 1574 b_elt = b_elt->next; | |
| 1575 } | |
| 1576 else | |
| 1577 { | |
| 1578 if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx)) | |
| 1579 a_elt = a_elt->next; | |
| 1580 else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx)) | |
| 1581 b_elt = b_elt->next; | |
| 1582 } | |
| 1583 | |
| 1584 dst_prev = *dst_prev_pnext; | |
| 1585 dst_prev_pnext = &dst_prev->next; | |
| 1586 dst_elt = *dst_prev_pnext; | |
| 1587 } | |
| 1588 | |
| 1589 if (dst_elt) | |
| 1590 { | |
| 1591 changed = true; | |
| 111 | 1592 /* Ensure that dst->current is valid. */ |
| 1593 dst->current = dst->first; | |
| 0 | 1594 bitmap_elt_clear_from (dst, dst_elt); |
| 1595 } | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1596 gcc_checking_assert (!dst->current == !dst->first); |
| 0 | 1597 if (dst->current) |
| 1598 dst->indx = dst->current->indx; | |
| 1599 return changed; | |
| 1600 } | |
| 1601 | |
| 1602 /* A |= B. Return true if A changes. */ | |
| 1603 | |
| 1604 bool | |
| 1605 bitmap_ior_into (bitmap a, const_bitmap b) | |
| 1606 { | |
| 1607 bitmap_element *a_elt = a->first; | |
| 1608 const bitmap_element *b_elt = b->first; | |
| 1609 bitmap_element *a_prev = NULL; | |
| 1610 bitmap_element **a_prev_pnext = &a->first; | |
| 1611 bool changed = false; | |
| 1612 | |
| 1613 if (a == b) | |
| 1614 return false; | |
| 1615 | |
| 1616 while (b_elt) | |
| 1617 { | |
| 1618 /* If A lags behind B, just advance it. */ | |
| 1619 if (!a_elt || a_elt->indx == b_elt->indx) | |
| 1620 { | |
| 1621 changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed); | |
| 1622 b_elt = b_elt->next; | |
| 1623 } | |
| 1624 else if (a_elt->indx > b_elt->indx) | |
| 1625 { | |
| 1626 changed = bitmap_elt_copy (a, NULL, a_prev, b_elt, changed); | |
| 1627 b_elt = b_elt->next; | |
| 1628 } | |
| 1629 | |
| 1630 a_prev = *a_prev_pnext; | |
| 1631 a_prev_pnext = &a_prev->next; | |
| 1632 a_elt = *a_prev_pnext; | |
| 1633 } | |
| 1634 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1635 gcc_checking_assert (!a->current == !a->first); |
| 0 | 1636 if (a->current) |
| 1637 a->indx = a->current->indx; | |
| 1638 return changed; | |
| 1639 } | |
| 1640 | |
| 1641 /* DST = A ^ B */ | |
| 1642 | |
| 1643 void | |
| 1644 bitmap_xor (bitmap dst, const_bitmap a, const_bitmap b) | |
| 1645 { | |
| 1646 bitmap_element *dst_elt = dst->first; | |
| 1647 const bitmap_element *a_elt = a->first; | |
| 1648 const bitmap_element *b_elt = b->first; | |
| 1649 bitmap_element *dst_prev = NULL; | |
| 1650 | |
| 1651 gcc_assert (dst != a && dst != b); | |
| 1652 if (a == b) | |
| 1653 { | |
| 1654 bitmap_clear (dst); | |
| 1655 return; | |
| 1656 } | |
| 1657 | |
| 1658 while (a_elt || b_elt) | |
| 1659 { | |
| 1660 if (a_elt && b_elt && a_elt->indx == b_elt->indx) | |
| 1661 { | |
| 1662 /* Matching elts, generate A ^ B. */ | |
| 1663 unsigned ix; | |
| 1664 BITMAP_WORD ior = 0; | |
| 1665 | |
| 1666 if (!dst_elt) | |
| 1667 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); | |
| 1668 else | |
| 1669 dst_elt->indx = a_elt->indx; | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1670 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
| 0 | 1671 { |
| 1672 BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix]; | |
| 1673 | |
| 1674 ior |= r; | |
| 1675 dst_elt->bits[ix] = r; | |
| 1676 } | |
| 1677 a_elt = a_elt->next; | |
| 1678 b_elt = b_elt->next; | |
| 1679 if (ior) | |
| 1680 { | |
| 1681 dst_prev = dst_elt; | |
| 1682 dst_elt = dst_elt->next; | |
| 1683 } | |
| 1684 } | |
| 1685 else | |
| 1686 { | |
| 1687 /* Copy a single element. */ | |
| 1688 const bitmap_element *src; | |
| 1689 | |
| 1690 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) | |
| 1691 { | |
| 1692 src = a_elt; | |
| 1693 a_elt = a_elt->next; | |
| 1694 } | |
| 1695 else | |
| 1696 { | |
| 1697 src = b_elt; | |
| 1698 b_elt = b_elt->next; | |
| 1699 } | |
| 1700 | |
| 1701 if (!dst_elt) | |
| 1702 dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx); | |
| 1703 else | |
| 1704 dst_elt->indx = src->indx; | |
| 1705 memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits)); | |
| 1706 dst_prev = dst_elt; | |
| 1707 dst_elt = dst_elt->next; | |
| 1708 } | |
| 1709 } | |
| 1710 /* Ensure that dst->current is valid. */ | |
| 1711 dst->current = dst->first; | |
| 1712 bitmap_elt_clear_from (dst, dst_elt); | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1713 gcc_checking_assert (!dst->current == !dst->first); |
| 0 | 1714 if (dst->current) |
| 1715 dst->indx = dst->current->indx; | |
| 1716 } | |
| 1717 | |
| 1718 /* A ^= B */ | |
| 1719 | |
| 1720 void | |
| 1721 bitmap_xor_into (bitmap a, const_bitmap b) | |
| 1722 { | |
| 1723 bitmap_element *a_elt = a->first; | |
| 1724 const bitmap_element *b_elt = b->first; | |
| 1725 bitmap_element *a_prev = NULL; | |
| 1726 | |
| 1727 if (a == b) | |
| 1728 { | |
| 1729 bitmap_clear (a); | |
| 1730 return; | |
| 1731 } | |
| 1732 | |
| 1733 while (b_elt) | |
| 1734 { | |
| 1735 if (!a_elt || b_elt->indx < a_elt->indx) | |
| 1736 { | |
| 1737 /* Copy b_elt. */ | |
| 1738 bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx); | |
| 1739 memcpy (dst->bits, b_elt->bits, sizeof (dst->bits)); | |
| 1740 a_prev = dst; | |
| 1741 b_elt = b_elt->next; | |
| 1742 } | |
| 1743 else if (a_elt->indx < b_elt->indx) | |
| 1744 { | |
| 1745 a_prev = a_elt; | |
| 1746 a_elt = a_elt->next; | |
| 1747 } | |
| 1748 else | |
| 1749 { | |
| 1750 /* Matching elts, generate A ^= B. */ | |
| 1751 unsigned ix; | |
| 1752 BITMAP_WORD ior = 0; | |
| 1753 bitmap_element *next = a_elt->next; | |
| 1754 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1755 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
| 0 | 1756 { |
| 1757 BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix]; | |
| 1758 | |
| 1759 ior |= r; | |
| 1760 a_elt->bits[ix] = r; | |
| 1761 } | |
| 1762 b_elt = b_elt->next; | |
| 1763 if (ior) | |
| 1764 a_prev = a_elt; | |
| 1765 else | |
| 1766 bitmap_element_free (a, a_elt); | |
| 1767 a_elt = next; | |
| 1768 } | |
| 1769 } | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1770 gcc_checking_assert (!a->current == !a->first); |
| 0 | 1771 if (a->current) |
| 1772 a->indx = a->current->indx; | |
| 1773 } | |
| 1774 | |
| 1775 /* Return true if two bitmaps are identical. | |
| 1776 We do not bother with a check for pointer equality, as that never | |
| 1777 occurs in practice. */ | |
| 1778 | |
| 1779 bool | |
| 1780 bitmap_equal_p (const_bitmap a, const_bitmap b) | |
| 1781 { | |
| 1782 const bitmap_element *a_elt; | |
| 1783 const bitmap_element *b_elt; | |
| 1784 unsigned ix; | |
| 1785 | |
| 1786 for (a_elt = a->first, b_elt = b->first; | |
| 1787 a_elt && b_elt; | |
| 1788 a_elt = a_elt->next, b_elt = b_elt->next) | |
| 1789 { | |
| 1790 if (a_elt->indx != b_elt->indx) | |
| 1791 return false; | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1792 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
| 0 | 1793 if (a_elt->bits[ix] != b_elt->bits[ix]) |
| 1794 return false; | |
| 1795 } | |
| 1796 return !a_elt && !b_elt; | |
| 1797 } | |
| 1798 | |
| 1799 /* Return true if A AND B is not empty. */ | |
| 1800 | |
| 1801 bool | |
| 1802 bitmap_intersect_p (const_bitmap a, const_bitmap b) | |
| 1803 { | |
| 1804 const bitmap_element *a_elt; | |
| 1805 const bitmap_element *b_elt; | |
| 1806 unsigned ix; | |
| 1807 | |
| 1808 for (a_elt = a->first, b_elt = b->first; | |
| 1809 a_elt && b_elt;) | |
| 1810 { | |
| 1811 if (a_elt->indx < b_elt->indx) | |
| 1812 a_elt = a_elt->next; | |
| 1813 else if (b_elt->indx < a_elt->indx) | |
| 1814 b_elt = b_elt->next; | |
| 1815 else | |
| 1816 { | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1817 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
| 0 | 1818 if (a_elt->bits[ix] & b_elt->bits[ix]) |
| 1819 return true; | |
| 1820 a_elt = a_elt->next; | |
| 1821 b_elt = b_elt->next; | |
| 1822 } | |
| 1823 } | |
| 1824 return false; | |
| 1825 } | |
| 1826 | |
| 1827 /* Return true if A AND NOT B is not empty. */ | |
| 1828 | |
| 1829 bool | |
| 1830 bitmap_intersect_compl_p (const_bitmap a, const_bitmap b) | |
| 1831 { | |
| 1832 const bitmap_element *a_elt; | |
| 1833 const bitmap_element *b_elt; | |
| 1834 unsigned ix; | |
| 1835 for (a_elt = a->first, b_elt = b->first; | |
| 1836 a_elt && b_elt;) | |
| 1837 { | |
| 1838 if (a_elt->indx < b_elt->indx) | |
| 1839 return true; | |
| 1840 else if (b_elt->indx < a_elt->indx) | |
| 1841 b_elt = b_elt->next; | |
| 1842 else | |
| 1843 { | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1844 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
| 0 | 1845 if (a_elt->bits[ix] & ~b_elt->bits[ix]) |
| 1846 return true; | |
| 1847 a_elt = a_elt->next; | |
| 1848 b_elt = b_elt->next; | |
| 1849 } | |
| 1850 } | |
| 1851 return a_elt != NULL; | |
| 1852 } | |
| 1853 | |
| 1854 | |
| 1855 /* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */ | |
| 1856 | |
| 1857 bool | |
| 1858 bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b, const_bitmap kill) | |
| 1859 { | |
| 1860 bool changed = false; | |
| 1861 | |
| 1862 bitmap_element *dst_elt = dst->first; | |
| 1863 const bitmap_element *a_elt = a->first; | |
| 1864 const bitmap_element *b_elt = b->first; | |
| 1865 const bitmap_element *kill_elt = kill->first; | |
| 1866 bitmap_element *dst_prev = NULL; | |
| 1867 bitmap_element **dst_prev_pnext = &dst->first; | |
| 1868 | |
| 1869 gcc_assert (dst != a && dst != b && dst != kill); | |
| 1870 | |
| 1871 /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */ | |
| 1872 if (b == kill || bitmap_empty_p (b)) | |
| 1873 { | |
| 1874 changed = !bitmap_equal_p (dst, a); | |
| 1875 if (changed) | |
| 1876 bitmap_copy (dst, a); | |
| 1877 return changed; | |
| 1878 } | |
| 1879 if (bitmap_empty_p (kill)) | |
| 1880 return bitmap_ior (dst, a, b); | |
| 1881 if (bitmap_empty_p (a)) | |
| 1882 return bitmap_and_compl (dst, b, kill); | |
| 1883 | |
| 1884 while (a_elt || b_elt) | |
| 1885 { | |
| 1886 bool new_element = false; | |
| 1887 | |
| 1888 if (b_elt) | |
| 1889 while (kill_elt && kill_elt->indx < b_elt->indx) | |
| 1890 kill_elt = kill_elt->next; | |
| 1891 | |
| 1892 if (b_elt && kill_elt && kill_elt->indx == b_elt->indx | |
| 1893 && (!a_elt || a_elt->indx >= b_elt->indx)) | |
| 1894 { | |
| 1895 bitmap_element tmp_elt; | |
| 1896 unsigned ix; | |
| 1897 | |
| 1898 BITMAP_WORD ior = 0; | |
| 1899 tmp_elt.indx = b_elt->indx; | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1900 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
| 0 | 1901 { |
| 1902 BITMAP_WORD r = b_elt->bits[ix] & ~kill_elt->bits[ix]; | |
| 1903 ior |= r; | |
| 1904 tmp_elt.bits[ix] = r; | |
| 1905 } | |
| 1906 | |
| 1907 if (ior) | |
| 1908 { | |
| 1909 changed = bitmap_elt_ior (dst, dst_elt, dst_prev, | |
| 1910 a_elt, &tmp_elt, changed); | |
| 1911 new_element = true; | |
| 1912 if (a_elt && a_elt->indx == b_elt->indx) | |
| 1913 a_elt = a_elt->next; | |
| 1914 } | |
| 1915 | |
| 1916 b_elt = b_elt->next; | |
| 1917 kill_elt = kill_elt->next; | |
| 1918 } | |
| 1919 else | |
| 1920 { | |
| 1921 changed = bitmap_elt_ior (dst, dst_elt, dst_prev, | |
| 1922 a_elt, b_elt, changed); | |
| 1923 new_element = true; | |
| 1924 | |
| 1925 if (a_elt && b_elt && a_elt->indx == b_elt->indx) | |
| 1926 { | |
| 1927 a_elt = a_elt->next; | |
| 1928 b_elt = b_elt->next; | |
| 1929 } | |
| 1930 else | |
| 1931 { | |
| 1932 if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx)) | |
| 1933 a_elt = a_elt->next; | |
| 1934 else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx)) | |
| 1935 b_elt = b_elt->next; | |
| 1936 } | |
| 1937 } | |
| 1938 | |
| 1939 if (new_element) | |
| 1940 { | |
| 1941 dst_prev = *dst_prev_pnext; | |
| 1942 dst_prev_pnext = &dst_prev->next; | |
| 1943 dst_elt = *dst_prev_pnext; | |
| 1944 } | |
| 1945 } | |
| 1946 | |
| 1947 if (dst_elt) | |
| 1948 { | |
| 1949 changed = true; | |
| 111 | 1950 /* Ensure that dst->current is valid. */ |
| 1951 dst->current = dst->first; | |
| 0 | 1952 bitmap_elt_clear_from (dst, dst_elt); |
| 1953 } | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1954 gcc_checking_assert (!dst->current == !dst->first); |
| 0 | 1955 if (dst->current) |
| 1956 dst->indx = dst->current->indx; | |
| 1957 | |
| 1958 return changed; | |
| 1959 } | |
| 1960 | |
| 1961 /* A |= (FROM1 & ~FROM2). Return true if A changes. */ | |
| 1962 | |
| 1963 bool | |
| 1964 bitmap_ior_and_compl_into (bitmap a, const_bitmap from1, const_bitmap from2) | |
| 1965 { | |
| 1966 bitmap_head tmp; | |
| 1967 bool changed; | |
| 1968 | |
| 1969 bitmap_initialize (&tmp, &bitmap_default_obstack); | |
| 1970 bitmap_and_compl (&tmp, from1, from2); | |
| 1971 changed = bitmap_ior_into (a, &tmp); | |
| 1972 bitmap_clear (&tmp); | |
| 1973 | |
| 1974 return changed; | |
| 1975 } | |
| 1976 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1977 /* A |= (B & C). Return true if A changes. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1978 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1979 bool |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1980 bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1981 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1982 bitmap_element *a_elt = a->first; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1983 const bitmap_element *b_elt = b->first; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1984 const bitmap_element *c_elt = c->first; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1985 bitmap_element and_elt; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1986 bitmap_element *a_prev = NULL; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1987 bitmap_element **a_prev_pnext = &a->first; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1988 bool changed = false; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1989 unsigned ix; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1990 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1991 if (b == c) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1992 return bitmap_ior_into (a, b); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1993 if (bitmap_empty_p (b) || bitmap_empty_p (c)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1994 return false; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1995 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1996 and_elt.indx = -1; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1997 while (b_elt && c_elt) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1998 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1999 BITMAP_WORD overall; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2000 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2001 /* Find a common item of B and C. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2002 while (b_elt->indx != c_elt->indx) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2003 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2004 if (b_elt->indx < c_elt->indx) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2005 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2006 b_elt = b_elt->next; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2007 if (!b_elt) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2008 goto done; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2009 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2010 else |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2011 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2012 c_elt = c_elt->next; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2013 if (!c_elt) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2014 goto done; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2015 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2016 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2017 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2018 overall = 0; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2019 and_elt.indx = b_elt->indx; |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2020 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2021 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2022 and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix]; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2023 overall |= and_elt.bits[ix]; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2024 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2025 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2026 b_elt = b_elt->next; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2027 c_elt = c_elt->next; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2028 if (!overall) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2029 continue; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2030 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2031 /* Now find a place to insert AND_ELT. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2032 do |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2033 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2034 ix = a_elt ? a_elt->indx : and_elt.indx; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2035 if (ix == and_elt.indx) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2036 changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, &and_elt, changed); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2037 else if (ix > and_elt.indx) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2038 changed = bitmap_elt_copy (a, NULL, a_prev, &and_elt, changed); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2039 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2040 a_prev = *a_prev_pnext; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2041 a_prev_pnext = &a_prev->next; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2042 a_elt = *a_prev_pnext; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2043 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2044 /* If A lagged behind B/C, we advanced it so loop once more. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2045 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2046 while (ix < and_elt.indx); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2047 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2048 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2049 done: |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2050 gcc_checking_assert (!a->current == !a->first); |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2051 if (a->current) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2052 a->indx = a->current->indx; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2053 return changed; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2054 } |
| 111 | 2055 |
| 2056 /* Compute hash of bitmap (for purposes of hashing). */ | |
| 2057 hashval_t | |
| 2058 bitmap_hash (const_bitmap head) | |
| 2059 { | |
| 2060 const bitmap_element *ptr; | |
| 2061 BITMAP_WORD hash = 0; | |
| 2062 int ix; | |
| 2063 | |
| 2064 for (ptr = head->first; ptr; ptr = ptr->next) | |
| 2065 { | |
| 2066 hash ^= ptr->indx; | |
| 2067 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | |
| 2068 hash ^= ptr->bits[ix]; | |
| 2069 } | |
| 2070 return (hashval_t)hash; | |
| 2071 } | |
| 2072 | |
| 0 | 2073 |
| 2074 /* Debugging function to print out the contents of a bitmap. */ | |
| 2075 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2076 DEBUG_FUNCTION void |
| 0 | 2077 debug_bitmap_file (FILE *file, const_bitmap head) |
| 2078 { | |
| 2079 const bitmap_element *ptr; | |
| 2080 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2081 fprintf (file, "\nfirst = " HOST_PTR_PRINTF |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2082 " current = " HOST_PTR_PRINTF " indx = %u\n", |
| 0 | 2083 (void *) head->first, (void *) head->current, head->indx); |
| 2084 | |
| 2085 for (ptr = head->first; ptr; ptr = ptr->next) | |
| 2086 { | |
| 2087 unsigned int i, j, col = 26; | |
| 2088 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2089 fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2090 " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {", |
| 0 | 2091 (const void*) ptr, (const void*) ptr->next, |
| 2092 (const void*) ptr->prev, ptr->indx); | |
| 2093 | |
| 2094 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) | |
| 2095 for (j = 0; j < BITMAP_WORD_BITS; j++) | |
| 2096 if ((ptr->bits[i] >> j) & 1) | |
| 2097 { | |
| 2098 if (col > 70) | |
| 2099 { | |
| 2100 fprintf (file, "\n\t\t\t"); | |
| 2101 col = 24; | |
| 2102 } | |
| 2103 | |
| 2104 fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS | |
| 2105 + i * BITMAP_WORD_BITS + j)); | |
| 2106 col += 4; | |
| 2107 } | |
| 2108 | |
| 2109 fprintf (file, " }\n"); | |
| 2110 } | |
| 2111 } | |
| 2112 | |
| 2113 /* Function to be called from the debugger to print the contents | |
| 2114 of a bitmap. */ | |
| 2115 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2116 DEBUG_FUNCTION void |
| 0 | 2117 debug_bitmap (const_bitmap head) |
| 2118 { | |
| 111 | 2119 debug_bitmap_file (stderr, head); |
| 0 | 2120 } |
| 2121 | |
| 2122 /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file, | |
| 2123 it does not print anything but the bits. */ | |
| 2124 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2125 DEBUG_FUNCTION void |
| 111 | 2126 bitmap_print (FILE *file, const_bitmap head, const char *prefix, |
| 2127 const char *suffix) | |
| 0 | 2128 { |
| 2129 const char *comma = ""; | |
| 2130 unsigned i; | |
| 2131 bitmap_iterator bi; | |
| 2132 | |
| 2133 fputs (prefix, file); | |
| 2134 EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi) | |
| 2135 { | |
| 2136 fprintf (file, "%s%d", comma, i); | |
| 2137 comma = ", "; | |
| 2138 } | |
| 2139 fputs (suffix, file); | |
| 2140 } | |
| 2141 | |
| 2142 /* Output per-bitmap memory usage statistics. */ | |
| 2143 void | |
| 2144 dump_bitmap_statistics (void) | |
| 2145 { | |
| 111 | 2146 if (!GATHER_STATISTICS) |
| 0 | 2147 return; |
| 2148 | |
| 111 | 2149 bitmap_mem_desc.dump (BITMAP_ORIGIN); |
| 2150 } | |
| 2151 | |
| 2152 DEBUG_FUNCTION void | |
| 2153 debug (const bitmap_head &ref) | |
| 2154 { | |
| 2155 dump_bitmap (stderr, &ref); | |
| 2156 } | |
| 2157 | |
| 2158 DEBUG_FUNCTION void | |
| 2159 debug (const bitmap_head *ptr) | |
| 2160 { | |
| 2161 if (ptr) | |
| 2162 debug (*ptr); | |
| 2163 else | |
| 2164 fprintf (stderr, "<nil>\n"); | |
| 2165 } | |
| 2166 | |
| 2167 #if CHECKING_P | |
| 2168 | |
| 2169 namespace selftest { | |
| 2170 | |
| 2171 /* Selftests for bitmaps. */ | |
| 2172 | |
| 2173 /* Freshly-created bitmaps ought to be empty. */ | |
| 2174 | |
| 2175 static void | |
| 2176 test_gc_alloc () | |
| 2177 { | |
| 2178 bitmap b = bitmap_gc_alloc (); | |
| 2179 ASSERT_TRUE (bitmap_empty_p (b)); | |
| 2180 } | |
| 2181 | |
| 2182 /* Verify bitmap_set_range. */ | |
| 2183 | |
| 2184 static void | |
| 2185 test_set_range () | |
| 2186 { | |
| 2187 bitmap b = bitmap_gc_alloc (); | |
| 2188 ASSERT_TRUE (bitmap_empty_p (b)); | |
| 2189 | |
| 2190 bitmap_set_range (b, 7, 5); | |
| 2191 ASSERT_FALSE (bitmap_empty_p (b)); | |
| 2192 ASSERT_EQ (5, bitmap_count_bits (b)); | |
| 2193 | |
| 2194 /* Verify bitmap_bit_p at the boundaries. */ | |
| 2195 ASSERT_FALSE (bitmap_bit_p (b, 6)); | |
| 2196 ASSERT_TRUE (bitmap_bit_p (b, 7)); | |
| 2197 ASSERT_TRUE (bitmap_bit_p (b, 11)); | |
| 2198 ASSERT_FALSE (bitmap_bit_p (b, 12)); | |
| 0 | 2199 } |
| 2200 | |
| 111 | 2201 /* Verify splitting a range into two pieces using bitmap_clear_bit. */ |
| 2202 | |
| 2203 static void | |
| 2204 test_clear_bit_in_middle () | |
| 0 | 2205 { |
| 111 | 2206 bitmap b = bitmap_gc_alloc (); |
| 0 | 2207 |
| 111 | 2208 /* Set b to [100..200]. */ |
| 2209 bitmap_set_range (b, 100, 100); | |
| 2210 ASSERT_EQ (100, bitmap_count_bits (b)); | |
| 2211 | |
| 2212 /* Clear a bit in the middle. */ | |
| 2213 bool changed = bitmap_clear_bit (b, 150); | |
| 2214 ASSERT_TRUE (changed); | |
| 2215 ASSERT_EQ (99, bitmap_count_bits (b)); | |
| 2216 ASSERT_TRUE (bitmap_bit_p (b, 149)); | |
| 2217 ASSERT_FALSE (bitmap_bit_p (b, 150)); | |
| 2218 ASSERT_TRUE (bitmap_bit_p (b, 151)); | |
| 0 | 2219 } |
| 2220 | |
| 111 | 2221 /* Verify bitmap_copy. */ |
| 2222 | |
| 2223 static void | |
| 2224 test_copying () | |
| 2225 { | |
| 2226 bitmap src = bitmap_gc_alloc (); | |
| 2227 bitmap_set_range (src, 40, 10); | |
| 2228 | |
| 2229 bitmap dst = bitmap_gc_alloc (); | |
| 2230 ASSERT_FALSE (bitmap_equal_p (src, dst)); | |
| 2231 bitmap_copy (dst, src); | |
| 2232 ASSERT_TRUE (bitmap_equal_p (src, dst)); | |
| 2233 | |
| 2234 /* Verify that we can make them unequal again... */ | |
| 2235 bitmap_set_range (src, 70, 5); | |
| 2236 ASSERT_FALSE (bitmap_equal_p (src, dst)); | |
| 2237 | |
| 2238 /* ...and that changing src after the copy didn't affect | |
| 2239 the other: */ | |
| 2240 ASSERT_FALSE (bitmap_bit_p (dst, 70)); | |
| 2241 } | |
| 2242 | |
| 2243 /* Verify bitmap_single_bit_set_p. */ | |
| 2244 | |
| 2245 static void | |
| 2246 test_bitmap_single_bit_set_p () | |
| 2247 { | |
| 2248 bitmap b = bitmap_gc_alloc (); | |
| 2249 | |
| 2250 ASSERT_FALSE (bitmap_single_bit_set_p (b)); | |
| 2251 | |
| 2252 bitmap_set_range (b, 42, 1); | |
| 2253 ASSERT_TRUE (bitmap_single_bit_set_p (b)); | |
| 2254 ASSERT_EQ (42, bitmap_first_set_bit (b)); | |
| 2255 | |
| 2256 bitmap_set_range (b, 1066, 1); | |
| 2257 ASSERT_FALSE (bitmap_single_bit_set_p (b)); | |
| 2258 ASSERT_EQ (42, bitmap_first_set_bit (b)); | |
| 2259 | |
| 2260 bitmap_clear_range (b, 0, 100); | |
| 2261 ASSERT_TRUE (bitmap_single_bit_set_p (b)); | |
| 2262 ASSERT_EQ (1066, bitmap_first_set_bit (b)); | |
| 2263 } | |
| 2264 | |
| 2265 /* Run all of the selftests within this file. */ | |
| 2266 | |
| 2267 void | |
| 2268 bitmap_c_tests () | |
| 2269 { | |
| 2270 test_gc_alloc (); | |
| 2271 test_set_range (); | |
| 2272 test_clear_bit_in_middle (); | |
| 2273 test_copying (); | |
| 2274 test_bitmap_single_bit_set_p (); | |
| 2275 } | |
| 2276 | |
| 2277 } // namespace selftest | |
| 2278 #endif /* CHECKING_P */ | |
| 2279 | |
| 0 | 2280 #include "gt-bitmap.h" |