]>
git.ipfire.org Git - thirdparty/git.git/blob - ewah/bitmap.c
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_word_alloc(size_t word_alloc
)
27 struct bitmap
*bitmap
= xmalloc(sizeof(struct bitmap
));
28 bitmap
->words
= xcalloc(word_alloc
, sizeof(eword_t
));
29 bitmap
->word_alloc
= word_alloc
;
33 struct bitmap
*bitmap_new(void)
35 return bitmap_word_alloc(32);
38 void bitmap_set(struct bitmap
*self
, size_t pos
)
40 size_t block
= EWAH_BLOCK(pos
);
42 if (block
>= self
->word_alloc
) {
43 size_t old_size
= self
->word_alloc
;
44 self
->word_alloc
= block
? block
* 2 : 1;
45 REALLOC_ARRAY(self
->words
, self
->word_alloc
);
46 memset(self
->words
+ old_size
, 0x0,
47 (self
->word_alloc
- old_size
) * sizeof(eword_t
));
50 self
->words
[block
] |= EWAH_MASK(pos
);
53 int bitmap_get(struct bitmap
*self
, size_t pos
)
55 size_t block
= EWAH_BLOCK(pos
);
56 return block
< self
->word_alloc
&&
57 (self
->words
[block
] & EWAH_MASK(pos
)) != 0;
60 struct ewah_bitmap
*bitmap_to_ewah(struct bitmap
*bitmap
)
62 struct ewah_bitmap
*ewah
= ewah_new();
63 size_t i
, running_empty_words
= 0;
64 eword_t last_word
= 0;
66 for (i
= 0; i
< bitmap
->word_alloc
; ++i
) {
67 if (bitmap
->words
[i
] == 0) {
68 running_empty_words
++;
73 ewah_add(ewah
, last_word
);
75 if (running_empty_words
> 0) {
76 ewah_add_empty_words(ewah
, 0, running_empty_words
);
77 running_empty_words
= 0;
80 last_word
= bitmap
->words
[i
];
83 ewah_add(ewah
, last_word
);
87 struct bitmap
*ewah_to_bitmap(struct ewah_bitmap
*ewah
)
89 struct bitmap
*bitmap
= bitmap_new();
90 struct ewah_iterator it
;
94 ewah_iterator_init(&it
, ewah
);
96 while (ewah_iterator_next(&blowup
, &it
)) {
97 ALLOC_GROW(bitmap
->words
, i
+ 1, bitmap
->word_alloc
);
98 bitmap
->words
[i
++] = blowup
;
101 bitmap
->word_alloc
= i
;
105 void bitmap_and_not(struct bitmap
*self
, struct bitmap
*other
)
107 const size_t count
= (self
->word_alloc
< other
->word_alloc
) ?
108 self
->word_alloc
: other
->word_alloc
;
112 for (i
= 0; i
< count
; ++i
)
113 self
->words
[i
] &= ~other
->words
[i
];
116 void bitmap_or_ewah(struct bitmap
*self
, struct ewah_bitmap
*other
)
118 size_t original_size
= self
->word_alloc
;
119 size_t other_final
= (other
->bit_size
/ BITS_IN_EWORD
) + 1;
121 struct ewah_iterator it
;
124 if (self
->word_alloc
< other_final
) {
125 self
->word_alloc
= other_final
;
126 REALLOC_ARRAY(self
->words
, self
->word_alloc
);
127 memset(self
->words
+ original_size
, 0x0,
128 (self
->word_alloc
- original_size
) * sizeof(eword_t
));
131 ewah_iterator_init(&it
, other
);
133 while (ewah_iterator_next(&word
, &it
))
134 self
->words
[i
++] |= word
;
137 size_t bitmap_popcount(struct bitmap
*self
)
141 for (i
= 0; i
< self
->word_alloc
; ++i
)
142 count
+= ewah_bit_popcount64(self
->words
[i
]);
147 int bitmap_equals(struct bitmap
*self
, struct bitmap
*other
)
149 struct bitmap
*big
, *small
;
152 if (self
->word_alloc
< other
->word_alloc
) {
160 for (i
= 0; i
< small
->word_alloc
; ++i
) {
161 if (small
->words
[i
] != big
->words
[i
])
165 for (; i
< big
->word_alloc
; ++i
) {
166 if (big
->words
[i
] != 0)
173 void bitmap_reset(struct bitmap
*bitmap
)
175 memset(bitmap
->words
, 0x0, bitmap
->word_alloc
* sizeof(eword_t
));
178 void bitmap_free(struct bitmap
*bitmap
)