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/>.
19 #ifndef __EWOK_BITMAP_H__
20 #define __EWOK_BITMAP_H__
23 typedef uint64_t eword_t
;
24 #define BITS_IN_EWORD (sizeof(eword_t) * 8)
27 * Do not use __builtin_popcountll. The GCC implementation
28 * is notoriously slow on all platforms.
30 * See: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36041
32 static inline uint32_t ewah_bit_popcount64(uint64_t x
)
34 x
= (x
& 0x5555555555555555ULL
) + ((x
>> 1) & 0x5555555555555555ULL
);
35 x
= (x
& 0x3333333333333333ULL
) + ((x
>> 2) & 0x3333333333333333ULL
);
36 x
= (x
& 0x0F0F0F0F0F0F0F0FULL
) + ((x
>> 4) & 0x0F0F0F0F0F0F0F0FULL
);
37 return (x
* 0x0101010101010101ULL
) >> 56;
40 /* __builtin_ctzll was not available until 3.4.0 */
41 #if defined(__GNUC__) && (__GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR > 3))
42 #define ewah_bit_ctz64(x) __builtin_ctzll(x)
44 static inline int ewah_bit_ctz64(uint64_t x
)
47 if ((x
& 0xffffffff) == 0) { x
>>= 32; n
+= 32; }
48 if ((x
& 0xffff) == 0) { x
>>= 16; n
+= 16; }
49 if ((x
& 0xff) == 0) { x
>>= 8; n
+= 8; }
50 if ((x
& 0xf) == 0) { x
>>= 4; n
+= 4; }
51 if ((x
& 0x3) == 0) { x
>>= 2; n
+= 2; }
52 if ((x
& 0x1) == 0) { x
>>= 1; n
+= 1; }
65 typedef void (*ewah_callback
)(size_t pos
, void *);
67 struct ewah_bitmap
*ewah_pool_new(void);
68 void ewah_pool_free(struct ewah_bitmap
*self
);
71 * Allocate a new EWAH Compressed bitmap
73 struct ewah_bitmap
*ewah_new(void);
76 * Clear all the bits in the bitmap. Does not free or resize
79 void ewah_clear(struct ewah_bitmap
*self
);
82 * Free all the memory of the bitmap
84 void ewah_free(struct ewah_bitmap
*self
);
86 int ewah_serialize_to(struct ewah_bitmap
*self
,
87 int (*write_fun
)(void *out
, const void *buf
, size_t len
),
89 int ewah_serialize_native(struct ewah_bitmap
*self
, int fd
);
90 int ewah_serialize_strbuf(struct ewah_bitmap
*self
, struct strbuf
*);
92 int ewah_deserialize(struct ewah_bitmap
*self
, int fd
);
93 ssize_t
ewah_read_mmap(struct ewah_bitmap
*self
, const void *map
, size_t len
);
95 uint32_t ewah_checksum(struct ewah_bitmap
*self
);
98 * Call the given callback with the position of every single bit
99 * that has been set on the bitmap.
101 * This is an efficient operation that does not fully decompress
104 void ewah_each_bit(struct ewah_bitmap
*self
, ewah_callback callback
, void *payload
);
107 * Set a given bit on the bitmap.
109 * The bit at position `pos` will be set to true. Because of the
110 * way that the bitmap is compressed, a set bit cannot be unset
113 * Furthermore, since the bitmap uses streaming compression, bits
114 * can only set incrementally.
117 * ewah_set(bitmap, 1); // ok
118 * ewah_set(bitmap, 76); // ok
119 * ewah_set(bitmap, 77); // ok
120 * ewah_set(bitmap, 8712800127); // ok
121 * ewah_set(bitmap, 25); // failed, assert raised
123 void ewah_set(struct ewah_bitmap
*self
, size_t i
);
125 struct ewah_iterator
{
126 const eword_t
*buffer
;
130 eword_t compressed
, literals
;
136 * Initialize a new iterator to run through the bitmap in uncompressed form.
138 * The iterator can be stack allocated. The underlying bitmap must not be freed
139 * before the iteration is over.
143 * struct ewah_bitmap *bitmap = ewah_new();
144 * struct ewah_iterator it;
146 * ewah_iterator_init(&it, bitmap);
148 void ewah_iterator_init(struct ewah_iterator
*it
, struct ewah_bitmap
*parent
);
151 * Yield every single word in the bitmap in uncompressed form. This is:
152 * yield single words (32-64 bits) where each bit represents an actual
153 * bit from the bitmap.
155 * Return: true if a word was yield, false if there are no words left
157 int ewah_iterator_next(eword_t
*next
, struct ewah_iterator
*it
);
160 struct ewah_bitmap
*ewah_i
,
161 struct ewah_bitmap
*ewah_j
,
162 struct ewah_bitmap
*out
);
167 size_t ewah_add_empty_words(struct ewah_bitmap
*self
, int v
, size_t number
);
168 void ewah_add_dirty_words(
169 struct ewah_bitmap
*self
, const eword_t
*buffer
, size_t number
, int negate
);
170 size_t ewah_add(struct ewah_bitmap
*self
, eword_t word
);
174 * Uncompressed, old-school bitmap that can be efficiently compressed
175 * into an `ewah_bitmap`.
182 struct bitmap
*bitmap_new(void);
183 void bitmap_set(struct bitmap
*self
, size_t pos
);
184 int bitmap_get(struct bitmap
*self
, size_t pos
);
185 void bitmap_reset(struct bitmap
*self
);
186 void bitmap_free(struct bitmap
*self
);
187 int bitmap_equals(struct bitmap
*self
, struct bitmap
*other
);
188 int bitmap_is_subset(struct bitmap
*self
, struct bitmap
*super
);
190 struct ewah_bitmap
* bitmap_to_ewah(struct bitmap
*bitmap
);
191 struct bitmap
*ewah_to_bitmap(struct ewah_bitmap
*ewah
);
193 void bitmap_and_not(struct bitmap
*self
, struct bitmap
*other
);
194 void bitmap_or_ewah(struct bitmap
*self
, struct ewah_bitmap
*other
);
195 void bitmap_or(struct bitmap
*self
, const struct bitmap
*other
);
197 size_t bitmap_popcount(struct bitmap
*self
);