annotate gcc/sbitmap.c @ 16:04ced10e8804

gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents f6334be47118
children 84e7813d76e9
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 /* Simple bitmaps.
16
kono
parents: 14
diff changeset
2 Copyright (C) 1999-2017 Free Software Foundation, Inc.
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
3
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 This file is part of GCC.
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
5
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 GCC is free software; you can redistribute it and/or modify it under
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 the terms of the GNU General Public License as published by the Free
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 Software Foundation; either version 3, or (at your option) any later
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 version.
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
10
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 for more details.
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
15
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 You should have received a copy of the GNU General Public License
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 along with GCC; see the file COPYING3. If not see
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 <http://www.gnu.org/licenses/>. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
19
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 #include "config.h"
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 #include "system.h"
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 #include "coretypes.h"
14
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
23 #include "sbitmap.h"
16
kono
parents: 14
diff changeset
24 #include "selftest.h"
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
25
14
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
26 typedef SBITMAP_ELT_TYPE *sbitmap_ptr;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
27 typedef const SBITMAP_ELT_TYPE *const_sbitmap_ptr;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
28
16
kono
parents: 14
diff changeset
29 /* Return the size in bytes of a bitmap MAP. */
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
30
16
kono
parents: 14
diff changeset
31 static inline unsigned int sbitmap_size_bytes (const_sbitmap map)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 {
16
kono
parents: 14
diff changeset
33 return map->size * sizeof (SBITMAP_ELT_TYPE);
kono
parents: 14
diff changeset
34 }
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
35
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
36
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 /* Bitmap manipulation routines. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
38
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 /* Allocate a simple bitmap of N_ELMS bits. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
40
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 sbitmap
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 sbitmap_alloc (unsigned int n_elms)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 unsigned int bytes, size, amt;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 sbitmap bmap;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
46
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 size = SBITMAP_SET_SIZE (n_elms);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 bytes = size * sizeof (SBITMAP_ELT_TYPE);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
49 amt = (sizeof (struct simple_bitmap_def)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
50 + bytes - sizeof (SBITMAP_ELT_TYPE));
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
51 bmap = (sbitmap) xmalloc (amt);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 bmap->n_bits = n_elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 bmap->size = size;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 return bmap;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
56
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
57 /* Resize a simple bitmap BMAP to N_ELMS bits. If increasing the
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 size of BMAP, clear the new bits to zero if the DEF argument
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 is zero, and set them to one otherwise. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
60
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 sbitmap
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
62 sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
63 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 unsigned int bytes, size, amt;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
65 unsigned int last_bit;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
66
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
67 size = SBITMAP_SET_SIZE (n_elms);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 bytes = size * sizeof (SBITMAP_ELT_TYPE);
16
kono
parents: 14
diff changeset
69 if (bytes > sbitmap_size_bytes (bmap))
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
70 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 amt = (sizeof (struct simple_bitmap_def)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 + bytes - sizeof (SBITMAP_ELT_TYPE));
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 bmap = (sbitmap) xrealloc (bmap, amt);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
74 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
75
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
76 if (n_elms > bmap->n_bits)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
77 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
78 if (def)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
79 {
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
80 memset (bmap->elms + bmap->size, -1,
16
kono
parents: 14
diff changeset
81 bytes - sbitmap_size_bytes (bmap));
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
82
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
83 /* Set the new bits if the original last element. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
84 last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
85 if (last_bit)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
86 bmap->elms[bmap->size - 1]
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
87 |= ~((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
88
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
89 /* Clear the unused bit in the new last element. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
90 last_bit = n_elms % SBITMAP_ELT_BITS;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
91 if (last_bit)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
92 bmap->elms[size - 1]
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
93 &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
94 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
95 else
16
kono
parents: 14
diff changeset
96 memset (bmap->elms + bmap->size, 0, bytes - sbitmap_size_bytes (bmap));
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
97 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
98 else if (n_elms < bmap->n_bits)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
99 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
100 /* Clear the surplus bits in the last word. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
101 last_bit = n_elms % SBITMAP_ELT_BITS;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
102 if (last_bit)
16
kono
parents: 14
diff changeset
103 bmap->elms[size - 1]
kono
parents: 14
diff changeset
104 &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
105 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
106
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
107 bmap->n_bits = n_elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
108 bmap->size = size;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
109 return bmap;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
110 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
111
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
112 /* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
113
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
114 sbitmap
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
115 sbitmap_realloc (sbitmap src, unsigned int n_elms)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
116 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
117 unsigned int bytes, size, amt;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
118 sbitmap bmap;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
119
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
120 size = SBITMAP_SET_SIZE (n_elms);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
121 bytes = size * sizeof (SBITMAP_ELT_TYPE);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
122 amt = (sizeof (struct simple_bitmap_def)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
123 + bytes - sizeof (SBITMAP_ELT_TYPE));
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
124
16
kono
parents: 14
diff changeset
125 if (sbitmap_size_bytes (src) >= bytes)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
126 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
127 src->n_bits = n_elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
128 return src;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
129 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
130
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
131 bmap = (sbitmap) xrealloc (src, amt);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
132 bmap->n_bits = n_elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
133 bmap->size = size;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
134 return bmap;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
135 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
136
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
137 /* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
138
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
139 sbitmap *
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
140 sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
141 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
142 unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
143 sbitmap *bitmap_vector;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
144
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
145 size = SBITMAP_SET_SIZE (n_elms);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
146 bytes = size * sizeof (SBITMAP_ELT_TYPE);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
147 elm_bytes = (sizeof (struct simple_bitmap_def)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
148 + bytes - sizeof (SBITMAP_ELT_TYPE));
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
149 vector_bytes = n_vecs * sizeof (sbitmap *);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
150
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
151 /* Round up `vector_bytes' to account for the alignment requirements
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
152 of an sbitmap. One could allocate the vector-table and set of sbitmaps
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
153 separately, but that requires maintaining two pointers or creating
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
154 a cover struct to hold both pointers (so our result is still just
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
155 one pointer). Neither is a bad idea, but this is simpler for now. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
156 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
157 /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
158 struct { char x; SBITMAP_ELT_TYPE y; } align;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
159 int alignment = (char *) & align.y - & align.x;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
160 vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
161 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
162
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
163 amt = vector_bytes + (n_vecs * elm_bytes);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
164 bitmap_vector = (sbitmap *) xmalloc (amt);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
165
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
166 for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
167 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
168 sbitmap b = (sbitmap) ((char *) bitmap_vector + offset);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
169
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
170 bitmap_vector[i] = b;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
171 b->n_bits = n_elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
172 b->size = size;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
173 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
174
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
175 return bitmap_vector;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
176 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
177
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
178 /* Copy sbitmap SRC to DST. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
179
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
180 void
16
kono
parents: 14
diff changeset
181 bitmap_copy (sbitmap dst, const_sbitmap src)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
182 {
16
kono
parents: 14
diff changeset
183 gcc_checking_assert (src->size <= dst->size);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
184
16
kono
parents: 14
diff changeset
185 memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
186 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
187
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
188 /* Determine if a == b. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
189 int
16
kono
parents: 14
diff changeset
190 bitmap_equal_p (const_sbitmap a, const_sbitmap b)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
191 {
16
kono
parents: 14
diff changeset
192 bitmap_check_sizes (a, b);
kono
parents: 14
diff changeset
193
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
194 return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
195 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
196
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
197 /* Return true if the bitmap is empty. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
198
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
199 bool
16
kono
parents: 14
diff changeset
200 bitmap_empty_p (const_sbitmap bmap)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
201 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
202 unsigned int i;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
203 for (i=0; i<bmap->size; i++)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
204 if (bmap->elms[i])
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
205 return false;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
206
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
207 return true;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
208 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
209
16
kono
parents: 14
diff changeset
210 /* Clear COUNT bits from START in BMAP. */
kono
parents: 14
diff changeset
211
kono
parents: 14
diff changeset
212 void
kono
parents: 14
diff changeset
213 bitmap_clear_range (sbitmap bmap, unsigned int start, unsigned int count)
kono
parents: 14
diff changeset
214 {
kono
parents: 14
diff changeset
215 if (count == 0)
kono
parents: 14
diff changeset
216 return;
kono
parents: 14
diff changeset
217
kono
parents: 14
diff changeset
218 bitmap_check_index (bmap, start + count - 1);
kono
parents: 14
diff changeset
219
kono
parents: 14
diff changeset
220 unsigned int start_word = start / SBITMAP_ELT_BITS;
kono
parents: 14
diff changeset
221 unsigned int start_bitno = start % SBITMAP_ELT_BITS;
kono
parents: 14
diff changeset
222
kono
parents: 14
diff changeset
223 /* Clearing less than a full word, starting at the beginning of a word. */
kono
parents: 14
diff changeset
224 if (start_bitno == 0 && count < SBITMAP_ELT_BITS)
kono
parents: 14
diff changeset
225 {
kono
parents: 14
diff changeset
226 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
kono
parents: 14
diff changeset
227 bmap->elms[start_word] &= ~mask;
kono
parents: 14
diff changeset
228 return;
kono
parents: 14
diff changeset
229 }
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
230
16
kono
parents: 14
diff changeset
231 unsigned int end_word = (start + count) / SBITMAP_ELT_BITS;
kono
parents: 14
diff changeset
232 unsigned int end_bitno = (start + count) % SBITMAP_ELT_BITS;
kono
parents: 14
diff changeset
233
kono
parents: 14
diff changeset
234 /* Clearing starts somewhere in the middle of the first word. Clear up to
kono
parents: 14
diff changeset
235 the end of the first word or the end of the requested region, whichever
kono
parents: 14
diff changeset
236 comes first. */
kono
parents: 14
diff changeset
237 if (start_bitno != 0)
kono
parents: 14
diff changeset
238 {
kono
parents: 14
diff changeset
239 unsigned int nbits = ((start_word == end_word)
kono
parents: 14
diff changeset
240 ? end_bitno - start_bitno
kono
parents: 14
diff changeset
241 : SBITMAP_ELT_BITS - start_bitno);
kono
parents: 14
diff changeset
242 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1;
kono
parents: 14
diff changeset
243 mask <<= start_bitno;
kono
parents: 14
diff changeset
244 bmap->elms[start_word] &= ~mask;
kono
parents: 14
diff changeset
245 start_word++;
kono
parents: 14
diff changeset
246 count -= nbits;
kono
parents: 14
diff changeset
247 }
kono
parents: 14
diff changeset
248
kono
parents: 14
diff changeset
249 if (count == 0)
kono
parents: 14
diff changeset
250 return;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
251
16
kono
parents: 14
diff changeset
252 /* Now clear words at a time until we hit a partial word. */
kono
parents: 14
diff changeset
253 unsigned int nwords = (end_word - start_word);
kono
parents: 14
diff changeset
254 if (nwords)
kono
parents: 14
diff changeset
255 {
kono
parents: 14
diff changeset
256 memset (&bmap->elms[start_word], 0, nwords * sizeof (SBITMAP_ELT_TYPE));
kono
parents: 14
diff changeset
257 count -= nwords * sizeof (SBITMAP_ELT_TYPE) * BITS_PER_UNIT;
kono
parents: 14
diff changeset
258 start_word += nwords;
kono
parents: 14
diff changeset
259 }
kono
parents: 14
diff changeset
260
kono
parents: 14
diff changeset
261 if (count == 0)
kono
parents: 14
diff changeset
262 return;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
263
16
kono
parents: 14
diff changeset
264 /* Now handle residuals in the last word. */
kono
parents: 14
diff changeset
265 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
kono
parents: 14
diff changeset
266 bmap->elms[start_word] &= ~mask;
kono
parents: 14
diff changeset
267 }
kono
parents: 14
diff changeset
268
kono
parents: 14
diff changeset
269 /* Set COUNT bits from START in BMAP. */
kono
parents: 14
diff changeset
270 void
kono
parents: 14
diff changeset
271 bitmap_set_range (sbitmap bmap, unsigned int start, unsigned int count)
kono
parents: 14
diff changeset
272 {
kono
parents: 14
diff changeset
273 if (count == 0)
kono
parents: 14
diff changeset
274 return;
kono
parents: 14
diff changeset
275
kono
parents: 14
diff changeset
276 bitmap_check_index (bmap, start + count - 1);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
277
16
kono
parents: 14
diff changeset
278 unsigned int start_word = start / SBITMAP_ELT_BITS;
kono
parents: 14
diff changeset
279 unsigned int start_bitno = start % SBITMAP_ELT_BITS;
kono
parents: 14
diff changeset
280
kono
parents: 14
diff changeset
281 /* Setting less than a full word, starting at the beginning of a word. */
kono
parents: 14
diff changeset
282 if (start_bitno == 0 && count < SBITMAP_ELT_BITS)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
283 {
16
kono
parents: 14
diff changeset
284 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
kono
parents: 14
diff changeset
285 bmap->elms[start_word] |= mask;
kono
parents: 14
diff changeset
286 return;
kono
parents: 14
diff changeset
287 }
kono
parents: 14
diff changeset
288
kono
parents: 14
diff changeset
289 unsigned int end_word = (start + count) / SBITMAP_ELT_BITS;
kono
parents: 14
diff changeset
290 unsigned int end_bitno = (start + count) % SBITMAP_ELT_BITS;
kono
parents: 14
diff changeset
291
kono
parents: 14
diff changeset
292 /* Setting starts somewhere in the middle of the first word. Set up to
kono
parents: 14
diff changeset
293 the end of the first word or the end of the requested region, whichever
kono
parents: 14
diff changeset
294 comes first. */
kono
parents: 14
diff changeset
295 if (start_bitno != 0)
kono
parents: 14
diff changeset
296 {
kono
parents: 14
diff changeset
297 unsigned int nbits = ((start_word == end_word)
kono
parents: 14
diff changeset
298 ? end_bitno - start_bitno
kono
parents: 14
diff changeset
299 : SBITMAP_ELT_BITS - start_bitno);
kono
parents: 14
diff changeset
300 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1;
kono
parents: 14
diff changeset
301 mask <<= start_bitno;
kono
parents: 14
diff changeset
302 bmap->elms[start_word] |= mask;
kono
parents: 14
diff changeset
303 start_word++;
kono
parents: 14
diff changeset
304 count -= nbits;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
305 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
306
16
kono
parents: 14
diff changeset
307 if (count == 0)
kono
parents: 14
diff changeset
308 return;
kono
parents: 14
diff changeset
309
kono
parents: 14
diff changeset
310 /* Now set words at a time until we hit a partial word. */
kono
parents: 14
diff changeset
311 unsigned int nwords = (end_word - start_word);
kono
parents: 14
diff changeset
312 if (nwords)
kono
parents: 14
diff changeset
313 {
kono
parents: 14
diff changeset
314 memset (&bmap->elms[start_word], 0xff,
kono
parents: 14
diff changeset
315 nwords * sizeof (SBITMAP_ELT_TYPE));
kono
parents: 14
diff changeset
316 count -= nwords * sizeof (SBITMAP_ELT_TYPE) * BITS_PER_UNIT;
kono
parents: 14
diff changeset
317 start_word += nwords;
kono
parents: 14
diff changeset
318 }
kono
parents: 14
diff changeset
319
kono
parents: 14
diff changeset
320 if (count == 0)
kono
parents: 14
diff changeset
321 return;
kono
parents: 14
diff changeset
322
kono
parents: 14
diff changeset
323 /* Now handle residuals in the last word. */
kono
parents: 14
diff changeset
324 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
kono
parents: 14
diff changeset
325 bmap->elms[start_word] |= mask;
kono
parents: 14
diff changeset
326 }
kono
parents: 14
diff changeset
327
kono
parents: 14
diff changeset
328 /* Return TRUE if any bit between START and END inclusive is set within
kono
parents: 14
diff changeset
329 the simple bitmap BMAP. Return FALSE otherwise. */
kono
parents: 14
diff changeset
330
kono
parents: 14
diff changeset
331 bool
kono
parents: 14
diff changeset
332 bitmap_bit_in_range_p (const_sbitmap bmap, unsigned int start, unsigned int end)
kono
parents: 14
diff changeset
333 {
kono
parents: 14
diff changeset
334 gcc_checking_assert (start <= end);
kono
parents: 14
diff changeset
335 bitmap_check_index (bmap, end);
kono
parents: 14
diff changeset
336
kono
parents: 14
diff changeset
337 unsigned int start_word = start / SBITMAP_ELT_BITS;
kono
parents: 14
diff changeset
338 unsigned int start_bitno = start % SBITMAP_ELT_BITS;
kono
parents: 14
diff changeset
339
kono
parents: 14
diff changeset
340 unsigned int end_word = end / SBITMAP_ELT_BITS;
kono
parents: 14
diff changeset
341 unsigned int end_bitno = end % SBITMAP_ELT_BITS;
kono
parents: 14
diff changeset
342
kono
parents: 14
diff changeset
343 /* Check beginning of first word if different from zero. */
kono
parents: 14
diff changeset
344 if (start_bitno != 0)
kono
parents: 14
diff changeset
345 {
kono
parents: 14
diff changeset
346 SBITMAP_ELT_TYPE high_mask = ~(SBITMAP_ELT_TYPE)0;
kono
parents: 14
diff changeset
347 if (start_word == end_word && end_bitno + 1 < SBITMAP_ELT_BITS)
kono
parents: 14
diff changeset
348 high_mask = ((SBITMAP_ELT_TYPE)1 << (end_bitno + 1)) - 1;
kono
parents: 14
diff changeset
349
kono
parents: 14
diff changeset
350 SBITMAP_ELT_TYPE low_mask = ((SBITMAP_ELT_TYPE)1 << start_bitno) - 1;
kono
parents: 14
diff changeset
351 SBITMAP_ELT_TYPE mask = high_mask - low_mask;
kono
parents: 14
diff changeset
352 if (bmap->elms[start_word] & mask)
kono
parents: 14
diff changeset
353 return true;
kono
parents: 14
diff changeset
354 start_word++;
kono
parents: 14
diff changeset
355 }
kono
parents: 14
diff changeset
356
kono
parents: 14
diff changeset
357 if (start_word > end_word)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
358 return false;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
359
16
kono
parents: 14
diff changeset
360 /* Now test words at a time until we hit a partial word. */
kono
parents: 14
diff changeset
361 unsigned int nwords = (end_word - start_word);
kono
parents: 14
diff changeset
362 while (nwords)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
363 {
16
kono
parents: 14
diff changeset
364 if (bmap->elms[start_word])
kono
parents: 14
diff changeset
365 return true;
kono
parents: 14
diff changeset
366 start_word++;
kono
parents: 14
diff changeset
367 nwords--;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
368 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
369
16
kono
parents: 14
diff changeset
370 /* Now handle residuals in the last word. */
kono
parents: 14
diff changeset
371 SBITMAP_ELT_TYPE mask = ~(SBITMAP_ELT_TYPE)0;
kono
parents: 14
diff changeset
372 if (end_bitno + 1 < SBITMAP_ELT_BITS)
kono
parents: 14
diff changeset
373 mask = ((SBITMAP_ELT_TYPE)1 << (end_bitno + 1)) - 1;
kono
parents: 14
diff changeset
374 return (bmap->elms[start_word] & mask) != 0;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
375 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
376
16
kono
parents: 14
diff changeset
377 #if GCC_VERSION < 3400
kono
parents: 14
diff changeset
378 /* Table of number of set bits in a character, indexed by value of char. */
kono
parents: 14
diff changeset
379 static const unsigned char popcount_table[] =
kono
parents: 14
diff changeset
380 {
kono
parents: 14
diff changeset
381 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,
kono
parents: 14
diff changeset
382 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,
kono
parents: 14
diff changeset
383 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,
kono
parents: 14
diff changeset
384 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,
kono
parents: 14
diff changeset
385 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,
kono
parents: 14
diff changeset
386 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,
kono
parents: 14
diff changeset
387 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,
kono
parents: 14
diff changeset
388 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,
kono
parents: 14
diff changeset
389 };
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
390
16
kono
parents: 14
diff changeset
391 static unsigned long
kono
parents: 14
diff changeset
392 sbitmap_popcount (SBITMAP_ELT_TYPE a)
kono
parents: 14
diff changeset
393 {
kono
parents: 14
diff changeset
394 unsigned long ret = 0;
kono
parents: 14
diff changeset
395 unsigned i;
kono
parents: 14
diff changeset
396
kono
parents: 14
diff changeset
397 /* Just do this the table way for now */
kono
parents: 14
diff changeset
398 for (i = 0; i < HOST_BITS_PER_WIDEST_FAST_INT; i += 8)
kono
parents: 14
diff changeset
399 ret += popcount_table[(a >> i) & 0xff];
kono
parents: 14
diff changeset
400 return ret;
kono
parents: 14
diff changeset
401 }
kono
parents: 14
diff changeset
402 #endif
kono
parents: 14
diff changeset
403
kono
parents: 14
diff changeset
404 /* Count and return the number of bits set in the bitmap BMAP. */
kono
parents: 14
diff changeset
405
kono
parents: 14
diff changeset
406 unsigned int
kono
parents: 14
diff changeset
407 bitmap_count_bits (const_sbitmap bmap)
kono
parents: 14
diff changeset
408 {
kono
parents: 14
diff changeset
409 unsigned int count = 0;
kono
parents: 14
diff changeset
410 for (unsigned int i = 0; i < bmap->size; i++)
kono
parents: 14
diff changeset
411 if (bmap->elms[i])
kono
parents: 14
diff changeset
412 {
kono
parents: 14
diff changeset
413 #if GCC_VERSION < 3400
kono
parents: 14
diff changeset
414 count += sbitmap_popcount (bmap->elms[i]);
kono
parents: 14
diff changeset
415 #else
kono
parents: 14
diff changeset
416 # if HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONG
kono
parents: 14
diff changeset
417 count += __builtin_popcountl (bmap->elms[i]);
kono
parents: 14
diff changeset
418 # elif HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONGLONG
kono
parents: 14
diff changeset
419 count += __builtin_popcountll (bmap->elms[i]);
kono
parents: 14
diff changeset
420 # else
kono
parents: 14
diff changeset
421 count += __builtin_popcount (bmap->elms[i]);
kono
parents: 14
diff changeset
422 # endif
kono
parents: 14
diff changeset
423 #endif
kono
parents: 14
diff changeset
424 }
kono
parents: 14
diff changeset
425 return count;
kono
parents: 14
diff changeset
426 }
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
427
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
428 /* Zero all elements in a bitmap. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
429
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
430 void
16
kono
parents: 14
diff changeset
431 bitmap_clear (sbitmap bmap)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
432 {
16
kono
parents: 14
diff changeset
433 memset (bmap->elms, 0, sbitmap_size_bytes (bmap));
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
434 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
435
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
436 /* Set all elements in a bitmap to ones. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
437
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
438 void
16
kono
parents: 14
diff changeset
439 bitmap_ones (sbitmap bmap)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
440 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
441 unsigned int last_bit;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
442
16
kono
parents: 14
diff changeset
443 memset (bmap->elms, -1, sbitmap_size_bytes (bmap));
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
444
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
445 last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
446 if (last_bit)
16
kono
parents: 14
diff changeset
447 bmap->elms[bmap->size - 1]
kono
parents: 14
diff changeset
448 = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
449 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
450
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
451 /* Zero a vector of N_VECS bitmaps. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
452
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
453 void
16
kono
parents: 14
diff changeset
454 bitmap_vector_clear (sbitmap *bmap, unsigned int n_vecs)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
455 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
456 unsigned int i;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
457
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
458 for (i = 0; i < n_vecs; i++)
16
kono
parents: 14
diff changeset
459 bitmap_clear (bmap[i]);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
460 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
461
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
462 /* Set a vector of N_VECS bitmaps to ones. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
463
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
464 void
16
kono
parents: 14
diff changeset
465 bitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
466 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
467 unsigned int i;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
468
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
469 for (i = 0; i < n_vecs; i++)
16
kono
parents: 14
diff changeset
470 bitmap_ones (bmap[i]);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
471 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
472
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
473 /* Set DST to be A union (B - C).
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
474 DST = A | (B & ~C).
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
475 Returns true if any change is made. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
476
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
477 bool
16
kono
parents: 14
diff changeset
478 bitmap_ior_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
479 {
16
kono
parents: 14
diff changeset
480 bitmap_check_sizes (a, b);
kono
parents: 14
diff changeset
481 bitmap_check_sizes (b, c);
kono
parents: 14
diff changeset
482
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
483 unsigned int i, n = dst->size;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
484 sbitmap_ptr dstp = dst->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
485 const_sbitmap_ptr ap = a->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
486 const_sbitmap_ptr bp = b->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
487 const_sbitmap_ptr cp = c->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
488 SBITMAP_ELT_TYPE changed = 0;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
489
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
490 for (i = 0; i < n; i++)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
491 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
492 const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
493 changed |= *dstp ^ tmp;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
494 *dstp++ = tmp;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
495 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
496
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
497 return changed != 0;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
498 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
499
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
500 /* Set bitmap DST to the bitwise negation of the bitmap SRC. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
501
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
502 void
16
kono
parents: 14
diff changeset
503 bitmap_not (sbitmap dst, const_sbitmap src)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
504 {
16
kono
parents: 14
diff changeset
505 bitmap_check_sizes (src, dst);
kono
parents: 14
diff changeset
506
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
507 unsigned int i, n = dst->size;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
508 sbitmap_ptr dstp = dst->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
509 const_sbitmap_ptr srcp = src->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
510 unsigned int last_bit;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
511
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
512 for (i = 0; i < n; i++)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
513 *dstp++ = ~*srcp++;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
514
16
kono
parents: 14
diff changeset
515 /* Zero all bits past n_bits, by ANDing dst with bitmap_ones. */
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
516 last_bit = src->n_bits % SBITMAP_ELT_BITS;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
517 if (last_bit)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
518 dst->elms[n-1] = dst->elms[n-1]
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
519 & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
520 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
521
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
522 /* Set the bits in DST to be the difference between the bits
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
523 in A and the bits in B. i.e. dst = a & (~b). */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
524
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
525 void
16
kono
parents: 14
diff changeset
526 bitmap_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
527 {
16
kono
parents: 14
diff changeset
528 bitmap_check_sizes (a, b);
kono
parents: 14
diff changeset
529 bitmap_check_sizes (b, dst);
kono
parents: 14
diff changeset
530
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
531 unsigned int i, dst_size = dst->size;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
532 unsigned int min_size = dst->size;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
533 sbitmap_ptr dstp = dst->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
534 const_sbitmap_ptr ap = a->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
535 const_sbitmap_ptr bp = b->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
536
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
537 /* A should be at least as large as DEST, to have a defined source. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
538 gcc_assert (a->size >= dst_size);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
539 /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
540 only copy the subtrahend into dest. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
541 if (b->size < min_size)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
542 min_size = b->size;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
543 for (i = 0; i < min_size; i++)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
544 *dstp++ = *ap++ & (~*bp++);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
545 /* Now fill the rest of dest from A, if B was too short.
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
546 This makes sense only when destination and A differ. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
547 if (dst != a && i != dst_size)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
548 for (; i < dst_size; i++)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
549 *dstp++ = *ap++;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
550 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
551
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
552 /* Return true if there are any bits set in A are also set in B.
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
553 Return false otherwise. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
554
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
555 bool
16
kono
parents: 14
diff changeset
556 bitmap_intersect_p (const_sbitmap a, const_sbitmap b)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
557 {
16
kono
parents: 14
diff changeset
558 bitmap_check_sizes (a, b);
kono
parents: 14
diff changeset
559
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
560 const_sbitmap_ptr ap = a->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
561 const_sbitmap_ptr bp = b->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
562 unsigned int i, n;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
563
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
564 n = MIN (a->size, b->size);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
565 for (i = 0; i < n; i++)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
566 if ((*ap++ & *bp++) != 0)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
567 return true;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
568
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
569 return false;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
570 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
571
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
572 /* Set DST to be (A and B).
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
573 Return nonzero if any change is made. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
574
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
575 bool
16
kono
parents: 14
diff changeset
576 bitmap_and (sbitmap dst, const_sbitmap a, const_sbitmap b)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
577 {
16
kono
parents: 14
diff changeset
578 bitmap_check_sizes (a, b);
kono
parents: 14
diff changeset
579 bitmap_check_sizes (b, dst);
kono
parents: 14
diff changeset
580
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
581 unsigned int i, n = dst->size;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
582 sbitmap_ptr dstp = dst->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
583 const_sbitmap_ptr ap = a->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
584 const_sbitmap_ptr bp = b->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
585 SBITMAP_ELT_TYPE changed = 0;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
586
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
587 for (i = 0; i < n; i++)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
588 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
589 const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
16
kono
parents: 14
diff changeset
590 SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
591 *dstp++ = tmp;
16
kono
parents: 14
diff changeset
592 changed |= wordchanged;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
593 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
594 return changed != 0;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
595 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
596
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
597 /* Set DST to be (A xor B)).
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
598 Return nonzero if any change is made. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
599
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
600 bool
16
kono
parents: 14
diff changeset
601 bitmap_xor (sbitmap dst, const_sbitmap a, const_sbitmap b)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
602 {
16
kono
parents: 14
diff changeset
603 bitmap_check_sizes (a, b);
kono
parents: 14
diff changeset
604 bitmap_check_sizes (b, dst);
kono
parents: 14
diff changeset
605
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
606 unsigned int i, n = dst->size;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
607 sbitmap_ptr dstp = dst->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
608 const_sbitmap_ptr ap = a->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
609 const_sbitmap_ptr bp = b->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
610 SBITMAP_ELT_TYPE changed = 0;
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
611
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
612 for (i = 0; i < n; i++)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
613 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
614 const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
16
kono
parents: 14
diff changeset
615 SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
616 *dstp++ = tmp;
16
kono
parents: 14
diff changeset
617 changed |= wordchanged;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
618 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
619 return changed != 0;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
620 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
621
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
622 /* Set DST to be (A or B)).
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
623 Return nonzero if any change is made. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
624
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
625 bool
16
kono
parents: 14
diff changeset
626 bitmap_ior (sbitmap dst, const_sbitmap a, const_sbitmap b)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
627 {
16
kono
parents: 14
diff changeset
628 bitmap_check_sizes (a, b);
kono
parents: 14
diff changeset
629 bitmap_check_sizes (b, dst);
kono
parents: 14
diff changeset
630
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
631 unsigned int i, n = dst->size;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
632 sbitmap_ptr dstp = dst->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
633 const_sbitmap_ptr ap = a->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
634 const_sbitmap_ptr bp = b->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
635 SBITMAP_ELT_TYPE changed = 0;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
636
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
637 for (i = 0; i < n; i++)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
638 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
639 const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
16
kono
parents: 14
diff changeset
640 SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
641 *dstp++ = tmp;
16
kono
parents: 14
diff changeset
642 changed |= wordchanged;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
643 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
644 return changed != 0;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
645 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
646
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
647 /* Return nonzero if A is a subset of B. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
648
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
649 bool
16
kono
parents: 14
diff changeset
650 bitmap_subset_p (const_sbitmap a, const_sbitmap b)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
651 {
16
kono
parents: 14
diff changeset
652 bitmap_check_sizes (a, b);
kono
parents: 14
diff changeset
653
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
654 unsigned int i, n = a->size;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
655 const_sbitmap_ptr ap, bp;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
656
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
657 for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
658 if ((*ap | *bp) != *bp)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
659 return false;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
660
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
661 return true;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
662 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
663
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
664 /* Set DST to be (A or (B and C)).
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
665 Return nonzero if any change is made. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
666
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
667 bool
16
kono
parents: 14
diff changeset
668 bitmap_or_and (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
669 {
16
kono
parents: 14
diff changeset
670 bitmap_check_sizes (a, b);
kono
parents: 14
diff changeset
671 bitmap_check_sizes (b, c);
kono
parents: 14
diff changeset
672 bitmap_check_sizes (c, dst);
kono
parents: 14
diff changeset
673
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
674 unsigned int i, n = dst->size;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
675 sbitmap_ptr dstp = dst->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
676 const_sbitmap_ptr ap = a->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
677 const_sbitmap_ptr bp = b->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
678 const_sbitmap_ptr cp = c->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
679 SBITMAP_ELT_TYPE changed = 0;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
680
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
681 for (i = 0; i < n; i++)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
682 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
683 const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
684 changed |= *dstp ^ tmp;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
685 *dstp++ = tmp;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
686 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
687
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
688 return changed != 0;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
689 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
690
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
691 /* Set DST to be (A and (B or C)).
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
692 Return nonzero if any change is made. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
693
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
694 bool
16
kono
parents: 14
diff changeset
695 bitmap_and_or (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
696 {
16
kono
parents: 14
diff changeset
697 bitmap_check_sizes (a, b);
kono
parents: 14
diff changeset
698 bitmap_check_sizes (b, c);
kono
parents: 14
diff changeset
699 bitmap_check_sizes (c, dst);
kono
parents: 14
diff changeset
700
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
701 unsigned int i, n = dst->size;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
702 sbitmap_ptr dstp = dst->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
703 const_sbitmap_ptr ap = a->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
704 const_sbitmap_ptr bp = b->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
705 const_sbitmap_ptr cp = c->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
706 SBITMAP_ELT_TYPE changed = 0;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
707
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
708 for (i = 0; i < n; i++)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
709 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
710 const SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
711 changed |= *dstp ^ tmp;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
712 *dstp++ = tmp;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
713 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
714
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
715 return changed != 0;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
716 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
717
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
718 /* Return number of first bit set in the bitmap, -1 if none. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
719
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
720 int
16
kono
parents: 14
diff changeset
721 bitmap_first_set_bit (const_sbitmap bmap)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
722 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
723 unsigned int n = 0;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
724 sbitmap_iterator sbi;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
725
16
kono
parents: 14
diff changeset
726 EXECUTE_IF_SET_IN_BITMAP (bmap, 0, n, sbi)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
727 return n;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
728 return -1;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
729 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
730
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
731 /* Return number of last bit set in the bitmap, -1 if none. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
732
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
733 int
16
kono
parents: 14
diff changeset
734 bitmap_last_set_bit (const_sbitmap bmap)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
735 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
736 int i;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
737 const SBITMAP_ELT_TYPE *const ptr = bmap->elms;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
738
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
739 for (i = bmap->size - 1; i >= 0; i--)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
740 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
741 const SBITMAP_ELT_TYPE word = ptr[i];
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
742
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
743 if (word != 0)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
744 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
745 unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
746 SBITMAP_ELT_TYPE mask
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
747 = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
748
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
749 while (1)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
750 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
751 if ((word & mask) != 0)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
752 return index;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
753
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
754 mask >>= 1;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
755 index--;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
756 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
757 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
758 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
759
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
760 return -1;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
761 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
762
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
763 void
16
kono
parents: 14
diff changeset
764 dump_bitmap (FILE *file, const_sbitmap bmap)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
765 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
766 unsigned int i, n, j;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
767 unsigned int set_size = bmap->size;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
768 unsigned int total_bits = bmap->n_bits;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
769
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
770 fprintf (file, " ");
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
771 for (i = n = 0; i < set_size && n < total_bits; i++)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
772 for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
773 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
774 if (n != 0 && n % 10 == 0)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
775 fprintf (file, " ");
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
776
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
777 fprintf (file, "%d",
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
778 (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
779 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
780
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
781 fprintf (file, "\n");
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
782 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
783
16
kono
parents: 14
diff changeset
784 DEBUG_FUNCTION void
kono
parents: 14
diff changeset
785 debug_raw (simple_bitmap_def &ref)
kono
parents: 14
diff changeset
786 {
kono
parents: 14
diff changeset
787 dump_bitmap (stderr, &ref);
kono
parents: 14
diff changeset
788 }
kono
parents: 14
diff changeset
789
kono
parents: 14
diff changeset
790 DEBUG_FUNCTION void
kono
parents: 14
diff changeset
791 debug_raw (simple_bitmap_def *ptr)
kono
parents: 14
diff changeset
792 {
kono
parents: 14
diff changeset
793 if (ptr)
kono
parents: 14
diff changeset
794 debug_raw (*ptr);
kono
parents: 14
diff changeset
795 else
kono
parents: 14
diff changeset
796 fprintf (stderr, "<nil>\n");
kono
parents: 14
diff changeset
797 }
kono
parents: 14
diff changeset
798
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
799 void
16
kono
parents: 14
diff changeset
800 dump_bitmap_file (FILE *file, const_sbitmap bmap)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
801 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
802 unsigned int i, pos;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
803
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
804 fprintf (file, "n_bits = %d, set = {", bmap->n_bits);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
805
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
806 for (pos = 30, i = 0; i < bmap->n_bits; i++)
16
kono
parents: 14
diff changeset
807 if (bitmap_bit_p (bmap, i))
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
808 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
809 if (pos > 70)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
810 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
811 fprintf (file, "\n ");
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
812 pos = 0;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
813 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
814
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
815 fprintf (file, "%d ", i);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
816 pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
817 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
818
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
819 fprintf (file, "}\n");
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
820 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
821
14
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
822 DEBUG_FUNCTION void
16
kono
parents: 14
diff changeset
823 debug_bitmap (const_sbitmap bmap)
kono
parents: 14
diff changeset
824 {
kono
parents: 14
diff changeset
825 dump_bitmap_file (stderr, bmap);
kono
parents: 14
diff changeset
826 }
kono
parents: 14
diff changeset
827
kono
parents: 14
diff changeset
828 DEBUG_FUNCTION void
kono
parents: 14
diff changeset
829 debug (simple_bitmap_def &ref)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
830 {
16
kono
parents: 14
diff changeset
831 dump_bitmap_file (stderr, &ref);
kono
parents: 14
diff changeset
832 }
kono
parents: 14
diff changeset
833
kono
parents: 14
diff changeset
834 DEBUG_FUNCTION void
kono
parents: 14
diff changeset
835 debug (simple_bitmap_def *ptr)
kono
parents: 14
diff changeset
836 {
kono
parents: 14
diff changeset
837 if (ptr)
kono
parents: 14
diff changeset
838 debug (*ptr);
kono
parents: 14
diff changeset
839 else
kono
parents: 14
diff changeset
840 fprintf (stderr, "<nil>\n");
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
841 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
842
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
843 void
16
kono
parents: 14
diff changeset
844 dump_bitmap_vector (FILE *file, const char *title, const char *subtitle,
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
845 sbitmap *bmaps, int n_maps)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
846 {
16
kono
parents: 14
diff changeset
847 int i;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
848
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
849 fprintf (file, "%s\n", title);
16
kono
parents: 14
diff changeset
850 for (i = 0; i < n_maps; i++)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
851 {
16
kono
parents: 14
diff changeset
852 fprintf (file, "%s %d\n", subtitle, i);
kono
parents: 14
diff changeset
853 dump_bitmap (file, bmaps[i]);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
854 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
855
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
856 fprintf (file, "\n");
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
857 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
858
16
kono
parents: 14
diff changeset
859 #if CHECKING_P
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
860
16
kono
parents: 14
diff changeset
861 namespace selftest {
kono
parents: 14
diff changeset
862
kono
parents: 14
diff changeset
863 /* Selftests for sbitmaps. */
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
864
16
kono
parents: 14
diff changeset
865 /* Checking function that uses both bitmap_bit_in_range_p and
kono
parents: 14
diff changeset
866 loop of bitmap_bit_p and verifies consistent results. */
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
867
16
kono
parents: 14
diff changeset
868 static bool
kono
parents: 14
diff changeset
869 bitmap_bit_in_range_p_checking (sbitmap s, unsigned int start,
kono
parents: 14
diff changeset
870 unsigned end)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
871 {
16
kono
parents: 14
diff changeset
872 bool r1 = bitmap_bit_in_range_p (s, start, end);
kono
parents: 14
diff changeset
873 bool r2 = false;
kono
parents: 14
diff changeset
874
kono
parents: 14
diff changeset
875 for (unsigned int i = start; i <= end; i++)
kono
parents: 14
diff changeset
876 if (bitmap_bit_p (s, i))
kono
parents: 14
diff changeset
877 {
kono
parents: 14
diff changeset
878 r2 = true;
kono
parents: 14
diff changeset
879 break;
kono
parents: 14
diff changeset
880 }
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
881
16
kono
parents: 14
diff changeset
882 ASSERT_EQ (r1, r2);
kono
parents: 14
diff changeset
883 return r1;
kono
parents: 14
diff changeset
884 }
kono
parents: 14
diff changeset
885
kono
parents: 14
diff changeset
886 /* Verify bitmap_set_range functions for sbitmap. */
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
887
16
kono
parents: 14
diff changeset
888 static void
kono
parents: 14
diff changeset
889 test_set_range ()
kono
parents: 14
diff changeset
890 {
kono
parents: 14
diff changeset
891 sbitmap s = sbitmap_alloc (16);
kono
parents: 14
diff changeset
892 bitmap_clear (s);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
893
16
kono
parents: 14
diff changeset
894 bitmap_set_range (s, 0, 1);
kono
parents: 14
diff changeset
895 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 0, 0));
kono
parents: 14
diff changeset
896 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 1, 15));
kono
parents: 14
diff changeset
897 bitmap_set_range (s, 15, 1);
kono
parents: 14
diff changeset
898 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 1, 14));
kono
parents: 14
diff changeset
899 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 15, 15));
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
900
16
kono
parents: 14
diff changeset
901 s = sbitmap_alloc (1024);
kono
parents: 14
diff changeset
902 bitmap_clear (s);
kono
parents: 14
diff changeset
903 bitmap_set_range (s, 512, 1);
kono
parents: 14
diff changeset
904 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 0, 511));
kono
parents: 14
diff changeset
905 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 513, 1023));
kono
parents: 14
diff changeset
906 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 512, 512));
kono
parents: 14
diff changeset
907 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 508, 512));
kono
parents: 14
diff changeset
908 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 508, 513));
kono
parents: 14
diff changeset
909 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 508, 511));
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
910
16
kono
parents: 14
diff changeset
911 bitmap_clear (s);
kono
parents: 14
diff changeset
912 bitmap_set_range (s, 512, 64);
kono
parents: 14
diff changeset
913 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 0, 511));
kono
parents: 14
diff changeset
914 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 512 + 64, 1023));
kono
parents: 14
diff changeset
915 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 512, 512));
kono
parents: 14
diff changeset
916 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 512 + 63, 512 + 63));
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
917 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
918
16
kono
parents: 14
diff changeset
919 /* Verify bitmap_bit_in_range_p functions for sbitmap. */
kono
parents: 14
diff changeset
920
kono
parents: 14
diff changeset
921 static void
kono
parents: 14
diff changeset
922 test_bit_in_range ()
kono
parents: 14
diff changeset
923 {
kono
parents: 14
diff changeset
924 sbitmap s = sbitmap_alloc (1024);
kono
parents: 14
diff changeset
925 bitmap_clear (s);
kono
parents: 14
diff changeset
926
kono
parents: 14
diff changeset
927 ASSERT_FALSE (bitmap_bit_in_range_p (s, 512, 1023));
kono
parents: 14
diff changeset
928 bitmap_set_bit (s, 100);
kono
parents: 14
diff changeset
929
kono
parents: 14
diff changeset
930 ASSERT_FALSE (bitmap_bit_in_range_p (s, 512, 1023));
kono
parents: 14
diff changeset
931 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 99));
kono
parents: 14
diff changeset
932 ASSERT_FALSE (bitmap_bit_in_range_p (s, 101, 1023));
kono
parents: 14
diff changeset
933 ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 100));
kono
parents: 14
diff changeset
934 ASSERT_TRUE (bitmap_bit_in_range_p (s, 64, 100));
kono
parents: 14
diff changeset
935 ASSERT_TRUE (bitmap_bit_in_range_p (s, 100, 100));
kono
parents: 14
diff changeset
936 ASSERT_TRUE (bitmap_bit_p (s, 100));
kono
parents: 14
diff changeset
937
kono
parents: 14
diff changeset
938 s = sbitmap_alloc (64);
kono
parents: 14
diff changeset
939 bitmap_clear (s);
kono
parents: 14
diff changeset
940 bitmap_set_bit (s, 63);
kono
parents: 14
diff changeset
941 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 63));
kono
parents: 14
diff changeset
942 ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 63));
kono
parents: 14
diff changeset
943 ASSERT_TRUE (bitmap_bit_in_range_p (s, 63, 63));
kono
parents: 14
diff changeset
944 ASSERT_TRUE (bitmap_bit_p (s, 63));
kono
parents: 14
diff changeset
945
kono
parents: 14
diff changeset
946 s = sbitmap_alloc (1024);
kono
parents: 14
diff changeset
947 bitmap_clear (s);
kono
parents: 14
diff changeset
948 bitmap_set_bit (s, 128);
kono
parents: 14
diff changeset
949 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 127));
kono
parents: 14
diff changeset
950 ASSERT_FALSE (bitmap_bit_in_range_p (s, 129, 1023));
kono
parents: 14
diff changeset
951
kono
parents: 14
diff changeset
952 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 128));
kono
parents: 14
diff changeset
953 ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 128));
kono
parents: 14
diff changeset
954 ASSERT_TRUE (bitmap_bit_in_range_p (s, 128, 255));
kono
parents: 14
diff changeset
955 ASSERT_TRUE (bitmap_bit_in_range_p (s, 128, 254));
kono
parents: 14
diff changeset
956 ASSERT_TRUE (bitmap_bit_p (s, 128));
kono
parents: 14
diff changeset
957
kono
parents: 14
diff changeset
958 bitmap_clear (s);
kono
parents: 14
diff changeset
959 bitmap_set_bit (s, 8);
kono
parents: 14
diff changeset
960 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 8));
kono
parents: 14
diff changeset
961 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 12));
kono
parents: 14
diff changeset
962 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 63));
kono
parents: 14
diff changeset
963 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 127));
kono
parents: 14
diff changeset
964 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 512));
kono
parents: 14
diff changeset
965 ASSERT_TRUE (bitmap_bit_in_range_p (s, 8, 8));
kono
parents: 14
diff changeset
966 ASSERT_TRUE (bitmap_bit_p (s, 8));
kono
parents: 14
diff changeset
967
kono
parents: 14
diff changeset
968 bitmap_clear (s);
kono
parents: 14
diff changeset
969 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 0));
kono
parents: 14
diff changeset
970 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 8));
kono
parents: 14
diff changeset
971 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 63));
kono
parents: 14
diff changeset
972 ASSERT_FALSE (bitmap_bit_in_range_p (s, 1, 63));
kono
parents: 14
diff changeset
973 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 256));
kono
parents: 14
diff changeset
974
kono
parents: 14
diff changeset
975 bitmap_set_bit (s, 0);
kono
parents: 14
diff changeset
976 bitmap_set_bit (s, 16);
kono
parents: 14
diff changeset
977 bitmap_set_bit (s, 32);
kono
parents: 14
diff changeset
978 bitmap_set_bit (s, 48);
kono
parents: 14
diff changeset
979 bitmap_set_bit (s, 64);
kono
parents: 14
diff changeset
980 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 0));
kono
parents: 14
diff changeset
981 ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 16));
kono
parents: 14
diff changeset
982 ASSERT_TRUE (bitmap_bit_in_range_p (s, 48, 63));
kono
parents: 14
diff changeset
983 ASSERT_TRUE (bitmap_bit_in_range_p (s, 64, 64));
kono
parents: 14
diff changeset
984 ASSERT_FALSE (bitmap_bit_in_range_p (s, 1, 15));
kono
parents: 14
diff changeset
985 ASSERT_FALSE (bitmap_bit_in_range_p (s, 17, 31));
kono
parents: 14
diff changeset
986 ASSERT_FALSE (bitmap_bit_in_range_p (s, 49, 63));
kono
parents: 14
diff changeset
987 ASSERT_FALSE (bitmap_bit_in_range_p (s, 65, 1023));
kono
parents: 14
diff changeset
988 }
kono
parents: 14
diff changeset
989
kono
parents: 14
diff changeset
990 /* Run all of the selftests within this file. */
kono
parents: 14
diff changeset
991
kono
parents: 14
diff changeset
992 void
kono
parents: 14
diff changeset
993 sbitmap_c_tests ()
kono
parents: 14
diff changeset
994 {
kono
parents: 14
diff changeset
995 test_set_range ();
kono
parents: 14
diff changeset
996 test_bit_in_range ();
kono
parents: 14
diff changeset
997 }
kono
parents: 14
diff changeset
998
kono
parents: 14
diff changeset
999 } // namespace selftest
kono
parents: 14
diff changeset
1000 #endif /* CHECKING_P */