]> git.ipfire.org Git - thirdparty/git.git/blame - ewah/bitmap.c
Merge branch 'tb/diff-tree-with-notes'
[thirdparty/git.git] / ewah / bitmap.c
CommitLineData
e1273106
VM
1/**
2 * Copyright 2013, GitHub, Inc
3 * Copyright 2009-2013, Daniel Lemire, Cliff Moon,
4 * David McIntosh, Robert Becho, Google Inc. and Veronika Zenz
5 *
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.
10 *
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.
15 *
16 * You should have received a copy of the GNU General Public License
48425792 17 * along with this program; if not, see <http://www.gnu.org/licenses/>.
e1273106 18 */
08c95df8 19#include "cache.h"
e1273106
VM
20#include "ewok.h"
21
34b935c0
JK
22#define EWAH_MASK(x) ((eword_t)1 << (x % BITS_IN_EWORD))
23#define EWAH_BLOCK(x) (x / BITS_IN_EWORD)
e1273106 24
14fbd260 25struct bitmap *bitmap_word_alloc(size_t word_alloc)
e1273106 26{
fb7dbf3e 27 struct bitmap *bitmap = xmalloc(sizeof(struct bitmap));
14fbd260
JK
28 bitmap->words = xcalloc(word_alloc, sizeof(eword_t));
29 bitmap->word_alloc = word_alloc;
e1273106
VM
30 return bitmap;
31}
32
14fbd260
JK
33struct bitmap *bitmap_new(void)
34{
35 return bitmap_word_alloc(32);
36}
37
e1273106
VM
38void bitmap_set(struct bitmap *self, size_t pos)
39{
414382fb 40 size_t block = EWAH_BLOCK(pos);
e1273106
VM
41
42 if (block >= self->word_alloc) {
43 size_t old_size = self->word_alloc;
14fbd260 44 self->word_alloc = block ? block * 2 : 1;
08c95df8 45 REALLOC_ARRAY(self->words, self->word_alloc);
e1273106
VM
46 memset(self->words + old_size, 0x0,
47 (self->word_alloc - old_size) * sizeof(eword_t));
48 }
49
414382fb 50 self->words[block] |= EWAH_MASK(pos);
e1273106
VM
51}
52
cc4aa285
JK
53void bitmap_unset(struct bitmap *self, size_t pos)
54{
55 size_t block = EWAH_BLOCK(pos);
56
57 if (block < self->word_alloc)
58 self->words[block] &= ~EWAH_MASK(pos);
59}
60
e1273106
VM
61int bitmap_get(struct bitmap *self, size_t pos)
62{
414382fb 63 size_t block = EWAH_BLOCK(pos);
e1273106 64 return block < self->word_alloc &&
414382fb 65 (self->words[block] & EWAH_MASK(pos)) != 0;
e1273106
VM
66}
67
68struct ewah_bitmap *bitmap_to_ewah(struct bitmap *bitmap)
69{
70 struct ewah_bitmap *ewah = ewah_new();
71 size_t i, running_empty_words = 0;
72 eword_t last_word = 0;
73
74 for (i = 0; i < bitmap->word_alloc; ++i) {
75 if (bitmap->words[i] == 0) {
76 running_empty_words++;
77 continue;
78 }
79
80 if (last_word != 0)
81 ewah_add(ewah, last_word);
82
83 if (running_empty_words > 0) {
84 ewah_add_empty_words(ewah, 0, running_empty_words);
85 running_empty_words = 0;
86 }
87
88 last_word = bitmap->words[i];
89 }
90
91 ewah_add(ewah, last_word);
92 return ewah;
93}
94
95struct bitmap *ewah_to_bitmap(struct ewah_bitmap *ewah)
96{
97 struct bitmap *bitmap = bitmap_new();
98 struct ewah_iterator it;
99 eword_t blowup;
100 size_t i = 0;
101
102 ewah_iterator_init(&it, ewah);
103
104 while (ewah_iterator_next(&blowup, &it)) {
08c95df8 105 ALLOC_GROW(bitmap->words, i + 1, bitmap->word_alloc);
e1273106
VM
106 bitmap->words[i++] = blowup;
107 }
108
109 bitmap->word_alloc = i;
110 return bitmap;
111}
112
113void bitmap_and_not(struct bitmap *self, struct bitmap *other)
114{
115 const size_t count = (self->word_alloc < other->word_alloc) ?
116 self->word_alloc : other->word_alloc;
117
118 size_t i;
119
120 for (i = 0; i < count; ++i)
121 self->words[i] &= ~other->words[i];
122}
123
124void bitmap_or_ewah(struct bitmap *self, struct ewah_bitmap *other)
125{
126 size_t original_size = self->word_alloc;
34b935c0 127 size_t other_final = (other->bit_size / BITS_IN_EWORD) + 1;
e1273106
VM
128 size_t i = 0;
129 struct ewah_iterator it;
130 eword_t word;
131
132 if (self->word_alloc < other_final) {
133 self->word_alloc = other_final;
08c95df8 134 REALLOC_ARRAY(self->words, self->word_alloc);
e1273106
VM
135 memset(self->words + original_size, 0x0,
136 (self->word_alloc - original_size) * sizeof(eword_t));
137 }
138
139 ewah_iterator_init(&it, other);
140
141 while (ewah_iterator_next(&word, &it))
142 self->words[i++] |= word;
143}
144
e1273106
VM
145size_t bitmap_popcount(struct bitmap *self)
146{
147 size_t i, count = 0;
148
149 for (i = 0; i < self->word_alloc; ++i)
150 count += ewah_bit_popcount64(self->words[i]);
151
152 return count;
153}
154
155int bitmap_equals(struct bitmap *self, struct bitmap *other)
156{
157 struct bitmap *big, *small;
158 size_t i;
159
160 if (self->word_alloc < other->word_alloc) {
161 small = self;
162 big = other;
163 } else {
164 small = other;
165 big = self;
166 }
167
168 for (i = 0; i < small->word_alloc; ++i) {
169 if (small->words[i] != big->words[i])
170 return 0;
171 }
172
173 for (; i < big->word_alloc; ++i) {
174 if (big->words[i] != 0)
175 return 0;
176 }
177
178 return 1;
179}
180
181void bitmap_reset(struct bitmap *bitmap)
182{
183 memset(bitmap->words, 0x0, bitmap->word_alloc * sizeof(eword_t));
184}
185
186void bitmap_free(struct bitmap *bitmap)
187{
188 if (bitmap == NULL)
189 return;
190
191 free(bitmap->words);
192 free(bitmap);
193}