2 * Copyright 2013, GitHub, Inc
3 * Copyright 2009-2013, Daniel Lemire, Cliff Moon,
4 * David McIntosh, Robert Becho, Google Inc. and Veronika Zenz
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 2
9 * of the License, or (at your option) any later version.
11 * This program 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.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, see <http://www.gnu.org/licenses/>.
22 #define EWAH_MASK(x) ((eword_t)1 << (x % BITS_IN_EWORD))
23 #define EWAH_BLOCK(x) (x / BITS_IN_EWORD)
25 struct bitmap
*bitmap_new(void)
27 struct bitmap
*bitmap
= xmalloc(sizeof(struct bitmap
));
28 bitmap
->words
= xcalloc(32, sizeof(eword_t
));
29 bitmap
->word_alloc
= 32;
33 void bitmap_set(struct bitmap
*self
, size_t pos
)
35 size_t block
= EWAH_BLOCK(pos
);
37 if (block
>= self
->word_alloc
) {
38 size_t old_size
= self
->word_alloc
;
39 self
->word_alloc
= block
* 2;
40 REALLOC_ARRAY(self
->words
, self
->word_alloc
);
41 memset(self
->words
+ old_size
, 0x0,
42 (self
->word_alloc
- old_size
) * sizeof(eword_t
));
45 self
->words
[block
] |= EWAH_MASK(pos
);
48 int bitmap_get(struct bitmap
*self
, size_t pos
)
50 size_t block
= EWAH_BLOCK(pos
);
51 return block
< self
->word_alloc
&&
52 (self
->words
[block
] & EWAH_MASK(pos
)) != 0;
55 struct ewah_bitmap
*bitmap_to_ewah(struct bitmap
*bitmap
)
57 struct ewah_bitmap
*ewah
= ewah_new();
58 size_t i
, running_empty_words
= 0;
59 eword_t last_word
= 0;
61 for (i
= 0; i
< bitmap
->word_alloc
; ++i
) {
62 if (bitmap
->words
[i
] == 0) {
63 running_empty_words
++;
68 ewah_add(ewah
, last_word
);
70 if (running_empty_words
> 0) {
71 ewah_add_empty_words(ewah
, 0, running_empty_words
);
72 running_empty_words
= 0;
75 last_word
= bitmap
->words
[i
];
78 ewah_add(ewah
, last_word
);
82 struct bitmap
*ewah_to_bitmap(struct ewah_bitmap
*ewah
)
84 struct bitmap
*bitmap
= bitmap_new();
85 struct ewah_iterator it
;
89 ewah_iterator_init(&it
, ewah
);
91 while (ewah_iterator_next(&blowup
, &it
)) {
92 ALLOC_GROW(bitmap
->words
, i
+ 1, bitmap
->word_alloc
);
93 bitmap
->words
[i
++] = blowup
;
96 bitmap
->word_alloc
= i
;
100 void bitmap_and_not(struct bitmap
*self
, struct bitmap
*other
)
102 const size_t count
= (self
->word_alloc
< other
->word_alloc
) ?
103 self
->word_alloc
: other
->word_alloc
;
107 for (i
= 0; i
< count
; ++i
)
108 self
->words
[i
] &= ~other
->words
[i
];
111 void bitmap_or_ewah(struct bitmap
*self
, struct ewah_bitmap
*other
)
113 size_t original_size
= self
->word_alloc
;
114 size_t other_final
= (other
->bit_size
/ BITS_IN_EWORD
) + 1;
116 struct ewah_iterator it
;
119 if (self
->word_alloc
< other_final
) {
120 self
->word_alloc
= other_final
;
121 REALLOC_ARRAY(self
->words
, self
->word_alloc
);
122 memset(self
->words
+ original_size
, 0x0,
123 (self
->word_alloc
- original_size
) * sizeof(eword_t
));
126 ewah_iterator_init(&it
, other
);
128 while (ewah_iterator_next(&word
, &it
))
129 self
->words
[i
++] |= word
;
132 size_t bitmap_popcount(struct bitmap
*self
)
136 for (i
= 0; i
< self
->word_alloc
; ++i
)
137 count
+= ewah_bit_popcount64(self
->words
[i
]);
142 int bitmap_equals(struct bitmap
*self
, struct bitmap
*other
)
144 struct bitmap
*big
, *small
;
147 if (self
->word_alloc
< other
->word_alloc
) {
155 for (i
= 0; i
< small
->word_alloc
; ++i
) {
156 if (small
->words
[i
] != big
->words
[i
])
160 for (; i
< big
->word_alloc
; ++i
) {
161 if (big
->words
[i
] != 0)
168 void bitmap_reset(struct bitmap
*bitmap
)
170 memset(bitmap
->words
, 0x0, bitmap
->word_alloc
* sizeof(eword_t
));
173 void bitmap_free(struct bitmap
*bitmap
)