]>
Commit | Line | Data |
---|---|---|
5f6c11d6 RH |
1 | /* Simple bitmaps. |
2 | Copyright (C) 1999 Free Software Foundation, Inc. | |
3 | ||
4 | This file is part of GNU CC. | |
5 | ||
6 | GNU CC is free software; you can redistribute it and/or modify | |
7 | it under the terms of the GNU General Public License as published by | |
8 | the Free Software Foundation; either version 2, or (at your option) | |
9 | any later version. | |
10 | ||
11 | GNU CC is distributed in the hope that it will be useful, | |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | GNU General Public License for more details. | |
15 | ||
16 | You should have received a copy of the GNU General Public License | |
17 | along with GNU CC; see the file COPYING. If not, write to | |
18 | the Free Software Foundation, 59 Temple Place - Suite 330, | |
19 | Boston, MA 02111-1307, USA. */ | |
20 | ||
21 | /* It's not clear yet whether using bitmap.[ch] will be a win. | |
22 | It should be straightforward to convert so for now we keep things simple | |
23 | while more important issues are dealt with. */ | |
24 | ||
25 | #define SBITMAP_ELT_BITS HOST_BITS_PER_WIDE_INT | |
26 | #define SBITMAP_ELT_TYPE unsigned HOST_WIDE_INT | |
27 | ||
28 | typedef struct simple_bitmap_def { | |
29 | /* Number of bits. */ | |
30 | int n_bits; | |
31 | /* Size in elements. */ | |
32 | int size; | |
33 | /* Size in bytes. */ | |
34 | int bytes; | |
35 | /* The elements. */ | |
36 | SBITMAP_ELT_TYPE elms[1]; | |
37 | } *sbitmap; | |
38 | ||
39 | typedef SBITMAP_ELT_TYPE *sbitmap_ptr; | |
40 | ||
41 | /* Return the set size needed for N elements. */ | |
42 | #define SBITMAP_SET_SIZE(n) (((n) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS) | |
43 | ||
44 | /* set bit number bitno in the bitmap */ | |
45 | #define SET_BIT(bitmap, bitno) \ | |
46 | ((bitmap)->elms [(bitno) / SBITMAP_ELT_BITS] \ | |
47 | |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS) | |
48 | ||
49 | /* test if bit number bitno in the bitmap is set */ | |
50 | #define TEST_BIT(bitmap, bitno) \ | |
51 | ((bitmap)->elms [(bitno) / SBITMAP_ELT_BITS] >> (bitno) % SBITMAP_ELT_BITS & 1) | |
52 | ||
53 | /* reset bit number bitno in the bitmap */ | |
54 | #define RESET_BIT(bitmap, bitno) \ | |
55 | ((bitmap)->elms [(bitno) / SBITMAP_ELT_BITS] \ | |
56 | &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS)) | |
57 | ||
58 | /* Loop over all elements of SBITSET, starting with MIN. */ | |
59 | #define EXECUTE_IF_SET_IN_SBITMAP(SBITMAP, MIN, N, CODE) \ | |
60 | do { \ | |
61 | unsigned int bit_num_ = (MIN) % (unsigned) SBITMAP_ELT_BITS; \ | |
62 | unsigned int word_num_ = (MIN) / (unsigned) SBITMAP_ELT_BITS; \ | |
63 | unsigned int size_ = (SBITMAP)->size; \ | |
64 | SBITMAP_ELT_TYPE *ptr_ = (SBITMAP)->elms; \ | |
65 | \ | |
66 | while (word_num_ < size_) \ | |
67 | { \ | |
68 | SBITMAP_ELT_TYPE word_ = ptr_[word_num_]; \ | |
69 | if (word_ != 0) \ | |
70 | { \ | |
71 | for (; bit_num_ < SBITMAP_ELT_BITS; ++bit_num_) \ | |
72 | { \ | |
73 | SBITMAP_ELT_TYPE mask_ = (SBITMAP_ELT_TYPE)1 << bit_num_; \ | |
74 | if ((word_ & mask_) != 0) \ | |
75 | { \ | |
76 | word_ &= ~mask_; \ | |
77 | (N) = word_num_ * SBITMAP_ELT_BITS + bit_num_; \ | |
78 | CODE; \ | |
79 | if (word_ == 0) \ | |
80 | break; \ | |
81 | } \ | |
82 | } \ | |
83 | } \ | |
84 | bit_num_ = 0; \ | |
85 | word_num_++; \ | |
86 | } \ | |
87 | } while (0) | |
88 | ||
89 | #define sbitmap_free(map) free(map) | |
90 | #define sbitmap_vector_free(vec) free(vec) | |
91 | ||
92 | extern void dump_sbitmap PROTO ((FILE *, sbitmap)); | |
dff01034 | 93 | extern void dump_sbitmap_vector PROTO ((FILE *, const char *, const char *, |
5f6c11d6 RH |
94 | sbitmap *, int)); |
95 | ||
96 | extern sbitmap sbitmap_alloc PROTO ((int)); | |
97 | extern sbitmap *sbitmap_vector_alloc PROTO ((int, int)); | |
98 | ||
99 | extern void sbitmap_copy PROTO ((sbitmap, sbitmap)); | |
100 | extern void sbitmap_zero PROTO ((sbitmap)); | |
101 | extern void sbitmap_ones PROTO ((sbitmap)); | |
102 | extern void sbitmap_vector_zero PROTO ((sbitmap *, int)); | |
103 | extern void sbitmap_vector_ones PROTO ((sbitmap *, int)); | |
104 | ||
105 | extern int sbitmap_union_of_diff PROTO ((sbitmap, sbitmap, sbitmap, sbitmap)); | |
106 | extern void sbitmap_difference PROTO ((sbitmap, sbitmap, sbitmap)); | |
107 | extern void sbitmap_not PROTO ((sbitmap, sbitmap)); | |
108 | extern int sbitmap_a_or_b_and_c PROTO ((sbitmap, sbitmap, sbitmap, sbitmap)); | |
109 | extern int sbitmap_a_and_b_or_c PROTO ((sbitmap, sbitmap, sbitmap, sbitmap)); | |
110 | extern int sbitmap_a_and_b PROTO ((sbitmap, sbitmap, sbitmap)); | |
111 | extern int sbitmap_a_or_b PROTO ((sbitmap, sbitmap, sbitmap)); | |
112 | ||
113 | struct int_list; | |
114 | extern void sbitmap_intersect_of_predsucc PROTO ((sbitmap, sbitmap *, | |
115 | int, struct int_list **)); | |
116 | #define sbitmap_intersect_of_predecessors sbitmap_intersect_of_predsucc | |
117 | #define sbitmap_intersect_of_successors sbitmap_intersect_of_predsucc | |
118 | ||
119 | extern void sbitmap_union_of_predsucc PROTO ((sbitmap, sbitmap *, int, | |
120 | struct int_list **)); | |
121 | #define sbitmap_union_of_predecessors sbitmap_union_of_predsucc | |
122 | #define sbitmap_union_of_successors sbitmap_union_of_predsucc |